Relation between an unsatisfiable set and a tautology

Question

In mathematical logic, satisfiability and validity are elementary concepts of semantics. A formula is satisfiable if it is possible to find an interpretation (model) that makes the formula true. A formula is valid if all interpretations make the formula true. The opposites of these concepts are unsatisfiability and invalidity, that is, a formula is unsatisfiable if none of the interpretations make the formula true, and invalid if some such interpretation makes the formula false.

I read some Midterm exam on logic for computation course. I read this fact on my tutorial note. But I think it's false.

if set of {$\varphi_1,\varphi_2,...,\varphi_m$} is not satisfiable, then formulate $\neg\varphi_1 \wedge \neg\varphi_2 \wedge ...\wedge \neg\varphi_m$ is a TAUTOLOGY.

I think it's False, but in my lecture note is written True. I think it's false. Any hint and tutorial would be highly appreciated.

One of the possible corrections is : if the set of formulae ${ φ1,φ_2,\ldots,φ_m }$ is not satisfiable, then the formula $(φ_1 ∧ φ_2 ∧ \ldots∧φ{m-1}) \rightarrow ¬φ_m$ is a TAUTOLOGY. — Mauro ALLEGRANZA, Jul 28 '14 at 06:48

score 3 · Accepted Answer · answered Jul 28 '14 at 02:51

3

It is not true. What is true is that $\lnot \varphi_1 \lor \lnot \varphi_2 \lor \cdots \lor \lnot \varphi_m$ is a tautology.

To see that the sentence with the $\land$ is not necessarily a tautology, let $m=2$, let $\varphi_1=\varphi$ and $\varphi_2=\lnot\varphi$.

answered Jul 28 '14 at 02:51

André Nicolas

507,029

Dear @Andre, can you mentioned 1 counterexample? – Jul 28 '14 at 02:54
1

basically anything you try would be a counterexample – John Fernley Jul 28 '14 at 02:55
I added a counterexample. As mentioned by John Fernley, they are easy to com by. – André Nicolas Jul 28 '14 at 02:56
you're very welcome @MokholiaPokholia – John Fernley Jul 28 '14 at 02:58

Relation between an unsatisfiable set and a tautology

1 Answers1