How can i show set of literals are satisfiable?

121 Views Asked by At

I know that,

For any atom A, the literals A, ¬A are said to be complementary to each other.

A set of literals is satisfiable iff it does not contain complementary pairs.

A set Γ of formulas entails a formula F (symbolically, Γ |= F), if every interpretation that satisfies all formulas in Γ satisfies F also.

Note that the notation for entailment uses the same symbol as the notation for satisfaction introduced earlier, the difference being that the expression on the left is an interpretation (I) in one case and a set of formulas (Γ) in the other.

The formulas entailed by Γ are also called the logical consequences of Γ.

Let Γ be a set of literals. How can i show the, Γ is satisfiable iff there is no atom A for which both A and ¬A belong to Γ.

1

There are 1 best solutions below

1
On

That seems to immediately follows from the first two definitions:

Def.1: For any atom A, the literals A, ¬A are said to be complementary to each other.

Def. 2 A set of literals is satisfiable iff it does not contain complementary pairs.

Therefore, a set of literals is satisfiable iff it does not contain literals A and ¬A for some atom A.

I suppose one could argue that definition 1 is not exactly clear on what the necessary conditions are for two literals to be complimentary. That is: it says that A and ¬A are complimentary, but it does not say that there cannot be two other kinds of literals (e.g. P and ¬Q) that are complimentary. But, I can tell you that there are no such other pairs. So, to be clear, Definition 1 should really be:

Def.1': Two literals are complimentary iff they are of the form A and ¬A for some atom A

And now your conclusion is really just substituting Def. 1' into Def.2