Question

First Order Logic

We would like to find out more information about a very shady organization called the Society of Americans for Nepotism. We already know the following facts about this organization:

1. sally and ellen are members.

2. ellen is related to bill.

3. Anyone related to a member is also a member.

4. Being related is symmetric (i.e., if X is related to Y, then Y is related to X)

5. bob is not a member.

a. Represent these facts as sentences in first-order predicate calculus (you can use ~ as the negation symbol).

b. Translate your sentences into Conjunctive Normal Form and then into clause form (show your work).

c. Use resolution-refutation to prove that Bill is a member of the organization. At each step show the current sub-goal, the clause from the knowledge-based being applied, and the resolvent. Also show any substitutions being applied

Answer 1

Let M(x) indicate that x is a member.

Let E(x,y) indicate that x is equal to y.

Let R(x,y) indicate that x and y are related.

a. Now let us translate each of the sentences one by one into first order logic.

"sally and ellen are members" will be translated as

$\forall x \hspace{1cm} E(x, sally) \vee E(x, ellen) \rightarrow M(x)$

"ellen is related to bill" will be translated as

$\forall x,y \hspace{1cm} E(x, ellen) \vee E(y, bill) \rightarrow R(x,y)$

"Anyone related to a member is also a member" will be translated as

$\forall x,y \hspace{1cm} R(x,y) \wedge M(x) \to M(y)$

"Being related is symmetric " will be translated as

$\forall x,y \hspace{1cm} R(x,y) \to R(y,x)$

"bob is not a member" will be translated as

VE Ez, bob) → MC

b. Now lets translate each of them into CNF clause where each elements are connected by $\vee$ connective. Note that $A \to B$ is equivalent to $\neg A \vee B$ . And $A \wedge B$ is equivalent to .

AV B

$\forall x \hspace{1cm} E(x, sally) \vee E(x, ellen) \rightarrow M(x)$ will be equivalent to

$\forall x \hspace{1cm} \neg (E(x, sally) \vee E(x, ellen)) \vee M(x)$

$\forall x,y \hspace{1cm} E(x, ellen) \vee E(y, bill) \rightarrow R(x,y)$ will be equivalent to

$\forall x,y \hspace{1cm} \neg (E(x, ellen) \vee E(y, bill)) \vee R(x,y)$

$\forall x,y \hspace{1cm} R(x,y) \wedge M(x) \to M(y)$ will be equivalent to $\forall x,y \hspace{1cm} \neg R(x,y) \vee \neg M(x) \vee M(y)$

$\forall x,y \hspace{1cm} R(x,y) \to R(y,x)$ will be equivalent to $\forall x,y \hspace{1cm} \neg R(x,y) \vee R(y,x)$

VE Ez, bob) → MC
will be equivalent to $\forall x \hspace{1cm} \neg E(x,bob) \vee \neg M(x)$

(c) Using resolution-refutation, we have to first connect all the clauses in CNF form by $\wedge$ connective.

Hence the combined statement will be

$\forall x \forall y\hspace{1cm} (\neg (E(x, sally) \vee E(x, ellen)) \vee M(x))$  $\wedge$

$\hspace{1cm} (\neg (E(x, ellen) \vee E(y, bill)) \vee R(x,y))$$\wedge$

$( \neg R(x,y) \vee \neg M(x) \vee M(y))$$\wedge$

$( \neg R(x,y) \vee R(y,x))$$\wedge$

$( \neg E(x,bob) \vee \neg M(x))$

Now to prove that Bill is the member of this organization, we need to prove that substituting E(x, Bill) to true and M(x) to be False at the same time will not lead to any satisfying assignment of the set of all clauses connected with $\wedge$ .

Since the clause $\hspace{1cm} (\neg (E(x, ellen) \vee E(y, bill)) \vee R(x,y))$ will be true if and only if Ellen and Bill are related and $( \neg R(x,y) \vee \neg M(x) \vee M(y))$ will be true if and only if both x and y are either member of organization or not member of orgianization. And clause $(\neg (E(x, sally) \vee E(x, ellen)) \vee M(x))$ will be true if and only if Sally and Ellen are member of organization. Now since Bill is related to Ellen and Ellen is member of origanization, hence if Bill is not member of organization then all of these clauses cannot be satisfied simultanously. Hence Bill must be the member of organization.

Please comment for any clarification