Calcul Propositionnel

Marc CHEVALIER

DI ENS

18 septembre 2017

1 Syntaxe

Définition 1 -Alphabet

Un symbole est l"une de ces quatre entités :

une variable propositionnelle (ou proposition atomique, ou atome) :A,B,C,A0, ...,An;

une constante :?,?;

un connecteur logique :?,?,¬;

une paire de séparateurs :(,).

Définition 2 -Formules

L"ensemble des formule est définie par induction par : les variables et constantes propositionnelles sont des formules;

si?1et?2sont des formules :

(?1??2)est une formule;

(¬?1)est une formule.

Définition 3 -Taille d"une formule

Étant donné une formule?, on définit sa taille|?|par : 1 si?est une variable ou constante propositionnelle;

1+|?1|si?= (¬?1);

1+max(|?1|,|?2|)si?= (?1??2)ou?= (?1??2);

où?1et?2sont des formules du calcul propositionnel. 1

Définition 4

On définit l"ensemble des variables par induction sur les formules de la manière suivante :

Var

(A)={A}siAest une variable propositionnelle;

Var

((¬?))=Var(?)si?est une formule du calcul proposition- nel;

Var

((?1??2))=Var(?1)?Var(?2)si?1et?2sont deux for- mules du calcul propositionnel;

Var

((?1??2))=Var(?1)?Var(?2)si?1et?2sont deux for- mules du calcul propositionnel.

2 Sémantique

Définition 5 -Environnement

SoitVun ensemble de variables propositionnelles. Un environnement sur

Vest une fonction deV→ B.

Définition 6 -Évaluation

Soient?une formule etVun sur-ensemble fini de Var(?). NotonsV:= {A1,...,An}. Soitσun environnement surV.

Nous définissons l"évaluation

[?]σde?sur l"environnementσpar induc- tion de la manière suivante : [?]σ=ff; [?]σ=tt; [Ai]σ=σ(Ai); ttsi[?]σ=ff, ffsinon; [(?1??2)]σ=? ttsi[?1]σ=ttou si[?2]σ=tt, ffsinon; [(?1??2)]σ=? ttsi[?1]σ=ttet si[?2]σ=tt, ffsinon. 2

Définition 7 -Table de vérité

Soient?une formule etVun sur-ensemble de Var(?)non vide. La sé- mantique de la formule?(paramétrée parV) est une fonction associant chaque environnementσsurVà la valeur[?]σprise par?pour l"environ- nementσ. Cette fonction est aussi appelée table de vérité. Elle est notée ???V.

Définition 8 -Équivalence sémantique

Soit?1et?2deux formules du calcul propositionnel. Nous dirons que?1 et?2sont équivalentes sur le point sémantique si et seulement si les deux tables de vérités coïncident ie.??1?Var(?1)?Var(?2)=??2?Var(?1)?Var(?2).

Dans ce cas, nous noterons?1≡?2.

Définition 9 -Tautologie

Soit?une formule. Nous dirons que?est une tautologie si et seulement si?≡ ?.

Définition 10 -Contradication

Soit?une formule. Nous dirons que?est une contradiction si et seule- ment si?≡ ?.

3 Autres connecteurs logiques

En théorie, il peut y avoir 4 (2

quotesdbs_dbs2.pdfusesText_3

[PDF] Calcul Propositionnel

Le calcul Propositionnel - mathdesc

1 Calcul propositionnel - Université de Limoges