Cours.tex

\documentclass[10pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\author{CLAVIER Paul}
\title{[Info 525]Logique}
\begin{document}
%head
\maketitle
\newpage
\tableofcontents
\newpage
%body

%TODO
%A REFAIRE
%\section{Définition}
%\begin{itemize}
%\item Logique vient du grec Logos, qui veut dire à la fois raison et langage.
%\item "Étude du discours rationnel."
%\item "Étude de la raison dans le langage."
%\item "Science des conditions de vérités."
%\end{itemize}
%\subsection{Logique classique $(<1850)$}
%\begin{itemize}
%\item Analyse du langage.
%\item Division de la grammaire: sujet attribut.
%\item Prédominance de la logique Aristotélicienne.
%\item Plusieurs périodes.
%\end{itemize}
%\subsection{Logique moderne, symbolique axiomatique}
%\begin{itemize}
%\item Mathématisation, algébrisation de la logique.
%\item Les relations perdent leur caractère grammatical.
%\item Un système d'axiomes choisis arbitrairement et soumis à des règles de déduction immédiates.
%\item \emph{Forme de pensée et une approche du logos différente.}
%\item Système de réécriture , manipulation des signes sans sens.
%\end{itemize}
%\framebox{Pas de définition unique: fonction de l'époque, du logicien, de l'objectif.}
%\section{De Morgan}
%\begin{itemize}
%\item Définit l'expression de l'induction mathématique.
%\item Auteur des lois de De Morgan
%\end{itemize}
%\section{Boole}
%\section{Frege}
%\begin{itemize}
%\item Fondateur de la logique moderne et de son symbolisme.
%\item Publie des ouvrages 
%\end{itemize}
%\section{Gentzen}
%\begin{itemize}
%\item Définit une déduction naturelle.
%\end{itemize}
%\section{Russel}
%\section{Méthodes}
%\subsection{Sémantique}
%On va s’intéresser au sens d'une formule (table de vérité)
%\subsection{Syntaxique}
%Réécriture\\
%\[ \dfrac{\Gamma \vdash A,\Delta \Gamma\vdash B,\Delta}{\Gamma \vdash A\wedge B, \Delta} \]
%\subsection{Types de logiques}
%\begin{itemize}
%\item Logique des propositions (ordre 0).
%\item Logique des prédicats.
%\item Logiques déviantes.
%\end{itemize}
\section{Logique}
	\subsection{Introduction}
		Le calcul des propositions ou des énoncés:
		\begin{itemize}
			\item des plus élémentaires (ordre 0)
			\item des plus fondamentaux
			\item des plus simples: propositions non analysée
		\end{itemize}
		Calcul: 
		\begin{itemize}
			\item étudie les énoncés qui sont soit vrais, soit faux
			\item Vériconditionnel: comment les énoncés complexes deviennent vrais ou faux selon que énoncés qui le compose sont vais ou faux.
		\end{itemize}
		\begin{description}
			\item[Définition]: Un énoncé ou proposition est de qui est vrai ou faux
				\begin{center}
					\underline{Notion simplificatrice de la vérité}
				\end{center}
		\end{description}
		\textbf{On s’intéresse à la structure des propositions complexes}
		\begin{itemize}
			\item indépendamment de leur contenu de signification
			\item indépendamment de la langue naturelle
		\end{itemize}
		La logique est un langage
		\begin{itemize}
			\item Vocabulaire
			\item Syntaxe
			\item Sémantique
		\end{itemize}
	\subsubsection{Vocabulaire}
		\begin{enumerate}
			\item Ensemble infini dénombrable de proposition
			\begin{itemize}
				\item désignés par une lettre minuscule
			\end{itemize}
			\item Ensemble d'opérateurs
			\begin{itemize}
				\item négation: $\neg$
				\item conjonction: $\wedge$
				\item disjonction: $\vee$
				\item implication: $\rightarrow$
				\item équivalence: $\leftrightarrow$
			\end{itemize}
			\item Ensemble de séparateurs: (, ), [, ] , \{, \}
		\end{enumerate}
		\subsubsection{Syntaxe}
			\begin{itemize}
				\item Le vocabulaire peut donner lieu à de multiples assemblages de symboles
				\item Les assemblages qui font partie du langage sont appelés des formules
				\item Les formules sont obtenues à partir de règles de formation
			\end{itemize}
			\begin{description}
				\item[Formules]:
				\begin{enumerate}
					\item Toute proposition est une formule: formule atomique
					\item Récurrence: Si $A$ et $B$ sont deux formules Alors $\neg A$, $(A\wedge B)$, $(A\vee B)$, $(A\rightarrow B)$, $(A\leftrightarrow B)$, ... sont des formules
					\item Clôture: rien d'autre n'est une formule
				\end{enumerate}
				\item[Remarques]:
				\begin{enumerate}
					\item Les parenthèses permettent de déterminer l'ordre d'application des règles
					\item Langage objet et méta-langage
					\begin{itemize}
						\item langage objet: objet de la théorie (langage des formules)
						\item introduction de nouveaux symboles: A, B, $\Leftrightarrow$, $\vDash$, ... qui permettent de parler des formules (langage de l'observateur)
					\end{itemize}
					\item L'ensemble des formules est infini dénombrable
					\item Cet ensemble est récursif
				\end{enumerate}
			\end{description}
\section{Validité d'une formule}
	\subsection{Sémantique}
		\begin{itemize}
			\item La sémantique attribue une signification aux formules du langage
			\item Un proposition est soit vraie soit fausse
		\end{itemize}
		\begin{description}
			\item[Définition]: Le domaine sémantique est $\{V, F\}$
			\item[Définition]: Interpréter une formule consiste à lui attribuer la valeur V ou F
			\item[Définition]: On appelle assignation sur $n$ propositions un ensemble d'interprétations de ces propositions. Elle définit un monde possible
			\item[Définition]: L'interprétation est une fonction appelée fonction de vérité $\{assignations\}\longrightarrow\{V,F\}$. A partir de $n$ propositions, il est possible de définir $2^{2^n}$
			\item[Opérateur propositionnel]:
			\begin{itemize}
				\item Les fonctions de vérité d'une ou de deux propositions constituent les définitions sémantiques des opérateurs propositionnels
				\item Ces opérateurs suffisent pour exprimer les fonctions de vérité de plus de 2 propositions
			\end{itemize}
			\item[Définition]: Une assignation qui rend vrai une formule est appelé un modèle pour cette formule
		\end{description}
	\subsection{Validité et Consistance}
		\begin{description}
			\item[Définition]: Une formule est sémantiquement consistance, ou consistance, si elle admet au moins un modèle.
			\item[Définition]: Une formule est dite valide si toutes ses assignations sont des modèles. Une formule valide est aussi appelée tautologie.
			\item[Théorème]: Si une formule est valide (resp. inconsistante), la formule obtenue en substituant chaque occurrence d'une lettre de proposition par une formule quelconque est également valide (resp. inconsistante).
		\end{description}
	\subsection{Remarque: Métalangage}
		\begin{itemize}
			\item L'expression: "A est une formule valide" appartiens au métalangage, on la note: $\vDash$
			\item Le symbole $\vDash$ ne peut pas apparaître dans une formule du langage objet
		\end{itemize}
		\begin{description}
			\item[Remarque]: $\rightarrow$ est un opérateur logique comme les autres.
		\end{description}
\section{Théorie syntaxique}
	\subsection{Introduction}
		Pour connaître la validité d'un formule, on dispose de 2 méthodes:
		\begin{itemize}
			\item méthode sémantique (table de vérité)
			\item méthode symbolique (syntaxique): transformer, réécrire, une formule équivalente pour aboutir à une formule remarquable (tautologie)
		\end{itemize}			
	\subsection{Équivalence et remplacement}
		\begin{itemize}
			\item Des formules différentes peuvent avoir la même table de vérité
		\end{itemize}
		\begin{description}
			\item[Définition]: 2 formules ont la même table de vérité ssi: \[ \vDash A \leftrightarrow B \]
			\item[Définition]: Relation d'équivalence logique: \[A\Leftrightarrow B\: ssi\: \vDash A \leftrightarrow B\]
			\item[Remarques]:
			\begin{itemize}
				\item $\Leftrightarrow$ n'est pas un opérateur permettant de définir une formule
				\item $A\Leftrightarrow B$ est une relation du méta-langage
				\item $\Leftrightarrow$ est une relation d'équivalence (réflexive, transitive, symétrique)
			\end{itemize}
			\item[Théorème de remplacement]: Notons $\Phi(F)$ une formule contenant la sous formule $F$. Si $A\Leftrightarrow B$ alors $\Phi(A)\Leftrightarrow \Phi(A/B)$ (\emph{A est remplacé par B}).
			\item[Corollaire]: Si $A\Leftrightarrow B$, alors si $\vDash\Phi(A), \vDash\Phi(A/B)$
			\item[Intérêt]: On peut construire une chaîne d'équivalences sans passer par les tables de vérité.
		\end{description}
	\subsection{Algèbre de Boole}
		\begin{description}
			\item[Calcul]: transformer une formule en une formule équivalente.
			\item[Équivalences fondamentales]: justifiées par les tables de vérité.
			\item[Définition]: $1$ et $0$ sont deux formules particulières. $1$ désigne la classe des formules valides, $0$ désigne celle des formules inconsistantes.
			\item[Notation]: $F\Leftrightarrow 1$ si $\vDash F$\\$F\Leftrightarrow 0$ si $\vDash\neg F$
			\item[Idempotence]: $A\vee A\Leftrightarrow A$, $A\wedge A\Leftrightarrow A$.
			\item[Non contradiction]: $A\wedge\neg A\Leftrightarrow 0$
			\item[Tiers exclu]: $A\vee\neg A\Leftrightarrow 1$
			\item[Double négation]: $\neg\neg A \Leftrightarrow A$
			\item[Éléments neutres]: $A\wedge 1 \Leftrightarrow A$, $A\vee 0 \Leftrightarrow A$
			\item[Commutativité]: $A\vee B\Leftrightarrow B\vee A$, $A\wedge B\Leftrightarrow B\wedge A$
			\item[Réécriture]: $A\leftrightarrow B \Leftrightarrow (A\wedge B)\vee (\neg A\wedge\neg B)$\\$A\rightarrow B \Leftrightarrow \neg A\vee B$
			\item[Corollaires]:
				\begin{description}
					\item[Lois d'absorption]: $A\vee (A\wedge B) \Leftrightarrow A$, $A\wedge (A\vee B) \Leftrightarrow A$
				\end{description}
		\end{description}
	\subsection{Formes normales}
		\begin{description}
			\item[Rôle important]: manipulation "courante" des formules mises sous formes normales.
			\item[Définition]: On appelle \emph{clause} une disjonction de termes ou chaque terme est soit une lettre de proposition, soit une négation de lettre de proposition.
			\item[Définition]: Une formule est dite en \emph{forme normale conjonctive (FNC)} si elle est une conjonction de clauses.
			\item[Définition]: Une formule est dite en \emph{forme normale disjonctive (FND)} si elle est une disjonction de conjonctions dont chaque terme est une lettre de proposition ou une négation de lettre de proposition.
			\item[Théorème]: Pour chaque formule, il existe au moins une FNC et une FND logiquement équivalente. Elles sont appelées formes normales de cette formule.
			\item[Algorithme de normalisation]:
				\begin{enumerate}
					\item Élimination des connecteurs $\rightarrow$ et $\leftrightarrow$
					\item Application des lois de De Morgan et élimination des doubles négations
					\item Application des règles de la distributivité
				\end{enumerate}
		\end{description}
	\subsection{Méthode des arbres}
		\subsubsection{Méthode syntaxique}
			\begin{itemize}
				\item décider si une formule est valide ou inconsistante
				\item permet de développer une formule
				\begin{itemize}
					\item construire une FND équivalente
				\end{itemize}
				\item système formel $\Rightarrow$ définir des \emph{règles de réécriture}
				\item méthode graphique:
				\begin{itemize}
					\item une conjonction est vraie ssi les 2 termes sont vrais:\emph{séquence}
					\item une disjonction est vraie ssi au moins 1 terme est vrai:\emph{branchement}
				\end{itemize}
				\item règles de constructions
				\begin{description}
					\item Construire un arbre à partir d'une formule donnée en ré-écrivant chaque formule
					\item on pointe une formule pour indiquer qu'elle a été réécrite
				\end{description}
				\item règles de réécriture pour: $\vee,\wedge,\neg,\rightarrow,\leftrightarrow$ et leur négation.
				\item construction de chemins
				\item fermeture d'un chemin: on ferme un chemin dès qu'il contient une formule et sa négation
				\item arbre complètement développé: les formules sont réécrites jusqu'au lettres de propositions ou leurs négations
				\item chemins \emph{non fermés} de l'arbre complètement développé
				\begin{itemize}
					\item chemins de vérité: conjonction de lettres de proposition obtenues en lisant l'arbre de bas en haut. Si la valeur d'un chemin est vraie, la formule est vraie
					\item termes d'une FND équivalente
				\end{itemize}
			\end{itemize}
\section{Validité d'un raisonnement}
	\subsection{Théorie sémantique}
		\begin{description}
		\subsubsection{Objectifs}
			\item[Jusqu’à présent]:
				\begin{itemize}
					\item véracité des énoncés
					\item relation entre formules ($\Leftrightarrow$)
				\end{itemize}
			\item[Déduction]:
				\begin{itemize}
					\item \emph{Opération} qui consiste à adjoindre à un ensemble d'énoncés un autre énoncé nécessairement vrai si les premiers le sont.
					\item \emph{Relation de déductibilité} entre hypothèses et conséquence résultante
					\item \emph{Tautologie - Validité}: A est valide si toutes les assignations sont des modèles
				\end{itemize}
			\item[Définition]: Nous notons $A_0,A_1,\ldots,A_n \models B$ ssi toute assignation qui vérifie conjointement $A_0,A_1,\ldots,A_n$ vérifie également $B$
			\item[Définition]: $B$ est une \emph{conséquence valide} de $A_0,A_1,\ldots,A_n$.\\
				$\models$ est une relation, \emph{la relation de déductibilité}, entre formules.
			\item[Remarque]: Une tautologie est toujours vraie, conditionnée par aucune prémisse: $\models A$ est une abréviation de $\emptyset\models A$.
			\item[Propriétés de la relation $\models$]:
				E et F désignent deux listes de formules finies
				\begin{enumerate}
					\item si $A in E, E\models A$
					\item si $E\models A$ alors $E,F\models A$
					\item si $E\models A$ et $F,A\models B$ alors $E,F\models B$
				\end{enumerate}
			\item[Théorème]: $B\models A$ ssi $\models B\rightarrow A$.
			\item[Théorème]: $A_0,\ldots,A_n\models A$ ssi $A_0,\ldots,A_{n-1} \models An \rightarrow A$.
		\end{description}
		
\section{Déduction naturelle}
	\subsection{Règles pour l'implication}
		\begin{itemize}
			\item $\rightarrow_e$ : $A,A\rightarrow B \vdash B$
			\item $\rightarrow_i$ : $X,A \vdash B, X \vdash A \rightarrow B$
		\end{itemize}
	\subsection{Règle pour la disjonction}
		\begin{itemize}
			\item $\vee_i$ : $A\vdash A\vee B$
			\item $\vee_e$ si $A\vdash C$ et $B\vdash C$, alors $A\vee B\vdash C$
		\end{itemize}
	\subsection{Règles pour la négation}
		\begin{itemize}
			\item $\neg \neg_e$ : $\neg\neg A\vdash A$
			\item $\neg_i$ : si $X,A\vdash B$ et $x,A\vdash \neg B$ alors $X\vdash \neg A$
		\end{itemize}
	











\end{document}