1. Limited time only! Sign up for a free 30min personal 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!

Homework Help: 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


    Staff: Mentor

    What do CNF and DNF mean?
  4. Jan 22, 2013 #3
    Disjunctive normal form and Conjunctive normal form
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook