Unit 2: Logic
Mathematics notes · PTU syllabus (UGCC2501)
On this page
Unit summary
Logic is the science of correct reasoning and the basis of programming conditions, digital circuits and mathematical proof. This unit covers logical statements, the connectives and basic logical operations (negation, conjunction, disjunction, conditional and biconditional), truth tables, logical equivalence of statements, and tautologies and contradictions.
After this unit you can
- Identify statements and form compound statements with connectives
- Construct truth tables for compound statements
- Prove logical equivalence using truth tables and standard laws
- Identify tautologies, contradictions and contingencies
PTU syllabus topics
- Logic statements
- connectives
- basic logic operations (conjunction, disjunction, negation)
- logical equivalence/equivalent statements
- tautologies and contradictions
Topic 1
Logic statements
A statement (proposition) is a declarative sentence that is either true or false, but not both.
Examples
"5 is a prime number" (true); "Delhi is in Punjab" (false)
"What is your name?" (question); "Close the door" (order); "x + 2 = 5" (depends on x)
Reason
Has a definite truth value
Has no truth value
- Truth value
- T (true) or F (false)
- Simple statement
- Cannot be broken into simpler statements
- Compound statement
- Made by joining simple statements with connectives
- Propositional variable
- Letters p, q, r that stand for statements
- Paradox
- Self-contradictory sentence such as "This sentence is false" — not a statement
Example
p: "The sun rises in the east" (T); q: "2 + 3 = 6" (F). The sentence "Is it raining?" is not a statement.
Topic 2
Connectives and basic logic operations
Negation
¬p or ~p
"not p"
Conjunction
p ∧ q
"p and q"
Disjunction
p ∨ q
"p or q" (inclusive)
Conditional (implication)
p → q
"if p then q"
Biconditional
p ↔ q
"p if and only if q"
Exclusive or
p ⊕ q
"p or q but not both"
Basic operations: negation, conjunction, disjunction
| p | q | ¬p | p ∧ q | p ∨ q |
|---|---|---|---|---|
| T | T | F | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | F |
- Negation
- Reverses the truth value
- Conjunction (AND)
- True only when both statements are true
- Disjunction (OR)
- False only when both statements are false
- Link with circuits
- AND gate = conjunction, OR gate = disjunction, NOT gate = negation
- Number of rows
- A truth table with n variables has 2ⁿ rows
Conditional and biconditional
| p | q | p → q | p ↔ q |
|---|---|---|---|
| T | T | T | T |
| T | F | F | F |
| F | T | T | F |
| F | F | T | T |
- p → q is false only when p is true and q is false. A promise "if you pass, I will give a gift" is broken only when you pass and get no gift.
Converse
q → p
No
Inverse
¬p → ¬q
No
Contrapositive
¬q → ¬p
Yes — always equivalent
Biconditional
(p → q) ∧ (q → p)
Equal to p ↔ q
Example
"If it rains, the match is cancelled": converse — "If the match is cancelled, it rained"; inverse — "If it does not rain, the match is not cancelled"; contrapositive — "If the match is not cancelled, it did not rain" (equivalent to the original).
Negation of compound statements
Negation of conjunction
¬(p ∧ q) ≡ ¬p ∨ ¬q
Negation of disjunction
¬(p ∨ q) ≡ ¬p ∧ ¬q
Negation of conditional
¬(p → q) ≡ p ∧ ¬q
Negation of biconditional
¬(p ↔ q) ≡ (p ∧ ¬q) ∨ (¬p ∧ q)
Double negation
¬(¬p) ≡ p
Topic 3
Truth tables
- 1List the variables and write 2ⁿ rows covering every combination of T and F
- 2Add a column for every sub-expression
- 3Fill the columns from the innermost bracket outward
- 4The last column gives the truth value of the whole statement
- 5Read the pattern: all T, all F or mixed
Example
Truth table for (p ∨ q) ∧ ¬(p ∧ q) — this is the exclusive-or p ⊕ q.
| p | q | p ∨ q | p ∧ q | ¬(p ∧ q) | (p ∨ q) ∧ ¬(p ∧ q) |
|---|---|---|---|---|---|
| T | T | T | T | F | F |
| T | F | T | F | T | T |
| F | T | T | F | T | T |
| F | F | F | F | T | F |
Example
Three variables need 8 rows: the pattern TTT, TTF, TFT, TFF, FTT, FTF, FFT, FFF lists every case exactly once.
Topic 4
Logical equivalence
Two statements are logically equivalent (≡) if they have the same truth value for every assignment of truth values — their truth table columns are identical.
Example
Prove p → q ≡ ¬p ∨ q.
| p | q | p → q | ¬p | ¬p ∨ q |
|---|---|---|---|---|
| T | T | T | F | T |
| T | F | F | F | F |
| F | T | T | T | T |
| F | F | T | T | T |
Standard logical equivalences
| Equivalence | |
|---|---|
| Commutative | p ∧ q ≡ q ∧ p ; p ∨ q ≡ q ∨ p |
| Associative | (p ∧ q) ∧ r ≡ p ∧ (q ∧ r) ; (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) |
| Distributive | p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) ; p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) |
| De Morgan | ¬(p ∧ q) ≡ ¬p ∨ ¬q ; ¬(p ∨ q) ≡ ¬p ∧ ¬q |
| Implication | p → q ≡ ¬p ∨ q ≡ ¬q → ¬p |
| Biconditional | p ↔ q ≡ (p → q) ∧ (q → p) |
| Idempotent | p ∧ p ≡ p ; p ∨ p ≡ p |
| Absorption | p ∨ (p ∧ q) ≡ p ; p ∧ (p ∨ q) ≡ p |
Set theory vs logic vs Boolean algebra
| Correspondence | |
|---|---|
| Union ∪ | Disjunction ∨ and Boolean OR + |
| Intersection ∩ | Conjunction ∧ and Boolean AND · |
| Complement ′ | Negation ¬ and Boolean NOT ′ |
| Universal set U | True (T, 1) |
| Empty set ∅ | False (F, 0) |
Exam tip
The same laws appear in sets, logic and Boolean algebra — learn them once. De Morgan in sets is (A ∪ B)′ = A′ ∩ B′, in logic ¬(p ∨ q) ≡ ¬p ∧ ¬q.
Topic 5
Tautologies and contradictions
Tautology
Always true, whatever the truth values of the variables — last column all T
p ∨ ¬p
Contradiction
Always false — last column all F
p ∧ ¬p
Contingency
Sometimes true, sometimes false
p → q
| p | ¬p | p ∨ ¬p (tautology) | p ∧ ¬p (contradiction) |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
Example
Show that [(p → q) ∧ p] → q (modus ponens) is a tautology.
| p | q | p → q | (p → q) ∧ p | [(p → q) ∧ p] → q |
|---|---|---|---|---|
| T | T | T | T | T |
| T | F | F | F | T |
| F | T | T | F | T |
| F | F | T | F | T |
- Excluded middle
- p ∨ ¬p
- Modus ponens
- [(p → q) ∧ p] → q
- Modus tollens
- [(p → q) ∧ ¬q] → ¬p
- Hypothetical syllogism
- [(p → q) ∧ (q → r)] → (p → r)
- Disjunctive syllogism
- [(p ∨ q) ∧ ¬p] → q
- Contrapositive
- (p → q) ↔ (¬q → ¬p)
- 1
Write the truth table
- 2
Look at the final column
- 3
All T — tautology
- 4
All F — contradiction
- 5
Mixed — contingency
- 6
Negation of a tautology is a contradiction and vice versa
Key terms
- Statement
- A sentence that is either true or false but not both
- Compound statement
- Statement formed from simpler ones using connectives
- Conjunction
- p ∧ q, true only when both are true
- Disjunction
- p ∨ q, false only when both are false
- Conditional
- p → q, false only when p is true and q is false
- Contrapositive
- ¬q → ¬p, equivalent to p → q
- Logical equivalence
- Same truth table for two statements
- Tautology
- A statement that is always true
- Contradiction
- A statement that is always false
Quick revision
- A statement is true or false, never both; questions and commands are not statements.
- ∧ true only if both true; ∨ false only if both false; p → q false only for T, F.
- p → q ≡ ¬p ∨ q ≡ ¬q → ¬p; the converse and inverse are not equivalent to it.
- De Morgan: ¬(p ∧ q) ≡ ¬p ∨ ¬q, ¬(p ∨ q) ≡ ¬p ∧ ¬q.
- Tautology — all T; contradiction — all F; otherwise contingency.
- n variables give 2ⁿ rows.
Important exam questions
Practice questions written to the PTU exam pattern for this unit's syllabus: short answers (Section A style) and long answers (Sections B and C style).
Short-answer questions
- Q1.Define a statement. Give one example and one non-example.
- Q2.Write the truth table of conjunction.
- Q3.When is a conditional statement false?
- Q4.Write the converse and contrapositive of "If x is even then x² is even".
- Q5.State De Morgan's laws for statements.
- Q6.What is a tautology? Give an example.
- Q7.What is a contradiction?
- Q8.Write the negation of "p ∧ q".
- Q9.How many rows are there in a truth table for 4 variables?
- Q10.What is logical equivalence?
Long-answer questions
- Q1.Explain the logical connectives with truth tables.
- Q2.Construct a truth table for (p → q) ∧ (q → p) and compare it with p ↔ q.
- Q3.Prove p → q ≡ ¬p ∨ q and ¬(p ∧ q) ≡ ¬p ∨ ¬q using truth tables.
- Q4.Show that [(p → q) ∧ p] → q is a tautology.
- Q5.Explain tautology, contradiction and contingency with examples.
Stuck on this unit?
Message SBS on WhatsApp for help with Mathematics, or to ask about studying BCA at Synetic.
