# Thread: Derivation using Logical Laws

1. ## Derivation using Logical Laws

Let A be the statement form $\displaystyle (\neg p \to (q \leftrightarrow r))$. Find a statement form B in "relaxed" disjunctive normal form which is logically equivalent to A. Then Show that $\displaystyle A \approx B$ (i.e. derive B from A using logical laws).

Attempt:

Here's my truth table, I've marked with a * the rows where A is true:

So the disjunctive normal form would be:

$\displaystyle B= ((((((\neg p \wedge (\neg q \wedge \neg r)) \vee (\neg p \wedge q \wedger))) \vee (p \wedge (\neg p \wedge \neg r))) \vee (p \wedge (\neg q \wedge r))) \vee (p \wedge(q \wedge \neg r))) \vee(p \wedge(q \wedge r)))$

Is this correct? ("Relaxed" DNF means we must have disjunctions of conjunctions in which eachvstatement variable occurs exactly once).

Now, we must derive B from A using logical laws

$\displaystyle A=(\neg p \to (q \to r))$

$\displaystyle \iff (\neg p \to ((q \wedge r)\vee(\neg q \wedge \neg r)))$ (Equivalence law)

$\displaystyle \iff (\neg \neg p \vee ((q \wedge r) \vee (\neg q \wedge \neg r)))$ (Implication law)

$\displaystyle \iff (p \vee ((q \wedge r) \vee (\neg q \wedge \neg r)))$ (Double negation)

$\displaystyle \iff (p \wedge ((q \wedge r ) \vee \neg (q \vee r)))$ (De Morgan's law)

$\displaystyle \iff ((p \vee (q \wedge r)) \vee (p \vee \neg (q \vee r)))$ (Distributive law)

This is how far I've got. Could anyone please show me how to complete this?

P.S. Here are the list of all laws http://img833.imageshack.us/img833/9242/laws.jpg

2. ## Re: Derivation using Logical Laws

"Relaxed" DNF means we must have disjunctions of conjunctions in which eachvstatement variable occurs exactly once
What is a "non-relaxed" DNF is then? I would say, the requirement to have each variable in every conjunct makes it the most stringent DNF. This would probably make the derivation pretty long. If not every variable has to appear, then $\displaystyle p\lor(r\land q)\lor(\neg r\land\neg q)$ would work as a DNF.

Your DNF is correct except that it misses r in the second disjunct. It is not necessary to write all the parentheses. In fact, more compact notations are preferable for DNFs, such as $\displaystyle p\bar{q}\bar{r}$ instead of $\displaystyle p\land\neg q\land\neg r$.