Predicates, Free Variables, And Atomic Formulas Quiz

1) Which of the following is a predicate rather than a proposition?

Open the book.

X is prime

The sky is blue.

Paris is the capital of France.

A predicate is a statement that contains variables and becomes a proposition only when the variables are replaced by specific values. Option B contains the variable x, so it is a predicate. The other options are either commands (A) or statements without variables (C and D), which are propositions because they have a definite truth value.

Explanation

A predicate is a statement that contains variables and becomes a proposition only when the variables are replaced by specific values. Option B contains the variable x, so it is a predicate. The other options are either commands (A) or statements without variables (C and D), which are propositions because they have a definite truth value.

2) What makes a predicate different from a proposition?

It contains quantifiers.

It contains a predicate symbol applied to arguments, which may include variables.

It contains a function that returns a numeric value.

It must be combined with logical connectives to be meaningful.

A predicate is a statement that involves a predicate symbol (like P, Q) applied to arguments, and these arguments can include variables. A proposition, on the other hand, is a statement that is either true or false and does not contain variables. While predicates can be used with quantifiers (A) or logical connectives (D), these are not the defining features.

Explanation

A predicate is a statement that involves a predicate symbol (like P, Q) applied to arguments, and these arguments can include variables. A proposition, on the other hand, is a statement that is either true or false and does not contain variables. While predicates can be used with quantifiers (A) or logical connectives (D), these are not the defining features.

3) Which is a well-formed formula containing a free variable?

P(x) ∧ Q

Y ∧ z

2+3=5

∀x P(x)

A well-formed formula is a syntactically correct expression. A free variable is a variable that is not bound by a quantifier. In option A, x is a free variable because there is no quantifier for x, and Q is a proposition (no variables). Option B is not well-formed because y and z are variables without a predicate.

Explanation

A well-formed formula is a syntactically correct expression. A free variable is a variable that is not bound by a quantifier. In option A, x is a free variable because there is no quantifier for x, and Q is a proposition (no variables). Option B is not well-formed because y and z are variables without a predicate.

4) P(3) is a:

Closed formula / proposition

Predicate with free variable

Quantified statement

Predicate schema

P(3) is a statement where the variable in the predicate P has been replaced by a constant (3). Therefore, it has no free variables and is a closed formula, which is also called a proposition. It is not a predicate with a free variable (B), not a quantified statement (C), and not a schema (D) because it is a specific instance.

Explanation

P(3) is a statement where the variable in the predicate P has been replaced by a constant (3). Therefore, it has no free variables and is a closed formula, which is also called a proposition. It is not a predicate with a free variable (B), not a quantified statement (C), and not a schema (D) because it is a specific instance.

5) Which has a free variable?

∀x P(x)

P(a)

∃y Q(y)

P(x)

A free variable is one that is not bound by a quantifier. In option D, x is a free variable because there is no quantifier for x. In options A and C, the variables x and y are bound by quantifiers. In option B, a is a constant, so there are no variables.

Explanation

A free variable is one that is not bound by a quantifier. In option D, x is a free variable because there is no quantifier for x. In options A and C, the variables x and y are bound by quantifiers. In option B, a is a constant, so there are no variables.

6) Which is the simplest atomic predicate (no function symbols)?

P(x) ∨ Q(x)

P(x) ∧ R(x)

P(f(x))

P(x)

An atomic predicate is one that does not contain logical connectives or quantifiers. Option D is simply a predicate symbol applied to a variable, which is the simplest form. Options A and B contain logical connectives (∨ and ∧), so they are compound. Option C contains a function symbol f, which is not allowed in the simplest atomic predicate.

Explanation

An atomic predicate is one that does not contain logical connectives or quantifiers. Option D is simply a predicate symbol applied to a variable, which is the simplest form. Options A and B contain logical connectives (∨ and ∧), so they are compound. Option C contains a function symbol f, which is not allowed in the simplest atomic predicate.

7) Translated to normal English language, 'Student(x)' means:

X is a student

There exists a student

All x are students

X is not a student

The expression "Student(x)" is a predicate that says that the object x has the property of being a student. It does not make an existential claim (B) or a universal claim (C), nor does it say that x is not a student (D).

Explanation

The expression "Student(x)" is a predicate that says that the object x has the property of being a student. It does not make an existential claim (B) or a universal claim (C), nor does it say that x is not a student (D).

8) Which of the following is an atomic predicate?

P(x) ⅴ Q(x)

¬R(x)

S(x,y)

∀x T(x)

An atomic predicate is a single predicate symbol applied to terms, without logical connectives and no quantifiers. Option C is just a predicate symbol applied to two arguments, so it is atomic.

Explanation

An atomic predicate is a single predicate symbol applied to terms, without logical connectives and no quantifiers. Option C is just a predicate symbol applied to two arguments, so it is atomic.

9) Which of the following is an open formula rather than a sentence?

P(x) ∧ Q(x)

∀x P(x)

P(a)

∃x R(x)

An open formula contains free variables and is not a complete sentence (proposition). Option A has free variables x, so it is an open formula. The other options are sentences: B and D are quantified (no free variables), and C uses a constant.

Explanation

An open formula contains free variables and is not a complete sentence (proposition). Option A has free variables x, so it is an open formula. The other options are sentences: B and D are quantified (no free variables), and C uses a constant.

10) Which is true about P(x) and P(2)?

P(x) is proposition, P(2) is predicate

P(x) has free variable, P(2) is proposition

P(x) is quantified, P(2) is free variable

None of the above

P(x) contains a free variable x, so it is a predicate (not a proposition). P(2) is the result of replacing x with the constant 2, so it has no free variables and is a proposition. Therefore, option B is correct.

Explanation

P(x) contains a free variable x, so it is a predicate (not a proposition). P(2) is the result of replacing x with the constant 2, so it has no free variables and is a proposition. Therefore, option B is correct.

11) Which of the following is not a single predicate symbol application?

P(a,b)

Q(x)

Q(x) ∧ R(y)

S(z)

A predicate symbol application is a single predicate applied to arguments, such as P(a,b), Q(x), or S(z). Option C is a compound formula that uses the logical connective ∧ to combine two predicate applications, so it is not a single predicate symbol application.

Explanation

A predicate symbol application is a single predicate applied to arguments, such as P(a,b), Q(x), or S(z). Option C is a compound formula that uses the logical connective ∧ to combine two predicate applications, so it is not a single predicate symbol application.

12) Which best describes an n-ary predicate?

A predicate with n quantifiers

A predicate taking n arguments

A predicate with n variables

A predicate of depth n

An n-ary predicate is one that takes n arguments. For example, a unary predicate takes one argument, a binary predicate takes two, and so on. It is not defined by the number of quantifiers (A), the number of variables (which might be more than the arity if some are bound), or depth (D).

Explanation

An n-ary predicate is one that takes n arguments. For example, a unary predicate takes one argument, a binary predicate takes two, and so on. It is not defined by the number of quantifiers (A), the number of variables (which might be more than the arity if some are bound), or depth (D).

13) Which is a ground atomic formula?

P(x)

P(a)

P(y,z)

∃x P(x)

A ground atomic formula is an atomic predicate that contains no variables. Option B uses a constant a, so it is ground. Options A and C contain variables, and option D is quantified and not atomic.

Explanation

A ground atomic formula is an atomic predicate that contains no variables. Option B uses a constant a, so it is ground. Options A and C contain variables, and option D is quantified and not atomic.

14) The predicate R(x,y) has an arity of:

0

1

2

Depends on domain

The arity of a predicate is the number of arguments it takes. R(x,y) takes two arguments, x and y, so its arity is 2. This is fixed and does not depend on the domain.

Explanation

The arity of a predicate is the number of arguments it takes. R(x,y) takes two arguments, x and y, so its arity is 2. This is fixed and does not depend on the domain.

15) Identify the free variables in P(x,z) ∧ ∃y Q(y):

X only

Z only

X and z

None

A free variable is one that is not bound by a quantifier. In the expression, x and z are not bound by any quantifier, so they are free. The variable y is bound by the existential quantifier ∃y, so it is not free.

Explanation

A free variable is one that is not bound by a quantifier. In the expression, x and z are not bound by any quantifier, so they are free. The variable y is bound by the existential quantifier ∃y, so it is not free.