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

^{Source : www.fvirtman.fr.st – Auteur : Fman}
ÓSNOCLUB.fr.st