Corrigé CCINP 2026 Informatique MP — Problème 3 (Q29 à Q41) : Logique implicationnelle et loi de Peirce

Sujet officiel du concours CCINP, session 2026, épreuve Informatique MP. Corrigé rédigé par Ibrahim Alame.

Énoncé

Un système logique a une syntaxe, une sémantique et un système de déduction. Le calcul propositionnel $C_{P} = (S_{P}, M_{P}, D_{P})$ : formules bâties sur $⊤$ , $⊥$ et les variables avec $\land, \lor, \neg, \to$ ; sémantique des tables de vérité ; $D_{P}$ est la déduction naturelle (annexe du sujet : ax, affaiblissement aff $\frac{Γ ⊢ A}{Γ , B ⊢ A}$ , introductions et éliminations de $\to, \land, \lor, \neg$ , élimination de $⊥$ , raisonnement par l'absurde ra $\frac{Γ , \neg A ⊢ ⊥}{Γ ⊢ A}$ ).

Q29. Montrer par une table de vérité que $A \to B$ et $\neg A \lor B$ sont équivalentes.
Q30. $\neg A$ et $A \to ⊥$ sont-elles équivalentes ?
Q31. Table de vérité détaillée de $φ = ((A \to B) \to A) \to A$ ; que dire de $φ$ ?
Q32. Un système de connecteurs est complet si toute formule de $S_{P}$ équivaut à une formule n'utilisant que ces connecteurs. Montrer par induction que ${\neg, \to}$ est complet.

Le calcul implicationnel $C_{I} = (S_{I}, M_{I}, D_{I})$ : les formules de $S_{I}$ sont $⊥$ , $⊤$ , les variables et les $A \to B$ ; sémantique standard ; $D_{I}$ a pour seules règles :

Q33. Justifier que toute formule de $S_{P}$ équivaut à une formule de $S_{I}$ .
Q34. Prouver dans $D_{I}$ : (1) $A ⊢ (A \to B) \to B$ ; (2) $A \to B, B \to C ⊢ A \to C$ ; (3) $(A \to B) \to C, A \to C ⊢ C$ , avec l'instance $((C \to B) \to C) \to C$ de Peirce.
Q35. Qu'est-ce qu'une règle correcte ? Montrer que les règles de $D_{I}$ le sont.
Q36. Si $Γ ⊢ F$ est prouvable avec des règles correctes, quelle relation sémantique lie $Γ$ et $F$ ?
Q37. Par un argument sémantique, expliquer pourquoi ce prétendu arbre de preuve, où $Γ = {A \to B, C \to B}$ , est incorrect :

Une règle est dérivable dans un système si l'on peut construire sa conclusion avec les règles du système, en supposant ses prémisses prouvées.

Q38. Prouver $(A \to B) \to A, \neg A ⊢ A$ dans $D_{P}$ .
Q39. En déduire que la loi de Peirce est dérivable dans $D_{P}$ (on pourra utiliser ra).
Q40. $D$ est $D_{P}$ privé de ra et augmenté de la loi de Peirce. Montrer que ra est dérivable dans $D$ (instance $((A \to ⊥) \to A) \to A$ ).
Q41. Que peut-on dire de $D$ ?

Corrigé

Dans tout le corrigé, $v$ désigne une valuation et $v (F) \in {0, 1}$ la valeur de vérité de $F$ ; $A$ et $B$ étant des formules, la valeur d'une formule construite sur $A$ et $B$ ne dépend que du couple $(v (A), v (B))$ , qui décrit au plus les quatre lignes d'une table. Les contextes $Γ$ sont des ensembles finis de formules : leur ordre n'importe pas.

Q29.

$A$	$B$	$\neg A$	$A \to B$	$\neg A \lor B$
0	0	1	1	1
0	1	1	1	1
1	0	0	0	0
1	1	0	1	1

Les deux dernières colonnes coïncident : pour toute valuation, $v (A \to B) = v (\neg A \lor B)$ . Les deux formules sont équivalentes.

Q30. Oui. $v (A \to ⊥) = 1$ si et seulement si $v (A) = 0$ ou $v (⊥) = 1$ , c'est-à-dire, puisque $v (⊥) = 0$ , si et seulement si $v (A) = 0$ , donc si et seulement si $v (\neg A) = 1$ . La table n'a que deux lignes ( $B$ n'intervient pas) : pour $v (A) = 0$ , les deux formules valent 1 ; pour $v (A) = 1$ , elles valent 0.

100 % gratuit

La suite du corrigé est sur Adloun

Le corrigé rédigé en entier, question par question, et le tuteur pour poser des questions sur ce sujet.

Voir le corrigé complet, gratuitement

Inscription gratuite en 30 secondes (e-mail, nom d'utilisateur, mot de passe, classe ou profil), sans carte bancaire : arrivée directe sur le corrigé.

Toutes les parties de l'épreuve

Corrigé complet gratuit →