Solution Found!
Prove the following tautologies by starting with the left
Chapter 1, Problem 28(choose chapter or problem)
Prove the following tautologies by starting with the left side and finding a series of equivalent wffs that will convert the left side into the right side. You may use any of the equivalencies in the list on page 9 or the equivalencies from Exercise 26.
a. \(A \wedge B^{\prime})^{\prime} \vee B \leftrightarrow A^{\prime} \vee B\)
b. \(A \wedge\left(A \wedge B^{\prime}\right)^{\prime} \leftrightarrow A \wedge B\)
c. \(A \wedge B)^{\prime} \wedge\left(A \vee B^{\prime}\right) \leftrightarrow B^{\prime}\)
Questions & Answers
QUESTION:
Prove the following tautologies by starting with the left side and finding a series of equivalent wffs that will convert the left side into the right side. You may use any of the equivalencies in the list on page 9 or the equivalencies from Exercise 26.
a. \(A \wedge B^{\prime})^{\prime} \vee B \leftrightarrow A^{\prime} \vee B\)
b. \(A \wedge\left(A \wedge B^{\prime}\right)^{\prime} \leftrightarrow A \wedge B\)
c. \(A \wedge B)^{\prime} \wedge\left(A \vee B^{\prime}\right) \leftrightarrow B^{\prime}\)
Step 1 of 3
(a) Consider the tautology, \(\left(A \wedge B^{\prime}\right)^{\prime} \vee B \leftrightarrow A^{\prime} \vee B\). Starting from left,
1. \(\left(A \wedge B^{\prime}\right)^{\prime} \vee B\), applying De Morgan’s law on \(\left(A \wedge B^{\prime}\right)^{\prime}\),
2. \(\left(A^{\prime} \vee\left(B^{\prime}\right)^{\prime}\right) \vee B\), applying \(\left(A^{\prime}\right)^{\prime} \leftrightarrow A\) , on \(\left(B^{\prime}\right)^{\prime}\)
3. \(\left(A^{\prime} \vee B\right) \vee B\), applying associative property 2a.
4. \(A^{\prime} \vee(B \vee B)\) applying \(A \vee A \leftrightarrow A\)
5. \(A^{\prime} \vee B\)
Thus starting from the left side, the right side is obtained.
Hence it is proved that \(\left(A \wedge B^{\prime}\right)^{\prime} \vee B \leftrightarrow A^{\prime} \vee B\).