Predicates and Quantifiers

Question 1

The statement “x is greater than 3” has two parts. The first part, the variable x, is the subject
of the statement. The second part—the ______________ “is greater than 3”—refers to a property that
the subject of the statement can have.

Answer 1

predicate

Question 2

We can denote the statement “x is greater than 3” by

Answer 2

P (x),
where P denotes the predicate “is greater than 3” and x is the variable

Question 3

The statement P (x) is
also said to be the value of the

Answer 3

propositional function P at x

Question 4

A statement of the form P (x1, x2, . . . , xn) is the value of the

Answer 4

propositional function P

Question 5

A statement of the form P (x1, x2, . . . , xn) is the value of the propositional function P at the
n-tuple (x1, x2, . . . , xn), and P is also called an

Answer 5

n-place predicate or a n-ary predicate

Question 6

The statements that describe valid input are known
as

Answer 6

preconditions

Question 7

The statements that describe valid input are known
as preconditions and the conditions that the output should satisfy when the program has run
are known as

Answer 7

postconditions

Question 8

When the variables in a propositional function are assigned values, the resulting statement
becomes a proposition with a certain truth value. However, there is another important way, called

Answer 8

quantification, to create a proposition from a propositional function

Question 9

The area of logic that deals with predicates
and quantifiers is called the .

Answer 9

predicate calculus

Question 10

Many mathematical statements assert that a property is
true for all values of a variable in a particular domain, called the

Answer 10

domain of discourse (or
the universe of discourse), often just referred to as the domain

Question 11

The notation ∀xP (x) denotes the universal quantication of P (x). Here ∀ is called the

Answer 11

universal quantier

Question 12

We read ∀xP (x) as “for all xP (x)” or “for every xP (x).” An element
for which P (x) is false is called a

Answer 12

counterexample of ∀xP (x).

Question 13

Remember that the truth
value of ∀xP (x) depends
on the

Answer 13

domain

Question 14

The existential quantification of P (x) is the

Answer 14

proposition

Question 15

We use the notation ∃xP (x) for the existential quantification of P (x). Here ∃ is called the

Answer 15

existential quantifier

Question 16

Remember that the truth
value of ∃xP (x) depends
on the

Answer 16

domain!

Question 17

there is no limitation on the number of different quantiers we can define, such as “there are
exactly two,” “there are no more than three,” “there are at least 100,” and so on. Of these other
quantiers, the one that is most often seen is the

Answer 17

uniqueness quantier, denoted by ∃! or ∃1

Question 18

When a quantifier is used on the variable x, we say that this occurrence of the variable is

Answer 18

bound

Question 19

An occurrence of a variable that is not bound by a quantier or set equal to a particular value
is said to be

Answer 19

free

Question 20

The part of a logical expression to which a quantier is applied is called the

Answer 20

scope of this quantifier

Question 21

Statements involving predicates and quantifiers are

Answer 21

logically equivalent if and only if they
have the same truth value no matter which predicates are substituted into these statements
and which domain of discourse is used for the variables in these propositional functions

Question 22

We use the notation S ≡ T to indicate that two statements S and T involving predicates and
quantifiers are

Answer 22

logically equivalent

Question 23

The rules for negations for quantiers are called

Answer 23

De Morgan’s laws for quantiers

Question 24

Prolog programs
include a set of declarations consisting of two types of statements

Answer 24

Prolog facts and Prolog
rules. Prolog