Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Given the sentences, S1, S2, if S1 |= S2 then all models that satisfy S1 also satisfy S2, how is the following statement correct?
A ∧ ¬A |= B
How can something and not something equate to true?
I am stuck trying to work out how true and false can still entail true, actually how can A and ¬A occur at the same time?
Thanks.
It's not easy to give a full explanation without knowing your axioms and rules, however, $A \land \neg A$ is a contradiction, and it is by exploiting that, that you can prove whatever you like.
First, let $\top = A \lor \neg A$.
We know that "true or whatever else" must be true. Since $\top$ is a tautology, then $\top \lor B$ must be true.
But since $A \land \neg A = \neg (A \lor \neg A) = \neg \top$ is assumed to be true we conclude the following:
It all hinges on the fact that $A \lor \neg A$ is a tautology and that you assume that the negation of a tautology is true.
So to answer your question "actually how can $A$ and $\neg A$ occur at the same time?" It cannot, unless you have a contradiction. When you assume a contradiction, you can prove anything.
Think of it this way.
There are no elements of the empty set $\emptyset$. Moreover, for all sets $A$, $\emptyset \subseteq A$.
But what does subset actually mean? $A \subseteq B$ means that any element of $A$ must be an element of $B$. That is, $\forall x \in A, x \in B$.
It follows that for all sets $A$, $\forall x \in \emptyset, x \in A$. Every single element of $\emptyset$, every one of them, every none of them, is an element of every other set.
Assuming that $A \wedge \neg A$ is false in your logic (there are logics that admit controlled contradiction), then there are no models satisfy $S_1$. It follows that all models that satisfy $S_1$, every one of them, every none of them, also satisfy $S_2$.
