%correction Prob4(c)
\documentstyle[12pt,twoside]{article}
\input{macros-course}

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

\pset{1}{February 2, 1998}{In lecture, Tuesday, February 10}

\reading 
Sections 1.1--1.5, 2.3, and 3.1 of Rosen.  Notes for Lecture 1 and
Recitation 1.  Start {\em The Nuts and Bolts of Proofs\/} aiming to
finish before the third week of class.

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 1: variant of F97

\problem\hfill

\bparts

\ppart

The {\em symmetric difference}, $A \oplus B$, of two sets, $A$
and~$B$, is defined by
\[A \oplus B = (A \cup B)-(A \cap B).\]

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

\ppart Prove that $\oplus$ is associative.

\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 2: variant of F97

\problem 
Show that each of the following implications is a tautology by using truth 
tables.

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

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 3  variant of F97

\problem Find a compound proposition involving the propositions $p$, $q$,
and $r$ that is true exactly when {\em both}\\
(i) at least one of the propositions is true, {\em and also}\\
(ii) at least one of the propositions is false.\\
The compound proposition is false otherwise.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 4  variant of F97
% 1.3 # 8 modified
\problem 

Let $W(x,y)$ be the statement ``$x$ was one of the writers of $y$,''
and $S(x)$ be the statement ``$x$ is a professional screenwriter,''
where the universe of the discourse for $x$ is the set of all people
and for $y$ is the set of all movies.  Express each of the following
sentences in terms of $W(x,y), S(x)$, quantifiers, and logical
connectives,

\begin{description}
\item[a)] Someone who helped write ``Titanic'' was not a professional screenwriter.
\item[b)] Every movie had a writer who was a professional screenwriter.
%typo corrected: inserted ``professional'':
\item[c)] There is a professional screenwriter who has written ``Pulp Fiction'' and
``Jackie Brown.''
\item[d)] There is only one movie which had exactly one writer who was not a professional screenwriter. (Don't introduce numbers.  You will have to add more
standard variables ranging over people and over movies).

\end{description}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 1.3 - 26
%Problem 5: from F96 pset1 prob 6
\problem

Show that $\forall x P(x) \vee \forall x Q(x)$ and $\forall x (P(x) 
\vee Q(x))$ are not logically equivalent. 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
%Problem 6 variant of F97

\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 Fairies are never fierce; some dragons are not fierce.  Thus,
some dragons are not fairies.

\problempart Gold is a liquid asset, and he will be satisfied only with
gold.  Thus, no fixed asset will satisfy him.
\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 7 unchanged form F97

\problem 
Cast the following into propositional symbols, and explain whether
Gandalf can be a Hobbit.

\begin{quote}
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.
\end{quote}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 8

\problem \hfill

\bparts

\ppart

Prove by contradiction: for all integers $n > 1$, the $n$th root of a
prime number is irrational.

\ppart Your proof must depend on some property of prime numbers not shared
by all integers greater than one.  Why?  What property?

\eparts


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Problem 9
\problem
Prove by cases: for every $n \in \naturals$, either $4 | n^2$ or $4 |
(n^2-1)$.


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