Coq中矢列式~(exists x:D,~R x) |- (forall y:D,R y)的语法实现求助
Coq实现:从
~ (exists x:D, ~R x)推导forall y:D, R y的证明方案 我们需要落地的矢列式规则为:给定前提~ (exists x:D, ~ R x),推导得出结论forall y:D, R y,其中D为自定义论域类型,R为类型D上的一元谓词。
前置逻辑说明
该推导是经典逻辑下德摩根律在量词域的直接应用,在纯直觉主义逻辑框架下不可证,需要引入经典逻辑的排中律公理才能完成证明。证明核心逻辑是对任意论域元素用反证法构造矛盾,完成目标收敛。
完整可运行的Coq代码
(* 引入经典逻辑公理,支撑排中律的合法使用 *) Require Import Coq.Logic.Classical. Section Quantifier_DeMorgan_Proof. (* 声明自定义论域类型D *) Variable D : Type. (* 声明定义在D上的一元谓词R *) Variable R : D -> Prop. Theorem exists_neg_implies_forall_pos : ~ (exists x : D, ~ R x) -> forall y : D, R y. Proof. (* 引入全局前提,引入任意论域元素y作为待验证对象 *) intros H_no_neg_exists any_y. (* 基于排中律,对R any_y的真值做分支讨论 *) destruct (classic (R any_y)) as [Ry_hold | Ry_not_hold]. - (* 分支1:R any_y直接成立,匹配目标完成证明 *) exact Ry_hold. - (* 分支2:~R any_y成立,结合全局前提导出矛盾 *) apply False_rect. (* 以any_y为证据构造存在~R x的命题,触发前提的矛盾判断 *) apply H_no_neg_exists. exists any_y. exact Ry_not_hold. Qed. End Quantifier_DeMorgan_Proof.
证明步骤拆解
- 首先引入全局前提
H_no_neg_exists(即“不存在任意元素x满足~R x”),再引入论域中任意元素any_y,将全称量词的目标收敛为对该单个元素证明R any_y。 - 基于经典排中律拆分两种真值分支:
- 若
R any_y本身为真,无需额外推导即可直接作为目标结论完成证明。 - 若
~ R any_y为真,此时可以将any_y作为存在量词的有效证据,构造出“存在x满足~R x”的命题,该命题与全局前提直接矛盾;根据Coq的证明规则,矛盾可以导出任意结论,因此自然可以得到R any_y成立的结果。
- 若
补充说明:如果不引入经典逻辑公理,上述定理在Coq中会停留在证明到
forall y:D, ~~R y的阶段,无法完成双重否定的消除得到原结论。
内容的提问来源于stack exchange,提问作者MayJuneJuly
相关产品推荐
相关产品推荐

