Predicate Calculus Exercises - Solutions

Q1Using the predicates given below translate the phrases given into predicate calculus. [Assume there is a given set or type PERSON which is the set of all people]

English / Predicate
x swims / Swims(x)
y walks / Walks(y)
z runs / Runs(z)
w dances / Dances(w)
x climbs / Climbs(x)

a)x runs

b)z walks

c)jim walks

d)y climbs

e)x runs or z climbs

f)x does not run

g)y climbs and x runs

h)if x runs then y climbs

i)if w climbs then w doesn't dance

j)For all x in PERSON x dances

k)There is x in PERSON where x swims

l)Everybody dances

m)Nobody dances

n)Somebody runs

o)Somebody runs and somebody dances

p)Somebody dances and swims

q)Somebody dances and doesn't swim

r)Everybody walks and everybody runs

s)If somebody runs then nobody swims

t)Everybody who runs also walks

u)Anyone who climbs dances

x runs / Runs(x)
z walks / Walks(z)
jim walks / Walks(jim)
y climbs / Climbs(y)
x runs or z climbs / Runs(x) Ú Climbs(z)
x does not run / ¬ Runs(x)
y climbs and x runs / Climbs(y) Ù Runs(x)
if x runs then y climbs / Runs(x) Û Climbs(y)
if w climbs then w doesn't dance / Climbs(w) Û ¬Dances(w)
For all x in PERSON x dances / Õx: PERSON × Dances(x)
There is x in PERSON where x swims / Öx: PERSON× Swims(x)
Everybody dances / Õx: PERSON ×Dances(x)
Nobody dances / Õx: PERSON ׬ Dances(x)
Somebody runs / Öx: PERSON× Runs(x)
Somebody runs and somebody dances / (Öx: PERSON × Runs(x) ) Ù (Öx: PERSON × Dances(x))
Somebody dances and swims / Öx: PERSON × Dances(x) Ù Swims(x) or
Öx: PERSON | Dances(x) × Swims(x)
Somebody dances and doesn't swim / Öx: PERSON × Dances(x) Ù ¬Swims(x) or
Öx: PERSON | Dances(x) × ¬Swims(x)
Everybody walks and everybody runs / (Õx: PERSON ×Walks(x)) Ù (Õx: PERSON× Runs(x))
If somebody runs then nobody swims / (Öx: PERSON × Runs(x) ) Û (Õx: PERSON × ¬Swims(x))
Everybody who runs also walks / Õx: PERSON × Runs(x) ÛWalks(x) or
Õx: PERSON | Runs(x) ×Walks(x)
Anyone who climbs dances / Õx: PERSON × Climbs(x) ÛDances(x) or
Õx: PERSON | Climbs(x) ×Dances(x)

In questions 2 and 3 the following predicates will be useful

x is odd / Odd(x)
x is even / Even(x)
x is prime / Prime(x)
x is divisible by y / Divisible(x, y)

Q2The following true statements have the form Õn:£ × P(n).

i)In each case below write out the statement formally as Õn:£ × P(n)

ii)identify the predicate which matches P(n)

iii)write down P(3)

iv)write down P(n+1)

a)Any natural number is either odd or even

b)A natural number is divisible by 1

c)If a natural number is odd then its square is odd

a)i) Õn:£ × Odd(n) Ú Even(n)

ii) Odd(n) Ú Even(n)

iii) Odd(3) Ú Even(3)

iv)Odd(n+1) Ú Even(n+1)

b)i)Õn:£ × Divisible(n, 1)

ii)Divisible(n, 1)

iii)Divisible(3, 1)

iv)Divisible(n+1, 1)

c)i)Õn:£ × Odd(n) Û Odd(n2)

ii)Odd(n) Û Odd(n2)

iii)Odd(3) Û Odd(32)

iv)Odd(n+1) Û Odd((n+1)2)

Q3The following false statements have the form Õn:£ × P(n).

i)In each case below write out the statement formally as Õn:£ × P(n)

ii)identify the predicate which matches P(n)

iii)write down P(3)

iv)write down P(n+1)

v)explain why the statement is false

a)Any natural number is odd

i)Õn:£ × Odd(n)

ii)Odd(n)

iii)Odd(3)

iv)Odd(n+1)

v)4 is not odd (nor is 0, 2 , 6,8,…..)

b)Any natural number is divisible by 2

i)Õn:£ × Divisible(n, 2)

ii)Divisible(n, 2)

iii)Divisible(3, 2)

iv)Divisible(n+1,2)

v)3 is not divisible by 2 [without remainder]

c)If a natural number is prime then it is odd

i)Õn:£ × Prime(n) ÛOdd(n)

ii)Prime(n) ÛOdd(n)

iii)Prime(3) ÛOdd(3)

iv)Prime(n+1) ÛOdd(n+1)

v)2 is prime but not odd

4 Note that there can be several ways of writing correct statements (see (i) for examples, and a couple more for (iii) )

  1.  x:PERSON | EatsTooMuch(x) ^ Doesn’tExercise(x) GetsOverweight(x)

 x:PERSON  (EatsTooMuch(x) ^ Doesn’tExercise(x)) => GetsOverweight(x)

 x:PERSON  EatsTooMuch(x)  Doesn’tExercise(x) => GetsOverweight(x)

  1.  x:PERSON | Smokes(x) ^ Drinks(x)  HasHeartStrain(x)
  2.  x:PERSON | Smokes(x) ^ Drinks(x) ^  EatsVeg(x)  HasHeartStrain(x)

 x:PERSON | Smokes(x) ^ Drinks(x)  EatsVeg(x) => HasHeartStrain(x)

  1.  x:PERSON | WorksHard(x) ^ Lucky(x) => Promoted(x)

5

  1. See your notes, but briefly, a proposition is a statement that can be either true or false; a predicate is like a Boolean function and is a statement whose truth value depends on the value of one or more variables.
  2. Here you can give any values for x, y and z, which give the required result of the predicate. The thing to note is that => only gives a false result if the value before the => is true and the value after the => is false. All other combinations give the result true. Thus, typical correct values might be:
  3. x=3, y=5, z=8
  4. x=3, y=5, z=1

6. (i) true (ii) false (iii) true (iv) true

7. (i) All natural numbers greater than 4, when multiplied by 3 are less than 12. False.

(ii) There is a natural number greater than 4 which, when multiplied by 3 is less than 16. True

(iii) All integers have at least one integer bigger than them. True.

(iv) There exists an integer such that all integers are bigger than it. (ie there is a smallest integer) False

8. i  n: n2=64

ii  n: n<=n

iii  m,n: | odd(m)^odd(n) odd(m*n)

iv  n: | n>2  ( x,y,z: | x>0 ^ y>0 ^ z>0  xn + yn = zn)

v  p:PERSON | isaprogrammer(p) playschess(p)

9One example is: let P(x) = odd(x) and Q(x) = even(x)

Another example is: let P(x) = double(x) and Q(x) = square(x)

Try them with various values of x. The important thing to note is that in the first quantified predicate the same value of x must be used in P(x) ^ Q(x), whereas in the second quantified predicate different values of x can be used on either side of the ^.

10i) m:MONTH  days(m)<28

 m:MONTH  days(m)>=28

(ii)

 m:MONTH  days(m) = days( next(m) )

(iii)

 m:MONTH (days(m)=30) ^ days(next(m))=30

11a) (i) true (ii) you can do this one

(b)  i: | i>2 s(i)=s(i-1)+s(i-2)

You can do parts (c) and (d) yourselves!