UNIT–1
Mathematical Logic
Statement-
When a declarative sentence which is true or false but not both is called statement.
The truth values “true” and “false” of a statement are denoted by T ad F respectively. We can denote them by 0 and 1 as well.
Examples of statements are-
1. 2 + 11 = 12
2. Jaipur is in India
Truth table-
The table showing the truth values of a statement formula is called ‘truth table’.
The truth tablefor a given statement form displays the truth values that correspond to all possible combinations of truth values for its component statement variables.
Laws of formal-
1. Law of contradiction- According to the law of contradiction the same predicate cannot be both affirmed and denied precisely of the same subject
For every preposition p is not the same that p is both true and false.
2. Law of excluded middle- If p is a statement, then either p is true or p is false and there cannot be middle ground.
Connectives-
Statements in mathematical logic are combinations of simpler statements joined by words and phrases like ‘and’. ‘or’, ‘if and only if’, etc. These words and phrases are called logical connectives.
Disjunction-
Definition: The disjunction of two propositions p and q is the compound statement 10 Elementary Logic p or q, denoted by p ∨ q.
For example, ‘Aman has a house or Amit has a house’ Is the disjunction of p and q, where-
p: Aman has a house, and
q: Amit has a house.
Example: Obtain the truth value of the disjunction of ‘The earth is flat’. and ‘3 + 5 = 2’.
Solution: Let p denote ‘The earth is flat,’ and q denote ‘3 + 5 = 2’. Then we know that the truth values of both p and q are F. Therefore, the truth value of p ∨ q is F.
Example-Let p: 5 + 2 = 7, q: 9 + 2 = 10 then p ∨q: 5 + 2 = 7 or 9 + 2 = 10
Truth table for disjunction-
Exclusive disjunction-
The exclusive disjunction of two propositions p and q is the statement ‘Either p is true or q is true, but both are not true.Either p is true or q is true, but both are not true’. We denote this by p ⊕q.
Conjunction-
Definition: We call the compound statement ‘p and q’ the conjunction of the
Statements p and q. We denote this by p ∧q.
Example- ‘3 + 1 ≠ 7 ∧ 2 > 0’ is the conjunction of ‘3 + 1 ≠ 7’ and ‘2 > 0’.
Example-
Obtain the truth value of the conjunction of ‘2 ÷5 = 1’ and ‘Ramesh is in Jaipur’.
Solution: Let p: 2 ÷5 = 1, and
q:Ramesh is in Jaipur.
Then the truth value of p is F. Therefore, from Table 3 you will find that the truth
Value of p ∧ q is F.
Negation-
The negation of a proposition p is ‘not p’, denoted by ~p.
Example-
If p is ‘Smriti is at the station.’, then ~ p is ‘Smriti is not at the station’.
Similarly, if p is ‘No person can live without food.’,~ p is ‘At least one person can live without food.’
Conditional connectives-
Given any two propositions p and q, we denote the statement ‘If p, then q’ by
p→ q. We also read this as ‘p implies q’. or ‘p is sufficient for q’, or ‘p only if q’. We also call p the hypothesis and q the conclusion. Further, a statement of the form p → q is called a conditional statement.
Truth table for implication-
Definition for converse-
The converse of p → q is q → p. In this case we also say ‘p is necessary for q’, or ‘p if q’when we combine an implication and its converse, then-
Let p and q be two propositions. The compound statement
(p→ q) ∧(q → p) is the bi-conditional of p and q. We denote it by p ↔ q, and
(Read) as ‘p if and only q’.
We use ‘if and only ‘if’ as iff
We also say that ‘p implies and is implied by q’. or ‘p is necessary and sufficient
forq’.
Example- Pradeep will get good marks if and only if he studies regularly means that Pradeep will get good marks if he studies regularly and Pradeep studies regularly if he gets good marks.
Truth table for two-way implication-
A statement formula is called wee-formed formula if it can be generated by the following rules-
1. A statement variable p standing alone is a well formed formula.
2. If p is a well-formed formula, then ~p is a well formed formula.
3. If p and q are well-formed formulas, then (p ∧q), (p ∨q), (p →q) and (p ↔q) are well-formed formulas.
4. A string of symbols is a well formed formula if and only if it is obtained by finitely many applications of the rules 1, 2 and 3.
~(p ∨q), (~p ∧q), (p →(p∨q)) are well formed formulas.
The truth table of a well formedformula is the summary of truth values of the resulting statements for all possible assignments of values to the variables appearing in the formula. The final column entries of the truth table of a well formed formula give the truth values of the formula.
A statement formula that is true for all possible values of its propositional variables is called a Tautology.
Similarly a proposition that is false for all possible truth values of the simple propositions that constitute it is called a contradiction.
Example-
(p∨q) ↔(q ∨p) is a tautology.
Example-
p∨~p is a tautology.
Example- Show that p ∨~p is a tautology.
Solution: First we will construct the truth table for (p ∨~p)
p |
| (p ∨~p) |
T | F | T |
T | T | T |
p∨~p is always true.
Hence p ∨~p is a tautology.
Example:
Show that (p ∧q) →p is tautology.
Solution: Let us construct the truth table for the statement (p ∧q) →p
p | q | p ∧q | (p ∧q) →p |
T | T | T | T |
T | F | F | T |
F | T | F | T |
F | F | F | T |
Here 4th column has T entries then (p ∧q) →p is a tautology.
Example:
Verify that p ∧q ∧~ p is a contradiction and p →q ↔~ p ∨q is a tautology.
Solution: Let us draw the truth tables of these two propositions-
Looking at the fifth column of the table, you can see that p ∧q ∧~p is a contradiction.
p→q ↔~ p ∨q is a tautology
Example: Show that
((p ∨~q) ∧(~p ∨~q)) ∨q is a tautology.
Solution: Consider
((p ∨~q) ∧(~p ∨~q)) ∨q
≡((p ∨~q) ∧~p ∨(p ∨~q) ∧~q) ∨q
≡((p ∧~p) ∨(~q ∧~p) ∨(p ∧~q) ∨(~q ∧~q)) ∨q
≡(f ∨(~q ∧~p) ∨(p ∧~q) ∨~q) ∨q
≡(~ q ∧~p) ∨(p ∧~q) ∨~q ∨q
≡(~ q ∧~p) ∨(p ∧~q) ∨t(Since ~q ∨q ≡t)
≡t
Hence ((p ∨~q) ∧(~p ∨~q)) ∨q is a tautology.
Laws of logic-
1. Idempotent Laws:
(a) p∨p ≡p (b) p ∧p ≡p
2. Commutative Laws:
(a) p∨p ≡q ∨p (b) p ∧q ≡q ∧p
3. Associative Laws:
(a) (p∨q) ∨r ≡p ∨(q ∨r) (b) (p ∧q) ∧r ≡p ∧(q ∧r)
4. Distributive Laws:
(a) p∨(q ∧r) ≡(p ∨q) ∧(p ∨r)
(b) p∧(q ∨r) ≡(p ∨q) ∨(p ∧r)
5. Identity Laws:
(a) (i) p ∨f ≡p (ii) p ∨t ≡t
(b) (i) p ∧f ≡f (ii) p ∧t ≡p
6. Complement Laws:
(a) (i) p ∧~p ≡t (ii) p ∧~p ≡f
(b) (i) ~~p ≡p (ii) ~t ≡f, ~ f ≡t
7. De Morgan’s Laws:
(a) ~(p ∨q) ≡~p ∧~q (b) ~(p ∧q) ≡~p ∨~q
Here t and f are used to denote the variables which are restricted to the truth values true and false respectively.
Duality law
Two statement formulas P and P* are said to be duals of each other if either one can be obtained from the other by replacing ∧and ∨and ∨by ∧.
A proposition P (p1, p2,...) is said to logically imply a proposition Q ( p1, p2, ...) if one of the conditions in Theorem 1.1 holds.
If P (p1, p2,...) logically implies Q ( p1, p2, ...) then we symbolically denote it by writing
P ( p1, p2, ...) ⇒Q ( p1, p2, ...)
Example- (p →q) ∧(q →r) →(p →r) is a tautology.
Hence (p →q) ∧(q →r) ⇒(p →r)
The other connectives are very useful In the field of computer science.
These are NAND, NOR connectives.
NAND is the combination of NOT and AND.
Here NOT is for negation and AND is for the conjunction.It is denoted by the symbol ↑
If P and Q are two formulas then P ↑Q ↔~(P ∧Q)
The connective ↑has the following equivalence:
P ↑P ↔~(P ∧P) ↔~ P ∨~ P ⇔~P
(P ↑Q) ↑(P ↑Q) ↔~ (P ↑Q) ↔P ∧Q
(P ↑P) ↑(Q ↑Q) ↔~ P ↑~Q ⇔~ (~P ∧~Q) ↔P ∨Q
NAND is commutative but not associative:
i.e., P ↑Q ↔Q ↑P but P ↑(Q ↑R) ↔~ P ∨(Q ∧R) and
(P ↑Q) ↑R ↔~ (P ∧Q) ~ R. Therefore the connective ↑is not associative
NOR is a combination of “NOT” and “OR”, where NOT means negation and
“OR” means disjunction
The connective NOR is denoted by the symbol ↓.
The connective ↓.has the following equivalence:
P ↓P ↔~ (P ∨P) ↔~ P ∧~ P ⇔~ P
(P ↓P) ↓(P ↓Q) ↔~ (P ↓Q) ↔P ∨Q
(P ↓P) ↓(Q ↓Q) ↔~ P ↑~ Q ↔P ∧Q
The connective ↓is commutative, but not associative, i.e.
P ↓Q ⇔Q ↓P but (P ↓Q) ↓Q ↔(P ∨Q) ∧~ R
P ↓(Q ↓R) ↔~ P ∧(Q ∨R)
Therefore the connective ↓is not associative.
The connectives ∧, ∨, ~ can be expressed in terms of the connective ↓as follows:
(i) ~ p ≡p ↓p
(ii) ~ q ≡q ↓q
(iii) p∧q ≡(p ↓p) ↓(q ↓q)
(iv) p∨q ≡(p ↓q) ↓(p ↓q)
Example: Show that
(p∧(~p ∨q)) ∨(q ∧~ (p ∧q) ≡q
Sol. L.H.S.
(p∧(~p ∨q)) ∨(q ∧~ (p ∧q)
≡((p ∧~p) ∨(p ∧q)) ∨(q ∧(~p ∨~q))
≡f∨(p ∧q) ∨(q ∧~p) ∨(q ∧~p) ∨(q ∧~q) where(p ∧~p = f )
≡(p ∧q) ∨(q ∧~p) ∨f
≡(p ∧q) ∨(q ∨~p)
≡(q ∧p) ∨(q ∨~p)
≡q∧(p ∨~p)
≡q∧(p ∨~p)
≡q∧t where (_ p ∨~p = t)
≡q
≡R.H.S.
Hence (p ∧(~p ∨q)) ∨(q ∧~(p ∧q) ≡q
Disjunctive normal form-
Definition-
SupposeA denotes a given formula. Another formula B which is equivalent to A will be called a disjunctive normal form of A if B is a sum of elementary products.
A disjunctive normal form of a given formula is constructed as given below-
(i) Replace ‘→’, ‘↔’ by using the logical connectives ∧, ∨and ~.
(ii) Use De Morgan’s laws to eliminate ~ before sums or products.
(iii) Apply distributive laws repeatedly and eliminate product of variables to obtain the required normal form.
Example: Obtain disjunctive normal form ofp ∨(~p →(q ∨(q →~r)))
Solution: p ∨(~p →(q ∨(q →~r)))
≡p ∨(~p →q ∨(~q ∨~r)))
≡p∨(p ∨(q ∨(~q ∨~r)))
≡p∨p ∨q ∨~q ∨~r
≡p∨q ∨~q ∨~r
Therefore, the disjunctive normal form of
p∨(~p →(q ∨( ~q →~r))) is p ∨q ∨~q ~r
Example: Obtain the disjunctive normal form of
(a) p∨(~p →(q ∨(q →~r)))
Solution:
(a) p∨(_ p →(q ∨(q →_ r)))
≡p∨(_ p →q ∨(_ q ∨_ r))
≡p∨( p ∨q ∨(_ q ∨_ r))
≡p∨p ∨q ∨_ q ∨_ r
≡p∨q ∨_ q ∨_ r
Conjunctive normal form-
Let A denote a given formula, another formula B which is equivalent to A is called conjunctive normalformula if B is a product of an elementary sum.
Principal disjunctive normal form-
Definition 1.5: If A is a given formula, then an equivalent formula B, consisting of disjunctives of Minterms only is called the Principal disjunctive normal form of the formula A.
Example: Obtain the principal disjunctive normal form of (~ p ∨~ q)→ (~ p ∧r ).
Solution: (~ p ∨~ q)→ (~ p ∧r )
⇔~(~ p ∨~ q) ∨ (~ p ∧r )
⇔~ (~(p ∧q)) ∨ (~ p ∧r )
⇔( p∧q) ∨ (~ p ∧r )
⇔( p∧q ∧ (r ∨~ r )) ∨ (~ p ∧r ∧ (q ∨~ q))
⇔( p∧q ∧r) ∨ ( p ∧q ∧~ r) ∨ (~ p ∧r ∧q) ∨ (~ p ∧r ∧~ q)
The principal disjunctive normal form of the given formula is
( p∧q ∧r) ∨( p∧q ∧~ r) ∨ (~ p ∧q ∧r) ∨ (~ p ∧~ q ∧r)
Example: Obtain the principal disjunctive normal form of ~p ∨q.
Solution: ~p ∨q ≡(~p ∧(q ∨~q)) ∨(q ∧(p ∨~p))
≡(~p ∧q) ∨(~p ∧~q) ∨(q ∧p) ∨(q ∧~p)
≡(~p ∧q) ∨(~p ∧~q) ∨(p ∧q)
Therefore (~p ∧q) ∧(~p ∧~q) ∧(p ∧q) is the required principal disjunctive normal form.
Principal conjunctive normal form-
Definition 1.6: If A is a given formula, then an equivalent formula B is called principle conjunctivenormal form of Aif B is a product of maxterms.
Theory of inference of statement calculus-
Modus ponens and modus tollens-
An argument form consisting of two premises and a conclusion is called a syllogism. Thefirst and second premises are called the major premiseand minor premise, respectively.
The most famous form of syllogism in logic is called modus ponens. It has the following form:
If p then q.
p
∴q
Example:
If the sum of the digits 469437 is divisible by 3
Then 469437 is divisible by 3.
The another valid argument form called modus tollens.
Modus tollens means- method of denying.
It has the following form-
If p then q.
∼q
∴∼p
For example-
If Rahim is tall, then Rahim is thick.
Rahim is not thick.
∴Rahim is not tall.
The rules of inference- (Modus ponens and modus tollens)
The theory of inference is a form of argument that is valid.
Modus ponens and modus tollens are both rules of inference.
The following result gives the rules of inference-
1. Modus ponens (Law of detachment)-
Let us consider the following argument-
If Ravi can fire, he will hit the target
Ravi can fire,
Therefore, he will hit the target.
In order to study the form of the argument, suppose p be the proposition ‘Ravi can fire’ and q be the proposition ‘ Ravi will hit the target’.
Then the premises are p→q and p.
The conclusion is q.
Hence the form of argument-
To check the validity of this argument we will construct a truth table as follows-
By looking the second column(the conclusion) and the fourth column(the premises).
Whenever the premises are true in first row the conclusion is true.
Hence the argument is valid.
This is the form of valid argument and this law is called law of detachment because the conclusion q is detached from a premise.
We also call it as the law of direct inference.
2. Modus tollens (Law of detachment)-
Let us consider the following argument-
If Ravi can fire, he will hit the target.
Ravi will not hit the target.
Therefore, Ravi cannot fire.
The argument is of the form-
