Prove every Propositional logic statement with at most one instance of a variable is satisfiable

Question

I'm having some trouble proving a simple statement about plain propositional logic. I hope one of you can help me with his or her ideas?

This is the task: Suppose a propositional formula $H$. There is not more than one propositional variable of each kind in $H$ (e.g. $ \alpha \land \beta $ but not: $\alpha \land \lnot\alpha$). Now i have to show that $H$ is satisfiable or in other words: that $H$ is no contradiction. How do i prove this? These are my ideas so far: Suppose that H is an atomic formula in the first step, so $H\equiv\alpha$. It is clear that H is satisfiable in this case, because there is an assignment $v(\alpha)$ which makes H true. So far so good. But now comes the part where it gets tricky, at least for me. I think that one has to proceed like this: Suppose a formula $H_1$ and a formula $H_2$. Suppose further that both $H_1$ and $H_2$ are satisfiable formulas, then i have to proof the following cases to complete the proof:

• If $H_1$ is satisfiable, then also $\lnot H_1$.
• If $H_1$ and $H_2$ are satisfiable, then also $H_1 \land H_2$
• If $H_1$ and $H_2$ are satisfiable, then also $H_1 \lor H_2$
• ... and so on for the conditional and the biconditional.

If i am correct up to this point: How can i proof each specific case? I'm a bit lost right now.

Answer 1

You're on the right track!

In fact, what you are doing is a proof by structural induction: an inductive proof that exploits the recursive nature of how statements in propositional logic are put together.

Now, as Mauro points out, you have a little issue with the negation once you get to the step: just because $H$ is satisfiable does not mean that $\neg H$ is satisfiable, for if $H$ is a tautology, then $H$ is satisfiable, but $\neg H$ is not.

However, to solve this problem, you should prove the stronger claim that every propositional logic statement with at most one instance of any variable is both satisfiable and falsifiable, i.e. that the statement can be set to true and that the statement can be set to false.

So yes, as the base case you show that the now stronger claim is true for any atomic statement, but that is still trivial: any atomic statement is both satisfiable and falsifiable.

And then you indeed consider any complex logic statement, using the inductive hypothesis that the claim holds for its component statements. Let me just do one of the cases for you, and you'll see how to do this in general:

Suppose the statement $H$ is a conditional $H_1 \rightarrow H_2$.

The inductive hypothesis is that both $H_1$ and $H_2$ are satisfiable as well as falsifiable. That is, there is a valuation $v_1$ such that $v_1(H_1)=True$, a valuation $v_2$ such that $v_2(H_1)=False$, a valuation $v_3$ such that $v_3(H_2)=True$, and a valuation $v_4$ such that $v_4(H_2)=False$.

Now, since $H_1$ and $H_2$ cannot share any instances of the same variable, we can combine $v_1$ and $v_3$ into a single valuation $v_5$ that sets the atomic statements to the same values as $v_1$ and $v_3$ do, and as such we have that $v_5(H_1)=True$ and $v_5(H_2)=True$. But that means that $v_5(H_1 \rightarrow H_2)= True$, and hence $H$ is satisfiable.

Likewise, we can combine $v_1$ and $v_4$ into a valuation $v_6$, and as such $v_6(H_1)=True$ and $v_6(H_2)=False$. Hence, $v_6(H_1 \rightarrow H_2)= False$, and hence $H$ is also falsifiable.

You should be able to do all other cases (connectives) similarly.

Finally, point out that the claim just proven trivially implies the claim you try to prove.

Answer 2

Thanks Mauro and Bram28. Let's see if i can finish the proof now. This is my proposal, based on your comments and answers:

The base step, as already pointed out, is to show that every formula $H$ which is an atomic formula is both satisfiable and falsifiable. So, for the case that $H \equiv \alpha$, there is a valuation $v_1(\alpha) = True $ and a valuation $v_2(\alpha) = False$. This trivially implies that $H$ is satisfiable and falsifiable in the case that $H \equiv \alpha$.

Now let's go through the different cases.

• Negation It is to be shown that if $H$ is both satisfiable and falsifiable then the same holds for $\neg H$. This can be seen for the two valuations $v_1(H)=True$ and $v_2(H)=False$. If both valuations are applied to $\neg H$ it follows (qua definition of the negation operator) that $v_1(\neg H)=False$ and $v_2(\neg H)=True$. Thus, if $H_1$ is both satisfiable and falsifiable then the same holds for $\neg H_1$.
• Conjunction It is to be shown that if $H_1$ and $H_2$ respectively are both satisfiable and falsifiable then the same holds for $H_1 \land H_2$. This can be seen via the four valuations $v_1(H_1)=True$, $v_2(H_1)=False$, $v_3(H_2)=True$ and $v_4(H_2)=False$. Now one can set up a fifth valuation: $v_5=v_1 \cup v_2$. Qua definition of the conjunction operator, it follows that $v_5(H_1 \land H_2)=True$, while all other combinations of the valuations $v_1$-$v_4$ are false. Thus, if $H_1$ and $H_2$ respectively are both satisfiable and falsifiable then the same holds for $H_1 \land H_2$.
• Disjunction It is to be shown that if $H_1$ and $H_2$ respectively are both satisfiable and falsifiable then the same holds for $H_1 \lor H_2$. Once again, we have four valuations $v_1(H_1)=True$, $v_2(H_1)=False$, $v_3(H_2)=True$ and $v_4(H_2)=False$. Now one can set up a fifth valuation $v_5=v_2 \cup v_4$. Qua definition of the conjunction operator, it follows that $v_5(H_1 \land H_2)=False$, while all other combinations of the valuations $v_1$-$v_4$ are true. Thus, if $H_1$ and $H_2$ respectively are both satisfiable and falsifiable then the same holds for $H_1 \lor H_2$.
• Implication It is to be shown, once more that if $H_1$ and $H_2$ respectively are both satisfiable and falsifiable then the same holds for $H_1 \rightarrow H_2$. Once again, we have four valuations $v_1(H_1)=True$, $v_2(H_1)=False$, $v_3(H_2)=True$ and $v_4(H_2)=False$. Suppose a fifth valuation $v_5=v_1 \cup v_4$, then - qua definition of the implication operator - $v_5(H_1 \rightarrow H_2)=False$ while all other combinations of $v_1$-$v_4$ are true. Thus, if $H_1$ and $H_2$ respectively are both satisfiable and falsifiable then the same holds for $H_1 \rightarrow H_2$.

I will leave out the induction step for the biconditional here.

Finally, for each formula $H$ which does not contain more than one variable of each kind, it follows that $H$ is both satisfiable and falsifiable. Ergo, any formula $H$ which fulfills this condition is necessarily neither a tautology nor a contradiction. ■