Exercices

La Théorie de la démonstration

Exercice I

Démontrer que :

càd démontrer que est un théorème.

1 − ⊢ 𝑃 → ((𝑃 → 𝑄) → ((𝑄 → 𝑀) → 𝑀))) 𝑓(𝑃, 𝑄, 𝑀): 𝑃 → ((𝑃 → 𝑄) → ((𝑄 → 𝑀) → 𝑀)) f est un théorème veut dire aussi que f est tautologie ( grâce au théorème de la complétude) 𝑓(𝑃, 𝑄, 𝑀) 𝑒𝑠𝑡 𝑢𝑛𝑒 𝑓𝑜𝑟𝑚𝑢𝑙𝑒 𝑑'𝑖𝑚𝑝𝑙𝑖𝑐𝑎𝑡𝑖𝑜𝑛 théorème de déduction (TDD) càd et grâce à ce théorème on peut transformer une démonstration en une déduction sous hypothèses: En appliquant le TDD sur ⊢ 𝑃 → ((𝑃 → 𝑄) → ((𝑄 → 𝑀) → 𝑀)))

; c’est le cas de figure pour l’application du

𝑃{ }⊢(𝑃 → 𝑄) → ((𝑄 → 𝑀) → 𝑀)) TDD 𝑃, 𝑃 → 𝑄 TDD 𝑃, 𝑃 → 𝑄, 𝑄 → 𝑀

}⊢(𝑄 → 𝑀) → 𝑀

}⊢𝑀

{ {

⊢ 𝑃 → ((𝑃 → 𝑄) → ((𝑄 → 𝑀) → 𝑀)))

en appliquant le TDD 3 fois on obtient :

A partir { 𝑃, 𝑃 → 𝑄, 𝑄 → 𝑀

}⊢𝑀

Déduction sous hypothèses } 𝑃, 𝑃 → 𝑄, 𝑄 → 𝑀 { ( remarque : c’est un ensemble d’hypothèses donc l’ordre des éléments n’affecte pas l’ensemble : en d’autres termes cet ensemble est aussi { 𝑃, 𝑄 → 𝑀, 𝑃 → 𝑄

{ } 𝑞𝑢𝑖 𝑒𝑠𝑡 𝑎𝑢𝑠𝑠𝑖 𝑄 → 𝑀, 𝑃 → 𝑄, 𝑃

}

)

1 − ℎ𝑦𝑝 𝑃 → 𝑄 2 − ℎ𝑦𝑝 𝑃 3 − 𝑚𝑝𝑝 𝑠𝑢𝑟 1&2 𝑃 → 𝑄, 𝑃 4 − ℎ𝑦𝑝 𝑄 → 𝑀 5 − 𝑚𝑝𝑝 𝑠𝑢𝑟 3&4 𝑄, 𝑄 → 𝑀 𝐶𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛 𝑀

{

}⊢𝑄 *

}⊢𝑀

++++++++++++++++++++Rappel: pour conduire correctement une démonstration ( ou encore selon le cas une déduction sous hypothèses): on peut utiliser: axiomes, hypothèses, résultats intermédiaires et aussi les règles d’inférences.

2- Démontrer que {𝐴, ¬𝐴}⊢𝐵

Il s’agit là d’une déduction sous hypothèses: {𝐴, ¬𝐴}

Déduction sous hypothèses

{𝐴, ¬𝐴}

1 − ℎ𝑦𝑝 𝐴 : 𝐴 → (¬𝐵 → 𝐴) 2 − 𝐴 1

: 𝑃 → (𝑄 → 𝑃) 𝐴 1

* 3 − 𝑚𝑝𝑝 𝑠𝑢𝑟 1 & 2: {𝐴, 𝐴 → (¬𝐵 → 𝐴)}⊢¬𝐵 → 𝐴

𝑚𝑝𝑝 {𝑃, 𝑃 → 𝑄}⊢𝑄

4 − ℎ𝑦𝑝 ¬𝐴 : ¬𝐴 → (¬𝐵 → ¬𝐴) 5: 𝐴 1

: 𝑃 → (𝑄 → 𝑃) 𝐴 1

6 − 𝑚𝑝𝑝 𝑠𝑢𝑟 4 &5 : {¬𝐴, ¬𝐴 → (¬𝐵 → ¬𝐴)}⊢ ¬𝐵 → ¬𝐴 * 7 − 𝐴

:(¬𝐵 → 𝐴) → ((¬𝐵 → ¬𝐴) → ¬¬𝐵)

10 𝐴

: (𝑃 → 𝑄) → ((𝑃 → ¬𝑄) → ¬𝑃)

8 − 𝑚𝑝𝑝 𝑠𝑢𝑟 3 & 7: {¬𝐵 → 𝐴, (¬𝐵 → 𝐴) → ((¬𝐵 → ¬𝐴) → ¬¬𝐵)}⊢(¬𝐵 → ¬𝐴) → ¬¬𝐵 * 9 − 𝑚𝑝𝑝 6 & 8: {¬𝐵 → ¬𝐴, (¬𝐵 → ¬𝐴) → ¬¬𝐵}⊢¬¬𝐵 * 10 − 𝐴

¬¬𝐵 → 𝐵

11 − 𝑚𝑝𝑝 𝑠𝑢𝑟 9 & 10: {¬¬𝐵 ¬¬𝐵 → 𝐵}⊢𝐵 𝐶𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛: 𝐵

𝑃 → (𝑄 → 𝑅) ⊢ (𝑃 ∧ 𝑄) → 𝑅

3- Montrer en utilisant la théorie de démonstration que théorème. On est déjà devant une déduction sous hypothèse car on a une première hypothèse 𝑃 → (𝑄 → 𝑅) Sauf que le résultat Par conséquent nous pouvons appliquer le TDD et identifier une autre hypothèse . en appliquant le TDD sur {𝑃 → (𝑄 → 𝑅), (𝑃 ∧ 𝑄)} ⊢ 𝑅

qui figure avant le signe introduisant le résultat.

s’exprime en fonction de l’implication.

𝑃 → (𝑄 → 𝑅) ⊢ (𝑃 ∧ 𝑄) → 𝑅

(𝑃 ∧ 𝑄) → 𝑅

on obtient:

est un

Déduction sous hypothèses

{𝑃 → (𝑄 → 𝑅), 𝑃 ∧ 𝑄}

1 − ℎ𝑦𝑝 𝑃 ∧ 𝑄 : (𝑃 ∧ 𝑄) → 𝑃 2 − 𝐴 4

3 − 𝑚𝑝𝑝 𝑠𝑢𝑟 1&2: {𝑃 ∧ 𝑄, (𝑃 ∧ 𝑄) → 𝑃} ⊢ 𝑃 * 𝑚𝑝𝑝: {𝐴, 𝐴 → 𝐵}⊢𝐵 𝑎𝑣𝑒𝑐 𝐴: 𝑃 ∧ 𝑄 𝑒𝑡 𝐵: 𝑃

4 − ℎ𝑦𝑝 𝑃 → (𝑄 → 𝑅) 5 − 𝑚𝑝𝑝 𝑠𝑢𝑟 3&4 : {𝑃, 𝑃 → (𝑄 → 𝑅)}⊢ 𝑄 → 𝑅 * : (𝑃 ∧ 𝑄) → 𝑄 6 − 𝐴 5

* 7 − 𝑚𝑝𝑝 𝑠𝑢𝑟 1&6 : {𝑃 ∧ 𝑄, (𝑃 ∧ 𝑄) → 𝑄} ⊢ 𝑄 8 − 𝑚𝑝𝑝 𝑠𝑢𝑟 5&7 : {𝑄, 𝑄 → 𝑅 }⊢𝑅 𝐶𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛: 𝑅

est un théorème.

}⊢(𝑃 ∧ ¬𝑄) → 𝑅

{ 𝑃 → (¬𝑄 ↔ (𝑅 ∨ 𝑆)) , ¬𝑆

4- Montrer que Cette démonstration est donnée sous la forme d’une déduction sous hypothèses avec un ensemble d’hypothèses contenant deux éléments On remarque en revanche que la formule du résultat de ce fait, on peut appliquer le TDD et ajouter une autre hypothèse à l'ensemble d’hypothèse donné: { 𝑃 → (¬𝑄 ↔ (𝑅 ∨ 𝑆)) , ¬𝑆 { 𝑃 → (¬𝑄 ↔ (𝑅 ∨ 𝑆)) , ¬𝑆 , 𝑃 ∧ ¬𝑄

. 𝑃 → (¬𝑄 ↔ (𝑅 ∨ 𝑆)) 𝑒𝑡 ¬𝑆

}⊢(𝑃 ∧ ¬𝑄) → 𝑅

est équivalent à

(𝑃 ∧ ¬𝑄) → 𝑅

}⊢ 𝑅

contient une implication.

Déduction sous hypothèses } 𝑃 → (¬𝑄 ↔ (𝑅 ∨ 𝑆)) , ¬𝑆 , 𝑃 ∧ ¬𝑄 {

; ℎ𝑦𝑝1: 𝑃 → (¬𝑄 ↔ (𝑅 ∨ 𝑆)) ℎ𝑦𝑝2: ¬𝑆 ℎ𝑦𝑝3: 𝑃 ∧ ¬𝑄

1 − ℎ𝑦𝑝 𝑃 ∧ ¬𝑄 2 − 𝐴4: (𝑃 ∧ ¬𝑄) → 𝑃

𝐴4: (𝐴 ∧ 𝐵) → 𝐴 𝑒𝑡 𝐴5 : (𝐴 ∧ 𝐵) → 𝐵: 𝑎𝑣𝑒𝑐 𝐴: 𝑃 𝑒𝑡 𝐵: ¬𝑄

3 − 𝑚𝑝𝑝 𝑠𝑢𝑟 1 & 2 𝑃 ∧ ¬𝑄, (𝑃 ∧ ¬𝑄) → 𝑃

{

}⊢𝑃 *

}⊢𝐵, 𝑎𝑣𝑒𝑐 𝐴: 𝑃 ∧ ¬𝑄 𝑒𝑡 𝐵: 𝑃

{

𝑚𝑝𝑝: 𝐴, 𝐴 → 𝐵 4 − ℎ𝑦𝑝𝑃 → (¬𝑄 ↔ (𝑅 ∨ 𝑆)) 5 − 𝑚𝑝𝑝 𝑠𝑢𝑟 3&4: 𝑃, 𝑃 → (¬𝑄 ↔ (𝑅 ∨ 𝑆)) 6 − 𝐴12: (¬𝑄 ↔ (𝑅 ∨ 𝑆)) → (¬𝑄 → (𝑅 ∨ 𝑆))

{

}⊢ ¬𝑄 ↔ (𝑅 ∨ 𝑆) *

𝐴12: (𝐴 ↔ 𝐵) → (𝐴 → 𝐵) ; 𝐴13: (𝐴 ↔ 𝐵) → (𝐵 → 𝐴) ; 𝐴: ¬𝑄 𝑒𝑡 𝐵: 𝑅 ∨ 𝑆

7 − 𝑚𝑝𝑝 𝑠𝑢𝑟 5&6: ¬𝑄 ↔ (𝑅 ∨ 𝑆), (¬𝑄 ↔ (𝑅 ∨ 𝑆)) → ((¬𝑄 → (𝑅 ∨ 𝑆))

{

* }⊢ ¬𝑄 → (𝑅 ∨ 𝑆)

𝑚𝑝𝑝: 𝐴, 𝐴 → 𝐵

{

}⊢𝐵, 𝑎𝑣𝑒𝑐 𝐴: ¬𝑄 ↔ (𝑅 ∨ 𝑆) 𝑒𝑡 𝐵: ¬𝑄 → (𝑅 ∨ 𝑆)

8 − ℎ𝑦𝑝 𝑃 ∧ ¬𝑄 9 − 𝐴5: (𝑃 ∧ ¬𝑄) → ¬𝑄 10 − 𝑚𝑝𝑝 𝑠𝑢𝑟 8&9 : 𝑃 ∧ ¬𝑄; (𝑃 ∧ ¬𝑄) → ¬𝑄 { { 11 − 𝑚𝑝𝑝 𝑠𝑢𝑟 7 & 10: ¬𝑄, ¬𝑄 → (𝑅 ∨ 𝑆) }⊢𝐵, 𝑎𝑣𝑒𝑐 𝐴: ¬𝑄 𝑒𝑡 𝐵: 𝑅 ∨ 𝑆 𝑚𝑝𝑝: 𝐴, 𝐴 → 𝐵

}⊢𝑅 ∨ 𝑆 *

}⊢ ¬𝑄

{ 12 − ℎ𝑦𝑝 ¬𝑆 13 − 𝑚𝑡𝑝 𝑠𝑢𝑟 11& 12: 𝑅 ∨ 𝑆, ¬𝑆

𝑚𝑡𝑝 𝐴 ∨ 𝐵, ¬𝐴

{

{ }⊢𝐵 𝑎𝑣𝑒𝑐 𝐴: 𝑆 𝑒𝑡 𝐵: 𝑅

}⊢𝑅

𝐶𝑜𝑛𝑐𝑙𝑢𝑠𝑖𝑜𝑛 : 𝑅

5- Prouver que la formule suivante est un théorème en utilisant une déduction naturelle (théorie de la démonstration) ( (𝑃 ∨ 𝑄

) → 𝑅) → (𝑅 → 𝑆) → ¬𝑆 → ¬𝑃

Il s’agit d’une démonstration d’implication donc le cas de figure d'application du théorème de la déduction: { ( (𝑃 ∨ 𝑄

( (𝑃 ∨ 𝑄 ) → 𝑅); 𝑅 → 𝑆; ¬𝑆

) → 𝑅) → (𝑅 → 𝑆) → ¬𝑆 → ¬𝑃

en appliquant 3 fois le TDD

est équivalente à

}⊢¬𝑃

) → 𝑅; 𝑅 → 𝑆; ¬𝑆 } ) → 𝑅

Déduction sous hypothèses 𝑃 ∨ 𝑄 ( { 1- ℎ𝑦𝑝 𝑃 ∨ 𝑄 ( 2- ℎ𝑦𝑝 𝑅 → 𝑆 3- Règle de la transitivité de l’implication sur 1&2: (remarque règle de la transitivité de l’implication 𝐴 → 𝐵; 𝐵 → 𝐶 { 4-ℎ𝑦𝑝 ¬𝑆 5- mtt sur 3&4: (remarque mtt 𝐴 → 𝐵; ¬𝐵 6- 𝐴 : (¬𝑃 ∧ ¬𝑄) → ¬𝑃 4

{ ( 𝑃 ∨ 𝑄 {

) → 𝑆; ¬𝑆

{ ( 𝑃 ∨ 𝑄

}⊢¬𝐴)

7- 𝑚𝑝𝑝 𝑠𝑢𝑟 5&6: ¬𝑃 ∧ ¬𝑄; (¬𝑃 ∧ ¬𝑄) → ¬𝑃 Conclusion : ¬𝑃

{

}⊢¬𝑃

* }⊢¬(𝑃 ∨ 𝑄) ¬(𝑃 ∨ 𝑄) ≡ ¬𝑃 ∧ ¬𝑄

) → 𝑅; 𝑅 → 𝑆

}⊢ 𝑃 ∨ 𝑄

(

* ) → 𝑆

}⊢𝐴 → 𝐶)

Théorie des démonstrations – Exercices et application du TDD