Library Coq.Logic.Decidable

Properties of decidable propositions




Definition decidable (P:Prop) := P \/ ~ P.




Theorem dec_not_not : forall P:Prop, decidable P -> (~ P -> False) -> P.

unfold decidable in |- *; tauto.

Qed.




Theorem dec_True : decidable True.

unfold decidable in |- *; auto.

Qed.




Theorem dec_False : decidable False.

unfold decidable, not in |- *; auto.

Qed.




Theorem dec_or :

 forall A B:Prop, decidable A -> decidable B -> decidable (A \/ B).

unfold decidable in |- *; tauto.

Qed.




Theorem dec_and :

 forall A B:Prop, decidable A -> decidable B -> decidable (A /\ B).

unfold decidable in |- *; tauto.

Qed.




Theorem dec_not : forall A:Prop, decidable A -> decidable (~ A).

unfold decidable in |- *; tauto.

Qed.




Theorem dec_imp :

 forall A B:Prop, decidable A -> decidable B -> decidable (A -> B).

unfold decidable in |- *; tauto.

Qed.




Theorem not_not : forall P:Prop, decidable P -> ~ ~ P -> P.

unfold decidable in |- *; tauto. Qed.




Theorem not_or : forall A B:Prop, ~ (A \/ B) -> ~ A /\ ~ B.

tauto. Qed.




Theorem not_and : forall A B:Prop, decidable A -> ~ (A /\ B) -> ~ A \/ ~ B.

unfold decidable in |- *; tauto. Qed.




Theorem not_imp : forall A B:Prop, decidable A -> ~ (A -> B) -> A /\ ~ B.

unfold decidable in |- *; tauto.

Qed.




Theorem imp_simp : forall A B:Prop, decidable A -> (A -> B) -> ~ A \/ B.

unfold decidable in |- *; tauto.

Qed.