PROPOSITIONAL CALCULUS
- Propositions.
- Logical connectives.
- Compound propositions.
- Conditional and biconditional propositions.
- Truth tables.
- Tautologies and contradictions.
- Contra positive.
- Logical equivalences and implications.
- DeMorgan’s Laws.
- Normal forms - Principal conjunctive and disjunctive.
- Rules of inference – Arguments - Validity of arguments.
1.1 Logic
1.1.1 Introduction
1.1.2 Atomic Statements
1.1.3 Connectives
1.1.4 Negation
1.1.5 Conjunction
1.1.6 Disjunction
1.1.7 Conditional and Bi-conditional
1.1.8 Well Formed Formulas
1.1.9 Tautologies
1.1.10 Equivalence of Formulas
1.1.1 Introduction
One of the main aims of logic is to provide rules by which one can determine whether any particular argument or reasoning is valid (correct).
Logic is concerned with all kinds of reasoning’s, whether they are legal arguments or mathematical proofs or conclusions in a scientific theory based upon a set of hypothesis. Based on the diversity of their application, these rules are called rules of inference. In logic we are concerned with the forms of the arguments. The theory of inference is formulated in such a way that one should be able to decide about the validity of an argument by following the rules mechanically and independently of our own feelings about the argument.
Any collection of rules or any theory needs a language. In this language these rules or theory can be explained. Natural languages are not used, and are not suitable for this purpose. Therefore, a formal language (object language) is developed and syntax is well defined in the object language. Symbols are used to define clearly in the object language. The object language requires the use of another language. We can use any of the natural languages like English to form the statements. Here English is called met language.
1.1.2 Atomic Statements
The object language consists of a set of declarative sentences. These declarative sentences are called primary or atomic or primitive statements. These statements have only two truth vales TRUE (T or 1) and FALSE (F or 0). The atomic statements are denoted by the symbols A, B, C, D, E …
The atomic statements are joined by using symbols, connectives and parenthesis. The connected statements are called declarative sentences.
If declarative sentences assume only one truth-value T or F, those sentences are called statements. Atomic statements are those which do not contain any connectives.
Consider the following examples:
- India is a country.
- London is the capital of Japan.
- This statement is true.
- Open the gate.
- Madurai is an old city.
- Man will reach Mars by 2020.
Statements (1) and (2) have truth values true and false respectively. (3) is not a statement and one can not assign a definite truth value T or F. (4) is a command and not a statement. (5) is true in some part of the world and false in certain other parts. It is a statement. The truth-value of (6) could be determined only in the year 2020 or earlier if a man reaches Mars before that date.
Proposition:A proposition is a statement that is either true or false but not both.
Generally name is used as a name of the object.
Consider an example :
- This chair is small.
"This chair" is used as a name of the object.
Consider another example :
- Srinivasan is a good man.
- "Srinivasan" contains ten letters.
The quality of a person is defined in (8) and the person’s name is Srinivasan. In (9), "Srinivasan" is used as a name of this name. (9) is about a name and not about a person.
1.1.3 Connectives
By using connectives, molecular or compound statements are formed from atomic statements. The statements are denoted by the capital letters A, B, C, D, E …
Example 1:
Let A be a proposition.
A: Mr. Bill Clinton went to the White House.
1.1.4 Negation
The symbol ‘ ’ is used to denote the negation. Alternate symbols used in the literature are ‘~’, a bar or "NOT", so that P is written as ~P, or NOT P.
Example 2:
B: I went to my native place yesterday.
B: I did not go to my native place yesterday.
Truth table 1.1.4
P / PT / F
F / T
1.1.5 Conjunction
The conjunction of two statementsA and B is the statement A B which is read as "A and B". The statement A B has truth value T whenever both A and B have truth value T; otherwise it has the truth value F.
Truth table 1.1.5
A / B / A BT / T / T
T / F / F
F / T / F
F / F / F
A: The University is conducting 25 Under Graduate courses.
B: It has 15 Post Graduate courses.
Solution:
The University is conducting 25 Under Graduate courses and it has 15
Post Graduate courses.
1.1.6 Disjunction
Let A and B be propositions. The disjunction of two statementsA and B is the statement A B B which is read as "A or B". The proposition has the truth value F only when both A and B have the truth value F; otherwise it is true.
Truth table 1.1.6
A / B / A BT / T / T
T / F / T
F / T / T
F / F / F
Consider an example :
Baskaran shall play cricket or hockey tomorrow.
The statement and have 22 possible combinations of truth values. If there are n distinct components in a statement, then the proposition has 2n possible combinations of truth values in order to obtain the truth table. A statement formula has no truth value. In the construction of formulas, the parenthesis will be used.
For example,
- () means negation of .
- means disjunction of and
- means conjunction of and
1.1.7 Conditional and Bi-conditional
Consider two statements A and B. The statement is called conditional statement and is read as "If A, then B". The statement has truth value F when B has F and A has T; otherwise it has T. A is called antecedent and B the consequent in.
Truth table 1.1.7(a)
A / B / A BT / T / T
T / F / F
F / T / T
F / F / T
is represented by any one of the following :
- B is necessary for A.
- A is sufficient for B.
- B if A.
- A only if B.
- A implies B.
Write the following statement in symbolic form.
Example 1: If Sindhu either reads the book or Vimal does the homework, then Viji will take the book to the college.
Solution:
Denoting the statement as
A : Sindhu reads the book.
B : Vimal does the home work.
C : Viji takes the book to the college.
Symbolic form:
Example 2: If there is a fire, then the forest will be destroyed.
Solution:
Denoting the statement as
A : There is a fire.
B : The forest will be destroyed.
Symbolic form:
The statement A B is called bi-conditional statement. It is translated as "A is necessary and sufficient for B". The statement A B has truth value T when both A and B has T or F. Otherwise it has truth value F.
Truth table 1.1.7(b)
A / B / A BT / T / T
T / F / F
F / T / F
F / F / T
Example 3:Construct truth table for (A B) (B A)
A / B / A B / B A / (A B) (B A)T / T / T / T / T
T / F / F / T / F
F / T / T / F / F
F / F / T / T / T
1.1.8 Well-formed formulas (wff)
A well-formed formula is nothing but a recursive definition of a statement formula. By applying the following rules a wff can be generated.
- A statement variable standing alone is a wff.
- If A is a wff, then A is a wff.
- If A and B are wffs, then AB, AB, A B and A B are wffs.
- A string of symbols containing the statement variables, connectives and parenthesis is a wff.
Example: AB, A B, A(B C), A (BC)
1.1.9 Tautologies
A statement formula which is true regardless of the truth values of the statements which replace the variables in it is called a universally valid formula or a tautology or a logical truth.A statement formula which is false regardless of the truth values of the statements which replace the variables in it is called a contradiction. The negation of contradiction is a tautology.
Consider two statement formulas, which are tautologies. If we assign any truth values to the variables of A and B, then the truth values of both A and B will be T. Therefore, the truth values of A B will be T, so that A B will be a tautology.
A statement ‘A’ is said to tautologically imply a statement ‘B’ if and only if is a tautology. We shall denote this ideas by which is read as "A implies B".
1.1.10 Equivalence of Formulas
- P is equivalent to P.
- P P is equivalent to P.
- P P is equivalent to Q Q.
- ( P P ) Q is equivalent to Q.
The equivalence of two formulas A and B is written as "A B" which is read as "A is equivalent to B".
Examples:
- P Q P Q.
- P Q (P Q) (Q P).
1.2 Normal Forms
1.2.1 Disjunctive Normal Forms
1.2.2 Conjunctive Normal Forms
1.2.3 Principal Disjunctive Normal Form
1.2.4 Principal Conjunctive Normal Form
Normal Forms
Let A(P1, P2, P3, …, Pn) be a statement formula where P1, P2, P3, …, Pn are the atomic variables. If A has truth value T for all possible assignments of the truth values to the variables P1, P2, P3, …, Pn , then A is said to be a tautology. If A has truth value F, then A is said to be identically false or a contradiction.
1.2.1 Disjunctive Normal Forms
A product of the variables and their negations in a formula is called an elementary product. A sum of the variables and their negations is called an elementary sum. That is, a sum of elementary products is called a disjunctive normal form of the given formula.
Example:
The disjunctive normal form of
- P (P Q) P ( P Q) (P P) (P Q).
- (P Q) (P Q)
( (P Q) (P Q)) ((P Q) (P Q))
( P Q P Q) (P P) (Q P) (P Q) (Q Q).
1.2.2 Conjunctive Normal Forms
A formula which is equivalent to a given formula and which consists of a product of elementary sums is called a conjunctive normal form of a given formula.
Example 1:
The conjunctive normal form of
(a) P (P Q) P ( P Q).
(b)(P Q) P Q.
(c) (P Q)
((P Q) (Q P))
(( P Q) ( Q P))
( P Q) ( Q P)
(P Q) (Q P)
(P Q) (Q Q) (P P) ( P Q).
(d) (P Q) (P Q)
( (P Q) (P Q)) ((P Q) (P Q))
((P Q) (P Q)) ( (P Q) ( P Q)
(P Q P) (P Q Q) ( P Q P) ( P Q Q).
Example 2:
(a) Show that the formula B ( A B) (A B) is a tautology.
B ( A B) (A B) B (( A A) B)
( B A A) ( B B)
T T
T.
Therefore, it is a tautology.
(b) Show that the formula ( B A) B is a contradiction.
( B A) B A (B B)
A F
F.
Therefore, it is a contradiction.
(c) Show that (Q P) ( P Q) is a contradiction.
(Q P) ( P Q) ( Q P) ( P Q)
( P Q Q) (P P Q)
F F
F.
Therefore, it is a contradiction.
1.2.3 Principal Disjunctive Normal Form (PDNF)
Let us assume A and B be two statement variables. All possible formulas by using conjunction are given as follows. The total number of formulas for two variables A and B are 22 formulas. They are A B, A B,
A B and A B.
These are called minterms or Boolean conjunctions of A and B. The minterms (2n terms) are denoted by M0, M1, … ,M2n-1.
A formula equivalent to a given formula consisting of the disjunction of minterms only is called PDNF of the given formula.
Example 1:
Obtain the PDNF of ( P Q) (P Q)
P / Q / P Q / P Q / ( P Q) (P Q)T / T / F / F / T
T / F / T / T / T
F / T / T / T / T
F / F / T / F / F
From the above table
( P Q) (P Q)
(P Q) (P Q) ( P Q)
( P Q) (P Q) (P Q)
Example 2: Obtain the PDNF of
P / Q / P QT / T / T
T / F / F
F / T / T
F / F / T
P Q
(P Q) ( P Q) ( P Q)
( P Q) ( P Q) (P Q)
Procedure for obtaining PDNF
Step1 : Get rid of , .
Step2 : Use De Morgan’s law.
Step3 : Use distributive law.
Step4 : Introduce missing factor in the disjunction.
Step5 : If there is elementary product of the form.
(P P) ( ) …… , delete P P.
For every truth value T in the truth table of the given formula, select minterm which also has the value T for the same combination of the truth values of P and Q. The disjunction of these minterms will be equivalent to the given formula.
To find a particular minterm Mi, the subscript i is expressed in the binary representation and suitable number of 0’s are added to the left.
Example 3:
Obtain PDNF for .
Assign 1 for P and 0 for P.
Example 4: Obtain PDNF for .
Solution:
Example 5:
Obtain PDNF for P ((P Q ( Q P))).
Solution:
P ((P Q ( Q P)))
P ((P Q (P Q)))
P ((P P Q))
P ( P (P Q))
P ( P (P Q))
P (P Q)
( P (Q Q)) (P Q)
( P Q) ( P Q) (P Q)
( P Q) ( P Q) (P Q)
.
1.2.4 Principal Conjunctive Normal Forms (PCNF)
The duals of minterms are called maxterms. For a given number of variables the maxterm consists of disjunctions in which each variable or its negation, but not both, appears only once.
For a given formula, an equivalent formula consisting of conjunctions of maxterms only is known as its principal conjunctive normal form. This is also called the product of sums canonical form.
Example 1:
Obtain the PCNF of ( P R) (Q P).
Solution:
( P R) (Q P) (P R) ((Q P) (P Q))
(P R) (( Q P) ( P Q))
(P R (Q Q)) ((P Q (R R)) ( P Q (R R))
(P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)
S (0,2,3,4,5).
S consisting of missing maxterms
M1 M6 M7
(P Q R) ( P Q R) ( P Q R).
Example2:
Obtain PCNF for A : ( P R) ((Q P) (P Q)).
Solution:
A (P R) (( Q P) ( P Q))
(P R (Q Q)) (P Q (R R)) ( P Q (R R))
(P Q R) (P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)
(P Q R) (P Q R) (P Q R) ( P Q R) ( P Q R)
(0,2,3,4,5).
Example 3: From the given truth table formula S, determine its PDNF and PCNF
Table 1.2.4
A / B / C / ST / T / T / T
T / T / F / F
T / F / T / F
T / F / F / F
F / T / T / F
F / T / F / F
F / F / T / F
F / F / F / T
By choosing the minterms corresponding to each T value of S,
the PDNF of S .
By choosing the maxterms corresponding to each F value of S,
the PCNF of
S ( A B C) ( A B C) ( A B C) (A B C) (A B C) (A B C) .
Example 4:Form the given truth table formula S, determine its PDNF and PCNF
T / T / T / F
T / T / F / F
T / F / T / T
T / F / F / F
F / T / T / T
F / T / F / T
F / F / T / F
F / F / F / T
By choosing minterms corresponding to each T value of S,
the PDNF of S (A B C) ( A B C) ( A B C) ( A B C)
.
By choosing maxterms corresponding to each F value of S,
the PCNF of S ( A B C) ( A B C) ( A B C) (A B C)
(1,4,6,7).
Example 5:
Obtain the product of sums canonical form of the formula A which is given by
(P Q R) ( P Q R) ( P Q R)
Solution:
A ( P Q R) (P Q R) (P Q R)
(0,3,7).
( A) consisting of missing maxterms
(1,2,4,5,6)
(P Q R) (P Q R) ( P Q R) ( P Q R) ( P Q R)
Example 6:
Obtain the product-of-sums canonical form of the formula A, which is given by
( P Q R S) (P Q R S) (P Q R S) ( P Q R S) (P Q R S).
Solution:
A (P Q R S) ( P Q R S) ( P Q R S)
(P Q R S) ( P Q R S)
(P Q R S) (P Q R S) ( P Q R S)
( P Q R S) ( P Q R S)
(5, 6, 9, 10, 12).
( A) consisting of missing maxterms
(0,1,2,3,4,7,8,11,13,14,15)
M0 M1 M2 M3 M4 M7 M8 M11 M13 M14 M15
(P Q R S) (P Q R S) (P Q R S) (P Q R S)
(P Q R S) (P Q R S) ( P Q R S) ( P Q R S) ( P Q R S) ( P Q R S) ( P Q R S).
Example 7:
Obtain the product of sums canonical form of (P Q) ( P Q) (P Q).
Solution:
A ( P Q) (P Q) ( P Q)
(P Q) ( P Q) ( P Q)
(1,2,3).
( A) consisting of missing maxterms
(0)
M0
P Q.
Try Yourself:
1. Write the following statements in symbolic form using the statements
P : Sandeep is rich. Q : Sandeep is happy.
- Sandeep is poor but happy.
- Sandeep is rich or unhappy.
- Sandeep is neither rich nor happy.
- Sandeep is poor or he is both rich and unhappy.
2. Write the negation of each of the following statements as simply as possible.
- He is tall but handsome.
- He has blond hair or blue eyes.
- He is neither rich nor happy.
- He lost his job or he did not go to work today.
- Neither Siva nor Sriram is unhappy.
- Ajay speaks Bengali or Hindi, but not German.
- If he studies, he will pass the exam.
- He swims if and only if the water is warm.
- If it snows, then he does not drive the car.
- If it is cold, then he wears a coat but no sweater.
- If he studies then he will go to college or to art school.
3. Write the following statement in symbolic form using the statements
P: It is cold. Q: It rains.
- It rains only if it is cold.
- A necessary condition for it to be cold is that it rain.
- A sufficient condition for it to be cold is that it rain.
- Whenever it rains it is cold.
- It never rains when it is cold.
4. Write each statement in symbolic form using
P : He is rich Q : He is happy.
- If he is rich then he is unhappy.
- He is neither rich nor happy.
- It is necessary to be poor in order to be happy.
- To be poor is to be unhappy.
- Being rich is a sufficient condition to being happy.
- Being rich is a necessary condition to being happy.
- One is never happy when one is rich.
- He is poor only if he is happy.
- To be rich means the same as to be happy.
- He is poor or else he is both rich and happy.
5. Write the negation of each statement in as simple a sentence as possible.
- If Sindhu is a poet, then she is poor.
- If Madhu passed the test, then he studied.
- If x is less than zero, then x is not positive.
- If it is cold, he wears a hat.
- If productivity increases, then wages rise.
6. From the formulas given below select those which are well formed and indicate which ones are tautologies or contradictions.
- (A ( A Q))
- ((A A)) A)
- (B A) B
- ((A C)) B) C)))
- ((A B) B
- ((A B) A)
7. Obtain the PCNF of the following
- (A B)
8. Obtain the product of sums canonical forms of the following.
- (P Q R) ( P Q R) ( P Q R) ( P Q R).
- ( P Q R S) (P Q R S) (P Q R S) ( P Q R S)
(P Q R S). - ( P Q) ( P Q) (P Q).
- (P Q) ( P Q R).
9. Obtain the PDNF and PCNF of the following
- (Q (P Q)).
- P ( P (Q ( Q R))).
- (P (Q R)) ( P ( Q R)).
- P (P (Q P)).
- (Q P) ( P Q).
1.3 Theory of Inference
1.3.1 Validity Using Truth Tables
1.3.2 Testing the Validity of a Conclusion
1.3.3 Rules of Inference
1.3.4 Consistency of Premises and Indirect Method of Proof
Theory of Inference
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 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 QH2 : PC : Q
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 QH2 : PC : Q
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 QH2 : (P Q)C : P
P / Q / H1 / H2 / CT / 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 : PH2 : P QC : P Q
P / Q / H1 / H2 / CT / 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 : RC : P
P / Q / R / Q R / H1 / H2 / CT / 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 QH2 : P RH3 : Q RC : R
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
I5 P P Q
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
E10 P 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} () 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) RRule 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)QPRule 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 RRule T, (1), (2) and I13
{4} (4) P R Rule P
{1, 2} (5)R PRule 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, H1H2… 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 PQ.
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)PQ Rule P
{4} (5)P Rule T, (4) and I1
{1, 4}(6) PP Rule T, (3), (5) and I9
Example 2:
Show that the given premises P Q, P R, QR, P are inconsistent.