Theory, which is associated with the inferring of conclusion from the given set of premises using accepted rules of reasoning, is called the theory of inference.
The process of derivation of a conclusion from the given set of premises using the rules of inference is known as formal proof or deduction.
In a formal proof, every rule of inference that is used at any stage in the derivation is acknowledged. The rules of implications and equivalences are used as the accepted rules in inference theory.
1.3.1 Validity Using Truth Tables
Let A and B two statement formulas we say that "B logically follows from A" or "B is a valid conclusion (consequence) of the premise A" iff A®B is a tautology. That is, . From a set of premises {H_{1}, H_{2}, . . ., H_{m}} a conclusion C follows logically iff .
1.3.2 Testing the Validity of a Conclusion
Let P_{1}, P_{2}, … , P_{n} be all the atomic variables appearing in the premises H_{1},H_{2}, … , H_{m} and the conclusion C.
In order to test the validity of a conclusion C from the premises H_{1}, H_{2}, … , H_{m} using truth table, we assign all possible combinations of truth values to all variables P_{1}, P_{2}, … , P_{n} that occur in H_{1}, H_{2}, … , H_{m} and C. Construct truth table of the premises and conclusion. Look for the rows in which all the H_{i}’s are true (T). If for every such row C is true, then C is a valid conclusion from the premises and hence H_{1}Ù H_{2}Ù …Ù H_{n} Þ C or look for rows in which C has a truth value false (F). If, in every such row, atleast one of the values of H_{1},H_{2},…,H_{m} is F, then C is a valid conclusion from the premises.
Example 1:
Determine whether the conclusion C follows logically from the premises H_{1} and H_{2}.
(a) H_{1} : P® Q H_{2} : P C : Q
P | Q | H_{1} | H_{2} | C |
T | T | T | T | T |
T | F | F | T | F |
F | T | F | F | T |
F | F | T | F | F |
If H_{1} and H_{2} have truth values T, then check C. If C has truth value T, then
H_{1} Ù H_{2} Þ C. The first row (in H_{1} and H_{2}) in which both premises have the value T. The conclusion C has the value T in that row. Therefore H_{1}Ù H_{2} Þ C. It is a valid conclusion.
(b) H_{1} : P® Q H_{2} : ù P C : Q
P | Q | H_{1} | H_{2} | C |
T | T | T | F | T |
T | F | F | F | F |
F | T | T | T | T |
F | F | T | T | F |
Check the third and fourth row. The conclusion Q is true only in the third row, but not in the fourth.
Hence the conclusion is not valid.
(c) H_{1} : P® Q H_{2} : ù (PÙ Q) C : ù P
P | Q | H_{1} | H_{2} | C |
T | T | T | F | F |
T | F | F | T | F |
F | T | T | T | T |
F | F | T | T | T |
Check third and fourth row, the conclusion C has true in both rows. Therefore it is a valid conclusion.
(d) H_{1} : ù P H_{2} : PÚ Q C : PÙ Q
P | Q | H_{1} | H_{2} | C |
T | T | F | T | T |
T | F | F | T | F |
F | T | T | T | F |
F | F | T | F | F |
Check the third row. The conclusion C has value F therefore it is not a valid conclusion.
(e) H_{1} : P® (Q® R) H_{2} : R C : P
P | Q | R | Q® R | H_{1} | H_{2} | C |
T | T | T | T | T | T | T |
T | T | F | F | F | F | T |
T | F | T | T | T | T | T |
T | F | F | T | T | F | T |
F | T | T | T | T | T | F |
F | T | F | F | F | F | F |
F | F | T | T | T | T | F |
F | F | F | T | T | F | F |
Check first, third, fifth and seventh rows. But C has truth value T only in first, third but not in fifth and seventh. Therefore, it is not a valid conclusion.
(f) H_{1} : PÚ Q H_{2} : P® R H_{3} : Q® R C : R
P | Q | R | H_{1} | H_{2} | H_{3} | C |
T | T | T | T | T | T | T |
T | T | F | T | F | F | F |
T | F | T | T | T | T | T |
T | F | F | T | F | T | F |
F | T | T | T | T | T | T |
F | T | F | T | T | F | F |
F | F | T | F | T | T | T |
F | F | F | F | T | T | F |
Check first, third and fifth rows. In all the above said rows H_{1}, H_{2}, H_{3} and C have truth value T. Therefore, it is a valid conclusion.
1.3.3 Rules of Inference
Consider
Rule P : A premise may be introduced at any point in the derivation.
Rule T : A formula S may be introduced in a derivation if S is tautologically implied by one or more of the preceding formulas in the derivation.
Table 1.3.3 : Implications
I_{6} Q Þ P® Q
I_{7} ù (P® Q) Þ P
I_{8} ù (P® Q) Þ ù Q
I_{9} P,Q Þ PÙ Q
I_{10} ù P,P Ú QÞ Q
I_{11} P, P® QÞ Q
I_{12} ù Q, P® QÞ ù P
I_{13} P® Q, Q® R Þ P® R
I_{14} PÚ Q, P® R, Q® R Þ R
Table 1.3.4 : Equivalences
E_{1} ù ù P Û P
E_{11} P Ù P Û P
E_{12} R Ú (P Ù ù P) Û R
E_{13} R Ù (P Ú ù P) Û R
E_{14} R Ú (P Ú ùP) Û T
E_{15} R Ù (P Ù ùP) Û F.
E_{16} P ® Q Û ù P Ú Q
E_{17} ù (P ® Q) Û PÙ ù Q
E_{18} P ® Q Û ù Q ® ù P
E_{19} P ® (Q ® R) Û (PÙ Q)® R
E_{20} ù (P Q) Û P ù Q
E_{21} P Q Û (P® Q)Ù (Q® P)
E_{22} (P Q) Û (PÙ Q) Ú (ù PÙ ù Q)
Example 1:
Show that R is a valid inference from the premises P® Q, Q® R, and P.
Solution:
{1} (1) P® Q Rule P
{2} (2) P Rule P
{1,2} (3) Q Rule T, (1), (2) and I_{11} (P, P® Q Û Q)
{4} (4) Q® R Rule P
{1, 2, 4} (5) R Rule T, (3), (4) and I_{11 }
Therefore, R is a valid inference.
Example 2:
Show that P Ú Q follows logically from the premises C Ú D, (C Ú D) ® ù H,
ù H® (A Ù ùB) and (A Ù ùB) ® (PÚ Q).
Solution :
{1} (1) (C Ú D) Rule P
{2} (2) (C Ú D)® ùH Rule P
{1, 2} (3) ù H Rule T, (1), (2) and I_{11 }
{4} (4) ù H® (A Ù ùB) Rule P
{1, 2, 4} (5) A Ù ùB Rule T, (3), (4) and I_{11 }
{6} (6) (A Ù ùB)® (P Ú Q) Rule P
{1, 2, 4, 6} (7) P Ú Q Rule T, (5), (6) and I_{11 }
Example 3:
Show that SÚ R is tautologically implied by (PÚ Q) Ù (P® R) Ù (Q® S).
Solution:
{1} (1) P Ú Q Rule P
{1} (2) ù P ® Q Rule T, (1), E_{1} and E_{16}
{3} (3) Q® S Rule P
{1,3} (4) ù P® S Rule T, (2), (3) and I_{13 }
{1,3} (5) ù S® P Rule T, (4) and E_{18 }
{6} (6) P® R Rule P
{1,3,6} (7) ù S® R Rule T, (5), (6) and I_{13 }
{1,3,6} (8) SÚ R Rule T, (7), E_{16} and E_{1 }
Example 4:
Show that (PÚ Q) Ù R is a valid conclusion from the premises PÚ Q, Q® R, P® M and ù M.
Solution :
{1} (1) ù M Rule P
{2} (2) P® M Rule P
{1,2} (3) ù P Rule T, (1), (2) and I_{12 }
{4} (4) PÚ Q Rule P
{1, 2, 4} (5) Q Rule T, (3), (4) and I_{10 }
{6} (6) Q® R Rule P
{1, 2, 4, 6} (7) R Rule T, (5), (6) and I_{11 }
{1, 2, 4, 6} (8) (P Ú Q)Ù R Rule T, (4), (7) and I_{9 }
Example 5:
Show that ùP is a valid inference solution form ùQ, P® Q.
Solution:
{1} (1) P® Q Rule P
{1} (2) ùQ® ùP Rule T, (1) and E_{18 }
{3} (3) ùQ Rule P
{1, 3} (4) ùP Rule T, (2), (3), and I_{11 }
Example 6:
Show that R is a valid inference from the premises PÚ Q, P® R, Q® R.
Solution:
{1} (1) PÚ Q Rule P
{2} (2) Q® R Rule P
{1, 2} (3) ùP® R Rule T, (1), (2) and I_{13 }
{4} (4) P® R Rule P
{1, 2} (5) ùR® P Rule T, (3) and E_{16 }
{1, 2, 4} (6) R Rule T, (4), (5) and I_{13 }
Rule CP: Rule of Conditional Proof.
If we can derive S from R and a set of premises, then we can derive R® S from the set of premises alone.
If the conclusion is of the form R® S, then R is taken as an additional premise and S is derived from the given premises and R.
Example 7:
Show that R® S can be derived from the premises P® (Q® S), ùRÚ P, and Q.
Solution:
We shall include R as an additional premise and show S first
{1} (1) ùRÚ P Rule P
{2} (2) R Rule P (assumed premise)
{1, 2} (3) P Rule T, (1), (2) and I_{10 }
{4} (4) P® (Q® S) Rule P
{1, 2, 4} (5) Q® S Rule T, (3), (4) and I_{11 }
{6} (6) Q Rule P
{1, 2, 4, 6} (7) S Rule T, (5), (6) and I_{11 }
{1, 2, 4, 6} (8) R® S Rule CP
1.3.4 Consistency of Premises and Indirect Method of Proof.
A set of formulas H_{1},H_{2},…,H_{m} is said to be consistent if their conjunction has the truth value T for some assignment of the truth values to the atomic variables appearing in H_{1},H_{2},…,H_{m}.
If, for every assignment of the truth values to the atomic variables, atleast one of the formulas H_{1},H_{2},…,H_{m} is false, so that their conjunction is identically false, then the formulas H_{1},H_{2},…,H_{m} are called inconsistent.
A set of formulas H_{1}, H_{2},…,H_{m} are inconsistent if their conjunction implies a contradiction.
That is, H_{1Ù }H_{2Ù }…Ù H_{m} Þ R Ù ùR
where R is any formula. R Ù ùR is a contradiction.
In order to show that a conclusion C follows logically from the premises
H_{1}, H_{2}, … , H_{m} we assume that C is false and consider ù C as an additional premises.
Example 1:
Show that ù(PÙ Q) follows from ùPÙ ùQ.
Solution:
We introduce ù ù(PÙ Q) as an additional premise and show that this additional premise leads to contradiction.
{1} (1) ù ù(PÙ Q) Rule P(assumed)
{1} (2) PÙ Q Rule T, (1), and E_{1}
{1} (3) P Rule T, (2) and I_{1}
{4} (4) ùPÙ ùQ Rule P
{4} (5) ùP Rule T, (4) and I_{1}
{1, 4} (6) PÙ ùP Rule T, (3), (5) and I_{9}
Example 2:
Show that the given premises P® Q, P® R, Q® ùR, P are inconsistent.
Solution:
{1} (1) P® Q Rule P
{2} (2) Q® ùR Rule P
{1, 2} (3) P® ùR Rule T, (1), (2) and I_{13}
{4} (4) P® R Rule P
{5} (5) P Rule P
{4, 5} (6) R Rule T, (4), (5) and I_{11}
{1, 2, 5} (7) ùR Rule T, (3), (5), and I_{11}
{1, 2, 4, 5} (8) R Ù ùR Rule T, (6), (7) and I_{9}
Example 3:
Show the following premises are inconsistent
- If Jack misses many classes through illness, then he fails high school.
- If Jack fails high school, then he is uneducated.
- If Jack reads a lot of books, then he is not uneducated.
- Jack misses many classes through illness and reads a lot of books.
Solution :
P : Jack misses many classes.
Q : Jack fails high school.
R : Jack reads a lot of books.
S : Jack is uneducated.
The premises are P ® Q, Q® S, R® ù S, and P Ù R.
{1} (1) P ® Q Rule P
{2} (2) Q® S Rule P
{1,2} (3) P ® S Rule T, (1), (2) and I_{13}
{4} (4) R ® ùS Rule P
{4} (5) S ® ùR Rule T, (4) and E_{18}
{1,2,4} (6) P ® ùR Rule T, (3) (5) and I_{13}
{1,2,4} (7) ùPÚùR Rule T, (5) and E_{16}
{1,2,4} (8) ù(PÙ R) Rule T, (6) and E_{8}
{9} (9) PÙ R Rule P
{1,2,4,9} (10) (PÙ R) Ù ù(PÙ R) Rule T, (8), (9) and I_{9}
Back to top
Exercise:
- Show that the conclusion C follows from the premises H_{1}, H_{2}, …… in the following cases.
- Determine whether the conclusion C is valid in the following, where H_{1},H_{2},…… are the premises.
(a) H_{1 }: P® Q C : P® (PÙ Q)
(b) H_{1 }: ùPÚ Q H_{2 }: ù(QÙùR) H_{3 }: ùR C : ùP
(c) H_{1 }: ùP H_{2 }: PÚ Q C : Q
(d) H_{1 }: ùP H_{2 }: P® Q C : ùP
(e) H_{1 }: P® Q H_{2 }: Q® R C : P® R
(f) H_{1 }: R H_{2 }: PÚùP C : R
(b) H_{1 }: PÚ Q H_{2} : P® R H_{3} : Q® R C : R
(c) H_{1} : P® (Q® R) H_{2} : PÙ Q C : R
3. Without constructing a truth table, show that AÙ E is not a valid consequence of A B,
B (CÙD), C (AÚ E), AÚ E.
Also show that AÚC is not a valid consequence of A (B® C), B (ùAÚùC), C (AÚùB), B.
4. Show that AÚB follows from PÙ QÙ R, (Q R)® (AÚB).
5. Show without constructing truth tables that the following statements cannot all be true simultaneously.
(a) P Q Q® R ù RÚS ù P® S ù S
(b) RÚM ù RÚS ù M ù S
1 comment:
Good Job .....
Ankit
www.onlykaraoke.in
Post a Comment