Introduction
Propositional logic is the foundation of formal reasoning. It deals with propositions (statements that are true or false) and the logical operators that combine them.
Understanding propositional logic is essential for:
- Mathematics: Constructing proofs and logical arguments
- Computer Science: Programming conditionals, Boolean expressions, circuit design
- Philosophy: Analyzing arguments and logical reasoning
- Artificial Intelligence: Knowledge representation and automated reasoning
- Formal Verification: Proving software and hardware correctness
This comprehensive guide explores propositional logic operators, truth tables, and the systematic evaluation of logical expressions.
Propositions and Propositional Variables
What is a Proposition?
A proposition is a declarative statement that is either true or false, but not both.
Key Characteristics:
- Declarative: It makes a statement (not a question or command)
- Definite: It has a definite truth value (true or false)
- Unambiguous: Its meaning is clear and precise
Examples of Propositions
Valid Propositions:
- “Paris is the capital of France” (True)
- “2 + 2 = 5” (False)
- “The Earth orbits the Sun” (True)
- “All humans are immortal” (False)
Not Propositions:
- “What time is it?” (Question - no truth value)
- “Close the door!” (Command - no truth value)
- “This sentence is false” (Paradox - cannot be consistently assigned a truth value)
- “x + 5 = 10” (Open sentence - truth depends on x)
- “She is tall” (Vague - no clear criterion for truth)
Propositional Variables
In propositional logic, we use variables to represent propositions.
Notation: Lowercase letters: p, q, r, s, t, …
Example:
p = "It is raining"
q = "The ground is wet"
r = "I have an umbrella"
Truth Values:
- T or 1 represents true
- F or 0 represents false
Logical Operators (Connectives)
Logical operators combine propositions to create compound propositions. There are five fundamental operators.
1. Negation (NOT) - ¬
Symbol: ¬p (also written as ~p, -p, or NOT p)
Meaning: “Not p” or “It is not the case that p”
Definition: Negation reverses the truth value of a proposition.
Truth Table:
| p | ¬p |
|---|---|
| T | F |
| F | T |
Examples:
- p = “It is raining” → ¬p = “It is not raining”
- p = “5 > 3” (True) → ¬p = “5 ≤ 3” (False)
- p = “All birds can fly” (False) → ¬p = “Not all birds can fly” (True)
Properties:
- Double Negation: ¬(¬p) ≡ p (negating twice returns to the original)
- Self-Contradiction: p ∧ ¬p is always false
- Excluded Middle: p ∨ ¬p is always true
2. Conjunction (AND) - ∧
Symbol: p ∧ q (also written as p & q, p · q, or p AND q)
Meaning: “p and q” (both p and q must be true)
Definition: A conjunction is true only when both components are true.
Truth Table:
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Key Point: Only one row (T, T) produces true.
Examples:
- “It is raining AND the ground is wet”
- “5 > 3 AND 2 is even” (True ∧ True = True)
- “5 > 3 AND 2 is odd” (True ∧ False = False)
- “5 < 3 AND 2 is even” (False ∧ True = False)
Properties:
- Commutative: p ∧ q ≡ q ∧ p (order doesn’t matter)
- Associative: (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) (grouping doesn’t matter)
- Idempotent: p ∧ p ≡ p (combining with itself gives itself)
- Identity: p ∧ T ≡ p (true is the identity element)
- Domination: p ∧ F ≡ F (false dominates)
3. Disjunction (OR) - ∨
Symbol: p ∨ q (also written as p | q, p + q, or p OR q)
Meaning: “p or q” (at least one of p or q is true, possibly both)
Definition: A disjunction is true when at least one component is true.
Truth Table:
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Key Point: Only one row (F, F) produces false. This is inclusive OR (allows both to be true).
Examples:
- “I will study math OR physics” (could study both)
- “5 > 3 OR 2 is even” (True ∨ True = True)
- “5 > 3 OR 2 is odd” (True ∨ False = True)
- “5 < 3 OR 2 is odd” (False ∨ False = False)
Properties:
- Commutative: p ∨ q ≡ q ∨ p
- Associative: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
- Idempotent: p ∨ p ≡ p
- Identity: p ∨ F ≡ p (false is the identity element)
- Domination: p ∨ T ≡ T (true dominates)
Exclusive OR (XOR):
In everyday language, “or” sometimes means “one or the other, but not both” (exclusive OR).
Symbol: p ⊕ q
Truth Table:
| p | q | p ⊕ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Relationship: p ⊕ q ≡ (p ∨ q) ∧ ¬(p ∧ q)
4. Implication (IF-THEN) - →
Symbol: p → q (also written as p ⊃ q, p ⇒ q, or IF p THEN q)
Meaning: “If p, then q” or “p implies q”
Components:
- p is the antecedent (the “if” part)
- q is the consequent (the “then” part)
Definition: An implication is false only when the antecedent is true and the consequent is false.
Truth Table:
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Key Point: When p is false, p → q is true regardless of q (vacuously true).
Examples:
- “If it rains, then the ground gets wet”
- “If 2 + 2 = 5, then pigs can fly” (True, because the hypothesis is false)
- “If x > 5, then x > 3” (True for all x)
Important Variations:
-
Converse: q → p (switching antecedent and consequent)
- Original: “If it rains, then the ground is wet”
- Converse: “If the ground is wet, then it rained” (NOT equivalent!)
-
Inverse: ¬p → ¬q (negating both parts)
- Original: “If it rains, then the ground is wet”
- Inverse: “If it doesn’t rain, then the ground is not wet” (NOT equivalent!)
-
Contrapositive: ¬q → ¬p (switching and negating)
- Original: “If it rains, then the ground is wet”
- Contrapositive: “If the ground is not wet, then it didn’t rain” (EQUIVALENT!)
Key Equivalences:
- p → q ≡ ¬p ∨ q (implication as disjunction)
- p → q ≡ ¬q → ¬p (contrapositive equivalence)
- ¬(p → q) ≡ p ∧ ¬q (negation of implication)
5. Biconditional (IF AND ONLY IF) - ↔
Symbol: p ↔ q (also written as p ≡ q, p ⇔ q, or p IFF q)
Meaning: “p if and only if q” (p and q have the same truth value)
Definition: A biconditional is true when both components have the same truth value.
Truth Table:
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Key Point: True when both are true or both are false.
Examples:
- “A triangle is equilateral if and only if all its sides are equal”
- “x = 0 if and only if x² = 0 and x ≥ 0”
- “It is raining if and only if the ground is wet” (only if rain is the only cause)
Equivalent Expression:
p ↔ q ≡ (p → q) ∧ (q → p)
This means: p implies q AND q implies p.
Properties:
- Commutative: p ↔ q ≡ q ↔ p
- Associative: (p ↔ q) ↔ r ≡ p ↔ (q ↔ r)
- Reflexive: p ↔ p ≡ T (always true)
Operator Precedence
When multiple operators appear in a formula, we need to know which to apply first.
Precedence (highest to lowest):
- ¬ (Negation) - highest
- ∧ (Conjunction)
- ∨ (Disjunction)
- → (Implication)
- ↔ (Biconditional) - lowest
Examples:
p ∧ q ∨ r means (p ∧ q) ∨ r, not p ∧ (q ∨ r)
¬p ∧ q means (¬p) ∧ q, not ¬(p ∧ q)
p → q ∨ r means p → (q ∨ r), not (p → q) ∨ r
Best Practice: Use parentheses to make your meaning clear, even when not strictly necessary.
Constructing Truth Tables
Step-by-Step Process
Step 1: Identify all propositional variables
Step 2: Determine the number of rows: 2ⁿ where n is the number of variables
Step 3: List all possible combinations of truth values
Step 4: Add columns for each sub-expression
Step 5: Calculate truth values from innermost to outermost operations
Example 1: Simple Expression
Formula: p ∧ ¬q
Variables: p, q (2 variables → 4 rows)
Truth Table:
| p | q | ¬q | p ∧ ¬q |
|---|---|---|---|
| T | T | F | F |
| T | F | T | T |
| F | T | F | F |
| F | F | T | F |
Example 2: Complex Expression
Formula: (p ∧ q) → r
Variables: p, q, r (3 variables → 8 rows)
Truth Table:
| p | q | r | p ∧ q | (p ∧ q) → r |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | F |
| T | F | T | F | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | T | F | F | T |
| F | F | T | F | T |
| F | F | F | F | T |
Example 3: De Morgan’s Law
Formula: ¬(p ∨ q) ↔ (¬p ∧ ¬q)
Truth Table:
| p | q | p ∨ q | ¬(p ∨ q) | ¬p | ¬q | ¬p ∧ ¬q | ¬(p ∨ q) ↔ (¬p ∧ ¬q) |
|---|---|---|---|---|---|---|---|
| T | T | T | F | F | F | F | T |
| T | F | T | F | F | T | F | T |
| F | T | T | F | T | F | F | T |
| F | F | F | T | T | T | T | T |
The final column is all T, confirming these expressions are logically equivalent.
Types of Formulas
Tautology
A tautology is a formula that is true in every interpretation (always true).
Examples:
- p ∨ ¬p (Law of Excluded Middle)
- ¬(p ∧ ¬p) (Law of Non-Contradiction)
- (p ∧ q) → p
- p → (p ∨ q)
Truth Table for p ∨ ¬p:
| p | ¬p | p ∨ ¬p |
|---|---|---|
| T | F | T |
| F | T | T |
All rows are true.
Contradiction
A contradiction is a formula that is false in every interpretation (always false).
Examples:
- p ∧ ¬p
- (p → q) ∧ (p ∧ ¬q)
- (p ∨ q) ∧ ¬p ∧ ¬q
Truth Table for p ∧ ¬p:
| p | ¬p | p ∧ ¬p |
|---|---|---|
| T | F | F |
| F | T | F |
All rows are false.
Contingency
A contingency is a formula that is true in some interpretations and false in others.
Examples:
- p ∧ q
- p → q
- (p ∨ q) ∧ r
Most practical formulas are contingencies.
Logical Equivalence
Two formulas are logically equivalent if they have the same truth value in every interpretation.
Notation: A ≡ B or A ⇔ B
Important Logical Laws
Identity Laws:
p ∧ T ≡ p
p ∨ F ≡ p
Domination Laws:
p ∨ T ≡ T
p ∧ F ≡ F
Idempotent Laws:
p ∨ p ≡ p
p ∧ p ≡ p
Double Negation Law:
¬(¬p) ≡ p
Commutative Laws:
p ∨ q ≡ q ∨ p
p ∧ q ≡ q ∧ p
Associative Laws:
(p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
(p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Distributive Laws:
p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
De Morgan’s Laws:
¬(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q
Absorption Laws:
p ∨ (p ∧ q) ≡ p
p ∧ (p ∨ q) ≡ p
Negation Laws:
p ∨ ¬p ≡ T (Law of Excluded Middle)
p ∧ ¬p ≡ F (Law of Non-Contradiction)
Implication Laws:
p → q ≡ ¬p ∨ q
p → q ≡ ¬q → ¬p (Contrapositive)
¬(p → q) ≡ p ∧ ¬q
Biconditional Laws:
p ↔ q ≡ (p → q) ∧ (q → p)
p ↔ q ≡ (p ∧ q) ∨ (¬p ∧ ¬q)
Simplifying Expressions Using Equivalences
Example: Simplify ¬(p ∨ ¬q) ∨ (¬p ∧ ¬q)
Solution:
¬(p ∨ ¬q) ∨ (¬p ∧ ¬q)
≡ (¬p ∧ ¬(¬q)) ∨ (¬p ∧ ¬q) [De Morgan's Law]
≡ (¬p ∧ q) ∨ (¬p ∧ ¬q) [Double Negation]
≡ ¬p ∧ (q ∨ ¬q) [Distributive Law]
≡ ¬p ∧ T [Excluded Middle]
≡ ¬p [Identity Law]
Normal Forms
Conjunctive Normal Form (CNF)
A formula is in CNF if it is a conjunction of disjunctions (AND of ORs).
Form: (p ∨ q ∨ r) ∧ (¬p ∨ s) ∧ (q ∨ ¬s ∨ t)
Advantages:
- Useful for automated reasoning
- Important for SAT solvers
- Can be converted from any formula
Example Conversion:
Original: (p → q) ∧ (r → s)
Step 1: (¬p ∨ q) ∧ (¬r ∨ s) [Implication law]
Result: Already in CNF
Disjunctive Normal Form (DNF)
A formula is in DNF if it is a disjunction of conjunctions (OR of ANDs).
Form: (p ∧ q ∧ r) ∨ (¬p ∧ s) ∨ (q ∧ ¬s ∧ t)
Advantages:
- Can be read directly from truth tables
- Useful for understanding when a formula is true
Example Conversion:
Original: (p ∨ q) ∧ r
Step 1: (p ∧ r) ∨ (q ∧ r) [Distributive law]
Result: Already in DNF
Practice Problems
Problem 1: Evaluate Expressions
Given: p = T, q = F, r = T
Evaluate:
- p ∧ q
- p → r
- ¬r ∨ q
- (p ∧ ¬r) → q
Solutions:
- T ∧ F = F
- T → T = T
- F ∨ F = F
- (T ∧ F) → F = F → F = T
Problem 2: Create Truth Table
Create a truth table for: (p → q) ↔ (¬p ∨ q)
Solution:
| p | q | p → q | ¬p | ¬p ∨ q | (p → q) ↔ (¬p ∨ q) |
|---|---|---|---|---|---|
| T | T | T | F | T | T |
| T | F | F | F | F | T |
| F | T | T | T | T | T |
| F | F | T | T | T | T |
The final column is all T, confirming these expressions are logically equivalent.
Problem 3: Simplify Expression
Simplify: (p ∧ q) ∨ (p ∧ ¬q)
Solution:
(p ∧ q) ∨ (p ∧ ¬q)
≡ p ∧ (q ∨ ¬q) [Distributive Law]
≡ p ∧ T [Excluded Middle]
≡ p [Identity Law]
Problem 4: Identify Formula Type
Determine whether each formula is a tautology, contradiction, or contingency:
- p ∨ ¬p
- p ∧ ¬p
- p ∧ q
Solutions:
- p ∨ ¬p = Tautology (always true)
- p ∧ ¬p = Contradiction (always false)
- p ∧ q = Contingency (depends on p and q)
Related Resources and Tools
Online Learning Platforms
- Stanford Encyclopedia of Philosophy - Propositional Logic - Comprehensive academic resource
- Khan Academy - Truth Tables - Video tutorials on truth tables
- Coursera - Mathematical Logic - University-level course
- MIT OpenCourseWare - Mathematics for Computer Science - Free course materials
Interactive Tools
- Truth Table Generator - Stanford Tool - Create and verify truth tables
- Logic Simulator - LogicSim - Visual logic circuit design
- Boolean Algebra Simplifier - Boolean Algebra Calculator - Simplify expressions
- Proof Checker - Fitch Proof Checker - Verify formal proofs
Recommended Books
- “Introduction to Logic” by Irving M. Copi and Carl Cohen - Classic textbook on propositional logic
- “A Concise Introduction to Logic” by Patrick J. Hurley - Accessible introduction with examples
- “Logic: The Laws of Truth” by Nicholas J.J. Smith - Modern comprehensive treatment
- “forall x: An Introduction to Formal Logic” by P.D. Magnus - Free online textbook
Academic Journals
- Journal of Symbolic Logic - Leading journal on mathematical logic
- Studia Logica - International journal on logic and philosophy
- Logic and Logical Philosophy - Open access journal on logic research
Software Tools
- Prolog - Logic programming language
- Python - For implementing truth table generators
- Z3 - SMT solver for automated reasoning
Glossary of Key Terms
- Antecedent: The “if” part of a conditional statement
- Biconditional: “If and only if” operator (↔)
- Conjunction: “And” operator (∧)
- Consequent: The “then” part of a conditional statement
- Contingency: Formula that is true in some interpretations and false in others
- Contradiction: Formula that is always false
- Disjunction: “Or” operator (∨)
- Equivalence: Two formulas with the same truth value in all interpretations
- Implication: “If-then” operator (→)
- Negation: “Not” operator (¬)
- Proposition: A statement that is either true or false
- Tautology: Formula that is always true
- Truth Table: Table showing truth values for all interpretations
- Truth Value: True or false
Conclusion
Propositional logic operators and truth tables are the foundation of formal reasoning. By mastering:
- The five fundamental operators (¬, ∧, ∨, →, ↔)
- Truth table construction and evaluation
- Logical equivalences and laws
- Normal forms (CNF and DNF)
You develop the ability to:
- Analyze logical expressions systematically
- Simplify complex formulas
- Verify logical equivalences
- Construct valid arguments
- Understand the foundations of computer science and mathematics
The next article in this series will explore Logical Equivalence and Normal Forms, diving deeper into simplifying and transforming logical expressions.
Which logical operator do you find most interesting or challenging? Have you used truth tables in your work? Share your experiences in the comments below!
Comments