You need to enable JavaScript to run this app. Coq中矢列式~(exists x:D,~R x) |- (forall y:D,R y)的语法实现求助
优惠活动
大模型
产品
解决方案
定价
更多

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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.18 18:36:09