Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
add comment

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
1  
Thanks Charles, Latex looks much better now. –  user474632 Feb 9 '12 at 22:28
    
Excellent, this is exactly what I was hoping to see. Thank you! –  Twisol Feb 10 '12 at 0:06
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 4:49
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. –  Henning Makholm 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 2:46
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.