# What's wrong with this argument? Determining satisfiability of CNF

I am working with the following definition of the conjunctive normal form of a propositional formula:

A formula $$\phi$$ with propositional variables $$P_1 \ldots P_n$$ is said to be in conjunctive normal form if $$\phi = (C_1 \land \cdots \land C_m)$$ where for each $$1 \leq k \leq m$$, $$C_k$$ is a distinct formula of the form $$L_{1k} \lor \cdots \lor L_{nk}$$ with $$L_{ik} \in \{P_i, \neg P_i \}.$$ In addition, we say that the formula $$P \lor \neg P$$ is in conjunctive normal form. We refer to the $$C_k$$'s as the CNF constituents of $$\phi$$.

It is known that to find the CNF of a formula, we look at the truth table for that formula and write down a constitutent for each assignment to variables in which the formula is false, saying the formula is false in that case. That is, if a formula is false in the case where $$P$$ is true and $$Q$$ is false, we include the constituent equivalent to $$\neg (P \land \neg Q)$$, i.e., we include $$(\neg P \lor Q)$$.

Given a formula already in CNF, it seems easy to determine whether the formula is satisfiable: we merely need to determine how many constituents the formula contains. If the formula is unsatisfiable, it is false in every case and so contains every possible constitutent. If the formula has $$n$$ variables there are $$2^n$$ possible assignments to variables; if the CNF formula has less than $$2^n$$ constituents, then, it must be satisfiable. The number of constituents is determined by the number of times the symbol $$\land$$ appears in the formula. To do this does not require anything other than reading the formula from left to right. I do not see how this is anything other than polynomial in the length of the input, which I am taking to be the length of the formula.

Obviously, however, SAT is an NP-complete problem and showing it is P would probably be a lot harder than the simple observation above. Any help identifying what I am missing would be appreciated.

For example, $$A \land \neg A \land B$$ is not satisfiable, despite only containining 3 constituents.
Of course, you are right that your construction would give $$(\neg A \lor \neg B) \land (\neg A \lor B) \land (A \lor \neg B) \land (A \lor B)$$, which has 4 constituents.