Proving any propositional formula can be written a certain way

Question

How do I start with this? I know that there are $2^4$ different possible truth tables for $P$ but i'm not sure where to go from there.

Answer 1

Note the equivalence of formulae $$\def\lequiv{\Leftrightarrow} \begin{align*} \lnot(A\lor B)&\sim(\lnot A)\land(\lnot B)\\ \lnot(A\land B)&\sim(\lnot A)\lor(\lnot B)\\ \lnot(A\lequiv B)&\sim(\lnot A)\lequiv B\\ (\lnot\lnot A)\square B&\sim A\square B\\ A\square\lnot\lnot B&\sim A\square B\\ \end{align*} $$ so for every $P$ it suffices to show one of $P,\lnot P$ is equivalent to $A\square B$.

Now count how many times $P$ is true (for brevity I'll say "$X$ is true" instead of "a $\{\bot,\top\}$-valuation $v$ such that $v(X)=\top$"):

• If $P$ is never true, then $P\sim(p\lequiv\lnot p)$. By duality we get $P$ always true.

• If $P$ is true only in one case then $P$ is obviously equivalent to $A\land B$ where we can read $A,B$ from the truth table. Dually this gives $P$ true in all-but-one case.

• All that remains is when $P$ is true in two cases (and false in the other two). WLOG suppose $P$ is true when both $p,q$ are. There is another case of $(p,q)$ where $P$ is true, i.e., one of $(\bot,\bot),(\bot,\top),(\top,\bot)$. It isn't hard to write down an equivalent $A\square B$ in each of these cases. For example, for $(\top,\bot)$, we have $P$ is true if (and only if) $p$ is, so we can use $p\land p$.