Answer to Question #178167 in Discrete Mathematics for Elaine

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$