comp2022 Tutorial 3 s2 2020 Problem 1. Give an example of a ternary predicate, i.e., one that takes three argu-
ments.
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.
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.
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?
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))
1
comp2022 Tutorial 3 s2 2020
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.
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 wffs 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.
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
2
comp2022 Tutorial 3 s2 2020
• 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
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)) 6. (∀xP(y, x) ∧ ∃yP(x, y))
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