\documentclass{article}

\usepackage{francais,t1enc}
\usepackage[all]{xy}
\usepackage{latexsym}

\renewcommand{\S}{\textbf{S}}
\newcommand{\N}{\texttt{\small |}\!\textsf{N}}
\newcommand{\vDash}{\mathop{|\!\!\!=}}
\newcommand{\Y}{\mathbf{Y}}
\newcommand{\K}{\mathbf{K}}
\renewcommand{\S}{\mathbf{S}}
\newcommand{\I}{\mathbf{I}}
\newcommand{\T}{\mathbf{T}}
\newcommand{\F}{\mathbf{F}}
\newcommand{\ou}{\ensuremath{\mathbf{ou}\ }}
\newcommand{\non}{\ensuremath{\mathbf{non}}}

\input{/home/plescann/ARTICLES/macros_lambda.tex}

\begin{document}
\title{Magistère d'Informatique et Modélisation}
\author{\textsf{Exercices de $\lambda$-calcul}}

\date{Novembre -- décembre 2001}

\maketitle 

\section*{Exercice 3}
On définit les deux termes $\T$ pour <<vrai>> et $\F$ pour <<faux>>. $\T$
est $\K$ et $\F$ est la forme normale de $\K\I$.
\begin{enumerate}
\item Quelle est  la forme normale de $\K\I$?
\item Si $M$ et $N$ sont des formes normales, quelles sont les formes
  normales de $\T M N$ et $\F M N$ ?
\item Quel terme représenterait le connecteur \non?  C'est-à-dire un
  terme tel que 
\begin{center}
\begin{math}
\begin{array}{ll}
\non~\T \rara \F & \non~\F \rara \T
\end{array} 
\end{math}
\end{center}

\item On suppose que $\T$ et $\F$ représentent les booléens.  Quel
  terme représenterait le connecteur \ou?   C'est-à-dire un
  terme tel que 
\begin{center}
\begin{math}
\begin{array}{ll}
\ou \T \T \rara \T & \ou \T \F \rara \T\\
\ou \F \T \rara \T & \ou \F \F \rara \F
\end{array}
\end{math}
\end{center}

\item Étant donnés deux termes $M$ et $N$ en formes normales, on
  définit le terme $P_{M,N} = \lambda z . z MN$.  Quelle est la forme
  normale de $(\lambda p. p \T) P_{M,N}$ et de $(\lambda p. p \F)
  P_{M,N}$?
\item Donnez un terme $Q$  tel que $Q P_{L, P_{M,N}} \rara N$.
\end{enumerate}
\end{document}
