Logical Connectives

The connectives $\neg, \wedge, \vee$ are the semantic bedrock of every subsequent tool in Truth Tables and in the study of The Conditional Statement, since all compound propositions in classical logic can be built from these three (together, later, with the conditional and biconditional, themselves definable in terms of $\neg,\wedge,\vee$). Beyond pure logic, these same operations appear, essentially unchanged, as:

• Digital circuit design and computer engineering, where AND-gates, OR-gates, and NOT-gates (inverters) are physical devices implementing exactly the truth tables above, and where the algebraic laws proved here (associativity, distributivity, De Morgan's laws) are the rules used daily to simplify circuits and reduce gate counts.
• Programming languages, where `&&`, `||`, and `!` (or `and`, `or`, `not`) implement these connectives, often with "short-circuit evaluation" that exploits exactly the asymmetry noted in Example 1 — once one operand of `&&` is false, the language need not evaluate the rest.
• Set theory, where $\wedge$ and $\vee$ correspond to intersection and union of sets, and De Morgan's laws for propositions become De Morgan's laws for sets ($(A \cap B)^c = A^c \cup B^c$), an exact structural mirror exploited throughout mathematics.
• Database query languages (SQL), where `WHERE` clause conditions are combined with `AND`/`OR`/`NOT`, and query optimizers apply De Morgan's laws and distributivity to rewrite queries into equivalent, faster forms.
• Cryptography and coding theory, where XOR (exclusive or, contrasted in the counterexample above) is a fundamental building block of stream ciphers and error-correcting codes, precisely because it lacks some of the algebraic properties of inclusive $\vee$ and instead satisfies its own useful laws (e.g., self-inverse: $p \oplus p \oplus q = q$).
• Statistics and probability, where events combined by "and"/"or" correspond to intersections and unions of event sets, and inclusion–exclusion formulas for probabilities trace back to the same $\vee$/$\wedge$ structure.

Ask the tutor: How do these three connectives combine with the conditional ($\to$) to let us define every possible truth-functional connective?

The three connectives can be pictured as operations on a two-element set $\{T, F\}$, much like arithmetic operations act on numbers. Negation is a unary operation — a single "switch" that swaps the two elements of $\{T,F\}$. Conjunction and disjunction are binary operations, each taking an ordered pair from $\{T,F\}^2$ (four possible pairs) to a single value in $\{T,F\}$. A useful mental picture: think of $T$ and $F$ as the numbers $1$ and $0$. Then conjunction behaves exactly like multiplication ($p \wedge q$ corresponds to $\min(p,q)$, or equivalently the product when values are $0/1$), and disjunction behaves like a "capped" addition ($p \vee q$ corresponds to $\max(p,q)$). Negation is $1 - p$. This is not a coincidence — it reflects the fact that $\wedge$ and $\vee$ are, respectively, the meet and join operations of the two-element Boolean lattice $\{F, T\}$ ordered by $F < T$, a structure you will meet again when connectives are studied algebraically. The figure below shows this lattice: $F$ at the bottom, $T$ at the top, with $\wedge$ moving toward the bottom (the stronger requirement — both must hold) and $\vee$ moving toward the top (the weaker requirement — either suffices).

There is also an important asymmetry to internalize: conjunction is demanding — a single false conjunct poisons the whole statement — while disjunction is forgiving — a single true disjunct rescues the whole statement. This asymmetry is exactly why De Morgan's laws (proved below) swap $\wedge$ and $\vee$ when negation is pushed through: negating a demanding statement produces a forgiving one, and vice versa.

Example 1 — a three-variable compound with mismatched components. Let

Here $S$ is true, $Q$ is false, $R$ is true (three propositions chosen to have deliberately different, non-symmetric truth values). Evaluate

Work from the innermost connectives outward, exactly as with arithmetic order of operations. Step 1: $\neg Q$. Since $Q$ is false, $\neg Q$ is true. Step 2: $S \wedge \neg Q$. Both $S$ (true) and $\neg Q$ (true) are true, so by the conjunction table (row $T,T \mapsto T$), $S \wedge \neg Q$ is true. Step 3: $\neg S$. Since $S$ is true, $\neg S$ is false. Step 4: $\neg S \wedge R$. Here $\neg S$ is false, so regardless of $R$'s value, by the conjunction table (any row with an $F$ input gives $F$), $\neg S \wedge R$ is false. Step 5: $X = (S\wedge \neg Q) \vee (\neg S \wedge R) = T \vee F$. By the disjunction table (row $T, F \mapsto T$), $X$ is true. Notice the compound is true only because of the first disjunct; the second disjunct is entirely false, and disjunction's inclusivity means one true disjunct suffices — this is precisely the demanding/forgiving asymmetry pictured above. Notice also this compound would remain true even if $R$ were false, illustrating that once a disjunct is settled false, its remaining internal structure ($R$'s truth value) becomes irrelevant to the outcome — a fact you will use routinely to shortcut truth-table computations in Truth Tables.

Example 2 — verifying a De Morgan instance on concrete number-theoretic propositions. Let $n = 15$, and define

Since $15 = 3 \times 5$ is odd, $A$ is false. Since $15 = 3\times 5$, $B$ is true. Consider the compound "$n$ is not divisible by both $2$ and $3$," symbolized $\neg(A \wedge B)$, and compare it to "$n$ is not divisible by $2$, or $n$ is not divisible by $3$," symbolized $\neg A \vee \neg B$. De Morgan's law asserts these are equivalent statements; let's confirm directly for $n=15$ rather than relying only on the abstract table. First, $A \wedge B$: since $A$ is false, by the conjunction table $A \wedge B$ is false ($15$ is not divisible by both $2$ and $3$ — correct, since it isn't even divisible by $2$). So $\neg(A\wedge B)$ is true. Second, $\neg A$: since $A$ is false, $\neg A$ is true ("$15$ is not divisible by $2$" — true). Then $\neg A \vee \neg B$: since $\neg A$ is already true, by the disjunction table the whole disjunction is true regardless of $\neg B$'s value ("$15$ is not divisible by $2$, or [anything]" is true just from the first disjunct). Both $\neg(A\wedge B)$ and $\neg A \vee \neg B$ come out true for $n = 15$, matching De Morgan's law. To see the law is not a coincidence of this particular $n$, repeat with $n = 12$: now $A$ (divisible by 2) is true and $B$ (divisible by 3) is true, so $A \wedge B$ is true, so $\neg(A\wedge B)$ is false; and $\neg A$ is false, $\neg B$ is false, so $\neg A \vee \neg B$ is false by the disjunction table (only row giving $F$ is $F,F$) — again matching. The theorem guarantees this match for every possible pair of truth values, which is exactly why it was proved once, abstractly, by exhaustive case analysis, rather than checked example-by-example forever.