Transcription of 6.825 Exercise Solutions: Week 3
1 Exercise Solutions: Week 3 SolutionsSeptember 27, 2004 Converting to CNFC onvert the following sentences to conjunctive normal (A B) CAnswer: ( A B) C(A B) C(A C) ( B C) (B C)Answer: A B C3. (A B) (B A)Answer:( A B) ( B A)T rue4. ( P (P Q))Answer: P ( P Q)P P QT rue5. (P (Q R)) (P (R Q))Answer: ( P Q R) ( P R Q)(P Q R) ( P R Q)(P P R Q) (Q P R Q) ( R P R Q) P Q R6. (P Q) ((Q R) (P R))Answer: ( P Q) ( ( Q R) ( P R))(P Q) ((Q R) ( P R))(P Q) ((Q P R) ( R P R))(P Q) Q P R(P P Q R) ( P Q Q R)T rue1 First Order Logic SentencesFor each of the following English sentences, write a corresponding sentence in The only good extraterrestrial is a drunk extraterrestrial. (x) Good(x) Drunk(x)2. The Barber of Seville shaves all men who do not shave themselves. x. Shaves(x, x) Shaves(BarberOf Seville, x)3. There are at least two mountains in England.
2 X, ountain(x) M ountain(y) InEngland(x) InEngland(y) x6=y4. There is exactly one coin in the box. (x) InBox(x) y.(Coin(y) InBox(y) x=y)5. There are exactly two coins in the box. x, (x) InBox(x) Coin(y) InBox(y) x6=y z.(Coin(z) InBox(z) (x=z y=z))6. The largest coin in the box is a quarter. (x) InBox(x) Quarter(x) y.(Coin(y) InBox(y) Quarter(y) Smaller(y, x))7. No mountain is higher than itself. ountain(x) Higher(x, x)8. All students get good grades if they study. (x) Study(x) GetGoodGrade(x)FOL Interpretations, Part 1 For each group of sentences, write an interpretation under which the last sentence is false and all the rest (x) g(x) (x) g(x) (x) h(x)An interpretation that makes the first two sentences true and the third false:U={A, B}I(f) ={A}I(g) ={A, B}I(h) ={B}2. x. (x, y) y. (x, y)An interpretation that makes the first sentence true and the second sentence false:U={A, B, C}I(f) ={< A, B >, < B, C >, < C, A >}3.
3 X.(f(x) g(A))( (x)) g(A)There is no interpretation that makes the first sentence true and the second sentence : For the second sentence to be false, (x) has to betrue,andg(A) has to befalse. With thesetwo requirements, we can see that the first sentence cannot be true becausef(x) is true for x, andg(A)is , if we replace xwith x, x.(f(x) g(A))( (x)) g(A)Then the following interpretation makes the first sentence true and the second sentence {A, B}f={B}g={B}FOL Interpretations, Part 2 For each group of sentences, give an interpretation in which all sentences are ( (x) q(x)) (x) (x) q(x) (x) q(x)Interpretation:U={A, B}I(p) ={A}I(q) ={B}I(r) ={B}2. x. f(x, x) x, y, (x, y) f(y, z) f(x, z) x. (x, y)There is no interpretation in a finite universe that makes all of these sentences true. However, if youconsider an infinite universe, ( , real numbers) and agreaterthanfunction (>), these sentences are :U=RI(f) =>3.
4 X. (x, y) x.(g(x) (y, x)) (x) x. f(x, x)Interpretation:U={A, B}I(f) ={< A, B >, < B, A >}I(g) ={A}3 FOL Semantics(6) Consider a world with objectsA,B, andC. We ll look at a logical languge with constant symbolsX,Y,andZ, function symbolsfandg, and predicate symbolsp,q, andr. Consider the following interpretation: I(X) =A,I(Y) =A,I(Z) =B I(f) ={ A,B , B,C , C,C } I(p) ={A,B} I(q) ={C} I(r) ={ B,A , C,B , C,C }For each of the following sentences, say whether it is true or false in the given (f(Z))Answer: (X, Y)Answer: F3. (w) =YAnswer: F4. (f(w), w)Answer: T5. u, (u, v) ( (u, w) v=w)Answer: F6. u, (u, v) ( (w, v) u=w)Answer: TClausal form(6) Convert each sentence below to clausal y. (x, y) s(x, y)Answer:r(f(y), y) s(f(y), y)2. y.( (x, y)) p(y)Answer: r(x, y) p(y)3. y. x.(r(x, y) p(x))AnsweR: r(f(y), y) p(f(y))Implication vs. EntailmentShow thatP|=Q (T rue|=P Q).
5 LetM(P) andM(Q) be the sets of interpretations (models) under which P and Q are true, AssumeP|=Q. By the definition of entailment, we haveM(P) M(Q). BecauseM(Q) andM( Q) aredisjoint (there are no interpretations under which bothQand Qare true), it follows thatM(P) M( Q) = . Therefore there are no interpretations under whichPis true andQis false, and soP Qis true underall interpretations:M(P Q) =M(T rue) and consequentlyM(T rue) M(P Q). By the definitionof entailment, this means thatT rue|=P Q, and so we have shown thatP|=Q (T rue|=P Q).2. AssumeT rue|=P Q. By the definition of entailment, this means thatP Qis true under allmodels, and so there can be no model such thatPis true andQis false:M(P) M( Q) = . ThereforeM(P) M(Q) and we can conclude thatP|=Q. Thus we have shown that (T rue|=P Q) P|=Q.(1) and (2) together prove the statementP|=Q (T rue|=P Q).4
