COMP 1002 Winter 2019
Homework Assignment # 3
Due: Feb 16, by 10pm
(Type it up and upload on D2L)
YOUR NAME HERE


  1. Predicate logic [50]
    Consider the following statements.

    1. Write the first statement as a predicate logic formula with"$x=y$\" and "$x

      *Solution:\ *

    2. Similarly, write a formula for the second statement using predicates \"$Parent(x,y)$\" and $x = y$. A cousin is a child of a sibling of a parent; you will need to come up with a predicate logic formula true for a pair of people that are cousins first, and then use it to make a formula for the statement above. You can shorten $Parent(x,y)$ to $P(x,y)$ to make your formula shorter.

      *Solution:\ *

    3. For both statements, give an example of a domain and, if needed, interpretations of predicates which make it true. You can use the same domain for all quantified variables in each formula. Either describe the domains (e.g. by listing elements) or refer to ones from the slides. You can make up your own domains of people by listing names.

      *Solution:\ *

    4. For both statements, give a counterexample (a domain and interpretations of predicates)

      *Solution:\ *

    5. Write negations of formulas from (a) and (b), pushing negations inside to predicates.

      *Solution:\ *

    6. Write English sentences corresponding to negations of the original statements, pushing negations inside again. You can talk about cousins directly.

      *Solution:\ *

  2. Proofs. In the problems below, start with restating the problem statement using quantifiers. In the proof itself, say when you are using universal/existential instantiation and generalization. State explicitly which definitions you are using and when, and show all proof steps (including algebra).

    1. For any real number $x$, an integer $y$ is called the ceiling of $x$ (written as $y=\lceil x \rceil$) if and only if it is the smallest integer greater than or equal to $x$.

      1. Write the definition above as a predicate logic formula. Use $<$, $\leq$ and $=$ predicates, and mention $\lceil x \rceil$.

        *Solution:\ *

      2. Give a proof that every rational number $x$ has a $\lceil x \rceil$. Use definitions of a rational number and quotient-remainder theorem from the slides, and the definition of a ceiling above.

        *Solution:\ *

      3. Disprove by giving a counterexample that for every real number $x$, $\lceil 2x \rceil = 2\lceil x \rceil$.

        *Solution:\ *

    2. Prove by contradiction that for any integer $n$, $n^2-3$ is not divisible by 9. Use the following definition of divisibility: $n\in\mathbb{Z}$ is divisible by $m\in\mathbb{Z}$ if and only if $\exists k\in \mathbb{Z}\ n=km$. You can use as a lemma that if a square of a number is divisible by 3, the number itself is divisible by 3.

      *Solution:\ *