HW03DanielShchur.tex

\documentclass[12pt,letterpaper]{article}

\usepackage{bm}
\usepackage{forest}
\usepackage[letterpaper, margin=.75in]{geometry}

\newcommand{\problem}{\vspace{.5cm}\textbf{Problem:~~}}
\newcommand{\answer}{\emph{Answer:~~}}
\newcommand{\ansindent}{\indent\hspace{0.5cm}}
\newcommand{\answerindent}{\hangindent=.5cm\hangafter=0\answer}
\newcommand{\ansend}{\vspace{0.25cm}\\}

\setlength{\parindent}{0pt}
\setlength{\parskip}{0cm}
\setlength{\intextsep}{.25cm}

\title{CSCE 235H Homework 03}
\author{Daniel Shchur}

\begin{document}

\maketitle

\problem (\#10 S1.4 Pg53) Let $C(x)$ be the statement ``$x$ has a cat,'' let $D(x)$ be the statement ``$x$ has a dog,'' and let $F(x)$ be the statement ``$x$ has a ferret.'' Express each of these statements in terms of $C(x), D(x), F(x)$, quantifiers, and logical connectives. Let the domain consist of all students in your class.

\begin{enumerate}

\item[a)]A student in your class has a cat, a dog, and a ferret.
  \begin{enumerate}
  \item[]\answer $\exists x (C(x) \wedge D(x) \wedge F(x))$
  \end{enumerate}

\item[b)]All students in your class have a cat, a dog, or a ferret.
  \begin{enumerate}
  \item[]\answer $\forall x (C(x) \wedge D(x) \wedge F(x))$
  \end{enumerate}
  
\item[c)]Some student in your class has a cat and a ferret, but not a dog.
  \begin{enumerate}
  \item[]\answer $\exists x (C(x) \wedge F(x) \wedge \neg D(x))$
  \end{enumerate}

\item[d)]No student in your class has a cat, a dog, and a ferret.
  \begin{enumerate}
  \item[]\answer $\neg \exists x (C(x) \wedge D(x) \wedge F(x))$
  \end{enumerate}

\item[e)]For each of the three animals, cats, dogs, and ferrets, there is a student in your class who has this animal as a pet.
  \begin{enumerate}
  \item[]\answer$\exists x,y,z (C(x) \wedge D(y) \wedge F(z))$
  \end{enumerate}

\end{enumerate}


\problem (\#14 S1.4 Pg53) Determine the truth value of each of these statements if the domain consists of all real numbers.

\begin{enumerate}

\item[a)]$\exists x (x^3 = -1)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[b)]$\exists x (x^4 < x^2)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\item[c)]$\forall x ((-x)^2 = x^2)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[d)]$\forall x (2x>x)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}

\problem (\#28 S1.4 Pg54) Translate each of these statements into logical expressions using predicates, quantifiers, and logical connectives.

\begin{enumerate}

\item[a)]Something is not in the correct place.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[b)]All tools are in the correct place and are in excellent condition.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\item[c)]Everything is in the correct place and in excellent condition.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[d)]Nothing is in the correct place and is in excellent condition.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[e)]One of your tools is not in the correct place, but it is in excellent condition.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}

\problem (\#32 S1.4 Pg55) Express each of these statements using quantifiers. Then form the negation of the statement so that no negation is to the left of a quantifier. Next, express the negation in simple English. (Do not simply use the phrase ``It is not the case that.'')

\begin{enumerate}

\item[a)]All dogs have fleas.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[b)]There is a horse that can add.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\item[c)]Every koala can climb.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[d)]No monkey can speak French.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[e)]There exists a pig that can swim and catch fish.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}


\problem (\#34 S1.4 Pg55) Express the negation of these propositions using quantifiers, and then express the negation in English.

\begin{enumerate}

\item[b)]All Swedish movies are serious.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[c)]No one can keep a secret.
  \begin{enumerate}
  \item[]\answer 
  \end{enumerate}
  
\item[d)]There is someone in this class who does not have a good attitude.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}

\problem (\#36 S1.4 Pg55) Find a counterexample, if possible, to these universally quantified statements, where the domain for all variables consists of all real numbers.

\begin{enumerate}

\item[a)]$\forall x (x^2 \neq x)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[b)]$\forall x (x^2 \neq 2)$
  \begin{enumerate}
  \item[]\answer 
  \end{enumerate}
  
\item[c)]$\forall x (|x| > 0)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}

\problem (\#38 S1.4 Pg55) Translate these system specifications into English where the predicate $S(x, y)$ is ``$x$ is in state $y$'' and where the domain for $x$ and $y$ consists of all systems and all possible states, respectively.

\begin{enumerate}

\item[b)]$\forall x(S(x$, malfunctioning$) \vee S(x$, diagnostic))
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[e)]$\forall x \neg S(x$, working)
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\end{enumerate}

\problem (\#6 S1.5 Pg65) Let $C(x, y)$ mean that student $x$ is enrolled in class $y$, where the domain for $x$ consists of all students in your school and the domain for $y$ consists of all classes being given at your school. Express each of these statements by a simple English sentence.

\begin{enumerate}

\item[a)]$C$(Randy Goldberg, CS 252)
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[b)]$\exists x C(x$, Math 695)
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\item[d)]$\exists x (C(x$, Math 222$) \wedge C(x$, CS 252)
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}

\problem (\#10 S1.5 Pg65) Let $F(x, y)$ be the statement ``$x$ can fool $y$,'' where the domain consists of all people in the world. Use quantifiers to express each of these statements.

\begin{enumerate}

\item[e)]Everyone can be fooled by somebody.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[g)]Nancy can fool exactly two people.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\item[h)]There is exactly one person whom everybody can fool.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[i)]No one can fool himself or herself.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[j)]There is someone who can fool exactly one person besides himself or herself.
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}

\problem (\#28 S1.5 Pg67) Determine the truth value of each of these statements if the domain of each variable consists of all real numbers.

\begin{enumerate}

\item[a)]$\forall x \exists y (x^2 = y)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[c)]$\exists x \forall y (xy = 0)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\item[e)]$\forall x(x \neq 0 \rightarrow \exists y(xy = 1))$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[g)]$\forall x \exists y (x + y = 1)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[i)]$\forall x \exists y (x + y = 2 \wedge 2x - y = 1)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}

\problem (\#30 S1.5 Pg67) Rewrite each of these statements so that negations appear only within predicates (that is, so that no negation is outside a quantifier or an expression involving logical connectives).

\begin{enumerate}

\item[b)]$\neg \forall x \exists P(x, y)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[d)]$\neg \exists y (\exists x R(x, y) \vee \forall x S(x, y))$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\item[e)]$\neg \exists y (\forall x \exists z T(x, y, z) \vee \exists x \forall z U(x, y, z))$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}
  
\end{enumerate}

\problem (\#40 S1.5 Pg68) Find a counterexample, if possible, to these universally quantified statements, where the domain for all variables consists of all integers.

\begin{enumerate}

\item[a)]$\forall x \exists y(x = 1/y)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[b)]$\forall x \exists y(y^2 - x < 100)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\item[c)]$\forall x \forall y(x^2 \neq y^3)$
  \begin{enumerate}
  \item[]\answer
  \end{enumerate}

\end{enumerate}

\problem (\#48 S1.5 Pg68) Show that $\forall x P(x) \vee \forall x Q(x)$ and $\forall x \forall y (P(x) \vee Q(y))$, where all quantifiers have the same nonempty domain, are logically equivalent. (the new variable $y$ is used to combine the quantifications correctly.)\vspace{.25cm}

\answerindent

\end{document}