Propositional Logic by Resolution Problem

I'm lost on this example problem. My professor did not explain it very well and the book is no help either. Any help would be appreciated. Here goes:

For each of the following cases, you are given a set of prepositional logic statements that is true. Using resolution, determine which of the individual statement is true or not.

Example (A OR NOT B), (A OR NOT C), (C OR D), (A OR NOT D) – by resolution, you can show that A must be true (but nothing about B, C, D individually)

a. (A OR B OR C), (NOT A OR NOT B), (NOT C OR NOT D)

b. (NOT A OR B), (C OR NOT D), (NOT C OR NOT D), (A OR B OR D)

-
No answer yet.. so meanwhile, I will try to recall resolution. You have a set of statements $S$ (in specific format: clauses). Pick two statements at a time from $S.$ The two statements should be the form $a \lor \lnot b, c \lor \lnot b.$ Produce a new statement $a \lor c,$ where $b$ is eliminated. This step is called resolution step. Add the new statement to $S.$ Repeat until you can show the goal statement or can not resolve more. –  user2468 Mar 20 '12 at 23:56
@J.D. Shouldn't $b$ have different polarities in the two original clauses? –  Henning Makholm Mar 21 '12 at 2:19
@HenningMakholm Indeed. It's a mistake. Thanks. Penn, I meant resolve $a \lor b$ with $c \lor \lnot b$ to get $a \lor c.$ –  user2468 Mar 21 '12 at 3:05

2 Answers

I will use the standard symbols $\lor$ for OR and $\lnot$ for NOT. Let’s look first at the example. You have \begin{align*} &A\lor\lnot B\tag{1}\\ &A\lor\lnot C\tag{2}\\ &C\lor D\tag{3}\\ &A\lor\lnot D\tag{4}\;. \end{align*}

You can resolve two of these if one of them contains $X$ and the other $\lnot X$ for some $X$. Here that gives you two possibilities, $(2)$ and $(3)$, where you have $C$ in one and $\lnot C$ in the other, and $(3)$ and $(4)$, where you have $D$ in one and $\lnot D$ in the other. Resolving $(2)$ and $(3)$ gives you $A\lor D$; it contains $D$, and $(4)$ contains $\lnot D$, so you can resolve these two to get $A\lor A$, or simply $A$. This shows that $A$ must be true.

What if we’d resolved $(3)$ and $(4)$ to get $C\lor A$? We could then have resolved that with $(2)$, getting rid of the $C$’s, to get $A\lor A$ and therefore $A$, so we’d have ended up in the same place.

Now let’s look at Problem (a). You have

\begin{align*} &A\lor B\lor C\tag{5}\\ &\lnot A\lor\lnot B\tag{6}\\ &\lnot C\lor\lnot D\tag{7}\;. \end{align*}

The proposition letter $D$ appears only once, so there’s no hope of resolving it away. On the other hand, $(5)$ and $(6)$ look like very good candidates for resolution. Unfortunately, they’re too good in a sense: after we ‘resolve out’ $A$, we have $B\lor C\lor\lnot B$, which is a tautology: it’s always true, on account of the $B\lor\lnot B$. Resolving out $B$ also leads to a tautology. (This always happens when you have more than one complementary pair, like $A$ and $\lnot A$ or $B$ and $\lnot B$, in the two expressions.) A tautology doesn’t tell us anything about the truth of the individual propositions mentioned in it, so it’s useless to us here.

Since that didn’t get us very far, let’s resolve out $C$ in $(5)$ and $(7)$ instead, getting $A\lor B\lor\lnot D$. And that’s pretty much a dead end: we could resolve with $(6)$, but we’d just get another tautology, and no other resolutions are available. Thus, we conclude that none of $A,B,C$ and $D$ is necessarily true or false.

If in doubt, you can verify this by brute force. Is it possible for $A$ to be true? Yes: if $A$ is true, $B$ is false, and $C$ is false, $(5)-(7)$ are true no matter what $D$ is. If $A$ is false, $B$ is true, and $D$ is false, $(5)-(7)$ are true no matter what $C$ is. Thus, any of the four atomic propositions can be either true or false when $(5)-(7)$ are true.

Problem (b) is actually a bit easier; since this is homework, I’ll give you a chance to try it on your own first. You should be able to show that one of the atomic propositions $A,B,C$, and $D$ is definitely true and that one is definitely false.

-

I don't know what kind of notation your professor is using, but I will use

• $XY$ or $X\cdot Y$ for X AND Y,
• $X+Y$ for X OR Y, and
• $\overline{X}$ for NOT X.

In order of highest to lowest precedence: NOT, AND, OR. To find all boolean tuples $(A,B,C,\ldots)$ that satisfy a list of statements, AND all the statements together repeatedly distribute the ANDs over the ORs as if ANDs were multiplication and ORs were addition. Another useful law is that $X + XY = X$. You can find basically all the laws you will need here (they use $\wedge$, $\vee$, and $\neg$ for AND, OR, NOT).

a. $$(A + B + C) \cdot (\overline{A} + \overline{B}) \cdot (\overline{C} + \overline{D}) \\ = (A \overline{A} + A\overline{B} + B \overline{A} + B\overline{B} + C \overline{A} + C \overline{B})\cdot(\overline{C} + \overline{D}) \\ = (A \overline{ B} + \overline{A}B + \overline AC + \overline BC) \cdot (\overline{C} + \overline{D}) \\ =A\overline B\,\overline C + \overline AB\overline C + \overline AC\overline C + \overline B C\overline C + A\overline B\,\overline D + \overline A B \overline D + \overline AC\overline D + \overline BC \overline D\\ =A\overline B\,\overline C + \overline AB\overline C + A\overline B\,\overline D + \overline A B \overline D + \overline AC\overline D + \overline BC \overline D$$

Any of these final six cases could occur. It appears that none of $A$, $B$, $C$, $D$ must always be true or false.

b.

$$(\overline A + B)\cdot(C + \overline D) \cdot (\overline C + \overline D) \cdot (A+B+D)\\ = (\overline A + B)\cdot(C\overline D + \overline C\,\overline D + \overline D)\cdot (A+B+D) \\ = (\overline A + B)\cdot\overline D\cdot (A+B+D) \\ = (\overline A + B)\cdot(A\overline D + B\overline D) \\ = \overline A B \overline D + AB\overline D + B\overline D\\ = B\overline D \\$$

(I've skipped some details, do work them out.) So B must be true and D must be false.

-
Wrong answer (but I did not downvote). The given clauses are not ANDed together. OP is supposed to perform resolution as in here –  user2468 Mar 21 '12 at 16:09