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. You're being tested on your ability 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 see a proof or translation problem, you need to instantly recognize which connective captures the logical relationship—and that comes from understanding the underlying principles, not rote recall.

---

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—this is what makes them truth-functional.

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 (operates on one proposition)
• Essential for contradiction and indirect proof—negating conclusions is how reductio arguments begin

Conjunction (AND)

• True only when both conjuncts are true—the most restrictive binary connective
• 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, allowing both to be true
• 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 most important skill in formal logic.

Conditional (IF-THEN)

• False only when the antecedent is true and consequent is false—this is the defining truth condition
• Symbolized by $\rightarrow$; $P \rightarrow Q$ means "if $P$, then $Q$"
• Equivalent to $\neg P \vee Q$—understanding this equivalence unlocks many proof techniques

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$ means $P$ and $Q$ are logically equivalent in that context
• Equivalent to $(P \rightarrow Q) \wedge (Q \rightarrow P)$—proves equivalence by showing 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 important for understanding logical relationships and 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)$—disjunction minus the overlap

NAND (NOT AND)

• True unless both propositions are true—the negation of conjunction
• Symbolized by $\uparrow$ (Sheffer stroke); $P \uparrow Q \equiv \neg(P \wedge Q)$
• Functionally complete alone—every truth function can be expressed using only NAND

NOR (NOT OR)

• True only when both propositions are false—the negation of disjunction
• Symbolized by $\downarrow$ (Peirce arrow); $P \downarrow Q \equiv \neg(P \vee Q)$
• Also functionally complete alone—like NAND, can express all other connectives

---

Functional Completeness and Expressive Power

Some connectives can define all others—this property is called functional completeness. Understanding which sets of connectives are complete is essential for proofs and logical system design.

Sheffer Stroke (NAND)

• Identical to NAND—$P | Q$ is true unless both $P$ and $Q$ are true
• Can express negation: $\neg P \equiv P | P$; self-NANDing yields negation
• Can express conjunction: $P \wedge Q \equiv (P | Q) | (P | Q)$—making it a universal connective

Material Implication

• Another name for the standard conditional—emphasizes its truth-functional definition
• Distinguished from "strict" implication in modal logic, which requires necessary connection
• The "paradoxes of material implication"—a false antecedent makes any conditional true, which can seem 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 and contrast inclusive disjunction ($\vee$) and exclusive disjunction ($\oplus$)—under what truth value assignments 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?