I know you can show that $X$ is a tautology when all branches of $\neg X$ close. But is it equivalent to prove that no branch of $X$ itself closes? Thanks in advance!
Asked
Active
Viewed 45 times
3
-
1If the tableau for $X$ does not close, this shows that $X$ is satisfiable. – Mauro ALLEGRANZA May 23 '17 at 21:19
1 Answers
3
No. Consider $X = P$, i.e. some atomic proposition. Then the tableau has no closed branches, but $X$ is not a tautology.
And by the way, it is also not true that if $X$ is a tautology, there will be no closed bracnhes.
Consider $X=(P \land \neg P) \lor (Q \lor \neg Q)$
$X$ is a tautology, but in the tableau for $X$, you get a branch with $P \land \neg P$ in one of the branches ... which will quickly close.
In sum, it is definitely not true that a statement is a tautology if and only if its tableau has no closed branches: you can have non-tautologies without an closed branches, and you can have a tautology that does have closed branches.
Bram28
- 100,612
- 6
- 70
- 118