Results 1 to 2 of 2

Math Help - disjunctive normal form

  1. #1
    Newbie
    Joined
    May 2010
    Posts
    1

    disjunctive normal form

    I know that the disjunctive normal form is not unique.

    <Start of excerpt from Wolfram MathWorld>
    A statement is in disjunctive normal form if it is a disjunction (sequence of ORs) consisting of one or more disjuncts, each of which is a conjunction (AND) of one or more literals (i.e., statement letters and negations of statement letters; Mendelson 1997, p. 30). Disjunctive normal form is not unique.
    <End of excerpt from Wolfram MathWorld>

    For my purposes, I repeat, for emphasis, one sentence from the above excerpt:
    Disjunctive normal form is not unique

    OK.

    ( I use "~" to denote Logical-Negation, "+" to denote Logical-OR (inclusive), and "*" to denote Logical-AND )

    I am _not_ looking for a formal proof of what I trying to do below; informality is sought.

    I have a statement in conjunctive normal form, and I can express that statement in disjunctive normal form.

    (~P + Q) * (P + ~Q) (Conjunctive Normal Form)
    Using the Law of Distribution, this statement can be converted to
    (~P * P) + (~P * ~Q) + (Q * P) + (Q * ~Q)
    Because of the Law of Contradiction, this statement can be converted to
    FALSE + (~P * ~Q) + (Q * P) + FALSE
    which can be converted to
    (~P * ~Q) + (Q * P) (which is in disjunctive normal form)

    I want to arrive at another, logically equivalent, statement in disjunctive normal form :
    (P * ~Q) + (~P * Q)

    How do I get, informally,
    From: (~P * ~Q) + (Q * P)
    To: (P * ~Q) + (~P * Q)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member Failure's Avatar
    Joined
    Jul 2009
    From
    Zürich
    Posts
    555
    Quote Originally Posted by brooks972 View Post
    I know that the disjunctive normal form is not unique.

    <Start of excerpt from Wolfram MathWorld>
    A statement is in disjunctive normal form if it is a disjunction (sequence of ORs) consisting of one or more disjuncts, each of which is a conjunction (AND) of one or more literals (i.e., statement letters and negations of statement letters; Mendelson 1997, p. 30). Disjunctive normal form is not unique.
    <End of excerpt from Wolfram MathWorld>

    For my purposes, I repeat, for emphasis, one sentence from the above excerpt:
    Disjunctive normal form is not unique

    OK.

    ( I use "~" to denote Logical-Negation, "+" to denote Logical-OR (inclusive), and "*" to denote Logical-AND )

    I am _not_ looking for a formal proof of what I trying to do below; informality is sought.

    I have a statement in conjunctive normal form, and I can express that statement in disjunctive normal form.

    (~P + Q) * (P + ~Q) (Conjunctive Normal Form)
    Using the Law of Distribution, this statement can be converted to
    (~P * P) + (~P * ~Q) + (Q * P) + (Q * ~Q)
    Because of the Law of Contradiction, this statement can be converted to
    FALSE + (~P * ~Q) + (Q * P) + FALSE
    which can be converted to
    (~P * ~Q) + (Q * P) (which is in disjunctive normal form)

    I want to arrive at another, logically equivalent, statement in disjunctive normal form :
    (P * ~Q) + (~P * Q)

    How do I get, informally,
    From: (~P * ~Q) + (Q * P)
    To: (P * ~Q) + (~P * Q)
    Well, you can't: because (\neg p \wedge \neg q)\vee (p\wedge q) does not imply (p\wedge \neg q)\vee (\neg p\wedge q).
    Proof: Set both p and q true. In that case (\neg p \wedge \neg q)\vee (p\wedge q) is true, but (p\wedge \neg q)\vee (\neg p\wedge q) is false.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. disjunctive normal form question
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: November 6th 2011, 11:22 PM
  2. Boolean Disjunctive Normal Form
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 5th 2011, 03:23 AM
  3. Disjunctive Normal Form
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 15th 2009, 07:03 PM
  4. Disjunctive Normal form
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: June 11th 2007, 05:03 PM
  5. Disjunctive Normal Form
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: February 23rd 2007, 01:03 PM

Search Tags


/mathhelpforum @mathhelpforum