Individual 3

1
London Metropolitan University
CS7051
Semantic Technologies
Group Coursework – I
Submitted By: Submitted To:

2
Contents
1. Satisfiability..............................................................................................3
2. Inference Rules........................................................................................5
3. Horn-Clause Conversion..........................................................................6
4. Resolution Rule........................................................................................7
3
Individual Work
1. Satisfiability
1. Every vehicle has a driver:

∀x Vehicle(x) → ∃y Driver(y) ∧ Drives(y, x)
 Given objects: Vehicles v1, v2, v3; Drivers d1, d2, d3.
 Associations: Driver d1 drives vehicle v1, driver d2 drives
vehicle v2, and driver d3 drives vehicle v3.
 Satisfiability: All vehicles v1, v2, and v3 have drivers related
with them (d1, d2, and d3, separately). Along these lines, this
heuristic is satisfiable.
2. Gas stations have fuel:

∀x GasStation(x) → ∃y Fuel(y) ∧ LocatedAt(y, x)
 Given objects: Gas stations g1, g2, g3; Fuel f1, f2, f3.
 Associations: gas station g1 has fuel f1, gas station g2 has fuel
f2, and gas station g3 has fuel f3.
 Satisfiability: All gas stations g1, g2, and g3 have fuel related to
them (f1, f2, and f3, individually). Thusly, this heuristic is
satisfiable.
3. Passengers are at stops:

∀x Passenger(x) → ∃y Stop(y) ∧ At(y, x)
 Given objects: Passengers p1, p2, p3; Stops s1, s2, s3.
 Associations: Passenger p1 is at stop s1, Passenger p2 is at
stop s2, and Passenger p3 is at stop s3.
4
 Satisfiability: All passengers p1, p2, and p3 are at their stops

(s1, s2, and s3, individually). Along these lines, this heuristic is
satisfiable.
4. Traffic lights are on roads:

∀x TrafficLight(x) → ∃y Road(y) ∧ LocatedAt(x, y)
 Given objects: Traffic lights t1, t2, t3; Roads r1, r2, r3.
 Associations: Traffic light t1 is located on road r1, traffic light t2
is located on road r2, and traffic light t3 is located on road r3.
 Satisfiability: All traffic lights t1, t2, and t3 are located on their
respective roads r1, r2, and r3. Therefore, this heuristic is
satisfiable.
5. Bicycles are used by passengers:

∀x Bicycle(x) → ∃y Passenger(y) ∧ Uses (y, x)
 Given objects: Bicycles b1, b2, b3; Passengers p1, p2, p3.
 Associations: Bicycle b1 is utilized by passenger p1, bicycle b2
is utilized by passenger p2, and bike b3 is utilized by passenger
p3.
 Satisfiability: All bicycles b1, b2, and b3 are utilized by their
separate passengers p1, p2, and p3. Thusly, this heuristic is
satisfiable.
5
2. Inference Rules
1. Heuristic: Every vehicle has a driver.

 ∀x Vehicle(x) → ∃y Driver(y) ∧ Drives(y, x)
 Given: Vehicle(v1)
 Inference: ∃y Driver(y) ∧ Drives(y, v1)
Universal Instantiation:
2. Heuristic: Gas stations have fuel.
 ∀x GasStation(x) → ∃y Fuel(y) ∧ LocatedAt(y, x)
 Given: GasStation(g1)
 Inference: ∃y Fuel(y) ∧ LocatedAt(y, g1)
Existential Introduction:
3. Heuristic: Passengers are at stops.
 ∀x Passenger(x) → ∃y Stop(y) ∧ At(y, x)
 Given: Passenger(p1)
 Inference: ∃y Stop(y) ∧ At(y, p1)
Modus Ponens:
4. Heuristic: Traffic lights are on roads.
 ∀x TrafficLight(x) → ∃y Road(y) ∧ LocatedAt(x, y)
 Given: TrafficLight(t1), Road(r1) ∧ LocatedAt(t1, r1)
 Inference: ∃y Road(y) ∧ LocatedAt(t1, y)
6
3. Horn-Clause Conversion
1. Facts:
 Fact 1: Gas station g1 has fuel f1.
 Fact 2: Gas station g2 has fuel f2.
 Fact 3: Passenger p1 is at stop s1.
 Fact 4: Passenger p2 is at stop s2.
 Fact 5: Traffic light t1 is located on road r1.
 Fact 6: Traffic light t2 is located on road r2.
2. Heuristics:
 Heuristic 1: Every vehicle has a driver.
 Heuristic 2: Gas stations have fuel.
 Heuristic 3: Passengers are at stops.
The Horn-clause representations for these facts and heuristics are as
follows:
1. Horn-clause for Facts:
 Fact 1: Fuel(f1) ∧ LocatedAt(f1, g1)
This fact can be represented as: Fuel(f1) ∧ LocatedAt(f1,
g1) ⇒ true

 Fact 2: Fuel(f2) ∧ LocatedAt(f2, g2)

This fact can be represented as: Fuel(f2) ∧ LocatedAt(f2,
g2) ⇒ true

 Fact 3: At(s1, p1)

 This fact can be represented as: At(s1, p1) ⇒ true
 Fact 4: At(s2, p2)
7
 This fact can be represented as: At(s2, p2) ⇒ true

 Fact 5: LocatedAt(t1, r1)
 This fact can be represented as: LocatedAt(t1, r1) ⇒ true
 Fact 6: LocatedAt(t2, r2)
 This fact can be represented as: LocatedAt(t2, r2) ⇒ true
2. Horn-clause for Heuristics:
 Heuristic 1: ∀x Vehicle(x) → ∃y Driver(y) ∧ Drives(y, x)
This heuristic can be represented as: Vehicle(x) ∧
¬Driver(y) ∧ Drives(y, x) ⇒ false

 Heuristic 2: ∀x GasStation(x) → ∃y Fuel(y) ∧ LocatedAt(y, x)

This heuristic can be represented as: GasStation(x) ∧
¬Fuel(y) ∧ LocatedAt(y, x) ⇒ false

 Heuristic 3: ∀x Passenger(x) → ∃y Stop(y) ∧ At(y, x)

This heuristic can be represented as: Passenger(x) ∧
¬Stop(y) ∧ At(y, x) ⇒ false.

4. Resolution Rule
1. Resolve Fact 1 and Heuristic 2:

 ¬Fuel(f1) ∨ LocatedAt(f1, g1) (Fact 1)
 ¬GasStation(g1) ∨ (∃y ¬Fuel(y) ∨ LocatedAt(y, g1)) (Heuristic
2)
 Resolve on ¬Fuel(f1)
 LocatedAt(f1, g1) ∨ (∃y ¬Fuel(y) ∨ LocatedAt(y, g1))
8
2. Resolve Fact 2 and Heuristic 2:

 ¬Fuel(f2) ∨ LocatedAt(f2, g2) (Fact 2)
 ¬GasStation(g1) ∨ (∃y ¬Fuel(y) ∨ LocatedAt(y, g1)) (Heuristic
2)
 Resolve on ¬Fuel(f2)
3. Resolve the above results with the fact that a gas station has fuel:
 Resolve on LocatedAt(f1, g1) and LocatedAt(f2, g2)
 (∃y ¬Fuel(y) ∨ LocatedAt(y, g1))

Individual 3

Uploaded by

Copyright:

Available Formats

Individual 3

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Individual 3

Uploaded by

Copyright:

Available Formats

1

London Metropolitan University

Submitted By: Submitted To:

1. Every vehicle has a driver:

2. Gas stations have fuel:

3. Passengers are at stops:

 Satisfiability: All passengers p1, p2, and p3 are at their stops

4. Traffic lights are on roads:

5. Bicycles are used by passengers:

1. Heuristic: Every vehicle has a driver.

 Fact 2: Fuel(f2) ∧ LocatedAt(f2, g2)

 Fact 3: At(s1, p1)

 This fact can be represented as: At(s2, p2) ⇒ true

 Heuristic 2: ∀x GasStation(x) → ∃y Fuel(y) ∧ LocatedAt(y, x)

 Heuristic 3: ∀x Passenger(x) → ∃y Stop(y) ∧ At(y, x)

1. Resolve Fact 1 and Heuristic 2:

2. Resolve Fact 2 and Heuristic 2:

You might also like