% 
% hw2.tex
%
%   This is LaTeX template to get you started
%   making problem-set solutions
%
 
\documentclass[11pt]{article}
\usepackage{amsthm,amsmath, amssymb}
\setlength{\oddsidemargin}{0in}
\setlength{\evensidemargin}{0in}
\setlength{\textheight}{9.0in}
\setlength{\textwidth}{6.5in}
\setlength{\topmargin}{-0.5in}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\title{\bf Data, Logic, and Computing\\[2ex] 
       \rm\normalsize ECS 17 (Winter 2026)}
\date{\today}
\author{Patrice Koehl\\koehl@cs.ucdavis.edu}

\begin{document}
\maketitle
\section*{\underline{Homework 6 }}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 1 }

Let $p$, $q$, and $r$ be three propositions. Using truth tables or logical equivalences, indicate which (if any) of the propositions below are tautologies, contradictions, or neither.

\begin{itemize}
\item [a)] $A = (p\land q) \lor r \lor (\lnot q \land \lnot r) \lor (\lnot p \land \lnot r)$

\item[b)] $[ p \lor ( q \rightarrow r) ] \rightarrow (p \lor q \lor r)$

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 2 } 

Let $n$ be a positive integer. Show that $n$ is even if and only if $7n+4$ is even.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 3 }

Let $a$ and $b$ be two positive integers. Prove that if $n=ab$, then $a \leq \sqrt{n}$ or $b \leq \sqrt{n}$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 4}

Let $m$ and $n$ be two integers. Show that if $m > 0$ and $n \le -2$, then $m^2 + mn + n^2 \ge 0$

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 5}

Let $a$ and $b$ be two integers. Show that if $a^2+b^2$ is even, then $a+b$ is even:
\begin{itemize}
\item [a)] Using an indirect proof (proof by contrapositive)

\item [b)] Using a proof by contradiction

\item [c)] Using a direct proof

\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section*{Exercise 6 }

This exercise relates to the inhabitants of the island of knights and knaves, where knights always tell the truth and knaves always lie. John and Bill are residents.
John tells you: ``if Bill is a knave, then I am a knight", while Bill tells you: ``if John is a knave and I am a knight, then 2+2=5". 
Can you say what John and Bill are?


\end{document}