Predicate Logic
Part 1: Set Comprehensions
Exercise 1
Describe in words the contents of the following sets. Let $A$ be the set of Animals in a zoo. Let $E$ be a set of animal enclosures at the zoo, and $P$ be a set of people. Assume the various predicates used are defined as appropriate over these sets.
- \( \{ x : A \mid \text{tall}(x) \wedge \text{giraffe}(x) \} \)The set animals that are tall giraffes
- \( \{ x : A; y : \mathbb{R} \mid \text{height}(x, y) \} \)The set of pairs $(a, h)$ where $a$ is an animal, and $h$ is a real number that is the height of the animal $a$.
- \( \{x : A \times A \mid (\exists y \in E) (\text{enclosureFor}(x.1,y) \wedge \text{enclosureFor}(x.2,y) ) \} \)The set of pairs of animals $(a, b)$ that both share an enclosure. In other words, there exists an enclosure in the zoo that contains both $a$ and $b$.
- \( \{x : A; y : \mathbb{N} \mid \text{age}(x, y) \bullet y \} \)The set of natural-number ages of animals in the zoo. In other words, the set of ages (e.g. 3, 5, 11, etc.) where there is at least one animal of that age in the zoo.
- \( \{x : A \mid (\forall y \in P) (\text{visitor}(y) \implies \text{loves}(y,x) ) \} \)The set of animals that are loved by every visitor.
Exercise 2
Define by extension the following sets. If the sets are infinite, list only 4 elements for the lowest \( n, m \).
- \( \{ n : \mathbb{N} \mid 0 < n < 10 \} \)\( \{1, 2, 3, 4, 5, 6, 7, 8, 9 \} \)
- \( \{ n : \mathbb{R} \mid n^2 = 1 \} \)\( \{ -1, 1 \} \) This set comprehension generates the set of numbers which when squared equal 1. As we are enumerating the real numbers (\( \mathbb{R} \)), $-1$ is included in our enumeration, and $-1^2 = 1.
- \( \{ n : \mathbb{N} \mid ( n < 10 ) \wedge \text{isPrime}(n) \} \)\( \{2, 3, 5, 7 \} \) This set comprehension generates the set of prime numbers that are smaller than 10.
- \( \{ n: \mathbb{N} \bullet n + n \} \)\( \{ 2, 4, 6, 8, \dots \} \)This set comprehension generates the set of positive even numbers, as an even number can be defined as $2k$ for some $k$.
- \( \{ n: \mathbb{N}; m: \mathbb{N} \bullet \frac{n}{m} \} \)\( \{ \frac{1}{1}, \frac{1}{2}, \frac{2}{1}, \frac{1}{3}, \dots \} \) This set comprehension generates the set of fractions \( \frac{n}{m} where $n$ and $m$ are natural numbers. This is equal to the set of positive rational numbers. \)
- \( \{ n: \mathbb{N} \bullet n^2 \} \)\( \{ 1, 2, 4, 9, 16, \dots \} \) This set comprehension generates the set of all square numbers.
Exercise 3
Define the following by set comprehension
- The set of numbers greater than 10 \( \{ n : \mathbb{N} \mid n > 10 \} \)
- The set of subsets of a set of numbers, \( S \) \( \{ n : \mathbb{P}(\mathbb{N}) \mid n \subseteq S \} \)
- The set of sets of numbers that have a proper subset \( \{ n : \mathbb{P}(\mathbb{N}) \mid (\exists s \in \mathbb{P}(\mathbb{N}))(s \subset n) \} \)
- The intersection of three sets of numbers, \( R, S, T \) \( \{ n : \mathbb{P}(\mathbb{N}) \mid n \subseteq R \wedge n \subseteq S \wedge n \subseteq T \} \)
- \( \{3, 6, 9, 12, \dots \} \) \( \{ n : \mathbb{N} \bullet 3n \} \)
- \( \{1, 0.5, 0.25, 0.125, \dots \} \) \( \{ n : \mathbb{N} \bullet 2^{-(n-1)} \} \)
Exercise 4
Give 4 elements from the following sets
- \( \{ a : \mathbb{N}; b: \mathbb{N}; c: \mathbb{N} \mid a > b > c \} \)\( \{(3,2,1), (4,3,2), (4,2,1), (4, 3, 1), \dots \} \)
- \( \{ a : \mathbb{N}; b: \mathbb{N}; c: \mathbb{N} \mid a < b < c \wedge a \not = b \not = c \bullet (a, c) \} \)\( \{(1,3), (1, 4), (2, 4), (3, 5), \dots \} \)
- \( \{ a : \mathbb{N}; S: \mathbb{P}(\mathbb{N}); \mid a \in S \wedge \#(S) = 3 \} \)\( \{ (1, \{1,2,3\}), (2, \{1,2,3\}), (1, \{1,3,4\}), (2, \{1,2,4\}), \dots \} \)
Part 2: Student Universe
The following table describes the properties students in a set $S$.
| Person | Amy | Ben | Clare | Doug | Emma |
|---|---|---|---|---|---|
| tall | X | X | X | ||
| friendly | X | X | |||
| careful | X | X | X | ||
| happy | X | X | X | ||
| busy | X | X | X | ||
| housemate | Clare | Doug | Amy | Ben | |
| dating | Ben | Amy | Emma | Clare | |
| hates | Doug | ||||
| admires | Emma | Emma | Emma | Emma | Emma |
Exercise 5
We can say several things about this group of students. For each of the following, describe in words what is being claimed, and state whether or not the proposition is true.
- $(\exists x) ( tall(x) )$ Someone is tall (true)
- $(\forall x) ( careful(x) \vee happy(x) )$ Everyone is either careful or happy (true)
- $(\forall x) ( \neg tall(x) \implies friendly(x) )$ Everyone who is not tall is friendly (true)
- $\neg (\exists x,y ) ( dating(x,y) \wedge hates(x,y) )$ There is no couple who are dating where one hates the other. / It is not the case that there exists two people $a$ and $b$, where $a$ is dating $b$ and $a$ hates $b$ (true)
- $\neg (\exists x, y) ( housemate(x,y) \wedge \neg housemate(y,x) ) \Longleftrightarrow (\forall(x,y)) (housemate(x,y) \implies housemate(y,x))$ It is equivalent to state "no one's housemate doesn't have them as a housemate", or "everyone's housemate has them as a housemate". / There is no pair of people $a$ and $b$ where $a$ is the housemate of $b$, but $b$ is not the housemate of $a$ if and only if for all pairs of people $x$ and $y$, if $x$ is a housemate of $y$ then $y$ is a housemate of $x$ (true)
Exercise 6
Now express each of the following in predicate logic, and state whether the proposition is true.
- There is somebody who is admired by everybody \( (\exists x)( (\forall y) ( admires(y, x) ) ) \) This proposition is true.
- Somebody admires themself \( (\exists x)( admires(x, x) ) \) This proposition is true.
- Clare is dating somebody \( (\exists x)( dating(Clare, x) ) \) This proposition is true.
- Everybody hates Doug \( (\forall x)( hates(x, Doug) ) \) This proposition is false.
- Everybody is tall or friendly \( (\forall x)( tall(x) \vee friendly(x) ) \) This proposition is true.
- If everybody has a housemate, then everybody is careful and friendly \( (\forall x)( (\exists y) housemate(x, y) ) \implies (\forall x)(careful(x) \wedge friendly (x) ) \) This proposition is true.