comp2022 Tutorial 3 s2 2020 Problem 1. Give an example of a ternary predicate, i.e., one that takes three argu-
ments.
Solution 1. E.g., the ternary predicate of three arguments x, y, z defined by z =
x+y.
Problem 2. Write the following as predicate logic formulas: 1. P is a reflexive binary relation.
2. P is a transitive binary relation.
3. f is an injective function.
4. f is a surjective function.
Solution 2.
1. ∀xP(x, x)
2. ∀x∀y∀z((P(x, y) ∧ P(y, z)) → P(x, z)) 3. ∀x∀y(¬E(x, y) → ¬E( f (x), f (y)))
4. ∀y∃xE(f(x),y)
Problem 3. Let child(x,y) be a binary relation expressing that x is a child of y. Write predicate logic formulas expressing the following:
1. the sibling relation,
2. the cousin relation,
3. the second-cousin relation (i.e., their parents are cousins),
4. no pair of siblings has any children,
5. no pair of first cousins has any children,
6. there are two second cousins (i.e., their grandparents are siblings) each of which have children.
Solution 3.
1. the sibling relation siblings(x1, x2) can be expressed by
∃y(child(x1, y) ∧ child(x2, y)) 2. the cousin relation cousins(x1, x2) can be expressed by
∃y1∃y2(siblings(y1, y2) ∧ child(x1, y1) ∧ child(x2, y2)) 3. the second-cousin relation can be expressed by
∃z1∃z2(cousins(z1, z2) ∧ child(x1, z1) ∧ child(x2, z2)) 1
comp2022 Tutorial 3 s2 2020
Problem 4. Recall the structure of integers Z and of strings S from lectures.
1. How is addZ different from addS ?
2. Find a sentence which is true in the structure of integers Z and of strings S.
3. Consider the structure T = (H, parent ofT , manT , womanT ), where parent ofT is binary relation, and man is a unary predicate, and womanT is a unary predi- cates. The formula (parent of(x,y) ∧ man(x)) means that x is the father of y. Write formulas that express that x is the sister of y, that x is the uncle of y, and other family relations.
4. Give a structure with 3 elements in the domain and one binary predicate.
5. Consider the formula ∃x∀y eq(add(y, x), y) that says that there is an element x such that when it is added to any element y we just get y. Is this formula true about strings? Is this formula true about integers?
Solution 4.
1. addZ is a function on the domain of integers, while addS is a function on the
domain of strings.
2. ∃x∀yeq(add(x,y),add(y,x)).
Problem 5. What are the subformulas of the following predicate logic formulas? 1. ∀x∀y(P(x, y) ∧ ¬P(y, x))
2. ∀x(P(x, f (x)) ∧ ∃y¬P(y, x))
3. ∀x∀y(P(x,y)↔¬R(x,y))
Solution 5.
1. The subformulas are ∀x∀y(P(x,y) ∧ ¬P(y,x)),
(P(x, y) ∧ ¬P(y, x)), P(x, y), ¬P(y, x)), and P(y, x).
∀y(P(x,y) ∧ ¬P(y,x)),
Problem 6. If F is a formula and F occurs as part of the formula G then F is called a subformula of G. Give a recursive procedure for determinining if F is a subformula of G.
Problem 7. Let Free(F) be the set of all variables that occur free in F. Define Free(F) by a recursive procedure.
Solution 7. The set Free(F) of free variables of F is defined by the following recur- sive procedure:
1. for an atomic formula F, Free(F) is the set of variables occuring in F. 2. Free(¬F) = Free(F)
3. Free((F ∨ G)) = Free((F ∧ G)) = Free(F) ∪ Free(G)
2
comp2022 Tutorial 3 s2 2020 4. Free(∃xF) = Free(∀xF) = Free(F) \ {x}.
Problem 8. Consider the formula ∀x E( f (x)) where E is a unary predicate-symbol and f is a unary function-symbol.
1. Provide a structure A in which the truth-value of this formula is 1.
2. Provide a structure B in which the truth-value of this formula is 0.
3. Provide a structure C in which the truth-value of the atomic formula E(f(x)) depends on the given assignment.
Problem 9. Consider the structure R = (R, PR, NR, SR) where • PR(x) expresses that x is positive,
• NR(x) expresses that x is a natural number,
• SR(x, y) expresses that x = y2.
Express the following formulas in English, and decide if they are true or false: 1. ∃x∃yP(x) ∧ S(x, y)
2. ∀x¬P(x)
3. ∃x¬P(x)
4. ¬∀xP(x)
5. ∀x∃yN(x) ∧ S(x, y) → P(x)
6. ∀xP(x) ∨ N(x)
7. ∃xS(x,y)
Do the same for the structure Z = (Z,PZ,NZ,SZ) where
• PZ (x) expresses that x is positive,
• NZ (x) expresses that x is a natural number, • SZ (x, y) expresses that x = y2.
Solution 9. Here is the solution for R:
1. There is a positive real number that is the square of another real number
2. All real numbers are not positive
3. There is a real number that is not positive
4. Not all real numbers are positive (this is equivalent to the previous formula)
3
comp2022 Tutorial 3 s2 2020
5. On first glance you might read this as meaning “If a natural number is the square of a number, then it is positive”, but actually this interpretation isn’t correct! For example, let y = π, then (N(x) ∧ S(x, y)) will be false for any value of x, which makes the formula trivially true.
A more appropriate formula for this statement would be: ∀xN(x) ∧ ∃yS(x, y) → P(x)
Or, equivalently: ∀x∀yN(x) ∧ S(x, y) → P(x)
6. All numbers are positive, or x is a a natural number (note: the second x in this formula is a free variable, so it refers to a specific number, unlike the first x, which is bound to the the ∀ quantifier.)
7. y is the square of a number
Problem 10. Suppose the domain D is the universe. Using the following predicates: • C(x):xisachild
• B(x):xisabook
• L(x, y) : x likes y
• E(x) : x is educational
Express the following sentences in predicate logic:
1. All children like books
2. Some child likes every single book
3. Not all children like all books
4. Some child does not like any book
5. There is a book that all children like
6. Books are always educational
7. Educational books are liked by children
8. Books are not always educational
9. No book, except for the educational ones, is liked by every child.
10. There is a child who likes all books that are not educational
Solution 10.
1. All children like books
∀x(C(x) → ∃y(B(y) ∧ L(x, y)))
4
comp2022 Tutorial 3 s2 2020 2. Some child likes every single book
∃xC(x) ∧ ∀yB(y) → L(x, y) 3. Not all children like all books
¬∀x∀yC(x) ∧ B(y) → L(x, y) 4. Some child does not like any book
∃x∀yC(x) ∧ B(y) → ¬L(x, y) 5. There is a book that all children like
∃y∀xB(y) ∧ C(x) → L(x, y) 6. Books are always educational
∀x(B(x) → E(x)) 7. (All) Educational books are liked by (all) children
∀x∀y(C(x) ∧ B(y)) ∧ E(y) → L(x, y) 8. Books are not always educational
¬∀x(B(x) → E(x))
9. No book, except for the educational ones, is liked by every child.
∀y∃xB(y) ∧ ¬E(y) → C(x) ∧ ¬L(x, y) 10. There is a child who likes all books that are not educational
∃x∀yC(x) ∧ (B(y) ∧ ¬E(y)) → L(x, y)
Problem 11. For each of the following expresions, indicate if it is a formula of predicate logic. If it is, then indicate the free occurrences of variables, the bound occurrences of variables, the constant symbols, the function symbols, and the pred- icate symbols.
1. (∀xP(x) ∧ P(c))
2. ∀x(P(x) ∧ P(y))
3. ∀x(P(x) ∧ Q(y, x))
4. ∀x(P(x, a) ∧ (∃y))
5. (∀x∃yP(y, x) ∧ P(x, y))
5
comp2022 Tutorial 3 6. (∀xP(y, x) ∧ ∃yP(x, y))
Solution 11.
P and Q are the predicate symbols. There are no function symbols.
1. Correct syntax, x is bound, c is a constant
2. Correct syntax, x is bound, y is free
3. Correct syntax, the x’s are bound, y is free
4. Incorrect syntax, the ∃y quantifier does not introduce a formula
s2 2020
5. Correct syntax, the first x and y are bound, but the second ones are free.
6. Correct syntax, the first x is bound but the second is free, the first y is free but the second is bound.
Problem 12. Consider the sentence:
∀x∀yP(x, y) ∧ (P(x, c) ∨ Q(x, c)) → P(c, f (x, y)) ∨ Q(c, f (x, y))
and the structure A with domain Z, and
• cA = 0,
• fA(x,y)=x+y,
• PA isthesetofpairs(a,b)with(a