\documentclass{amsart} % 
\usepackage{fullpage}
\usepackage{graphicx}
\usepackage{graphics}
\usepackage{psfrag}
\usepackage{amsmath,amssymb}
%\input{preface}

\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9in}

\title{Math 214 Sample Homework Solution}
\date{}


\begin{document} 
\maketitle


%Solve the following problems.  Due Feb 5, 2009. 



\bigskip

\begin{enumerate}
% taken from http://www.hku.hk/cgi-bin/philodep/knight/puzzle, puzzle 55
\item {\em Recall the Knights and Knaves from the first day of class.  Recall
  that knights always tell the truth, and knaves always lie. You meet
  three inhabitants: Patricia, Quinn and Roberta. Patricia claims that
  it's false that Roberta is a knave. Quinn says, `Either Roberta is a
  knight or I am a knight.' Roberta says that Quinn is a knave.  Who are
  knights and who are knaves?  Prove your answer (using truth table).}
  
  \bigskip
  
  \item[] {\bf  Solution:}    Let $P$ be ``Patricia is a knight'', $Q$ be ``Quinn is a knight'', and $R$ be ``Roberta is a knight''. 
  Then what Patricia claimed is $\neg(\neg R)$, what Quinn said is $R\vee Q$, and what Roberta said is $\neg Q$.  Since the above sentences have two sources of truth values:  by its speaker and by its content, we have the following truth table. 
  
 \[
 \begin{tabular}{|c|c|c|c|c|c|}\hline
 P  & Q & R & $\neg(\neg R)$ &  $R\vee Q$  &  $\neg Q$ \\ \hline
 T  &  T & T &  T/T                  &   T/T             &  T/F\\
 T  &  T & F  & T/F                  &                     &       \\
 T &  F  & T  & T/T                  &   F/T             &   \\
 T &  F  & F  & T/F                  &                      &        \\
 F  & T  & T  & F/T                  &                      &        \\
 F  & T  & F  & F/F                  &  T/T               &  F/F\\
 F  & F   & T & F/T                  &                       &     \\
 F  & F   & F &  F/F                &  F/F                & F/T\\ \hline
  \end{tabular}
 \]
 
 So the answer is: Patricia is a knave, Quinn is a knight, and Roberta is a knave. 
 
 \bigskip
  


 
 
  
\item {\em By using truth tables prove that, for all statements P and Q, the statement `P$\Rightarrow$ Q' and `(not Q)$\Rightarrow$ (not P)' are equivalent. }

\bigskip

\item[] {\bf Solution:} By definition of logically equivalent of two statements, we just need to show that $P\Rightarrow Q$ and $(\neg Q)\Rightarrow (\neg P)$ have the same truth table. 

\[
\begin{tabular}{|c|c|c|c|} \hline
P   &  Q   &   P$\Rightarrow$ Q     &   $(\neg Q)\Rightarrow (\neg P)$\\ \hline
T  &   T   &    T                           &   T \\ 
T   &  F   &    F                           &   F \\
F   &  T   &    T                           &   T\\
F   &  F   &    T                           &   T\\ \hline
\end{tabular}
\]



\item {\em Prove that for all real numbers $a, b$ and $c$, 
\[   bc+ac+ab\le a^2+b^2+c^2.  \]}

\bigskip

\item[] {\bf Solution:}  For real numbers $a, b$ and $c$, we have $(a-b)^2, (a-c)^2, (b-c)^2\ge 0. $
So $$(a-b)^2+(a-c)^2+(b-c)^2\ge 0.$$  Since $(a-b)^2+(a-c)^2+(b-c)^2=(a^2-2ab+b^2)+(a^2-2ac+c^2)+(b^2-2bc+c^2)=2(a^2+b^2+c^2)-2(ab+ac+bc)\ge 0, $  we have $2(a^2+b^2+c^2)\ge 2(ab+ac+bc)$.  Thus $bc+ac+ab\le a^2+b^2+c^2$. 

\bigskip

\item {\em Prove that for all real numbers $a$ and $b$, 
\[  |a|<|b| \Rightarrow a^2\le b^2.  \] }

\bigskip

\item[] {\bf Solution:} Let $c=|a|, d=|b|$. Then both $c$ and $d$ are non-negative real numbers, $c<d$, and $c^2=a^2, d^2=b^2$.  From $c<d$, by multiply both sides by $c$, we have $c^2<cd$ (if $c>0$) or $c^2=cd$ (if $c=0$). So $c^2\le cd$.  On the other hand, from $c<d$ by multiply both sides by $d$, we have $cd<d^2$.  Therefore, $c^2\le cd<d^2$, we have $c^2<d^2$, which implies that $c^2\le d^2$. 

\bigskip


\item {\em Prove that in  a graph the number of vertices with odd degrees is even.} 
\bigskip

\item[] {\bf Solution:} Suppose by contradiction that a graph has odd number of vertices with odd degrees.  Then the sum of odd degrees is odd. We also know that the sum of even degrees is even. Since the sum of degrees is the sum of odd degrees and the sum of even degrees, the sum of all degrees is odd. This is a contradiction to the fact that the degree sum of any graph is even.  

\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: 
