First Order Logic : Satisfiability of an amount of Formulas

67 Views Asked by At

Let's take Σ that contains an amount of formulas A, B...

We have that :

  1. Σ |= A exactly when Σ ∪ {¬A} unsatisfiable.

Does this mean that if Σ and A both satisfiable are, then Σ ∪ {A} satisfiable ? => I found this in a website, and i'm not sure if it's correct...

Cause what if ¬A is satisfiable and in Σ ...AND... A is also satisfiable ?

then Σ ∪ {A} is also satisfiable !? Which seems contradictory to (1) because we have :

Σ |= A and still Σ ∪ {¬A} is satisfiable

Thank you in advance, and i hope the question is clear.

1

There are 1 best solutions below

3
On BEST ANSWER

We have that :

  1. Σ |= A exactly when Σ ∪ {¬A} unsatisfiable.

Yes, that is correct.

Does this mean that if Σ and A both satisfiable are, then Σ ∪ {A} satisfiable ?

No, it means that if $A$ is true in all interpretations that satisfy $\Sigma$ then $\Sigma\cup\{\lnot A\}$ is unsatisfiable, and vice versa. (If this seems like I'm just spouting a tautology, good... the point is that when we write out what $\Sigma\models A$ means in natural language, it is readily apparent that it means the same thing as $"\Sigma\cup\{\lnot A\}$ is unsatisfiable.")

Cause what if ¬A is satisfiable and in Σ ...AND... A is also satisfiable ?

Yes, that would be a counterexample.

In a little more detail, let's say $A$ is a sentence is a sentence that is true in some interpretations and false in others and that $\Sigma=\{\lnot A\}.$ Then, $\Sigma$ and $A$ are both satisfiable, but clearly $\Sigma\cup \{\lnot A\} =\{A,\lnot A\}$ is not.

then Σ ∪ {A} is also satisfiable !? Which seems contradictory to (1) because we have : Σ |= A and still Σ ∪ {¬A} is satisfiable

Just because $\Sigma\cup\{A\}$ is satisfiable doesn't mean $\Sigma\models A,$ so I don't think this line of reasoning works. Still, like I said above, you're right that this situation does result in a contradiction.