# Homework Help: CNF/DNF logic problem

1. Jan 21, 2013

### DrAlexMV

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. Jan 22, 2013

### Staff: Mentor

What do CNF and DNF mean?

3. Jan 22, 2013

### DrAlexMV

Disjunctive normal form and Conjunctive normal form