2
$\begingroup$

I am having a hard time on a homework problem which involves converting a given English sentence into first order logic and then converting that into Conjunctive Normal Form.

The sentences are (EDIT: Along with the entire problem statement)

Translate the following into First Order Logic and then convert to Conjunctive Normal Form (CNF):

According to the Pidgeon: If little girls eat eggs, then they are a kind of serpent. Alice (who is a little girl) eats eggs. Therefore, she is a kind of serpent.

I think I have done well so far below but I seem to be stuck trying to reduce the sentences any further, I am not sure what rule to apply from here.

Hypothesis where L(x) = LittleGirl(x), E(x) = EatEggs(x), S(x) = Serpent(x)

{[∀x ((L(x) ∧ E(x)) ⇒ S(x))] ∧ [L(Alice) ∧ E(Alice)]} ⇒ S(Alice)

Implication: [A ⇒ B ≡ ¬A ∨ B] Applied to: L and E

{[∀x (¬(L(x) ∧ E(x)) ∨ S(x))] ∧ [L(Alice) ∧ E(Alice)]} ⇒ S(Alice)

Implication: [A ⇒ B ≡ ¬A ∨ B] Applied to: Pidgeon's final implication

¬{[∀x (¬(L(x) ∧ E(x)) ∨ S(x))] ∧ [L(Alice) ∧ E(Alice)]} ∨ S(Alice)

Universal Instantiation: [∀x P(x) ⇒ P(a/x)] Applied to: The only occurance

¬{[(¬(L(a/x) ∧ E(a/x)) ∨ S(a/x))] ∧ [L(Alice) ∧ E(Alice)]} ∨ S(Alice)

DeMorgan's Law: [¬(A ∧ B) ≡ ¬A ∨ ¬B, ¬(A ∨ B) ≡ ¬A ∧ ¬B] Applied to: Statement in brackets

¬[(¬(L(a/x) ∧ E(a/x)) ∨ S(a/x))] ∨ ¬[L(Alice) ∧ E(Alice)] ∨ S(Alice)

DeMorgan's Law: [¬(A ∧ B) ≡ ¬A ∨ ¬B, ¬(A ∨ B) ≡ ¬A ∧ ¬B] Applied to: a/x statement

(¬¬(L(a/x) ∧ E(a/x)) ∧ ¬S(a/x)) ∨ ¬[L(Alice) ∧ E(Alice)] ∨ S(Alice)

DeMorgan's Law: [¬(A ∧ B) ≡ ¬A ∨ ¬B, ¬(A ∨ B) ≡ ¬A ∧ ¬B] Applied to: Middle statement

(¬¬(L(a/x) ∧ E(a/x)) ∧ ¬S(a/x)) ∨ ¬L(Alice) ∨ ¬E(Alice) ∨ S(Alice)

Double negation elimination: [¬¬A ≡ A] Applied to: Left statement

((L(a/x) ∧ E(a/x)) ∧ ¬S(a/x)) ∨ ¬L(Alice) ∨ ¬E(Alice) ∨ S(Alice)

Though after doing some reading I think that I might have done this wrong. After reviewing this webpage describing Universal Instantiation I feel like I could apply its example problem directly to mine. I could have initially applied Universal Instantiation and then Modus ponens to have simply ended with Serpent(Alice) which is in CNF. But this feels like I am "cheating" the problem, or is this most likely the solution the professor seeks for the question?

Am I on the right track above or should I try applying the example from the website to my problem? If I am on the right track what rule might I apply next (specifically to the top statement) to continue?

|cite|improve this question
$\endgroup$
1
$\begingroup$

One immediate problem I see is that hou have three sentences (making up 1 argument), but you treat this as 1 sentence. Instead, you should put each of the three sentences in CNF by themselves.

Second, you say to put the sentences in CNF, but the first sentence involves a quantifier. Does this mean that you just have to put the body in CNF and leave the quantifier? Or are you doing the preprocessing to use resolution? I get the feeling you are ...

Anyway, let's take that first sentence, and do some algebraic manipulation:

$\forall x ((L(x) \land E(x)) \rightarrow S(x)) \Leftrightarrow$ (Implication)

$\forall x (\neg (L(x) \land E(x)) \lor S(x)) \Leftrightarrow$ (DeMorgan)

$\forall x (\neg L(x) \lor \neg E(x) \lor S(x))$

And now the body is in CNF. If you have to get rid of the unatifier in preparation of resolution, you just drop it and get:

$\neg L(x) \lor \neg E(x) \lor S(x)$

The second statement is already in CNF:

$L(a) \land E(a)$

And again , assuming you are setting this up for resolution (which is a consistency checking method), you should negate the conclusion ... Which is also in CNF:

$\neg S(a)$

This gives you 4 clauses:

  1. $\{ \neg L(x) , \neg E(x) , S(x) \}$

  2. $\{ L(a) \}$

  3. $\{ E(a) \}$

  4. $\{ \neg S(a)\}$

And now we ca resolve:

  1. $\{ \neg E(a), S(a) \}$ 1,2

  2. $\{ S(a) \}$ 3,5

  3. $\{ \}$ 4,6

Contradition, so the original argument is valid!

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I have posted the entire problem statement, there is not need for resolution only to "put [the sentences] into CNF". // Though I feel like its "cheating"/not in the spirit of the problem to not link the three English sentences into one logical sentence? $\endgroup$ – KDecker Feb 20 '17 at 0:13
  • $\begingroup$ Also, could you add a short explanation why the body is in CNF even through it is the disjunction of 3 functions? $\endgroup$ – KDecker Feb 20 '17 at 0:24
  • $\begingroup$ @KDecker I really don't think it is cheating to not link the 3 sentences together, because the passage contains 3 sentences, not 1. There is 1 argument, but an argument is not a sentence. Indeed, an 'if... Then' sentence is really quite different from a '.. Therefore ...' argument. $\endgroup$ – Bram28 Feb 20 '17 at 0:31
  • $\begingroup$ @KDecker Any disjunction of literals is in CNF. That feels weird, but it is true. A claim is in CNF when it is a general conjunction of disjunctions of literals. A claim like $A \lor B$ Is in CNF because it is a single conjunct, which is a disjunction of literals! $\endgroup$ – Bram28 Feb 20 '17 at 0:34
  • $\begingroup$ When reading the Wikipedia for CNF I saw A∨B was in CNF so I had assumed A∨B∨C would also be. But yes that is quite odd. Do you mean anything special by "general conjunction" or just conjunction? // As for using 3 or 1 statements, could I come to 1 statement at the end by and'ing all three statements together (which would be in CNF?) (¬L(x) ∨ ¬E(x) ∨ S(x)) ∧ (L(Alice) ∧ E(Alice)) ∧ S(Alice)? $\endgroup$ – KDecker Feb 20 '17 at 0:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.