Question I: basic logic

  1. Write the truth table for \(P\land Q\) (AND: logical conjunction).
  2. Write the truth table for \(P\mathrel{\oplus} Q\) (eXclusive OR: one or other, but not both).
  3. Write the truth table for \(P\Rightarrow Q\) (implication).
  4. (Unmarked) Write the truth table for \(\top\) (truth).
  5. Assume a type \(X\). What is the truth-value of \(\forall x:X\bullet x=x\)?
  6. What does the predicate \(\forall x:X\bullet x\neq x\) tell us about the type \(X\)?
  7. How about \(\forall x:X\bullet \bot\)? (Hint)
    This does not say “every element is false”. Elements are not true or false; predicates are true or false. So what does it tell you about $X$ if “false” is true of every $x$ in $X$?
  8. What does the predicate \(\exists x:X\bullet \top\) tell us about the type \(X\)? (Hint)
    So in English this says that there exists $x:X$ such that $\top$ is true of $x$. But what does that tell us about $X$?
  9. (Unmarked) Simplify the predicate \(\exists x:X\bullet \bot\).
  10. Write a predicate to express that the type \(X\) has exactly one element.
  11. Write a predicate to express that the type \(X\) has at most two elements, using only sets notation, logical connectives, quantifiers, and equality.
  12. Assume a unary predicate \(P\). Write a predicate to express that \(P(x)\) holds for some \(x:X\).
  13. Write a predicate to express that there exists an \(x:X\) such that if \(P(x)\) holds, then for all \(x’:X\), \(P(x’)\) holds. (Hint)
    So we have an “if-then”, which translates to $\Rightarrow$ (implies), and we have a quantifier “$\forall x’:X$”. Be careful to nest these correctly. Quantifier nesting is a delicate business.
  14. (Unmarked) Simplify the predicate of the previous question. (Answer)
    This simplifies to $\exists x:X\bullet\top$, regardless of $P$. Since, if $P(x)$ holds for all $x$ then the implication is valid because its RHS is true, and if $P(x)$ holds for no $x$ then pick one such $x$ and the implication is valid because its LHS is true. Thus, so long as some $x$ exists in $X$, we are OK. This is a famous logical brain-teaser from philosophy. My brother taught it to me when he was studying Philosophy as an undergraduate; the dinnertable conversation at home was wild stuff.

Question II: complex predicates

The syntax for writing out quantifiers is given in lecture 2. See slide 11 and surrounding slides.

Assume a function \(g:\mathbb N\rightarrow\mathbb Z\). Assume that \(g\) represents quality of life at day \(i\). So e.g. \(g(0)\) is the quality of life at the beginning of time, and \(g(10)\) is the quality of life at “day 10”.
- Larger values of \(g(i)\) are considered “better”, lower values are considered “worse”.
- Above zero values are considered “good”.
- Below zero values are considered “bad”.
- We fix a day \(i>0\) which we call “today”.
For example: “Tomorrow will be no worse than today” is rendered in predicate logic as \(g(i+1)\geq g(i)\).

With the above in mind, translate the following English assertions into predicate logic:

  1. Things are good (today).
  2. Tomorrow will be good.
  3. Yesterday, things were bad.
  4. Things can only get better (from today onwards; there are at least two interpretations of this, so explain in English which one you are using). (Hint)
    I’m getting all kinds of crazy answers to this. Read this question carefully: from today. So if you quantify over all days including days in the past, then your answer is wrong.
  5. Things can’t get any worse (than they are today).
  6. For every day, there are always both good days and bad days in the future. (Hint)
    Your answer should not mention $i$ because the question does not mention “today”; it explicitly quantifies over all days by saying “For every day”.
  7. From today, every day will be at least twice as good as the day before it.
  8. Things will get worse before they get better.
  9. (Unmarked) Tomorrow is another day (in other words, there is no particular connection between how good today is, and how good tomorrow will be). (Answer)
    My favourite answer so far: $\exists x:\mathbb N\bullet x>i$.
Back


Question III: sets

The syntax for writing out sets expressions (sets comprehension) is given on slide 10 of lecture 3.

  1. Assume an integer \(y:\mathbb N\). Write, giving full types (that means: tell me the type of the sets expression, and don’t forget to type all the variables mentioned in it), a sets expression for the set of numbers divisible by \(y\).
  2. Write, giving full types, a sets expression for the set \(primes\) of prime numbers.
  3. Write, giving full types, a sets expression for the set of three-digit numbers that are equal to the sum of the cubes of their digits.
    If we write \(f(n)\) for the sum of the cubes of the digits of \(n\) then \(f(14)\) equals \(1^3+4^3\) equals \(65\neq 14\), whereas \(f(153)\) equals \(1^3+5^3+3^3\) equals \(1+125+27\) equals \(153\).
    (This sets expression can be simplified to \(\{153,370,371,407\}\). See the Narcissistic numbers.)
  4. Write, giving full types, a sets expression for the set of pairs of prime numbers separated by 2 (twin primes; e.g. \(12\pm 1\) or \(3756801695685\times 2^{666669}{\pm}1\)).
    So each element of the set you specify should itself be a set, containing precisely two prime numbers.
  5. Assume a type \(X\). Giving full types, write a sets expression for the union of \(S,T:\mathbb P X\) (the elements that are in \(S\) or in \(T\) or in both).
    Sets union is usually written \(S\cup T\).
  6. Giving full types, write a sets expression for the exclusive or of \(S,T:\mathbb P X\) (the elements that are in \(S\) or \(T\) but not in both).
    This is sometimes written \(S\oplus T\), but you can’t use this symbol without first defining it (as this question asks you to do).
  7. Giving full types, write a sets expression for \(\bigcup\mathcal S\) where \(\mathcal S:\mathbb P\mathbb P X\) (the set of elements of elements of \(\mathcal S\)).
  8. Harder Giving full types, write a sets expression for the set of elements that are in a prime number of elements of \(\mathcal S\) (you may assume the set \(primes\) defined above, and you may use cardinality of a set \(\#S\) without comment).
  9. Unmarked A perfect number is equal to the sum of its proper positive divisors (so \(6=1+2+3\)). Specify the set of perfect numbers in Z.

Question IV: schemas

Assume a type \( \mathsf{BOTTLE} \) and an enumerated type \( \mathsf{COLOUR} ::= Green \mid Red \) and a function \( colour : \mathsf{BOTTLE} \rightarrow \mathsf{COLOUR} \).

  1. Write a schema \( \mathit{WallState} \) with state variable \( bottlesOnWall : \mathbb{P} \mathsf{BOTTLE} \), representing a wall with bottles on it.
  2. Write out \( \Delta \mathit{WallState} \) and \( \Xi \mathit{WallState} \) and explain in English what the difference is between these.
  3. I throw a stone at the bottles and miss. No bottles fall. Write a schema \(\mathit{JamieCantThrowToSaveHisLife}\) expressing this.
  4. Somebody else throws a stone at the bottles and knocks a green bottle off the wall. Write a schema \(\mathit{GreenBottleKnocked }\) to express this, using input variable \( \mathit{thisBottle}? \).
    Note that your schema should check just that \( \mathit{thisBottle}? : \mathsf{BOTTLE} \) is green and on the wall.
  5. Write a schema to output the number of green and red bottles on the wall on variables \( \mathit{greenBottles}!, \mathit{redBottles}! : \mathbb N \).
  6. Write a schema \( \mathit{Earthquake} \) such that all bottles fall off the wall.
  7. Harder A green bottle accidentally falls. Write a schema \(\mathit{GreenBottleFalls}\) to express this. Note that there should be no input variable telling us which bottle should fall; some bottle falls by accident and the schema does not specify or control which one.
  8. Write a schema \( \mathit{McCarthy} \) which removes all the red bottles, leaving the green bottles on the wall for later.
Back


Question V: fun with relations

Assume a type $\mathsf{PERSON}$ of people, and assume $p:\mathsf{PERSON}$ and $\mathsf{parentOf}:\mathsf{PERSON}\leftrightarrow \mathsf{PERSON}$. The intuition of $p\mapsto q\in\mathsf{parentOf}$ is that $p$ is the parent of $q$.

  1. Write an expression for $\mathsf{parentOf}^{-1}$ and explain the intuition of $x\mapsto y\in\mathsf{parentOf}^{-1}$. (Hint)
    There are lots of ways of doing this and mostly people are getting it right. But one note on notation: don’t be afraid to write $\{p\mapsto q:parentOf\bullet \dots\}$. Reading all those existential quantifiers is wearing me out.
  2. Write an expression for $\mathsf{dom}(\mathsf{parentOf})$ (the domain of $\mathsf{parentOf}$).
  3. Assume an element $S:\mathbb P\mathsf{PERSON}$. Write a sets expression for relational application $\mathsf{parentOf}(S)$.
  4. Write a sets expression for domain restriction $S\triangleleft\mathsf{parentOf}$.
  5. Write an expression for the children of $p$; here and henceforth you may use without comment any operations defined before the question you are doing (so you can assume $\mathsf{dom}$, relational application $\mathsf{parentOf}(-)$, and domain restriction).
  6. Write an expression for $\mathsf{parentOf};\mathsf{parentOf}$ (the composition of $\mathsf{parentOf}$ with itself).
  7. Write an expression for the great-grandparents of $p$.
  8. Express in logic that nobody is the parent of themselves.
  9. Express in logic that everybody has exactly two parents.
  10. Write an expression for the siblings of $p$ (children of both parents of $p$, other than $p$).
    Assume sets $\mathsf{male}:\mathbb P\mathsf{PERSON}$ and $\mathsf{female}:\mathbb P\mathsf{PERSON}$.
  11. Express in formal logic the assertion that every person is precisely one of male or female.
  12. Translate the assertion “I am your father” into logic, for constants $\mathsf{Luke},\mathsf{Vader}\in \mathsf{male}$ (see Luke, I am your father; get your answer the right way round, please). (Hint)
    If your answer begins with “\( \mathsf{Luke}, \mathsf{Vader} : \mathsf{PERSON} \bullet \)” then it’s wrong: \(\mathsf{Luke}\) and \(\mathsf{Vader}\) are constants declared in the question, so must be left free (unquantified) in the answer.
  13. Write an expression for the uncles of $p$ (brothers of the father of $p$).
  14. Assuming $\mathsf{TC}(\mathsf{parentOf})$ (transitive closure) without comment, assert that everybody is descended from $p$, who is male, and $q$ who is female (see Adam and Eve).
  15. (Harder) Assert that there exists a $p$ such that for every $q$, eventually every descendent of $q$ is also descended from $p$ (hint: you may assume $n$-fold composition of relations, such as $\mathsf{parentOf}^n$, without comment).
    Two such $p$ actually exist: see Mitochondrial Eve and Y-chromosomal Adam.
  16. (Harder) Write an expression for the step-siblings of $p$ (children of a parent of $p$ who share precisely one parent with $p$).
  17. (Unmarked) Assert that the population bottlenecks through $S$; for a fictional account see Children of Men, or for the scientific version see Population Bottlenecks.
  18. (Unmarked) Express in logic the assertion that $q$ is both the sister and the daughter of $p$ (see Chinatown).
Back