MAT2002 Module 2

Rule P: Introduce
Inference Rule:
Rule T: Derivation
P
Modus Ponens: P→Q
Q
∼Q
Modus Tollens: P→Q
∼P
∼P ∼Q
Disjunctive Syllogism: P∨Q and P ∨ Q
Q P
P∧Q
Simplification:
P or Q
P, Q
Conjunction:
P∧Q
P −→ Q
Hypothetical Syllogism: Q −→ R
P −→ R
Dilemma P ∨ Q, P → R, Q → R ⇒ R
Dr.A.Benevatho Jaison MAT1002 March 30, 2021 52 / 199
Example 2.1.1
Prove that S is a valid conclusion from the premises P →∼ Q, Q ∨ R, ∼ S → P
and ∼ R.
Steps Statement Rule Step in- Justification
formula volved
1 ∼R P - -
2 Q∨R P - -
3 Q T 1,2 Disjunctive Syllogism
4 P →∼ Q P - -
5 ∼P T 3,4 Modus Tollens
6 ∼S→P P - -
7 ∼ (∼ S) T 5,6 Modus Tollens
8 S T 7 Double Negation

Example 2.1.2
Prove that R ∧ (P ∨ Q) is a valid conclusion from the premises P ∨ Q, Q → R,
P → M, ∼ M.
Steps Statement Rule Step in- Justification
formula volved
1 ∼M P - -
2 P→M P - -
3 ∼P T 1,2 Modus Tollens
4 P∨Q P - -
5 Q T 3,4 Disjunctive Syllogism
6 Q→R P - -
7 R T 5,6 Modus Ponnens
8 R ∧ (P ∨ Q) T 4,7 Conjunction

Definition 2.2.1 (Rules for k-map simplification)
1 Groups may not contain zero.
2 We can group 1, 2, 4, 8, . . . or 2n , n = 0, 1, 2, . . . cells.
3 Each group should be as large as possible.
4 Cells containing 1 must be grouped.
5 Groups may overlap.
6 Opposite grouping and other grouping is allowed.
7 There should be as few groups as possible.

Example 2.2.2
Simplify A + AB using K-map.
A B A + AB X
0 0 0+1.0 0
0 1 0+1.1 1
1 0 1+0.0 1
1 1 1+0.1 1
B
0 1
0 0 1
A
1 1 1
Grouping I Grouping II
A B A B
1 0 0 1
1 1 1 1
Answer: A+B
Example 2.2.3
Simplify f = ABC + ABC + AB + C using K-map.
A B C ABC +ABC +AB+C X

0 0 0 001+010+10+1 1
0 0 1 000+011+10+0 0
0 1 0 011+000+11+1 1
0 1 1 010+001+11+0 1
1 0 0 101+110+00+1 1
1 0 1 100+111+00+0 1
1 1 0 111+100+01+1 1
1 1 1 110+101+01+0 1

BC
00 01 11 10
0 1 0 1 1
A
1 1 1 1 1
Grouping I Grouping II Grouping III

A B C A B C A B C
1 0 1 0 1 1 0 1 0
1 1 1 0 1 0 0 0 0
1 1 0 1 1 1 1 1 0
1 0 0 1 1 0 1 0 0
A B C
f =A+B+C

Example 2.2.4
Simplify f = ĀB̄C + ĀBC + BC̄ + B̄C̄ using K-map.
A B C ĀB̄C + ĀBC + BC̄ + B̄C̄ X

0 0 0 110+100+01+11 1
0 0 1 110+101+00+10 1
0 1 0 100+110+11+01 1
0 1 1 101+111+10+00 1
1 0 0 010+000+01+11 1
1 0 1 011+001+00+10 0
1 1 0 000+010+11+01 1
1 1 1 001+011+10+00 0

BC
00 01 11 10
A 0 1 1 1 1
1 1 0 0 1
Grouping-I Grouping-II
A B C A B C
0 0 0 0 0 0
0 0 1 1 0 0
0 1 1 0 1 0
0 1 0 1 1 0
A C
F =A+C

Definition 2.3.1 (Logical statement or proposition)
A statement or a proposition is a sentence which is either true or false but not
both.
A statement which is both true and false simultaneously is not a statement,
rather it is a paradox.
Example 2.3.2 (True statement)

1 Delhi is the capital of India.
2 The earth is a planet.
Example 2.3.3 (Paradox)

1 Where are you going.
2 Switch on light.

Definition 2.3.4 (True value of a statement)
The truth value or falsity of a statement is called its truth value. If a statement
is true, we say that its truth value is TRUE, or T and if it is false. We say that
its truth value is FALSE or F.
Example 2.3.5
TRUE Delhi is the capital of India.
FALSE Earth is a star.
Definition 2.3.6 (Simple statement)

A statement is said to be simple statement if it can not be brocken into two or
more statements.
Example 2.3.7
Rose is a flower.

Definition 2.3.8 (Compound statement)
If a statement in the combination of two or more simple statements, then it is
said to be compound statement.
Example 2.3.9
It is raining and it is cold.
Truth value of compound statement determine by the truth value of its sub-
statements together.

Definition 2.3.10 (Connectives)
The word which combine simple statements to form compound statements are
called connectives. Some of the connectives are ‘and’, ‘or’ etc.
Definition 2.3.11 (Conjunction)

If two simple statement p and q are connected by the word ‘and’, then the
resulting compound statement ‘p and q’ is called the conjunction of p and q, it
is written in the symbolic form as ‘p ∧ q0 .
Example 2.3.12
p: Rahul is intelligent.
q: Ravi is handsome.
p ∧ q: Rahul is intelligent and Ravi is handsome.

Definition 2.3.13 (Convert the statement into symbolic form)
Mala and Kala are going to school. Then the statement can be written as
p : Mala is going to school.
q : Kala is going to school.
p ∧ q: is the symbolic form of Mala and Kala are going to school.
Definition 2.3.14 (Disconjunction)

If two simple statements p and q are connected by the word ‘or’, then the
resulting compound statement ‘p and q’ is called the disconjunction of p and q
is written in symbolic form as p ∨ q.

Definition 2.3.15 (Negation)
The negation of a statement is generally formed by introducing the word ‘not’
at some proper place in the statement or by prefixing the statement with ‘It is
not the case that’ or ‘It is false that’.
If p denotes a statement, then the negation of p is written a p.
p : Boys playing cricket.
∼ p : Not all boys playing cricket.

Logic - Equivalence - Implications
(i) Truth table for ‘and’, ‘×0 or (p ∧ q)
p q p∧q
T T T
T F F
F T F
F F F
(ii) Truth table for ‘or’, ‘+0 or (p ∨ q)
p q p∨q
T T T
T F T
F T T
F F F

(iii) Truth table for negation.
p ∼p
T F
F T
(iV) Truth table for Logical implication.
p q p→q
T T T
T F F
F T T
F F T
(V) Truth table for Logical implication.
p q p↔q
T T T
T F F
F T F
F F T
(i) Draw the truth table for (∼ p) ∨ (∼ q)
p q ∼p ∼q ∼ p∨ ∼ q
T T F F F
T F F T T
F T T F T
F F T T T
(ii) Draw the truth table for ∼ ((∼ p) ∧ q)
p q ∼p (∼ p) ∧ q ∼ ((∼ p) ∧ q)
T T F F T
T F F F T
F T T T F
F F T F T

(iii) Draw the truth table for ∼ ((∼ p) ∧ (∼ q))
p q ∼p ∼q ((∼ p) ∧ (∼ q)) ∼ ((∼ p) ∧ (∼ q))

T T F F F T
T F F T F T
F T T F F T
F F T T T F

(iv) Draw the truth table for (∼ W)(X + Y)Z
W X Y Z ∼W X+Y (∼ W)(X + Y) (∼ W)(X + Y)Z
F F F F T F F F
F F F T T F F F
F F T F T T T F
F F T T T T T T
F T F F T T T F
F T F T T T T T
F T T F T T T F
F T T T T T T T
T F F F F F F F
T F F T F F F F
T F T F F T F F
T F T T F T F F
T T F F F T F F
T T F T F T F F
T T T F F T F F
T T T T F T F F
Example 2.4.1
Draw a truth table for the following expressions
Example Solution
A + BC 11111000
A(B + D) 11100000
(A + B)(A + C) 11111000
W(X + Y)Z 0000000010101000
PT(P + Z) 00110000

Definition 2.4.2 (Tautology)
A statement form which is always true. The truth does not rely upon the values
of the individual statements substituted for the statement variables, but upon
the logical structure of the statement itself. (i.e., You will get an A in this class,
or you will not.).
Example 2.4.3
p q p→q q→p (p → q) ∨ (q → p)
T T T T T
T F F T T
F T T F T
F F T T T

Definition 2.4.4 (Contradiction)
A statement form which is always false. Like a tautology, the falsity does
not lie in the individual statement variables, but in the logical structure of the
statement itself. (i.e., I always tell lies.).
Example 2.4.5
p q p→q ∼ (p → q) q∧ ∼ (p → q)
T T T F F
T F F T F
F T T F F
F F T F F

Definition 2.4.6 (Logical equivalence)
Two compound statements A and B are said to be logically equivalent, if they
identical last column in their truth table. In this case we write A ≡ B.
∼ (p ∨ q) ≡ (∼ p) ∧ (∼ q)
Example 2.4.7
Show that P → Q and ∼ P ∨ Q are logically equivalent.
p q p→q ∼p ∼p∨q
T T T F T
T F F F F
F T T T T
F F T T T

Example 2.4.8
Prove that each of the following logical equivalencies
1 (∼ P → (Q∧ ∼ Q)) ≡ P
2 (P ↔ Q) ≡ (∼ P ∨ Q) ∧ (∼ Q ∨ P)
3 ∼ (P ↔ Q) ≡ (P∧ ∼ Q) ∨ (Q∧ ∼ P)
4 (P → Q) → R ≡ (P∧ ∼ Q) ∨ R
5 (P → Q) → R ≡ (∼ P → R) ∧ (Q → R)
6 [(P ∧ Q) → (R ∨ S)] ≡ [(∼ R∧ ∼ S) → (∼ P∨ ∼ Q)]
7 [(P ∧ Q) → (R ∨ S)] ≡ [(P ∧ Q∧ ∼ R) → S]
8 [(P ∧ Q) → (R ∨ S)] ≡ (∼ P∨ ∼ Q ∨ R ∨ S)
9 ∼ [(P ∧ Q) → (R ∨ S)] ≡ (P ∧ Q∧ ∼ R∧ ∼ S)

Equivalent law
Obsorbtion law P ∧ (P ∨ Q) = P
Double Negation ∼ (∼ P) ⇔ P
Conditional equivalence P → Q ⇔∼ P ∨ Q
Idempotent P∧P⇔P
P∨P⇔P
Commutative P∧Q⇔Q∧P
P∨Q⇔Q∨P
Identities P∧T ⇔P
P∨F ⇔P
Dominance Law P∨T ⇔T
P∧F ⇔F
Complement P∧ ∼ P ⇔ F
P∨ ∼ P ⇔ T
Associative law P ∧ (Q ∧ R) ⇔ (P ∧ Q) ∧ R
P ∨ (Q ∨ R) ⇔ (P ∨ Q) ∨ R
Distributive law P ∧ (Q ∨ R) ⇔ (P ∧ Q) ∨ (P ∧ R)
P ∨ (Q ∧ R) ⇔ (P ∨ Q) ∧ (P ∨ R)
DeMorgan’s law ∼ P∧ ∼ Q ⇔∼ (P ∨ Q)
∼ P∨ ∼ Q ⇔∼ (P ∧ Q)

Variations in distributive law
(P ∧ Q) ∨ (R ∧ S) = (P ∨ R) ∧ (P ∨ S) ∧ (Q ∨ R) ∧ (Q ∨ S)
(P ∧ Q) ∨ (R ∨ S) = (P ∨ (R ∨ S)) ∧ (Q ∨ R ∨ S)

Example 2.5.1
Show that [(P ∨ Q)∧ ∼ (∼ P ∧ (∼ Q∨ ∼ R))]∨[(∼ P∧ ∼ Q) ∨ (∼ P∧ ∼ R)]
is a tautology without using truth table. (Using equivalence law)
Statement
[(P ∨ Q)∧ ∼ (∼ P ∧ (∼ Q∨ ∼ R))] ∨ [(∼ P∧ ∼ Q) ∨ (∼ P∧ ∼ R)]
DeMorgans law
[(P ∨ Q)∧ ∼ (∼ P∧ ∼ (Q ∧ R))] ∨ [(∼ P∧ ∼ Q) ∨ (∼ P∧ ∼ R)]
Distributive law
[(P ∨ Q)∧ ∼ (∼ P∧ ∼ (Q ∧ R))] ∨ [∼ P ∧ (∼ Q∨ ∼ R)]
DeMorgans law
[(P ∨ Q)∧ ∼ × ∼ (P ∨ (Q ∧ R))] ∨ [∼ P∧ ∼ (Q ∧ R)]
Double negation, DeMorgans law
[(P ∨ Q) ∧ (P ∨ (Q ∧ R))] ∨ ∼ [P ∨ (Q ∧ R)]
Distributive law
[(P ∨ Q) ∧ {(P ∨ Q) ∧ (P ∨ R)}] ∨ ∼ [P ∨ (Q ∧ R)]
Associative law
[{(P ∨ Q) ∧ (P ∨ Q)} ∧ (P ∨ R)] ∨ ∼ [P ∨ (Q ∧ R)]

Idempotent
[(P ∨ Q) ∧ (P ∨ R)] ∨ ∼ [P ∨ (Q ∧ R)]
Distributive law
[P ∨ (Q ∧ R)] ∨ ∼ [P ∨ (Q ∧ R)]
Complement ⇔ T

Example 2.5.2
Prove that [∼ P ∧ (∼ Q ∧ R)] ∨ [(Q ∧ R) ∨ (P ∧ R)] ⇔ R without using truth
table. (Using equivalence law)
Statement
[∼ P ∧ (∼ Q ∧ R)] ∨ [(Q ∧ R) ∨ (P ∧ R)]
Associative law, Distributive law
[(∼ P∧ ∼ Q) ∧ R] ∨ [(Q ∨ P) ∧ R]
DeMorgans law
[∼ (P ∨ Q) ∧ R] ∨ [(P ∨ Q) ∧ R]
Distributive law
[∼ (P ∨ Q) ∨ (P ∨ Q)] ∧ R
Complement
T ∧R
Identities
R

Example 2.5.3
Prove that ((P → R) ∧ (Q → R)) ⇒ ((P ∨ Q) → R)
A ⇒ B if A → B is a Tautology.
So we need to prove that ((P → R) ∧ (Q → R)) → ((P ∨ Q) → R) is a Tau-
tology.
Statement
((P → R) ∧ (Q → R)) → ((P ∨ Q) → R)
Conditional equivalence
((∼ P ∨ R) ∧ (∼ Q ∨ R)) → ((P ∨ Q) → R)
Distributive law
[(∼ P∧ ∼ Q) ∨ R] → ((P ∨ Q) → R)
DeMorgan’s law
[∼ (P ∨ Q) ∨ R] → ((P ∨ Q) → R)
[(P ∨ Q) → R] → [(P ∨ Q) → R]
∼ [(P ∨ Q) → R] ∨ ((P ∨ Q) → R)
Complement
T
Example 2.5.4
Using the laws of logic, show that the following expression are logically equiv-
alent
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [(Q ∧ R) ∨ (Q∧ ∼ R)] ≡∼ P → Q
Statement
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [(Q ∧ R) ∨ (Q∧ ∼ R)]
Distributive
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [Q ∧ (R∨ ∼ R)]
Complement
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [Q ∧ T]
Identities
[P ∧ (P∨ ∼ R ∨ Q)] ∨ [Q]

Associative
[P ∧ (P ∨ (∼ R ∨ Q))] ∨ [Q]
Obsorbtion law
P∨Q
Double Negation
∼ [∼ P] ∨ Q
∼P→Q

Example 2.5.5
Without using truth table, prove that the following relation is Tautology
((A → B) ∧ A) → B
Statement
((A → B) ∧ A) → B
((∼ A ∨ B) ∧ A) → B
∼ ((∼ A ∨ B) ∧ A) ∨ B
DeMorgan’s law
(∼ (∼ A ∨ B)∨ ∼ A) ∨ B
DeMorgan’s law
((A∧ ∼ B)∨ ∼ A) ∨ B
Distributive
((A∨ ∼ A) ∧ (∼ B∨ ∼ A)) ∨ B
Complement
(T ∧ (∼ B∨ ∼ A)) ∨ B
Identities
(∼ B∨ ∼ A) ∨ B
Associative
∼ B ∨ (∼ A ∨ B)
Commutative
∼ B ∨ (B∨ ∼ A)
Associative
(∼ B ∨ B) ∨ ∼ A
Complement
T∨ ∼ A
Dominance Law
T

MAT2002 Module 2

Uploaded by

Copyright:

Available Formats

MAT2002 Module 2

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

MAT2002 Module 2

Uploaded by

Copyright:

Available Formats

Rule P: Introduce

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 53 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 54 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 55 / 199

A B C ABC +ABC +AB+C X

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 57 / 199

Grouping I Grouping II Grouping III

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 58 / 199

A B C ĀB̄C + ĀBC + BC̄ + B̄C̄ X

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 59 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 60 / 199

Example 2.3.2 (True statement)

Example 2.3.3 (Paradox)

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 61 / 199

Definition 2.3.6 (Simple statement)

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 62 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 63 / 199

Definition 2.3.11 (Conjunction)

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 64 / 199

Definition 2.3.14 (Disconjunction)

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 65 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 66 / 199

(i) Truth table for ‘and’, ‘×0 or (p ∧ q)

(ii) Truth table for ‘or’, ‘+0 or (p ∨ q)

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 67 / 199

(ii) Draw the truth table for ∼ ((∼ p) ∧ q)

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 69 / 199

p q ∼p ∼q ((∼ p) ∧ (∼ q)) ∼ ((∼ p) ∧ (∼ q))

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 70 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 72 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 73 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 74 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 75 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 76 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 77 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 78 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 79 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 80 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 81 / 199

[P ∧ (P∨ ∼ R ∨ Q)] ∨ [(Q ∧ R) ∨ (Q∧ ∼ R)] ≡∼ P → Q

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 83 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 84 / 199

Dr.A.Benevatho Jaison MAT1002 March 30, 2021 86 / 199

You might also like