Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456 Formal Languages and Computability
The lectures we had last Friday were devoted
to an introduction to propositional (aka Boolean) logic and its uses
as a problem solving and modelling tool in Computer Science. We saw
that propositional logic and satisfiability checking were
general-purpose problem solving tools in Computer Science that can be
applied with success in many situations.
There are, however, cases in
which it is not very natural to describe some statements formally
using propositional logic. Consider, for instance, the statement
"All students will pass the exam in Formal Languages and Computability."
If we know precisely what students are taking the course in question,
say Hanne, Steen and Frank, we could express this statement in
propositional logic using the formula
Hanne_Passes AND Steen_Passes and Frank_Passes
where X_Passes is a variable that is intended to be true if X passes
the exam. Note that if we have lots of students, the formula grows in
size, and that for different sets of students we need different
formulae.
What we would like to write here is a formula like
For all X, Follows(X,Formal Languages and Computability) implies Passes(X,Formal Languages and Computability).
Here X is a variable that ranges over the collection of students. The
so-called first-order logic is an extension of propositional
logic that allows us to write formulae like the one above. This
lecture is devoted to a brief introduction to this important logic.
Time and Location
Monday, 27 September, 2004 at 10:15 in A4-106.
Reading Material
All the reading material for the lectures devoted to logic is
available on line in the Base Logic module
of the TeachLogic
project. In particular, for this lecture you should read Part
IV: Quantifiers (first-order logic).
Exercises
I suggest that you work out the exercises on the slides for this
lecture. Moreover, on this page, you
will find a large number of exercises. How many of those you decide to
do, and which ones, depends on your interests and confidence with the
material. I strongly suggest, however, that you attempt some of the
basic ones to test your understanding of the notions. At the very
least, you should work out problems 2-9 there.
Show that, over the natural numbers, the relation < is definable
in terms of the constant 0, the function symbol + and equality --- in
other words, find a formula LESS-THAN(x,y) that uses 0, + and = that,
for all natural numbers x and y, is true if, and only if, x < y.
Let us say that a model of a sentence F is a structure
over the language of F where the formula is true. For instance,
if we interpret the symbol "<" as "less than over the natural
numbers", the natural numbers are a model of the formula
For
all x (0 < x OR x = 0)
but the set of integers is not a model of the formula.
Can you write a formula that has only models with exactly one object?
Write a formula that is only satisfied by infinite models.