Write axioms describing the predicates: GrandChild, GreatGrandparent, Brother, Sister, Daughter, Son, Aunt, Uncle, BrotherInLaw, SisterInLaw and FirstCousin.
These predicates are all relational and they should be read as relation
(a,b) ⇒ a is a relation
of b.
GrandChild
(a,b) ⇒
parent
(b,x) ∧ parent
(x,a)
GreatGrandparent
(a,b) ⇒
parent
(a,x) ∧ GrandChild
(b,x)
The Sibling relationship is added to make the expression of some future relationships simpler. In this situation, Sibling encompasses full, half and step siblings.
Sibling
(a,b) ⇒
parent
(x,a) ∧ parent
(x,b) ∧
not_equal
(a,b)
Sibling
(a,b) ⇒ Sibling
(b,a)Brother
(a,b) ⇒
Sibling
(a,b) ∧ gender
(a,'male')
Sister
(a,b) ⇒
Sibling
(a,b) ∧ gender
(a,'female')
Son
(a,b) ⇒
parent
(b,a) ∧ gender
(a,'male')
Daughter
(a,b) ⇒
parent
(b,a) ∧ gender
(a,'female')
Uncle
(a,b) ⇒
parent
(x,b) ∧ Sibling
(x,a)
∧ gender
(a,'male')
Aunt
(a,b) ⇒
parent
(x,b) ∧ Sibling
(x,a)
∧ gender
(a,'female')
married
is a primitive relation, meaning it is not defined in terms of any other relations. It is necessary however to note that it is reflexive.
married
(a,b) ⇒ married
(b,a)BrotherInLaw
(a,b) ⇒
married
(b,x) ∧ Sibling
(a,x)
∧ gender
(a,'male')
SisterInLaw
(a,b) ⇒
married
(b,x) ∧ Sibling
(a,x)
∧ gender
(a,'female')
FirstCousin
(a,b) ⇒
parent
(x,a) ∧ parent
(y,b) ∧
Sibling
(x,y)
Express the proper definition of a mth cousin removed n times in first-order logic.
From: www.tedpack.org/cousins.html:
Removedness is a function of generations, if two cousins are from different generations, they are removed that once for each generation.
The first step is to express the mth cousin. This definition, for the sake of brevity expresses siblings as 0th cousins.
Cousin
(a,b,m) ⇒
(greater
(m,0) ∧
parent
(x,a) ∧ parent
(y,b) ∧
Cousin
(x,y,m-1)) ∨
(equal
(m,0) ∧ Sibling
(a,b))
Cousin
(a,b,m) ⇒ Cousin
(b,a,m)Next, a different predicate is added which is distinguished by the number of arguments. A n is added to represent "removed n times."
Cousin
(a,b,m,n) ⇒
(greater
(n,0) ∧
(parent
(x,a) ∧ Cousin
(x,b,m,n-1)) ∨
(parent
(x,b) ∧ Cousin
(x,a,m,n-1))) ∨
(equal
(n,0) ∧ Cousin
(a,b,m))
Cousin
(a,b,m,n) ⇒
Cousin
(b,a,m,n)
Write the basic facts of the following family tree using a suitable reasoning system:
A suitable reasoning system would be Prolog. family_tree.prolog represents the above relations and predicates.
Using the same system, Tell
it the sentences and Ask
it who are Elizabeth's grandchildren, Diana's brothers-in-law, and Zara's great-grandparents.
Using gprolog and family_tree.prolog, the following results are derived:
grandchild
(A,'Elizabeth'). (Elizabeth's grandchildren)
brotherInLaw
(A,'Diana'). (Diana's brothers-in-law)
greatGrandparent
(A,'Zara'). (Zara's great-grandparents)
Any m-input, n-output gate or circuit may be represented using a predicate with m + n arguments, such that the predicate is true exactly when the inputs and outputs are consistent. For example, not-gates are described by the binary predicate not
(i,o), for which not
(0,1) and not
(1,0) are known. Compositions of gate predicates are defined by conjunctions of gate predicates in which shared variables indicate direct connections. For example, a nand
circuit can be composed from and
s and not
s:
∀i1,i2,oa,o
nand
(i1,i2,o) ⇐
and
(i1,i2,oa) ∧
not
(oa,o)
Using this representation, define and explain the queries you would use to verify:
A full one-bit adder
This predicate will be based off other existing predicates:
and
(i1,i2,oa)
and
(0,0,0)and
(0,1,0)and
(1,0,0)and
(1,1,1)or
(i1,i2,oo)
or
(0,0,0)or
(0,1,1)or
(1,0,1)or
(1,1,1)xor
(i1,i2,ox)
xor
(0,0,0)xor
(0,1,1)xor
(1,0,1)xor
(1,1,0)ToDo: Express xor
as an implication.
The adder then may be expressed as:
add
(i1,i2,ic,o,oc) ⇐
xor
(i1,i2,x1) ∧and
(i1,i2,a1) ∧xor
(ic,x1,o) ∧and
(ic,x1,a2) ∧or
(aa,a2,oc)This predicate should produce these expressions:
add
(i1,i2,ic,o,oc)
add
(0,0,0,0,0)add
(0,0,1,1,0)add
(0,1,0,1,0)add
(0,1,1,0,1)add
(1,0,0,1,0)add
(1,0,1,0,1)add
(1,1,0,0,1)add
(1,1,1,1,1)A four-bit adder
This adder may be expressed in terms of the one-bit adder:
add4
(x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4,z5) ⇐
add
(x1,y1,
0,z1,a1) ∧
add
(x2,y2,
a1,z2,a2) ∧
add
(x3,y3,
a2,z3,a3) ∧
add
(x4,y4,
a3,z4,z5) ∧
The number of raw possible inputs is 28. If the following reflexivity is recognized:
add4
(x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4,z5) ⇔
add4
(y1,y2,y3,y4,x1,x2,x3,x4,z1,z2,z3,z4,z5)
This removes half the possibilities, but there are still 27 which are too many to list. Another identity is:
add4
(x1,x2,x3,x4,0,0,0,0,x1,x2,x3,x4,0)
That removes an additional 24, but there are still over 100. Some examples are:
add4
(x1,x2,x3,x4,y1,y2,y3,y4,z1,z2,z3,z4) ⇐
add4
(0,0,0,0,0,0,0,0,0,0,0,0)add4
(1,0,0,0,0,0,0,1,0,0,0,0)add4
(0,1,0,0,0,0,0,0,1,0,0,0)add4
(1,0,0,0,1,0,0,0,1,0,0,0)add4
(1,0,0,0,1,0,0,0,1,0,0,0)add4
(1,0,0,0,1,0,0,0,1,0,0,0)What kinds of queries are not supported by this representation that are supported by the representation in Section 8.4 of Artificial Intelligence by Russel and Norvig?
Represent each of the following sentences in first-order logic, using a consistent vocabulary (which you must define).
A computer system is intelligent if it can perform a task which, if performed by a human, requires intelligence.
task(x) ∧ requires_human_intelligence(x) ∧ computer(y) ∧ can_perform(x,y) ⇒ is_intelligent(y)
Every city has a dogcatcher who has been bitten by every dog in town.
∀z city(z) ⇒ ∃x ∀y dog(y) ∧ lives_in(y,z) ∧ dogcatcher_for(x,z) ⇒ has_bitten(y,x)
There is an agent who sells policies only to people who are not insured.
An interesting ambiguity of this sentence is crystallized by this question "Does this agent sell policies to corporations?" It distinguishes whether "only to people who are not insured" means:
The interpretation changes whether being a person is an antecedent or a consequent.
∃x ∀y,z agent(x) ∧ person(y) ∧ policy(z) ∧ sells(x,y,z) ⇒ ¬insured(y)
A person born in the UK, each of whose parents is a UK citizen or a UK resident, is a UK citizen by birth.
It is assumed that "parents" refers to the sum total of an individuals parents. An orphan adopted by an individual would have a single parent legally. It is the legal definition that is used since citizenship is a legal matter.
A person born outside the UK, one of whose parents is a UK citizen by birth, is a UK citizen by descent.
Convert the following well-formed formulas to CNF.
[¬(∀x P(x))] ⇒ [∃x ¬P(x)]
Eliminate implications: (A ⇒ B ⇔ ¬B ∨ A)
¬[∃x ¬P(x)] ∨ [¬(∀x P(x))]
Reduce negation scope: (¬∀x p ⇔ ∃x ¬p; ¬∃x p ⇔ ∀x ¬p)
[∀x P(x)] ∨ [∀x ¬P(x)]
Drop qualifiers on now universally qualified variables:
P(x) ∨ ¬P(y)
∀x ∃y [(P(x,y) ⇒ Q(y,x)) ∧ (Q(y,x) ⇒ S(x,y))] ⇒ ∃x ∀y [P(x,y) ⇒ S(x,y)]
Eliminate implications:
Reduce negation scope:
Guarantee qualified variable uniqueness:
Replace existential qualifiers with functions (skolemization):
Drop qualifiers on now universally qualified variables:
For the safe of clarity, temporarily perform some substitutions:
Distribute ∧ over ∨:
The conjoined clauses resubstituted are:
(A ∨ ¬C ∨ D) ∧ | = | (S(x1,f1(x1)) ∨ ¬Q(f2(x2),x2) ∨ P(x2,f2(x2))) ∧ |
(A ∨ ¬E ∨ F) ∧ | (S(x1,f1(x1)) ∨ ¬S(x2,f2(x2)) ∨ Q(f2(x2),x2)) ∧ | |
(¬B ∨ ¬C ∨ D) ∧ | (¬P(x1,f1(x1)) ∨ ¬Q(f2(x2),x2) ∨ P(x2,f2(x2))) ∧ | |
(¬B ∨ ¬E ∨ F) | (¬P(x1,f1(x1)) ∨ ¬S(x2,f2(x2)) ∨ Q(f2(x2),x2)) |
Write logical representations for the following sentences suitable for use with Generalized Modus Ponens:
According to Russel and Norvig, definite clauses are "a" form appropriate for Generalized Modus Ponens. Since no other suitable forms are mentioned, definite clauses will be used. Definite clauses are either:
Horses, cows and pigs are mammals.
∀a Horse
(a) ∨ Cow
(a) ∨
Pig
(a) ⇒ Mammal
(a)
As definite clauses, this would be written as:
Horse
(a) ⇒ Mammal
(a)Cow
(a) ⇒ Mammal
(a)Pig
(a) ⇒ Mammal
(a)The offspring of a horse is a horse.
∀a,b Horse
(a) ∧ Offspring
(b,a) ⇒
Horse
(b)
Bluebeard is a horse.
Horse
('Bluebeard')
Bluebeard is Charlie's parent.
Parent
('Bluebeard','Charlie')
Offspring and parent are inverse relationships.
∀a,b Parent
(a,b) ⇔ Offspring
(b,a)
As definite clauses, this would be written as:
Parent
(a,b) ⇒ Offspring
(b,a)Offspring
(a,a) ⇒ Parent
(b,a)Every mammal has a parent.
∀a ∃b Mammal
(a) ⇒ Parent
(b,a)
Use those sentences to answer the following questions using a backward-chaining algorithm:
What is the proof tree generated by an exhaustive backward-chaining algorithm for the query ∃h Horse
(h), where clauses are matched in the order given?
What is noticeable about this domain?
The search tree recurses infinitely because predicates are examined in the order listed and the first predicate with Horse
as a consequent also has Horse
as an antecedent and no binding.
If the order of predicates in the expansion was different, then the algorithm would have expanded the Parent
⇒ Offspring
predicate first. This would also have recursed infinitely alternating between the Parent
and Offspring
predicates.
If the order was such that "Bluebeard is a horse" was before "The offspring of a horse is a horse," then h would have bound to 'Bluebeard'
immediately.
How many solutions for h actually follow from the given sentences?
Bluebeard is identified as a horse. The offspring of a horse is also a horse and Charlie is Bluebeard's offspring, so Charlie is a horse as well. There are two solutions.
What is a method for finding all of them? (Smith et al. (1986) is potentially relevant.)
If, along a branch of the search tree, predicates with unbound variables were not repeated unless a binding had taken place in that predicate then it would force a constant reduction in the unbound elements in a given predicate. Then a depth-first search with backtracking to try all possible expansions should find all the possible bindings.
Given the following sentences in first-order logic:
Assume that the variables range over the natural numbers, 0,1,2,…,∞, and "≥" means "greater than or equal to." Under this interpretation, translate the sentences into English:
Is (A) true under this interpretation?
x and y are not qualified as being unequal, so:
The original statement then becomes:
Which is true, since it is true ∀x.
Is (B) true under this interpretation?
An existential statement needs only a single case to prove truth and for the natural numbers, every number is greater than or equal to 0, so the statement is true.
Does (A) logically entail (B)?
No. Assume that the domain for these numbers was ℝ rather than ℕ. (A) remains true in that there is always a number less than any given number. (B) ceases to be true because there is no longer a lower bound.
Does (B) logically entail (A)?
Yes. (B) identifies a specific value from the domain over which the statement is defined. That value can then always be used to satisfy (A), so if (B) is true then (A) will be as well.
Using resolution, attempt to prove that (A) follows from (B). Show the unifying substitution at each resolution step. If the proof fails, explain where, how and why it breaks down.
Using resolution, attempt to prove that (B) follows from (A). Show the unifying substitution at each resolution step. If the proof fails, explain where, how and why it breaks down.
This is true since a number is either greater than or equal to or not greater than or equal to another (P ∨ ¬P is true).
Consider the problem of planning a route for a robot to take from one city to another. The basic action taken by the robot is Go
(x,y), which takes it from city x to city y if there is a direct route between those cities. DirectRoute
(x,y) is true iff there is a direct route from x to y. Given a robot in Arad and attempting to reach Bucharest with a knowledge base modeling the following map:
Write a suitable logical description for the initial position of the robot.
The nature of this answer depends on the structure of how the reasoning system operates. The basic problem is that when the robot moves from one city to another, the fact of where it is changes. There are two basic approaches to this problem:
Universal Invariant Knowledge Base: The knowledge base essentially knows where the robot is at any point that it's knowledge spans. Since the robot is the only actor changing state in the world, an appropriate chronon, if ordering is the only needed function, would be a simple incremental count of the altered robot states. For this representation, the initial state would be:
At
('robot','Arad',0)
Which means "The robot is at Arad for step 0."
Dynamic Current Knowledge Base: The knowledge base represents the current known state of the world. So far as planning this is frequently a more convenient representation. Predicates don't exist in isolation, but are coupled with possibility and effects axioms that determine when a predicate may be applied and what the results of the application are. In this representation, the robot being at Arad would simply be written as:
At
('robot','Arad')
The predicate would be removed from the knowledge base by the Go
action.
Write a suitable logical query whose solutions will provide possible paths to the goal.
The following solutions will use the Universal Invariant Knowledge Base because more semantic information is captured in the knowledge base. This is not always desirable, but this method increases information demonstrated in the solution and not stored within the reasoning engine.
At
('robot','Bucharest',s)
The binding for s will be the number of steps it took to reach Bucharest.
Write a sentence describing the Go
action.
Go
(a,x,y) is read as a goes from x to y. This form is expanded a bit in an effort to provide greater efficiency. Specifically, it will never be productive to revisit a town that we have previously searched as a stop on the path. Since the knowledge base contains all previous states this seems relatively straightforward. The one condition is we may have visited a particular city at some point in the past before this particular Go
process and in that case, it should be considered.
The reasoning is as follows:
a goes from x to y starting at step s0 and ending at step s | Go (a,x,y,s0,s) |
if and only if | ⇔ |
the current city is the goal city | = (x,y) |
or ((this city has not been visited yet in the search |
∨ (¬(At (a,x,st)
∧ ≥ (st,s0)
|
other than currently) |
∨ (=(st,s) ∧ At (a,x,st)))
|
and the next city on the path is x' |
∧ DirectRoute (x,x')
|
and the next step for the robot is x') |
∧ Go (a,x,x',s0,s + 1))
|
Suppose that following the direct route between two cities consumes an equal amount of fuel to the distance between those cities. The robot starts with fuel at full capacity. Augment your representation to include these considerations. Your action description should be such that the query you specified earlier will still result in feasible plans.
Since the steps are uniquely numbered, the gas can simply be tracked separately for each step with the predicate Gas
(a,g,s) meaning agent a had a gas level of g at step s. A predicate GasCapacity
(b,c) will also be added to represent b has a gas capacity of c.
Describe the initial situation and write a new rule of rules describing the Go
action.
The initial is now.
At
('robot','Arad',0) ∧ GasCapacity
('robot',c) ∧ Gas
('robot',0,c)
a goes from x to y starting at step s0 and ending at step s | Go (a,x,y,s0,s) |
if and only if | ⇔ |
the current city is the goal city | = (x,y) |
or ((this city has not been visited yet in the search |
∨ (¬(At (a,x,st)
∧ ≥ (st,s0)
|
other than currently) |
∨ (=(st,s) ∧ At (a,x,st)))
|
and the next city on the path is x' |
∧ DirectRoute (x,x')
|
and the next step for the robot is x' |
∧ Go (a,x',y,s0,s + 1)
|
and there's enough gas to get to x' |
∧ (Gas (a,g,s)
∧ Distance (x',d)
∧ ≥ (g,d))
|
and the amount of gas for the next step is reduced) |
∧ Gas (a,g - d,s + 1))
|
Suppose some of your vertices are also gas stations, at which your robot can fill its tank. Extent the representation and write all the rules needed to describe gas stations, including the FillUp
action.
The new predicates would be:
There is a gas stating in x.
GasStationIn
(x)
The agent a is filled up at step s. a may or may not be at a gas station, maybe someone carries a gas can from a city with a gas station. It doesn't really matter the method. Additionally, the robot is always filled completely by the FillUp
action.
FillUp
(a,s) ⇒
GasCapacity
('robot',c) ∧ Gas
(a,c,s)
To make the representation clearer, I would move the adjustment of the gas level to an additional predicate which operates assuming that if a robot passes through a city with a gas station, it will fill up.
set the gas level for a at step s to level g | SetGas (a,s,g) |
implies | ⇒ |
the agent is in a city | At (a,x,s) ∧ |
if the city has a station, fill up | ((GasStationIn (x) ∧ FillUp (a,s)) |
otherwise set the level requested | ∨ (¬GasStationIn (x) ∧ Gas (a,g,s))) |
The original Go
predicate is modified as:
a goes from x to y starting at step s0 and ending at step s | Go (a,x,y,s0,s) |
if and only if | ⇔ |
the current city is the goal city | = (x,y) |
or ((this city has not been visited yet in the search |
∨ (¬(At (a,x,st)
∧ ≥ (st,s0)
|
other than currently) |
∨ (=(st,s) ∧ At (a,x,st)))
|
and the next city on the path is x' |
∧ DirectRoute (x,x')
|
and the next step for the robot is x' |
∧ Go (a,x',y,s0,s + 1)
|
and there's enough gas to get to x' |
∧ (Gas (a,g,s)
∧ Distance (x',d)
∧ ≥ (g,d))
|
and the amount of gas for the next step is reduced) |
∧ SetGas (a,g - d,s + 1))
|
Construct a representation for exchange rates between currencies that allows fluctuations on a daily basis.
The basic predicate will be Exchange
(n,c1,c2,d) which should be read as, "on date d, n of c1 was equal to one c2." So, Exchange
('0.68208','EUR','USD','2007-11-10') would be, "on Nov. 11, 2007, 0.68208 Euro was worth one US Dollar."
Primitive relationships between several of the major currencies would be defined. Since there are over 170 currencies, it is not realistic to define all permutations. Exchange
would therefore have, in addition to some primitive definitions, an an expansion similar to the route finding algorithm for the robot:
n of currency c1 is worth one unit of c2 on date d | Exchange (n,c1,c2,d) |
if and only if | ⇔ |
there is an intermediate currency on the conversion path between them |
Exchange (n1,c1,ci,d) ∧
Exchange (n2,ci,c2,d)
|
implies | ⇒ |
those rates combined form the rate for the requested exchange |
Exchange (n1 * n2,c1,c2,d)
|
Another potentially useful relationship to recognize is the inverse:
Exchange
(n,c1,c2,d) ⇔
Exchange
(1 / n,c2,c1,d)