Transcript lecture slides

F22H1
Logic and Proof
Week 5
Overview of weeks 5—9
Predicates and Quantifiers
Overview of rest of module
Contacting me: [email protected]
Monday lecture: lecture
Thursday/Friday: practice
We will cover much but not all of:
• Nederpelt & Kamareddine: Chapters 8, 9, 11, 16,
17
• Two lectures (not from book) on the topics of
clausal form and resolution.
What we will do this week
Chapters 8 and 9, and the exercises therein.
What you will learn about:
• Predicates and Quantifiers: predicate logic
• Translating english into predicate logic
• Equivalences in predicate logic
Examinable material:
Sections: 8.2, 8.3, 8.4, 9.1—9.9
Propositions vs Predicates
Let A stand for: “Bob is a student”
A is a proposition – it is either True or False –
definitely one or the other.
Now let S = {Anna, Bill, Callum, Dave, …} … the
set of students, and let P be the set of all people,
and let x be a variable.
“x is a student” is not a proposition. What is it?
Propositions vs Predicates
Instead of “x is a student”, we typically invent suitable
function names and write predicates as functions. E.g.
here are a few examples:
Which of these are predicates and which are propositions?
student(x)
cat(Tom)
taller_than(Madonna, x)
prime_minister_of(x, y)
hates(Garfield, Mondays)
Quantifiers
Let S be the set of all students; “x is a student” is a
predicate we can decide to write it as: “x in S” instead, or
maybe “student(x)”
Suppose P is the set of all people.
With quantifiers, we can express other possible statements:
This is universal quantification
x [P(x): student(x)] -- “every person is a student”
x [S(x): has_a_brain(x)] -- “every student has a brain”
Quantifiers
x [P(x): student(x)]
“there exists a member of P who is a
student” --- i.e. “at least one person is a student” – i.e.
there is a student
x [P(x): student(x) AND attends_lectures(x) ]
x [S(x): attends_lectures(x) ]

x [S(x):
attends_lectures(x) ]
Exercises
Many-place predicates
This is what chapter 9 is all about:
This means, for example:
x[ student ( x)  y[mother ( y, x)]]
q[ student (q)  y[mother ( y, q)]]
All this means is:
“ Every man or woman has an ID card”
is equivalent to:
“Every man has an ID card AND Every woman has an ID card”
“There is a man or a woman at the top of the mountain”
is equivalent to:
“There is a man at the top of the mountain OR there is a woman at
the top of the mountain”
This just means:
“Every person who is Tom lives in Edinburgh”
is equivalent to “Tom lives in Edinburgh”
And
“There is someone who is Tom who lives in Edinburgh”
is equivalent to “Tom lives in Edinburgh”
Obviously, the quantification isn’t needed in such cases; all the rule
does is remove it.
These seem rather daft. But the expressions on the LHS might arise
in the middle of trying to prove something, and so the rule helps to
automatically simplify it.
E.g. we may have:
x[ x  5  x  2 : x  y ]
The domain is equivalent to False (why?), so the whole thing = True
Don’t worry about it; logic provides a language that enables us to
express anything at all in a formal way that computers can manipulate;
But logic is powerful enough to also express crazy things like this that
we would never say, however they may arise during calculation.
Proving the first of the “Empty domain” rules
Domain Weakening
We can move the domain statements to the right, and make them
part of the proposition.
This is obvious when you think of it.
Means: “For all x in D, A(x)”
Means: “For all, if x is in D then A(x)”
Logically, there is no difference
“There is an x in D for which A(x)” is equivalent to
“There is an x in D and A(x)”
These observations lead to the following rules:
E.g.:
“Every student who attends lectures and works hard will pass”
is equivalent to:
“For every student who attends lectures, if they work hard they’ll pass”
“There is a closed passenger door with a red light flashing”
is equivalent to:
“There is a closed door, which is a passenger door and
has a red light flashing”
but not equivalent to
“There is a closed door, and if it is a passenger door then it has a red
“It is NOT true that every student eats cheese” is equivalent to:
“There exists a student who does not eat cheese”
“There does NOT exist a camel that can dance the samba”
is equivalent to:
“Every camel cannot dance the samba”
Some practice with logical calculation
Showing:
Term Splitting
Some exercises