Table of Contents
Algebra of Statements:
A compound proposition having component statements p, q, r, … may be denoted by P(p, q, r, …). Two compound statements P1(p, q, r, …) and P2(p, q, r, …) having component statements p, q, r, … are said to be logically equivalent (or simply equivalent or equal) if they have identical truth values and in that case, we write P1(p, q, r, …) ≡ P2(p, q, r, …).
Various Laws on the Algebra of Statements are discussed below:
Idempotent Laws:
For any statement p, (a) p ∨ p ≡ p (b) p ∧ p ≡ p
Proof: The table showing the truth values of p ∨ p and p ∧ p is constructed as shown below.
| p | p ∨ p | p ∧ p |
|---|---|---|
| T | T | T |
| F | F | F |
From the truth table, it is clear that p ∨ p ≡ p and p ∧ p ≡ p.
Identity Laws:
For any statement p, if t and c are some tautology and contradiction respectively in terms of the statement p, then (a) p ∨ t ≡ t (b) p ∨ c ≡ p (c) p ∧ t ≡ p (d) p ∧ c ≡ c
Proof: The truth values of p ∨ t, p ∨ c, p ∧ t, and p ∧ c are shown below.
| p | t | c | p ∨ t | p ∨ c | p ∧ t | p ∧ c |
|---|---|---|---|---|---|---|
| T | T | F | T | T | T | F |
| F | T | F | T | F | F | F |
Thus, from the truth table, it is clear that p ∨ t ≡ t, p ∨ c ≡ p, p ∧ t ≡ p, and p ∧ c ≡ c.
Complement Laws:
For any statement p, if t and c are respectively some tautology and contradiction in terms of p, then (a) p ∨ (~p) ≡ t (b) p ∧ (~p) ≡ c (c) ~ (~p) ≡ p (d) ~t ≡ c (e) ~c ≡ t
Proof: The truth table showing the truth values of p ∨ (~p), p ∧ (~p), ~ (~p), ~t, and ~c is constructed as shown below.
| p | ~p | p ∨ ~p | t | p ∧ ~p | c | ~ (~p) | ~t | ~c |
|---|---|---|---|---|---|---|---|---|
| T | F | T | T | F | F | T | F | T |
| F | T | T | T | F | F | F | F | T |
From the table, we see that p ∨ (~p) ≡ t, p ∧ (~p) ≡ c, ~ (~p) ≡ p, ~t ≡ c, and ~c ≡ t.
Commutative Laws:
For any two statements p and q, (a) p ∨ q ≡ q ∨ p (b) p ∧ q ≡ q ∧ p
Proof: The table showing the truth values of the conjunction and disjunction of the statements p and q is constructed as shown below.
| p | q | p ∨ q | q ∨ p | p ∧ q | q ∧ p |
|---|---|---|---|---|---|
| T | T | T | T | T | T |
| T | F | T | T | F | F |
| F | T | T | T | F | F |
| F | F | F | F | F | F |
Thus, p ∨ q ≡ q ∨ p and p ∧ q ≡ q ∧ p.
Associative Laws:
For any three statements p, q, and r (a) (p ∨ q) ∨ r ≡ p ∨ (q ∨ r) (b) (p ∧ q) ∧ r ≡ p ∧ (q ∧ r)
Proof: (a) The table showing the truth values of (p ∨ q) ∨ r and p ∨ (q ∨ r) is constructed as shown.
| p | q | r | p ∨ q | q ∨ r | (p ∨ q) ∨ r | p ∨ (q ∨ r) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | T | T | T |
| T | F | T | T | T | T | T |
| T | F | F | T | F | T | T |
| F | T | T | T | T | T | T |
| F | T | F | T | T | T | T |
| F | F | T | F | T | T | T |
| F | F | F | F | F | F | F |
As the last two columns are identical, we conclude that (p ∨ q) ∨ r ≡ p ∨ (q ∨ r).
(b) For the truth values of (p ∧ q) ∧ r and p ∧ (q ∧ r), the following table is constructed.
| p | q | r | p ∧ q | q ∧ r | (p ∧ q) ∧ r | p ∧ (q ∧ r) |
|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T |
| T | T | F | T | F | F | F |
| T | F | T | F | F | F | F |
| T | F | F | F | F | F | F |
| F | T | T | F | T | F | F |
| F | T | F | F | F | F | F |
| F | F | T | F | F | F | F |
| F | F | F | F | F | F | F |
From the last two columns, it is clear that (p ∧ q) ∧ r ≡ p ∧ (q ∧ r).
Distributive Laws:
For any three statements p, q, and r (a) p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) (b) p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r)
Proof: (a) The table showing the truth values of p ∧ (q ∨ r) and (p ∧ q) ∨ (p ∧ r) is shown below.
| p | q | r | q ∨ r | p ∧ q | p ∧ r | p ∧ (q ∨ r) | (p ∧ q) ∨ (p ∧ r) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | T | T | F | T | T |
| T | F | T | T | F | T | T | T |
| T | F | F | F | F | F | F | F |
| F | T | T | T | F | F | F | F |
| F | T | F | T | F | F | F | F |
| F | F | T | T | F | F | F | F |
| F | F | F | F | F | F | F | F |
From the last two columns, it is evident that p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r).
(b) The truth table for p ∨ (q ∧ r) and (p ∨ q) ∧ (p ∨ r) is shown below.
| p | q | r | q ∧ r | p ∨ q | p ∨ r | p ∨ (q ∧ r) | (p ∨ q) ∧ (p ∨ r) |
|---|---|---|---|---|---|---|---|
| T | T | T | T | T | T | T | T |
| T | T | F | F | T | T | T | T |
| T | F | T | F | T | T | T | T |
| T | F | F | F | T | T | T | T |
| F | T | T | T | T | T | T | T |
| F | T | F | F | T | F | F | F |
| F | F | T | F | F | T | F | F |
| F | F | F | F | F | F | F | F |
It is clear from the last two columns that p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r).
De-Morgan’s Laws:
For any two statements p and q, (a) ~ (p ∧ q) ≡ ~ p ∨ ~ q (b) ~ (p ∨ q) ≡ ~ p ∧ ~ q
Proof: The following truth table is constructed.
| p | q | ~ p | ~ q | p ∧ q | ~ (p ∧ q) | p ∨ q | ~ (p ∨ q) | ~ p ∧ ~ q | ~ p ∨ ~ q |
|---|---|---|---|---|---|---|---|---|---|
| T | T | F | F | T | F | T | F | F | F |
| T | F | F | T | F | T | T | F | F | T |
| F | T | T | F | F | T | T | F | F | T |
| F | F | T | T | F | T | F | T | T | T |
From the table, we get ~ (p ∧ q) ≡ ~ p ∨ ~ q and ~ (p ∨ q) ≡ ~ p ∧ ~ q.
Duality:
Two logically equivalent statements are said to be dual to each other with respect to two connectives if one of the equivalences can be obtained from the other by the mere interchange of the connectives. Thus, the two equivalence p ∨ (q ∧ r) ≡ (p ∨ q) ∧ (p ∨ r) and p ∧ (q ∨ r) ≡ (p ∧ q) ∨ (p ∧ r) are dual to each other with respect to the connectives ‘∨’ and ‘∧’.
Application of Logic in Solving Simple Problems:
Before we proceed to discuss the method of solving simple problems by applying logic, we need to be familiar with some relevant terms.
An argument is a statement indicating that a given set of n compound statements p1, p2, … pn yield another compound statement Q and is represented by the symbol p1, p2, …. pn ⊢ Q.
The compound statements p1, p2, …. pn are known as assumptions (or premises or hypothesis), and the compound statement Q is called the conclusion. The symbol ‘⊢’ is known as the turnstile.
An argument is said to be a valid argument if it is true. The argument p1, p2, …. pn ⊢ Q is true if Q is true whenever p1, p2, …. pn are all true; otherwise the argument is false.
For solving simple problems with the help of mathematical logic the steps are-
- The component statements p, q, r … of the given argument are identified.
- The assumptions in the given argument are identified and are denoted by p1, p2, …
- The conclusion in the given argument is identified and denoted by Q.
- The assumptions p1, p2, p3, … and the conclusion Q is expressed in terms of p, q, r, …
- Constructing the truth table, the truth values of p1, p2, p3, …, and Q are found out.
- The arguments p1, p2, p3, … ⊢ Q is valid if Q is found to be true whenever p1, p2, p3, … are all true, otherwise it is declared to be invalid.
| Example 1: Using the laws of the algebra of statements prove the following equivalences: (a) (p ∧ t) ∨ (p ∧ q) ≡ p Solution- (p ∧ t) ∨ (p ∧ q) ≡ p ∧ (t ∨ q) [∵ (p ∧ q) ∨ (p ∧ r) = p ∧ (q ∨ r), from Distributive Law] ≡ p ∧ t [∵ t ∨ q = t] ≡ p (b) p ∧ (p ∨ q) ≡ p ∨ (p ∧ q) Solution- p ∧ (p ∨ q) ≡ (p ∧ p) ∨ (p ∧ q) [∵ p ∧ (q ∨ r) = (p ∧ q) ∨ (p ∧ r), from Distributive Law] ≡ p ∨ (p ∧ q) [∵ p ∧ p = p] (c) ~ (p ∨ q) ∨ (~ p ∧ q) ≡ ~ p Solution- ~ (p ∨ q) ∨ (~ p ∧ q) ≡ (~ p ∧ ~ q) ∨ (~ p ∧ q) [De-Morgan’s Law] ≡ ~ p ∧ (~ q ∨ q) [∵ (p ∧ q) ∨ (p ∧ r) = p ∧ (q ∨ r), from Distributive Law] ≡ ~ p ∧ t [∵ ~ q ∨ q = t] ≡ ~ p |
| Example 2: Determine the validity of the following argument. ‘If 5 is less than 3’ then 5 is not a prime number. 5 is not less than 3. Therefore, 5 is a prime number. Solution- Let us first translate the argument into symbolic form. Let p denote the statement ‘5 is less than 3’ and q be the statement ‘5 is not a prime number’. The assumptions are p ⇒ q, ~ p and the conclusion is ~ q. Let p1 ≡ p ⇒ q, p ≡ ~ p and Q ≡ ~ q. Thus, the given argument may be written as p1, p2 ⊢ Q. To find the truth values of p1, p2, and Q, the following truth table is constructed. |
| p | q | p1 ≡ p ⇒ q | p ≡ ~ p | Q ≡ ~ q |
|---|---|---|---|---|
| T | T | T | F | F |
| T | F | F | F | T |
| F | T | T | T | F |
| F | F | T | T | T |
In the third row p1 and p2 are true but Q is not true. Thus, the given argument is not valid.
Comments (No)