\part{Fundamentals}


\chapter{Predicate logic}


The foundation of all mathematics is logic. We commence our study by considering propositions; statements that are either true or false.

Understanding propositional logic will give us an idea of the basic building blocks and concepts of logic that are found in higher order logics and often in other logical systems. 


Logic is the most fundamental part of mathematics, so it is defined in terms of a natural language (i.e English). We say that English is our \emph{metalanguage} and logic is our \emph{object language}.



Later in this book, we will construct propositional logic (and other logics!) in a more rigorous fashion (although still in a metalanguage). This will allow us to say more about our logical systems, but for now our goal is to understand the the basics of logic for the requirements of a discrete mathematics course.


Statement


\section{Terms}
\subsection{Variables}

\begin{definition}[Propositional variable]
A \emph{propositional variable} is a symbol representing some free variable that takes a single truth value (either the top or the bottom). It is a type of \emph{atomic formula}; a propositional formula irreducible to constituent parts (more on this later).
They are often represented by minuscule letters $p,q,\hdot$
\end{definition}

%\subsection{Function}
\section{Logical connectives and truth tables}


\subsection{Nullary connectives (Truth values)}
Value that relates a proposition to its truth.
\begin{definition}[Top]
The \emph{top} or \emph{verum} is the symbol $\top$ repesenting truth.
\end{definition}

\begin{definition}[Bottom]
The \emph{bottom} or \emph{falsum} is the symbol $\bot$ repesenting nontruth.
\end{definition}

\subsection{Unary connectives}
\begin{definition}[Negation (NOT)]
\[\neg P \]
\end{definition}

\subsection{Binary connectives}
\begin{definition}[Conjunction (AND)]
\[P \land Q\]
\end{definition}

\begin{definition}[Disjunction (OR)]
\[P \lor Q\]
\end{definition}

\begin{definition}[Conditional (IMPLY)]
\[P \implies Q \]
\end{definition}

\begin{definition}[Biconditional (IFF)]
\[P \iff Q \]
\end{definition}



\section{Tautologies and contradictions}














\chapter{First order logic}

In propositional logic, the most basic constituents were propositional variables, however what if we consider predicates? Predicates are functions that map objects to truth variables. Such a logic is called \emph{first order logic}, and we'll introduce some more logical symbols to discuss what statements are possible with predicates.




\section{Equality}

\section{Quantifiers}


\subsection{Universal quantifier}
\begin{definition}[Universal quantifier (FORALL)]
\[\forall x \]
\end{definition}

\subsection{Existential quantifier}
\begin{definition}[Existential quantifier (EXISTS)]
\[\exists x \]
\end{definition}

\[\exists! x \]

\subsection{De Morgan's laws for quantifiers}







\chapter{Proof techniques}

It is a useful skill for a mathematician to leverage knowledge of logic to create proofs. 

Indeed, the key to creating proofs for various theorems is to find a suitable proof method.

\section{Direct proof}
\section{Proof by contraposition}
\section{Proof by contradiction}
\section{Proof by mathematical induction}
\section{Combinatorial proof}



\section{Proof by construction}



\chapter{Metalinguistics}

