[PDF] Le calcul propositionnel Soit R en ensemble dé

View - Download Le calcul propositionnel

Previous PDF

Next PDF

Syntaxe

Sémantique

Dénissabilité

Systèmes de preuves

Systèmes de preuves sémantiques (tables de vérité)

Systèmes de preuves syntaxiques

lettres dites propositionnelles formules de la logique propositionnelle est le plus petit ensemble contenantR?? ????? :(p)_(p;p)!(^(p;q);:(r)) :p p_p(p^q)! :r ?? ??????#????_?^??!?

SiA??? ??? ??????p?

SF(A) =fpg?

SiA???:(B)?

SF(A) =f:Bg [ SF(B)?

SiA???#(B;C)?

SF(A) =f#(B;C)g [ SF(B)[ SF(C)?

Fixer une

interprétation qui donneV??F? ?????? ??????

Dénir la

fonction booléenne unaire FB ::BOOL!BOOL fonctions booléennes binaires FB _;FB^;FB!:BOOL2!BOOL?

Construire la

valeur de vérité de la formuleA? FB (V) =F FB (F) =V FB _ (V;V) =V FB _ (V;F) =V FB _ (F;V) =V FB _ (F;F) =F FB (V;V) =V FB (V;F) =F FB (F;V) =F FB (F;F) =F FB (V;V) =V FB (V;F) =F FB (F;V) =V FB (F;F) =V ?????? ?? ?????? ????? ???????A??? ??????? ? ???

SiA??? ??? ??????p?

[A]I =I(p)?

SiA???:(B)?

[A]I =FB:([B]I)?

SiA???#(B;C)?

[A]I =FB#([B]I;[C]I)? ?????? ?? ?????? ?? ?? ???????(p_q)! :(q^q)??? ??????? ?I? Méthode pour raisonner sur les modèles de formules propositionnelles.

Comment ça marche?

SoitA??? ??????? ????? ????? ???????

1. Construire une table où chaque colonne est étiquetée par une 2.

Pour chaque lignem?? ?? ????? ?

(a) Donner une interprétationIm??? ???????p1;:::;pn? (b)

Calculer les valeurs[A1]Im;:::;[Ak]Im

I une formule

A??[A]I=V

I une formule

A??[A]I=F?

I un ensemble de formules I un ensemble de formules ???????A????Δ????? ???[A]I=F?

Dénition :

formule A??? satisfaisable s'il existe au moins ensemble de formules satisfaisable s'il existe au moins une interprétationI????? ???I formule A??? contradictoire si elle n'est pas satisfaisable, c'est à dire s'il n'existe pas d'interprétationI??? ensemble de formules contradictoire si il n'est pas satisfaisable (s'il n'existe pas d'interprétation qui satisfait toutes les formules deΔ

Dénition :

formule A??? valide si toute interprétation satisfaitA? ?? ensemble de formulesΔ??? valide si toute formule deΔ??? ??????? formule A??? conséquence logique d'un ensemble de formules

Δj=A

Si la colonne étiquetée par la formuleA???? ??? ??? valide contradictoire Sinon, l'interprétation qui rendsV?? ??????? ?? ?? ???????A ???????A A?

Dénition :

equivalentes , noté

A´B? ???fAg j=B??fBg j=A?

:A´B???(A!B)^(B!A)??? ??????? (A_B)_C´A_(B_C) (A^B)^C´A^(B^C)

A_B´B_A

A^B´B^A

A_A´A

A^A´A

:(A^B)´ :A_ :B :(A_B)´ :A^ :B

A_(B^C)´(A_B)^(A_C)

A^(B_C)´(A^B)_(A^C)

::A´A

A!B´ :A_B

fE1;:::;Eng j=A??? ?? ???????E1^:::^En!A??? ??????? 2. 3.

L'ensemble vide est satisfaisable.

4. L'ensemble de toutes les formules est contradictoire. 5. 6. 7. Toute formule est conséquence logique d'un ensemble insatisfaisable de formules. 8. Toute formule valide est conséquence logique d'un ensemble quelconque de formules, en particulier de l'ensemble vide. 10.

Théorème :

satisfaisable ssi tout sous-ensemble ni deΔ??? satisfaisable

Dénition :

p

1;:::;pn?n¸0?? ??

fonction booléenne n-aire qui réalise la formule FB

A(v1;:::;vn) = [A]I??I(pi) =vi

Dénition :

complet ssi pour v 1 v 2 v 3 f(v1;v2;v3) V V V V (p1^p2^p3)_ V V F F V F V F V F F V (p1^ :p2^ :p3)_ F V V V (:p1^p2^p3)_ F V F V (:p1^p2^ :p3)_ F F V F F F F V (:p1^ :p2^ :p3)quotesdbs_dbs29.pdfusesText_35

[PDF] logique propositionnelle exercice corrigé

[PDF] calcul propositionnel exercices corrigés

[PDF] logique propositionnelle table de vérité

[PDF] calcul propositionnel formel

[PDF] calcul des propositions exercices corrigés

[PDF] le resultat dune multiplication est

[PDF] comment calculer le taux de possession du stock

[PDF] cout de stockage annuel

[PDF] calcul du stock moyen

[PDF] exercice cout de passation et possession

[PDF] calcul tangente formule

[PDF] calcul tangente fonction

[PDF] calcul tangente en ligne

[PDF] calculer tangente calculatrice

[PDF] a quoi sert le sinus