Advertisement
If you have a new account but are having problems posting or verifying your account, please email us on hello@boards.ie for help. Thanks :)
Hello all! Please ensure that you are posting a new thread or question in the appropriate forum. The Feedback forum is overwhelmed with questions that are having to be moved elsewhere. If you need help to verify your account contact hello@boards.ie

Disjunctive Normal Form Conversion.

Options
  • 24-05-2007 3:43pm
    #1
    Raskolnikov
    Registered Users Posts: 10,148 ✭✭✭✭


    Can anyone convert this for me to DNF?

    T1 OR T2 AND(T3 OR T4).


Comments

  • Options
    #2
    cousin_borat
    Registered Users Posts: 995 ✭✭✭cousin_borat


    (T1 AND T3 ) OR (T1 AND T4) OR (T2 AND T3) OR (T2 AND T4)
    Raskolnikov wrote:
    Can anyone convert this for me to DNF?

    T1 OR T2 AND(T3 OR T4).


  • Options
    #3
    Raskolnikov
    Registered Users Posts: 10,148 ✭✭✭✭Raskolnikov


    cousin_borat wrote:
    (T1 AND T3 ) OR (T1 AND T4) OR (T2 AND T3) OR (T2 AND T4)
    Is T1 OR T2 AND(T3 OR T4) the same as (T1 OR T2) AND (T3 OR T4) so?


  • Options
    #4
    cousin_borat
    Registered Users Posts: 995 ✭✭✭cousin_borat


    Raskolnikov wrote:
    Is T1 OR T2 AND(T3 OR T4) the same as (T1 OR T2) AND (T3 OR T4) so?

    I'm a little rusty as its 5 years since I done this stuff in CSLL. I'm pretty sure they are Semantically the same but neither are in DNF.


  • Options
    #5
    bonkey
    Registered Users Posts: 15,443 ✭✭✭✭bonkey


    I thought under standard boolean precedence, AND came before OR?

    SO the first statement would be equivalent to :

    T1 OR (T2 AND (T3 OR T4))

    Which gets expanded to :

    T1 OR ((T2 AND T3) OR (T2 AND T4))

    We can then drop the superfluous brackets and get :

    T1 OR (T2 AND T3) OR (T2 AND T4)

    and finally...

    T1 OR T2 AND T3 OR T2 AND T4


  • Options
    #6
    Fremen
    Registered Users Posts: 2,481 ✭✭✭Fremen


    Is T1 OR T2 AND(T3 OR T4) the same as (T1 OR T2) AND (T3 OR T4) so?

    No, the two are different

    with T1 OR T2 AND(T3 OR T4) if T1 is true, then the expression evaluates to true.

    with (T1 OR T2) AND (T3 OR T4) T1 can be true but if T3 and T4 are false, then it evaluates to false.

    I'm assuming T1 OR T2 AND(T3 OR T4) is equivalent to T1 OR (T2 AND(T3 OR T4))


  • Advertisement
Advertisement