Notes and Questions

Well-Ordering Principle Proof

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)$