# Translation of english sentences to first order logic in conjunctive normal form walkthrough?

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?

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!

• 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? Feb 20, 2017 at 0:13
• Also, could you add a short explanation why the body is in CNF even through it is the disjunction of 3 functions? Feb 20, 2017 at 0:24
• @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. Feb 20, 2017 at 0:31
• @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! Feb 20, 2017 at 0:34
• 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)? Feb 20, 2017 at 0:53