A progression of logical languages
Propositional logic programs: atoms have no arguments. Datalog: allow for logical variables in clauses and queries. Prolog: Datalog + function symbols
CPSC 312 — Lecture 18 1 / 11
©D. Poole 2021
A progression of logical languages
Propositional logic programs: atoms have no arguments. Datalog: allow for logical variables in clauses and queries. Prolog: Datalog + function symbols
CPSC 312 — Lecture 18 1 / 11
©D. Poole 2021
Propositional Logic Program Syntax
An atom is of the form p, a word that (can contain letters, digits and underscore ) and starts with a lower-case letter.
CPSC 312 — Lecture 18 2 / 11
©D. Poole 2021
Propositional Logic Program Syntax
An atom is of the form p, a word that (can contain letters, digits and underscore ) and starts with a lower-case letter. A body is either
an atom or
(b1, b2) where b1 and b2 are bodies. (Parentheses are
optional). A comma in a body means “and”.
CPSC 312 — Lecture 18 2 / 11
©D. Poole 2021
Propositional Logic Program Syntax
An atom is of the form p, a word that (can contain letters, digits and underscore ) and starts with a lower-case letter. A body is either
an atom or
(b1, b2) where b1 and b2 are bodies. (Parentheses are
optional). A comma in a body means “and”. A definite clause is either
an atomic clause: an atom or
arule: h:-bwherehisanatomandbisabody.
:- means “if”
An atomic clause is treated as a rule with an empty body. All definite clauses ends with a period “.”
CPSC 312 — Lecture 18 2 / 11
©D. Poole 2021
Propositional Logic Program Syntax
An atom is of the form p, a word that (can contain letters, digits and underscore ) and starts with a lower-case letter. A body is either
an atom or
(b1, b2) where b1 and b2 are bodies. (Parentheses are
optional). A comma in a body means “and”. A definite clause is either
an atomic clause: an atom or
arule: h:-bwherehisanatomandbisabody.
:- means “if”
An atomic clause is treated as a rule with an empty body. All definite clauses ends with a period “.”
A logic program or knowledge base is a set of definite clauses
A query is a body that is asked at the Prolog prompt (ended with a period).
CPSC 312 — Lecture 18 2 / 11
©D. Poole 2021
Datalog Syntax
An atom is of the form p(t1,…,tn) or p
p is a predicate symbol, a word that starts with lower-case letter
CPSC 312 — Lecture 18 3 / 11
©D. Poole 2021
Datalog Syntax
An atom is of the form p(t1,…,tn) or p
p is a predicate symbol, a word that starts with lower-case
letter
A word can contain letters, digits and underscore each ti is a term which is either:
a constant: a number or a word starting with a lower-case letter
a logical variable: a word starting with an upper-case letter or _
CPSC 312 — Lecture 18 3 / 11
©D. Poole 2021
Datalog Syntax
An atom is of the form p(t1,…,tn) or p
p is a predicate symbol, a word that starts with lower-case
letter
A word can contain letters, digits and underscore each ti is a term which is either:
a constant: a number or a word starting with a lower-case letter
a logical variable: a word starting with an upper-case letter or _ In a clause, a variable means “for all”. E.g.: grandmother(X,Z) :- mother(X,Y), parent(Y,Z).
CPSC 312 — Lecture 18 3 / 11
©D. Poole 2021
Datalog Syntax
An atom is of the form p(t1,…,tn) or p
p is a predicate symbol, a word that starts with lower-case
letter
A word can contain letters, digits and underscore each ti is a term which is either:
a constant: a number or a word starting with a lower-case letter
a logical variable: a word starting with an upper-case letter or _
In a clause, a variable means “for all”. E.g.:
grandmother(X,Z) :- mother(X,Y), parent(Y,Z).
In a query, a variable is asking whether there exists an instance that makes the query follow from knowledge base. E.g.:
?- grandmother(G,xavier).
CPSC 312 — Lecture 18 3 / 11
©D. Poole 2021
Electrical Environment
cb1
w5
outside power
circuit breaker
off
on switch
two-way switch
light
power outlet
s1
cb2
s2 w1 w2
s3
w3
w6
p2
p1
w0
w4
l1
l2
©D. Poole 2021
CPSC 312 — Lecture 18 4 / 11
Example Knowledge Base (elect prop.pl)
light l1. light l2. down s1. up s2. up s3. ok l1.
ok l2.
ok cb1.
ok cb2.
live outside.
lit l1 :- live w0, ok l1
live w0 :- live w1, up s2. live w0 :- live w2, down s2. live w1 :- live w3, up s1. live w2 :- live w3, down s1. lit l2 :- live w4, ok l2.
live w4 :- live w3,
live p1 :- live w3.
live w3 :- live w5,
live p2 :- live w6.
live w6 :- live w5,
live w5 :- live outside.
up s3. ok cb1. ok cb2.
©D. Poole 2021
CPSC 312 — Lecture 18 5 / 11
Human’s view of semantics
Step 1 Step 2
Step 3
Step 4
Begin with a task domain.
Choose atoms in the computer to denote propositions. These atoms have meaning to the KB designer.
Tell the system knowledge about the domain.
Ask the system questions.
— The system gives answers.
— Person can interpret the answer with the meaning associated with the atoms.
©D. Poole 2021
CPSC 312 — Lecture 18 6 / 11
Electrical Environment
cb1
w5
outside power
circuit breaker
off
on switch
two-way switch
light
power outlet
s1
cb2
s2 w1 w2
s3
w3
w6
p2
p1
w0
w4
l1
l2
©D. Poole 2021
CPSC 312 — Lecture 18 7 / 11
Role of semantics in electrical domain
In user’s mind:
light1 broken: light 1 is broken
sw1 up: switch 1 is up sw2 up: switch 2 is up
power: there is power in the building
unlit light1: light 1 isn’t lit
lit light2: light 2 is lit
The computer doesn’t know the meaning of the symbols
The user can interpret the symbol using their meaning
In computer:
light1 broken :- sw1 up,
sw2 up, power, unlit light1.
sw1 up.
sw2 up.
power :- lit light2. unlit light1.
lit light2.
Conclusion: light1 broken
CPSC 312 — Lecture 18 8 / 11
©D. Poole 2021
Semantics
An interpretation I assigns a truth value to each atom.
True of compound propositions in interpretation is derived from truth table:
p qp,qp:-q true true true true true false false true
false true false false false false false true
CPSC 312 — Lecture 18
9 / 11
©D. Poole 2021
Semantics
An interpretation I assigns a truth value to each atom. True of compound propositions in interpretation is derived
from truth table:
Abody(b1, b2)istrueinI if
p qp,qp:-q true true true true true false false true
false true false false false false false true
CPSC 312 — Lecture 18
9 / 11
©D. Poole 2021
Semantics
An interpretation I assigns a truth value to each atom. True of compound propositions in interpretation is derived
from truth table:
p qp,qp:-q true true true true true false false true
false true false false false false false true
Abody(b1, b2)istrueinI ifb1 istrueinI andb2 istrueinI. Aruleh:-bisfalseinI if
CPSC 312 — Lecture 18 9 / 11
©D. Poole 2021
Semantics
An interpretation I assigns a truth value to each atom. True of compound propositions in interpretation is derived
from truth table:
p qp,qp:-q true true true true true false false true
false true false false false false false true
Abody(b1, b2)istrueinI ifb1 istrueinI andb2 istrueinI.
Aruleh:-bisfalseinI ifbistrueinI andhisfalseinI. The rule is true otherwise.
CPSC 312 — Lecture 18 9 / 11
©D. Poole 2021
Semantics
An interpretation I assigns a truth value to each atom. True of compound propositions in interpretation is derived
from truth table:
p qp,qp:-q true true true true true false false true
false true false false false false false true
Abody(b1, b2)istrueinI ifb1 istrueinI andb2 istrueinI. Aruleh:-bisfalseinI ifbistrueinI andhisfalseinI.
The rule is true otherwise.
A knowledge base KB is true in I if and only if every clause in KB is true in I.
CPSC 312 — Lecture 18 9 / 11
©D. Poole 2021
Models and Logical Consequence
A model of a set of clauses is an interpretation in which all the clauses are true.
CPSC 312 — Lecture 18 10 / 11
©D. Poole 2021
Models and Logical Consequence
A model of a set of clauses is an interpretation in which all the clauses are true.
If KB is a set of clauses and g is a conjunction of atoms, g is a logical consequence of KB, written KB |= g, if g is true in every model of KB.
CPSC 312 — Lecture 18 10 / 11
©D. Poole 2021
Models and Logical Consequence
A model of a set of clauses is an interpretation in which all the clauses are true.
If KB is a set of clauses and g is a conjunction of atoms, g is a logical consequence of KB, written KB |= g, if g is true in every model of KB.
That is, KB |= g if there is no interpretation in which KB is true and g is false.
CPSC 312 — Lecture 18 10 / 11
©D. Poole 2021
Models and Logical Consequence
A model of a set of clauses is an interpretation in which all the clauses are true.
If KB is a set of clauses and g is a conjunction of atoms, g is a logical consequence of KB, written KB |= g, if g is true in every model of KB.
That is, KB |= g if there is no interpretation in which KB is true and g is false.
Prolog says “yes” to a query if the query is a logical consequence; otherwise it says “no”.
(SWI Prolog uses true and false).
CPSC 312 — Lecture 18 10 / 11
©D. Poole 2021
©D. Poole 2021
CPSC 312 — Lecture 18 11 / 11