Chapitre 6 : Logique propositionnelle

Enigme : Alice, Bob et Carole sont pris en flagrant délit par leurs parents après avoir brisé l'aquarium du salon
Alice : "Carole a cassé l'aquarium et bob n'a rien fait"
Bob : "Je suis innocent et l'une au moins ds 2 filles à touché à l'aquarium"
Carole : "Si Alice a touché à l'aquarium alors Bob y a touché"
Sachant qu'un seul enfant ment, qui est-il ?

Si Bob ment alors
	- soit Bob est coupable -> alors Alice ment : impossible
	- soit les deux filles n'ont pas touché à l'aquarium -> Alice ment : impossible
Donc Bob ne ment pas

Si Alice ment alors
	- soit carole n'a pas cassé l'aquarium => Alice a cassé l'aquarium => Bob a touché à l'aquarium => impossible
	- soit bob a cassé l'aquarium => Bob ment => impossible
Donc Carole a cassé l'aquarium alors Alice a cassé l'aquarium et Bob n'a rien fait alors Carole a cassé l'aquarium
Conclusion : Les 2 filles ont cassé l'aquarium

6.1 Le langage propositionnel

A = alphabet constitué par :
	- des constantes : T ou 
	- un ensemble P dénombrable de variables propositionnelles
	- un ensemble de conncteur
		- 	¬ 	négation
		- 	^ 	conjonction
		- 	v 	disjonction
		- 	-> 	implication
		- 	<-> 	équivalence
	- des parenthèses ()
A = {T,} u P u {¬,^,v,->,<->} u {()}

Les formules propositionelles sont les mots construits à partir de A  et vérifiant :
Syntaxe :
def : l'ensemble des propositions F construit sur A est le plus petit ensemble tel que
	(i) 	Les constantes sont dans F
	(ii)	P c F
	(iii)	si F appartient à F alors ¬F appartient à F
	(iv)	si (F,G) appartient à F alors 
			(FvG) appartient à F
			(F^G) appartient à F
			(F->G) appartient à F
			(F <-> G) appartient à F

Def : une famille propositionnelle est atomique si elle est de la forme
¬A, AvB, A^B, A->B, A<->B
avec (A , B) appartient à P²

Décomposition d'une famille propositionnelle
Théorème : Si F st un proposition de F alors F est l'une des formes suivantes :
	- F appartient à {T,}
	- F appartient à P
	- F = ¬G on a G appartient à F
	- F 	= (G^H)
		= (GvH)
		= (G->H)
		= (G<->H)
Toute famile se décompose de manière unique en formules ayant au plus un connecteur
On s'arrête lorsque les formules sont atomiques
ex : ¬(A->(B->((CvD)^E)))
= ¬F avec 
F = A -> A'
A' = B->B'
B' = (E' ^ E)
E' = C v D fin

6.2 Sémantique
Il s'agit d'évaluer les formules propositionnelles
T : vrai noté 1
 : faux noté 0
Une valuation est une fonction µ
µ: 	P -> {0,1}
	P -> µ(P)
On étend cette valuation aux formules atomques puis à toute formule en utilisant
µ(¬P) =1 - µ(P)
µ(P^)=1 si µ(P)=µ(Q)=1 			0 sinon
µ(PvQ)=1 si µ(P)=1 ou µ(Q)=1 	0 sinon
µ(P->Q) = 0 si µ(P)=1 et µ(Q)=0 	1 sinon
µ(P<->Q)=1 si µ(P)=µ(Q)			0 sinon

Tables de vérité
Représentation sous forme de tables d'une valuation

Tautologie, Antilogie

Déf : Une formule est un tautologie si sa table de vérité ne comporte que des 1
ex : A -> A
Déf : Une antilogie est un formule dont la table de vérité ne comporte que des 0
ex : A ^ ¬A

Déf : 2 formules sont logiquement équivalentes si elle ont la même table de vérité. On écrit =
ex : ( A -> B ) = ( ¬A v B )
A : Alice a cassé l'aquarium
B : Bob a cassé l'aquarium
C : Carole a cassé l'aquarium
Alice dit : C ^ (¬B)
Bob dit : (¬B) ^ (A v C)
Carole dit : A -> B

C'est Carole qui ment
Propriétés : 
associativité :
	A v (B v C) = (A v B) V C
	A ^ ( B ^ C) = (A ^ B) ^ C
commutativité
	A v B = B v A
	A ^ B = B ^ A
distributivité
	A v (B ^ C) = (A v B) ^ (A v C)
	A ^ (B v C) = (A ^ B) v (A ^ C)
Morgan
¬ (A v B) = ¬A ^ ¬B
¬ (A ^ B) = ¬A v ¬B

Absorption
 A^(AvB) = A
Av(A^B)= A