，标签对应书本
可能有错，仅供参考
f1．
2．
离散数学知识点
4
内容及范围主要来自ppt，标签对应书本
可能有错，仅供参考
f1．
2．
离散数学知识点
5
形式系统
1
内容及范围主要来自ppt，标签对应书本
可能有错，仅供参考
一个形式系统I由下面四个部分组成：
非空的字母表，记作AI
AI中符号构造的合式公式集，记作EI
3EI中一些特殊的公式组成的公理集，记作AXI
4推理规则集，记作RI
记IAIEIAXIRI其中AIEI是I的形式语言系统AXIRI是I的形式
2
演算系统
自然推理系统无公理即AXI
公理推理系统推出的结论是系统中的重言式称作定理【定义32】
P规则：在推导过程中可以随时添加前提。
T规则：在推导过程中可以引入公式S，它是由其前题的一个或多个公式借助重言、蕴含而得到
的。
推理（证明）：从前提A1A2Ak到结论B的推理是一个公式序列C1C2Cl其中Ci1il
是某个Aj或者可由序列中前面的公式应用推理规则得到并且ClB。
【定义33】
CP规则演绎定理：若RS，则RS其中为命题公式的集合。
个体词：用于表示命题中主语部分的符号或符号串。
个体常元
表示确指个体。
个体变元
表示不确指个体。
个体域个体变元的取值范围，常用D表示。
量词：限定个体数量特性的词。
全称量词：对所有的
存在量词：有些
谓词语言：用符号串表示个体、谓词、量词和命题
个体变元符号：x，y，z，…
个体常元符号：a，b，c，…
函数符号：f，g，…
谓词符号：P，Q，R，…
，

命题常元符号：
量词符号：，
连接词符号：
辅助符号：
）（
【定义41】
项1个体常元和变元是项；
2若f是
元函数符号，t1…t
是项，则ft1…t
是项；
3仅仅有限次使用1，2产生的符号串是项。【定义42】
原子公式若P是一个元谓词符号，t1…t
是项则Pt1…t
是原子公式。
【定义43】
合式公式：1原子公式是公式；
2若A是合式公式，则A是合式公式；
3若A，B是公式，则AB，AB，AB，AB是公式；
4若A是公式，x是变元，则xA，xA是公式；
5仅仅有限次使用１～４得到的符号串才是合式公式。【定义44】
设公式的一个子公式为xA或xA。则称：
指导变元：x是或的指导变元。
辖域：A是相应量词的辖域。
约束出现：辖域中x的一切出现，以及x中的x称为x在中的约束出现。
f自由出现：变元的非约束出现。
约束变元：约束出现的变元。
自r