Question

Find simpler statement forms that are logically equivalent to p ⊕ p and (p ⊕ p) ⊕ p.

b) Is (p ⊕ q) ⊕ r ≡ p ⊕ (q ⊕ r)? Justify your answer.

c) Is (p ⊕ q) ∧ r ≡ (p ∧ r) ⊕ (q ∧ r)? Justify your answer.

Answer 1

a) Let us find the truth table for $p ⊕ p$ and $(p ⊕ p) ⊕ p:$

$\begin{array}{|c|c|c|c|c|c|c|} \hline p & p\oplus p & (p\oplus p)\oplus p \\ \hline 0 & 0 & 0 \\ \hline 1 & 0 & 1 \\ \hline \end{array}$

It follows that $p ⊕ p\equiv 0$ and $(p ⊕ p) ⊕ p\equiv p$.

b) Let us find the truth table for $(p ⊕ q) ⊕ r$ and $p ⊕ (q ⊕ r)$:

$\begin{array}{|c|c|c|c|c|c|c|} \hline p & q & r & p\oplus q & (p\oplus q)\oplus r & q\oplus r & p\oplus (q\oplus r)\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 1 & 0 & 1 & 1 & 1\\ \hline 0 & 1 & 0 & 1 & 1 & 1 & 1\\ \hline 0 & 1 & 1 & 1 & 0 & 0 & 0\\ \hline 1 & 0 & 0 & 1 & 1 & 0 & 1\\ \hline 1 & 0 & 1 & 1 & 0 & 1 & 0\\ \hline 1 & 1 & 0 & 0 & 0 & 1 & 0\\ \hline 1 & 1 & 1 & 0 & 1 & 0 & 1\\ \hline \end{array}$

Since the formulas $(p ⊕ q) ⊕ r$ and $p ⊕ (q ⊕ r)$ have the same truth value in all cases, they are logically equivalent. It follows that $(p ⊕ q) ⊕ r ≡ p ⊕ (q ⊕ r).$

c) Let us find the truth table for $(p ⊕ q) ∧ r$ and $(p ∧ r) ⊕ (q ∧ r)$:

$\begin{array}{|c|c|c|c|c|c|c|c|} \hline p & q & r & p\oplus q & (p\oplus q)\land r & p\land r & q\land r &p\land r\oplus q\land r\\ \hline 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\ \hline 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0\\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 1 & 1\\ \hline 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 0 & 1\\ \hline 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\ \hline 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0\\ \hline \end{array}$

Since the formulas $(p ⊕ q) ∧ r$ and $(p ∧ r) ⊕ (q ∧ r)$ have the same truth value in all cases, they are logically equivalent. It follows that $(p ⊕ q) ∧ r ≡ (p ∧ r) ⊕ (q ∧ r).$