6.1 Propositions, Connectives, Truth Tables & Logical Equivalences

Back to Discrete Mathematics Notes

📚Module 06: Propositional Logic & Inference RulesTopic 6.1: Propositions, Connectives, Truth Tables & Equivalences⏱️5 min read

🎯High-Yield For:Semester Exams • GATE CSE • Technical Interviews

💡 Core Intuition: The 3-Second Mental Model

🍳 The Everyday Analogy: Light Switches & Legal Contracts

Think of propositional logic like electrical circuits and binding legal contracts:

1. The Proposition (Unambiguous Fact): "The server is running." It is either 100% True ($T$) or 100% False ($F$). There is zero middle ground, no "maybe," and no rhetorical questions.
2. Compound Connectives:
   • Conjunction (AND $\land$): Two switches in series. Current flows only if switch 1 AND switch 2 are closed.
   • Disjunction (OR $\lor$): Two switches in parallel. Current flows if either switch is closed.
   • Implication (IF-THEN $\to$): A conditional contract: "If you pay me $100, I will deliver the laptop." The contract is breached (False) in only one single scenario: you paid the $100, but I failed to deliver the laptop! If you never paid me, the contract was never violated, regardless of whether I gave you a laptop or not (Vacuous Truth).
3. Tautology vs Contradiction:
   • Tautology: A statement wired so it is impossible to turn off ($p \lor \neg p$: "It is raining or it is not raining").
   • Contradiction: A short circuit wired so it can never turn on ($p \land \neg p$: "It is raining and it is not raining").

💻 Bridging to Computer Science: Boolean Circuits, Branching & SAT Solvers

In computer systems:

• CPU Control Units & ALU: Processors evaluate propositional logic at gigahertz clock rates using silicon logic gates (NAND, NOR, XOR).
• Control Flow & Branch Prediction: If-statements if (A && !B || C) are compound propositional formulas evaluated via short-circuit evaluation.
• SAT Solvers (Z3, MiniSat): Automated theorem provers and hardware verification engines solve the Boolean Satisfiability Problem (SAT) to verify microchip designs and formal software specifications.

📑Table of Contents

• ⚡ Propositions & The Classical Laws of Thought
• 🔌 Compound Logical Connectives & Master Truth Tables
  • Master Truth Table of Binary Connectives
• 🔢 Truth Tables & Counting Boolean Functions
  • Master Inventory of All 16 Binary Truth Functions (n = 2)
• ⚖️ Classifying Propositional Formulas
• 🧰 Functionally Complete Sets of Connectives
  • Expressing Fundamental Connectives using Universal Gates
• 🏛️ System of Fundamental Logical Equivalences
• 📝 Step-by-Step Worked Examples
  • Example 1: Proving a Tautology via Truth Table & Logical Equivalence
  • Example 2: Verifying Functional Completeness of Implication and Falsehood
  • Example 3: Determining Satisfiability of a Compound Formula
• 🎯 Exam & Interview Pitfall Check

---

⚡ Propositions & The Classical Laws of Thought

📖Definition 6.1: Propositiondefinition

A proposition (or statement) is a declarative sentence that is either True ($T$) or False ($F$), but not both simultaneously.

• Valid Propositions:
  • "New Delhi is the capital of India" ($T$).
  • "$5 \le 11$" ($T$).
  • "Paris is the capital of USA" ($F$).
  • "In any simple undirected graph, $\sum \deg(v) = 2\vert E\vert$" ($T$).
• Sentences that are NOT Propositions:
  • "$x + y = z$" (Open mathematical predicate; truth value depends on unquantified variables $x, y, z$).
  • "How are you?" (Interrogative question; carries no truth value).
  • "Read this carefully!" (Imperative command).
  • "It is cold today" (Subjective / vague statement without an objective threshold).
  • "This statement is false" (The Liar Paradox; self-referential contradiction).

📐Theorem 6.1: The Two Foundational Laws of Classical Logictheorem

In standard bivalent propositional logic, all propositions obey two fundamental axioms:

1. Law of Non-Contradiction (LNC): A proposition cannot be both True and False simultaneously in the same sense: $$\neg(P \land \neg P) \equiv \mathbf{T}$$
2. Law of Excluded Middle (LEM): Every proposition must be either True or its negation must be True; there is no third intermediate truth value: $$P \lor \neg P \equiv \mathbf{T}$$

---

🔌 Compound Logical Connectives & Master Truth Tables

The 6 Core Propositional Connectives & Operational Rules

Formal mathematical symbols, operational mechanics, and English semantics

🚫

Negation (¬p / ~p)

NOT Operator

• Inverts truth value: ¬T = F, ¬F = T.
• Unary operator with the highest binding precedence.
• English: 'It is not the case that p', 'Not p'.

🤝

Conjunction (p ∧ q)

AND Operator

• True if and only if BOTH p and q are True.
• False if at least one operand is False.
• English: 'p and q', 'p but q', 'p as well as q'.

🔀

Disjunction (p ∨ q)

Inclusive OR

• True if AT LEAST ONE operand (p, q, or both) is True.
• False ONLY when BOTH operands are False.
• English: 'p or q (or both)'.

⚡

Exclusive OR (p ⊕ q)

XOR Operator

• True when p and q have DIFFERENT truth values.
• False when both are True or both are False.
• Formal: (p ∨ q) ∧ ¬(p ∧ q).

➡️

Conditional (p → q)

Implication

• p is Hypothesis (Antecedent); q is Conclusion (Consequent).
• False ONLY when p = T and q = F. True in all other 3 cases!
• Equivalence: p → q ≡ ¬p ∨ q.

🔄

Biconditional (p ↔ q)

Equivalence (XNOR)

• True if and only if p and q have IDENTICAL truth values.
• Formal: (p → q) ∧ (q → p) ≡ (p ∧ q) ∨ (¬p ∧ ¬q).
• English: 'p if and only if q' (iff).

Master Truth Table of Binary Connectives

$p$	$q$	$\neg p$	$p \land q$	$p \lor q$	$p \oplus q$	$p \to q$	$p \leftrightarrow q$
$T$	$T$	$F$	$T$	$T$	$F$	$T$	$T$
$T$	$F$	$F$	$F$	$T$	$T$	$F$	$F$
$F$	$T$	$T$	$F$	$T$	$T$	$T$	$F$
$F$	$F$	$T$	$F$	$F$	$F$	$T$	$T$

Operator Precedence Hierarchy in Logic

Binding order when evaluating unparenthesized propositional expressions

Precedence 1 (Highest)

Negation (¬ / ~)

1️⃣

Binds immediately to its adjacent propositional variable.

↓Next Highest Precedence

Precedence 2

Conjunction (∧)

2️⃣

Evaluated before disjunctions and conditionals.

↓Next Highest Precedence

Precedence 3

Disjunction (∨)

3️⃣

Evaluated after conjunctions.

↓Next Highest Precedence

Precedence 4

Conditional Implication (→)

4️⃣

Evaluated after all Boolean operations.

↓Lowest Precedence

Precedence 5 (Lowest)

Biconditional (↔)

5️⃣

Lowest binding affinity across the entire expression.

---

🔢 Truth Tables & Counting Boolean Functions

📐Theorem 6.2: Propositional Truth Table & Function Countstheorem

Let $n$ be the number of distinct propositional variables:

1. Number of Rows in Truth Table: Each variable has $2$ possible truth assignments ($T$ or $F$). Thus, a truth table over $n$ variables has: $$\text{Total Rows} = 2^n$$
2. Total Number of Distinct Truth Functions: A truth function assigns either $T$ or $F$ to each of the $2^n$ rows. Thus, the total number of distinct Boolean truth functions of $n$ variables is: $$\text{Total Distinct Functions} = 2^{2^n}$$
   • For $n = 1$: $2^{2^1} = 2^2 = 4$ functions ($\mathbf{F}$, $p$, $\neg p$, $\mathbf{T}$).
   • For $n = 2$: $2^{2^2} = 2^4 = 16$ distinct binary functions!

Master Inventory of All 16 Binary Truth Functions (n = 2)

Index	$TT$	$TF$	$FT$	$FF$	Common Mathematical Name	Symbolic Form	Operational Meaning
0	$F$	$F$	$F$	$F$	Contradiction (False)	$\mathbf{0} / \mathbf{F}$	Null function
1	$F$	$F$	$F$	$T$	Joint Denial (NOR)	$p \downarrow q$	Peirce arrow $\neg(p \lor q)$
2	$F$	$F$	$T$	$F$	Converse Non-Implication	$\neg p \land q$	$q$ but not $p$
3	$F$	$F$	$T$	$T$	Negation of $p$	$\neg p$	Inverts $p$
4	$F$	$T$	$F$	$F$	Non-Implication	$p \land \neg q$	$\neg(p \to q)$
5	$F$	$T$	$F$	$T$	Negation of $q$	$\neg q$	Inverts $q$
6	$F$	$T$	$T$	$F$	Exclusive OR (XOR)	$p \oplus q$	Different truth values
7	$F$	$T$	$T$	$T$	Alternative Denial (NAND)	$p \uparrow q$	Sheffer stroke $\neg(p \land q)$
8	$T$	$F$	$F$	$F$	Conjunction (AND)	$p \land q$	Both True
9	$T$	$F$	$F$	$T$	Biconditional (XNOR)	$p \leftrightarrow q$	Identical truth values
10	$T$	$F$	$T$	$F$	Projection $q$	$q$	Identity of $q$
11	$T$	$F$	$T$	$T$	Conditional Implication	$p \to q$	$\neg p \lor q$
12	$T$	$T$	$F$	$F$	Projection $p$	$p$	Identity of $p$
13	$T$	$T$	$F$	$T$	Converse Implication	$q \to p$	$p \lor \neg q$
14	$T$	$T$	$T$	$F$	Disjunction (OR)	$p \lor q$	At least one True
15	$T$	$T$	$T$	$T$	Tautology (True)	$\mathbf{1} / \mathbf{T}$	Universal True

---

⚖️ Classifying Propositional Formulas

📖Definition 6.2: Tautology, Contradiction, Contingency & Satisfiabilitydefinition

Let $P(p_1, p_2, \dots, p_n)$ be a compound proposition constructed from $n$ propositional variables:

1. Tautology (Valid): Evaluates to True ($T$) in every single row of its truth table ($2^n$ True entries).
   • Canonical example: $p \lor \neg p$ (Law of Excluded Middle).
2. Contradiction (Unsatisfiable / Fallacy): Evaluates to False ($F$) in every single row of its truth table ($2^n$ False entries).
   • Canonical example: $p \land \neg p$ (Law of Non-Contradiction).
3. Contingency: Evaluates to True for at least one truth assignment AND False for at least one truth assignment (neither tautology nor contradiction).
   • Canonical example: $p \to q$, $p \lor q$.
4. Satisfiable: A compound proposition is satisfiable if there exists at least one truth assignment that makes the formula True ($T$). $$\text{Satisfiable Formulas} = \text{Tautologies} \cup \text{Contingencies}$$ $$\text{Unsatisfiable Formulas} \equiv \text{Contradictions}$$

Propositional Formula Taxonomy: Tautology vs Contradiction vs Contingency

Partitioning all Boolean formulas by truth table output columns

Tautology (Valid)

Always True (100% T)

🌟

Dominant Architecture / DomainUniversal Validity

• •Every row evaluates to True.
• •Negation of a tautology is a Contradiction: ¬(Tautology) ≡ Contradiction.
• •Core SAT status: Automatically Satisfiable.

"Holds True in all possible mathematical universes."

Contradiction

Always False (100% F)

💥

Dominant Architecture / DomainUnsatisfiability

• •Every row evaluates to False.
• •Negation of a contradiction is a Tautology: ¬(Contradiction) ≡ Tautology.
• •Core SAT status: Strictly Unsatisfiable.

"Cannot be satisfied by any physical assignment."

Contingency

Mixed Truth Values (Some T, Some F)

⚖️

Dominant Architecture / DomainConditional Reality

• •Contains at least one T and at least one F.
• •Negation of a contingency is always another Contingency!
• •Core SAT status: Satisfiable (not a tautology).

"Truth value depends entirely on variable assignments."

---

🧰 Functionally Complete Sets of Connectives

📖Definition 6.3: Functional Completenessdefinition

A set of logical connectives is functionally complete if and only if every possible Boolean truth function (all $2^{2^n}$ functions for any $n$) can be expressed using only the connectives in that set.

1. Standard Complete Pairs:
   • $\{\neg, \land\}$: Since $p \lor q \equiv \neg(\neg p \land \neg q)$ and $p \to q \equiv \neg(p \land \neg q)$.
   • $\{\neg, \lor\}$: Since $p \land q \equiv \neg(\neg p \lor \neg q)$ and $p \to q \equiv \neg p \lor q$.
   • $\{\neg, \to\}$: Since $p \lor q \equiv \neg p \to q$ and $p \land q \equiv \neg(p \to \neg q)$.
2. Universal Singletons (Minimal Sets of Size 1):
   • NAND ($\uparrow$, Sheffer Stroke): Alone forms a complete set!
   • NOR ($\downarrow$, Peirce Arrow): Alone forms a complete set!
3. Incomplete Sets:
   • $\{\land, \lor\}$: Incomplete! Cannot express $\neg p$ because any formula using only $\land$ and $\lor$ is monotone (if all inputs are $T$, output is strictly $T$; cannot invert $T$ to $F$).
   • $\{\neg, \leftrightarrow\}$ or $\{\neg, \oplus\}$: Incomplete! Affine / linear functions only; cannot express non-linear conjunction $p \land q$.

Expressing Fundamental Connectives using Universal Gates

Target Operation	Using ONLY NAND ($\uparrow$)	Gate Count	Using ONLY NOR ($\downarrow$)	Gate Count
NOT ($\neg p$)	$p \uparrow p$	1	$p \downarrow p$	1
AND ($p \land q$)	$(p \uparrow q) \uparrow (p \uparrow q)$	2	$(p \downarrow p) \downarrow (q \downarrow q)$	3
OR ($p \lor q$)	$(p \uparrow p) \uparrow (q \uparrow q)$	3	$(p \downarrow q) \downarrow (p \downarrow q)$	2
Conditional ($p \to q$)	$p \uparrow (q \uparrow q)$	2	$((p \downarrow p) \downarrow q) \downarrow ((p \downarrow p) \downarrow q)$	4
Biconditional ($p \leftrightarrow q$)	$(p \uparrow q) \uparrow ((p \uparrow p) \uparrow (q \uparrow q))$	4	$((p \downarrow q) \downarrow (p \downarrow q)) \downarrow ((p \downarrow p) \downarrow (q \downarrow q))$	4

---

🏛️ System of Fundamental Logical Equivalences

Two compound propositions $P$ and $Q$ are logically equivalent (denoted $P \equiv Q$ or $P \Leftrightarrow Q$) if and only if $P \leftrightarrow Q$ is a tautology.

⚡Law 6.1: Master Inventory of Logical Equivalenceslaw

Law Name	Conjunction Form ($\land$)	Disjunction Form ($\lor$)
Identity Laws	$p \land \mathbf{T} \equiv p$	$p \lor \mathbf{F} \equiv p$
Domination Laws	$p \land \mathbf{F} \equiv \mathbf{F}$	$p \lor \mathbf{T} \equiv \mathbf{T}$
Idempotent Laws	$p \land p \equiv p$	$p \lor p \equiv p$
Double Negation	$\neg(\neg p) \equiv p$	—
Commutative Laws	$p \land q \equiv q \land p$	$p \lor q \equiv q \lor p$
Associative Laws	$(p \land q) \land r \equiv p \land (q \land r)$	$(p \lor q) \lor r \equiv p \lor (q \lor r)$
Distributive Laws	$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$	$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
De Morgan's Laws	$\neg(p \land q) \equiv \neg p \lor \neg q$	$\neg(p \lor q) \equiv \neg p \land \neg q$
Absorption Laws	$p \land (p \lor q) \equiv p$	$p \lor (p \land q) \equiv p$
Negation Laws	$p \land \neg p \equiv \mathbf{F}$	$p \lor \neg p \equiv \mathbf{T}$

⚡Law 6.2: Conditional & Biconditional Equivalenceslaw

1. Conditional Implication Law: $$p \to q \equiv \neg p \lor q$$
2. Negation of Conditional: $$\neg(p \to q) \equiv \neg(\neg p \lor q) \equiv p \land \neg q$$
3. Contrapositive Law: $$p \to q \equiv \neg q \to \neg p$$
4. Exportation Law: $$(p \land q) \to r \equiv p \to (q \to r)$$
5. Biconditional Decomposition: $$p \leftrightarrow q \equiv (p \to q) \land (q \to p) \equiv (\neg p \lor q) \land (\neg q \lor p) \equiv (p \land q) \lor (\neg p \land \neg q)$$
6. Negation of Biconditional (XOR): $$\neg(p \leftrightarrow q) \equiv p \oplus q \equiv (p \land \neg q) \lor (\neg p \land q)$$

---

📝 Step-by-Step Worked Examples

Example 1: Proving a Tautology via Truth Table & Logical Equivalence

Problem Statement: Prove that $[(p \to q) \land p] \to q$ is a tautology (the classical Modus Ponens tautology):

1. Using a complete Truth Table.
2. Using algebraic logical equivalences.

Step-by-Step Solution:

1. Step 1: Truth Table Verification

$p$	$q$	$p \to q$	$(p \to q) \land p$	$[(p \to q) \land p] \to q$
$T$	$T$	$T$	$T$	$T$
$T$	$F$	$F$	$F$	$T$
$F$	$T$	$T$	$F$	$T$
$F$	$F$	$T$	$F$	$T$

Every entry in the final column is $T$. Thus, the statement is a Tautology.

2. Step 2: Algebraic Verification
   • Apply the Implication Law to $p \to q$: $$[(p \to q) \land p] \to q \equiv [(\neg p \lor q) \land p] \to q$$
   • Distribute $p$ over $(\neg p \lor q)$: $$[(\neg p \land p) \lor (q \land p)] \to q$$
   • By the Negation Law, $\neg p \land p \equiv \mathbf{F}$: $$[\mathbf{F} \lor (q \land p)] \to q \equiv (p \land q) \to q$$
   • Apply the Implication Law to $(p \land q) \to q$: $$\neg(p \land q) \lor q$$
   • Apply De Morgan's Law: $$(\neg p \lor \neg q) \lor q$$
   • Use Associativity to group $\neg q \lor q$: $$\neg p \lor (\neg q \lor q) \equiv \neg p \lor \mathbf{T} \equiv \mathbf{T}$$
   • The expression reduces strictly to $\mathbf{T}$, proving it is a tautology!

Key Takeaway: Algebraic reductions using De Morgan and the Implication Law eliminate the need for $2^n$-row truth tables when verifying tautologies.

---

Example 2: Verifying Functional Completeness of Implication and Falsehood

Problem Statement: Determine whether the set of connectives $\{\to, \mathbf{F}\}$ is functionally complete.

Step-by-Step Solution:

1. Recall the Criteria: A set is functionally complete if it can express $\{\neg, \land\}$ or $\{\neg, \lor\}$.
2. Can we express Negation ($\neg p$)?
   • In truth tables, when $q = \mathbf{F}$, $p \to \mathbf{F}$ evaluates to:
     • $T \to F = F$
     • $F \to F = T$
   • Thus: $$\neg p \equiv p \to \mathbf{F}$$
   • Negation is successfully expressed using only $\to$ and $\mathbf{F}$!
3. Can we express Disjunction ($p \lor q$)?
   • Recall $p \to q \equiv \neg p \lor q$.
   • Replacing $p$ with $\neg p$: $$\neg p \to q \equiv \neg(\neg p) \lor q \equiv p \lor q$$
   • Substituting our formula for $\neg p$: $$p \lor q \equiv (p \to \mathbf{F}) \to q$$
   • Disjunction is successfully expressed!
4. Conclusion: Since both $\neg$ and $\lor$ are expressible, $\{\to, \mathbf{F}\}$ is strictly functionally complete!

---

Example 3: Determining Satisfiability of a Compound Formula

Problem Statement: Determine whether the formula $\phi = (p \lor q) \land (\neg p \lor \neg q) \land (p \lor \neg q) \land (\neg p \lor q)$ is satisfiable.

Step-by-Step Solution:

1. Step 1: Simplify First Pair of Clauses

   • Clause 1: $(p \lor q)$
   • Clause 2: $(\neg p \lor \neg q)$
   • Together, $(p \lor q) \land (\neg p \lor \neg q)$ is the exact definition of Exclusive OR ($p \oplus q$)!
   • This requires $p$ and $q$ to have different truth values:
     • Case A: $p = T, q = F$
     • Case B: $p = F, q = T$

2. Step 2: Simplify Second Pair of Clauses

   • Clause 3: $(p \lor \neg q) \equiv q \to p$
   • Clause 4: $(\neg p \lor q) \equiv p \to q$
   • Together, $(p \to q) \land (q \to p)$ is the exact definition of Biconditional ($p \leftrightarrow q$)!
   • This requires $p$ and $q$ to have identical truth values:
     • Case 1: $p = T, q = T$
     • Case 2: $p = F, q = F$

3. Step 3: Combine Requirements

   • The overall formula is: $$\phi \equiv (p \oplus q) \land (p \leftrightarrow q)$$
   • Since $p \oplus q \equiv \neg(p \leftrightarrow q)$, this is equivalent to: $$\neg(p \leftrightarrow q) \land (p \leftrightarrow q) \equiv \mathbf{F}$$
   • The formula is a Contradiction!
   • Because no assignment can ever make it True, $\phi$ is Unsatisfiable.

Key Takeaway: Recognizing macro-equivalences (like XOR and Biconditional) allows instant unsatisfiability detection without testing all truth assignments.

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

Question 1: If an implication $p \to q$ is True, does that mean $p$ caused $q$? Key Focus Points: No! Propositional implication ($p \to q$) is a material conditional, NOT causal or temporal. For example, "If $2 + 2 = 4$, then Paris is in France" is 100% True in formal logic because both antecedent and consequent are True ($T \to T = T$), even though mathematics does not cause French geography!

Question 2: What is "Vacuous Truth"? Key Focus Points: When the antecedent $p$ is False, the implication $p \to q$ is automatically True ($F \to T = T$ and $F \to F = T$), regardless of the truth value of $q$. For example, "If pigs can fly, then $1 = 2$" is a True statement in propositional logic because pigs cannot fly ($p = F$).

Common Interview Traps: Architectural Trade-Offs

Trap 1: Confusing Inclusive OR with Exclusive OR Why it fails: In everyday English, "Do you want coffee or tea?" implies Exclusive OR (pick one, not both). In mathematical logic, $p \lor q$ is strictly Inclusive OR: it is True if both $p$ and $q$ are True! Always assume inclusive OR unless $\oplus$ is explicitly specified.

Trap 2: Forgetting the Negation of an Implication Why it fails: Students frequently write $\neg(p \to q) \equiv p \to \neg q$. This is completely wrong! By the Implication Law: $\neg(p \to q) \equiv \neg(\neg p \lor q) \equiv p \land \neg q$. The negation of an implication is an AND statement, not another implication!

Trap 3: Believing that $\{\land, \lor\}$ is Functionally Complete Why it fails: Connectives $\{\land, \lor\}$ can never invert a truth value from $T$ to $F$! Any circuit built purely with AND and OR gates outputs $1$ whenever all inputs are $1$ (Monotone boolean property). Negation ($\neg$) or an inverting gate is strictly mandatory for functional completeness.

🗺️View Complete Discrete Mathematics Roadmap & Syllabus

← Previous Topic5.3 Cosets, Normal Subgroups, Rings, Integral Domains & FieldsNext Topic →6.2 Implications: Converse, Inverse, Contrapositive & Normal Forms (CNF/DNF)