Efficient Algorithm for Solving CNF/DNF Logic Problem with 9 Input Literals

[DrAlexMV]

Homework Statement

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.

Homework Equations

Just the definition of CNF and DNF

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.

 

[Mark44]

Homework Statement

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.

Homework Equations

Just the definition of CNF and DNF

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.

What do CNF and DNF mean?

 

[DrAlexMV]

Disjunctive normal form and Conjunctive normal form