Answer to Question #178168 in Discrete Mathematics for Elaine

Question

V. Determine whether each pair of propositions are logically equivalent or not. Use Logical Equivalence Rules.

1. ¬(p∨(¬p∧q)) and ¬p∧¬q
2. ¬(p↔q) and p↔¬q
3. p↔(q∧r) and (p↔q)∧(p↔r)
4. ¬(p↔q) and p⊕q

Answer 1

Let us determine whether each pair of propositions are logically equivalent or not. 

1) Since $¬(p∨(¬p∧q))=¬((p∨¬p)∧(p\lor q)))=¬(T∧(p\lor q))=¬(p\lor q)=¬p\land ¬q$, we conclude that $¬(p∨(¬p∧q))$ and $¬p∧¬q$ are logically equivalent.

2) Since $¬(p↔q)=¬((p\to q)\land (q\to p))=¬((\neg p\lor q)\land (\neg q\lor p))= ¬(\neg p\lor q)\lor\neg (\neg q\lor p)=(p\land\neg q)\lor (q\land \neg p)=(p\lor q)\land (\neg q\lor\neg p)= (\neg q\to p)\land (p\to\neg q)=p↔\neg q$, we conclude that $¬(p↔q)$ and $p↔¬q$ are logically equivalent.

3) Since for $p=r=0, \ q=1$ we have that $p↔(q∧r)=F↔(T∧F)=F↔F=T$ but $(p↔q)∧(p↔r)=(F↔T)∧(F↔F)=F\land T=F$, we conclude that the formulas are not logically equivalent.

4) Since $¬(p↔q) = ¬((p\to q)\land (q\to p))= ¬((\neg p\lor q)\land (\neg q\lor p))= ¬(\neg( p\land \neg q)\land \neg( q\land \neg p))= (p(q\oplus 1)\oplus 1)(q(p\oplus 1)\oplus 1)\oplus 1= (pq\oplus p\oplus 1)(qp\oplus q\oplus 1)\oplus 1=pq\oplus pq \oplus pq \oplus pq \oplus pq \oplus p\oplus pq\oplus q \oplus 1\oplus 1=p\oplus q,$

we conclude that the formulas $¬(p↔q)$ and $p⊕q$ are logically equivalent.