CS计算机代考程序代写 Hive database This page was last updated: 06/11/2018 00:16:20

This page was last updated: 06/11/2018 00:16:20
Activity 8.1 Three Godesses in a Temple
Three goddesses were sitting in an old Indian temple. Their names were Truth, Lie and Wisdom. Truth always told the truth, Lie always lied and Wisdom sometimes told the truth and sometimes lied. A man entered the temple. He first asked the goddess on the left: “Who is sitting next to you?” “Truth,” she answered. He then asked the middle one: “Who are you?” “Wisdom.” Finally he asked the one on the right: “Who is your neighbor?” “Lie,” she replied. Can you say which goddess was which?
COMP3411 Tutorial – Week 5

The goddess on left cannot be True because she said someone else was True. The middle one cannot be True either, so the one on the right must be True. This means the middle one is Lie and the left goddess is
a. Smoke ⇒ Smoke
Valid [implication, excluded middle]
Valid [implication, excluded middle] b. Smoke ⇒ Fire
b. Smoke ⇒ Fire Satisfiable Satisfiable
Logic
Wisdom.
Activity 8.2 Validity and Satisfiability
Question 1 – Propositional Logic
Dyecoiduer wdheectihseiroenaschuosfinthge ftorullothwitnagbslensteonrcelsoigsivcallide, qsautisvfialbelne,coer anenidtheirn. fVeerreifnycyeourur dlesc.isFioonrs uthsiongse that are
(Exercise 7.10 from R & N)
Decide whether each of the following sentences is valid, satisfiable, or unsatisfiable. Verify
satisfiable, list all the models that satisfy them.
truth tables or equivalence and inference rules. For those that are satisfiable, list all the models that satisfy
them.
a. Smoke ⇒ Smoke
Smoke
Fire
Smoke ⇒ Fire
T
T
T
T
F
F
F
T
T
F
F
T
Models are: {Smoke, Fire}, {Fire}, {}
Models are: {Smoke, Fire}, {Fire}, {}. c. ( Smoke ⇒ Fire ) ⇒ ( ¬ Smoke ⇒ ¬ Fire )
COMP3411 Tutorial Solutions Week 8 ⇒
⇒ 4/12/18, 8(52 pm ( ¬ Smoke ⇒ ¬ Fire ) Satisfiable
http:c. ( Smoke //www.cse.unsw.edu.au/~cs3411/18s1/tut/sol/wk09sol.html
Fire )
Page 1 of 5
Satisfiable
Models are: {Smoke, Fire}, {Smoke}, {}
Models are: {Smoke, Fire}, {Smoke}, {}
d. Smoke ∨ Fire ∨ ¬ Fire Valid
e. (( Smoke ∧ Heat ) ⇒ Fire ) ⇔ (( Smoke ⇒ Fire ) ∨ ( Heat ⇒ Fire ))
Valid
(( S ∧ H ) ⇒ F ) ⇔ (F ∨ ¬(S ∧ H)) [implication]
⇔ (F ∨ ¬ S ∨ ¬ H) [de Morgan]
⇔ (F ∨ ¬ S ∨ F ∨ ¬ H) [idempotent, commutativity] ⇔ (S ⇒ F) ∨ (H ⇒ F) [implication]
f. ( Smoke ⇒ Fire ) ⇒ (( Smoke ∧ Heat ) ⇒ Fire )
Valid
( S ⇒ F ) ⇔ ( F ∨ ¬ S ) [implication]
⇒ ( F ∨ ¬ S ∨ ¬ H ) [generalization] ⇒ ( F ∨ ¬ ( S ∧ H )) [de Morgan]
⇒ (( S ∧ H ) ⇒ F ) [conditional]
g. Big ∨ Dumb ∨ ( Big ⇒ Dumb )
Valid
Big ∨ Dumb ∨ ( Big ⇒ Dumb ) ⇔ Big ∨ Dumb ∨ Dumb ∨ ¬ Big [implication]
Smoke
Fire
Smoke ⇒ Fire
¬ Smoke ⇒ ¬ Fire
KB
T
T
T
T
T
T
F
F
T
T
F
T
T
F
F
F
F
T
T
T
⇔ Big ∨ ¬ Big ∨ Dumb [idempotent]
⇔ TRUE ∨ Dumb [excluded middle]

TFFTT FTTFF FFTTT
Models are: {Smoke, Fire}, {Smoke}, {}
d. Smoke ∨ Fire ∨ ¬ Fire
Valid
e. (( Smoke ∧ Heat ) ⇒ Fire ) ⇔ (( Smoke ⇒ Fire ) ∨ ( Heat ⇒ Fire ))
Valid
(( S ∧ H ) ⇒ F ) ⇔ (F ∨ ¬(S ∧ H)) [implication]
⇔ (F ∨ ¬ S ∨ ¬ H) [de Morgan]
⇔ (F ∨ ¬ S ∨ F ∨ ¬ H) [idempotent, commutativity] ⇔ (S ⇒ F) ∨ (H ⇒ F) [implication]
f. ( Smoke ⇒ Fire ) ⇒ (( Smoke ∧ Heat ) ⇒ Fire )
Valid
( S ⇒ F ) ⇔ ( F ∨ ¬ S )
⇒ ( F ∨ ¬ S ∨ ¬ H ) ⇒ ( F ∨ ¬ ( S ∧ H )) ⇒ (( S ∧ H ) ⇒ F )
g. Big ∨ Dumb ∨ ( Big ⇒ Dumb ) Valid
Big ∨ Dumb ∨ ( Big ⇒ Dumb
h. ( Big ∧ Dumb ) ∨ ¬ Dumb Satisfiable
[implication] [generalization] [de Morgan] [conditional]
) ⇔ Big ∨ Dumb ∨ Dumb ∨ ¬ Big [implication]
⇔ Big ∨ ¬ Big ∨ Dumb ⇔ TRUE ∨ Dumb
⇔ TRUE
[idempotent] [excluded middle]
4/12/18, 8(52 pm
Page 2 of 5
COMP3411 Tutorial
http://www.cse.u
Big
Dumb
(Big ∧ Dumb)
(Big ∧ Dumb) ∨ ¬ Dumb
T
T
T
T
Solution
T
s Week 8
F
F
T
nsw.
F
edu.au
F
T
/~cs3411/1
F
F
8s1/tut/sol/wk09sol.ht
F
ml
T
F
Models are: {Big, Dumb}, {Big}, {}
Models are: {Big, Dumb}, {Big}, {}
Activity 8.3 Resolution and Conjunctive Normal Form
(Exercise 7.2 from R & N)
Consider the following Knowledge Base of facts:
If the unicorn in mythical, then it is immortal, but if it is not mythical, then it is mortal and a mammal. If the unicorn in either immortal or a mammal, then it is horned. The unicorn is magical if it is horned.
1. Translate the above statements into Propositional Logic.
Myth ⇒ ¬ Mortal
¬Myth ⇒ ( Mortal ∧ Mammal ) ¬Mortal ∨ Mammal ⇒ Horned
Horned ⇒ Magic
2. Convert this Knowledge Base into Conjunctive Normal Form.

⇔ ¬P ∨ Q
⇔5.(¬P􏰂∨ Q) ∧ 3(¬, ¬4 PRe∧so¬luRt)io∧n(¬¬P ∧ ¬Q) [Double Negation and De Morgan]
CNF(Q → R) ⇔ ¬Q ∨ R
CNF(¬(P → R))
⇔ ¬(¬P ∨ R) [Remove →]
⇔ ¬¬P ∧ ¬R [De Morgan] Question 2 – Tautologies
⇔ P ∧ ¬R [Double Negation)
Determine whether the following sentences are valid (i.e. tautologies) using truth tables.
2. ¬Q ∨ R (i) ((P∨Q)∧¬P)→Q
Proof:
1. ¬P ∨ Q
[Hypothesis]
[Hypothesis]
[Negation of Query]
3. P
(ii) ((P →Q)∧¬(P →R))→(P →Q)
(iii) ¬(¬P ∧P)∧P 4. ¬R 5. Q
(iv) (P ∨Q)→¬(¬P6.∧¬QR) 7. 􏰂
5. (i)
[Negation of Query] 1, 3 Resolution
2, 5 Resolution
4, 6 Resolution
P
Q
¬P
P∨Q
(P ∨Q)∧¬P
((P ∨ Q) ∧ ¬P ) → Q
T T F F
T F T F
F F T T
T T T F
F F T F
T T T T
Last column is always true no matter what truth assignment to P and Q. Therefore ((P ∨ Q) ∧ ¬P ) → Q is a tautology.
Last column is always true no matter what truth assignment to P and Q. Therefore (ii) S=((P →Q)∧¬(P →R))→(P →Q)
((P ∨ Q) ∧ ¬P ) → Q is a tautology.
P Q R P→Q P→R ¬(P→R) (P→Q)∧¬(P→R) S
(ii) S=((P →Q)∧¬(P →R))→(P →Q) TTTTTFFT
PT
QF
RT
P → QF
P → RT
¬(P → R)T
(P →Q)∧¬(P →R)T
S
Las
TF
((P Last TF
((SP= TT
TP S =T
F TF
P
FT TF
F T
st co
T
FT

T
t col
TT
∨Q colu TF
(Q(P) FT
FQ ((PF
TTT Q
TT TF
F F
lumn
T
FF
Q)∧ F
umn
TF
)∧¬ mn
FF
∧→¬
TT FR
→ QT TTT
R
FF TT
TT
is a
F
FF
¬(P T
is always
T P)→Qi
is always
T
) ∧→¬Q(Pis
F
FP → Q
)∧¬(P T
TT T P→Q
TT T
T
TF
lways true
T
TF
→ R)) → F
T
F
T
true no
T
F
s a tautol true no m
F
a Rta)u)t→olo(
T
FP → R
T
F
R ) ) → (F
TT F P→R
TF T
F
TT
no matte
F
TF
(P → Q) T
atter what t
F
F
gy.
atter what tr
T
F
gPy.→ Q) F
F T¬(P → R)
→Q) F
F FF
¬(P → R)
FT F
F
F F
r what truth
T
FT
is a tautolog
F
ruth assignment to P an
F
uth assignment to P an
T
T T T
F
F(P →Q)∧¬(P →R) T
T
F FT
(P →Q)∧¬(P →R) FT
F
F F
assignment to P , Q and T
FF y.F
dQ T
d Q. T
T
TS
TT S
TT T
TT
.T
T
TT T
T
T
T
La ((P
m o
∨ QP → →P
. Therefore Therefore
herefore
(ii)
F (ii)F F F
R
LaFst coTlumnT is aTlways trueTno matteFr what truth Fassignment to P , Q and RT. Therefore TFFFFTFT
P ¬P
¬P ∧P ¬(¬P ∧P) ¬(¬P ∧P)∧P
((PF → TQ) ∧F¬(PT→ R)) →T(P → Q)Fis a tautologFy. T FTTTTFFT
(iii)TFF T T FFTTTFFT
FP T¬P F¬PT∧P ¬(¬TP ∧P) F¬(¬P ∧P)F∧P T FTFTF
FFFTTFFT (iii)FTFTFT TT FT F T Last column is not always true. Therefore ¬(¬P ∧ P ) ∧ P is not a tautology.
Last column is always true no matter what truth assignment to P , Q and R. Therefore FFTFFT TT FF F T
(iv) (P ∨((QP)→Q¬)(¬∧P¬(∧P¬→Q)R)) → (P → Q) is a tautology.
Last column is always true no matter what truth assignment to P , Q and R. Therefore Last column is not always true. Therefore ¬(¬P ∧ P ) ∧ P is not a tautology.
P( → (P ∨Q)→¬(¬P ∧¬Q) (iv) ( Q
Q (P
P∨
¬P ¬QP) ∧
Q) →
¬Q P ¬(P ∧→PR
¬(¬P ∧ ¬
∨Q ¬P∧¬ ) ) ¬ →( ¬ ( P P ∧ → P ) Q )
)
Q ¬(¬P∧¬Q) i¬s (a¬tPau∧toPlo)g∧y.P
T T
P PF
F T
F F
¬P QF ¬
T F
FT F
¬P ∧ P PT ¬QT
F F
P∨QF ¬P
F
T
¬(¬P ∧P)
T T
TT
¬(¬P ∧P)∧P
∧¬QT ¬(¬P∧¬
F T
TT
(iii) Q) (P ∨Q)→¬(¬P ∧¬Q) TT
(iii)TTFFTFT T FTTFTFTT
Last column is not always true. Therefore ¬(¬P ∧ P ) ∧ P is not a tautology. FTFTF
F TF FT F T T F T T F F T T T
(iv)L(aPst∨coQlu)m→n¬is(¬nPot∧al¬wQay)s true. Therefore ¬(¬P ∧P)∧P is not a tautology. FTTFTFTT
Last column is always true no matter what truth assignment to P and Q. Therefore FP FQ T¬P T¬Q FP ∨Q T¬P ∧¬Q F¬(¬P ∧¬Q) T(P ∨Q)→¬(¬P ∧¬Q)
(iv()P (∨PQ∨)Q→) →¬(¬P(¬∧P¬∧Q¬)Qis)a tautology.
o re ⇔∨m
LaTst P¬
coTlu Q
mnF is ¬P

alFway ¬Q
¬
s tTrue n P∨Q

mFatter wh ¬P ∧ ¬Q
atTtruth assign ¬(¬P ∧ ¬Q)
menTt to P and Q. Therefo (P ∨Q)→¬(¬P ∧¬Q)
(PT∨ T
¬(¬( F
T
CNF ¬¬((
F F
⇔¬ (P ∨ Las
F
⇔¬
QF) T
(PT
F
(¬(( P∨ F
T
(¬(( Q) t col F ¬((P
→ F¬ ( ¬ F
Q)∧ T
F
(P ∨ Q)∧
T T
∨Q ¬P
umn i
T ∨Q)
P T∧ ¬ F
¬P)∨ F
T
)∧¬ P)∧ T
F
)∧¬P ¬Q [ s alwa
T ∧¬P)
Q)Tis a t T
Q) [Re T
T
P ) → Q) ¬Q [De
F T
) ∨ Q) [ Double ys true n
F
∧ ¬Q [D
autFology. F
ove →] F
)F
organ]
T F
emove →] egation]
o matter w
T
e Morgan]
T T
T T
F T
hat truth assign
F
T T
T T
T T
ment to P and Q. Theref T
6.(i)CNF((((PQ)∧P) Q)) 6. (i) Q
⇔¬M PR
⇔∧∧N
ore ProLoafs:t column is always true no matter what truth assignment to P and Q. Therefore
(P ∨ Q) → ¬(¬P ∧ ¬Q) is a tautology. ⇔ (P ∨ Q) ∧ ¬P ∧ ¬Q [Double Negation]
1. P ∨ Q [Negated Query]
(P ∨ Q) → ¬(¬P ∧ ¬Q) is a tautology.
6. 6.
Th2e.refo¬rPe ¬(((P[N∨eQga)t∧ed¬QPu)e→ry]Q) is a tautology. 1. P ∨ Q [Negated Query]
(i) CNF(¬(((P ∨ Q) ∧ ¬P) → Q)) 2.Pro¬oPf: [Negated Query]
⇔ ¬(¬((P ∨ Q) ∧ ¬P ) ∨ Q) [Remove →] (i) C1N.F(¬P((∨(PQ∨Q[N)e∧ga¬tPed)→QuQer)y)]
3. ¬Q
[Negated Query]
⇔ ¬¬((P ∨ Q) ∧ ¬P ) ∧ ¬Q [De Morgan] ⇔2.¬(¬(P(P ∨ Q)[N∧eg¬aPte)d∨Qu)e[rRy]emove →]
4. Q
1, 2 Resolution
⇔ (P ∨ Q) ∧ ¬P ∧ ¬Q [Double Negation] ⇔3.¬¬¬((QP ∨ Q)[∧Ne¬gPat)e∧d ¬QQue[rDye] Morgan]
5. 􏰂 3, 4 Resolution
⇔4.(P Q∨ Q) ∧ ¬1P, ∧2 ¬RQeso[Dluotiuobnle Negation]
ThePrerfooref: ¬(((P ∨ Q) ∧ ¬P ) → Q) is a tautology.
51. . 􏰂P ∨ Q 3[,N4egRaetseodluQtiuoenry]
(ii) CNPFr(o¬o(f(:(P → Q) ∧ ¬(P → R)) → (P → Q)))
⇔ ¬(¬((¬P ∨ Q) ∧ ¬(¬P ∨ R)) ∨ (¬P ∨ Q)) [Remove →] 3. ¬Q [Negated Query]
(ii) C2N.F(¬(P((P →[QN)eg∧at¬e(dPQ→ueRry)]) → (P → Q)))
⇔ ¬¬((¬P ∨ Q) ∧ ¬(¬P ∨ R)) ∧ ¬(¬P ∨ Q) [De Morgan]
4. Q 1, 2 Resolution
⇔3.¬(¬(Q(¬P ∨ Q[N)e∧ga¬t(e¬dPQ∨ueRry)]) ∨ (¬P ∨ Q)) [Remove →]
⇔ (¬P ∨ Q) ∧ (¬¬P ∧ ¬R) ∧ (¬¬P ∧ ¬Q) [Double Negation and De Morgan] 5. 􏰂 3, 4 Resolution
⇔4.¬¬Q((¬P ∨Q1),∧2¬R(e¬sPolu∨tiRon))∧¬(¬P ∨Q) [De Morgan] ⇔ (¬P ∨ Q) ∧ (P ∧ ¬R) ∧ (P ∧ ¬Q) [Double Negation]
Therefore ¬(((P ∨ Q) ∧ ¬P ) → Q) is a tautology.

R: it will rain today
(iii) ¬S → ¬P , or ¬(P ∧ ¬S) (check these are equivalent) Where:
S: you study
P: you will pass this course
2. (i)P→Q
¬P ∨ Q [Remove →]
Question 3 – Entailment
(ii) (P →¬Q)→R
Show using the truth table method that the corresponding inferences are valid.
¬(¬P ∨ ¬Q) ∨ R [Remove →]
(¬¬P ∧ ¬¬Q) ∨ R [De Morgan]
(P ∧ Q) ∨ R [Double Negation] (i)P → Q, ¬Q |= ¬P
(P ∨R)∧(Q∨R) [Distribute ∨ over ∧] (ii) P → Q |= ¬Q → ¬P
(iii) ¬(P ∧ ¬Q) → (¬R ∨ ¬Q) (iii)P→¬Q¬,(QP→∧¬RQ|)=∨P(¬→RR∨¬Q)[Remove→]
(P ∧ ¬Q) ∨ (¬R ∨ ¬Q) [Double Negation]
(P ∨¬R∨¬Q)∧(¬Q∨¬R∨¬Q) [Distribute ∨ over ∧]
This can be further simplified to (P ∨ ¬R ∨ ¬Q) ∧ (¬Q ∨ ¬R)
and even further simplified to ¬Q ∨ ¬R, since ¬Q ∨ ¬R subsumes P ∨ ¬R ∨ ¬Q
(i)
In all rows where both P → Q and ¬Q true, ¬P is true. Therefore, valid inference.
(ii)
In all rows where both P → Q true, ¬Q → ¬P is true. Therefore, valid inference.
(iii)
In all rows where both P → Q and Q → R true, P → R is true. Therefore, valid inference.
P
Q
P→Q
¬Q
¬P
T T F F
T F T F
T F T T
F T F T
F F T T
3.
P
Q
¬P
¬Q
P→Q
¬Q → ¬P
T T F F
T F T F
F F T T
F T F T
T F T T
T F T T
P
Q
R
P→Q
Q→R
P→R
T T T T F F F F
T T F F T T F F
T F T F T F T F
T T F F T T T T
T F T T T F T T
T F T F T T T T

COMP3411 Tutorial Solutions Week 8
4/12/18, 8(52 pm
FTFF FFFT
Models are: {Big, Dumb}, {Big}, {}
Question 4 – Inference Rules
Activity 8.3 RFesoluTtion and CFonjunctive Normal FForm FFFT
(Exercise 7.2 from R & N) (Exercise 7.2 from R & N)
Models are: {Big, Dumb}, {Big}, {}
Consider the following Knowledge Base of facts:
Consider the following Knowledge Base of facts:
Activity 8.3 Resolution and Conjunctive Normal Form
COMP3411 Tutorial Solutions Week 8 4/12/18, 8(52 pm
If the unicorn in mythical, then it is immortal, but if it is not mythical, then it is mortal and a
If the unicorn in mythical, then it is immortal, but if it is not mythical, then it is mortal and a
mammal. If the unicorn in either immortal or a mammal, then it is horned. The unicorn is
mammal. If the unicorn in either immortal or a mammal, then it is horned. The unicorn is FTFF
magical if it is horned.
(Exercise 7.2 from R & N)
magical if it is horned. FFFT
Conside1r.the fTorllaonwsilnagteKtnhoewalebdogveeBsatsaeteomf feacnttss: into Propositional Logic. 1. TranslMaotedetlhs earea:b{oBvige, Dstuamteb}m, {eBnitgs},in{}to Propositional Logic.
If the unicorn in mythical, then it is immortal, but if it is not mythical, then it is mortal and a Activity 8.3 ReMsoyluthion⇒and¬CMonojurntcatlive Normal Form
mammal. If the unicorn in either immortal or a mammal, then it is horned. The unicorn is
¬Myth ⇒ ( Mortal ∧ Mammal ) magical if it is horned.
(Exercise 7.2 from R & N)
¬Mortal ∨ Mammal ⇒ Horned
1C.onTsirdaenr tshleatfeoHlltohowerinaegbdKovn⇒oewsMlteadatgegemiBceasnetsofinfatcotsP: ropositional Logic.
If the unicorn in mythical, then it is immortal, but if it is not mythical, then it is mortal and a 2. ConveMrt yththis⇒Kn¬oMwloerdtagle Base into Conjunctive Normal Form.
mammal. If the unicorn in either immortal or a mammal, then it is horned. The unicorn is
¬Myth ⇒ ( Mortal ∧ Mammal ) magical if it is horned.
(¬My¬tMh∨or¬talM∨oMrtalm)m∧a(lM⇒ytHho∨rnMedortal)∧(Myth∨Mammal)∧(Mortal∨Horned)∧(¬Mammal∨ 1. Translate the above statements into Propositional Logic.
HorneHd)o∧rn(e¬dH⇒orMneadgi∨c Magic)
2. Convert this Knowledge Base into Conjunctive Normal Form.
Myth ⇒ ¬ Mortal 23..CUosnevear¬tsMethryiteshs⇒Kon(foMrweoslretoadlug∧etiMoBanamsmetoailnp)trooCveonthjuantctthiveeuNniocromrnaliFsoHrmor.ned.
¬Mortal ∨ Mammal ⇒ Horned
Horned ⇒ Magic
(¬Myth ∨ ¬ Mortal) ∧ (Myth ∨ Mortal) ∧ (Myth ∨ Mammal) ∧ (Mortal ∨ Horned) ∧ (¬Mammal ∨
Using Proof by Contradiction, we add to the database the negative of what we are trying to prove:
Horned) ∧ (¬Horned ∨ Magic)
2. Convert this Knowledge Base into Conjunctive Normal Form.
¬Horned
(¬Myth ∨ ¬ Mortal) ∧ (Myth ∨ Mortal) ∧ (Myth ∨ Mammal) ∧ (Mortal ∨ Horned) ∧ (¬Mammal ∨ 3. Use a series of resolutions to prove that the unicorn is Horned.
Horned) ∧ (¬Horned ∨ Magic)
3. Use a series of resolutions to prove that the unicorn is Horned. We then try to derive the “empty clause” by a series of Resolutions:
Using Proof by Contradiction, we add to the database the negative of what we are trying to prove: 3. Use a series of resolutions to prove that the unicorn is Horned.
¬Horned ∧ (Mortal ∨ Horned)
¬HUosirnngePdroof by Contradiction, we add to the database the negative of what we are trying to prove:
Mortal
¬Horned
We then try to derive the “empty clause” by a series of Resolutions:
¬Horned ∧ (¬Mammal ∨ Horned)
We then try to derive the “empty clause” by a series of Resolutions:
¬Mammal
¬Horned ∧ (Mortal ∨ Horned)
¬Horned ∧ (Mortal ∨ Horned) Mortal
Mortal
Mortal ∧ (¬Myth ∨ ¬Mortal)
¬Myth
¬Horned ∧ (¬Mammal ∨ Horned)
¬Horned ∧ (¬Mammal ∨ Horned) ¬Mammal
¬Mammal
¬Myth ∧ (Myth ∨ Mammal)
Mortal ∧ (¬Myth ∨ ¬Mortal) MoMrtalm∧m(¬alMyth ∨ ¬Mortal)
¬Myth ¬Myth
M¬Mamythm∧a(lM∧yt¬hM∨ Mamammal) Mammal
¬Myth ∧ (Myth ∨ Mammal)
HMavaminmg adlerived the empty clause, the proof (of Horned) is complete.
Mammal ∧ ¬Mammal
Having derived the empty clause, the proof (of Horned) is complete.
Mammal ∧ ¬Mammal http://www.cse.unsw.edu.au/~cs3411/18s1/tut/sol/wk09sol.html
Page 3 of 5
Having derived the empty clause, the proof (of Horned) is complete.
4. Give all models that satisfy the Knowledge Base. Can you prove that the unicorn is
http://www.cse.unsw.edu.au/~cs3411/18s1/tut/sol/wk09sol.html
Page 3 of 5
http://www.cse.unsw.edu.au/~cs3411/18s1/tut/sol/wk09sol.html Page 3 of 5
Mythical? How about Magical?
Because of the rule (Horned ⇒ Magic), Magic must also be True. We can construct a truth table for the remaining three variables:

Because of the rule (Horned ⇒ Magic), Magic must also be True.
around and sees that everyone else has brown eyes, he will conclude that he must have blue
Because of the rule (Horned ⇒ Magic), Magic must also be True.
We can construct a truth table for the remaining three variables:
We can construct a truth table for the remaining three variables:
Myth
Myth M Mortal
ortal Ma Mammal
mMmytahl⇒My¬tMh ⇒orta¬l
T
TT
TT
TFF
T
TT
TF
FFF
TF
FF
FTT
There are three models which satisfy the entire Knowledge Base:
There are three models which satisfy the entire Knowledge Base:
Mortal ¬ Myth ⇒ (Mortal ∧ ¬ Myth ⇒ (Mortal ∧ Mammal)
{Horned, Magic, Myth, Mammal}, {Horned, Magic, Myth}, {Horned, Magic, Mortal, Mammal}.
{Horned, Magic, Myth, Mammal}, {Horned, Magic, Myth}, {Horned, Magic, Mortal, M We cannot prove that the unicorn is Mythical, because of the third model where Mythical is False.
TT
TT
T
T
am KB
F
al) KB
F F T T T F F F
F
T
TF
FT
TTT
TT
T
T
T
F
FT
TT
TTT
T
T
T
F
FT
TF
FTT
F
F
F
F
FF
FT
TTT
F
F
F
F
FF
FF
FTT
F
F
F
ammal}. We cannot prove that the unicorn is Mythical, because of the third model where Mythical is False.
Activity 8.4 Sentences in First Order Logic Activity 8.4 Sentences in First Order Logic
RepreQseuntethsetfioollonwi5ng-senFteinrcsestiOn firdst-eordeLr ologici,cusing a consistent vocabulary.
Represent the following sentences in first-order logic, using a consistent vocabulary.
Represent the following sentences in first-order logic, using a consistent vocabulary.
a. Some students studied French in 2016.
b.
c.
d.
e.
http://ww CO
http://www.cse.unsw.edu.au/~cs3411/18s1/tut/sol/wk09sol.html
Activity 8.5 The Interplanetary Visitor
Page 4 of 5 4/12/18, 8(52 pm
Mm
a. Some students studied French in 2016.
∃ x Student(x) ∧ Study(x,French,2016)
∃ x Student(x) ∧ Study(x,French,2016)
Only one student studied Greek in 2015.
b. Only one student studied Greek in 2015.
∃x Study(x,Greek,2015) ∧ ∀y (Study(y,Greek,2015) ⇒ y = x )
∃x Study(x,Greek,2015) ∧ ∀y (Study(y,Greek,2015) ⇒ y = x )
sometimes written as sometimes written as
∃!x Study(x,Greek,2015)
∃!x Study(x,Greek,2015)
The highest score in Greek is always higher than the highest score in French.
c. The highest score in Greek is always higher than the highest score in French.
∀t ∃x ∀y Score(x,Greek,t) > Score(y,French,t)
∀t ∃x ∀y Score(x,Greek,t) > Score(y,French,t)
Every person who buys a policy is smart. d.E∀vxe,pryPpeerrssoonn(xw)∧hoPbouliycsy(ap)p∧olBicuyy(isx,spm)⇒art.Smart(x)
No person bu∀yxs,panPexrpsoens(ixv)e∧poPloiclyic.y(p) ∧ Buy(x,p) ⇒ Smart(x) ¬∃x,p Person(x) ∧ Policy(p) ∧ Expensive(p) ∧ Buy(x,p)
e. No person buys an expensive policy.
¬∃x,p Person(x) ∧ Policy(p) ∧ Expensive(p) ∧ Buy(x,p) MP3411 Tutorial Solutions Week 8
w.cse.unsw.edu.au/~cs3411/18s1/tut/sol/wk09sol.html
Page 4 of 5
f. There is a barber who shaves all men in town who do not shave themselves.
∃b Barber(b) ∧ ∀m (Man(m) ∧ InTown(m) ∧ ¬Shave(m,m) ⇒ Shave(b,m))
g. Politicians can fool some of the people all of the time, and they can fool all of the people some of
the time, but they can’t fool all of the people all of the time.
∀p ( Politician(p) ⇒ ((∃x∀t Fool(p,x,t)) ∧ (∃t∀x Fool(p,x,t)) ∧ (¬∀x∀t Fool(p,x,t))))
On a certain planet there are 100 highly intelligent but also highly religious inhabitants who all know and see each other on a daily basis. Some number n of them have blue eyes, the rest have brown eyes. The religious laws of the planet dictate that anybody who is able to prove that their own eyes must be blue has to ritually commit suicide the same evening, at midnight. Everybody knows that everybody else will obey this law without question. For this reason, it has become forbidden on the planet to discuss eye colour, and all mirrors, cameras and other such devices have long since been destroyed. One day a visitor comes from a neighboring planet whose inhabitants are known to always speak the truth. Everyone has gathered for his departure. Just before closing the door of his spaceship, he says in a voice loud enough for everyone to hear: “At least one of you has blue eyes.” What will happen in the days (and nights) that follow?
(Hint: consider first the case n=1, then n=2, n=3, etc.)
First consider the case where there is only one inhabitant with blue eyes. When he looks