(Additional problem #4) We\'re working in first-order logic again. We use only quantifiers
(V,d). boolean connectives , Boolean connective , variables (x, y, z, and so on), and the
following list of symbols and relations. You can assume that all variables represent integers.
(You may want to review Section 1.4.) O(x): x is odd P(x): x is prime = x | (\"divides\") Why
does the statement P(x) have no truth value? Why is Ungrammatical? What is the difference
between and Write each of these as a sentence in English and explain why they do not have the
same meaning.
Solution
(a) P(x): x is prime
P(x) is a predicate and not a proposition or statement.The truth of a predicate depends on the
value assigned to its variables.The predicate would have had a truth value is we had given some
values to x. Given a predicate P(x), the statement “for some x, P(x)” (or “there is some x such
that p(x)”), represented “x P(x)”, has a denite truth value, so it is a proposition in the usual sense.
(b) (x)(xO(x))
The English transformation of this statement is \"For all x, x belongs to x is odd\". The
construction should have been \"For all x, x is odd\" , hence the statement would be
(x)(O(x))
(c)(x)(y)(y|x)
This statement means \"For all x , there exists some y such that y divides x\"
(y)(x)(y|x)
This statement means \"There exist some y such that for all x, y divides x\"
There is a basic difference between the two statements.The first one says that every x has some
factor y which is different for different x values, while the second statement says that y is a
universal factor of all x , that is why it divides all x.
(V,d). boolean connectives , Boolean connective , variables (x, y, z, and so on), and the
following list of symbols and relations. You can assume that all variables represent integers.
(You may want to review Section 1.4.) O(x): x is odd P(x): x is prime = x | (\"divides\") Why
does the statement P(x) have no truth value? Why is Ungrammatical? What is the difference
between and Write each of these as a sentence in English and explain why they do not have the
same meaning.
Solution
(a) P(x): x is prime
P(x) is a predicate and not a proposition or statement.The truth of a predicate depends on the
value assigned to its variables.The predicate would have had a truth value is we had given some
values to x. Given a predicate P(x), the statement “for some x, P(x)” (or “there is some x such
that p(x)”), represented “x P(x)”, has a denite truth value, so it is a proposition in the usual sense.
(b) (x)(xO(x))
The English transformation of this statement is \"For all x, x belongs to x is odd\". The
construction should have been \"For all x, x is odd\" , hence the statement would be
(x)(O(x))
(c)(x)(y)(y|x)
This statement means \"For all x , there exists some y such that y divides x\"
(y)(x)(y|x)
This statement means \"There exist some y such that for all x, y divides x\"
There is a basic difference between the two statements.The first one says that every x has some
factor y which is different for different x values, while the second statement says that y is a
universal factor of all x , that is why it divides all x.
