1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

CNF/DNF logic problem

  1. Jan 21, 2013 #1
    1. The problem statement, all variables and given/known data

    There exists a function f. Assume that you are given f's CNF representation and f's DNF representation. The CNF representation has some number of clauses, and each clause has 3 literals. The DNF representation has some number of terms where each term has 3 literals. The CNF representation and the DNF representation correspond to the same function f. Now you are also given an input x = x_1,....,x_n. Give an algorithm for determining f(x) (either T or F) that only looks at 9 literals within x.


    2. Relevant equations

    Just the definition of CNF and DNF

    3. The attempt at a solution

    CNF is formatted such as: (A and B and C) or (D and E and F).
    DNF is formatted such as: (A or B or C) and (D or E or F).

    Somehow since you only need to look at one literal in a term of the CNF to know whether that term will be false, you can look also look at that same literal in the DNF to see if that term will be true in the DNF.

    I am not sure what else to do.
     
  2. jcsd
  3. Jan 22, 2013 #2

    Mark44

    Staff: Mentor

    What do CNF and DNF mean?
     
  4. Jan 22, 2013 #3
    Disjunctive normal form and Conjunctive normal form
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: CNF/DNF logic problem
  1. Logic Problem (Replies: 2)

  2. Pizza Logic problem (Replies: 3)

  3. Hardest logic problem! (Replies: 0)

Loading...