# How far can a logical sentence with only two variables be simplified?

Given any sentence in sentential logic with two variables ($\mathbf{P}$ and $\mathbf{Q}$), is it possible to reduce it to an equivalent sentence where each variable is only invoked once?

As an example off the top of my head, let's take a sentence

$$\big((\mathbf{P}\lor\mathbf{Q})\land\mathbf{Q}\big)\land\big((\mathbf{P}\land\mathbf{Q})\lor\lnot\mathbf{P}\big)\;.$$

I've just derived that it's equivalent to $(\mathbf{Q}\lor\lnot\mathbf{P})$, which is a sentence that only invokes $\mathbf{P}$ and $\mathbf{Q}$ once each. Is this applicable to any complex sentence with two variables?

My thought process is that, in a truth table with two variables, the only possible values of a sentence are all true, three true and one false, two of each, one true and three false, and all false. These line up with $\mathbf{T}$, $\mathbf{P}\land\mathbf{Q}$, $\mathbf{P}\leftrightarrow\mathbf{Q}$, $\mathbf{P}\lor\mathbf{Q}$, and $\mathbf{F}$, respectively. The order of the $\mathbf{T}$'s and $\mathbf{F}$'s in the table may differ, but that can be accounted for by applying negation to one or both of the operands.

-
Wouldn't that be (~ A <-> ~ B) ? – Twisol Feb 9 '12 at 21:42
Sorry, drop one of those negations. – Twisol Feb 9 '12 at 21:48
I was assuming $\lnot$, $\lor$, $\land$, $\rightarrow$ only. Will delete previous comment. – André Nicolas Feb 9 '12 at 22:06

Using truth tables observe that four possible variable states dictate the outcome of one expression, allowing $2^4$ possible logical functions of two variables. The most simplified sentence for the corresponding table will be your solution.
$$\begin{array}{l|cccc} A:& T&T&F&F\\ B:& T&F&T&F\\ Contradiction:&F&F&F&F\\ \lnot (A\lor B):& F&F&F&T\\ \lnot A\land B:& F&F&T&F\\ \lnot A:& F&F&T&T\\ A\land \lnot B:& F&T&F&F\\ \lnot B:& F&T&F&T\\ \lnot(A \iff B):& F&T&T&F\\ \lnot (A\land B):& F&T&T&T\\ A\land B:& T&F&F&F\\ A \iff B:& T&F&F&T\\ B:&T&F&T&F\\ \lnot A\lor B:& T&F&T&T\\ A:& T&T&F&F\\ A\lor \lnot B:& T&T&F&T\\ A\lor B:& T&T&T&F\\ Tautology:& T&T&T&T\\ \end{array}$$