Prouver la tautologie avec coq

12

Actuellement, je dois apprendre le Coq et je ne sais pas comment gérer un or:

Par exemple, aussi simple soit-il, je ne vois pas comment prouver:

Theorem T0: x \/ ~x.

J'apprécierais vraiment, si quelqu'un pouvait m'aider.

Pour référence, j'utilise cette feuille de triche .

Voici également un exemple de preuve que j'ai en tête: ici pour la double négation:

Require Import Classical_Prop.

Parameters x: Prop.

Theorem T7: (~~x) -> x. 
intro H. 
apply NNPP. 
exact H. 
Qed.

logic coq Imago
la source

NNPPLe type est forall p:Prop, ~ ~ p -> p., donc c'est de la triche de l'utiliser pour prouver T7. Lorsque vous importez, Classical_Propvous obtenezAxiom classic : forall P:Prop, P \/ ~ P.

Anton Trunov

Donc, apply classic.résout votre objectif T0.

Anton Trunov

14

Vous ne pouvez pas le prouver dans Coq "vanille", car il est basé sur une logique intuitionniste :

Du point de vue de la théorie de la preuve, la logique intuitionniste est une restriction de la logique classique dans laquelle la loi de l' élimination du milieu et de la double négation exclus ne sont pas des règles logiques valides.

Il existe plusieurs façons de gérer une situation comme celle-ci.

Introduire la loi du milieu exclu comme axiome:
```
Axiom excluded_middle : forall P:Prop, P \/ ~ P.
```
Il n'est plus nécessaire de prouver quoi que ce soit après ce point.
Introduisez un axiome équivalent à la loi du milieu exclu et prouvez leur équivalence. Voici quelques exemples.
- L'élimination de la double négation est l'un de ces axiomes:
```
Axiom dne : forall P:Prop, ~~P -> P.
```
- La loi de Peirce est un autre exemple:
```
Axiom peirce : forall P Q:Prop, ((P -> Q) -> P) -> P.
```
- Ou utilisez l'une des lois de De Morgan :
```
Axiom de_morgan_and : forall P Q:Prop, ~(~P /\ ~Q) -> P \/ Q.
```

Anton Trunov
la source

Merci beaucoup jusqu'à présent. Je ne connais pas tout ce que vous avez écrit, mais je vais vérifier. J'utilise le coqIde et en fait j'ai également obtenu une preuve de double négation, je l'ai ajouté à la description du problème pour plus de clarté plus tard. Je m'attendais à ce qu'il y ait une manière analogue pour le problème donné ci-dessus. J'aurais peut-être dû inclure un exemple.

Imago

1

@AntonTrunov, vous devez ajouter quelques parenthèses à votre Axiom peirce: en l'état, ce n'est pas la loi de Peirce (et c'est en fait trivialà prouver).

gallais

@gallais Merci d'avoir repéré ça! Fixé.

Anton Trunov

6

Comme d'autres vous l'ont informé, votre tautologie n'est pas une tautologie à moins que vous ne supposiez une logique classique. Mais puisque vous faites des tautologies sur des valeurs de vérité décidables, vous pouvez utiliser à la boolplace de Prop. Ensuite, votre tautologie tient:

Require Import Bool.

Lemma how_about_bool: forall (p : bool), Is_true (p || negb p).
Proof.
  now intros [|].
Qed.

Andrej Bauer
la source

Prouver la tautologie avec coq

Réponses: