If $\Gamma\cup\{\sim(A\land B)\}$ is consistent, what can be said about $\Gamma\cup\{\sim(A\lor B)\},\Gamma\cup\{\sim A\},\Gamma\cup\{\sim B\}$?

130 Views Asked by At

The following question arose in the NOI of India Section taken a few days back:

Let $\Gamma$ be a set of predicate formulas, and let $A, B$ be two predicate formulas; if the theory $\Gamma \cup \{ \sim (A \wedge B) \}$ is consistent, which of the following is true?

1) At most one of $\Gamma \cup \{ \sim (A \wedge B) \}$ or $\Gamma \cup \{ \sim (A \vee B) \}$ is consistent.

2) At least one of $\Gamma \cup \{ \sim A \}$ or $\Gamma \cup \{ \sim B \}$ is consistent.

Thanks to anyone...

1

There are 1 best solutions below

0
On BEST ANSWER

Let us look at this from a semantic viewpoint, without getting bogged down in the details of any specific formalism (also motivated by the fact that you didn't specify a formalism).

So we have a model $\mathcal M$ for $\Gamma$ that is also a model for $\neg(A \land B)$. That is, $A$ and $B$ are not both true in $\mathcal M$.

As to 1., since $\mathcal M$ already testifies the first of the two to be consistent, it can only be true if we can prove $\Gamma$ and $\neg(A \lor B)$ cannot be simultaneously satisfied. However, considering the case $A = B$, where $A \land B \equiv A \lor B$, we see that $\mathcal M$ may very well be a model for the second theory as well. Thus, 1. is false.

To prove 2., we have to find a model for $\Gamma$ and at least one of $\neg A$ and $\neg B$. But we already saw that $\mathcal M$ cannot model both of $A$ and $B$. So it must be a model of at least one of $\neg A$ and $\neg B$.

In conclusion, 1. is false while 2. is true.