COMP111: Artificial Intelligence – Section 7(b). KR&R: Propositional Logic and Review
COMP111: Artificial Intelligence
Section 7(b). KR&R: Propositional Logic and Review
Frank Wolter
Propositional Logic
For many purposes, rules are not expressive enough. For example,
I one cannot express that something is not the case:
not FrenchFootballClub(LiverpoolFC)
I one cannot connect sentences using ‘or’:
Today, I will do the AI exercise or I will play football
Propositions
A proposition is a statement that can be true or false, but not
both at the same time!
I Logic is easy;
I I eat toast;
I 2 + 3 = 5;
I 2 · 2 = 5.
What about these?
I 4 + 5;
I Which city is the capital of the UK?
I Logic is not easy;
I Logic is easy or I eat toast;
Reasoning about propositions
The meeting takes place if all members have been
informed in advance, and it is quorate. It is quorate
provided that there are at least 15 people present.
Members will have been informed in advance if there is
not a postal strike.
Therefore,
If the meeting does not take place, we conclude that
there were fewer than 15 members present, or there was
a postal strike.
Understanding compound true/false propositions
The meeting takes place if all members have been
informed in advance, and it is quorate. It is quorate
provided that there are at least 15 people present.
Members will have been informed in advance if there is
not a postal strike. Therefore, if the meeting does not
take place, we conclude that there were fewer than 15
members present, or there was a postal strike.
Compound statements are built from atomic propositions — the
‘simplest’ statements that it is possible to make about the world
m: “the meeting takes place” a: “all members have been informed”
p: “there is a postal strike” q: “the meeting is quorate”
f : “there are at least 15 members present”
From
If a and q then m. If f then q. If not p then a.
conclude
If not m then not f or p.
Connectives
I Propositions may be combined with other propositions to
form compound propositions. These in turn may be combined
into further propositions.
I The connectives that may be used are
¬ not negation (∼)
∧ and conjunction (& or .)
∨ or disjunction (| or +)
⇔ if and only if equivalence (↔)
⇒ if . . . then implication (→)
I Some books use different notations. Some of these are given
in parentheses.
Propositional Formulas
The set of propositional formulas is defined as follows:
I Every atomic proposition is a propositional formula. We
denote atomic propositions by p, q, a, p1, p2, and so on.
I If P and Q are propositional formulas, then
I (P ∧ Q)
I (P ∨ Q)
I (P ⇒ Q)
I (P ⇔ Q)
are propositional formulas.
I If P is a propositional formula, then ¬P is a propositional
formula.
Example
The following are propositional formulas:
I p
I ¬¬p
I (p ∨ q)
I (((p ⇒ q) ∧ ¬q)⇒ ¬p)
The following are not propositional formulas:
I p ∧ q
I (p)
I (p ∧ q)¬q
Giving meaning to propositions: Truth values
An interpretation I assigns to every atomic proposition p a truth
value
I (p) ∈ {0, 1}.
I If I (p) = 1, then p is called true under the interpretation I .
I If I (p) = 0, then p is called false under the interpretation I .
Given an assignment I we can compute the truth value of
compound formulas step by step using truth tables.
Negation
The negation ¬P of a formula P
It is not the case that P
Truth table:
P ¬P
1 0
0 1
Examples
p: propositional logic is easy.
¬p: propositional logic is not easy.
q: The exam is in January.
¬q: It is not the case that the exam is in January
Conjunction
The conjunction (P ∧ Q) of P and Q.
both P and Q are true
Truth table:
P Q (P ∧ Q)
1 1 1
1 0 0
0 1 0
0 0 0
Examples
p: Logic is easy.
q: I eat toast.
(p ∧ q): Logic is easy and I eat toast
(¬p ∧ q): Logic is not easy and I eat toast
(¬p ∧ ¬q): Logic is not easy and I do not eat toast
Disjunction
The disjunction (P ∨ Q) of P and Q
at least one of P and Q is true
Truth table:
P Q (P ∨ Q)
1 1 1
1 0 1
0 1 1
0 0 0
Examples
p: I’ll have tea.
q: I’ll have coffee.
(p ∨ q): I’ll have tea or I’ll have coffee
Equivalence
The equivalence (P ⇔ Q) of P and Q
P and Q take the same truth value
Truth table:
P Q (P ⇔ Q)
1 1 1
1 0 0
0 1 0
0 0 1
Examples
p: You can take a flight.
q: You buy a ticket.
(p ⇔ q): You can take a flight if and only if you buy a ticket
Implication
The implication (P ⇒ Q) of P and Q
if P then Q
Truth table:
P Q (P ⇒ Q)
1 1 1
1 0 0
0 1 1
0 0 1
Truth under an interpretation
So, given an interpretation I , we can compute the truth value of
any formula P under I .
I If I (P) = 1, then P is called true under the interpretation I .
I If I (P) = 0, then P is called false under the interpretation I .
Example 1
List the interpretations I such that P = ((p1 ∧ ¬p2)⇒ (p2 ∧ ¬p1))
is true under I .
p1 p2 ¬p2 ¬p1 (p1 ∧ ¬p2) (p2 ∧ ¬p1) P
1 1 0 0 0 0 1
1 0 1 0 1 0 0
0 1 0 1 0 1 1
0 0 1 1 0 0 1
Remember the negation truth table:
P ¬P
1 0
0 1
Remember the conjunction truth table:
P Q (P ∧ Q)
1 1 1
1 0 0
0 1 0
0 0 0
Remember the implication truth table:
P Q (P ⇒ Q)
1 1 1
1 0 0
0 1 1
0 0 1
Thus, the interpretations I making P true are:
I I (p1) = 1 and I (p2) = 1
I I (p1) = 0 and I (p2) = 1
I I (p1) = 0 and I (p2) = 0
Example 2
How many interpretations I of p1, p2 and p3 are there such that
P = ((p1 ∨ p2)⇔ p3) is true under I?
p1 p2 p3 (p1 ∨ p2) P
1 1 1 1 1
1 1 0 1 0
1 0 1 1 1
1 0 0 1 0
0 1 1 1 1
0 1 0 1 0
0 0 1 0 0
0 0 0 0 1
Disjunction truth table:
P Q (P ∨ Q)
1 1 1
1 0 1
0 1 1
0 0 0
Equivalence truth table:
P Q (P ⇔ Q)
1 1 1
1 0 0
0 1 0
0 0 1
Thus, there are 4 interpretations making P true.
Example 3
How many interpretations I of p1, p2 and p3 are there such that
P = ((p1 ∨ ¬p2) ∧ p3) is true under I?
p1 p2 p3 ¬p2 (p1 ∨ ¬p2) P
1 1 1 0 1 1
1 1 0 0 1 0
1 0 1 1 1 1
1 0 0 1 1 0
0 1 1 0 0 0
0 1 0 0 0 0
0 0 1 1 1 1
0 0 0 1 1 0
Negation truth table:
P ¬P
1 0
0 1
Disjunction truth table:
P Q (P ∨ Q)
1 1 1
1 0 1
0 1 1
0 0 0
Conjunction truth table:
P Q (P ∧ Q)
1 1 1
1 0 0
0 1 0
0 0 0
Thus, there are 3 interpretations making P true.
Satisfiability
A propositional formula is satisfiable if there exists an
interpretation under which it is true.
Example. The formula (p ∧ ¬p) is not satisfiable, because
I (p ∧ ¬p) = 0
for all interpretations I :
p ¬p (p ∧ ¬p)
1 0 0
0 1 0
Example 1
P = (p1 ⇒ (p2 ∧ ¬p2)) is satisfiable.
To see this, simply choose any interpretation I with I (p1) = 0.
Then I (P) = 1 and we have found an interpretation I that makes
P true.
The same argument shows that every formula of the form
(p1 ⇒ Q) is satisfiable.
Example 2
P = (p1 ⇔ ((p2 ∧ ¬p3) ∧ p4)) is satisfiable.
To see this, let I be any interpretation of p2, p3, p4. Compute
I (((p2 ∧ ¬p3) ∧ p4))
Then let I (p1) = I (((p2 ∧ ¬p3) ∧ p4)). I is an interpretation that
makes P true.
The same argument shows that every formula of the form
(p1 ⇔ Q) such that p1 does not occur in Q is satisfiable.
Note that (p1 ⇔ ¬p1) is not satisfiable. So the condition that p1
does not occur in Q is needed.
Deciding satisfiability
I P is satisfiable if I (P) = 1 for some interpretation I .
I There are 2n interpretations if P has n propositional atoms.
I Thus, to check whether P is satisfiable directly using truth
tables, a table with 2n rows is needed.
I This is not practical, even for small n (such as 100):
combinatorial explosion again.
I There has been great progress in developing very fast
satisfiability checking algorithms (called SAT solvers) that can
deal with formulas with very large numbers of propositional
atoms (using heuristics again).
A Knowledge Base
The meeting can take place if all members have been
informed in advance, and it is quorate. It is quorate
provided that there are at least 15 people present.
Members will have been informed in advance if there is
not a postal strike.
Consequence: Therefore, if the meeting was cancelled,
we conclude that there were fewer than 15 members
present, or there was a postal strike.
Let
m: “the meeting takes place” a: “all members have been informed”
p: “there is a postal strike” q: “the meeting is quorate”
f : “there are at least 15 members present”
Then the text can be formalised as the following knowledge base:
((a ∧ q)⇒ m), (f ⇒ q), (¬p ⇒ a)
Propositional Knowledge Bases and Reasoning
A propositional knowledge base X is a finite set of propositional
formulas.
Suppose a propositional knowledge base X is given. Then a
propositional formula P follows from X if the following holds for
every interpretation I :
If I (Q) = 1 for all Q ∈ X , then I (P) = 1.
This is denoted by
X |= P.
Example. We have seen that:
{((a ∧ q)⇒ m), (f ⇒ q), (¬p ⇒ a)} |= (¬m⇒ (¬f ∨ p))
Example 1
Show {(p1 ∧ p2)} |= (p1 ∨ p2).
p1 p2 (p1 ∧ p2) (p1 ∨ p2)
1 1 1 1
1 0 0 1
0 1 0 1
0 0 0 0
Thus, from I (p1 ∧ p2) = 1 it follows that I (p1 ∨ p2) = 1.
But {(p1 ∨ p2)} 6|= (p1 ∧ p2) since there exists an interpretation I
with I (p1 ∨ p2) = 1 and I (p1 ∧ p2) = 0. For example, I (p1) = 1
and I (p2) = 0.
Example 2
Show {p1, p1 ⇒ p2} |= p2.
p1 p2 (p1 ⇒ p2)
1 1 1
1 0 0
0 1 1
0 0 1
Thus, whenever I (p1) = 1 and I (p1 ⇒ p2) = 1, then I (p2) = 1.
But {p1, p2 ⇒ p1} 6|= p2. This is shown by the interpretation I
with I (p1) = 1 and I (p2) = 0.
Reasoning
I X |= P if I (P) = 1 for all interpretations I such that I (Q) = 1
for all Q ∈ X .
I There are 2n different relevant interpretations if P and X
together have n propositional atoms.
I Thus, to check X |= P directly using truth tables, a table with
2n rows is needed.
I X |= P can be checked using a SAT solver: assume that X
contains P1, . . . ,Pn and let
Q = P1 ∧ · · · ∧ Pn ∧ ¬P
Then
X |= P if and only if Q is not satisfiable
{P1, . . . ,Pn} |= P and satisfiability of P1 ∧ . . . ∧ Pn ∧ ¬P
Let X = {P1, . . . ,Pn} be a knowledge base.
P follows from X if for every interpretation I , if I (Pi ) = 1 for all
Pi ∈ X , then I (P) = 1.
P does NOT follow from X if there exists an interpretation I such
that I (Pi ) = 1 for all Pi ∈ X , but I (P) = 0 (I (¬P) = 1).
P does NOT follow from X if P1 ∧ . . . ∧ Pn ∧ ¬P is satisfiable.
P follows from X if P1 ∧ . . . ∧ Pn ∧ ¬P is NOT satisfiable.
What is the point?
Different points of view can lead to different techniques
I different algorithms
I different heuristics
for example, checking all interpretations vs looking for one
Summary
I In KR&R knowledge is stored in a knowledge base. Reasoning
is needed to make implicit knowledge explicit.
I We have considered rule-based and propositional knowledge
bases and corresponding reasoning.
I In the rule-based case we have given reasoning algorithms.
I Databases only store atomic assertions. In contrast,
knowledge bases store knowledge that goes beyond atomic
assertions (such as rules and compound propositions).
I Knowledge stored in knowledge bases is mostly incomplete,
whereas knowledge stored in databases is mostly complete.
I Many other KR&R languages with corresponding reasoning
algorithms have been developed.
How to apply what we have learned?
When facing a new problem, ask yourself
I can I use any of the KR languages I know?
I Answer depends on whether any of the KR languages is
sufficiently expressive to model the problem.
Modelling Example
The meeting can take place if all members have been
informed in advance, and it is quorate. It is quorate
provided that there are at least 15 people present.
Members will have been informed in advance if there is
not a postal strike. Therefore, if the meeting was
cancelled, we conclude that there were fewer than 15
members present, or there was a postal strike.
m: “the meeting takes place” a: “all members have been informed”
p: “there is a postal strike” q: “the meeting is quorate”
f : “there are at least 15 members present”
The problem can be modelled as
{((a ∧ q)⇒ m), (f ⇒ q), (¬p ⇒ a)} |= (¬m⇒ (¬f ∨ p))
Recalling Examples: Example 1
Consider the following knowledge base:
I If I have an AI lecture today, then it is Tuesday or Friday.
I It is not Tuesday.
I I have an AI lecture today or I have no class today.
I If I have no class today, then I am sad.
I I am not sad.
Can you infer what day it is?
Can we model it using the rule-based approach?
I No, some concepts cannot be expressed. For example, “it is
Tuesday or Friday”, and “it is not Tuesday”.
We can model it using propositional logic.
Recalling Examples: Example 2
Consider the following medical knowledge base:
I Pericardium is a tissue contained in the heart
I Pericarditis is an inflammation located in the pericardium
I Inflammation is a disease that acts on tissue
I A disease located in something contained in the heart is a
heartdisease
Can you infer that pericarditis is a heartdisease?
Can we model it using propositional logic?
I No, some concepts cannot be expressed. For example, we
cannot express “any inflammation is a disease”.
We can model it using a rule-based approach.
Modelling Example 2
Representation in Rule-Based Language. Let K be the following
knowledge base.
Tissue(Pericardium), ContinHeart(Pericardium)
Inflammation(Pericarditis)
LocatedIn(Pericarditis,Pericardium)
Inflammation(x)⇒ Disease(x)
Disease(x) ∧ LocatedIn(x , y) ∧ contInHeart(y)⇒ Heartdisease(x)
Then
K |= Heartdisease(Pericarditis)
Modelling Example 1
Consider the following knowledge base:
I If I have an AI lecture today, then it is Tuesday or Friday.
I It is not Tuesday.
I I have an AI lecture today or I have no class today.
I If I have no class today, then I am sad.
I I am not sad.
Can you infer what day it is?
Which means: is it Monday? Is it Tuesday? . . . Is it Friday?
Let us focus only on the question: is it Friday?
Modelling Example 1: propositions
Consider the following knowledge base:
I If I have an AI lecture today, then it is Tuesday or Friday.
I It is not Tuesday.
I I have an AI lecture today or I have no class today.
I If I have no class today, then I am sad.
I I am not sad.
What propositions do we need?
a: “I have an AI lecture today” c : “I have class today”
t: “it is Tuesday” f : “it is Friday”
s: “I am sad”
Modelling Example 1: rewriting the knowledge base
Consider the following knowledge base:
I If I have an AI lecture today, then it is Tuesday or Friday.
I (a⇒ (t ∨ f ))
I It is not Tuesday.
I ¬t
I I have an AI lecture today or I have no class today.
I (a ∨ ¬c)
I If I have no class today, then I am sad.
I (¬c ⇒ s)
I I am not sad.
I ¬s
Our propositions
a: “I have an AI lecture today” c : “I have class today”
t: “it is Tuesday” f : “it is Friday”
s: “I am sad”
Modelling Example 1: is it Friday?
Let us define some abbreviation:
I P1 = (a⇒ (t ∨ f ))
I P2 = ¬t
I P3 = (a ∨ ¬c)
I P4 = (¬c ⇒ s)
I P5 = ¬s
And X = {P1,P2,P3,P4,P5}
Checking if it is Friday corresponds to check whether X |= f holds.
Alternatively: is P1 ∧ P2 ∧ P3 ∧ P4 ∧ P5 ∧ ¬f not satisfiable?.
Remember:
X |= f if and only if P1 ∧ P2 ∧ P3 ∧ P4 ∧ P5 ∧ ¬f is not satisfiable
Modelling Example 1: does X |= f hold?
We have 5 propositions, meaning 25 rows using a truth table. Let
us try to avoid a huge truth table.
We show using a proof by contradiction that
P1 ∧ P2 ∧ P3 ∧ P4 ∧ P5 ∧ ¬f is not satisfiable. Thus, assume that
P1 ∧ P2 ∧ P3 ∧ P4 ∧ P5 ∧ ¬f is satisfiable. Then there is an
interpretation I such that
I I (P1) = 1, I (P2) = 1, . . . , I (P5) = 1, and I (¬f ) = 1;
I I (¬f ) = 1 means I (f ) = 0;
I since P2 = ¬t and P5 = ¬s, then I (t) = 0 and I (s) = 0;
I since P4 = (¬c ⇒ s), then I (P4) = 1 only if I (c) = 1;
I since P1 = (a⇒ (t ∨ f )), then I (P1) = 1 only if I (a) = 0;
I since P3 = (a ∨ ¬c), then I (P3) = 0!
We have derived a contraction as I (P3) = 1 and I (P3) = 0.
Thus, X |= f holds.
Not always that easy
How would you model this using propositional logic?
7 4 1
3 2 6
1 7 4 5 2 3
4 1 6 8
2 9 7 6 3
7 4 2 1
7 5 2 6 3 9
3 4 1
1 4 3
What propositions?
Hint: number x is in row y and column z
What to model?
I at least one number per cell (pair of
row and column)
I at most one number per cell (pair of
row and column)
I no number can be repeated in a row
I no number can be repeated in a column
I no number can be repeated in a region