\documentstyle[fleqn,fullpage]{article}
\newcommand{\imply}{\rightarrow}
\newcommand{\dimply}{\leftrightarrow}
\newcommand{\lequiv}{\Leftrightarrow}
\newcommand{\Sum}{\sum}
\newcommand{\exist}{\exists}
\begin{document}
\begin{center}
CSE 20, Discrete Mathematics, Winter 1995\\
Section 1, 1 PM, First Practice Midterm
\end{center}

\begin{enumerate}

\item
In ``The Prince'', Machiavelli gives an argument that
it is better for a prince to be feared than to be loved.
He starts with the following premises (parenthetical comments
are just to make the story coherrent, and have no logical 
content):
\begin{itemize}
\item
If the prince is to rule, he must be loved or feared.
\item
For the prince to be loved, it is necessary for him to give his
supporters favors.
\item
If the times are troubled, he cannot give his supporters
favors (because his treasury will be emptied by war, plague, or
whatever else is causing the troubles.)
\end{itemize}
From these premises, he concludes that if the times are
troubled, and the prince is to rule, then he must be feared.
Show that, (while Machiavelli's morals are questionable), his
logic is sound, by formalizing the above premises and
conclusion, and giving a proof that the conclusion follows
from the premises.

Answer:  First, note that the construction "for p, q must be
true" is equivalent to "q is a necessary condition for p"
or $p \imply q$. Although $p$ does not cause $q$, and in
general, you could say that $q$ to some extent causes $q$,
if we know $p$, then we can deduce $q$,
Thus, if we let $r \lequiv $"The prince rules", $l \lequiv$
"The prince is loved", $f \lequiv $ "The prince is feared".
$t \lequiv $ "The times are troubled". and $s \lequiv $ "The
prince gives his supporters favors", the premises translate
to:
\begin{itemize}
\item
$r \imply (l \lor f)$
\item
$l \imply s$
\item
$t \imply \lnot s$
\end{itemize}
and the conclusion is $(t \land r) \imply f$.  Since
our goal is of the form something implies something,
we assume the hypothesis and try to prove the conclusion.
\begin{enumerate}
\item
$r \imply (l \lor f)$ (premise)
\item
$l \imply s$(premise)
\item
$t \imply \lnot s$ (premise)
\item
Assume $t \land r$  (assumption, our goal is now to prove $f$)
\item
$t$ (4, Conj. Simp.)
\item 
$\lnot s$ (3,4, Modus Ponens)
\item
$\lnot l$ (2,5 Modus Tollens)
\item $r$ (4, Conj. Simp.)
\item $ l \lor f $(1, 7, Modus Ponens)
\item $f$ (6,8, Disj. Simp.)
\item Therefore, $(t \land r) \imply f$ (Assumption 4 implies
conclusion 9)
\end{enumerate}


Let $A,B,C$ be sets from a common universe.
Prove that if $\lnot (A \subseteq B)$ and $A \subseteq C$,
then $\lnot (C \subseteq B)$.

Answer:  Discussion:  First our goal is to prove
$\lnot (C \subseteq B)$.  This is equvalent to: 
$ \lnot \forall x (x \in C \imply x \in B) \lequiv \exist x [ \lnot (x \in C \imply
x \in B)] \lequiv \exist x [ x \in C \land x \notin B]$,
so our goal is to find some $x$ that is in $C$ but not in $B$.
Then we can finish the proof by first using "existence by
example", and then going backwards through the above
equivalences.  We are given $\lnot (A \subseteq B) \lequiv
\exist x (x \in A \land x \notin B)$, so we will use this to
find our $x$, using choice to get an $x$ in $A$ but not in
$B$.  We then need to prove that $x \in C$, so we use the
other premise $A \subseteq C$.
\begin{enumerate}
\item
Assume $\lnot(A \subseteq B)$, and $A \subseteq C$.
(assumption, goal is to prove $\lnot (C \subseteq B)$.)
\item
$\lnot (\forall x (x \in A \imply x \in B))$. (1, definition of
subset)
\item $(\exist x (\lnot (x \in A \imply x \in B)))$ (2, negation
rule for quantifiers)
\item $\exist x (x \in A \land x \notin B)$ (3, negation rule
for implication)
\item Pick $x_0$ so that $x_0 \in A \land x_0 \notin B$ (4,
rule of choice)
\item $\forall x (x \in A \imply x \in C) $(1, definition of
subset)
\item $x_0 \in A \imply x_0 \in C$ (6, Universal spec.,
$x=x_0$)
\item $x_0 \in C$ (5,7, Modus ponens)
\item $x_0 \in C \land x_0 \notin B$ (5,8)
\item $\exist x [x \in C \land x \notin B]$ (9, exist. by
example)
\item $\exist x [ \lnot (x \in C \imply x \in B)]$(10.
negation rule for implication)
\item $\lnot \forall x [x \in C \imply x \in B]$ (11, negation
rule for quantifiers)
\item $\lnot(C \subseteq B)$ (12, definition of subset)
\item Therefore, if $\lnot (A \subseteq B) \land A \subseteq
C$, then $ \lnot (C \subseteq B)$ (Assumption 1 implies concl.
13)
\end {enumerate}

\item 
A combinatorial optimization problem associates with
each possible ``solution'' $S$ a numerical ``value''
$v(S)$.  A solution $S$ is {\em optimal} if there is no solution
$S'$
with a strictly higher value.  Formalize this definition
using quantifiers (with the universe taken to be the set
of possible solutions), and then formalize and prove that
for any two solutions, if both are optimal, then they have
the same value.  
\end{enumerate}

\noindent
Answer: The first sentence does not need to be formalized,
all it does is tell you what types of objects the variables
and expressions represent:  $S$, etc., are "solutions" 
whereas  $S$'s "value",$v(S)$ is a number, 
and so can be added, compared etc, using normal algebra.
The definition is of a predicate that takes one object of
type "solution" as input.  Thus, the translation should
start $opt(S) \lequiv ...$  Note that, as I said in class,
when giving a definition, it is the convention to frequently
drop the "only if", but it should be understood. Since what
we are defining is a function of $S$, $S$ should be thought
of as a particular solution, and we are defining what it
means for $S$ to be optimal.  Thus, $S$ will be "free" in
the definition, meaning not involved in any quantifier, as
opposed to the other variables, which should all be "bound"
(quantified over exactly once).  The form of the definition
is "there is no S' so that.."  which should be translated
$\lnot \exist S' $something.  The something is that $S'$
has a strictly larger value than $S$, or $v(S') > v(S)$.
Putting it together we get $opt (S) \lequiv \lnot (\exist S'
[ v(S') > v(S)])$.  Note that $S'$ is bound, but $S$ is free.
Our goal is to prove: $\forall S, S' [opt(S) \land opt(S')
\imply (v(S)=v(S'))]$.
Since our goal is a universal rule, we will need to use
universal generalization as the last step.  Thus, in
the first step we pick two arbitrary solutions $S_0$ and
$S_1$.  We then need to show $opt(S_0) \land opt(S_1) \imply
(v(S_0)=v(S_1))$, so as the second step we assume the
former and try to prove that $v(S_0)=v(S_1)$.  What
we have to work with is that both $S_0$ and $S_1$ satisfy
the defintion of optimal.

\begin{enumerate}
\item
Let $S_0$ and $S_1$ be arbitrary solutions. 
\item
Assume $opt(S_0)$ and $opt(S_1)$. (assumption)
\item
$\lnot (\exist S' [ v(S') > v(S_0)])$ (2, definition of opt)
\item 
$\forall S' [ v(S') \le v(S_0)] $ (3, negation rule for
quantifiers)
\item
$v(S_1) \leq v(S_0)$ (4, Univ. Spec., $S'=S_1$)
\item
$\lnot (\exist S' [ v(S') > v(S_1)])$ (2, definition of opt)
\item 
$\forall S' [ v(S') \le v(S_1)] $ (6, negation rule for
quantifiers)
\item
$v(S_0) \le v(S_1)$ (7, Univ. Spec., $S'=S_0$)
\item
$v(S_0)=v(S_1)$ (5,8, Algebra)
\item
Therefore $(opt(S_0) \land opt(S_1)) \imply
v(S_0)=v(S_1)$(assumption 2 implies conclusion 9)
\item
Since $S_0,S_1$ were arbitrary, $\forall S, S' [(opt(S)
\land opt(S')) \imply (v(S)=v(S'))]$ (1,10, univ.
generalization)
\end{enumerate}


\end{document}