Predicates are used in Control Statements in high level languages.
Predicates may be either “constants” or “variables”. Values of the
individual variables are drawn from a set of values called “Universe of
discourse”.
In order to change a predicate into a proposition, each individual variable
of the predicate should be “bound”. There are two ways of doing it.
(i) The first way to bind an individual variable is by assigning a value to it.
Example: P = “a + b = 6”.
which is denoted by P(x, y).
If a = 2, and b = 3, then
P(2, 3) is false.
(ii) The second way to bind an individual variable is by “quantification” of the
variable.
It can be done either by “universal” or “extential”.
“For all values of x, the assertion P(x) is true.”
“For all x, P(x)” is written as “∨ x P x
( )”, where ∨ is a “Universal
Quantifier”.
“There exists a value of x for which the assertion P(x) is true”. This
statement is written as “ℑ x P x
( )” where ℑ is called “External Quantifier”.
The proposition ∨ x P x
( ) is equivalent to the conjunction
P
P
P
P
( )
( )
( )
( )
1
2
3
4
∧
∧
∧
for the universal consisting of integers 1, 2, 3, and 4.
The proposition ℑ x P x
( ) is equivalent to the disjunction
P
P
P
P
( )
( )
( )
( )
1
2
3
4
∨
∨
∨
The proposition ℑ! ( )
xP x is equivalent to the proposition
[ ( )
( )
( )] [ ( )
( )
( )]
[ ( )
( )
P
P
P
P
P
P
P
P
1
2
3
2
1
3
3
1
∧ ¬
∧ ¬
∨
∧ ¬
∧ ¬
∨
∧ ¬
∧ ¬ P ( )]
2
Note that the sequence ∨ ∨
x
y can always be replaced by ∨ ∨
y
x , and the
sequence ℑ ℑ
x y can always be replaced by ℑ ℑ
y x , though the order in which
individual variables are bound cannot always be changed without affecting the
meaning of an assertion.
Ì Exam ple 8.3.1: Let S(x, y, z) denote the predicate “x + y = z”. P(x, y, z)
denote “x y z
⋅ = ” and L(x, y) denote “x < y”. Let the universe of discourse
be the natural numbers N. Using the above predicates, express the
following assertions. The phrase “there is an x” does not imply that x has a
unique value.
Prop o si tions and Pred i cates
277