Synetic College Logo
Unit 2 of 4 · B.Sc IT Sem 1

Unit 2: Algebra of logic and mathematical induction

Mathematics-I notes · PTU syllabus (BSIT103/BSBC103)

4 min read10 topics10 exam questions
On this page
  1. Unit summary
  2. Propositions
  3. Logical operations
  4. Truth tables
  5. Tautologies and contradictions
  6. Arguments and validity
  7. Propositions generated by a set
  8. Laws of equivalence and implication
  9. Mathematical systems
  10. Quantifiers
  11. Principle of mathematical induction
  12. Key terms
  13. Quick revision
  14. Important questions

Unit summary

Logic underlies programming conditions, digital circuits and proofs. This unit covers propositions and logical operations, truth tables, arguments and validity, propositions generated by a set, laws of equivalence and implication, mathematical systems, quantifiers and the principle of mathematical induction.

After this unit you can

  • Use propositions, logical operations and truth tables
  • Test arguments for validity
  • Apply laws of logic and quantifiers
  • Prove results by mathematical induction

PTU syllabus topics

  • Propositions and logic operations
  • truth tables
  • arguments and validity
  • propositions generated by a set
  • equivalence and implication laws of logic
  • mathematical systems
  • quantifiers
  • principle of mathematical induction
ComparisonTruth table for logical connectives
p = T, q = F
p = F, q = F

p ∧ q (AND)

F

F

p ∨ q (OR)

T

F

p → q (implies)

F

T

p ↔ q (iff)

F

T

1

Topic 1

Propositions

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.

2

Topic 2

Logical operations

ComparisonThe main connectives
Symbol
Read as

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.
3

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.

pq¬pp ∧ qp ∨ qp → qp ↔ q
TTFTTTT
TFFFTFF
FTTFTTF
FFTFFTT

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.

4

Topic 4

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¬pp ∨ ¬pp ∧ ¬p
TFTF
FTTF

The column p ∨ ¬p is all T (tautology); p ∧ ¬p is all F (contradiction). Note that the negation of a tautology is a contradiction.

5

Topic 5

Arguments and validity

  • Argument: premises P1, P2, …, Pn and a conclusion Q; it is valid if the conclusion is true whenever all premises are true — i.e., (P1 ∧ P2 ∧ … ∧ Pn) → Q is a tautology.
Key formulasRules of inference

  • Modus ponens

    p, p → q; therefore q

  • Modus tollens

    ¬q, p → q; therefore ¬p

  • Hypothetical syllogism

    p → q, q → r; therefore p → r

  • Disjunctive syllogism

    p ∨ q, ¬p; therefore q

Example

"If it rains, the match is cancelled. It rains. Therefore the match is cancelled." — valid by modus ponens.

6

Topic 6

Propositions generated by a set

  • Given a set of propositions S = {p, q}, the propositions generated by S are all compound propositions formed from them using ∧, ∨, ¬, →, ↔ — for n variables there are 2^(2^n) distinct truth functions (16 for two variables).
7

Topic 7

Laws of equivalence and implication

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."

Key formulasLaws of logic

  • De Morgan's

    ¬(p ∧ q) ≡ ¬p ∨ ¬q; ¬(p ∨ q) ≡ ¬p ∧ ¬q

  • Implication

    p → q ≡ ¬p ∨ q

  • Contrapositive

    p → q ≡ ¬q → ¬p

  • Distributive

    p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)

  • Absorption

    p ∨ (p ∧ q) ≡ p

8

Topic 8

Mathematical systems

  • A mathematical system consists of a set of undefined terms, definitions, axioms (assumed true) and theorems (proved from axioms) — e.g., Euclidean geometry, Boolean algebra, group theory.
  • Proof methods: direct proof, contrapositive, contradiction, cases, induction.
9

Topic 9

Quantifiers

  • Universal quantifier ∀ ("for all") and existential quantifier ∃ ("there exists").
  • Negation: ¬∀x P(x) ≡ ∃x ¬P(x); ¬∃x P(x) ≡ ∀x ¬P(x).

Example

"All students passed" (∀x P(x)) is negated as "Some student did not pass" (∃x ¬P(x)).

10

Topic 10

Principle of mathematical induction

ProcessProof by induction
  1. 1Basis step

    Show P(1) is true

  2. 2Inductive hypothesis

    Assume P(k) is true

  3. 3Inductive step

    Prove P(k + 1) using P(k)

  4. 4Conclusion

    P(n) is true for all n ≥ 1

Example

Prove 1 + 2 + … + n = n(n + 1)/2. Basis: n = 1 gives 1 = 1. Step: assume true for k; then 1 + … + k + (k + 1) = k(k + 1)/2 + (k + 1) = (k + 1)(k + 2)/2 — true for k + 1.

Key terms

Proposition
Statement that is either true or false
Tautology
Proposition always true
Valid argument
Conclusion true whenever premises are true
Quantifier
Symbol expressing "for all" or "there exists"
Mathematical induction
Proof method using basis and inductive steps

Quick revision

  • Propositions; ¬, ∧, ∨, →, ↔; truth tables.
  • Tautology, contradiction, contingency.
  • Validity; modus ponens, modus tollens, syllogisms.
  • Equivalence laws; contrapositive; mathematical systems; quantifiers and negation.
  • Induction: basis, hypothesis, step.

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

  1. Q1.Define a proposition.
  2. Q2.Construct the truth table of p → q.
  3. Q3.What is modus tollens?
  4. Q4.Write the contrapositive of p → q.
  5. Q5.Negate "∀x, x² ≥ 0".
  6. Q6.State the principle of mathematical induction.

Long-answer questions

  1. Q1.Explain logical operations with truth tables.
  2. Q2.Test the validity of an argument using truth tables or rules of inference.
  3. Q3.Explain the laws of logic and quantifiers.
  4. Q4.Prove a result using mathematical induction.

Stuck on this unit?

Message SBS on WhatsApp for help with Mathematics-I, or to ask about studying B.Sc IT at Synetic.

WhatsApp us