\documentclass[12pt]{article}
\usepackage[Mickael]{ammaths}

\begin{document}

\module{Formal equivalences}{2}{04}{1 period}

\prereq{\begin{itemize}
        \item Truth tables.
	\item Logical operators $\neg$, $\wedge$, $\vee$, $\rightarrow$, $\leftrightarrow$.
	\item Notion of formal equivalence.
	\end{itemize}}

\object{\begin{itemize}
        \item Build some complex truth tables.
	\item Compare truth tables and find formal equivalences.
	\end{itemize}}

\mater{\begin{itemize}
	\item Fact sheet with a few logical transformation rules.
	\item Nine pairs of formally equivalent propositions involving three propositions $p$, $q$, $r$.
	\item Complete truth tables of each proposition.
	\item Beamer with a few logical transformation rules.
	\end{itemize}}

\modpart{Build a truth table}{15 mins}

Students work in pairs. Each pair is given a logical proposition and has to build its truth table. The teacher checks
each truh table before proceeding to the second part.

\modpart{Find formal equivalences}{10 mins}

Students mingle (still working by pairs) to find a proposition formally equivalent to the one they have.

\modpart{Formal derivation}{20 mins}

The teacher gives a few logical transformation rules, with a few examples. Then students, working in teams of four, have
to use them to transform one of their two propositions into the other.

\modpart{Challenge}{10 mins}

Students have to reduce the following property so that there are brackets and no conditional. 
To prove that their result is good, they have to build the truth tables of the two propositions.
$$\neg\left((p\wedge \neg r)\vee (\neg p\vee r)\right)\longrightarrow \neg\left(p\wedge (\neg q\vee r)\right)$$


\pagebreak

\moddocdis{Formal equivalences : a few rules}{2}{04}{Lesson}
\en\nocouleur

\section*{De Morgan's laws}

\newcounter{chap}
\setcounter{chap}{03}

\theo{}{$$\neg(p\wedge q) \Longleftrightarrow (\neg p\vee\neg q) \textrm{ and }\neg(p\vee q) \Longleftrightarrow(\neg
p\wedge\neg q)$$}


\proo{Let's look at the truth table of each proposition.
\begin{center}
\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $p\wedge q$ & $\neg(p\wedge q)$ & $\neg p$ & $\neg q$ & $\neg p\vee\neg q$ \\
\hline
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 \\
\end{tabular}
\end{center}
As $\neg(p\wedge q)$ and $\neg p\vee\neg q$ have the same truth table, they are formally equivalent.\\
\begin{center}
\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $p\vee q$ & $\neg(p\vee q)$ & $\neg p$ & $\neg q$ & $\neg p\wedge\neg q$ \\
\hline
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 \\
\end{tabular}
\end{center}
As $\neg(p\vee q)$ and $\neg p\wedge\neg q$ have the same truth table, they are formally equivalent.}

\section*{Conditional and biconditional}

\theo{}{$$(p\rightarrow q)\Longleftrightarrow (\neg q\rightarrow\neg p)\Longleftrightarrow(\neg p\vee q)$$}

\proo{The first formal equivalence has been proven in the previous session, so we just have to look at the truth tables of $p\rightarrow q$ and $\neg p\vee q$.\begin{center}
\begin{tabular}{c|c|c|c|c}
$p$ & $q$ & $p\rightarrow q$ & $\neg p$ & $\neg p\vee q$ \\
\hline
0 & 0 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 \\
\end{tabular}
\end{center}
As $p\rightarrow q$ and $\neg p\vee q$ have the same truth table, they are formally equivalent.
}

\pagebreak

\theo{}{$$(p\leftrightarrow q)\Longleftrightarrow (\neg q\leftrightarrow\neg p)$$}

\proo{Once again, we just have to look at the truth tables of the two propositions.
\begin{center}
\begin{tabular}{c|c|c|c|c|c}
$p$ & $q$ & $p\leftrightarrow q$ & $\neg p$ & $\neg q$ & $\neg p\leftrightarrow \neg q$ \\
\hline
0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 0\\
1 & 0 & 0 & 0 & 1 & 0\\
1 & 1 & 1 & 0 & 0 & 1\\
\end{tabular}
\end{center}
As $p\leftrightarrow q$ and $\neg p\leftrightarrow \neg q$ have the same truth table, they are formally equivalent.
}

\pagebreak

\moddoc{Pairs of formally equivalent propositions}

{\Huge
\hrulefill

$$(p\wedge q)\rightarrow r$$
\hrulefill

$$\neg r\rightarrow (\neg p\vee\neg q)$$
\hrulefill

$$(\neg p \wedge \neg r)\rightarrow q$$
\hrulefill

$$\neg q\rightarrow (p\vee r)$$
\hrulefill

$$\neg p\rightarrow \neg(q\vee r) $$
\hrulefill

$$\neg(\neg q\wedge\neg r)\rightarrow p$$
\hrulefill

\pagebreak

\hrulefill
$$(\neg p\rightarrow q)\rightarrow \neg r$$
\hrulefill

$$r\rightarrow (\neg p\wedge \neg q)$$
\hrulefill

$$(p\vee q)\rightarrow (p\wedge r)$$
\hrulefill

$$(\neg p\vee\neg r)\rightarrow (\neg q\wedge \neg p)$$
\hrulefill

$$\neg p\leftrightarrow (q\wedge r)$$
\hrulefill

$$(\neg q\vee \neg r)\leftrightarrow p$$
\hrulefill

\pagebreak

\hrulefill
$$(p\rightarrow q)\vee (p\rightarrow \neg r)$$
\hrulefill

$$p\rightarrow (q\vee \neg r)$$
\hrulefill

$$(p\wedge q)\leftrightarrow (\neg p\vee r)$$
\hrulefill

$$(p\wedge \neg r)\leftrightarrow(\neg p\vee\neg q)$$
\hrulefill

$$(\neg p\vee p)\rightarrow (q\wedge r)$$
\hrulefill

$$(\neg q\vee\neg r)\rightarrow (p\wedge \neg p)$$
\hrulefill

}


\pagebreak

\moddoc{Pairs of formally equivalent propositions with complete truth tables}

\fbox{$(p\wedge q)\rightarrow r$} \medskip

\begin{tabular}{c|c|c|c|c}
$p$ & $q$ & $r$ & $p\wedge q$ & $(p\wedge q)\rightarrow r$ \\ \hline
0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 1 \\
0 & 1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 \\
1 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 1 \\
\end{tabular}

\medskip

\fbox{$\neg r\rightarrow (\neg p\vee\neg q)$} \medskip

\begin{tabular}{c|c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$  & $\neg q$ & $\neg r$ & $\neg p\vee\neg q$ & $\neg r\rightarrow (\neg p\vee\neg q)$ \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 0 & 0 & 1 & 1\\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
\end{tabular}

\medskip

\fbox{$(\neg p \wedge \neg r)\rightarrow q$} \medskip

\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $\neg r$ & $\neg p \wedge \neg r$ & $(\neg p \wedge \neg r)\rightarrow q$\\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 & 1  \\
0 & 1 & 0 & 1 & 1 & 1 &  1 \\
0 & 1 & 1 & 1 & 0 & 0 &  1 \\
1 & 0 & 0 & 0 & 1 & 0 & 1  \\
1 & 0 & 1 & 0 & 0 & 0 & 1  \\
1 & 1 & 0 & 0 & 1 & 0 & 1  \\
1 & 1 & 1 & 0 & 0 & 0 & 1  \\
\end{tabular}

\medskip

\fbox{$\neg q\rightarrow (p\vee r)$} \medskip

\begin{tabular}{c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg q$ & $p\vee r$ & $\neg q\rightarrow (p\vee r)$  \\ \hline
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 $\neg p\rightarrow \neg(q\vee r) $& 1 \\
1 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 1 \\
\end{tabular}

\pagebreak

\fbox{$\neg p\rightarrow \neg(q\vee r) $} \medskip

\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $q\vee r$ & $\neg(q\vee r)$ & $\neg p\rightarrow \neg(q\vee r) $ \\ \hline
0 & 0 & 0 & 1 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 \\
1 & 1 & 0 & 0 & 1 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 & 1 \\
\end{tabular}

\medskip

\fbox{$\neg(\neg q\wedge\neg r)\rightarrow p$} \medskip

\begin{tabular}{c|c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg q$ & $\neg r$ & $\neg q\wedge\neg r$ & $\neg(\neg q\wedge\neg r)$ &  $\neg(\neg q\wedge\neg r)\rightarrow p$ \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 \\
1 & 0 & 1 & 1 & 0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 1 & 1 \\
\end{tabular}

\medskip

\fbox{$(\neg p\rightarrow q)\rightarrow \neg r$} \medskip

\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $\neg r$ & $\neg p\rightarrow q$ & $(\neg p\rightarrow q)\rightarrow \neg r$  \\ \hline
0 & 0 & 0 & 1 & 1 & 0 & 1 \\
0 & 0 & 1 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 1 & 0 \\
\end{tabular}

\medskip

\fbox{$r\rightarrow (\neg p\wedge \neg q)$} \medskip

\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $\neg q$ & $\neg p\wedge \neg q$ & $r\rightarrow (\neg p\wedge \neg q)$  \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 0 & 1 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 \\
\end{tabular}

\pagebreak

\fbox{$(p\vee q)\rightarrow (p\wedge r)$} \medskip

\begin{tabular}{c|c|c|c|c|c}
$p$ & $q$ & $r$ & $p\vee q$ &  $p\wedge r$ & $(p\vee q)\rightarrow (p\wedge r)$ \\ \hline
0 & 0 & 0 & 0 & 0 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 1 & 1 & 1 \\
\end{tabular}

\medskip

\fbox{$(\neg p\vee\neg r)\rightarrow (\neg q\wedge \neg p)$} \medskip

\begin{tabular}{c|c|c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $\neg q$ & $\neg r$ & $\neg p\vee\neg r$ & $\neg q\wedge \neg p$ & $(\neg p\vee\neg r)\rightarrow (\neg q\wedge \neg p)$  \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{tabular}

\medskip

\fbox{$\neg p\leftrightarrow (q\wedge r)$} \medskip

\begin{tabular}{c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $q\wedge r$ & $\neg p\leftrightarrow (q\wedge r)$  \\ \hline
0 & 0 & 0 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 & 0 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 \\
\end{tabular}

\medskip

\fbox{$(\neg q\vee \neg r)\leftrightarrow p$} \medskip

\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg q$ & $\neg r$ & $\neg q\vee \neg r$ & $(\neg q\vee \neg r)\leftrightarrow p$ \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 0 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 1 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 \\
\end{tabular}

\pagebreak

\fbox{$(p\rightarrow q)\vee (p\rightarrow \neg r)$} \medskip

\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg r$ & $p\rightarrow q$ & $p\rightarrow \neg r$ & $(p\rightarrow q)\vee (p\rightarrow \neg r)$  \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 1 \\
0 & 0 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 & 1 \\
1 & 0 & 0 & 1 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 0 & 1 \\
\end{tabular}

\medskip

\fbox{$p\rightarrow (q\vee \neg r)$} \medskip

\begin{tabular}{c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg r$ & $q\vee \neg r$ & $p\rightarrow (q\vee \neg r)$  \\ \hline
0 & 0 & 0 & 1 & 1 & 1 \\
0 & 0 & 1 & 0 & 0 & 1 \\
0 & 1 & 0 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 0 \\
1 & 1 & 0 & 1 & 1 & 1 \\
1 & 1 & 1 & 0 & 1 & 1 \\
\end{tabular}

\medskip

\fbox{$(p\wedge q)\leftrightarrow (\neg p\vee r)$} \medskip

\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $p\wedge q$ & $\neg p\vee r$ & $(p\wedge q)\leftrightarrow (\neg p\vee r)$  \\ \hline
0 & 0 & 0 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 1 & 1 \\
\end{tabular}

\medskip

\fbox{$(p\wedge \neg r)\leftrightarrow(\neg p\vee\neg q)$} \medskip

\begin{tabular}{c|c|c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $\neg q$ & $\neg r$ & $p\wedge \neg r$ & $\neg p\vee\neg q$ & $(p\wedge \neg r)\leftrightarrow(\neg p\vee\neg q)$  \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\
1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{tabular}

\pagebreak

\fbox{$(\neg p\vee p)\rightarrow (q\wedge r)$} \medskip

\begin{tabular}{c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $\neg p\vee p$ & $q\wedge r$ & $(\neg p\vee p)\rightarrow (q\wedge r)$  \\ \hline
0 & 0 & 0 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 1 & 1 & 1 \\
1 & 0 & 0 & 0 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 1 & 1 & 1 \\
\end{tabular}

\medskip

\fbox{$(\neg q\vee\neg r)\rightarrow (p\wedge \neg p)$} \medskip

\begin{tabular}{c|c|c|c|c|c|c|c|c}
$p$ & $q$ & $r$ & $\neg p$ & $\neg q$ & $\neg r$ & $\neg q\vee\neg r$ & $p\wedge \neg p$ & $(\neg q\vee\neg r)\rightarrow (p\wedge \neg p)$ \\ \hline
0 & 0 & 0 & 1 & 1 & 1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\
0 & 1 & 0 & 1 & 0 & 1 & 1 & 0 & 0 \\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 \\
1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\
\end{tabular}

\medskip

\end{document}
