Question

Let p and q be two propositions. Consider the following two formulae in propositional logic.

S₁ : (¬p ∧ (p ∨ q)) → q

S₂ : q → (¬p ∧ (p ∨ q))

Which one of the following choices is correct?

1. Neither S₁ nor S₂ is a tautology.
2. S₁ is not a tautology but S₂ is a tautology.
3. Both S₁ and S₂ are tautologies.
4. S₁ is a tautology but S₂ is not a tautology.

Answer 1

Correct Answer - Option 4 : S₁ is a tautology but S₂ is not a tautology.

Data:

¬ ≡ NOT ≡ ̅ 

OR ≡ ∨ ≡ +

AND ≡ ∧ ≡ .

Formula:

a → b ≡ a̅ + b

Calculation:

S₁ : (¬p ∧ (p ∨ q)) → q 

S₁ ≡ (p̅.(p + q) → q

S₁ ≡ (p̅.p + p̅.q) → q

S₁ ≡ (p̅.q) → q

S₁ ≡ \(\overline{\overline p.q} + q\)

S₁ ≡ p + q̅ + q ≡ p + 1 ≡ 1

S1 is a tautology

S₂ ≡  q → (¬p ∧ (p ∨ q))

S2 ≡ q → (p̅.(p + q))

S2 ≡ q̅  + (p̅.p + p̅.q)) 

S2 ≡ q̅ + p̅.q ≡ p̅ + q̅  

S2 is not a tautology.

Therefore option 4 is correct