首页 > 其他分享 >1003 Reasoning(大模拟)

1003 Reasoning(大模拟)

时间:2023-08-15 20:22:41浏览次数:59  
标签:psi 公式 varphi 替换 lnot forall 1003 Reasoning 模拟

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\)

标签:psi,公式,varphi,替换,lnot,forall,1003,Reasoning,模拟
From: https://www.cnblogs.com/ClapEcho233/p/17632268.html

相关文章

  • HDU 5499(模拟)
    SDOITimeLimit:2000/1000MS(Java/Others)    MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):500    AcceptedSubmission(s):210ProblemDescriptionn(n≤100) peoplecomestotheSelectandthereis m(m≤50) people......
  • cf 583 B. Robot's Task(模拟)
    链接:http://codeforces.com/problemset/problem/583/B//求改变的方向次数//直接模拟题目是从1开始所以从左到右从右到左#include<stdio.h>#include<algorithm>usingnamespacestd;inta[1000+10];intvis[1000+10];intmain(){intn,t=0;scanf("%d",&n);......
  • Mysql中使用存储过程插入decimal和时间数据递增的模拟数据
    场景Mysql插入数据从指定选项中随机选择、插入时间从指定范围随机生成、Navicat使用存储过程模拟插入测试数据:https://blog.csdn.net/BADAO_LIUMANG_QIZHI/article/details/129179745在上面的基础上,如何使用存储过程构造坐标数据规律递增以及时间递增的模拟数据。表结构如下......
  • 8.14 模拟赛小结
    前言最喜欢的一集T1儒略历题意化简:给你一个长度为\(n\)的序列需要挑选\(4\)个数下标为\(A,B,C,D\),满足\(A<B<C<D\)\(A\timesB\timesC=D\)\(n\leq10^4\)这个很简单枚举\(C\)预处理\(A*B\)再枚举\(D\)时间复杂度\(O(n^2)\)能过Code#include<bits/stdc......
  • 2023-08-14 CSP-J模拟联考 游记
    8:00 赶到 FZ,9:00正式开考。开考前先洗了一把脸。9:00~9:15开T1,原本没有思路,但后来想到可以贪心,每次找到<n 的最大的斐波那契数。于是打了个斐波那契的表,就过了。9:15~10:00T2写了45分钟我是什么东西。一开始想法是把每一个字符的数量统计起来,如果相差<1就满足要求,否......
  • CSP模拟 21
    GetOnYourWay.木偶戏你看台上台下角色跟着反转大红的衣衫配上滑稽妆扮一唱一和多少人在围观乌鸦跟着鼓掌笑风水轮流转两语三言拉扯我的五感衣带要系紧不得有碍观瞻木偶提线怪事又成一桩美谈A.[CEOI2016]kangaroo神奇的DP,从未涉及的领域。观察题意,一......
  • PCIe卡设计方案:631-单路12Gsps 3G 带宽模拟信号源PCIe卡
     一、板卡概述    单路3G带宽模拟信号源卡由DA子卡和PCIe底板组成,二者通过标准FMC连接器互联,可以实现将PCIe总线数据转换为一路高速的模拟量输出。北京太速科技该板可广泛用于雷达、通信、光电领域的噪声信号、毛刺、脉冲信号模拟产生等领域。 二、性能指标 板卡功能......
  • 在安卓模拟器上如何实现HTTP代理自动切换
    在开发和测试应用程序时,有时需要在安卓模拟器上实现HTTP代理的自动切换以方便调试。本文将介绍如何在安卓模拟器上实现HTTP代理的自动切换。1.使用脚本文件使用脚本文件是一种实现HTTP代理自动切换的简单方法。以下是一个示例脚本文件:这个脚本定义了一个代理服务器地址和端口号数组......
  • 8.12模拟赛小结
    前言最ez的一集T1打工原题化简题意:有\(n\)个工作,每个工作有固定的工资截止时间你可以在\(1\)个时间单位内选择一项工作并完成它求最后最大工资思考:诶好像做个这个题?上次似乎讲过,用反悔贪心来做思路:首先讲原工作的截止时间从小到大排序然后每次遍历一个工作如果......
  • 使用夜神模拟器调试安卓apk
    安装夜神模拟器,安装后打开 进入模拟器的安装目录Nox.exe所在的目录 在此目录进入cmd  然后输入命令 1adbconnect127.0.0.1:62001 5.查看adbdevices这样就是连接成功了,就可以通过adb命令对夜神的模拟器进行编辑了 1PSD:\ProgramFiles\Nox\bin>cmd......