\chapterimage{shadocklogic}

\chapter{Logique des propositions}
\Pasc

\section{Généralités}

On appellera \textbf{proposition} tout  énoncé dont on peut décider s'il
est vrai ou faux indépendamment de ses composantes.

On  distinguera   la  logique  des   propositions  de  la   logique  des
\textbf{prédicats} qui  introduit des variables dans  les assertions qui
peut  les rendre  donc parfois  vraies et  parfois fausses  et  que nous
étudierons en deuxième année.


Par exemple \og \textit{Igor dort}\fg{} est une proposition susceptible d'être
vraie ou  fausse dans toute situation  alors que la valeur  de vérité de
\og \textit{x dort}\fg{} dépend de $x$.

Nous  distinguerons  également la  \textbf{syntaxe}  de  la logique  des
propositions de sa \textsc{sémantique}.

Le dictionnaire propose les définitions suivantes: 

\begin{itemize}
\item \textbf{syntaxe}:
n.  f. (bas  latin  syntaxis, du  grec  suntaksis, ordre)  Partie de  la
grammaire qui décrit les  règles par lesquelles les unités linguistiques
se combinent en phrases. 

\item \textbf{sémantique}:
n. f. (bas latin semanticus, du grec sêmantikos, qui signifie)
\textbf{1.} Étude du sens des unités linguistiques et de leurs combinaisons.
\textbf{2.} Étude  des propositions d'une théorie déductive  du point de
vue de leur vérité ou de leur fausseté. 

\end{itemize}
  

L'étude  de  l'aspect  syntaxique   consiste  à  préciser  comment  l'on
construit les formules et l'aspect sémantique interprète les formules en
terme de \textit{Vrai} ou \textit{Faux}.

\section{Syntaxe}

\subsection{Les symboles}

L'alphabet du langage de la logique des propositions est constitué de:

\begin{itemize}
\item  un  ensemble  fini  ou infini  dénombrable  de  \textit{variables
    propositionnelles};
\item la constante logique $\bot$ qui se lit \og FAUX\fg{};
\item les \textit{connecteurs} $\lnot$ (non), $\land$ (et), $\lor$ (ou),
  $\rightarrow$ (implique) et $\leftrightarrow$ (équivalent);
\item les parenthèses \og (\fg{} et \og )\fg{}.

\end{itemize}
 

Le connecteur  $\lnot$ est un  \textit{connecteur unaire} et  les autres
sont des \textit{ connecteurs binaires}.

L'\textit{ensemble des  formules} de la logique  propositionnelle est le
plus petit ensemble $\CR F$ tel que:

\begin{itemize}
\item toute variable propositionnelle est un élément de $\FR$;
\item $\bot$ est un élément de $\FR$;
\item si $p\in \FR$, alors $(\lnot p)\in \FR$;
\item si $p$ et $q$ sont  dans $\FR$, alors $(p\land q)$, $(p\lor q)$,
  $(p \rightarrow q)$,  et $(p \leftrightarrow q)$ sont  des éléments de
  $\FR$.
\end{itemize}

Par exemple, $s\rightarrow ((p\lor (\lnot q))\lor(p\lor (\lnot r)))$ est une
proposition mais $\lnot \land(p)\lor$ ne l'est pas.

On  peut se passer  de quelques  parenthèses en  adoptant les  règles de
priorité suivantes:

\begin{itemize}
\item $\lnot$ est prioritaire sur les autres opérateurs;
\item  $\lor$   et  $\land$  sont  prioritaires   sur  $\rightarrow$  et
  $\leftrightarrow$.
\end{itemize}

Mais attention! $p\lor q\land r$ est ambigu.


\subsection{Démonstration par induction}


\begin{theoreme}
  Si une propriété P portant sur les formules de $\FR$ est telle que:

  \begin{itemize}
  \item toute variable propositionnelle vérifie P;
\item $\bot$ vérifie P;
\item si la formule $p$ vérifie P, alors $(\lnot p)$ vérifie P;
\item  si $p$  et  $q$ vérifient  P,  alors $(p\lor  q)$, $(p\land  q)$,
  $(p\rightarrow q)$ et $(p \leftrightarrow q)$ vérifient P;
  \end{itemize}

alors toutes les formules de $\FR$ vérifient P.
\end{theoreme}


Ce théorème permet par exemple de prouver le théorème suivant:

\begin{theoreme}
Toute  formule  de  $\FR$  a  autant de  parenthèses  ouvrantes  que  de
parenthèses fermantes.
\end{theoreme}

La preuve est laissée en exercice.

\subsection{Sous-formules}

Nous n'entrerons pas dans les détails mais on peut définir par induction
les sous-formules d'une formule  donnée: on retiendra juste qu'il s'agit
de toutes les formules apparaissant dans une formule donnée.

Par exemple, l'ensemble des sous-formules de $(p\rightarrow q)\lor
\lnot(q\leftrightarrow r)$ est $$\bigl\{p\rightarrow q,
\lnot(q\leftrightarrow r),q\leftrightarrow r,p,q,r\bigr\}$$


\section{Sémantique}


\subsection{Valeurs et tables de vérité}


On considère  un ensemble $\BR=\bigl\{0,1\bigr\}$  ou $\bigl\{F,V\bigr\}$ ou
$\bigl\{{\rm Oui},{\rm Non}\bigr\}$, etc.


\begin{definition}
Une \textit{distribution des valeurs  de vérité} est une application $v$
de $\FR$ dans $\BR$ définie inductivement par:

\begin{itemize}
\item $v(\bot)=0$,
\item $v(\lnot p)=1$ si, et seulement si, $v(p)=0$;
\item $v(p\land q)=1$ si, et seulement si, $(p)=v(q)=1$;
\item $v(p\lor q)=0$ si, et seulement si, $v(p)=v(q)=0$;
\item $v(p \rightarrow q)=0$ si, et seulement si, $v(p)=1$ et $v(q)=0$;
\item $v(p\leftrightarrow)=1$ si, et seulement si, $v(p)=v(q)$,
\end{itemize}

avec $p$ et $q$ des éléments quelconques de $\FR$.
\end{definition}


Cette  définition   permet  d'établir  les   \textit{tables  de  vérité}
suivantes:

puis de généraliser à n'importe quelle formule:


\subsection{Calcul propositionnel et Calcul dans $\mathbf{F_2}$}

On  muni   $\bigl\{0,1\bigr\}$  des  opérations  $+$   et  $\cdot$.   On
n'oubliera pas que dans $\bbf_2$, $x+x=0$ et $x^2=x$.


On peut alors définir une  distribution des valeurs de vérité cette fois
à valeurs dans $\bbf_2$:

\begin{itemize}
\item $v(\bot)=0$;
\item $v(p)=x\in \bigl\{0,1\bigr\}$; $v(q)=y\in \bigl\{0,1\bigr\}$
\item $ v(\lnot p)=1+x$;
\item $v(a\lor q)=x+y+x\cdot y$;
\item $v(p\land q)=x\cdot y$;
\item $v(p\rightarrow q)=1+x+x\cdot y$;
\item $v(p \leftrightarrow q)=1+x+y$.
\end{itemize}




%%% Local Variables: 
%%% TeX-master: "PolyInfo10"
%%% End: 
