Truth Tables
In Boolean algebra, truth table is a table showing the truth value of a statement formula for each possible combinations of truth values of component statements. A statement is a declarative sentence which has one and only one of the two possible values called truth values. Truth values are true and false denoted by the symbols T and F respectively, sometimes also denoted by symbols 1 and 0. Since we allow only two possible truth values, this logic is called two-valued logic.
Basic Logical Operations
1. Negation: It means the opposite of the original statement. If p is a statement, then the negation of p is denoted by ~p and read as 'it is not the case that p.' So, if p is true then ~ p is false and vice versa.
Example: If statement p is Paris is in France, then ~ p is 'Paris is not in France'.
| p | ~ p |
| T | F |
| F | T |
2. Conjunction: It means Anding of two statements. If p, q are two statements, then "p and q" is a compound statement, denoted by p ∧ q and referred as the conjunction of p and q. The conjunction of p and q is true only when both p and q are true. Otherwise, it is false.
| p | q | p ∧ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | F |
3. Disjunction: It means Oring of two statements. If p, q are two statements, then "p or q" is a compound statement, denoted by p ∨ q and referred to as the disjunction of p and q. The disjunction of p and q is true whenever at least one of the two statements is true, and it is false only when both p and q are false.
| p | q | p ∨ q |
| T | T | T |
| T | F | T |
| F | T | T |
| F | F | F |
4. Implication / if-then (⟶): An implication p⟶q is the proposition "if p, then q." It is false if p is true and q is false. The rest cases are true.
| p | q | p ⟶ q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | F |
5. If and Only If (↔): p ↔ q is bi-conditional logical connective which is true when p and q are same, i.e., both are false or both are true.
| p | q | p ↔ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
Derived Connectors
1. NAND: It means negation after ANDing of two statements. Assume p and q be two propositions. Nanding of pand q to be a proposition which is false when both p and q are true, otherwise true. It is denoted by p ↑ q.
| p | q | p ∨ q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | T |
2. NOR or Joint Denial: It means negation after ORing of two statements. Assume p and q be two propositions. NORing of p and q to be a proposition which is true when both p and q are false, otherwise false. It is denoted by p ↑ q.
| p | q | p ↓ q |
| T | T | F |
| T | F | F |
| F | T | F |
| F | F | T |
3. XOR: Assume p and q be two propositions. XORing of p and q is true if p is true or q is true but not both and vice-versa. It is denoted by p ⨁ q.
| p | q | p ⨁ q |
| T | T | F |
| T | F | T |
| F | T | T |
| F | F | F |
Example1: Prove that X ⨁ Y ≅ (X ∧∼Y)∨(∼X∧Y).
Solution: Construct the truth table for both the propositions.
| X | Y | X⨁Y | ∼Y | ∼X | X ∧∼Y | ∼X∧Y | (X ∧∼Y)∨(∼X∧Y) |
| T | T | F | F | F | F | F | F |
| T | F | T | T | F | T | F | T |
| F | T | T | F | T | F | T | T |
| F | F | F | T | T | F | F | F |
As the truth table for both the proposition is the same.
Example2: Show that (p ⨁q) ∨(p↓q) is equivalent to p ↑ q.
Solution: Construct the truth table for both the propositions.
| p | q | p⨁q | (p↓q) | (p⨁q)∨ (p↓q) | p ↑ q |
| T | T | F | F | F | F |
| T | F | T | F | T | T |
| F | T | T | F | T | T |
| F | F | F | T | T | T |
Conditional and BiConditional Statements
Conditional Statement
Let p and q are two statements then "if p then q" is a compound statement, denoted by p→ q and referred as a conditional statement, or implication. The implication p→ q is false only when p is true, and q is false; otherwise, it is always true. In this implication, p is called the hypothesis (or antecedent) and q is called the conclusion (or consequent).
| p | q | p → q |
| T | T | T |
| T | F | F |
| F | T | T |
| F | F | T |
For Example: The followings are conditional statements.
- If a = b and b = c, then a = c.
- If I get money, then I will purchase a computer.
Variations in Conditional Statement
Contrapositive: The proposition ~q→~p is called contrapositive of p →q.
Converse: The proposition q→p is called the converse of p →q.
Inverse: The proposition ~p→~q is called the inverse of p →q.
Example1: Show that p →q and its contrapositive ~q→~p are logically equivalent.
Solution: Construct the truth table for both the propositions:
| 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 |
As, the values in both cases are same, hence both propositions are equivalent.
Example2: Show that proposition q→p, and ~p→~q is not equivalent to p →q.
Solution: Construct the truth table for all the above propositions:
| p | q | ~p | ~q | p →q | q→p | ~p→~q |
| T | T | F | F | T | T | T |
| T | F | F | T | F | T | T |
| F | T | T | F | T | F | F |
| F | F | T | T | T | T | T |
As, the values of p →q in a table is not equal to q→p and ~p→~q as in fig. So both of them are not equal to p →q, but they are themselves logically equivalent.
BiConditional Statement
If p and q are two statements then "p if and only if q" is a compound statement, denoted as p ↔ q and referred as a biconditional statement or an equivalence. The equivalence p ↔ q is true only when both p and q are true or when both p and q are false.
| p | q | p ↔ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
For Example: (i) Two lines are parallel if and only if they have the same slope.
(ii) You will pass the exam if and only if you will work hard.
Example: Prove that p ↔ q is equivalent to (p →q) ∧(q→p).
Solution: Construct the truth table for both the propositions:
| p | q | p ↔ q |
| T | T | T |
| T | F | F |
| F | T | F |
| F | F | T |
| p | q | p →q | q→p | (p →q)∧(q→p) |
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | T | F | F |
| F | F | T | T | T |
Since, the truth tables are the same, hence they are logically equivalent. Hence Proved.
Principle of Duality
Two formulas A1 and A2 are said to be duals of each other if either one can be obtained from the other by replacing ∧ (AND) by ∨ (OR) by ∧ (AND). Also if the formula contains T (True) or F (False), then we replace T by F and F by T to obtain the dual.
Note1: The two connectives ∧ and ∨ are called dual of each other.
2. Like AND and OR, ↑ (NAND) and ↓ (NOR) are dual of each other.
3. If any formula of the proposition is valid, then it's dual of each other.
Equivalence of Propositions
Two propositions are said to be logically equivalent if they have exactly the same truth values under all circumstances.
The table1 contains the fundamental logical equivalent expressions:
Laws of the algebra of propositions
| Idempotent laws | (i) p ∨ p≅p | (ii) p ∧ p≅p |
| Associative laws | (i) (p ∨ q) ∨ r ≅ p∨ (q ∨ r) | (ii) (p ∧ q) ∧ r ≅ p ∧ (q ∧ r) |
| Commutative laws | (i) p ∨ q ≅ q ∨ p | (ii) p ∧ q ≅ q ∧ p |
| Distributive laws | (i) p ∨ (q ∧ r) ≅ (p ∨ q) ∧ (p ∨ r) | (ii) p ∧ (q ∨ r) ≅ (p ∧ q) ∨ (p ∧ r) |
| Identity laws | (i)p ∨ F ≅ p (iv) p ∧ F≅F | (ii) p ∧ T≅ p (iii) p ∨ T ≅ T |
| Involution laws | (i) ¬¬p ≅ p | |
| Complement laws | (i) p ∨ ¬p ≅ T | (ii) p ∧ ¬p ≅ T |
| DeMorgan's laws: | (i) ¬(p ∨ q) ≅ ¬p ∧ ¬q | (ii) ¬(p ∧ q) ≅¬p ∨ ¬q |
Example: Consider the following propositions
Are they equivalent?
Solution: Construct the truth table for both
| p | q | ~p | ~q | ~p∨∼q | p∧q | ~(p∧q) |
| T | T | F | F | F | T | F |
| T | F | F | T | T | F | T |
| F | T | T | F | T | F | T |
| F | F | T | T | T | F | T |
Truth Tables Examples
Example 1: Find the logical truth table for given values using conjunction.
If P: F F T F T and Q: F T T T F
Solution:
| P | Q | P ∧ Q |
| F | F | F |
| F | T | F |
| T | T | T |
| F | T | F |
| T | F | F |
Example 2: Construct the truth table for ~P∨∼Q and ∼(P∧Q).
Solution:
| P | Q | ~P | ~Q | ~P∨∼Q | (P∧Q) | ~(P∧Q) |
| T | T | F | F | F | T | F |
| T | F | F | T | T | F | T |
| F | T | T | F | T | F | T |
| F | F | T | T | T | F | T |
Example 3: Which of the following is the contrapositive of ‘if two triangles are identical, then these are similar’?
A) If two triangles are not similar, then they are not identical.
B) If two triangles are not identical, then these are not similar.
C) If two triangles are not identical, then these are similar.
D) If two triangles are not similar, then these are identical.
Solution:
Consider the following statements
p: Two triangles are identical.
q: Two triangles are similar.
Clearly, the given statement in symbolic form is p ⇒ q.
Therefore, its contrapositive is given by ∼q ⇒ ∼p
Now,
Example 4: The statement ~(p↔ ~q) is
A) equivalent to p↔q
B) equivalent to ~p↔q
C) a tautology
D) a fallacy
Solution:
| p | q | ∼q | p↔∼q | ∼(p↔∼q) | p↔q |
| T | T | F | F | T | T |
| T | F | T | T | F | F |
| F | T | F | T | F | F |
| F | F | T | F | T | T |
Example 5: Let S be a non-empty subset of R. Consider the following statement: P: There is a rational number x ∈ S such that x>0. Which of the following statements is the negation of the statement p?
A) x ∈ S and x ≤ 0 ⇒ x is not rational.
B) There is a rational number x ∈ S such that x ≤ 0.
C) There is no rational number x ∈ S such that x ≤ 0.
D) Every rational number x ∈ S satisfies x ≤ 0.
Solution:
P: There is a rational number x ∈ S such that x > 0.
~ P: Every rational number x ∈ S satisfies x ≤ 0.
0 Comments