COMP 1.41 INTRODUCTION TOLOGIC
1
Logic and AI Programming:
Introduction to Logic
Introduction to Prolog
F. SADRI
Autumn Term
October – December
2
Course Material
Course material will be available via CATE,
including:
Notes
Tutorial Exercises
Tutorial Exercise Solutions
Coursework
3
CONTENTS
Introduction to logic
Propositional logic
• Syntax
• Semantics (Truth Tables)
• Rules of inference (Natural Deduction)
Predicate logic
• Syntax
• Informal semantics
• Rules of inference (Natural Deduction)
Prolog programming
Time permitting:Probabilistic Prologor
Abductive Reasoniong
4
Books
background reading on logic
• Any book on logic will have useful examples.
• Richard Spencer-Smith, Logic and Prolog,
Harvester Wheatsheaf, (The library has a
number of copies)
• Jim Woodcock and Martin Loomes, Software
Engineering Mathematics”, Pitman Publishing
5
Books
Prolog
• Ivan Bratko, “Prolog programming for
artificial intelligence“, Addison-Wesley,
Third Edition, 2001 and later.
Assessments and Examination
• One Logic Coursework
• One Prolog Lab Assessment
• One Examination in May:
Paper M1 (Program Design and Logic) will have:
– two questions on Logic and
– two questions on Object-Oriented Design
6
Relevance of this course to
Spring Term Modules
• Logic-based Learning course
• Introduction to Artificial Intelligence
• System Verification
• Argumentation and Multi-Agent Systems
7
and to a lesser extent
• Databases
– Database languages, e.g. relational calculus and
some features of SQL
– Datalog: emerging e.g. in data integration,
information extraction, network monitoring,
security and cloud computing
8
Logic has many applications in
computing
For example:
• Basis of a family of programming
languages, e.g. Prolog, ASP (Answer Set
Programming).
• Basis of verification tools to reason about
C, Java and JavaScript programs, and
algorithms for concurrency, e.g. using
Separation Logic.
9
• Software engineering: Formal specifications
and formal verification of programs.
How do you make sure a program is
“correct”?
Review, again and again and ….
– Review the spec
– Review the design description
– Review the code
10
Test, again and again and ….
– Unit testing
– Integration testing
– Validation testing
11
But that is not enough.
How many tests do you run to be sure the
system is correct?
Logic provides a way of proving the system
correct and
this can be automated too.
12
13
Logic is also useful more
generally in life
• Clear thinking
• Judging validity of arguments and
justification of conclusions
• Spotting inconsistencies
• Awareness and avoidance of ambiguities of
natural language
14
Which of the following
arguments are valid?
Advertisement for a computing book: If you
don’t use computers you don’t need this
book.But you are a person who uses
computers.So you need this book.
If you work hard you will succeed. So if
you do not succeed you have not worked
hard.
15
Which of the following
arguments are valid?
Heard in a radio interview with a well-
known politician: All our problems have
come from the EU. So nothing good has
resulted for us from our membership of the
EU.
More reasoning exercises
1. All the trees in the park are flowering trees.
2. Some of the trees in the park are dogwoods.
3. All dogwoods in the park are flowering trees.
If the first two statements are true, the third
statement is
A. true
B. false
C. uncertain
16
More reasoning exercises
1. All the tulips in Zoe’s garden are white.
2. All the roses in Zoe’s garden are yellow.
3. All the flowers in Zoe’s garden are either white or yellow
If the first two statements are true, the third statement is
A. true
B. false
C. uncertain
17
More reasoning exercises
Fact 1: All dogs like to run.
Fact 2: Some dogs like to swim.
Fact 3: Some dogs look like their owners.
If these three statements are facts, which of the following statements
must also be a fact?
I. All dogs who like to swim look like their owners.
II. Dogs who like to swim also like to run.
III. Dogs who like to run do not look like their owners.
A. I only
B. II only
C. II and III only
D. None of the statements is a known fact.
18
Some arguments –
Are they valid?
It has been proven that all heroin addicts
smoked marijuana in their youth. Therefore,
smoking marijuana leads to heroin
addiction.
We cannot win the war on poverty without
spending money.So if we do spend money
we will conquer poverty.
19
20
Another argument – Is it valid?
One of the old arguments of tobacco spokesmen
against the claim that smoking causes lung cancer:
Lung cancer is more common among male
smokers than it is among female smokers.If
smoking were the cause of lung cancer, this would
not be true.The fact that lung cancer is more
common among male smokers means that it is
caused by something in the male make-up.If
follows that lung cancer is not caused by smoking,
but something in the male make-up.
Propositional Logic
• A good place to start.
• It is the core of many logics.
21
22
Components of a logic
• Language:
– alphabet : symbols
– syntax : rules for putting together the symbols
to make grammatically correct sentences.
• Semantics:
meaning of the symbols and the sentences.
• Inference rules
23
The Propositional Language:
Alphabet
• Propositional symbols
e.g. use_computers, need_book, p, q, r, s, p1
• Logical connectives:
:and (conjunction)
:(inclusive) or (disjunction)
:not (negation)
sometimes denoted as ~
: implication (if-then)
: double implication(if and only if)
24
The Propositional Language:
Syntax of a grammatically correct sentence
(well formed formula, wff)
• A propositional symbol is a wff.
• If W, W1 and W2 are wffs then so are
(W) sometimes written as ~(W)
(W1 W2)
(W1 W2)
(W1 W2) (W2 W1)
(W1 W2)
• There are no other wffs.
25
Examples
Suppose p, q, r, s, t are propositions. Then:
(p q) is a wff
(r t) is not a wff
(p q)is not a wff
((p q)((p r) (s)))is a wff
((p q)((p r) (s)))
Draw a parse tree.
26
Examples
Passing the exams and the project implies
passing the MSc.
(pass_exams pass_proj) pass_MSc
You do not pass the MSc and you do not get a
certificate if you do not pass the exams or you do
not pass the project.
( pass_exams ¬ pass_proj)
(¬ pass_MSc get_certificate)
27
Exercise
Formulate the first two arguments from the
beginning of the notes.
Advertisement for a computing book: If you don’t
use computers you don’t need this book.But you
are a person who uses computers.So you need
this book.
If you work hard you will succeed. So if you do
not succeed you have not worked hard.
28
Some notes on simplifying
syntax
• To avoid ending up with a large number of
brackets one can drop the outermost
brackets.
Examples:
(p q) can be written as p q
((p q) r) can be written as (p q) r.
29
• “ “ binds more closely than the other
connectives.This can be used to drop some
brackets.
Example
( (p) q) t can be written as
( p q) t
30
• and bind more closely than and . This
can be used to drop some brackets.
Examples:
( p q) t can be written as
p q t.
(p q) (r s) can be written as
p q r s.
Binding Strength
of the Connectives
To avoid having to use many brackets, there is
a convention of ordering the connectives.
Also :
• Order of precedence
• Binding priority
31
Binding Strength
of the Connectives
Strongest ¬
Weakest
32
Binding conventions: Examples
• p q r is understood as p (q r)
• ¬p qis understood as (¬p) q
• pqr is understood as (pq)r
I prefer the first and third bracketed versions.
They are more clear, and having a few
brackets is not much of a burden! Please
don’t write unreadable formulas like
p ¬q → ¬r ↔ ¬¬s ∧ t ¬u
33
34
Use brackets to remove
ambiguity
Example:
P Q R
is ambiguous.
In general
P (Q R)
and
(P Q) R
are not equivalent (do not have the same meaning).
Binding conventions
Sop q r
is a problem.
It needs brackets to disambiguate it.
But p ∧ q ∧ rand p ∨ q ∨ r
are fine (to be discussed later).
35
36
Exercise:
Which of the following are wffs?
Assume
p, q, r, sad, happy,
tall, rich, work_hard,
steal, borrow, and possess
are propositional symbols.
37
• rich happy
• (p q)(r p)
• pq
• sadhappy
• happysad
38
• richhappy
• rich(work_hard steal)
• (steal borrow)possess
• (steal borrow)possess
• steal borrowpossess
39
• (pq r) (p q)
• p p
• p p
We will look at
Parse trees
Principle connectives
Subformulas
in the lecture.
40
41
Notes on terminology
• is a unary operator.
• The other connectives are binary operators.
• X Yis called the disjunction of X and Y.
• X Y X and Y are disjuncts.
• X Yis called the conjunction of X and Y.
• X Y X and Y are conjuncts.
• X is called the negation of X.
Notes on terminology cntd.
• A → Bis called an implication.
A is called the antecedent,
B is called the consequent.
A Literal is a proposition or the negation of a
proposition.
42
Semantics
Provides
• The meaning of the simple (atomic) units
• Rules for putting together the meaning of
the atomic units to form the meaning of the
complex units (sentences).
Semantics specifies under what circumstances
a sentence is true or false.
43
44
T (truth) and
F (falsity)
are known as truth values.
45
Constructing Truth Tables for
the connectives
A A
T F
F T
46
A B A B
T T T
T F F
F T F
F F F
47
Example
John is not happy, but he is comfortable.
Represent as h c
Four possible cases
48
Example cntd.
h c h h c
T T F F
T F F F
F T T T
F F T F
49
A B AB
T T T
T F T
F T T
F F F
50
A B AB
T T T
T F F
F T T
F F T
51
Compare with
A B A B
T T T
T F F
F T F
F F F
A B AB
T T T
T F F
F T T
F F T
52
A B AB
T T T
T F F
F T F
F F T
53
Note
For any wffs A and B,“A B”is true
exactly when A and B have the same truth
values, i.e. when they are both true or both
false.
54
The truth value of a wff is uniquely
determined by the truth value of its
components.
Example:
The truth table for the wff (p q) (r p)
is as follows:
55
pq r p qr p (p q) (r p)
TT T T TT
TT F T TT
TF T T TT
TF F T TT
FT T T FF
FT F T TT
FF T F FF
FF F F TF
56
Exercise:
How many rows will there be in a truth table
for a wff containing n propositional
symbols?
2n
57
Exercise:
Recall we said the two wffs
P (Q R)and
(P Q) R
in general do not have the same meaning.
Under which interpretation(s)do the truth values of
the two wffs differ?
58
Notes
The connective “” stands for inclusive or, i.e.
p q is interpreted as true when either
proposition is true or both are.
Often in English when we use “or” we intend
exclusive or, e.g.
• I’ll go shopping or I’ll stay at home.
• We will meet at his house or at the club.
59
Notes cntd.
In this propositional language there is no connective
for exclusive or, but we can still express the
concept, e.g.
(goShopping stayHome)
(goShopping stayHome)
In general“p exor q”can be represented as:
(p q) (p q)
Exercise:
Draw the truth table of the first wff above.
60
A B AB ¬(AB) A exor B
(AB) ¬(AB)
T T T F F
T F T T T
F T T T T
F F F T F
61
Notes cntd.
• Law of excluded middle:
A proposition (and consequently a wff) is either
true or false – there is no middle ground, no
“unknown”.
• So propositional logic is a 2-valued logic.
• There are other logics, including 3-valued ones.
• SQL, for example, implements 3-valued logic,
where comparisons with NULL, including that of
another NULL gives UNKNOWN.
Example NULL Values
Table T of people and their hair colours:
NameHat SizeHair Colour
Helen NULLBrown
JohnMediumRed
TomLargeNULL
Select Name
From T
Where Hat Size=Large AND Hair Colour Brown
62
63
A B A B
T T T
T F T
F T T
F F F
T U T
U T T
F U U
U F U
U U U
• A proposition (and consequently a wff)
cannot be both true and false.
Exercise:
Draw the truth table forA A.
64
65
A ¬A A A
T F F
F T F
66
Notes cntd.
• The interpretation of “” may be
unintuitive sometimes.
• The semantics of “” is very simple in
logic.
• A B is simply the same as A B.
• In English we use “ if .. then” in many
different ways, and sometimes quite
confusingly.
• Don’t read A B as “A causes B”.
67
Some definitions
Definition :
A wff which evaluates to true in every interpretation
of its constituent parts is called a tautology.
ExampleA A
A A
The two wffs above represent the Law of excluded
middle.
68
A ¬A A ¬A
T F T
F T T
69
Definition
A wff which evaluates to false in every
interpretation of its constituent parts is
called an inconsistency (contradiction), or
is said to be inconsistent.
ExampleA A
70
Definition
A wff which is neither a tautology, nor an
inconsistency is a contingency, or is said to
be contingent.
71
Exercise
For each of the following determine if it is a
tautology, inconsistency or contingency by
drawing the truth table.
a. P (P Q)
b. (P Q) (P Q)
c. Q P (P (Q P))
d. (P (Q P)) P
e. (P Q) ( P Q)
f. ((P Q) (R S) (P R)) (Q S)
72
Definition: Equivalence
Two wffs are equivalent iff their truth values
are the same under every interpretation.
A is equivalent to B is represented as
A B .
“” is the metasymbol for equivalence.
73
Some useful equivalences
Double Negation Rule
A A
Implication Rule
A BA B
74
Some useful equivalences
Commutative Rules
A BB A
A BB A
Associative Rules
(A B) CA (B C)
(A B) CA (B C)
Some useful equivalences
Idempotence
A ∧ A A
A ∨ A A
75
76
Some useful equivalences
Distributive Rules
A (B C)(A B) (A C)
A (B C)(A B) (A C)
De Morgan’s Rules
(A B)A B
(A B)A B
Some useful equivalences
A↔ B
(A → B) ∧ (B → A)
77
Some useful equivalences
A ∧ B Bif????
A ∧ B Bif A is a tautology
A B B if ????
A B B if A is an inconsistency
78
79
Exercise
Show
A B (A B)
Example
I get an MSc I get big salary
(I get an MSc I get big salary )
Exercises
Show
A B (A B) ( A B)
Show
A B ¬A ¬B
80
Showing A B ¬A ¬B
LHS (A B) (B A)
RHS (A B) (¬B ¬A)
(¬B ¬A) (A B)commutativity of
Compare LHS with RHS:
LHS (A B) (B A)
RHS (¬B ¬A) (A B)
81
And both correspondences are an instance of
one equivalence:
X Y ¬Y ¬X
So this equivalence is enough to prove
LHS RHS.
82
Showing X Y ¬Y ¬X
X Y
¬X Y implication rule
¬X ¬¬Y double negation
¬¬Y ¬X commutativity of
¬Y ¬X implication rule
83
84
Back to Exercise
For each of the following determine if it is a
tautology, inconsistency or contingency by
drawing the truth table.
a. P (P Q)
b. (P Q) (P Q)
c. Q P (P (Q P))
d. (P (Q P)) P
e. (P Q) ( P Q)
f. ((P Q) (R S) (P R)) (Q S)
Reviews
There are no reviews yet.