Results 1 to 2 of 2

Math Help - Derivation using Logical Laws

  1. #1
    Member
    Joined
    Dec 2009
    Posts
    224

    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:



    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,527
    Thanks
    773

    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 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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Derivation and Jordan derivation
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: May 8th 2011, 09:22 PM
  2. Prove/disprove using logical using logical arguments
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: February 24th 2010, 06:29 AM
  3. Replies: 3
    Last Post: January 21st 2010, 07:45 AM
  4. Is it logical???
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: November 8th 2009, 08:10 PM
  5. [SOLVED] Logical Laws and Equivalence
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 23rd 2009, 02:21 AM

Search Tags


/mathhelpforum @mathhelpforum