Scribd
Importer
11 vues13 pages

Introduction à la théorie de la démonstration

Le document présente les concepts de base de la théorie de la démonstration, y compris les définitions d'une théorie de démonstration, les formules, les axiomes, les règles d'inférence, et les théorèmes de consistance et de complétude.

Transféré par

kamirbenayad
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
11 vues13 pages

Introduction à la théorie de la démonstration

Le document présente les concepts de base de la théorie de la démonstration, y compris les définitions d'une théorie de démonstration, les formules, les axiomes, les règles d'inférence, et les théorèmes de consistance et de complétude.

Transféré par

kamirbenayad
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Chapitre 02:

Théorie de la démonstration (¬,⇒)

K. MESSAOUDI
Université Ziane Achour de DJELFA

January 17, 2022

Kaddour MESSAOUDI January 17, 2022 1 / 13


Introduction

La théorie de démonstration offre un moyen


formel qui nous permet de vérifier la validité
d’une formule et de déduire des formules à partir
d’autres formules sans s’intéresse aux
valeurs de vérité.

Kaddour MESSAOUDI January 17, 2022 2 / 13


Définitions

Une théorè de démonstration T est définie par:


Un ensemble de formules bien formées de T.
Un sous-ensemble de formules formant les
axiomes de T.
Une ou plusieurs règles d’inférences.

Kaddour MESSAOUDI January 17, 2022 3 / 13


Définitions

Une formule α est un théorème (on note


⊢α) si elle est admet une preuve dans T.
Une déduction Γ ⊢α dans T d’une formule
α à partir d’un ensemble de formule Γ est
une séquence de formules {α1,α2, ... , αn }
telle que α est la dernière ligne de la
déduction (α = αn ).

Kaddour MESSAOUDI January 17, 2022 4 / 13


Les formules

a) Les variables propositionnelles sont des


formules.
b) Si α et β sont des formules alors ¬α, α⇒β
sont des formule.

Kaddour MESSAOUDI January 17, 2022 5 / 13


Les axiomes

Un axiome est une formule admis sans


démonstration la validité.
A1: (α⇒(β⇒α))
A2: (α⇒(β⇒γ))⇒((α⇒β)⇒(α⇒γ))
A3: (¬α⇒¬β)⇒((¬α⇒β)⇒α)

Kaddour MESSAOUDI January 17, 2022 6 / 13


Les règles d’inférences

[Link] Ponens (MP en abrégé)


Si on a α, et α⇒β, alors on a β
β est une conséquence logique de α, et α⇒β.
[Link] Tolens (MT en abrégé)
Si on a α⇒β et ¬β, alors on a ¬α
¬α est une conséquence logique de α⇒β et ¬β.

Kaddour MESSAOUDI January 17, 2022 7 / 13


Exemple 1.1

⊢α⇒α

Kaddour MESSAOUDI January 17, 2022 8 / 13


Exemple 1.2

¬¬α⊢α

Kaddour MESSAOUDI January 17, 2022 9 / 13


Théorème de la déduction

Définition:
Si α1,α2, ... , αm ⊢ αn ⇒ β alors α1,α2, ... ,
αm ,αn ⊢ β.
Cas particulier:
Si ⊢ α ⇒ β alors α ⊢ β

Kaddour MESSAOUDI January 17, 2022 10 / 13


Exemple 1.3
α⇒β ⊢ ¬β⇒¬α

Kaddour MESSAOUDI January 17, 2022 11 / 13


Théorème de consistance

Soient α1,α2, ... , αn et β des formules de T.


Alors:
α1,α2,...,αn ⊢ β ⇔ α1,α2,...,αn ⊨ β.
Cas particulier:
⊢β⇔⊨β
Tous ce qui est démontrable est vrai.

Kaddour MESSAOUDI January 17, 2022 12 / 13


Théorème de complétude

Soient α1,α2, ... , αn et β des formules de T.


Alors:
α1,α2,...,αn ⊨ β ⇔ α1,α2,...,αn ⊢ β
Cas particulier:
⊨β⇔⊢β
Tous ce qui est vrai est démontrable.

Kaddour MESSAOUDI January 17, 2022 13 / 13

Vous aimerez peut-être aussi