Review:
Vocabulary
- Canonical CNF, canonical DNF, Boolean functions
- Sets, $\emptyset, \mathbb{N, Z, Q, R}$.
- Predicates, domain (universe) of a predicate, existential and universal quantifiers, predicate logic
- Free and bound variables, scope of quantifiers, prenex form.
- Universal modus ponens, rules of inference in predicate logic, universal/existential instantiation/generalization
Individual work
Solve each of the following exercises.
- For each of the following Boolean functions, construct a canonical CNF and a canonical DNF. Hint: you can write the whole truth table, but you don't necessarily need to.
- $AllTheSame(x,y,z)$ which returns true when either all its inputs are true, or all its inputs are false.
- $Parity(x,y,z)$ which returns true when an odd number of its inputs are true (that is, either one or three)
- Let $x = y, x < y, Even(x)$ and $Prime(x)$ be predicates. Translate the following from English to logic (you can use standard arithmetic operations). Make sure to specify domains of quantifiers using $\mathbb{N, Z, Q, R}$, and note which of these statements are true, and which are false.
- Every integer greater than n is not prime.
- There is a smallest natural number.
- If an integer gives the same value when multiplied by two different integers, that integer must be 0. (Hint: in order to ensure that two variables take different values state explicitly that they are not equal.)
- Which of the following pairs consist of equivalent formulas? That is, when is $F \equiv G$ for formulas below?
- $F=\forall x \forall y P(x,y)$, $G= \forall y \forall x P(x,y)$
- $F = \forall x \exists y P(x,y)$, $G = \forall y \exists x P(x,y)$
- $F=\forall x \forall y P(y,x)$, $G= \forall x \forall y P(x,y)$
- $F = \forall x \exists y P(x,y)$, $G = \exists x \forall y P(x,y)$
- Let Parent(x,y), read as "x is a parent of y", and Female(x) be a predicates over the domain of people. Say which relationship between people denoted by free variables the following formulas describe (for example, $\exists y, Parent(x,y)\wedge Parent(y,z)$ states that x is a grandparent of z).
- $Parent(x,y)\wedge Female(x)$
- $\exists z Parent(z,x) \wedge Parent(z,y)$
- $\exists z \exists u Parent(z,x) \wedge Parent(z,u) \wedge Parent(u,y) \wedge \neg Female(x)$
- As before, take predicates Parent(x,y) and Female(x) be a predicates over the domain of people. Now, say in English what facts about people denoted by free variables these formulas describe.
- $\forall y \neg (\exists z Parent(z,y) \wedge Parent(z,x) \wedge Female(y)) $
- $Female(x) \wedge \forall y (\exists z Parent(z,y) \wedge Parent(z,x)) \to y=x $
- $\forall z (Parent(z,x) \leftrightarrow Parent(z,y))$
Group exercises
For this part of the lab, you will be working in groups of three. In the first part of the exercise, each of three people in the group picks one of the topics below, and solves the corresponding questions. Then, each of you will explain to two of your peers how you have solved these questions. Your explanation should be good enough that they can then solve similar questions on their own.
Topic 1: Quantifiers over finite domain
Recall that $\forall$ quantifier corresponds to $\wedge$ over elements of its domain, and $\exists$ quantifier, respectively, is an $\vee$ over elements of its domain. For the following formulas, take $x \in \{1,2,3\} $ and the domain of $y$ to be all integers such that $2 < y <5$. Now, write these formulas in propositional form by converting $\forall$ to $\wedge$ and $\exists$ to $\vee$ (hint: you should end up with propositions where a variable is replaced with a number from its domain). For each of them, say whether the formula is true or false on these domains with the standard interpretation of the predicates.
- $\forall y, Even(y) \vee y > 3 $
- $(\exists x, x<2) \wedge (\exists y, y < 2) $
- $\forall x \exists y, x = y $
Topic 2: Prenex form of a formula
Recall that a formula is in prenex form when each quantified variable has a unique name, and all quantifiers are in front of the formula. Now, convert each of the following into prenex form. For simplicity, start by opening up implications using $F \to G \equiv \neg F \vee G$ rule.
- $\forall x (\exists y P(x,y)) \to (\exists y Q(x,y))$
- $ (( \exists x P(x)) \to (\exists x \neg P(x))) \to (\exists x \forall y P(x) \vee \neg P(y)) $
Topic 3: Negating quantified formulas
For each of the following formulas, negate them and simplify until all negations are on predicates. Use DeMorgan, double negation, definitions of implication and quantifiers.
- $\forall x \forall y \exists z, P(x,z) \wedge P(y,z) \to Q(x,y)$
- $\exists x \forall y Q(y,z) \wedge ((\forall z P(x,y,z)) \to Q(x,y))$
Review after the group exercises
Let $ F=(\exists x P(x)) \to (\exists x \neg P(x))$.
- Convert F into prenex form (and get rid of the implication).
- Negate the formula from the previous subquestion, and simplify it until all negations are on predicates.
- Now, suppose that the domain of x is $\{black, blue, green\}$. Write the original $F$ as a propositional formula by replacing $\forall$ with $\wedge$ over the domain, and $\exists$ with $\vee$. Is this formula true for P(x)= 'the word x starts with letter "b"'?.