Odd Summation. (Problem 2.12) Prove that for all $n > 0$, the sum of the first $n$ odd numbers is $n^2$.

#
#
## Notations
Mathematics and other domains often use many symbols to mean the same
thing. Section 3.2 of the book gives some common notations, but there
are others in common use.
\begin{center}
\begin{tabular}{cccc}
English & Logic & C, Java, Rust & Python \\ \hline
$P$ \smallcaps{implies} $Q$ & $P \implies Q$ {\em or} $P \longrightarrow Q$ & - & - \\
\smallcaps{not}$(P)$ & $\neg P$ {\em or} $\overline{P}$ & \verb+!p+ & \verb+not p+ \\
$P$ \smallcaps{and} $Q$ & $P \wedge Q$ & \verb+p && q+ & \verb+p and q+ \\
$P$ \smallcaps{or} $Q$ & $P \vee Q$ & \verb+P || Q+ & \verb+p or q+ \\
$P$ \smallcaps{xor} $Q$ & $P \oplus Q$ & \verb+p ^ q+ (bitwise) or \verb+p != q+ & \verb+p ^ q+ \\
\end{tabular}
\end{center}
For what values in Java or C are \verb+p ^ q+ and \verb+p != q+ both valid, but have different meanings?
## Logical Formulas
\begin{center}
\begin{tabular}{c|c|c}
$P$ & \smallcaps{not}$(P)$ & \_\_\_\_\_\_\_\_ \\ \hline
\T & \F & \\
\F & \T & \\
\end{tabular}
\end{center}
How many one-input Boolean operators are there? How many do we need to
produce them all?
#
\begin{center}
\begin{tabular}{cc|c|c|c|c|c}
$P$ & $Q$ & $P \wedge Q$ & $P \vee Q$ & $P \implies Q$ & \_\_\_\_\_\_\_\_ & $P \oplus Q$ \\ \hline
\T & \T & \T & \T & & \T & \F \\
\T & \F & & \T & & \F & \T \\
\F & \T & & \T & & \F & \T \\
\F & \F & & \F & & \T & \F \\
\end{tabular}
\end{center}
How many two-input Boolean operators are there?
#
**De Morgan's Laws:**
$$\neg(P \wedge Q) \equiv (\neg P) \vee (\neg Q) \qquad \neg(P \vee Q) \equiv (\neg P) \wedge (\neg Q)$$
How can these be written without the $\neg$ in front?
##
Prove that it is possible to make all two-input Boolean operators using
just \smallcaps{not} and any _odd_ two-input operator. (An operator is _odd_,
if the number of outputs that are **True** are odd.)
##
**Definition: valid.** A logical formula is _valid_ if there is no way
to make it **false**. That is, no matter what truth values its
variables have, it is always **true**. (Another name for this is a
_tautology_.)
**Definition: satisfiable.** A logical formula is _satisfiable_ if there
is _some_ way to make it **true**. That is, there is at least one
assignment of truth value to its variables that makes the forumla
true.
For each of the formulas below, determine if it is _valid_ and if it is _satisfiable_.
1. $(P \vee \neg P)$
2. $(P \vee Q) \wedge (\neg P \vee Q)$
3. $((P \implies Q) \wedge (Q \implies P)) \vee (P \xor Q)$