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 {H1, H2, . . ., Hm} a conclusion C follows logically iff 
.
1.3.2 Testing the Validity of a Conclusion
Let P1, P2, … , Pn be all the atomic variables appearing in the premises H1,H2, … , Hm and the conclusion C.
In order to test the validity of a conclusion C from the premises H1, H2, … , Hm using truth table, we assign all possible combinations of truth values to all variables P1, P2, … , Pn that occur in H1, H2, … , Hm and C. Construct truth table of the premises and conclusion. Look for the rows in which all the Hi’s are true (T). If for every such row C is true, then C is a valid conclusion from the premises and hence H1Ù H2Ù …Ù Hn Þ 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 H1,H2,…,Hm is F, then C is a valid conclusion from the premises.
Example 1:
Determine whether the conclusion C follows logically from the premises H1 and H2.
(a) H1 : P® Q H2 : P C : Q
| P | Q | H1 | H2 | C |
| T | T | T | T | T |
| T | F | F | T | F |
| F | T | F | F | T |
| F | F | T | F | F |
If H1 and H2 have truth values T, then check C. If C has truth value T, then
H1 Ù H2 Þ C. The first row (in H1 and H2) in which both premises have the value T. The conclusion C has the value T in that row. Therefore H1Ù H2 Þ C. It is a valid conclusion.
(b) H1 : P® Q H2 : ù P C : Q
| P | Q | H1 | H2 | 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) H1 : P® Q H2 : ù (PÙ Q) C : ù P
| P | Q | H1 | H2 | 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) H1 : ù P H2 : PÚ Q C : PÙ Q
| P | Q | H1 | H2 | 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) H1 : P® (Q® R) H2 : R C : P
| P | Q | R | Q® R | H1 | H2 | 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) H1 : PÚ Q H2 : P® R H3 : Q® R C : R
| P | Q | R | H1 | H2 | H3 | 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 H1, H2, H3 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
I6 Q Þ P® Q
I7 ù (P® Q) Þ P
I8 ù (P® Q) Þ ù Q
I9 P,Q Þ PÙ Q
I10 ù P,P Ú QÞ Q
I11 P, P® QÞ Q
I12 ù Q, P® QÞ ù P
I13 P® Q, Q® R Þ P® R
I14 PÚ Q, P® R, Q® R Þ R
Table 1.3.4 : Equivalences
E1 ù ù P Û P
E11 P Ù P Û P
E12 R Ú (P Ù ù P) Û R
E13 R Ù (P Ú ù P) Û R
E14 R Ú (P Ú ùP) Û T
E15 R Ù (P Ù ùP) Û F.
E16 P ® Q Û ù P Ú Q
E17 ù (P ® Q) Û PÙ ù Q
E18 P ® Q Û ù Q ® ù P
E19 P ® (Q ® R) Û (PÙ Q)® R
E20 ù (P
Q) Û P ù Q
E21 P Q Û (P® Q)Ù (Q® P)
E22 (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 I11 (P, P® Q Û Q)
{4} (4) Q® R Rule P
{1, 2, 4} (5) R Rule T, (3), (4) and I11
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 I11
{4} (4) ù H® (A Ù ùB) Rule P
{1, 2, 4} (5) A Ù ùB Rule T, (3), (4) and I11
{6} (6) (A Ù ùB)® (P Ú Q) Rule P
{1, 2, 4, 6} (7) P Ú Q Rule T, (5), (6) and I11
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), E1 and E16
{3} (3) Q® S Rule P
{1,3} (4) ù P® S Rule T, (2), (3) and I13
{1,3} (5) ù S® P Rule T, (4) and E18
{6} (6) P® R Rule P
{1,3,6} (7) ù S® R Rule T, (5), (6) and I13
{1,3,6} (8) SÚ R Rule T, (7), E16 and E1
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 I12
{4} (4) PÚ Q Rule P
{1, 2, 4} (5) Q Rule T, (3), (4) and I10
{6} (6) Q® R Rule P
{1, 2, 4, 6} (7) R Rule T, (5), (6) and I11
{1, 2, 4, 6} (8) (P Ú Q)Ù R Rule T, (4), (7) and I9
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 E18
{3} (3) ùQ Rule P
{1, 3} (4) ùP Rule T, (2), (3), and I11
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 I13
{4} (4) P® R Rule P
{1, 2} (5) ùR® P Rule T, (3) and E16
{1, 2, 4} (6) R Rule T, (4), (5) and I13
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 I10
{4} (4) P® (Q® S) Rule P
{1, 2, 4} (5) Q® S Rule T, (3), (4) and I11
{6} (6) Q Rule P
{1, 2, 4, 6} (7) S Rule T, (5), (6) and I11
{1, 2, 4, 6} (8) R® S Rule CP
1.3.4 Consistency of Premises and Indirect Method of Proof.
A set of formulas H1,H2,…,Hm 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 H1,H2,…,Hm.
If, for every assignment of the truth values to the atomic variables, atleast one of the formulas H1,H2,…,Hm is false, so that their conjunction is identically false, then the formulas H1,H2,…,Hm are called inconsistent.
A set of formulas H1, H2,…,Hm are inconsistent if their conjunction implies a contradiction.
That is, H1Ù H2Ù …Ù Hm Þ 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
H1, H2, … , Hm 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 E1
{1} (3) P Rule T, (2) and I1
{4} (4) ùPÙ ùQ Rule P
{4} (5) ùP Rule T, (4) and I1
{1, 4} (6) PÙ ùP Rule T, (3), (5) and I9
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 I13
{4} (4) P® R Rule P
{5} (5) P Rule P
{4, 5} (6) R Rule T, (4), (5) and I11
{1, 2, 5} (7) ùR Rule T, (3), (5), and I11
{1, 2, 4, 5} (8) R Ù ùR Rule T, (6), (7) and I9
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 I13
{4} (4) R ® ùS Rule P
{4} (5) S ® ùR Rule T, (4) and E18
{1,2,4} (6) P ® ùR Rule T, (3) (5) and I13
{1,2,4} (7) ùPÚùR Rule T, (5) and E16
{1,2,4} (8) ù(PÙ R) Rule T, (6) and E8
{9} (9) PÙ R Rule P
{1,2,4,9} (10) (PÙ R) Ù ù(PÙ R) Rule T, (8), (9) and I9
Back to top
Exercise:
- Show that the conclusion C follows from the premises H1, H2, …… in the following cases.
- Determine whether the conclusion C is valid in the following, where H1,H2,…… are the premises.
(a) H1 : P® Q C : P® (PÙ Q)
(b) H1 : ùPÚ Q H2 : ù(QÙùR) H3 : ùR C : ùP
(c) H1 : ùP H2 : PÚ Q C : Q
(d) H1 : ùP H2 : P® Q C : ùP
(e) H1 : P® Q H2 : Q® R C : P® R
(f) H1 : R H2 : PÚùP C : R
(b) H1 : PÚ Q H2 : P® R H3 : Q® R C : R
(c) H1 : P® (Q® R) H2 : 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