Training Set Theory & Logic Propositional Logic & Truth Tables
2 / 5

Propositional Logic & Truth Tables

24 min Set Theory & Logic
Propositional logic studies statements (propositions) that are either true or false, and how they combine through connectives: NOT (¬), AND (∧), OR (∨), IMPLIES (→), and IF-AND-ONLY-IF (↔). A truth table systematically lists every combination of truth values for the component propositions and evaluates the compound statement. Two statements are logically equivalent when their truth tables match in every row—for example, ¬(p ∧ q) ≡ (¬p ∨ ¬q) is De Morgan's law. A tautology is always true regardless of inputs; a contradiction is always false. Recognizing logical equivalences simplifies proofs, circuit design, and database query optimization.

Propositional Logic & Truth Tables

Proposition

A statement that is either true (T) or false (F), but not both.

Logical Connectives
  • Negation: $\lnot p$ — "not $p$"
  • Conjunction: $p \land q$ — "$p$ and $q$"
  • Disjunction: $p \lor q$ — "$p$ or $q$"
  • Conditional: $p \to q$ — "if $p$ then $q$"
  • Biconditional: $p \leftrightarrow q$ — "$p$ if and only if $q$"
Conditional $p \to q$

False only when $p$ is true and $q$ is false. Logically equivalent to $\lnot p \lor q$.

Example 1

Build a truth table for $p \land (\lnot q)$.

$p$$q$$\lnot q$$p \land \lnot q$
TTFF
TFTT
FTFF
FFTF
Example 2

Show $p \to q \equiv \lnot p \lor q$ by truth table.

  1. Both columns match for all 4 rows of input, confirming logical equivalence.
Example 3

Is $(p \lor q) \land (\lnot p)$ a tautology?

  1. When $p = T, q = F$:
  2. $(T \lor F) \land F = F$.
  3. Not a tautology.

Practice Problems

1. Build a truth table for $p \lor q$.
2. Truth table for $p \to q$.
3. What is the negation of "All cats are black"?
4. Is $p \land \lnot p$ a contradiction?
5. Converse of $p \to q$?
6. Contrapositive of $p \to q$?
7. Truth table for $p \leftrightarrow q$.
8. Is $p \lor \lnot p$ a tautology?
9. Write in symbols: "If it rains, the ground is wet."
10. Negate: $p \land q$.
11. How many rows in a truth table with 3 variables?
12. Simplify: $\lnot(\lnot p)$.
Show Answer Key

1. F only when both F

2. F only when T→F

3. "There exists a cat that is not black."

4. Yes

5. $q \to p$

6. $\lnot q \to \lnot p$

7. T when both same, F when different

8. Yes (law of excluded middle)

9. $r \to w$

10. $\lnot p \lor \lnot q$ (De Morgan)

11. $2^3 = 8$

12. $p$ (double negation)

📋 Truth Table Builder
p=T, q=T
p=T, q=F
p=F, q=T
p=F, q=F
Classification
Sets & Set Operations Quantifiers & Predicate Logic