95 lines
3.4 KiB
TeX
95 lines
3.4 KiB
TeX
\documentclass[../../script.tex]{subfiles}
|
|
|
|
% !TEX root = ../../script.tex
|
|
|
|
\begin{document}
|
|
\section{Logic}
|
|
\begin{defi}[Statements]
|
|
A statement is a sentence (mathematical or colloquial) which can be either true or false.
|
|
\end{defi}
|
|
|
|
\begin{eg}
|
|
Statements are
|
|
\begin{itemize}
|
|
\item Tomorrow is Monday
|
|
\item $x > 1$ where $x$ is a natural number
|
|
\item Green rabbits grow at full moon
|
|
\end{itemize}
|
|
No statements are
|
|
\begin{itemize}
|
|
\item What is a statement?
|
|
\item $x + 20y$ where $x, y$ are natural numbers
|
|
\item This sentence is false
|
|
\end{itemize}
|
|
\end{eg}
|
|
|
|
\begin{defi}[Connectives]
|
|
When $\Phi, \Psi$ are statements, then
|
|
\begin{enumerate}[(i)]
|
|
\item $\neg\Phi$ (not $\Phi$)
|
|
\item $\Phi \wedge \Psi$ ($\Phi$ and $\Psi$)
|
|
\item $\Phi \vee \Psi$ ($\Phi$ or $\Psi$)
|
|
\item $\Phi \implies \Psi$ (if $\Phi$ then $\Psi$)
|
|
\item $\Phi \iff \Psi$ ($\Phi$ if and only if (iff.) $\Psi$)
|
|
\end{enumerate}
|
|
are also statements. We can represent connectives with truth tables
|
|
\begin{center}
|
|
\begin{tabular}{ c|c||c|c|c|c|c }
|
|
$\Phi$ & $\Psi$ & $\neg\Phi$ & $\Phi \wedge \Psi$ & $\Phi \vee \Psi$ & $\Phi \implies \Psi$ & $\Phi \iff \Psi$ \\
|
|
\hline
|
|
t & t & f & t & t & t & t\\
|
|
t & f & f & f & t & f & f\\
|
|
f & t & t & f & t & t & f\\
|
|
f & f & t & f & f & t & t\\
|
|
\end{tabular}
|
|
\end{center}
|
|
\end{defi}
|
|
|
|
\begin{rem}\leavevmode
|
|
\begin{enumerate}[(i)]
|
|
\item $\vee$ is inclusive
|
|
\item $\Phi \implies \Psi$, $\Phi \impliedby \Psi$, $\Phi \iff \Psi$ are NOT the same
|
|
\item $\Phi \implies \Psi$ is always true if $\Phi$ is false (ex falso quodlibet)
|
|
\end{enumerate}
|
|
\end{rem}
|
|
|
|
\begin{defi}[Hierarchy of logical operators]
|
|
$\neg$ binds stronger than $\wedge$ and $\vee$, which bind stronger than $\implies$ and $\iff$.
|
|
\end{defi}
|
|
|
|
\begin{eg}\leavevmode
|
|
\begin{align*}
|
|
\neg\Phi \wedge \Psi ~&\cong~ (\neg\Phi) \wedge \Psi \\
|
|
\neg\Phi \implies \Psi ~&\cong~ (\neg\Phi) \wedge \Psi \\
|
|
\Phi \wedge \Psi \iff \Psi ~&\cong~ (\Phi \wedge \Psi) \iff \Psi \\
|
|
\neg\Phi \vee \neg\Psi \implies \neg\Psi \wedge \Psi ~&\cong~ ((\neg\Phi) \vee (\neg\Psi)) \implies ((\neg\Psi) \wedge \Psi)
|
|
\end{align*}
|
|
We avoid writing statements like $\Phi \wedge \Psi \vee \Theta$. A statement that is always true is called a tautology. Some important equivalencies are
|
|
\begin{align*}
|
|
\Phi ~&\text{equiv.}~ \neg(\neg\Phi)) \\
|
|
\Phi \implies \Psi ~&\text{equiv.}~ \neg\Psi \implies \neg\Phi \\
|
|
\Phi \iff \Psi ~&\text{equiv.}~ (\Phi \implies \Psi) \wedge (\Psi \implies \Phi) \\
|
|
\Phi \vee \Psi ~&\text{equiv.}~ \neg(\neg\Phi \wedge \neg\Psi)
|
|
\end{align*}
|
|
Logical operators are commutative, associative and distributive.
|
|
\end{eg}
|
|
|
|
\begin{defi}[Quantifiers]
|
|
Let $\Phi(x)$ be a statement depending on $x$. Then $\forall x ~\Phi(x)$ and $\exists x ~\Phi(x)$ are also statements. The interpretation of these statements is
|
|
\begin{itemize}
|
|
\item $\forall x ~\Phi(x)$: "For all $x$, $\Phi(x)$ holds."
|
|
\item $\exists x ~\Phi(x)$: "There is (at least one) $x$ s.t. $\Phi(x)$ holds."
|
|
\end{itemize}
|
|
\end{defi}
|
|
|
|
\begin{rem}\leavevmode
|
|
\begin{enumerate}[(i)]
|
|
\item $\forall x ~x \ge 1$ is true for natural numbers, but not for integers. We must specify a domain.
|
|
\item If the domain is infinite the truth value of $\forall x ~\Phi(x)$ cannot be algorithmically determined.
|
|
\item $\forall x ~\Phi(x)$ and $\forall y ~\Phi(y)$ are equivalent.
|
|
\item Same operators can be exchanged, different ones cannot.
|
|
\item $\forall x ~\Phi(x)$ is equivalent to $\neg(\exists x ~\neg\Phi(x))$.
|
|
\end{enumerate}
|
|
\end{rem}
|
|
|
|
\end{document} |