Answer to Question #178167 in Discrete Mathematics for Elaine

Question #178167

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)
1
Expert's answer
2021-05-04T13:15:29-0400

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"


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!

Leave a comment

LATEST TUTORIALS
New on Blog
APPROVED BY CLIENTS