Logical Connectives

Why This Matters

Logical connectives are the grammar of formal reasoning. They're how you build complex statements from simple propositions and determine when arguments are valid. To work with them well, you need to recognize how connectives behave under different truth conditions, translate natural language into symbolic form, and manipulate compound statements in proofs. The concepts here, truth functionality, logical equivalence, and functional completeness, show up repeatedly in truth tables, derivations, and equivalence proofs.

Don't just memorize symbols and definitions. Know why each connective produces its truth values, how connectives relate to each other through equivalences, and which connectives can express others. When you encounter a proof or translation problem, you need to instantly recognize which connective captures the logical relationship, and that comes from understanding the underlying principles.

---

Basic Truth-Functional Connectives

These are your foundational tools. Each one takes propositions as inputs and outputs a truth value determined entirely by the truth values of those inputs. That's what makes them truth-functional: the output depends on nothing beyond the input truth values.

Negation (NOT)

• Flips the truth value: if $P$ is true, $\neg P$ is false, and vice versa
• Symbolized by $\neg$ or $\sim$; the only unary connective (it operates on just one proposition)
• Essential for contradiction and indirect proof. Negating a conclusion is how reductio ad absurdum arguments begin.

Conjunction (AND)

• True only when both conjuncts are true. This makes it the most restrictive binary connective: out of four possible truth-value combinations, only one row comes out true.
• Symbolized by $\wedge$; $P \wedge Q$ requires both $P$ and $Q$ to hold simultaneously
• Order doesn't matter (commutativity: $P \wedge Q \equiv Q \wedge P$), which simplifies proof strategies

Disjunction (OR)

• True when at least one disjunct is true. This is inclusive OR, meaning both being true still counts.
• Symbolized by $\vee$; $P \vee Q$ is false only when both $P$ and $Q$ are false
• Key for disjunctive syllogism: if you know $P \vee Q$ and $\neg P$, you can derive $Q$

---

Conditional Connectives

These connectives express relationships of dependency and equivalence between propositions. Mastering the conditional is arguably the single most important skill in formal logic.

Conditional (IF-THEN)

• False only when the antecedent is true and the consequent is false. That's the one defining truth condition to internalize.
• Symbolized by $\rightarrow$; $P \rightarrow Q$ means "if $P$, then $Q$"
• Equivalent to $\neg P \vee Q$. This equivalence is worth committing to memory because it unlocks many proof techniques: you can always rewrite a conditional as a disjunction with a negated antecedent.

Biconditional (IF AND ONLY IF)

• True when both propositions share the same truth value: both true or both false
• Symbolized by $\leftrightarrow$; $P \leftrightarrow Q$ asserts that $P$ and $Q$ match in truth value within that context
• Equivalent to $(P \rightarrow Q) \wedge (Q \rightarrow P)$. To prove a biconditional, you prove implication in both directions.

---

Exclusive and Negated Connectives

These connectives are defined in terms of the basic ones but appear frequently enough to warrant their own symbols. They're especially relevant for understanding logical relationships and, in applied contexts, circuit design.

Exclusive OR (XOR)

• True when exactly one proposition is true. Unlike inclusive OR, both being true yields false.
• Symbolized by $\oplus$; $P \oplus Q$ captures "either...or...but not both"
• Equivalent to $(P \vee Q) \wedge \neg(P \wedge Q)$. You can think of this as inclusive disjunction minus the overlap case.

NAND (NOT AND)

• True unless both propositions are true. It's simply the negation of conjunction.
• Symbolized by $\uparrow$ (Sheffer stroke); $P \uparrow Q \equiv \neg(P \wedge Q)$
• Functionally complete on its own: every truth function can be expressed using only NAND (more on this below)

NOR (NOT OR)

• True only when both propositions are false. It's the negation of disjunction.
• Symbolized by $\downarrow$ (Peirce arrow); $P \downarrow Q \equiv \neg(P \vee Q)$
• Also functionally complete on its own, just like NAND

---

Functional Completeness and Expressive Power

A set of connectives is functionally complete if it can define every possible truth function. Understanding which sets are complete matters for proofs, logical system design, and recognizing when a system has full expressive power.

Sheffer Stroke (NAND)

The Sheffer stroke is just another notation for NAND: $P \mid Q$ is true unless both $P$ and $Q$ are true. What makes it significant is how it can build every other connective from scratch:

1. Express negation: $\neg P \equiv P \mid P$ (NAND a proposition with itself)
2. Express conjunction: $P \wedge Q \equiv (P \mid Q) \mid (P \mid Q)$ (NAND the result with itself to flip it back)
3. From negation and conjunction, you can derive everything else. That's why a single connective qualifies as a universal basis.

Material Implication

• Another name for the standard conditional, emphasizing its purely truth-functional definition
• Distinguished from "strict" implication in modal logic, which requires a necessary connection between antecedent and consequent
• The so-called "paradoxes of material implication" arise because a false antecedent makes any conditional true. For instance, $P \rightarrow Q$ is true whenever $P$ is false, regardless of $Q$. This is technically correct by the truth table but can feel counterintuitive.

---

Quick Reference Table

---

Self-Check Questions

1. Which two connectives are both individually functionally complete, and how do their truth tables differ?

2. The conditional $P \rightarrow Q$ is logically equivalent to which combination of negation and disjunction? Why does this equivalence matter for proofs?

3. Compare inclusive disjunction ($\vee$) and exclusive disjunction ($\oplus$). Under what truth-value assignment do they differ?

4. If you needed to express $\neg P$ using only the Sheffer stroke, how would you do it? What about expressing $P \wedge Q$?

5. A statement is true when both propositions have the same truth value and false otherwise. Which connective is this, and how does it relate to the conditional?