انت هنا الان : شبكة جامعة بابل > موقع الكلية > نظام التعليم الالكتروني > مشاهدة المحاضرة

# Predicate Logic

الكلية كلية العلوم للبنات     القسم قسم الحاسبات     المرحلة 1
أستاذ المادة زينب عبد المنعم عبد الهادي محمد شربة       09/07/2017 21:44:12
Discrete Structure , lecture 2 Predicate Logic
Propositional Logic is not enough
Suppose we have:
All men are mortal.” “Socrates is a man”.
Does it follow that “Socrates is mortal”?
This cannot be expressed in propositional logic.
We need a language to talk about objects, their properties and their relations.

Predicate Logic
Extend propositional logic by the following new features.
-Variables: x, y, z, . . .
-Predicates (i.e., propositional functions):
P(x ), Q(x ), R(y ), M(x, y ), . . .
-Quantifiers: ?, ?.
Propositional functions are a generalization of propositions. Can contain variables and predicates, e.g., P(x ).
Variables stand for (and can be replaced by) elements from their domain

Propositional Functions
Propositional functions become propositions (and thus have truth values) when all their variables are either
- replaced by a value from their domain, or
- bound by a quantifier
P(x ) denotes the value of propositional function at x . The domain is often denoted by U (the universe).
Example: Let P(x ) denote “x > 5” and U be the integers. Then
P(8) is true.
P(5) is false.
Examples of Propositional Functions
Let P(x, y, z) denote that x + y = z and U be the integers for all three variables.
P(?4, 6, 2) is true.
P(5, 2, 10) is false.
P(5, x, 7) is not a proposition.
Let Q(x, y, z) denote that x ? y = z and U be the integers.
P(1, 2, 3) ? Q(5, 4, 1) is true.
P(1, 2, 4) ? Q(5, 4, 0) is true.
P(1, 2, 3) ? Q(5, 4, 0) is false.
P(1, 2, 4) ? Q(x, 4, 0) is not a proposition.
Quantifiers
We need quantifiers to formally express the meaning of the words "all" and "some" .
The two most important quantifiers are:
Universal quantifier, “For all”. Symbol: ?
Existential quantifier, “There exists”. Symbol: ?
?x P(x ) asserts that P(x ) is true for every x in the domain.
?x P(x ) asserts that P(x ) is true for some x in the domain.
The quantifiers are said to bind the variable x in these expressions.
Variables in the scope of some quantifier are called bound variables. All other variables in the expression are called free variables.
A propositional function that does not contain any free variables is a proposition and has a truth-value.
Universal Quantifier
?x P(x ) is read as “For all x , P(x )” or “For every x , P(x )”.
The truth value depends not only on P, but also on the domain U.
Example: Let P(x ) denote x > 0.
If U is the integers then ?x P(x ) is false.
If U is the positive integers then ?x P(x ) is true.
Some Examples
Example: P(x, y): x + y = 8
Assign x to be 1, and y to be 7. We get proposition P(1, 7) which is true.
Proposition P(2, 5) is false since 2 + 5 ?8.
Example: ?x[x ? 0]
U = N (non-negative integers)
We could re-write this proposition as: ?x ? N, x ? 0 Is the proposition true?
What if the universe is R?

Example: ?x?y[x + y > x] Is this proposition true if:
1- If U = N?
If U = R?

Existential Quantifier
?x P(x ) is read as “For some x , P(x )” or “There is an x such that, P(x )”, or “For at least one x , P(x )”.
The truth value depends not only on P, but also on the domain U.
Example: Let P(x ) denote x < 0.
If U is the integers then ?x P(x ) is true.
If U is the positive integers then ?x P(x ) is false.

Order of Quantifiers
Quantifiers can be grouped into blocks
?x?y . . . ?z ?a?b . . . ?c ?u?v . . . ?w . . . . . .
Quantifiers can be swapped inside a block, but not between blocks.
Let P(x, y ) denote x + y = y + x and U be the real numbers. Then ?x ?y P(x, y ) is equivalent to ?y ?x P(x, y )
Let Q(x, y ) denote x + y = 0 and U be the real numbers. Then
?x ?y P(x, y ) is true, but ?y ?x P(x, y ) is false.

Precedence of Quantifiers
Quantifiers ? and ? have higher precedence then all logical operator ?x P(x ) ? Q(x ) means (?x P(x )) ? Q(x ). In particular, this expression contains a free variable.
?x (P(x ) ? Q(x )) means something different.
Translating English to Logic
Translate the following sentence into predicate logic: “Every student in this class has taken a course in Java.”
Solution:
First decide on the domain U.
Solution 1: If U is all students in this class, define a propositional function J(x ) denoting “x has taken a course in Java” and translate as ?x J(x ).
Solution 2: But if U is all people, also define a propositional function
S(x ) denoting “x is a student in this class” and translate as
?x (S(x ) ? J(x )).
Note: ?x (S(x ) ? J(x )) is not correct. What does it mean?

Equivalences in Predicate Logic
Statements involving predicates and quantifiers are logically equivalent if and only if they have the same truth value for every predicate substituted into these statements and for every domain of discourse used for the variables in the expressions.
The notation S ? T indicates that S and T are logically equivalent. Example: ?x ¬¬S(x ) ? ?x S(x )

Quantifiers as Conjunctions/Disjunctions
If the domain is finite then universal/existential quantifiers can be expressed by conjunctions/disjunctions
If U consists of the integers 1,2, an d 3, then
?x P(x ) ? P(1) ? P(2) ? P(3)
?x P(x ) ? P(1) ? P(2) ? P(3)
Even if the domains are infinite, you can still think of the quantifiers in this fashion, but the equivalent expressions without quantifiers will be infinitely long
De Morgan’s Law for Quantifiers
The rules for negating quantifiers are:
¬?x P(x ) ? ?x ¬P(x )
¬?x P(x ) ? ?x ¬P(x )

المادة المعروضة اعلاه هي مدخل الى المحاضرة المرفوعة بواسطة استاذ(ة) المادة . وقد تبدو لك غير متكاملة . حيث يضع استاذ المادة في بعض الاحيان فقط الجزء الاول من المحاضرة من اجل الاطلاع على ما ستقوم بتحميله لاحقا . في نظام التعليم الالكتروني نوفر هذه الخدمة لكي نبقيك على اطلاع حول محتوى الملف الذي ستقوم بتحميله .