Tautological implication
Dr. S. Ramesh
Department of Mathematics
Institute of Science
GITAM(Deemed to be University)
Tautological implication Dr.S.Ramesh, Dept. of Mathematics,GIS
Symmetric connectives
It is clear that ∧, ∨ and ⇄ are symmetric.
(That is (P ∧ Q) ⇔ (Q ∧ P), (P ∨ Q) ⇔ (Q ∨ P) and (P ⇄ Q) ⇔ (Q ⇄ P)).
Non-symmetric connective
But P → Q is not symmetric.
(That is (P → Q) is not equivalent to (Q → P)).
Tautological implication Dr.S.Ramesh, Dept. of Mathematics,GIS
Converse statement
If (P → Q) is a statement formula, then (Q → P) is called the converse statement of
(P → Q).
Contrapositive statement
If (P → Q) is a statement formula, then (ℸQ → ℸP) is called the contrapositive
statement of (P → Q).
Inverse statement
If (P → Q) is a statement formula, then (ℸP → ℸQ) is called the inverse statement
of (P → Q).
Tautological implication Dr.S.Ramesh, Dept. of Mathematics,GIS
Tautologically imply
A statement formula A is said to be “tautologically imply” a statement formula B if
and only if A → B is a tautology. It is denoted by A =⇒ B.
Tautological implication Dr.S.Ramesh, Dept. of Mathematics,GIS
Some Tautological implications
1. (P ∧ Q) =⇒ P
2. (P ∧ Q) =⇒ Q
3. P =⇒ (P ∨ Q)
4. Q =⇒ (P ∨ Q)
5. ℸP =⇒ (P → Q)
6. Q =⇒ (P → Q)
7. ℸ(P → Q) =⇒ P
8. ℸ(P → Q) =⇒ ℸQ
9. P ∧ (P → Q) =⇒ Q
10. ℸQ ∧ (P → Q) =⇒ ℸP
11. ℸP ∧ (P ∨ Q) =⇒ Q
12. (P → Q) ∧ (Q → R) =⇒ (P → R)
13. (P ∨ Q) ∧ (P → R) ∧ (Q → R) =⇒ R
Tautological implication Dr.S.Ramesh, Dept. of Mathematics,GIS
Remarks
▶ If a statement formula is equivalent to a tautology, the it must be be a tautology.
▶ If a statement formula is tautological implied by a tautology, then it is a tautology.
▶ Tautological implication is transitive. (That is A =⇒ B and B =⇒ C , then
A =⇒ C ).
▶ If A =⇒ B and A =⇒ C , then A =⇒ B ∧ C .
▶ If H1 , H2 , · · · , Hn =⇒ Q, then (H1 ∧ H2 ∧ · · · ∧ Hn ) =⇒ Q.
▶ If H1 , H2 , · · · , Hn and P =⇒ Q, then H1 , H2 · · · Hn =⇒ (P → Q).
Tautological implication Dr.S.Ramesh, Dept. of Mathematics,GIS
Problems
1. Show that (P ∧ Q) =⇒ (P → Q).
2. Show that P =⇒ (Q → P).
3. Show that (P → (Q → R)) =⇒ ((P → Q) → (P → R)).
4. Show that P → Q =⇒ P → (P ∧ Q).
5. Show that ((P → Q) → Q) =⇒ (P ∨ Q).
6. Show that ((P ∨ ℸP) → Q) → ((P ∨ ℸP) → R) =⇒ (Q → R).
7. Show that (Q → (P ∧ ℸP)) → (R → (P ∧ ℸP)) =⇒ (R → Q).
Tautological implication Dr.S.Ramesh, Dept. of Mathematics,GIS
THANK YOU
Tautological implication Dr.S.Ramesh, Dept. of Mathematics,GIS
