false

Textbook Notes
(368,107)

United States
(205,941)

Temple University
(1,844)

CIS 1166
(4)

David Shulman
(4)

Chapter

Unlock Document

Computer & Information Science

CIS 1166

David Shulman

Spring

Description

Quanti▯cational Logic Part 1
1 What is Quanti▯cational Logic?
Quanti▯cational Logic is the logic of the operators for all and there exists. We
need to be able to reason automatically about these operations and we need
notation to help us express precisely certain requirements and relationships
that can be expressed in terms of these operators. Quanti▯cational Logic
allows us to reason about more things than we could reason with just using
propositional logic.
There are many di▯erent names for the quanti▯cational logic this note
descrbes. We also could call it predicate calculus, ▯rst-order logic and many
other things. The name predicate calculus comes from the fact that predi-
cates play an important role in this logic; this logic allows us to reason not
only about whole sentences but also about individual entities such as Socrates
or the number 6 and their properties such as being mortal or greater than
3. The name ▯rst-order logic comes from the fact that certain more complex
constructions are not allowed in our logic.
In this note I shall try to explain the semantics and syntax of some of the
more basic aspects of this logic. I shall also discuss some simple rules that
help you; among these rules will be De Morgan rules for quanti▯cation.
One thing to keep in mind when you write your own formulae in Quan-
ti▯cation logic is that this logic should be treated like a strictly typed pro-
gramming language. In a language like C or Java if you declare f to be a
function that takes 3 integers as inputs and outputs integers, then if you give
it the wrong number of inputs or inputs of the wrong type, you get nonsense
and you cannot write f(g, x, z) if x is a char, g is another function, and z is
complex expression that evaluates to a string of integers because f takes three
integers as input. It is very important that you not write similar nonsense
when working with quanti▯cational logic.
1 2 Predicates
Before we can discuss quanti▯ers such as for all and there exists, we need to
say something about predicates. When we say all x have some property such
as being mortal or greater than 3, it helps us if we do not have to think about
all entities including your father’s father’s favorite song, the ▯rst boat to use
a harbor in Portugal to depart for the Far East and other irrelevant things
when we only care about all animals or all people or all real numbers. There
is also a danger of paradox if we do not restrict our domain of interest. So
we need to talk about predicates that apply to certain lists of inputs, only
inputs satisfying certain type constraints.
3 Variables
We have symbols representing variables, symbols such as x, y, z. Associated
with each of these variables is a domain of things that they might possibliy
represent. In the simplest case all variables represent things belonging to
the same domain such as real numbers, people, words etc. But in general
variables can be of di▯erent types.
4 Constants
We also have symbols such as 3, SOCRATES etc. that designate indivual
objects.
5 Predicates
An m place predicate is something that takes a list of m entities that belong
to the correct domains and outputs a truth value truth or false. So for
example there is the 1 place or monadic predicate HEALTHY that takes as
input a person and outputs true or false depnding of whether that person is
healthy. Of course there is also a similar predicate with a somewhat di▯eent
domain where we allow our input to be any animal or maybe any animal or
machine. We have the two place predicate KNOWS which has as input a list
of 2 people x and y and if the input is given with x ▯rst y second, then the
output is true i▯ x knows y; otherwise the output is false. We have the two
2 place predicate < which is input a list x, y of integers and outputs true or
false depending on whether x is less than y or not; there is also a very similar
predicate (represented by the same symbol) that takes as input 2 reals and
outputs true or false depending on whether the ▯rst number is less than the
second number.
Some more predicates: There is a three place predicate PLUS such that
for PLUS (x, y, z) to make sense x, y, z must be integers and PLUS(x, y, z)
is TRUE i▯ x+y = z; otherwise we output false. There are also very similar
predicates that use real number input.
6 Universal and Existential Quanti▯cation
There are two quanti▯ers we use. We have 8 and 9 meaning for all and there
exists respectively. There are other quanti▯ers but these are the two basic
quanti▯ers and in fact it will turn out that we could get away with using just
one of these quanti▯ers.
If P is a propositional formula (something that would become a propo-
sition if we gave de▯nite values to the variables appearing in the formula),
then 8xP means no matter what allowed value is given to x, P is true and
9xP means there is an allowed value for x that makes P true. There might
be many such values but as long as we have one, we are o.k.
Note in the special case where your domain is empty (say you are quan-
tifying over unicorns and there are no unicorns), then 9xP must be false; if
there are no unicorns hence there is no unicorn that makes P true. If there are
no unicorns and unicorns is our domain then 8x;P is TRUE because there
is no unicorn available to prove the statement false. (If this seems strange to
you, just accept that this rule makes reasoning by computer simpler.)
7 Warnings and Cautions about Quanti▯ers
and Predicates
I can de▯ne a four place predicate S whose input domain (for all inputs) is
the real numbers and such that S(x;y;z;w) i▯ x + y = z. Here w is totally
irrelevant but you have to write the fourth input. So S(3;2;5;81) is true and
S(3;4;98;7) is false.
3 Another important point is that input must be of the required type. If I
de▯ne a predicate SPEAKS whose ▯rst input has domain the set of people
and whose second input has domain the set of languages, it is ▯ne to write
SPEAKS(Alice, Latin), but it not ▯ne to write SPEAKS(Alice, a romance
language). A romance language is not one speci▯c language. You could
instead write 9x SPEAKS(Alice, x) ^ RomanceLanguage(x).
Another example of type violation: Let SUM(x, y, z) be true i▯ x+y = z
where the required domains are all the integers. Then it is bad to write
SUM(3, 5, < 9). < 9 does not represent an integer. It actually by itself does
not represent anything but if it represented anything it would be the set of
integers less than 9 and that is not an integer.
You also must not write SPEAKS(Ebenezer, Latin and Greek). You
would write instead SPEAKS(Ebenezer, Latin) ^ SPEAKS(Ebenezer, Greek).
I will discuss later the precise rules of quanti▯ciational logic syntax but
things are a little more complicated if we use di▯erent domains for all our vari-
ables. We could instead use one big domain. So for the predicate SPEAKS,
we might have one domain that includes both people and languages and say
SPEAKS(x, y) is true i▯ x is a person and y is a language and x speaks
y and false otherwise. (But of course SPEAKS(x, y) is nonsense if x or y
represents something that is neither a language nor a person. So we can say
SPEAKS(Latin, Alice) or SPEAKS(Latin, Latin), which are both false but
SPEAKS(4, Latin) is nonsense because 4 is neither a language nor a person.
If you wanted to say that 4 people speak Latin, you would say 9x9y9z9w
(SPEAKS(x, Latin) and SPEAKS(y, Latin) and SPEAKS (z, Latin) and
SPEAKS (w, Latin) and NOT EQUAL(x, y) and NOT EQUAL (x, z) and
NOT EQUAL (x, w) and NOT EQUAL (y, z) and NOT EQUAL (y, w) and
NOT EQUAL (z, w)) where you must use ^ where I wrote the word and
and use y 6= z instead of NOT EQUAL(y, z) and similarly with the other
occurences of NOT EQUAL.
8 Implementing Quanti▯ers with a Program
If your domain D is ▯nite and the variable x has to represent an element
of domain D, then you can implement 8xP(x) on your computer if you can
implement P on your computer and you can also implement 9xP(x). To
implement 8xP, proceed as follows: Initialize RESULT = true then loop
through all possible values of x and for each value d, do if P has value false
4 when x = d, set RESULT = false and escape loop. When done with the loop
return RESULT. Thus if you never get P has truth value false, you return
TRUE. To implement 9xP, proceed as follows: Initialize RESULT = false
then loop through all possible valiues of x and for each value d, do if P has
value true when x = d, set RESULT = true and escape loop. When done
with the loop return RESULT. This way if you never get P has truth value
true, you return FALSE.
In practice you would not really implement such a loop, but thinking
about such an imaginary program might help us understand precisely how
quanti▯ers work.
9 Some Example Translations
Let S be a two place predicate such that S(x, y) means person x speaks
language y and other than that I will just use standard relations such as <
on the real numbers. Notice that predicates are usually written before their
inputs but special predicate

More
Less
Related notes for CIS 1166

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.