Formulas of propositional logic, two sets and refutation.

35 Views Asked by At

Let $\alpha$ and $\beta$ be two formulas of propositional logic and set $S_\alpha$ and $S_\beta$ be the sets of clauses representing $\neg \alpha$ and $\neg \beta$, respectively. Show that if $S_\alpha \subseteq S_\beta$ and $S_\alpha$ has a refutation, then $\beta$ must be a tautology.

1

There are 1 best solutions below

0
On BEST ANSWER

If $S_a$ has a refutation, this means that it is unsatisfiable.

Thus also the set $S_b$ (which includes $S_a$) is unsatisfiable.

But $S_b$ represents $\lnot \beta$ and thus $\lnot \beta$ is unsatisfiable.

Finally, a formula $\phi$ is a tautology iff its negation: $\lnot \phi$ is unsatisfiable.