I need to use theorem 2.1.1 in order to verify the following:
∼((∼p ∧ q) ∨ (∼ p ∧ ∼q)) ∨ (p ∧ q) ≡ p
I applied the Double Negative Law to get
((p ∧ q) ∨ (∼p ∧ ∼q)) ∨ (p ∧ q)
I noticed we have (p ∧ q) twice, which is redundant so I applied the Idempotent law to get:
(p ∧ q) ∨ (∼p ∧ ∼q)
not sure if that was the correct step. But from this point I get lost. Essentially this is saying p and q or not p and not q.
If anyone can let me know if I am going in the right direction and any help regarding what to do next, it would be greatly appreciated. I have been trying to solve this myself for a while now and haven't been able to get past this point.
$\endgroup$ 13 Answers
$\begingroup$∼((∼p ∧ q) ∨ (∼ p ∧ ∼q)) ∨ (p ∧ q) ≡ p
I applied the Double Negative Law to get
((p ∧ q) ∨ (∼p ∧ ∼q)) ∨ (p ∧ q)
You have to negate everything in the brackets following the negation symbol, not just the first term.
$\neg\underline{((\neg p ∧ q) ∨ (\neg p ∧ \neg q))} ∨ (p ∧ q)$
Apply deMorgan's
${(\neg\underline{(\neg p ∧ q)} \land \neg\underline{(\neg p ∧ \neg q)})} ∨ (p ∧ q)$
Again
${((\neg\neg p \lor \neg q) \land (\neg\neg p \lor \neg\neg q))} ∨ (p ∧ q)$
Now apply Double Negation
${((p \lor \neg q) \land (p \lor q))} ∨ (p ∧ q)$
$\endgroup$ $\begingroup$Your first step is not correct. There is no double negation there, since the first negation is the negation of the disjunction of $\neg p \land q$ and $\neg p \land \neg q$
However, whenever you have such a negation (a negation of a disjunction), you can do DeMorgan. Do you see how that works in this case?
$\endgroup$ $\begingroup$Step-by-step:
$$\begin{align} \lnot((\lnot p \land q) \lor (\lnot p \land \lnot q)) \lor (p \land q) & ≡ \text{ [de Morgan]} \\ (\lnot(\lnot p \land q) \land \lnot(\lnot p \land \lnot q)) \lor (p \land q) & ≡ \text{ [de Morgan]} \\ ((\lnot\lnot p \lor \lnot q) \land (\lnot\lnot p \lor \lnot\lnot q)) \lor (p \land q) & ≡ \text{ [double neg]} \\ ((p \lor \lnot q) \land (p \lor q)) \lor (p \land q) & ≡ \text{ [distributivity]} \\ (p \lor (\lnot q \land q)) \lor (p \land q) & ≡ \text{ [complementation]} \\ (p \lor 0) \lor (p \land q) & ≡ \text{ [identity for disjunction]} \\ p \lor (p \land q) & ≡ \text{ [identity for conjunction]} \\ (p\land 1) \lor (p \land q) & ≡ \text{ [distributivity]} \\ p\land (1 \lor q) & ≡ \text{ [annihilation]} \\ p\land 1 & ≡ \text{ [identity]} \\ p & \ \ \ \text{ [q.e.d]}\\ \end{align}$$
$\endgroup$
