Prueba de tautología con coq

12

Actualmente tengo que aprender Coq y no sé cómo lidiar con un or:

Como ejemplo, tan simple como es, no veo cómo demostrar:

Theorem T0: x \/ ~x.

Realmente lo agradecería si alguien pudiera ayudarme.

Como referencia utilizo esta hoja de trucos .

También un ejemplo de una prueba que tengo en mente: aquí para doble negación:

Require Import Classical_Prop.

Parameters x: Prop.

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

logic coq Imagen
fuente

NNPPEl tipo es forall p:Prop, ~ ~ p -> p., así que es una trampa usarlo para probar T7. Cuando importas Classical_PropobtienesAxiom classic : forall P:Prop, P \/ ~ P.

Anton Trunov

Entonces, apply classic.resuelve tu objetivo T0.

Anton Trunov

14

No se puede probar en Coq "vainilla", porque se basa en una lógica intuicionista :

Desde una perspectiva de prueba teórica, la lógica intuicionista es una restricción de la lógica clásica en la que la ley de eliminación de la negación media y doble excluida no son reglas lógicas válidas.

Hay varias formas de lidiar con una situación como esta.

Introduzca la ley del medio excluido como un axioma:
```
Axiom excluded_middle : forall P:Prop, P \/ ~ P.
```
No hay más necesidad de probar nada después de este punto.
Introducir algún axioma equivalente a la ley del medio excluido y demostrar su equivalencia. Aquí hay solo algunos ejemplos.
- La eliminación de la doble negación es uno de esos axiomas:
```
Axiom dne : forall P:Prop, ~~P -> P.
```
- La ley de Peirce es otro ejemplo:
```
Axiom peirce : forall P Q:Prop, ((P -> Q) -> P) -> P.
```
- O use una de las leyes de De Morgan :
```
Axiom de_morgan_and : forall P Q:Prop, ~(~P /\ ~Q) -> P \/ Q.
```

Anton Trunov
fuente

Muchas gracias hasta ahora. No estoy familiarizado con todo lo que ha escrito, pero lo comprobaré. Utilizo el código y, de hecho, también obtuve una prueba de doble negación, la agregué a la descripción del problema para mayor claridad más adelante. Esperaba que hubiera una forma análoga para el problema mencionado anteriormente. Quizás debería haber incluido un ejemplo.

Imago

1

@AntonTrunov necesita agregar algunos paréntesis a su Axiom peirce: tal como está, no es la ley de Peirce (y de hecho es trivialpara probar).

gallais

@gallais ¡Gracias por ver eso! Fijo.

Anton Trunov

6

Como otros le informaron, su tautología no es una tautología a menos que asuma la lógica clásica. Pero como estás haciendo tautologías sobre valores de verdad decidibles, puedes usarlas en boollugar de Prop. Entonces su tautología sostiene:

Require Import Bool.

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

Andrej Bauer
fuente

Prueba de tautología con coq

Respuestas: