Scribd
Upload
381 views3 pages

Tautology, Contradictions and Equivalence

The document presents six problems involving propositional logic and uses truth tables to determine whether statements are tautologies, contradictions, or equivalences. It shows that (P ∧ Q) ⇒ (P ∨ Q) and (P ∨ ¬P) are tautologies, while (P ∧ ¬P) is a contradiction. It also determines several equivalences, finding that ¬(P ∨ Q) ≡ (¬P ∧ ¬Q), P ⇒ Q ≡ ¬P ∨ Q, and P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) are all equivalent

Uploaded by

Muhammad Shifaz Mamur
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
381 views3 pages

Tautology, Contradictions and Equivalence

The document presents six problems involving propositional logic and uses truth tables to determine whether statements are tautologies, contradictions, or equivalences. It shows that (P ∧ Q) ⇒ (P ∨ Q) and (P ∨ ¬P) are tautologies, while (P ∧ ¬P) is a contradiction. It also determines several equivalences, finding that ¬(P ∨ Q) ≡ (¬P ∧ ¬Q), P ⇒ Q ≡ ¬P ∨ Q, and P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R) are all equivalent

Uploaded by

Muhammad Shifaz Mamur
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Tautology, Contradictions and Equivalence

(1) Construct the truth tables for the following propositions and show the tautology and
contradictions.
Problem: (a). (P ∧ Q) ⇒ (P ∨ Q)
Solution:
Truth Table:
P Q P∧Q P∨Q (P ∧ Q) ⇒ (P ∨ Q)
T T T T T
T F F T T
F T F T T
F F F F T

So this proposition is a tautology.


Problem: (b) (P ∨ ¬ P) and (P ∧ ¬ P)
Solution:
Truth table for (P ∨ ¬P)
P ¬P (P ∨ ¬ P)
T F T
F T T

So this proposition is tautology.


Truth table is for (P ∧ ¬P)
P ¬P (P ∧ ¬ P)
T F F
F T F

So this proposition is a contradiction.

Problem: (c) ¬ (P ∧ Q) ⇒ P ∨ ¬ Q
Solution:
Truth table:
P Q ¬Q P∧Q ¬ (P ∧ Q) P∨¬Q ¬ (P ∧ Q) ⇒ P ∨ ¬ Q
T T F T F T T
T F T F T T T
F T F F T F F
F F T F T T T

So this is a tautology.

(2) Use truth tables to prove or disprove the following equivalencies.


Problem: (a) ¬ (P ∧ Q) ≡ P ∨ ¬ Q
Solution:
Truth table:
P Q ¬Q P∧Q ¬ (P ∧ Q) P∨¬Q
T T F T F T
T F T F T T
F T F F T F
F F T F T T

So this statement is not equivalent.

Problem: (b) ¬ (P ∨ Q) ≡ (¬ P ∧ ¬ Q)
Solution:
Truth table:
P Q ¬P ¬Q P∨Q ¬ (P ∨ Q) (¬ P ∧ ¬ Q)
T T F F T F F
T F F T T F F
F T T F T F F
F F T T F T T

So this statement is equivalent.

Problem: (c) P ⇒ Q ≡ ¬ P ∨ Q
Solution:
Truth Table:
P Q ¬P P⇒Q ¬P∨Q
T T F T T
T F F F F
F T T T T
F F T T T

So this statement is equivalent.

Problem: (d) ¬ (P ⇒ Q) ≡ P ∧ ¬ Q
Solution:
Truth table:
P Q ¬Q P⇒Q ¬ (P ⇒ Q) P∧ ¬Q
T T F T F F
T F T F T T
F T F T F F
F F T T F F

So this statement is equivalent.


Problem: (e) P ∧ (Q ∨ R) ≡ (P ∧ Q) ∨ (P ∧ R)
Solution:
Truth table:
P Q R (Q ∨ R) P ∧ (Q ∨ R) (P ∧ Q) (P ∧ R) (P ∧ Q) ∨ (P ∧ R)
T T T T T T T T
T F T T T F T T
F T T T F F F F
F F T T F F F F
T T F T T T F T
T F F F F F F F
F T F T F F F F
F F F F F F F F

So this statement is equivalent.

You might also like