Info

Solution

You can solve these in various ways. Here I provide some different styles of solutions.

a)

We do this with a truth-table, which goes through all possible values:

b)

Also here, truth-tables is a good method:

c)

Here we can give a rather simple argument:

$\nu(A)$ is either 0 or 1. If $\nu(A)=0$, then $\nu(\neg A)=1$. But then $v(\neg A\to A)=1\Rightarrow 0=0$. If, instead, $\nu(A)=1$, then $\nu(\neg A)=0$ and so $\nu(\neg A\to A)=0\Rightarrow \nu(A)=1$.

d)

We do a truth-table:

e)

Here we can give a more sophisticated argument:

The only way in which we can have $\nu(A\to(B\to C))=0$ is if $\nu(A)=1$, $\nu(B\to C)=0$. The latter can only be if $\nu(B)=1$ and $\nu(C)=0$. But then, $\nu(A\land B)=1$ and $\nu(C)=0$ and so $\nu((A\land B)\to C)=\nu(A\land B)\Rightarrow \nu(C)=1\Rightarrow 0=0$.

Similarly, the only way in which $\nu((A\land B)\to C)=0$ is if $\nu(A\land B)=1$ and $\nu(C)=0$. But then $\nu(A)=1$ and $\nu(B)=1$, since $\nu(A\land B)=\nu(A)\times\nu(B)=1$. But then $\nu(B\to C)=0$ since $\nu(B\to C)=\nu(B)\Rightarrow\nu(C)=1\Rightarrow 0$ and so $\nu(A\to (B\to C)=\nu(A)\Rightarrow \nu(B\to C)=1\Rightarrow 0=0$.

So the two formulas are false in the exact same cases, which means in all other cases they must both be true.

Alternatively, you can do an 8-row truth-table:

Solution

a)

$$x\Rightarrow y=-x+y.$$

b)

$$x\Rightarrow y=-(x\times -y)$$

c)

$$x=-x\Rightarrow x$$

d)

$$x\Rightarrow y=-y\Rightarrow -x$$

e)

$$x\Rightarrow(y\Rightarrow z)=(x\times y)\Rightarrow z$$

Solution

There are many different options, we sample to show the variety:

a)

$\mathsf{RAIN}\to \mathsf{CAR}\vDash (\mathsf{RAIN}\land \mathsf{WARM})\to \mathsf{CAR}$

Here we use a semantic argument: Suppose that $\nu(\mathsf{RAIN}\to\mathsf{CAR})=1$. The only way in which $\nu((\mathsf{RAIN}\land \mathsf{WARM})\to \mathsf{CAR})=0$ is if $\nu(\mathsf{RAIN}\land \mathsf{WARM})=1$ and $\nu(\mathsf{CAR})=0$. But if $\nu(\mathsf{RAIN}\land \mathsf{WARM})=1$, then $\nu(\mathsf{RAIN})=1$. Since $\nu(\mathsf{RAIN}\to\mathsf{CAR})=1$, this means that $\mathsf{CAR}=1$ (since otherwise $\nu(\mathsf{RAIN}\to\mathsf{CAR})=0$). So, for $\nu((\mathsf{RAIN}\land \mathsf{WARM})\to \mathsf{CAR})=0$ we have to both have $\nu(\mathsf{CAR})=1$ and $\nu(\mathsf{CAR})=0$, which is impossible. Consequently, $\nu((\mathsf{RAIN}\land \mathsf{WARM})\to \mathsf{CAR})=0$ is impossible if $\nu(\mathsf{RAIN}\to\mathsf{CAR})=1$.

This means the inference is valid.

b)

Let’s do a big truthtable:

Since the relevant conditional is a logical truth, the inference is valid.

c)

This inference is _in_valid. We can see this, for example, using a truth-table:

As you can see, if you set $\nu(\mathsf{CAR})=1$ and $\nu(\mathsf{RAIN})=0$, we have both premises true, but the conclusion false.

d)

Also here a truth-table gives a quick answer:

We see that if we set $\mathsf{BIKE}=1$ and $\mathsf{SUN}=0$, the premises are true and the conclusion false.

Solution

a)

Pick an arbitrary Horn clause.

$$\neg p_1\lor\ldots\lor\neg p_n\lor q$$

This is the boolean algebra truth-conditions:

$$- p_1 + \ldots + - p_n+q$$

By DeMorgan principles this is equivalent to:

$$-(p_1 \times \ldots \times p_n)+q$$

By conditional laws (from exercise 2) we get:

$$(p_1 \times \ldots \times p_n)\Rightarrow q$$

Which is the truth-condition of the following formula:

$$(p_1 \land \ldots \land p_n)\rightarrow q$$

b)

No. Example: $p\land q$ does not have an equivalent Horn form.

Consider an arbitrary Horn clause $\neg r_1\lor\neg r_2\lor\ldots\lor s$. Call it $A$. Since $A$ has at most one positive part $s$ by definition, the following thing must happen in all valuations: $\nu(A)=1$ if and only if $\nu(r_i)=0$ for one of its negative parts or $\nu(s)=1$ for its positive part. This gives us a general idea of the format of truth-conditions for any Horn clause.

Now, pick a Horn clause $B$ that involves the literals $p$ and $q$ as parts. Could this be equivalent to the conjunction $p\land q$? We will show that it cannot be. There are only three possibilities for the shape of this Horn clause:

1. $p$ is a positive part of $B$
2. $q$ is a positive part of $B$
3. neither $p$ nor $q$ is positive in $B$

In situation 1. the literal $q$ must be a negative part of $B$, so whenever $\nu(B)=1$, then $\nu(q)=0$. Obviously that means $B$ is not equivalent to $p\land q$. In situation 2. the literal $p$ must be negative in $B$, so whenever $\nu(B)=1$, then $\nu(p)=0$. Obviously that means $B$ is not equivalent to $p\land q$. In situation 3. both $p$ and $q$ would be negative parts of $B$ so we get an even worse result.

Solution

a)

We want to show that this is valid:

$$l_1\lor l_2\lor\ldots\lor p ,; \neg p\lor k_1\lor k_2\lor\ldots \vDash l_1\lor l_2\lor\ldots\lor k_1\lor k_2\lor\ldots $$

To do this, we will think about the premises combined with the negation of the conclusion. This is what the negation of the conclusion looks like.

$\neg(l_1\lor l_2\lor\ldots\lor k_1\lor k_2\lor\ldots)$

Convert the negated conclusion into CNF.

$\neg l_1\land\neg l_2\land\ldots\land\neg k_1\land\neg k_2\land\ldots$

Together with the premises, this gives us a set of conditions.

$\Set{ \Set{l_1, l_2,\ldots p },\Set{\neg p, k_1, k_2,\ldots },\Set{\neg l_1 }, \Set{\neg l_2 }, \ldots, \Set{\neg k_1 }, \Set{\neg k_2 }, \ldots, $

By unit propogation on $\neg l_1$ we get:

$\Set{ \Set{ l_2,\ldots p },\Set{ \neg p, k_1, k_2,\ldots },\Set{ \neg l_2 }, \ldots, \Set{ \neg k_1 }, \Set{ \neg k_2 }, \ldots, }$

Continue unit propogation with each $\neg l_i$ to get:

$\Set{ \Set{ p }, \Set{ \neg p, k_1, k_2,\ldots }, \Set{ \neg k_1 }, \Set{ \neg k_2 }, \ldots, }$

By unit propogation on $\neg k_1$ we get:

$\Set{ \Set{ p }, \Set{ \neg p, k_2,\ldots }, \Set{ \neg k_2 }, \ldots, }$

Continue unit propogation with each $\neg k_j$ to get:

$\Set{ \Set{ p }, \Set{ \neg p } }$

A final step of unit propogation on $p$ shows us that the set is unsatisfiable.

$\Set{ \Set{ } }$

This means that it is impossible to make the premises and negation of the conclusion true. Which means that the inference is valid.

b)

This inference, called the Disjunctive Syllogism (DS), is just an application of the Resolution Rule. We just showed in part (a) that the Resolution Rule always leads to valid reasoning. So this gives us a new way to see why DS is valid. The reasoning we use for resolution is just like the Splitting rule of the DPLL algorithm.

c)

We take the premises combined with the negation of the conclusion and convert into a single CNF formula:

$\mathsf{RAIN}\land(\neg\mathsf{RAIN}\lor\neg\mathsf{RAIN})\land(\neg\mathsf{RAIN}\lor\neg\mathsf{SUN})$

So we have this set of conditions.

$\Set{ \Set{ \mathsf{RAIN} }, \Set{ \neg\mathsf{RAIN},\neg\mathsf{RAIN} }, \Set{ \neg\mathsf{RAIN},\neg\mathsf{SUN} } }$

Equivalent to this set of conditions.

$\Set{ \Set{ \mathsf{RAIN} }, \Set{ \neg\mathsf{RAIN} }, \Set{ \neg\mathsf{RAIN},\neg\mathsf{SUN} } }$

By applying the Resolution Rule on the first two clauses we get:

$\Set{ \Set{ }, \Set{ \neg\mathsf{RAIN},\neg\mathsf{SUN} } }$

Since there is an empty set, this shows that the inference is valid.

d)

The only time we can apply the Resolution Rule to two Horn clauses is when the same literal occurs as a positive part in one Horn clause and a negative part in the other Horn clause. Like the literal $q$ in these two formulas:

$$\neg p_1\lor\ldots\lor\neg p_n\lor q$$

$$\neg q\lor\neg r_1\lor\ldots\lor\neg r_m\lor s$$

When we apply the Resolution Rule we get this:

$$\neg p_1\lor\ldots\lor\neg p_n\lor\neg r_1\lor\ldots\lor\neg r_m\lor s$$

Since the original two formulas had only one positive part, and the positive $q$ was eliminated by Resolution, this means that the final formula also has only one positive part. Which means that it still qualifies as a Horn clause.

e) We take the premises combined with the negation of the conclusion and convert into a single CNF formula:

$(\neg\mathsf{RAIN}\lor\mathsf{CAR})\land(\neg\mathsf{CAR}\lor\mathsf{KEYS})\land\mathsf{RAIN}\land\neg\mathsf{KEYS}$

So we have this set of conditions.

$\Set{ \Set{ \neg\mathsf{RAIN},\mathsf{CAR} }, \Set{ \neg\mathsf{CAR},\mathsf{KEYS} }, \Set{ \mathsf{RAIN} }, \Set{ \neg\mathsf{KEYS} } }$

Apply the Resolution Rule on $\mathsf{RAIN}$.

$\Set{ \Set{ \mathsf{CAR} }, \Set{ \neg\mathsf{CAR},\mathsf{KEYS} }, \Set{ \neg\mathsf{KEYS} } }$

Apply the Resolution Rule on $\mathsf{CAR}$.

$\Set{ \Set{ \mathsf{KEYS} }, \Set{ \neg\mathsf{KEYS} } }$

Apply the Resolution Rule on $\mathsf{KEYS}$.

$\Set{ \Set{ } }$

Since there is an empty set, this shows that the inference is valid.

f)

If we have two simply Horn clauses that are eligible for Resolution, they look like this.

$$\neg p_1\lor\ldots\lor\neg p_n\lor q$$

$$\neg q\lor\neg r_1\lor\ldots\lor\neg r_m\lor s$$

These are equivalent to:

$$(p_1\land\ldots\land p_n)\rightarrow q$$

$$q\rightarrow((r_1\ldots\land r_m)\rightarrow s)$$

Generalizing from exercise (5e) we can see how these premises validly imply the formula below, by using the Resolution rule.

$$(p_1\land\ldots\land p_n)\rightarrow((r_1\ldots\land r_m)\rightarrow s)$$

Notice this is just an instance of Transitivity, but the result that it gives us is equivalent to the formula we reached in exericse (5d).

$$\neg p_1\lor\ldots\lor\neg p_n\lor\neg r_1\lor\ldots\lor\neg r_m\lor s$$