Unit 2: Logic
Mathematics notes · PTU syllabus (UGCC2501)
On this page
Unit summary
Logic is the study of correct reasoning, and it is the foundation of programming conditions, circuit design and database queries. Here, logic is studied in its mathematical form, using statements and symbols.
You will learn what counts as a logical statement, how connectives join statements, how to build truth tables, and how to recognise tautologies, contradictions and logically equivalent statements.
After this unit you can
- Decide whether a sentence is a logical statement
- Use the connectives AND, OR, NOT, IF–THEN and IF AND ONLY IF
- Build truth tables for compound statements
- Prove logical equivalence and identify tautologies and contradictions
PTU syllabus topics
- Logic statements
- connectives
- basic logic operations (conjunction, disjunction, negation)
- logical equivalence/equivalent statements
- tautologies and contradictions
- Conjunction (p ∧ q)
- True only when both p and q are true
- Disjunction (p ∨ q)
- True when at least one is true
- Negation (¬p)
- Reverses the truth value of p
- Tautology
- A statement that is always true, e.g. p ∨ ¬p
- Contradiction
- A statement that is always false, e.g. p ∧ ¬p
- Logical equivalence
- Two statements with identical truth tables
Topic 1
Logic statements
A statement (proposition) is a declarative sentence that is either true or false, but not both. Its truth or falsity is called its truth value (T or F).
- "Delhi is the capital of India." — a statement (true).
- "5 + 3 = 9." — a statement (false).
- "Close the door." / "What is your name?" / "x + 2 = 5" — not statements: commands, questions and open sentences have no fixed truth value.
Statements are written with small letters p, q, r. A simple statement has one idea; a compound statement joins two or more simple statements using connectives.
Exam tip
Questions, exclamations, commands and sentences containing a variable are not statements. Mention this in any definition answer.
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
Conditional
p → q
if p then q
Biconditional
p ↔ q
p if and only if q
- Negation (¬p): reverses the truth value. If p is true, ¬p is false.
- Conjunction (p ∧ q): true only when both p and q are true.
- Disjunction (p ∨ q): true when at least one of p or q is true; false only when both are false.
- Conditional (p → q): false only when p is true and q is false.
- Biconditional (p ↔ q): true when p and q have the same truth value.
Topic 3
Truth tables
A truth table lists the truth value of a compound statement for every combination of truth values of its parts. With n simple statements there are 2ⁿ rows.
| p | q | ¬p | p ∧ q | p ∨ q | p → q | p ↔ q |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | T |
| T | F | F | F | T | F | F |
| F | T | T | F | T | T | F |
| F | F | T | F | F | T | T |
Example
Let p: "It is raining" and q: "I carry an umbrella". p → q ("If it rains, I carry an umbrella") is broken only when it rains and I don't carry one — row 2.
Topic 4
Logical equivalence
Two statements are logically equivalent (written ≡) if they have identical truth values in every row of their truth tables. Important equivalences:
- Double negation: ¬(¬p) ≡ p
- De Morgan's laws: ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q
- Conditional: p → q ≡ ¬p ∨ q
- Contrapositive: p → q ≡ ¬q → ¬p
- Biconditional: p ↔ q ≡ (p → q) ∧ (q → p)
Example
To prove ¬(p ∨ q) ≡ ¬p ∧ ¬q, build one truth table with columns p, q, p ∨ q, ¬(p ∨ q), ¬p, ¬q, ¬p ∧ ¬q. The columns for ¬(p ∨ q) and ¬p ∧ ¬q come out identical: F, F, F, T.
Exam tip
When proving equivalence, always write the conclusion: "Since the last two columns are identical, the statements are logically equivalent."
Topic 5
Tautologies and contradictions
- A tautology is a compound statement that is always true, whatever the truth values of its parts. Example: p ∨ ¬p.
- A contradiction is a statement that is always false. Example: p ∧ ¬p.
- A statement that is sometimes true and sometimes false is a contingency.
| p | ¬p | p ∨ ¬p | p ∧ ¬p |
|---|---|---|---|
| T | F | T | F |
| F | T | T | F |
The column p ∨ ¬p is all T (tautology); p ∧ ¬p is all F (contradiction). Note that the negation of a tautology is a contradiction.
Key terms
- Statement
- A sentence that is either true or false, but not both
- Connective
- A word or symbol joining statements: and, or, not, if–then, iff
- Truth table
- A table of truth values for every combination of inputs
- Tautology
- A statement true in every case
- Contradiction
- A statement false in every case
- Logical equivalence
- Two statements with identical truth tables
Quick revision
- A truth table with n statements has 2ⁿ rows.
- AND is true only if both are true; OR is false only if both are false.
- p → q is false only when p is T and q is F.
- p → q ≡ ¬p ∨ q ≡ ¬q → ¬p (contrapositive).
- p ∨ ¬p is a tautology; p ∧ ¬p is a contradiction.
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. Which of these are statements: "2 + 2 = 4", "Go home", "x > 3"?
- Q2.Write the truth table for p ∧ q and p ∨ q.
- Q3.What is a tautology? Give an example.
- Q4.Define logical equivalence.
- Q5.Write the negation of "All students are present."
- Q6.When is p → q false?
Long-answer questions
- Q1.Explain the basic logical connectives with their truth tables.
- Q2.Prove using truth tables that ¬(p ∧ q) ≡ ¬p ∨ ¬q and ¬(p ∨ q) ≡ ¬p ∧ ¬q.
- Q3.Show that (p → q) ↔ (¬q → ¬p) is a tautology.
- Q4.Determine whether (p ∧ q) → (p ∨ q) is a tautology, a contradiction or a contingency.
Stuck on this unit?
Message SBS on WhatsApp for help with Mathematics, or to ask about studying BCA at Synetic.