Question

IV. Use Logical Equivalence Rules to simplify the following. Construct the truth tables for each of the compound propositions and its simplified expression.

1. ¬b∧(a→b)∧a
2. (a→b)↔(¬a∨b)
3. ((p→q)→r)∧(¬q↔(p∧¬q))
4. ¬a∧(b⊕c)∧(¬b∨c)

Answer 1

1) $\neg b \wedge \left( {a \to b} \right) \wedge a = \neg b \wedge \left( {\neg a \vee b} \right) \wedge a = \left( {\neg b \wedge \neg a \vee \neg b \wedge b} \right) \wedge a = \left( {\neg b \wedge \neg a \vee 0} \right) \wedge a = \neg b \wedge \neg a \wedge a = \neg b \wedge \left( {\neg a \wedge a} \right) = \neg b \wedge 0 = 0$

We have a contradiction.

Let's build a truth table for the formula to show that it is a contradiction:

Answer: contradiction

2) $\left( {a \to b} \right) \leftrightarrow \left( {\neg a \vee b} \right) = \left( {\neg a \vee b} \right) \leftrightarrow \left( {\neg a \vee b} \right) = 1$

We have a tautology.

Let's build a truth table for the formula to show that it is a tautology:

Answer: tautology

3) $\left( {\left( {p \to q} \right) \to r} \right) \wedge \left( {\neg q \leftrightarrow \left( {p \wedge \neg q} \right)} \right) = \left( {\neg \left( {p \to q} \right) \vee r} \right) \wedge \left( {\neg q \to \left( {p \wedge \neg q} \right)} \right) \wedge \left( {\left( {p \wedge \neg q} \right) \to \neg q} \right) = \left( {\neg \left( {\neg p \vee q} \right) \vee r} \right) \wedge \left( {q \vee \left( {p \wedge \neg q} \right)} \right) \wedge \left( {\neg \left( {p \wedge \neg q} \right) \vee \neg q} \right) = \left( {p \wedge \neg q \vee r} \right) \wedge \left( {q \vee \left( {p \wedge \neg q} \right)} \right) \wedge \left( {\neg p \vee q \vee \neg q} \right) = \left( {\left( {p \wedge \neg q} \right) \vee \left( {r \wedge q} \right)} \right) \wedge \left( {\neg p \vee 1} \right) = \left( {\left( {p \wedge \neg q} \right) \vee \left( {r \wedge q} \right)} \right) \wedge 1 = \left( {p \wedge \neg q} \right) \vee \left( {r \wedge q} \right)$

Let's build a truth table for the given ${f_1} = \left( {\left( {p \to q} \right) \to r} \right) \wedge \left( {\neg q \leftrightarrow \left( {p \wedge \neg q} \right)} \right)$ and obtained ${f_2} = \left( {p \wedge \neg q} \right) \vee \left( {r \wedge q} \right)$ formulas:

Thus, the formula is found correctly

Answer: $\left( {p \wedge \neg q} \right) \vee \left( {r \wedge q} \right)$

4) $\neg a \wedge \left( {b \oplus c} \right) \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \overline {\left( {b \leftrightarrow c} \right)} \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \overline {\left( {\left( {b \to c} \right) \wedge \left( {c \to b} \right)} \right)} \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \left( {\overline {\left( {b \to c} \right)} \vee \overline {\left( {c \to b} \right)} } \right) \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \left( {\overline {\left( {\neg b \vee c} \right)} \vee \overline {\left( {\neg c \vee b} \right)} } \right) \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \left( {\left( {b \wedge \neg c} \right) \vee \left( {c \wedge \neg b} \right)} \right) \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \left( {b \vee c} \right) \wedge \left( {\neg c \vee c} \right) \wedge \left( {b \vee \neg b} \right) \wedge \left( {\neg c \vee \neg b} \right) \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \left( {b \vee c} \right) \wedge 1 \wedge 1 \wedge \left( {\neg c \vee \neg b} \right) \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \left( {b \vee c} \right) \wedge \left( {\neg c \vee \neg b} \right) \wedge \left( {\neg b \vee c} \right) = \neg a \wedge \left( {b \vee c} \right) \wedge \neg b \wedge \left( {\neg c \vee c} \right) = \neg a \wedge \left( {b \vee c} \right) \wedge \neg b = \left( {\neg a \wedge b \vee \neg a \wedge c} \right) \wedge \neg b = \neg a \wedge b \wedge \neg b \vee \neg a \wedge c \wedge \neg b = 0 \vee \neg a \wedge c \wedge \neg b = \neg a \wedge c \wedge \neg b$

Let's build a truth table for the given and obtained formulas:

Thus, the formula is found correctly.

Answer: $\neg a \wedge c \wedge \neg b$