4

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.

Brian M. Scott
  • 616,228
Twisol
  • 143
  • 5

1 Answers1

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

user474632
  • 427
  • 1
    Thanks Charles, Latex looks much better now. – user474632 Feb 09 '12 at 22:28
  • Excellent, this is exactly what I was hoping to see. Thank you! – Twisol Feb 10 '12 at 00:06
  • As this answer also somewhat indicates, the result generalizes. In other words, for a formula with n variables, each variable needs to appear only once also. – Doug Spoonwood Feb 10 '12 at 00:46
  • 1
    Yes but ... both question and answer gloss over the question of which primitive logical symbols are specified for the language of our sentential logic. And it makes a difference whether you're looking for a sentential formula in which all defined logical symbols have been eliminated. Suppose the only logical primitive is the Sheffer stroke (see Wikipedia). Suppose also you're looking for a formula with no defined symbols. Then the answer to the original question is probably "No", though I have no proof of that. – MikeC Feb 10 '12 at 04:49
  • Nand is an equivalent replacement for And and Or in terms of sentence length. XOr and XNor would be slightly longer however. – user474632 Feb 10 '12 at 16:01
  • 1
    @MikeC: If you only have the Sheffer stroke and no defined symbols, then the number of variables in a formula will be one plus the number of connectives. If you cannot duplicate variables, this severely limits how complex a formula with two variables can be. It is very easy to enumerate them all explicitly and see that there aren't enough of them. – hmakholm left over Monica Feb 12 '12 at 21:02
  • 1
    @Henning: I think you're agreeing with me. Suppose the Sheffer stroke is our only logical primitive. Suppose we're only looking at formulas in primitive notation, that is, with no defined logical symbols. Then we still have 16 (equivalence classes of) formulas to express the 16 semantically distinct cases in the truth table given in the answer. (That's the point of the Sheffer stroke, that you can express anything with enough combinations of it.) But the 16 formulas cannot contain each variabl only once. Isn't that what you said? So the answer in this case is "No, you can't reduce as desired." – MikeC Feb 13 '12 at 02:46
  • @MikeC: Yes, we agree. I was responding to your "though I have no proof of that". – hmakholm left over Monica Feb 13 '12 at 02:51