1003 Reasoning(大模拟)

  • 来源:博客园
  • 时间:2023-08-18 12:12:41


(资料图)

translation

现有一个推理系统,有如下符号组成:

  • 圆括号:\((\) 和 \()\)
  • 逻辑连词:\(\lnot\) 和 \(\to\)
  • 全称量词:\(\forall\)
  • 变量:\(u-z\)
  • 常量:\(a-e\)
  • 函数:\(f-h\)
  • 谓词:\(P-T\)

这个推理系统还包括项(term)、公式(formula)、自由出现(free occurrence)和替换(replacement)等概念。基于这些概念,我们可以定义某个项 \(t\) 是否可以毫无冲突地替换某个变量 \(x\)。这是推理的基础之一,你想先解决这个问题。

项(term)的定义如下:

  • 所有的变量 \(v\) 是一个项
  • 所有的常量 \(c\) 是一个项
  • 如果 \(t_1,t_2,\dots,t_n\) 是一些项,\(f\) 是一个函数,则 \(f_{t_1,t_2,\dots,t_n}\) 是一个项

公式(formula)的定义如下:

  • 如果 \(t_1,t_2,\dots,t_n\) 是一些项,\(P\) 是一个谓词,则 \(P_{t_1,t_2,\dots,t_n}\) 是一个公式,而且这种公式被称为原子公式(atomic formula)
  • 如果 \(\varphi\) 和 \(\psi\) 都是公式,则 \((\lnot\varphi)\) 和 \((\varphi\to\psi)\) 都是公式
  • 如果 \(\varphi\) 是公式,\(v\) 是变量,则 \(\forall v\varphi\) 是公式

\(x\) 可以在 \(\varphi\) 中自由出现(free occurrence)的定义如下:

  • 如果 \(\varphi\) 是原子公式,\(x\) 可以在 \(\varphi\) 中自由出现当且仅当在 \(\varphi\) 中有 \(x\)(可以理解为字符 \(x\) 在字符串 \(\varphi\) 中出现)
  • 如果 \(\varphi\) 是 \((\lnot\psi)\),\(x\) 可以在 \(\varphi\) 中自由出现当且仅当 \(x\) 可以在 \(\psi\) 中自由出现
  • 如果 \(\varphi\) 是 \((\psi\to\gamma)\),\(x\) 可以在 \(\varphi\) 中自由出现当且仅当 \(x\) 可以在 \(\psi\) 中自由出现或在 \(\gamma\) 中自由出现
  • 如果 \(\varphi\) 是 \(\forall v\psi\),\(x\) 可以在 \(\varphi\) 中自由出现当且仅当 \(x\) 可以在 \(\psi\) 中自由出现且 \(x\neq v\)

对于所有公式 \(\varphi\),变量 \(x\),项 \(t\),替换(replacement)\(\varphi^x_t\) 的定义如下:

  • 如果 \(\varphi\) 是原子公式,那么 \(\varphi^x_t\) 是通过简单地将每个字符 \(x\) 替换为字符串 \(t\) 形成的表达式
  • 如果 \(\varphi\) 是 \((\lnot\psi)\),那么 \((\lnot\psi)^x_t=(\lnot\psi^x_t)\)
  • 如果 \(\varphi\) 是 \((\psi\to\gamma)\),那么 \((\psi\to\gamma)^x_t=(\psi^x_t\to\gamma^x_t)\)
  • 如果 \(\varphi\) 是 \(\forall y\psi\),那么 \((\forall y\psi)^x_t=\left\{\begin{array}{ll}\forall y(\psi^x_t) & & \text{if}\ x\neq y\\\forall y\psi & & \text{if}\ x=y\end{array}\right.\)

最后,无冲突替换的定义如下:

  • 如果 \(\varphi\) 是原子公式,那么 \(t\) 始终可以在 \(\varphi\) 中无冲突替换 \(x\)
  • 如果 \(\varphi\) 是 \((\lnot\psi)\),那么 \(t\) 在 \(\varphi\) 中可以无冲突替换 \(x\) 当且仅当 \(t\) 在 \(\psi\) 中可以无冲突替换 \(x\)
  • 如果 \(\varphi\) 是 \((\psi\to\gamma)\),那么 \(t\) 在 \(\varphi\) 中可以无冲突替换 \(x\) 当且仅当 \(t\) 在 \(\psi\) 和 \(\gamma\) 中都可以无冲突替换 \(x\)
  • 如果 \(\varphi\) 是 \(\forall y\psi\),那么 \(t\) 在 \(\varphi\) 中可以无冲突替换 \(x\) 当且仅当:
    • \(x\) 不能在 \(\varphi\) 中自由出现,或
    • \(y\) 不能在 \(t\) 中自由出现,且 \(t\) 在 \(\psi\) 中可以无冲突替换 \(x\)

关键词:

精彩推送

蔽匿(关于蔽匿简述)
网卡 2023/08/18
1003 Reasoning(大模拟)
企业 2023/08/18
冻的海虾怎么做好吃?
期货 2023/08/18
仁王2魂核怎么升级
财经 2023/08/18
房企爆雷的意思
观众 2023/08/18
pdm系统(pm系统)
雪佛兰 2023/08/18
墨绿墨红玉石
数据 2023/08/18

资讯播报

守住老百姓“救命钱”
滚动 2023/08/18
详解“选基导航仪”
汽车 2023/08/18
superoneclick(v1.9.1)
网络 2023/08/18
共济失调可以恢复吗
证券 2023/08/18
堡垒之夜&咒术回战等级一
雪佛兰 2023/08/18