A 3-CNF formula is a formula in CNF in which every clause contains at most 3 literals. Consider the propositional formula $E = (((P\vee Q)\vee R)\vee\neg(S))$. Explain why there is no 3-CNF formula containing only the variables $P, Q, R$, and $S$ that is logically equivalent to $E$.
As a beginner of mathematical logic I have no clue of solving it. How should I be reasoning?
Let $C_1\land C_2\land\cdots$ be a 3-CNF, where $C_i$'s are the clauses. Since $C_1$ contains at most three literals, there exists one in $\{P, Q, R, S\}$ that is not in $C_1$, without loss of generality, say $P$ is missing from $C_1$.
Then we can make assignments of $Q, R, S$ such that $C_1$ is false, therefore $C_1\land C_2\land \cdots$ is false. Now we assign $P$ to be true, then $E$ is true, so $E\not=C_1\land C_2\land \cdots$.