数理逻辑 | Wyaaaattwho’s Blog

命题逻辑 Lead in 命题命题逻辑命题变元（项）逻辑运算符联结词联结词的顺序命题表达式命题常项命题变项合式公式命题表达式公式的层次真值表公式的赋值真值表公式的分类语意蕴含语义蕴含逻辑等价等值式 SAT 范式等值演算主合取与主析取范式命题逻辑的推理理论推理的结构形式自然演绎规则自然推理系统谓词逻辑基本概念命题逻辑的局限性个体词，谓词与量词谓词逻辑命题符号化谓词逻辑公式谓词逻辑等值演算等值式与置换规则自然演绎规则证明方法

命题逻辑

Lead in

👉

知识表示与推理 Knowledge Representation and Reasoning, KR&R

命题

命题是一个陈述语句，即一个陈述事实的句子

要么真，要么假

不能既真又假

命题逻辑

数理逻辑中研究推理的分支，推理由一系列陈述句组成

真值，假值

简单命题（原子命题）

复杂命题

命题变元（项）

常用小写字母表示命题变元，如： p, q, r

命题变元的取值范围为： {T, F}，{1, 0}

命题也可以表示为命题变元的形式，可以理解为该变元“已赋值”

p: 今天是周五（p=0） q: 2+2=4 （q =1）

逻辑运算符

联结词

否定

合取

析取

注意在自然语言下有排斥或和兼容或

蕴含

双蕴含

联结词的顺序

命题表达式

命题常项

简单命题是最基本的单位，其真值往往是确定的，我们定义为命题常元

命题变项

我们用可取1，可取0的命题来组成真值变换的命题，称为命题变项

合式公式

我们用逻辑联结词和圆括号将命题变元联结起来形成的符号串。

命题表达式

命题变元是命题表达式，如果定义为一个逻辑表达式的形式

公式的层次

真值表

公式的赋值

真值表

公式的分类

重言式，矛盾式，可满足式

语意蕴含

语义蕴含

💡

语句A语义蕴含语句B，当且仅当，给定任何一组真值指派，若A为真，则B为真。记为A|=B

形式定义：集合A蕴涵集合B，当且仅当在其中A中所有句子都为真的所有模型中，在B中的所有句子也是真的。在图表形式中，它看起来像：

逻辑等价

💡

如果p↔q是永真式，则复合命题p和q称为是逻辑等价（Logically equivalent）的。用记号p≡q表示p和q是逻辑等价的。

常用<=>代替≡

等值式

💡

若A，B始终具有相同的真值，即A↔B为重言式，则称A，B为等值式，记作A<=>B

通过真值表判断等值是件复杂的事，可以通过一些变换来证明

SAT

可满足性问题(Boolean Satisfiability Problem)，简称SAT问题，源于数理逻辑中经典命题逻辑关于公式的可满足性的概念，是理论计算机科学中一个重要的问题，也是第一个被证明的NP-complete问题。

范式

💡

简单合取式：由有限个文字组成的合取式叫简单合取式，命题变项及其否定都是文字

例如：

同理我们可以定义简单析取式

此时可以得出一个定理

💡

若我们有一个简单析取式A，若A为重言式，则A必包含某个命题p及其否定；

若我们有一个简单合取式A，若A为矛盾式，则A必包含某个命题p及其否定；

由此定义范式

💡

由有限个简单合取式析取组成的叫做析取范式，由有限个简单析取式合取组成的叫做合取范式，统称为范式。

我们可以得出以下定理：任何公式都有其等值的析取范式与合取范式。

通过以下步骤化简

消去蕴含联结词

消去否定符

使用分配律

等值演算

要在后面写出规则

主合取与主析取范式

💡

主析取范式含有n个不同的命题变项，则其极小项就必须含有n个不同的命题变项，且不允许一个文字及其否定同时存在。

在含有n个命题变项的简单合取式（简单析取式）中，若每个命题变项和它的否定式恰好出现一个且仅出现一次，而且命题变项或它的否定式按照下标从小到大或按照字典顺序排列，称这样的简单合取式（简单析取式）为极小项（极大项）

由于每个命题变项在极小项中以原形或否定形式出现且仅出现一次，因而n个命题变项共可以产生 2" 个不同的极小项. 每个极小项都有且仅有一个成真赋值.若极小项的成真赋值所对应的二进制数等于十进制数 i ，就将这个极小项记作 . 类似地， n个命题变项共可产生2” 个不同的极大项，每个极大项只有一个成假赋值，将其对应的十进制数 i 做极大项的下标，记作.

假设某个主析取范式含有p, q两个命题变项，则它的极小项最多有4种，分别为

对于上我们有下表

而且有以下定理

对于一个命题，有

由此可以知道由主析取范式推出主合取范式的办法

任何命题都有其对应的主析取范式与主合取范式，且唯一对应

我们还可以推断以下定理

任意两个极小项的合取必然为加，任意两个极大项的析取必然为真
所有极小项的析取必为真，所有极大项的合取必为假

我们做出如下规定：重言式的主合取范式为1；矛盾式的主析取范式为0

命题逻辑的推理理论

推理的结构形式

💡

也就是说，集合中默认是合取

💡

定理：推导出为有效的当且仅当为重言式，且将该式子称为推理的形式结构，其中前件又称为前提，后件又称为结论

在命题逻辑中，若蕴含式为重言式，我们可记作

📌

关于什么是推理：在实际应用中，证明推理正确和进行有效推理的基本方法是构造推理的证明，即构造一个从前提到结论的公式序列，序列中的每一个公式都是前提的有效结论

称永真的蕴涵式为推理定律，推理的一些重要定理

我们可以根据等值式置换的原理置换这些公式

自然演绎规则

下述规则也是自然演绎规则

自然推理系统

形式系统一般分为两类：一类是自然推理系统，它的特点是从任意给定的前提出发，应用系统中的推理规则进行推理演算，最后得到的命题公式是推理的结论（它是有效的结论，可能是重言式，也可能不是重式）. 另一类是公理推理系统，它只能从若干条给定的公理出发，应用系统中的推理规则进行推理演算，得到的结论是系统中的重言式，称为系统中的定理.

自然演绎来源自对共通于弗雷格、罗素和希尔伯特系统的判句公理化(希尔伯特演绎系统)的不满。这种公理化最著名使用是在罗素和怀特海的《数学原理》的数学论述中。在1926年由扬·武卡谢维奇在波兰发起的一系列研讨会提倡一种对逻辑的更加自然处理，斯坦尼斯瓦夫·亚希科夫斯基做了定义更自然的演绎的最早尝试，首先在1929年使用了一种图表表示法，并在1934年和1935年的一序列论文中更改了他的提议。

我们引入两种推理方法

附加前提证明法

归谬法

谓词逻辑

基本概念

命题逻辑的局限性

命题逻辑甚至无法判定一些基本的简单命题，例如：凡是偶数都能被二整除

为此，我们引入个体词、谓词和量词，以期达到表达出个体与总体的内在联系和数量关系，这就是一阶逻辑所研究的内容.一阶逻辑也称一阶谓词逻辑或谓词逻辑.

个体词，谓词与量词

个体词

个体词是指所研究对象中可以独立存在的具体的或抽象的客体.例如，小王，小李，中国，1，2，3等都可作为个体词
将表示具体或特定的客体的个体词称作个体常项，一般用小写英文字母a,b,c，…表示，而将表示抽象或泛指的个体词称为个体变项，常用x，y，z，⋯表示。并称个体变项的取值范围为个体域（或称论域）
个体域可以是有穷集合，例如，（1，2，3），｛a,b,c,d｝，{a，b，c，⋯，x，y，z}，…，也可以是无穷集合。例如，自然数集合 N=｛0,1,2，⋯}，实数集合R=｛z l z是实数）
有一个特殊的个体域，它是由宇宙间一切事物组成的，称全总个体域。本书在论述或推理中如无指明所采用的个体域，都是使用的全总个体域

谓词

谓词是用来刻画个体词性质及个体词之间相互关系的词
考虑下面4个命题（或命题变项）：（1）是无理数. （2）是有理数. （3）小王与小李同岁. （4）x与y具有关系L

在（1）中，是个体常项，“······是无理数”是谓词，记为F，并用表示（1）中命题
在（2）中，x是个体变项，”······是有理数”是谓词，记G，用表示（2）中命题
在（3）中，小王，小李都是个体常项，“⋯⋯与⋯⋯同岁”是谓词，记为H，则（3）中命题符号化形式为，其中，a：小王，b：小李
在（4）中，z，为两个个体变项，“⋯⋯与⋯⋯有关系L”是谓词，符号化为.

同个体词一样，谓词也有常项与变项之分.表示具体性质或关系的谓词称为谓词常项，表示抽象的或泛指的性质或关系的谓词称为谓词变项.无论是谓词常项或变项都用大写英文字母F，G，H，⋯表示，要根据上下文区分
更一般地，用表示含n（n≥1）个命题变项的n元谓词，n=1时，表示，具有性质P，n≥2时，表示具有关系P
实质上，n元谓词可以看成以个体域为定义域，以｛0，1｝为值域的n元函数或关系。它不是命题，要想使它成命题，必须用谓词常项取代F，用个体常项取代得命题或加量词（见下文）
有时将不带个体变项的谓词称为0元谓词，例如等都是0元谓词，当F,G,P为谓词常项时，0元谓词为命题。这样一来，命题逻辑中的命题均可以表示成0元谓词，因而可将命题看成特殊的谓词