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
    Wouldn't that be (~ __A__ <-> ~ __B__) ?2012-02-09
  • 0
    Sorry, drop one of those negations.2012-02-09
  • 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}$$

  • 1
    Thanks Charles, Latex looks much better now.2012-02-09
  • 0
    Excellent, this is exactly what I was hoping to see. Thank you!2012-02-10
  • 0
    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.2012-02-10
  • 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.2012-02-10
  • 0
    Nand is an equivalent replacement for And and Or in terms of sentence length. XOr and XNor would be slightly longer however.2012-02-10
  • 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.2012-02-12
  • 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."2012-02-13
  • 0
    @MikeC: Yes, we agree. I was responding to your "though I have no proof of that".2012-02-13