LOGIQUE (par L. Iturrioz)

Les relations :
2 éléments peuvent être en relation, ou pas… Cela peut être n’importe quoi. Voir les exemples du vocabulaire…
Vocabulaire :
On défini x,y,z des éléments d’un ensemble :
•	Réflexive : Si xRx (x en relation avec x).
« est divisible par » est réflexive, « est le carré de » non.
•	Transitive : Si xRy et yRz,  alors xRz.
« est plus grand que » est transitive , « est le double de » ne l’est pas (ex : x=2, y=4, z=8)
•	Antisymétrique : Si xRy et yRx, alors x=y.
« est plus grand que (sens large) » est antisymétrique, « est l‘opposé de » ne l’est pas

Une relation d’ordre est une relation réflexive, transitive, et antisymétrique. Les exemples typiques de relation d’ordre sont .

Le diagramme de Hasse :
On représente les éléments d’un ensemble associé d’une relation d’ordre sur le diagramme de Hasse.
•	Si l’élément est plus haut qu’un autre, cela veut dire qu’il est supérieur, 
•	Si il est plus bas, il est inférieur,
•	S’il est sur la même ligne, il est du même niveau mais pas en relation avec ses semblables (sinon, ce serait le même !)
Règles : 
•	On relie les éléments entre eux s’il sont en relation (on comprend d’après la phrase précédente pourquoi on ne fait jamais de traits horizontaux)
•	On ne représente pas la réflexivité (on ne fait jamais de traits qui ont le début et la fin confondues…)
•	On ne représente pas la transitivité (jamais de triangles !)
•	Un élément isolé est toujours placé au niveau 0.
Ex : soit l’ensemble {1,2,3,5,30}, avec la relation d’ordre divisibilité :

On voit sur ce diagramme que 1 est l’élément le plus bas (niveau 0), on dit que c’est un atome.
On voit que 1 divise 2, 3 et 5 (d’ou les traits de relation),  au niveau au dessus.
2, 3 et 5 sont sur le même niveau parce qu’ils ne se divisent pas entre eux : règle 1. 
On ne dit pas que 1 divise lui même : règle 2 : pas de reflexivité. 
Mais il divisent 30, alors on met 30 sur le niveau supérieur, car 30 > 2, 3 et 5.
1 divise 30 aussi, mais on ne met pas de traits règle 3 : car se serait de la transitivité avec 2, 3 ou 5, et on verrait des triangles (1-3-30 ; 1-2-30 ; 1-5-30) : interdit ! !

       30

     2     3       5
  
	  1

Ex : soit l’ensemble E={1,2,3,5,6,10,15,30}, avec la relation d’ordre divisibilité :

Non, ce n’est pas un dessin en 3D, c’est un diagramme de Hasse en 2D normal…
1 est la base : rien ne divise 1 dans E. Mais 1 divise tout. Les autres seront donc au dessus, on les prend un par un :
2 est un multiple de 1 ( 1 divise 2). On le met au niveau 1.
3 est multiple de 1, mais pas de 2, on le met aussi au niveau 1.
5 est multiple de 1, mais pas de 2, ni de 3, on le met aussi au niveau 1.
6 est multiple de 1, et de 2, et de 3, on le met au niveau 2, relié à 2 et 3, mais pas à 1 : règle 3
pareil pour 10 et 15, reliés à leurs diviseurs du niveau 1, on les met aussi au niveau 2 car ils ne se divisent pas mutuellement, ni avec 6, ni par 6…
30 est multiple de 6, 10 et 15, on le met au dessus (niveau 3), relié a 6, 10 et 15.

  30                  (niv 3)

 6      10      15 (niv 2)
  2     3        5    (niv 1)

         1         (niv 0)

Ce cas est un cas particulier, quand il forme une belle figure comme ça qui ressemble à un cube : c’est une algèbre de Boole.

Les treillis :

Voilà un treillis, c’est représenté par un diagramme de Hasse ayant les particularités suivantes : 
Un niveau n est formé de x éléments,
Le niveau inférieur est l’intersection de ces éléments.
Le niveau supérieur est l’union de ces éléments.
( concrètement, si A={a,b,c} , E = P(A) = {{},{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}, alors posons a = {a}, b = {b}, alors , ayez cet exemple en tête ! !)

               

   a	          b

Propiétés des treillis : 
•	
•	
•	
•	
N’oubliez pas que l’on peut remplacer les a,b,c,d par n’importe quels ensembles, y compris poser c = d par exemple (ça sert !), et garder bien l’exemple en tête pour illustrer ceci…

Les Algèbres de BOOLE :
Une algèbre de Boole contient l’élément 0 (qui signifie « rien ») , l’élément 1 (qui signifie « tout ») . On peut envisager d’autres éléments qui sont entre le rien et le tout.

Ex : tout le trait, c’est l’algèbre de Boole. L’élément 1, c’est tout le trait, l’élément 0, c’est rien, et un élément a de l’algèbre de boole, c’est le segment entre les points par exemple.
Et l’élément b, c’est le segment entre les flèches.
On a 2 opérations :
•	Le OU , noté ou ۷, est l’union de 2 éléments. Ex : a OU b, c’est le segment du 1e point à la 2e  flèches. (c’est tout ce qui est sur a et/ou sur b donc)
•	Le ET , noté ou ۸, est l’intersection de 2 élémnts. Ex : a ET b, c’est le segment de le 1e flèche au 2e point, c’est plus petit (c’est tout ce qui est sur a et sur b)
De la on défini ⌐a c’est tout ce qui n’est pas le segment a. Donc l’union : a⌐a =1.
Les règles des algèbres de Boole sont intuitives.(et c’est trop chiant à écrire)
Les moins évidentes et archi importantes : , ce qui équivaut à 

Les relations d’ordre dans les algèbres de Boole :
Il faut connaître 2 règles : 
•	(rappelez vous des treillis, le OU est au dessus (donc plus grand) et le ET est en dessous (donc plus petit)
•	(j’ai mis a et b en colonne pour dire que ça marche aussi bien si on met a ou si on met b)
Exercice : 
Montrer que 
Visuellement c’est facile (imaginez le segment en haut avec des petits segments a et b, si a est plus grand que b, alors ⌐a sera plus petit que ⌐b), mais plus rigoureusement : 
=> soit a≤b  règle 1 : a = a۸b et b = a۷b. Donc ⌐a = ⌐(a۸b) = ⌐a۷⌐b   et    ⌐b= ⌐(a۷b) = ⌐a۸⌐b.	on reprend la règle 1, on a bien ⌐b≤⌐a…
<= soit ⌐b≤⌐a  ⌐a = ⌐a۷⌐b et ⌐b = ⌐a۸⌐b. Donc a = ⌐(⌐a۷⌐b) =a۸b et⌐b= ⌐(⌐a۷⌐b)= a۷b. on reprend la règle 1, on a bien a≤b…
La double implication est démontrée, donc c’est équivalent CQFD.
Sur les relations d’ordre comme ça, il suffit de connaître les 2 règles, et c’est de la recette, et c’est toujours pareil…

Quel rapport avec le diagramme de Hasse du haut ?
Le niveau 0 de l’arbre, c’est celui tout en bas. Même si l’élément est appelé 1, ici c’est le 0 de l’algèbre de Boole, car il est tout en bas, et l’élément le plus petit d’une algèbre de Boole est le 0. L’élément tout en haut est le 1 de l’agèbre de Boole  car il est tout en haut, c’est le plus grand. (il est appelé 30 dans ce cas, c’est son nom)
Les éléments 2, 3 et 5 sont juste au dessus de l ‘élément 0, on dit que ce sont des atomes.
On ne peut pas les décomposer.
Mais on peut décomposer 6 en 3*2. (rappel dans ce cas les liaisons sont en fonction de la divisibilité). Donc 6 n’est pas un atome.
6 est juste au dessus de 2 et 3, on dit qu’il couvre 2 et 3.
Visuellement, car c’est mieux :

			30 : tout l’ensemble de l’algèbre de Boole (élément 1 de l’algèbre)
			10									6
							15
     				      5						    3	                   2				
C’est visuel, c’est hors programme, c’est juste pour avoir une vision de ce qu’on fait.
30 contient les segments 10, 15 et 6 (et tous les autres aussi) car tous ces nombres divisent 30.
Le 10 déborde sur le 6 car ils ont une partie commune, le 2.
Le 10 et le 15 ont une partie commune, le 5, c’est pour ça qu’ici : 10۸15 = 5
Bref, bon, c’est ma façon à moi de voir, si vous avez compris ou je veux en venir, tant mieux, sinon, filez dans l’abstrait avec les règles, et surtout… Bonne chance (vous en aurez bien besoin…)

Calcul propositionnel

On travaille sur des inconnus pouvant prendre 2 valeurs, soit vrai, soit faux.
Les opérateurs :
Les opérateurs relient ces éléments, et donnent vrai ou faux selon que les éléments opérés sont vrais ou faux.
Exemple : ab (qui veut dire a ET b) donne vrai que si a et b sont tous les 2 vrais, sinon, il donne faux.)
Voici tous les tables de vérité et les opérateurs qu’on étudiera :
Soit A et B des propositions. On note 1 si elles sont vraies, 0 si elles sont fausses. Ce tableau envisage tous les cas de combinaisons entre A et B
A	B	A	AB 	AB	B	AB	AB	
0	0	1	0	0	1	1	0	
1	0	0	0	1	0	0	1	
0	1	1	0	1	1	0	1	
1	1	0	1	1	1	1	0	

Propriété des opérateurs :
•	Le  (NON) renvoie le contraire. Si A est vrai, alors A est faux ; si A est faux, A est vrai
•	Le (ET) (pour s’en souvenir, on pense à l’intersection(même symbole), qui donne l’ intervalle donné ET par l’un, et par l’autre.). Le ET renvoie vrai que si les 2 propositions testées sont vrais. Des qu’on sait que l’un est faux, il devient inutile de calculer le 2è : le résultat sera de toute façon faux.
•	Le (OU) (symbole réunion, qui donne l’intervalle donné par l’un OU l’autre). Le OU renvoie vrai si au moins une des 2 est vraie. Si on sait que l’une des 2 est vraie, inutile de calculer la 2e, le résultat sera de toute façon vrai.
•	Le (OU exclusif), (en fait, c’est un V à l’envers avec un point dedans), renvoie vrai que si l’une ou l’autre des propositions est vraie mais pas les 2 : il renvoie faux si les 2 propositions dont vraies.
•	Le  (Equivalent), renvoie vrai si les 2 propositions sont toutes les 2 vraies, ou toutes les 2 fausses, donc si les 2 propositions sont équivalentes.
•	Les (implique) renvoie vrai dans tous les cas, sauf quand le vrai implique le faux (voir tableau. On peut remplacer AB par B.

Vocabulaire :
Une proposition est dite valide lorsqu’elle est toujours vraie, quelque soit les valeurs de ses inconnus, on dit que cette proposition est une TAUTOLOGIE.
Ex : est une tautologie. En effet, si b est vrai, alors le OU est vrai et A est vrai. Si b est faux, alors b est vrai, et le OU est vrai, et A est vrai. Donc la proposition A est toujours vraie, c’est une tautologie.
Une proposition est dite inconsistance si elle est toujours fausse : Ex : 
Une proposition est dite consistante si elle peut être vraie ou fausse selon que les propositions qui la constituent sont vraies ou fausses. (donc toutes les propositions qui ne sont ni valides ni inconsistantes)

Diagramme de QUINE :
Il sert à simplifier des expressions compliquées.
Ex : on veut simplifier 
On a 3 propositions la dedans qui peuvent être soit vraies soit fausses, p, q et r.
A est est donc une proposition plus compliquée dépendant de p, q et r.
Pour le diagramme de QUINE, on choisi une de ces inconnues, et on va envisager 2 cas. D’un coté, q est vraie, de l’autre, q est fausse. On va représenter ça sous forme d’un arbre.

			             vrai		q		faux

						Valide

	      vrai	     p	      faux	

	r				r
Dans cet exemple, on choisit q en premier (choisi au hasard). D’un coté de l’arbre, on a dit   « q est vrai », de l’autre, on dit « q est faux ».
On raisonne ensuite en remplaçant les q par vrai ou faux, et on écrit une expression simplifiée, des fois tellement simplifiée que ça devient une forme valide ou une forme inconsistante.
Type :Si l’implication vous gène, on peut remplacer par , c’est équivalent.
Donc tout est vachement simplifié.
On trouve donc que la proposition globale est vraie si q est faux ou que r est vrai ( p n’a pas d’importance). 
On peut donc écrire cette proposition plus simplement :  . Voilà, c’est simplifié.

Exercice type 1:
Utiliser la méthode de QUINE pour simplifier ’expression:
Si vous êtes à l’aise avec des  (parce que pas moi), lancez vous franco dans l’arbre de QUINE. Si vous êtes prudent, virez les  grâce au type plus haut, et si vous voulez vous donner à fond, utilisez les propriétés de simplification de l’algèbre de Boole.

Et quand vous êtes plus à l’aise (moins mal à l’aise), go !

on pose P vrai d’un coté, faux de l’autre.	        P
					   Vrai			Faux

							

Si P est faux, la formule est valide
								Sinon, encore consistantcontinue
								Envisageons, par exemple, Q
			Vrai		Q		Faux

								

Si Q est Vrai à partir de P vrai, c’est valide, sinon…
								R
							  Vrai           Faux
						  F				V
Fini ! Plus d’ambiguités ! On a plus que des feuilles en vrai ou faux.
Il faut raisonner : 
Cherchons : Quand est-ce que E est vrai ? (général : à retenir)
Il est plus facile de déterminer ici quand E est faux.
E n’est faux que si P est vrai, Q est faux, et R est vrai … (Facile à voir non ?)
Cela s’écrit : 

On bidouille tout ça pour isoler E, on trouve :

Voilà qui est bien simplifié… FINI.

FND et Clauses :
Considérons une FND (forme normale disjonctive) : une expression de cette forme :

Chaque C s’appelle une Clause. Une clause est de la forme . Chaque a est un littéral, c’est à dire une variable booléenne (comme P, Q et R dans l’exercice type1)
On peut écrire les FND sous la forme ou la virgule sera l’équivalent du ET.
Règles : 
•	Une FND vide (sans clauses) est Vraie (Si on ajoute un à la FND, cela ne lui change rien, si on enlève toutes les clauses, il ne reste que ce V)
•	Une clause vide (sans littéraux) est fausse (Si on ajoute un à la clause, cela ne lui change rien, si on enlève tous les littéraux, il ne reste que ce F)
•	Une clause fausse rend toute la FND fausse (car )
•	On peut écrire toute expression compliquée sous forme de FND. (dans l’exercice type 1, on a une expression compliquée qui s’écrit comme une FND avec qu’une clause.
Exercice type 2 :
Avec la méthode quine, prouver la validité de : {P, (PQ)}╞ Q.
On voit des accolades avec un signe bizarre derrière, les accolades, c’est une FND 
Rem : (PQ) n’est pas une clause ? Si ! c’est , et P est une clause à 1 littéral.
Ceci veut dire « à partir des hypothèses P et (PQ) (entre accolades, les hypothèses), on en déduit (signe bizarre) Q. » (autrement dit, si tout ce qui a dans les accolades est vrai et seulement si toutes les propositions de l accolade sont vraies, alors Q est vrai).
Operations effectuables avec des FND suivies de ╞ 
•	On peut ramener ce qu’il y a après le signe ╞ dans la FND en mettant un « non » devant.
{P, (PQ)}╞ Q  {P,(PQ),⌐Q}╞ Faux
•	On peut développer la FND en remettant des ET à la place des virgules.
{P,(PQ),⌐Q}  

Donc pour prouver que {P, (PQ)}╞ Q, il faut montrer que , donc inconsistante. On le démontre avec la méthode de QUINE. (voir exercice type 1)
Faites la méthode de QUINE, toutes les feuilles donnent faux, la formule est donc inconsistante, CQFD.

Algorithme de Davis et Putnam :
Il sert à tester la validité , la consistance et l’inconsistance d’une FND.
C’est une autre méthode que celle de QUINE, mais donne la même chose.
Ex : 
Comme avec QUINE, on va choisir un litéral (A, S, P ou T), puis on va faire 2 branches. Sauf qu’ici, on garde l’expression sous cette forme entre accolade. A gauche on considérer le littéral choisi, à droite, sa négation.

					   A			      ⌐A

	Ici, on enlève les clauses contenant A	     Ici, on enlève les clauses contenant ⌐A

	Et les littéraux ⌐A				     et les littéraux contenant A
	Ici, on continue encore car		La dernière clause devient vide, donc fausse.
	est encore consistant		Donc ={F}.
….
On continue la méthode (trop long à dessiner, la suite de l’arbre…)

On trouve que E est faux de partout sauf pour 
Chacun de ces chemins qui conduit à un vrai s’appelle un modèle.
On a ici 2 modèle, on note comme ça : 
1e modèle : I(A)=1, I(S)=1, I(T)=1, I(P)=0 (tout est vrai sauf le P)
2e modèle : I(A)=1, I(S)=0, I(T)=0, I(P)=1

Note : on aurait pu faire l’exercice type 2 par cette méthode, on aurait eu aucun modèle, preuve de l’inconsistance.

Exercice type 3 :
Est ce que ce raisonnement est juste ? Analyser.
L’attaque envisagée réussira seulement si l’ennemi est surpris ou si la position est peu défendue. L’ennemi ne sera pas surpris, à moins qu’il soit téméraire. Il n’est pas téméraire si la position est peu défendue. Donc l’attaque ne réussira pas.

Posons les littéraux :
A : attaque réussie.
S : ennemi surpris.
P : Position peu défendue.
T : ennemi téméraire.

Posons les hypothèses : 
H1) L’attaque envisagée réussira seulement si l’ennemi est surpris ou si la position est peu défendue
 SI attaque réussie ALORS (ennemi surpris OU position peu défendue) 
H2) L’ennemi ne sera pas surpris, à moins qu’il soit téméraire
 SI l’ennemi n’est pas téméraire ALORS il n’est pas surpris 
H3) Il n’est pas téméraire si la position est peu défendue
SI la position est peu défendue ALORS il n’est pas téméraire  
CONCLUSION) Donc l’attaque ne réussira pas

SI le raisonnement est juste, alors les hypothèses engendrent la conclusion, ce qui se traduit par :
{H1,H2,H3}╞ Conc
Apres, la réflexion est finie, on applique :
 {H1,H2,H3,⌐Conc}╞ Faux 
Y’a plus qu’à confirmer ou démentir. A votre choix, la méthode de Putnam (après avoir vu que toutes les hypothèses et la conclusion sont bien des Clauses) ou celle de QUINE (après avoir écrit {H1,H2,H3,⌐Conc}  )
….
On trouve que toutes les branches de l’arbre ne mènent pas à du faux. Le raisonnement donné par l’énoncé n’est pas fiable.
Car si on a A, S, T, ⌐P le raisonnement passe (donc l’attaque passe si l’ennemi est surpris, téméraire et pas peu défendu ).
Et aussi A, ⌐S, ⌐T, P est vrai (l’attaque passe aussi si l’ennemi n’est pas surpris, pas téméraire et à une position peu défendue).
(Ces 2 dernières phrases qui montrent les possibilités de contredire le raisonnement sont ici des modèles)

BONNE CHANCE LES GARS !