Answer to Question #214877 in Discrete Mathematics for Taj

Question

Q2. Show that that the following are Logically equivalent or not.
1. ∼ (p ∧ q) and ∼ p∨ ∼ q (de Morgan’s Laws)
2. ∼ (p ∧ q) and ∼ p∨ ∼ q
3. (∼ p ∨ q) ∧ (∼ q) ≡∼ (p ∨ q).
4. (p∧ ∼ q) ∨ (∼ p ∨ q) ≡ t.

Answer 1

1. $\neg(p \wedge q) = 0 \Leftrightarrow p \wedge q =1 \Leftrightarrow p=q=1$

$(\neg p\vee\neg q)=0 \Leftrightarrow \neg p=\neg q=0 \Leftrightarrow p=q=1$

Therefore, the formulas $\neg(p \wedge q)$ and $\neg p\vee\neg q$ are logically equivalent.

2. $\neg(p \vee q) = 1 \Leftrightarrow p \vee q =0 \Leftrightarrow p=q=0$

$(\neg p\wedge\neg q)=1 \Leftrightarrow \neg p=\neg q=1 \Leftrightarrow p=q=0$

Therefore, the formulas $\neg(p \vee q)$ and $\neg p\wedge\neg q$ are logically equivalent.

3. $(\neg p \vee q) \wedge \neg q =1 \Leftrightarrow \neg p \vee q=1, \neg q=1 \Leftrightarrow \neg p=1, q=0 \Leftrightarrow p=q=0$

$\neg (p \vee q)=1 \Leftrightarrow p \vee q=0 \Leftrightarrow p=q=0$

Therefore, the formulas $(\neg p \vee q) \wedge \neg q$ and $\neg (p \vee q)$ are logically equivalent.

4. $(p\wedge \neg q) \vee (\neg p \vee q) =0 \Leftrightarrow p\wedge \neg q=0, \neg p \vee q=0$ $\Leftrightarrow p\wedge \neg q=0, \neg p = q = 0$ $\Leftrightarrow p\wedge \neg q=0, p = 1, q = 0$ $\Leftrightarrow p\wedge \neg q=0, p\wedge \neg q=1$ $\Leftrightarrow$ never

Therefore, $(p\wedge \neg q) \vee (\neg p \vee q) \equiv 1$ (i.e. it is a tautology)