What is Propositional Logic?
Propositional logic (also called sentential logic or statement logic) is a branch of logic that deals with propositions and their relationships. It forms the foundation of mathematical reasoning and is essential for computer science, particularly in areas like circuit design, software verification, and artificial intelligence.
Propositions
A proposition is a declarative statement that is either true or false, but not both.
Examples of Valid Propositions:
- “The Earth revolves around the Sun.” → True
- “2 + 2 = 5” → False
- “New Delhi is the capital of India.” → True
- “All cats are mammals.” → True
- “7 is an even number.” → False
Examples of Non-Propositions:
These are NOT propositions because they cannot be assigned a truth value:
- “What time is it?” → (Question, not a statement)
- “Close the door!” → (Command, not a statement)
- “x + 2 = 5” → (Contains a variable, truth value depends on x)
- “This sentence is false.” → (Paradox, cannot determine truth value)
Propositional Variables
We use letters like p, q, r, s, t to represent propositions.
Example:
- Let p = “It is raining”
- Let q = “The ground is wet”
Logical Connectives (Logical Operators)
Logical connectives are used to combine or modify propositions to create compound propositions.
1. Negation (NOT) - ¬ or ~
The negation of a proposition p, written as ¬p or ~p, has the opposite truth value of p.
Truth Table:
| p | ¬p |
|---|---|
| T | F |
| F | T |
Examples:
-
If p = “It is raining” (True)
-
Then ¬p = “It is not raining” (False)
-
If q = “5 is an odd number” (True)
-
Then ¬q = “5 is not an odd number” (False)
2. Conjunction (AND) - ∧
The conjunction of p and q, written as p ∧ q, is true only when both p and q are true.
Truth Table:
| p | q | p ∧ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
Examples:
-
Let p = “It is raining” (True)
-
Let q = “I have an umbrella” (True)
-
Then p ∧ q = “It is raining AND I have an umbrella” (True)
-
Let p = “Today is Monday” (True)
-
Let q = “It is snowing” (False)
-
Then p ∧ q = “Today is Monday AND it is snowing” (False)
3. Disjunction (OR) - ∨
The disjunction of p and q, written as p ∨ q, is true when at least one of p or q is true.
Truth Table:
| p | q | p ∨ q |
|---|---|---|
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
Examples:
-
Let p = “You can have tea” (True)
-
Let q = “You can have coffee” (False)
-
Then p ∨ q = “You can have tea OR coffee” (True)
-
Let p = “I will study math” (False)
-
Let q = “I will study science” (False)
-
Then p ∨ q = “I will study math OR science” (False)
4. Exclusive OR (XOR) - ⊕
The exclusive or of p and q, written as p ⊕ q, is true when exactly one of p or q is true, but not both.
Truth Table:
| p | q | p ⊕ q |
|---|---|---|
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Examples:
- Let p = “The coin shows heads” (True)
- Let q = “The coin shows tails” (False)
- Then p ⊕ q = “The coin shows heads XOR tails” (True)
- A coin cannot show both heads and tails simultaneously
5. Conditional (Implication) - →
The conditional statement p → q is read as “if p then q”. It is false only when p is true and q is false.
- p is called the hypothesis (or antecedent)
- q is called the conclusion (or consequent)
Truth Table:
| p | q | p → q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
Examples:
-
p → q: “If it rains, then the ground is wet”
- When it rains (T) and ground is wet (T) → True
- When it rains (T) but ground is not wet (F) → False
- When it doesn’t rain (F) and ground is wet (T) → True (maybe from sprinkler)
- When it doesn’t rain (F) and ground is not wet (F) → True
-
“If you study hard, then you will pass the exam”
- Study hard (T), Pass (T) → True ✓
- Study hard (T), Fail (F) → False ✗
- Don’t study (F), Pass (T) → True (maybe lucky)
- Don’t study (F), Fail (F) → True (no promise was broken)
6. Biconditional (If and only if) - ↔
The biconditional statement p ↔ q is true when p and q have the same truth value.
Truth Table:
| p | q | p ↔ q |
|---|---|---|
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Examples:
-
p ↔ q: “It is raining if and only if the ground is wet”
- Raining (T) and Wet (T) → True
- Raining (T) and Not Wet (F) → False
- Not Raining (F) and Wet (T) → False
- Not Raining (F) and Not Wet (F) → True
-
“A number is even if and only if it is divisible by 2”
- This is always true for any integer
Compound Propositions
Compound propositions are formed by combining propositions using logical connectives.
Example 1:
- p = “It is sunny”
- q = “It is warm”
- r = “We will go to the beach”
Compound proposition: (p ∧ q) → r
Meaning: “If it is sunny AND warm, then we will go to the beach”
Example 2:
- p = “I study”
- q = “I pass the exam”
Compound proposition: p → q
Meaning: “If I study, then I pass the exam”
Negation: ¬(p → q) = “I study but I don’t pass the exam”
Precedence of Logical Operators
When evaluating compound propositions, operators have a specific order of precedence (from highest to lowest):
- ¬ (Negation)
- ∧ (Conjunction)
- ∨ (Disjunction)
- → (Conditional)
- ↔ (Biconditional)
Example:
p ∨ q ∧ ¬r is evaluated as p ∨ (q ∧ (¬r))
Constructing Truth Tables
Truth tables show all possible truth value combinations for compound propositions.
Example 1: Truth table for (p ∨ q) ∧ ¬r
| p | q | r | ¬r | p ∨ q | (p ∨ q) ∧ ¬r |
|---|---|---|---|---|---|
| T | T | T | F | T | F |
| T | T | F | T | T | T |
| T | F | T | F | T | F |
| T | F | F | T | T | T |
| F | T | T | F | T | F |
| F | T | F | T | T | T |
| F | F | T | F | F | F |
| F | F | F | T | F | F |
Example 2: Truth table for p → (q ∨ r)
| p | q | r | q ∨ r | p → (q ∨ r) |
|---|---|---|---|---|
| T | T | T | T | T |
| T | T | F | T | T |
| T | F | T | T | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | T | F | T | T |
| F | F | T | T | T |
| F | F | F | F | T |
Important Concepts
Tautology
A tautology is a compound proposition that is always true, regardless of the truth values of its propositional variables.
Example: p ∨ ¬p (Law of Excluded Middle)
| p | ¬p | p ∨ ¬p |
|---|---|---|
| T | F | T |
| F | T | T |
Contradiction
A contradiction is a compound proposition that is always false.
Example: p ∧ ¬p
| p | ¬p | p ∧ ¬p |
|---|---|---|
| T | F | F |
| F | T | F |
Contingency
A contingency is a compound proposition that is neither a tautology nor a contradiction (it can be true or false depending on the truth values).
Example: p → q
Key Points to Remember for Exams
- Always identify whether a statement is a proposition before analyzing it
- Learn all truth tables by heart - they are fundamental
- Understand the difference between ∨ (OR) and ⊕ (XOR)
- The conditional p → q is only false when p is true and q is false
- Biconditional p ↔ q is true when both have the same truth value
- Follow operator precedence when evaluating compound propositions
- For n variables, a truth table has 2^n rows
- Practice constructing truth tables for complex expressions
Practice Problems
-
Determine if the following are propositions:
- “Where are you going?”
- “Paris is in France”
- “x > 10”
-
Let p = “I am hungry” and q = “I will eat”. Write in words:
- p ∧ q
- p → q
- ¬p ∨ q
-
Construct truth tables for:
- (p → q) ∧ (q → p)
- ¬(p ∨ q)
- (p ∧ q) → r
-
Identify whether the following are tautologies, contradictions, or contingencies:
- p ∨ (¬p ∧ q)
- (p → q) ↔ (¬q → ¬p)
- p ∧ ¬p ∧ q