Prove that the set of sentences $\{A \land (B \lor C), (\lnot C \lor H) \land (H \rightarrow \lnot H), \lnot B\}$ is inconsistent

Question

Prove that the set of sentences

$\left\{A \land (B \lor C), (¬C \lor H) \land (H \to \lnot H), \lnot B\right\}$ is inconsistent.

I'm confused because it doesn't look like any of the forms I've learned about?

Answer 1

To reiterate my assumptions: I assume we are trying to derive a contradiction from this set of sentences? i.e. inconsistent means that at least one of these sentences must be false.

From $A\wedge ( B \vee C)$, we have $B\vee C$. Since $\lnot B$, we have $C$ by disjunctive syllogism. Therefore since $(\lnot C \vee H)\wedge (H\implies \lnot H)$, we have $\lnot C \vee H$, but this is true $\iff (C\implies H)$, but then since we already derived $C$ from this set of sentences, we now have $H$. but $H\implies \lnot H$, so we can derive $\lnot H$. Contradiction.

Answer 2

Whenever we have one of these let's look at what we know assuming the system is consistent.

We know:

1. $\neg B$ and
2. $A\wedge (B\vee C)$ so using $\wedge$-elimination we know $(B\vee C)$

If $B$ were true then we would get a contradiction, namely $\neg B$ and $B$. So $C$ must be true. Using a similar process you can show $H$ must be true. Once you know this and rules about $\rightarrow$ with $H\rightarrow\neg H$, the result follows. Since no matter what we do, we get a contradiction.

The process in these is to strategically start breaking up everything. If you don't know where to start, just start proving as much information as you can about the problem. However, I should say that before doing this you should do some sanity checks for clear bugs like $p\wedge\neg p$ and look for potential weak spots like $p\rightarrow\neg p$.

Answer 3

We have the premises: $\Gamma=\{A∧(B∨C),(¬C∨H)∧(H→¬H),¬B\}$

Notice the second premise is a conjunction and the second half of that is: $H\to\neg H$. This will lead to a contradiction if $H$ is true.

Notice the first half of the conjunction: $\neg C\vee H$. $H$ will be true is $C$ is true. Put the conjunction together and we will have a contradiction if $C$ is shown to be true.

How might $C$ be true? Look at the first premise: either $B$ or $C$ is true. But the third premise says $B$ is false. So we're done.

Formally: $$\begin{align} \tag{P1} \Gamma & \vdash A∧(B∨C) \\ \tag{P2} \Gamma & \vdash (¬C∨H)∧(H→¬H) \\ \tag{P3} \Gamma & \vdash \neg B \\ \tag{1} A\wedge(B\vee C) &\vdash (B\vee C) \\ \tag{2} (B\vee C), \neg B &\vdash C \\ \tag{3} (\neg C\vee H)\wedge (H\to \neg H) &\vdash \neg C\vee H \\ \tag{4} (\neg C\vee H)\wedge (H\to \neg H) &\vdash H\to \neg H \\ \tag{5} C, \neg C\vee H &\vdash H \\ \tag{6} H, H\to\neg H &\vdash \neg H \\ \tag{7} H, \neg H &\vdash H\wedge \neg H \\ \tag{8} H\wedge \neg H &\vdash \bot \\ \hline \Gamma & \vdash \bot & \Box \end{align}$$