4
$\begingroup$

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.

  • 0
    I was assuming $\lnot$, $\lor$, $\land$, $\rightarrow$ only. Will delete previous comment.2012-02-09

1 Answers 1

6

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.

Assuming the order of values in your table is

$ \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}$

  • 0
    @MikeC: Yes, we agree. I was responding to your "though I have no proof of that".2012-02-13