ENCS $3340$:Artiticial Intelligence, HW#$3$ Logic

Due Date: $22/1/2024$

Represent the following in first$-$order logic.

$1.$ Represent the following sentences in first$-$order logic:

a$.$ All swans are white.

b$.$ There is a black swan.

c$.$ All bowlers drink soda.

d$.$ Some dogs have fleas.

e$.$ There is somebody who loves everyone.

f$.$ Everybody is loved by someone.

g$.$ There is a barber in Ramallah who shaves all men in Ramallah who do not shave themselves.

h$.$ Politicians can fool some of the people all of the time, and all of the people some of the time, but they can$$t fool

all of the people all of the time.

$2.$ Consider the following definite $($Horn$)-$clause KB:

Notation: $$: for all, $$: exists, &: and, $=>$: implication, $<=>$: biconditional, ~: not

$$x$$y Smoker$($x$)$ & Friends$($y$,$x$)=>$ Smoker$($y$)$

$$x$$y Friends$($x$,$y$)=>$ Friends$($y$,$x$)$

Friends$($Adam$,$Betty$)$

Friends$($Carl$,$David$)$

Friends$($Eddie$,$Adam$)$

Friends$($Eddie$,$David$)$

Smoker$($Eddie$)$:

Answer: Are Betty, Carl smokers? Show your work.

Assume we perform forward$-$chaining starting from this KB $($with all of the rules and facts already loaded$)$ and show the specific conclusions added in their exact order as rules are matched and fired. Assume rules and facts are always matched in the exact order given above and that newly inferred facts are immediately added to the end of the list.

$3.$ Consider the following definite Horn$-$clause KB:

$$x$$y$$z Parent$($x$,$y$)$ & Parent$($x$,$z$)$ & y$!=$z $=>$ Sibling$($y$,$z$)$

$$x$$y$$z Sibling$($v$,$w$)$ & Parent$($w$,$u$)$ & Male$($u$)=>$ Nephew$($u$,$v$)$

Parent$($Bob$,$Mary$),$ Male$($Bob$),$ Female$($Mary$),$ Parent$($Bob$,$Fred$),$ Male$($Fred$),$ Parent$($Mary$,$Tom$),$ Male$($Tom$),$ Parent$($Mary$,$Ann$),$ Female$($Ann$)$

Assume backward$-$chaining rule$-$based inference is used to try to answer the query: Nephew$($s$,$Fred$).$

$4$: Use a truth table to prove modus tollens is sound for proposition logic and to prove that $$P$$Q is equivalent to P$->$Q$.$

$5$: Find the Most General Unifier $($MGU$),$ if one exists for the pairs:

$1.$ f$($g$($x$,$y$),$ c$)$ and f$($g$($f$($d$,$x$),$z$),$c$)$ not unifiable

$2.$ h$($c$,$d$,$g$($x$,$y$))$ and h$($z$,$d$,$g$($g$($a$,$y$),$z$))$

$3.$ P$($f$($a$),$ g$($X$))$ and P$($Y$,$Y$)$

$4.$ P$($a$,$X$,$h$($g$($Z$)))$ and P$($Z$,$h$($Y$),$h$($Y$))$

$5.$ P$($X$,$X$)$ and P$($Y$,$f$($Y$))$

$6.$ P$($a$,$ f$($x$,$ a$))$ and P$($a$,$ f$($g$($y$),$ y$))$

$6$: $($Bonus$)$ not a must: Assume KB consists of the following rules:

R$1$: Soda$($x$)^$ Chips$($y$)$ Cheaper$($x$,$ y$)$

R$2$: Chips$($x$)^$ Cereals$($y$)$ Cheaper$($x$,$ y$)$

R$3$: Cheaper$($x$,$ y$)^$ Cheaper$($y$,$ z$)$ Cheaper$($x$,$ z$)$

And the facts:

F$1$: Soda$($Sprite$)$

F$2$: Chips$($Ruffles$)$

F$3$: Cereals$($Cheerios$)$

F$4$: Cereals$($MiniWheats$)$

a$.$ Assume that all facts F$1-$F$4$ are known at the beginning of the inference process. Illustrate the process of forward chaining by listing all newly inferred facts. Assume that both rules and facts are matched and tried in the order of their appearance.

b$.$ Show how to prove Cheaper$($Sprite$,$ Cheerios$)$ using backward chaining and the KB given in part a$.$ Draw the graph for the problem, assuming rules and facts are tried and matched in the order given