JNTU B.Tech II MATHEMATICAL FOUNDATIONS OF COMPUTER SCIENCE Previous Question Paper (October - 2020 - R16)

To obtain the Principal Conjunctive Normal Form (PCNF), we first simplify the given expression: (~p → r) ∧ (q ↔ p).

1. Simplify (~p → r): Using the identity (A → B) ≡ (~A ∨ B), we get (p ∨ r).

2. Simplify (q ↔ p): This is equivalent to (q → p) ∧ (p → q), which is (~q ∨ p) ∧ (~p ∨ q).

3. Combine the expressions: (p ∨ r) ∧ (~q ∨ p) ∧ (~p ∨ q).

4. Convert to PCNF by adding missing variables using the distributive law (A ∨ (B ∧ ~B) ≡ A):

For (p ∨ r): (p ∨ r ∨ q) ∧ (p ∨ r ∨ ~q) ≡ (p ∨ q ∨ r) ∧ (p ∨ ~q ∨ r).

For (~q ∨ p): (~q ∨ p ∨ r) ∧ (~q ∨ p ∨ ~r) ≡ (p ∨ ~q ∨ r) ∧ (p ∨ ~q ∨ ~r).

For (~p ∨ q): (~p ∨ q ∨ r) ∧ (~p ∨ q ∨ ~r).

5. Combine and remove duplicates: (p ∨ q ∨ r) ∧ (p ∨ ~q ∨ r) ∧ (p ∨ ~q ∨ ~r) ∧ (~p ∨ q ∨ r) ∧ (~p ∨ q ∨ ~r).

In minterm notation, this is M₀ ∧ M₂ ∧ M₃ ∧ M₄ ∧ M₅.

To show inconsistency, we assume all premises are true and derive a contradiction:

1. P → Q
2. R → S
3. P ∨ R
4. ~(Q ∨ S) ≡ ~Q ∧ ~S

From (4), we have ~Q and ~S. Using Modus Tollens on (1) and ~Q, we get ~P. Using Modus Tollens on (2) and ~S, we get ~R. Now we have ~P and ~R, which implies ~(P ∨ R). This contradicts premise (3), which states P ∨ R. Since the set of premises leads to a contradiction, the premises are inconsistent.