\documentstyle[12pt,twoside]{article}
\input{macros-course}

\addtolength{\textheight}{.05in}
\begin{document}

\pset{1}{September 4, 1997}{Start of Class, Tuesday, September 9}

{\bf Reading Assignment: 

Read all of ``The Nuts and Bolts of Proofs'' during the first 2 weeks of class.

Read 1.1-1.5 and 2.3 of Rosen as background for the course.

Read 3.1 of Rosen.}

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Set Identities from 1.5
%Problem 1
\problem

\bparts

\ppart


Establish the following set identity

$(B-A) \cup (C-A) = (B \cup C)-A$

\ppart
The {\em symmetric difference} of two sets is defined by
$A \oplus B = (A-B) \cup (B-A)$.

Show that $A \oplus B = (A \cup B)-(A \cap B)$.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2
%Truth Tables: problem 1.3-8
\problem 
Show that each of the following implications is a tautology by using truth 
tables.

\bparts
\ppart $[\neg p \wedge (p \vee q)] \rightarrow q$
\ppart $[p \wedge (p \rightarrow q)] \rightarrow q$
\ppart $[(p \vee q) \wedge (p \rightarrow r) \wedge (q \rightarrow r)] 
\rightarrow r$
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3
% 1.2 - 25 modified 
\problem Find a compound proposition involving the propositions $p$,
$q$, and $r$ that is false when exactly two of $p$, $q$, and $r$ are
false.  The compound proposition is true otherwise. 


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4
% 1.3 # 8 modified
\problem 

Let $P(x,y)$ be the statement ``$x$ wrote $y$.''
Express each of the following sentences in terms of $P(x,y)$,
quantifiers and logical connectives, where the universe of the
discourse for $x$ is the set of all poets and for
$y$ is the set of all poems.

\begin{description}
\item[a)] There is a poet who wrote ``The Raven'' 
\item[b)] Every poet has written a poem.
\item[c)] Not every poem has been written by a poet.
\item[d)] There is a poet who has written ``The Lady of Shallot'' and the 
``Lotus Eaters''
\item[e)] At least two poets have written a poem with the name
    ``Ulysses'' (Don't introduce numbers.  You will have to add one more
  standard symbol for this one).

\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 5
\problem 
Show that $\exists z \forall x \exists y Q(x,y,z)$ implies but 
is not equivalent to $\forall x \exists y \exists z Q(x,y,z)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%modified from last semester (Lewis Carrol type)
%Problem 6

\problem   
Define predicates and state the following arguments as
predicate logic formulas. Prove the correct arguments 
 and show the incorrect ones are false.

\begin{problemparts}
\problempart No lemons are fierce; some dragons are not fierce.  Thus,
some dragons are not lemons.
\problempart Gold is heavy; nothing but gold will silence him.  Thus,
nothing light will silence him.
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7
%Problem in the Superman spirit
\problem 
Cast the following into propositional symbols and answer the question.

\begin{it}
Careless and weak people are not Wizards. People who are not careless are 
cautious.  Cautious people don't eat mushrooms. Weak people are not powerful.
Hobbits are not powerful and eat mushrooms. Gandalf is a Wizard.  Can Gandalf
be a Hobbit?
\end{it}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Modified from last semester
%Problem 8
%In the spirit of 3.1-3
\problem 
Prove that a positive integer $n$ is a perfect square if and only if 
there are an odd number of positive integers (not necessarily just primes)
that divide $n$.  For example, there is one positive integer that divides 1.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem 
Prove by contradiction: the square root of an irrational number 
is irrational.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 10
%by Santosh
\problem
You have a set of 5 identical-looking balls, and you are told that there
are only two possible values for the weight of each ball. 
You are allowed to compare the weights of (any) two balls (but only
two at a time). There are two possible outcomes of a comparison:
``equal'' or ``not equal'' ({\em not} which ball is heavier). 
Can you find a ball with the same weight as the majority of the  
balls in three comparisons?  
(For example if all five balls have the same weigh, then any ball will do).



\end{problems}
\end{document}
% Local Variables: 
% mode: latex
% TeX-master: t
% End: 
% LocalWords:  Carrol
