% !TEX program = pdflatex
% ---------------------------------------------------------------------------
\documentclass[10pt,a4paper,english]{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathtools}
\usepackage{physics}
\usepackage{enumitem}
\usepackage{tikz}
\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 \#1}
\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
State whether or not each sentence is a proposition. If it is a proposition, what is its truth value?
\begin{enumerate}
\item Paris is the capital of Denmark.
\item Don’t eat the daisies.
\item Take two aspirin and call me in the morning.
\item x + 3 = 7 and x = 4
\item 2 + 7 = 9
\item 2 – 7 = 5
\item This statement is false.
\end{enumerate}
\item
Write the negation of each of these propositions:
\begin{enumerate}
\item George Washington was the first president of the United States.
\item 1 + 5 = 7
\item It is hot today.
\item 6 is negative.
\end{enumerate}
\item
Is the use of “or” in these English sentences intended to be inclusive or exclusive?
\begin{enumerate}
\item ``If you fail to make a payment on time or fail to pay the amount due, you will incur a penalty.''
\item ``If I can’t schedule the airline flight or if I can’t get a hotel room, then I can’t go on the trip.''
\item ``She has one or two brothers.''
\item ``If you do not wear a shirt or do not wear shoes, then you will be denied service in the restaurant.''
\end{enumerate}
\item
A sign at the entrance of a restaurant declares: ``No shoes, no shirt, no service.''
Write this sentence as a conditional proposition.
\item
Write the negation of the statement ``If you pay your membership dues, then if you come to the club, you can enter free''.
\item
Write the contrapositive, converse, and inverse of the following propositions:
\begin{enumerate}
\item ``If the number is positive, then its square is positive.''
\item ``I stay home whenever it is stormy.''
\end{enumerate}
\item
Let $p$ stand for the proposition ``I did well in CS40'', and $q$ for ``I understand discrete mathematics''.
Express the following as natural English sentences:
\begin{enumerate}
\item $\neg p$
\item $p \lor q$
\item $p \land q$
\item $p \to q$
\item $\neg p \to \neg q$
\item $\neg p \lor \qty(p \land q)$
\end{enumerate}
\item
Suppose $u$ represents ``you understand the material'', $s$ represents ``you study the theory'', and $w$
represents ``you work on exercises''.
Write the following compound proposition using $u$, $s$, $w$ and the
appropriate connectives:
``You study the theory and work on exercises, but you don’t understand the material''.
\item
Show that $\quad \neg p \to \qty(q \to r) \qand q \to \qty(p \lor r) \quad$ are logically equivalent.
\item
Use a truth table to verify:
\begin{enumerate}
\item The first De Morgan’s Law: $\quad \neg\qty(p \land q) \equiv \neg p \lor \neg q$
\item The second De Morgan’s Law: $\quad \neg\qty(p \lor q) \equiv \neg p \land \neg q$
\end{enumerate}
\item
Show that each of these conditional statements is a tautology by using truth tables.
\begin{enumerate}
\item $[\neg p\land(p\lor q)]\rightarrow q$
\item $[(p\rightarrow q)\land(q\rightarrow r)]\rightarrow (p\rightarrow r)$
\item $[p\land(p\rightarrow q)]\rightarrow q$
\item $[(p\lor q)\land(p\rightarrow r)\land (q\rightarrow r)]\rightarrow r$
\end{enumerate}
\item
Solve the following logic puzzles:
\begin{enumerate}
\item You come across two people. $P$ says ``I am lying if $Q$ is," and $Q$ says, ``$P$ is lying if I am." Can you tell who if anyone is telling the truth?
\item You come across three people. $P$ says, ``If $Q$ is lying, then so is $R$," $Q$ says, ``If $R$ is lying, then so is $P$," and $R$ says, ``If $P$ is lying, then so is $Q$." Who if anyone is telling the truth?
\end{enumerate}
\end{enumerate}
\end{document}