Tautologie beweisen mit coq

12

Momentan muss ich Coq lernen und weiß nicht, wie ich damit umgehen soll or:

Als Beispiel, so einfach es ist, kann ich nicht beweisen:

Theorem T0: x \/ ~x.

Ich würde mich sehr freuen, wenn mir jemand helfen könnte.

Als Referenz verwende ich diesen Spickzettel .

Auch ein Beispiel für einen Beweis, an den ich denke: Hier für die doppelte Verneinung:

Require Import Classical_Prop.

Parameters x: Prop.

Theorem T7: (~~x) -> x. 
intro H. 
apply NNPP. 
exact H. 
Qed.
logic coq Imago
quelle
NNPP's Typ ist forall p:Prop, ~ ~ p -> p., also ist es Betrug, ihn zu benutzen, um zu beweisen T7. Wenn Sie importieren, erhalten Classical_PropSieAxiom classic : forall P:Prop, P \/ ~ P.
Anton Trunov
Also, apply classic.löst dein Ziel für T0.
Anton Trunov

Antworten:

14

Sie können es in "Vanilla" Coq nicht beweisen, da es auf der intuitionistischen Logik basiert :

Die intuitionistische Logik ist unter beweistheoretischen Gesichtspunkten eine Beschränkung der klassischen Logik, bei der das Gesetz der ausgeschlossenen mittleren und doppelten Verneinung keine gültigen logischen Regeln sind.

Es gibt verschiedene Möglichkeiten, mit einer solchen Situation umzugehen.

  • Führe das Gesetz der ausgeschlossenen Mitte als Axiom ein:

    Axiom excluded_middle : forall P:Prop, P \/ ~ P.

    Nach diesem Punkt besteht keine Notwendigkeit mehr, irgendetwas zu beweisen.

  • Führen Sie ein Axiom ein, das dem Gesetz der ausgeschlossenen Mitte entspricht, und beweisen Sie deren Gleichwertigkeit. Hier sind nur einige Beispiele.

    • Doppelte Verneinung ist ein solches Axiom:

      Axiom dne : forall P:Prop, ~~P -> P.

    • Peirces Gesetz ist ein weiteres Beispiel:

      Axiom peirce : forall P Q:Prop, ((P -> Q) -> P) -> P.

    • Oder verwenden Sie eines der Gesetze von De Morgan :

      Axiom de_morgan_and : forall P Q:Prop, ~(~P /\ ~Q) -> P \/ Q.
Anton Trunov
quelle
Vielen Dank bis jetzt. Ich bin nicht mit allem vertraut, was Sie geschrieben haben, werde es aber überprüfen. Ich benutze die CoqIde und habe tatsächlich auch einen Beweis für die doppelte Verneinung erhalten. Ich habe ihn später der Problembeschreibung hinzugefügt, um mehr Klarheit zu schaffen. Ich habe erwartet, dass es einen analogen Weg für das oben angegebene Problem gibt. Vielleicht hätte ich ein Beispiel hinzufügen sollen.
Imago
1
@AntonTrunov müssen Sie einige Klammern hinzufügen Axiom peirce: Wie es aussieht , ist es nicht Peirces Gesetz (und ist in der Tat trivialzu beweisen).
Gallais
@gallais Danke, dass du das gesehen hast! Fest.
Anton Trunov
6

Wie andere Ihnen mitgeteilt haben, ist Ihre Tautologie keine Tautologie, es sei denn, Sie gehen von klassischer Logik aus. Da Sie jedoch Tautologien zu entscheidenden Wahrheitswerten durchführen, können Sie boolstattdessen verwenden Prop. Dann gilt Ihre Tautologie:

Require Import Bool.

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