A propositional variable is similar to any real variable you see in mathematics. For example xis a variable that can take any mathematical value. Similarly, a propositional variable, say P, can take any proposition as a value. The proposition as a value is called a propositional constant.
Definition:
WFFs produce a proposition. To construct a WFF for predicate logic, following rules are applicable:
(A) ‘True’ (T) and ‘False’ (F) are wffs.
(B) A propositional constant (i.e. a specific proposition) and each propositional variable are wffs.
(C) If P and Q are wffs then so are ¬P, P Ʌ Q, P V Q, P→Q and P ↔ Q.
(D) If x is a variable (representing objects of the universe of discourse) and P is a wff then so are ∀P and ∃P. (These are the existential quantifiers and will be focused upon in separate section).
(E) A string of propositional variables is a wff if and only if it is obtained by a finite number of applications of (A) – (D).
Truth table for a Well Formed Formula
If A is a WFF consisting of n propositional variables, then the table giving all possible truth values for the WFF A obtained by replacing these propositional variables by arbitrary truth values is called the truth table for A.
If WFF A has n propositional variables then there will be 2n possible combinations of truth values for these and hence 2n rows in the truth table for WFF A.
Example:
Construct the truth table for the following:
(P ∨ Q) → ((P ∨ R) → (R ∨ Q))
Solution: let’s denote the above WFF by A. A contains 3 propositional variables, hence there will be 23=8
rows in the truth table of A as obtained below:
|
P |
Q |
R |
P ∨ Q |
P ∨ R |
R ∨ Q |
(P ∨ R) → (R ∨Q) |
A |
|
F |
F |
F |
F |
F |
F |
T |
T |
|
F |
F |
T |
F |
T |
T |
T |
T |
|
F |
T |
F |
T |
F |
T |
T |
T |
|
F |
T |
T |
T |
T |
T |
T |
T |
|
T |
F |
F |
T |
T |
F |
F |
F |
|
T |
F |
T |
T |
T |
T |
T |
T |
|
T |
T |
F |
T |
T |
T |
T |
T |
|
T |
T |
T |
T |
T |
T |
T |
T |
Tautology and Contradiction
(a) Tautology: A WFF α is said to be a Tautology if in its truth table all the values in last column are T (True) only.
(b) Contradiction: A WFF α is said to be a Contradiction if in its truth table all the values in last column are F (False) only.
Equivalence of Well Formed Formulas
Two WFFs α and β are said to be equivalent (or logically equivalent) if the formula α ↔ β is a tautology. When α and β are equivalent, we write α ≡ β.
Example:
Prove the equivalence of following:
P ≡ (P ∨ Q) ∧ (P ∨ ¬Q)
Solution:
Let α denote P
And β denote (P ∨ Q) ∧ (P ∨ ¬Q)
Then we need to prove that α ↔ β is a tautology. This can be done with the help of following truth table:
|
P (α) |
Q |
¬Q |
P ∨ Q |
P ∨ ¬Q |
(P ∨ Q) ∧ (P ∨ ¬Q) (β) |
α ↔ β |
|
F |
F |
T |
F |
T |
F |
T |
|
F |
T |
F |
T |
F |
F |
T |
|
T |
F |
T |
T |
T |
T |
T |
|
T |
T |
F |
T |
T |
T |
T |
As we can see that the last column of the table (values for α ↔ β) contains the truth values T (True) only, this implies that α ↔ β is a tautology and hence the equivalence holds.
Logical identities
Definition: Logical identities are certain equivalences which can be used to simplify other complex WFFs.
The procedure for doing so is based on the following paradigm that if a WFF β is part of another WFF α and β is equivalent to β’ then, it can be replaced by β’ in α and the resulting WFF will still be equivalent to α.
All the logical identities can be proved by the equivalence proof method described above.
Some commonly useful logical identities are listed in the below:
1. Idempotent laws
P ∨ P ≡ P, P ∧ P ≡ P
2. Commutative law
P ∨ Q ≡ Q ∨ P, P ∧ Q ≡ Q ∧ P
3. Associative law
P ∨ (Q ∨ R) ≡ (P ∨ Q) ∨ R,
P ∧ (Q ∧ R) ≡ (P ∧ Q) ∧ R
4. Distributive law
P ∨ (Q ∧ R) ≡ (P ∨ Q) ∧ (P ∨ R),
P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
5. Absorption law
P ∨ (P ∧ Q) ≡ P,
P ∧ (P ∨ Q) ≡ P
6. De Morgan’s law
¬ (P ∨ Q) ≡ ¬P ∧ ¬Q,
¬ (P ∧ Q) ≡ ¬P ∨ ¬Q
7. Double negation
P ≡ ¬ (¬P)
8. P ∨ ¬P ≡ T, P ∧ ¬P ≡ F
9. P ∨ T ≡ T, P ∨ F ≡ P, P ∧ T ≡ P, P ∧ F ≡ F,
10. P → Q ≡ ¬P ∨ Q
11. (P → Q) ∧ (P → ¬Q) ≡ ¬P
12. Contrapositive
P → Q ≡ ¬Q → ¬P
(NOTE: Try to remember as many identities as you can. These are a real help in the exams.)
Example:
We’ve proven the following equivalence by method of truth table above:
P ≡ (P ∨ Q) ∧ (P ∨ ¬Q)
Now let’s prove the same by using logical identities.
Solution:
Taking the R.H.S.:
R.H.S. ≡ (P ∨ Q) ∧ (P ∨ ¬Q)
≡ P ∨ (Q ∧ ¬Q) (Distributive Law)
≡ P ∨ F
≡ P
≡ L.H.S.