Solve each of the following exercises.
For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.
First draw parse trees for the formulas below. Then write a truth table for each of these two formulas. Include intermediate subformulas (nodes from your parse tree) as columns.
First draw parse trees for the formulas below. Use the parse trees to parenthesize the formulas fully. Then, negate the resulting formulas (using the parse trees as a hint) by applying double negation and De Morgan's laws, until all negations are on the variables. You will also find it useful to remember that $\neg (F \to G) \equiv (F \wedge \neg G)$.
First draw parse trees for the formulas below. Use the parse trees to parenthesize the formulas fully. Then, use the parse trees and the equivalences from the table below to simplify the resulting formulas as much as you can. It might be also helpful to remember that $F \to G \equiv (\neg F \vee G)$. You might find it useful to note which equivalences you use as you are writing your simplifications; do not bother memorizing the names.
Name | $\wedge$-version | $\vee$-version |
---|---|---|
Double negation | $\neg \neg p \equiv p$ | |
DeMorgan's laws | $\neg (p \wedge q) \equiv (\neg p \vee \neg q)$ | $\neg (p \vee q) \equiv (\neg p \wedge \neg q)$ |
Commutativity | $( p \wedge q ) \equiv (q \wedge p)$ | $( p \vee q ) \equiv (q \vee p)$ |
Associativity | $(p \wedge (q \wedge r)) \equiv ((p \wedge q) \wedge r)$ | $(p \vee (q \vee r)) \equiv ((p \vee q) \vee r)$ |
Distributivity | $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$ | $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$ |
Identity | $p \wedge TRUE \equiv p$ | $p \vee FALSE \equiv p$ |
$p \wedge FALSE \equiv FALSE$ | $p \vee TRUE \equiv TRUE$ | |
Idempotence | $p \wedge p \equiv p $ | $p \vee p \equiv p$ |
Absorption | $p \wedge (p \vee q) \equiv p$ | $p \vee (p \wedge q) \equiv p$ |
Here, $p, q, r$ are propositional variables. TRUE and FALSE are formulas that are always true and always false, respectively. In particular, $TRUE = (A \vee \neg A)$ and $FALSE = (A \wedge \neg A)$ for some (any) formula $A$.
Take a formula $(\neg B \vee A) \to (\neg A \wedge \neg B)$. Now, do all of the following tasks on this formula: