% !TEX program = pdflatex
% ---------------------------------------------------------------------------
\documentclass[10pt,a4paper,english]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{physics}
\usepackage{enumitem}
\usepackage{xcolor}
\usepackage{fancyvrb}
\usepackage{nth}
% redefine \VerbatimInput
\RecustomVerbatimCommand{\VerbatimInput}{VerbatimInput}%
{fontsize=\footnotesize,
%
commandchars=\|\(\), % escape character and argument delimiters for
% commands within the verbatim
commentchar=* % comment character
}
\title{CS40 Winter 2021 Homework \#2}
\begin{document}
\maketitle
\paragraph{Notes}
\begin{itemize}
\item
You may work with a partner in order to understand the problems and discuss how to approach them.
If you do so, write clearly on your assignment the name of the student you collaborated with.
\item
Please re-read the ``Conduct'' section in the class syllabus.
\item
No late submissions! Turn-in what you have by the deadline.
\end{itemize}
\dotfill
\begin{enumerate}
\item
Prove the following equivalences by using a series of logical equivalences.
Justify each step by stating which rule is applied.
\begin{enumerate}
\item $\neg\qty[r \lor \qty(q \land \qty(\neg r \to \neg p))] \equiv \neg r \land \qty(p \lor \neg q)$
\item $\qty[q \land \qty(p \to \neg q)] \to \neg p \equiv \mathbf{T}$
\end{enumerate}
\item
Express the following propositions in Conjunctive Normal Form:
\begin{enumerate}
\item $p \lor q$
\item $p \to \qty(q\land r)$
\item $\neg\qty(\neg p \lor q)\lor(r\to \neg s)$
\end{enumerate}
\item
Express the negation of the following sentences in English, as simply as you can (using quantifiers, and do not start with ``It is not the case that ...")
\begin{enumerate}
\item Every student in the class likes movies.
\item Some student has been to every state except Alaska.
\item No student has ever been to a castle in Germany.
\item There is a student in the class who has been in every classroom on this campus.
\item Some students like movies and some students like operas.
\end{enumerate}
\item
Negate ``Some integer is negative and all integers are positive.''
Write your answer in English, try to simplify.
\item
Let $P(x, y)$ be the statement ``Student $x$ has taken class
$y$,'' where the domain for $x$ consists of all students in your
class and for $y$ consists of all computer science courses at your school.
Express each of these quantifications in English:
\begin{enumerate}
\item $\exists x \exists y P(x,y)$
\item $\exists x \forall y P(x,y)$
\item $\forall x \exists y P(x,y)$
\item $\exists y \forall x P(x,y)$
\item $\forall y \exists x P(x,y)$
\item $\forall x \forall y P(x,y)$
\end{enumerate}
\item
Write the following facts about real numbers in predicate logic (do not use the uniqueness quantifier, $\exists !$):
\begin{enumerate}
\item
``Given a number, there is a number smaller than it.''
\item
``Given a number, there is a unique number which is greater by one than it.''
\item
``Given a non-zero number, its square is positive.''
\item
``The product of two positive numbers is positive.''
\end{enumerate}
\item
Let \\
$C(x)$: ``x is a Computer Science major'',\\
$M(y)$: ``y is a math course'', and\\
$T(x, y)$: ``$x$ is taking $y$'', \\
where $x$ represents students and $y$ represents courses.
Write the following statement in English, using the predicates:
$$ \forall x \ \exists y \ \qty[C(x) \to M(y) \land T (x, y)] $$
\item
Rewrite each of the following statements so that the negations appear only within predicates
(i.e., no negation is outside a quantifier or an expression involving logical connectives):
\begin{enumerate}
\item
$ \neg\forall x \forall y \qty[P(x,y) \to Q (x, y)] $
\item
$ \neg\forall x \qty[\exists y \forall z P(x,y,z) \lor \exists z \forall y \neg Q(x,y,z)] $
\end{enumerate}
\item
Find a common domain for the variables $x$, $y$ and $z$
for which the statement $\forall x\forall y\qty[(x \neq y) \to \forall z((z = x) \lor (z = y))]$ is true and
another domain for which it is false.
\item
Prove the following propositions.
\begin{enumerate}
\item If $x$ and $y$ are integers and $xy$ is even, then $x$ is even or $y$ is even.
\item If $x$ is a positive integer, then $x$ is even if and only if $3x + 2$ is even.
\end{enumerate}
\item
Use proof by contradiction to prove the following:
\begin{enumerate}
\item In a room of 13 people, 2 or more people have their birthdays in the same month.
\item If $r$ is a rational number, then $ r+ \sqrt{2}$ is irrational.
\item An even perfect square cannot be of the form $ 4k+1$.
\end{enumerate}
\item
Prove that if $n$ is any integer not divisible by 5, then its square is of the form $5k+1$ or $5k+4$ (for example $13^2 = 5 \cdot 33 +4$ and $9^2 = 5 \cdot 16+1$).
\end{enumerate}
\end{document}