Compound Statements, Logical Connectives, and Truth Tables

Simple vs compound statements. A simple (atomic) statement cannot be broken into smaller statements. A compound (molecular) statement is built from two or more simple statements. Example: "1 is not a prime number and Ooty is in Kerala" is compound, built from $p$: "1 is not a prime number" and $q$: "Ooty is in Kerala." Any simple statement, taking only the values $T$ or $F$, can be treated like a variable -- a statement (propositional) variable, usually named $p,q,r,\ldots$

Definition 12.9 (Logical Connectives). Words such as "and", "or", "if-then", "if and only if" and "not" that join simple statements into compound ones are logical connectives. The three basic ones are negation (not), conjunction (and) and disjunction (or).

Definition 12.10. An expression built from one or more statements joined by connectives is a statement formula.

Definition 12.11 (Truth Table). A table showing, for every combination of truth values of the component simple statements, the resulting truth value of the compound statement is a truth table.

Definition 12.12 -- the three basic connectives:

1. Negation, $\neg p$ ("not $p$"): truth value opposite to $p$ -- $\neg p$ is $T$ when $p$ is $F$, and $F$ when $p$ is $T$.
2. Conjunction, $p\wedge q$ ("$p$ and $q$", read "$p$ hat $q$"): $T$ exactly when both $p$ and $q$ are $T$; $F$ otherwise.
3. Disjunction, $p\vee q$ ("$p$ or $q$", read "$p$ cup $q$"): $F$ exactly when both $p$ and $q$ are $F$; $T$ otherwise (the inclusive or). Truth tables for the three:

Example 12.12 (worked pattern). With $p$: "It is cold" and $q$: "It is raining": $\neg p$ = "It is not cold"; $p\wedge q$ = "It is cold and raining"; $p\vee q$ = "It is cold or raining"; $q\vee\neg p$ = "It is raining or it is not cold."

Row count. A formula in $p$ alone has $2^1=2$ rows; a formula in two variables like $p\wedge q$ or $p\vee q$ has $2^2=4$ rows. In general, a formula with $n$ distinct variables has $2^n$ rows -- e.g. $3$ variables give $2^3=8$ rows, $6$ variables give $2^6=64$ rows.

Conditional statement.

Definition 12.13. The conditional statement "if $p$, then $q$", written $p\to q$, calls $p$ the hypothesis (antecedent) and $q$ the conclusion (consequent). $p\to q$ is $F$ only when $p$ is $T$ and $q$ is $F$; otherwise it is $T$.

Example 12.14 (worked pattern). For $p\to q$: "If today is Monday, then $4+4=8$" -- here $q$ ("$4+4=8$") is $T$, so $p\to q$ is $T$ regardless of what day it actually is; $p\to q$ is judged purely by the truth values of $p,q$, never by whether they are related in meaning.

Three statements derived from $p\to q$: the converse $q\to p$, the inverse $\neg p\to\neg q$, and the contrapositive $\neg q\to\neg p$.

Example 12.15 (worked pattern). For $p$: "The number of primes is infinite" and $q$: "Ooty is in Kerala": conditional $p\to q$ = "If the number of primes is infinite then Ooty is in Kerala"; converse $q\to p$ = "If Ooty is in Kerala then the number of primes is infinite"; inverse $\neg p\to\neg q$ = "If the number of primes is not infinite then Ooty is not in Kerala"; contrapositive $\neg q\to\neg p$ = "If Ooty is not in Kerala then the number of primes is not infinite."

Biconditional statement.

Definition 12.14. The biconditional "$p$ if and only if $q$", written $p\leftrightarrow q$, is $T$ whenever $p$ and $q$ share the same truth value, and $F$ otherwise. …