Satisfiability in logic

Question

I'm working on an exercise where I've to prove that if:

is satisfiable, then formulas G are as well:

F and G are any formulas of any logic.

I've problems to understand, how I can prove it. As I know, to be called satisfiable there must exist a model and for the model itself all the formulas in H are true.

But how can I prove that all formulas are true - how can I prove it for all the formulas from $1$ to $n+1$?

I hope someone can help me!

Kind regards

Answer 1

Hint:

First use induction to show that:

$$(G_2\lor\neg F_1\lor F_2)\land\dots\land(G_n\lor\neg F_{n-1}\lor F_n)\\\Rightarrow\bigvee_{i=2}^nG_i\lor\neg F_1\lor F_n$$

So we also have $H$ implies $\bigvee_{i=2}^nG_i\lor\neg F_1\lor F_n$, use this to prove:

$$H\equiv H \land (G_1\lor\dots\lor G_{n+1})$$

Finally, if $G_1\lor\dots\lor G_{n+1}$ is not SAT, that $H$ is not SAT, which is a contradiction.

---

Answer:

Use Induction we want to prove that:

$$M(n):=(G_2\lor\neg F_1\lor F_2)\land\dots\land(G_n\lor\neg F_{n-1}\lor F_n)\\\Rightarrow\bigvee_{i=2}^nG_i\lor\neg F_1\lor F_n$$

Base case: $n=2$ \begin{align} M(2)&\equiv(G_2\lor\neg F_1\lor F_2)\\ &\equiv\bigvee_{i=2}^2G_i\lor\neg F_1\lor F_2 \end{align}

Inductive step:

Assume that for $n=k$:

\begin{align} M(k)&\equiv(G_2\lor\neg F_1\lor F_2)\land\dots\land(G_k\lor\neg F_{k-1}\lor F_k)\\ &\Rightarrow\bigvee_{i=2}^kG_i\lor\neg F_1\lor F_k \end{align}

Show it hold for $n=k+1$:

\begin{align} M(k+1)&\equiv(G_2\lor\neg F_1\lor F_2)\land\dots\land\color{blue}{(G_{k+1}\lor\neg F_{k}\lor F_{k+1})}\\ &\Rightarrow\bigvee_{i=2}^{k+1}G_i\lor\neg F_1\lor F_{k+1} \end{align}

Since $M(k+1)$ implies $M(k)$ so also implies $\bigvee_{i=2}^kG_k\lor\neg F_1\lor F_k$

Apply $((\bigvee_{i=1}^kP_i\lor R)\land(\bigvee_{i=1}^jQ_i\lor \neg R))\Rightarrow \bigvee_{i=1}^kP_i\lor \bigvee_{i=1}^jQ_i$ we have:

$(\bigvee_{i=2}^kG_k\lor\neg F_1\lor F_k)\land\color{blue}{(G_{k+1}\lor\neg F_{k}\lor F_{k+1})}$ impleis $\bigvee_{i=2}^{k+1}G_i\lor\neg F_1\lor F_{k+1}$

This proved the induction.

Since $H\Rightarrow M(n)$ that $H$ also implies $\bigvee_{i=2}^{n}G_i\lor\neg F_1\lor F_{n}$

Apply $((\bigvee_{i=1}^kP_i\lor R)\land(\bigvee_{i=1}^jQ_i\lor \neg R))\Rightarrow \bigvee_{i=1}^kP_i\lor \bigvee_{i=1}^jQ_i$ again:

Then we have $(\bigvee_{i=2}^{n}G_i\lor\neg F_1\lor F_{n})\land(G_1\lor F_1)\land(G_{n+1}\lor\neg F_n)$ implies: $G_1\lor\dots\lor G_{n+1}$

Hence we proved $H\equiv H\land(G_1\lor\dots\lor G_{n+1})$

Answer 2

HINT:

You cannot show that each one of the formulas $G_1$ through $G_{n+1}$ is satisfiable. Here is a quick counterexample to the claim that you could:

Let $n=1$, $F_1=A$, $G_1 = \bot$, and $G_2=B$

Then $(G_1 \lor F_1) \land (G_2 \lor \neg F_1)$, which would be $(\bot \lor A) \land (B \lor \neg A)$ is satisfiable (set $A=B=T$), but clearly $G_1$ by itself is not.

However, you are not being asked to show that each individual $G_i$ is satisfiable, but rather that the whole disjunction $G_1 \lor ... \lor G_{n+1}$ is satisfiable. Indeed, in the above example, we see that $G_1 \lor G_2$ is satisfiable.

So: now that you know what the real question is, give that another thought.

Another quick hint though: do you know the Resolution rule?