2.4 Logical connectives

Basic logical connectives

Logical connectives let you combine simple true/false statements into more complex ones. They're the glue that holds mathematical arguments together, and you'll use them constantly when writing proofs or analyzing whether an argument is valid.

There are five connectives you need to know. Each one has a specific symbol, a specific meaning, and a truth table that tells you exactly when the result is true or false.

Conjunction (AND)

Conjunction, written as $\wedge$, combines two statements and is true only when both statements are true. Think of it as a strict requirement: both parts must hold.

• $A \wedge B$ is true when A is true AND B is true
• $A \wedge B$ is false in all other cases (if either A or B is false, the whole thing is false)

For example, "x is even $\wedge$ x is positive" is only true for numbers like 2, 4, 6... A number like -4 is even but not positive, so the conjunction is false.

In set theory, conjunction corresponds to intersection: $A \cap B$ contains elements that belong to A and B.

Disjunction (OR)

Disjunction, written as $\vee$, is true when at least one of the statements is true. This is the inclusive OR, meaning it's also true when both are true.

• $A \vee B$ is false only when both A and B are false
• $A \vee B$ is true in every other case

This differs from exclusive OR ($\oplus$), which is true when exactly one statement is true but not both. In math, unless stated otherwise, "or" means inclusive or.

In set theory, disjunction corresponds to union: $A \cup B$ contains elements in A, in B, or in both.

Negation (NOT)

Negation, written as $\neg$ (or sometimes $\sim$), simply flips the truth value of a statement.

• If A is true, then $\neg A$ is false
• If A is false, then $\neg A$ is true

Negation is the simplest connective since it operates on just one statement. It plays a central role in proof by contradiction (assume $\neg P$, derive a contradiction, conclude P) and in forming contrapositives.

Implication (IF-THEN)

Implication, written as $\rightarrow$ or $\Rightarrow$, expresses a conditional relationship: "if A, then B." This one trips up a lot of students because of how it handles false antecedents.

• $A \rightarrow B$ is false only when A is true and B is false
• $A \rightarrow B$ is true in all other cases, including when A is false

Why is it true when A is false? Think of it as a promise: "If it rains, I'll bring an umbrella." If it doesn't rain, you haven't broken your promise regardless of whether you bring an umbrella. The implication is only violated when the condition holds (it rains) but the result doesn't follow (no umbrella).

In this connective, A is called the antecedent (the "if" part) and B is the consequent (the "then" part). Most mathematical theorems take this form.

Biconditional (IF AND ONLY IF)

The biconditional, written as $\leftrightarrow$ or $\Leftrightarrow$, means both directions of implication hold simultaneously. It's true when both statements share the same truth value.

• $A \leftrightarrow B$ is true when A and B are both true, or both false
• $A \leftrightarrow B$ is false when A and B have different truth values

This is equivalent to $(A \rightarrow B) \wedge (B \rightarrow A)$. You'll see "if and only if" (often abbreviated "iff") in mathematical definitions, where it establishes that two conditions are truly equivalent.

Truth tables

Truth tables give you a systematic way to determine the truth value of any compound statement. For every possible combination of inputs, you calculate the output. No guesswork involved.

Construction of truth tables

To build a truth table:

1. Identify all distinct propositions (variables) in the statement.
2. Determine the number of rows: $2^n$ where n is the number of propositions. Two variables give 4 rows; three give 8.
3. List every possible combination of T (true) and F (false) for those propositions.
4. Add columns for intermediate sub-expressions, working from the inside out.
5. Fill in the final column, which represents the truth value of the entire compound statement.

For example, to evaluate $(A \wedge B) \rightarrow C$ with three propositions, you'd need $2^3 = 8$ rows, a column for $A \wedge B$, and then a final column for the full implication.

Evaluating compound statements

When a statement has multiple connectives, evaluate them according to precedence (covered below). Use parentheses to make the order explicit. Work through intermediate columns step by step, left to right, until you reach the final result.

Tautologies and contradictions

• A tautology is a statement that's true in every row of its truth table. Example: $A \vee \neg A$ is always true.
• A contradiction is a statement that's false in every row. Example: $A \wedge \neg A$ is always false.
• A statement that is neither is called a contingency, meaning its truth value depends on the inputs.

Recognizing tautologies is especially useful because they represent logical laws you can always rely on.

Properties of logical connectives

These properties let you rearrange and simplify logical expressions, much like algebraic rules let you manipulate equations.

Commutativity

The order of operands doesn't matter for conjunction and disjunction:

• $A \wedge B \equiv B \wedge A$
• $A \vee B \equiv B \vee A$

Implication is not commutative. $A \rightarrow B$ and $B \rightarrow A$ are different statements (the second is the converse of the first).

Associativity

You can regroup operands without changing the result for conjunction and disjunction:

• $(A \wedge B) \wedge C \equiv A \wedge (B \wedge C)$
• $(A \vee B) \vee C \equiv A \vee (B \vee C)$

This means when you chain together multiple ANDs or multiple ORs, parentheses don't matter.

Distributivity

Conjunction and disjunction distribute over each other, similar to how multiplication distributes over addition in algebra:

• $A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)$
• $A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C)$

Note that the second form (OR distributing over AND) doesn't have a direct parallel in regular algebra, so it can feel unfamiliar at first.

De Morgan's laws

These laws tell you how to negate compound statements by "pushing" the negation inward and flipping the connective:

• $\neg(A \wedge B) \equiv \neg A \vee \neg B$ (not both → at least one is false)
• $\neg(A \vee B) \equiv \neg A \wedge \neg B$ (not either → both are false)

De Morgan's laws come up constantly. Whenever you need to negate a compound statement in a proof, these are your go-to tools.

Compound statements

Forming complex propositions

You build compound statements by connecting simple propositions with logical connectives. Start simple and add complexity one connective at a time. For instance:

• Start with propositions P ("x is prime") and Q ("x is odd")
• Form $P \wedge Q$ ("x is prime and x is odd")
• Add R ("x > 2") to get $(P \wedge Q) \rightarrow R$

Always use parentheses to make your intended grouping explicit, especially when mixing different connectives.

Precedence of logical operators

When parentheses are absent, evaluate connectives in this order (highest precedence first):

1. $\neg$ (Negation)
2. $\wedge$ (Conjunction)
3. $\vee$ (Disjunction)
4. $\rightarrow$ (Implication)
5. $\leftrightarrow$ (Biconditional)

So $\neg A \wedge B \vee C$ is read as $((\neg A) \wedge B) \vee C$. This is analogous to PEMDAS in arithmetic. When in doubt, add parentheses.

Parentheses for clarity

Even when precedence rules technically make the meaning unambiguous, parentheses improve readability. Compare:

• $\neg A \wedge B \rightarrow C \vee D$
• $(\neg A \wedge B) \rightarrow (C \vee D)$

The second version is immediately clear. In mathematical writing, clarity always wins over brevity.

Logical equivalence

Two statements are logically equivalent if they produce identical truth values for every possible assignment of their variables. Logical equivalence is a relationship about statements, not a connective within a statement.

Definition and notation

• Logical equivalence is denoted by $\equiv$ (or sometimes $\Leftrightarrow$ in metalogical contexts)
• This differs from the biconditional $\leftrightarrow$, which is a connective inside a formula. The distinction: $A \leftrightarrow B$ is itself a statement that can be true or false, while $A \equiv B$ is a claim that A and B always have the same truth value.
• Two statements are equivalent precisely when their truth tables have identical final columns.

Proving logical equivalence

You can prove two statements are logically equivalent in two main ways:

1. Truth table method: Build truth tables for both statements and verify that every row matches.
2. Algebraic method: Start with one statement and apply known equivalences (De Morgan's laws, distributivity, etc.) step by step until you arrive at the other statement.

The algebraic method is usually faster for complex expressions, while truth tables provide a guaranteed mechanical check.

Common equivalent forms

These equivalences are worth memorizing since they come up repeatedly:

• Double negation: $\neg\neg A \equiv A$
• Commutativity: $A \wedge B \equiv B \wedge A$, and $A \vee B \equiv B \vee A$
• Associativity: $(A \wedge B) \wedge C \equiv A \wedge (B \wedge C)$, and $(A \vee B) \vee C \equiv A \vee (B \vee C)$
• Distributivity: $A \wedge (B \vee C) \equiv (A \wedge B) \vee (A \wedge C)$, and $A \vee (B \wedge C) \equiv (A \vee B) \wedge (A \vee C)$
• De Morgan's laws: $\neg(A \wedge B) \equiv \neg A \vee \neg B$, and $\neg(A \vee B) \equiv \neg A \wedge \neg B$
• Implication equivalence: $A \rightarrow B \equiv \neg A \vee B \equiv \neg(A \wedge \neg B)$

That last one is particularly useful. It lets you rewrite any implication in terms of OR and NOT, which can simplify proofs and truth table work.

Applications in mathematics

Conditional statements in theorems

Most theorems take the form "If P, then Q" ($P \rightarrow Q$). Three related statements are worth knowing:

• Contrapositive: $\neg Q \rightarrow \neg P$ — logically equivalent to the original, so proving the contrapositive proves the theorem
• Converse: $Q \rightarrow P$ — not equivalent to the original; must be proved separately
• Inverse: $\neg P \rightarrow \neg Q$ — not equivalent to the original (but is equivalent to the converse)

The biconditional $P \leftrightarrow Q$ establishes that P is a necessary and sufficient condition for Q. To prove it, you must prove both directions: $P \rightarrow Q$ and $Q \rightarrow P$.

Quantifiers and connectives

Quantifiers and connectives interact in specific patterns:

• The universal quantifier ($\forall$) often pairs with implication: "For all x, if x is a dog, then x is a mammal" → $\forall x (D(x) \rightarrow M(x))$
• The existential quantifier ($\exists$) often pairs with conjunction: "There exists an x such that x is prime and x is even" → $\exists x (P(x) \wedge E(x))$

A common mistake is pairing $\forall$ with $\wedge$ or $\exists$ with $\rightarrow$ when translating from English. Pay attention to which pairing matches the intended meaning.

The order of quantifiers also matters: $\forall x \exists y$ ("for every x there's some y") is very different from $\exists y \forall x$ ("there's a single y that works for every x").

Negation of complex statements

To negate quantified statements, flip the quantifier and negate the predicate:

• $\neg(\forall x\, P(x)) \equiv \exists x\, \neg P(x)$
• $\neg(\exists x\, P(x)) \equiv \forall x\, \neg P(x)$

For compound predicates, apply De Morgan's laws after flipping the quantifier. For example:

$\neg(\forall x\, (P(x) \rightarrow Q(x)))$ $\equiv \exists x\, \neg(P(x) \rightarrow Q(x))$ $\equiv \exists x\, (P(x) \wedge \neg Q(x))$

That last step uses the equivalence $\neg(A \rightarrow B) \equiv A \wedge \neg B$. This technique is essential for proof by contradiction.

Boolean algebra

Boolean algebra extends logical connectives into an algebraic system, and it's the mathematical foundation for digital circuits and computer science.

Relationship to logical connectives

The correspondence is direct:

All the properties you've learned (commutativity, associativity, distributivity, De Morgan's laws) carry over directly into Boolean algebra.

Boolean functions

Boolean functions map Boolean inputs to Boolean outputs. They can be represented as truth tables, algebraic expressions, or logic gate diagrams.

Beyond the basic AND, OR, and NOT, common composite functions include:

• XOR (exclusive or): true when inputs differ
• NAND (not-and): the negation of AND
• NOR (not-or): the negation of OR

A key fact: any Boolean function can be built using only NAND gates (or only NOR gates). This property is called functional completeness and is why NAND gates are so important in chip design.

Simplification of Boolean expressions

Simplifying Boolean expressions reduces the number of operations (and in hardware, the number of logic gates). Useful laws include:

• Absorption: $A \vee (A \wedge B) = A$ and $A \wedge (A \vee B) = A$
• Idempotent: $A \wedge A = A$ and $A \vee A = A$
• Complement: $A \wedge \neg A = 0$ and $A \vee \neg A = 1$

For more complex expressions, Karnaugh maps provide a visual grouping method, and the Quine-McCluskey algorithm offers a systematic approach. Both aim to find the simplest equivalent expression.

Logical inference

Logical inference is how you derive new true statements from ones you already know. It's the engine behind every mathematical proof.

Valid vs. invalid arguments

An argument is valid if the conclusion must be true whenever all the premises are true. Validity is about the structure of the argument, not whether the premises are actually true in the real world.

An argument is sound if it's both valid and its premises are actually true. Soundness is the stronger condition.

An invalid argument has a logical structure that allows true premises to lead to a false conclusion. Even if the conclusion happens to be true, the argument is still invalid if the form doesn't guarantee it.

Modus ponens and modus tollens

These are the two most fundamental inference rules:

Modus ponens (affirming the antecedent):

1. $P \rightarrow Q$ (if P then Q)
2. $P$ (P is true)
3. Therefore, $Q$ (Q must be true)

Modus tollens (denying the consequent):

1. $P \rightarrow Q$ (if P then Q)
2. $\neg Q$ (Q is false)
3. Therefore, $\neg P$ (P must be false)

Modus ponens drives direct proofs. Modus tollens drives proofs by contraposition. Both are valid, and you'll rely on them constantly.

Fallacies in reasoning

Fallacies are argument forms that look convincing but are logically invalid. The two most important for this course:

• Affirming the consequent: "If P then Q. Q is true. Therefore P." This is invalid. Knowing $P \rightarrow Q$ and Q doesn't tell you P is true, because Q could be true for other reasons.
• Denying the antecedent: "If P then Q. P is false. Therefore Q is false." Also invalid. The implication says nothing about what happens when P is false.

Other common fallacies (false dichotomy, ad hominem, appeal to authority) appear more in informal reasoning, but recognizing the two formal fallacies above is critical for evaluating mathematical arguments.

Connectives in natural language

Translating between logic and English

Complex sentences may need multiple connectives. Break them into simple propositions first, identify the logical relationships, then assemble the formal expression.

Ambiguities in everyday language

Natural language is full of logical traps:

• "Or" ambiguity: "You can have soup or salad" usually means exclusive or, but "Students who study math or physics may apply" usually means inclusive or. Logic defaults to inclusive.
• "If" ambiguity: In conversation, "if" often implies "if and only if." Saying "I'll go if you go" usually means both directions, but in logic, $A \rightarrow B$ is strictly one-directional.
• Negation scope: "It's not the case that A and B" ($\neg(A \wedge B)$) is different from "not-A and not-B" ($\neg A \wedge \neg B$). People often confuse these in everyday speech.

Precision in mathematical statements

Formal logic exists precisely to eliminate these ambiguities. In mathematical writing:

• Use symbols and quantifiers explicitly rather than relying on context
• Define all terms before using them
• Use parentheses to make logical grouping unambiguous
• Translate natural language claims into formal logic before attempting a proof

The ability to move fluently between English and logical notation is one of the most practical skills you'll develop in this course.