# Derivation using Logical Laws

• Aug 3rd 2011, 06:10 AM
demode
Derivation using Logical Laws
Let A be the statement form $(\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 $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:

http://img607.imageshack.us/img607/2843/tablew.jpg

So the disjunctive normal form would be:

$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

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

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

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

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

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

$\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
• Aug 4th 2011, 06:24 AM
emakarov
Re: Derivation using Logical Laws
Quote:

"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 $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 $p\bar{q}\bar{r}$ instead of $p\land\neg q\land\neg r$.