ISC Class 11 Computer Science Notes: Propositional Logic and Truth Tables

Propositional logic is the foundation for Boolean algebra, which carries a large share of marks in both the ISC Class 11 and Class 12 Computer Science papers. If you understand truth tables and the laws of logic well now, K-maps and logic gates become much easier next year.

1. What is a Proposition?

A proposition (or statement) is a sentence that is either true or false, but not both.

• "Delhi is the capital of India." is a proposition (true).
• "7 is an even number." is a proposition (false).
• "Close the door." is NOT a proposition, because it is a command.
• "How are you?" is NOT a proposition, because it is a question.
• "x + 2 = 5" is NOT a proposition until the value of x is known.

Propositions are usually written with letters such as p, q and r. A simple proposition has one idea. A compound proposition joins two or more simple propositions using connectives.

2. Logical Connectives

Connective      Symbol   Read as             Boolean form
-------------   ------   -----------------   ------------
Negation        ¬p, ~p   not p               p'
Conjunction     p ∧ q    p and q             p · q
Disjunction     p ∨ q    p or q              p + q
Implication     p → q    if p then q         p' + q
Biconditional   p ↔ q    p if and only if q  p ⊙ q (XNOR)

3. Truth Tables

A truth table lists every possible combination of truth values. With n variables there are 2ⁿ rows.

Negation, AND and OR

 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

Implication (Conditional)

p → q is false only when p is true and q is false. In every other case it is true.

 p  q | p → q
 T  T |   T
 T  F |   F
 F  T |   T
 F  F |   T

Think of it as a promise: "If you score 90, I will give you a prize." The promise is broken only if you score 90 and do not get the prize. If you do not score 90, the promise has not been broken, whatever happens.

Biconditional

p ↔ q is true when both p and q have the same truth value.

 p  q | p ↔ q
 T  T |   T
 T  F |   F
 F  T |   F
 F  F |   T

4. Converse, Inverse and Contrapositive

For the conditional p → q:

• Converse: q → p
• Inverse: ¬p → ¬q
• Contrapositive: ¬q → ¬p

Key fact: a conditional statement is always logically equivalent to its contrapositive. The converse is equivalent to the inverse.

Example: "If a number is divisible by 4, then it is even."

• Converse: If a number is even, then it is divisible by 4. (false, for example 6)
• Inverse: If a number is not divisible by 4, then it is not even. (false, for example 6)
• Contrapositive: If a number is not even, then it is not divisible by 4. (true)

5. Tautology, Contradiction and Contingency

• Tautology: a compound proposition that is always true, for example p ∨ ¬p.
• Contradiction: a compound proposition that is always false, for example p ∧ ¬p.
• Contingency: a proposition that is neither, because it is true for some values and false for others, for example p → q.

Solved Example: Show that (p ∧ q) → p is a tautology

 p  q | p ∧ q | (p ∧ q) → p
 T  T |   T   |      T
 T  F |   F   |      T
 F  T |   F   |      T
 F  F |   F   |      T

Every entry in the last column is T, so it is a tautology.

Solved Example: Prove that p → q ≡ ¬q → ¬p

 p  q | ¬p  ¬q | p → q | ¬q → ¬p
 T  T |  F   F |   T   |    T
 T  F |  F   T |   F   |    F
 F  T |  T   F |   T   |    T
 F  F |  T   T |   T   |    T

The last two columns are identical, so the two statements are logically equivalent.

6. Laws of Propositional Logic

These laws are the same as the Boolean algebra laws you will use in Class 12.

• Identity: p ∧ T ≡ p, and p ∨ F ≡ p
• Domination: p ∨ T ≡ T, and p ∧ F ≡ F
• Idempotent: p ∨ p ≡ p, and p ∧ p ≡ p
• Double negation: ¬(¬p) ≡ p
• Commutative: p ∨ q ≡ q ∨ p, and p ∧ q ≡ q ∧ p
• Associative: (p ∨ q) ∨ r ≡ p ∨ (q ∨ r)
• Distributive: p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r)
• De Morgan's: ¬(p ∧ q) ≡ ¬p ∨ ¬q, and ¬(p ∨ q) ≡ ¬p ∧ ¬q
• Absorption: p ∨ (p ∧ q) ≡ p, and p ∧ (p ∨ q) ≡ p
• Complement: p ∨ ¬p ≡ T, and p ∧ ¬p ≡ F
• Implication: p → q ≡ ¬p ∨ q

Solved Example: Simplify ¬(p → q) using the laws

¬(p → q) ≡ ¬(¬p ∨ q)       (Implication law)
         ≡ ¬(¬p) ∧ ¬q      (De Morgan's law)
         ≡ p ∧ ¬q          (Double negation)

7. Practice Questions

1. Which of these are propositions? (a) "Java is a programming language." (b) "Please sit down." (c) "5 > 9"
2. Draw the truth table for (p ∨ q) → ¬p.
3. Write the converse, inverse and contrapositive of: "If it is Sunday, then the school is closed."
4. Show that p ∧ ¬p is a contradiction.
5. Using the laws of logic, prove that p ∨ (¬p ∧ q) ≡ p ∨ q.

Hints: 1. (a) and (c) are propositions. 2. The result column is F, F, T, T for the rows TT, TF, FT, FF. 5. Apply the distributive law: (p ∨ ¬p) ∧ (p ∨ q) = T ∧ (p ∨ q) = p ∨ q.

Exam tip: in ISC papers, always draw a complete truth table with a column for every intermediate expression. Step marks are given for each correct column.

Continue your Class 11 preparation with our notes on Number Systems and Conversions and the ISC Class 11 solved programs section.