一阶逻辑语言简记

vntlly / 2023-08-04 / 原文

命题

自然语言和逻辑语言相比具有极大的歧义性，如当笔者谈论“苹果”时，读者并不能知道这是水果还是手机，而逻辑因为其严谨性可以较大消除其歧义。

逻辑最基础的构件便是二极管般的【命题】（proposition），是指一个可判断真假的陈述句

显而易见的是命题的定义最重要的一个性质是能判断真假，将此真假性质称作【真值】，其中真值为True的命题称作【真命题】，真值为False的命题称作【假命题】

为了形式化命题，采用【命题变量】（即命题的内容不确定）来讨论命题形式上的架构，一般采用字母\(p,q,r...\)表示命题变量，而其真值也采用1、0表示真、假（这里用1表示真，0表示假）

命题的运算

命题的域只有\(\{0,1\}\)，为构建其运算，定义了一些常用的函数，一般将命题的运算符称作【联结词】，而参与命题的数量称作【元】或【目】

显然，假设有\(n\)元联结词，计数后有\(2^n\)种不同的联结词，下述常用的运算也被赋予了一些自然语言上的含义

■否定

其运算是关于真值的颠倒，语义上如其名表示否定，用\(￢p\)表示（也可能用\(\overline p、-p、!p、p'\)等方式表示）

下述表格称作【真值表】，其中第一行表示命题或命题运算后的复合命题，其下为真值以直观展示命题与运算后的情况

p	￢p
0	1
1	0

如“p：我喜欢苹果”的否定为

“￢p：我不喜欢苹果”

■合取

两命题全为真命题结果才为真命题，语义上表示为“且”，记作\(p~∧~q\)

如有命题

p：我喜欢可乐

q：我喜欢雪碧

复合命题p∧q：我喜欢可乐，并且我也喜欢雪碧

p	q	p∧q
0	0	0
0	1	0
1	0	0
1	1	1

■析取

命题存在真命题结果便为真命题，语义上表示为“兼或”，记作\(p~∨~q\)

如有命题

p：学过数学可以解决这道题

q：学过物理可以解决这道题

复合命题p∨q：学过数学或物理才能解决这道题

p	q	p∨q
0	0	0
0	1	1
1	0	1
1	1	1

■异或

两命题相异结果为真命题，语义上也表示为“或”，但这一或在日常语言中更常用，记作\(p~⊕~q\)

如有命题

p：我想买可乐

q：我想买雪碧

复合命题p⊕q：我想买瓶可乐，或者买瓶雪碧（此时自然语言上的或并不是析取意义上的或，我并不想都买）

p	q	p⊕q
0	0	0
0	1	1
1	0	1
1	1	0

■同或

两命题相同结果为真命题，电路、计算机中用得较多，记作\(p~⊙~q\)

p	q	p⊙q
0	0	1
0	1	0
1	0	0
1	1	1

■条件（蕴含）

记作\(p~→~q\)

推理中极其重要的运算，其中p称作前提、前件，q称作后件。推理上一般表示【如果p，则q】【p是q的充分条件】【q是p的必要条件】【q成立，除非￢p成立】

在条件运算符上进一步提出了一些新的定义，已知一个复合命题\(p→q\)，这也是几乎所有的数学问题的形式

那么其逆命题是指\(q→p\)

其否命题（或称反命题）是指\(￢p→￢q\)

其逆否命题是指\(￢q→￢p\)

p	q	p→q
0	0	1
0	1	1
1	0	0
1	1	1

■双条件（双蕴含）

记作\(p~←→~q\)，其等价于\(p→q~∧~q→p\)

一般表示为【p、q互为充要条件】【p，当且仅当q】

充分条件、必要条件的定义是在条件、双条件之上提出的，已知命题p、q

（1）如果p→q，那么就称p是q的充分条件，或称q是p的必要条件

（2）如果q→p，那么就称q是p的充分条件，或称p是q的必要条件

（3）如果（1）（2）都满足，那么就称p、q互为充要条件（指充分必要）

（4）如果（1）（2）都不满足，那么p、q是无关的，称作互为既不充分也不必要的

p	q	p←→q
0	0	1
0	1	0
1	0	0
1	1	1

■定义运算符的优先级

定义运算符的优先级是为了防止运算出现混淆，就像1+2×3，如果我们事先并不知道乘法优先级更高，显然是有可能视作(1+2)×3的

优先级只出现在了二元联结词上，也几乎不可能出现其他三元或更高元（除非你使用某种很新奇的写法）、一元上，因为这是我们语言上的一种简写导致的某种bug，优先级正是为了填补这种bug

在最开始便提到了这本质上是一种函数，如果我们用函数的视角来看，1+2×3实际上是\(+(1,×(2,3))\)，显然写成函数形式我们并不会错误地当成\(×(+(1,2),3)\)

但我们一般情况下不再使用函数那种形式化的写法而是采用了自然语言上处理后的写法。但自然语言处理后并非没有规律可循，比如一般情况下，更低元运算符的优先级是比更高级运算符的优先级要高的（括号例外且仅限于同一域的运算符）

在编程语言里会有特别多的运算符也有为处理语言bug的优先级表，而计算机依靠了图论（这里不过多说明）的知识去识别并将自然语言还原成原本函数形式的语言

目前所定义的运算符优先级如下

运算符	优先级
￢	1
∧	2
∨	3
→	4
←→	5

逻辑等价式

一般证明命题常常是比较复杂的命题等价式，即一个函数\(F(p,q,r,...)\)，而根据真值对其进行分类

（1）重言式（永真式，tautology），指无论原子命题的真值如何该复合命题真值都为1

（2）矛盾式（contradiction），指无论原子命题的真值如何该复合命题真值都为0

（3）可能式，即最终复合命题的真值无法确定，而由其原子命题组成

例如已知命题p，\(p∨￢p\)则为永真式，而\(p∨￢p\)则为矛盾式

（4）可满足性是指某个复合命题存在一种赋值情况使其为真的情况，即该命题为重言式或可能式。而其中可满足性命题的一个为真的赋值便称作其解。可满足性的概念是为了辨别某些问题是否能去解决而不是无法解决的。但判定可满足性的难点在于复合命题的赋值往往是巨量的，甚至超出千亿级的，而纯粹循环以此判定是否存在一种为真的赋值是很困难的，这一问题与算法复杂度相挂钩

（5）已知复合命题p、q，如果\(p←→q\)为重言式，则称p、q逻辑等价，一般记作\(p≡q\)（或\(p⇔q\)）

同一律

■\(p≡p∧1\)

■\(p≡p∨0\)

幂等律

■\(p≡p∧p\)

■\(p≡p∨p\)

支配律

■\(1≡p∨1\)

■\(0≡p∧0\)

矛盾律

■\(0≡p∧￢p\)

排中律

■\(1≡p∨￢p\)

双重否定律

■\(p≡￢￢p\)

交换律

■\(p∧q≡q∧p\)

■\(p∨q≡q∨p\)

⭐结合律

■\((p∧q)∧r≡p∧(q∧r)\)

■\((p∨q)∨r≡p∨(q∨r)\)

⭐吸收律

■\(p∧(p∨q)≡p\)

■\(p∨(p∧q)≡p\)

⭐分配律

■\(p∨(q∧r)≡(p∨q)∧(p∨r)\)

■\(p∧(q∨r)≡(p∧q)∨(p∧r)\)

⭐德摩根律

■\(￢(p∧q)≡￢p∨￢q\)

■\(￢(p∨q)≡￢p∧￢q\)

扩展的德摩根律

由于交换律，不管析取合取任意项都是有良好性质，因此定义

（1）\(∧_{i=1}^n~p_i≡p_1∧p_2∧...p_n\)

（2）\(∨_{i=1}^n~p_i≡p_1∨p_2∨...p_n\)

■\(￢(∧p_i)≡∨￢p_i\)

■\(￢(∨p_i)≡∧￢p_i\)

条件命题相关

■⭐等值式：\(p→q≡￢p∨q\)

■⭐逆否律：\(p→q≡￢q→￢p\)

■否定：\(￢(p→q)≡p∧￢q\)

■\(p∨q≡￢p→q\)

■\(p∧q≡￢(p→￢q)\)

■⭐输出律：\(p→(q→r)≡(p∧q)→r\)

■⭐归谬律：\((p→q)∧(p→￢q)≡￢p\)

■\((p→q)∧(p→r)≡p→(q∧r)\)（p能推出q，p也能推出r；即p能推出q、r）

■\((p→r)∧(q→r)≡(p∨q)→r\)（p能推出r，q也能推出r；即p或q都能推出r）

■\((p→q)∨(p→r)≡p→(q∨r)\)（p能推出q，或p能推出r；即p能推出q或r或都能推出）

■\((p→r)∨(q→r)≡(p∧q)→r\)（p能推出r，或q能推出r；即p、q都满足时也能推出r）

双条件命题相关

■⭐等值式：\(p←→q≡(p→q)∧(q→p)\)

■⭐否定等值式：\(p←→q≡￢p←→￢q\)

■否定：\(￢(p←→q)≡p←→￢q\)

■\(p←→q≡(p∧q)∨(￢p∧￢q)\)

上述大量等值式中笔者用⭐表示笔者认为比较重要的等值式

证明逻辑等价式：一般地虽然可以采用真值表，但对于一些复杂的逻辑等价式建议直接采用已有等价式去证明

如证明\(￢(∧p_i)≡∨￢p_i\)

\(￢∧_{i=1}^n~p_i \\≡￢(p_1∧∧_{i=2}^n~p_i) \\≡￢p_1∨￢∧_{i=2}^n~p_i \\≡... \\≡∨_{i=1}^n￢p_i\)

谓词逻辑

命题逻辑在可满足性那暴露了其问题，例如我想表述“我电脑上有一百个文件，有些删除了，有些留下了”，如果用命题逻辑去表述我需要设立一百个命题依次表述第X号文件是否被删除，以此联立，显然这种表述是繁琐的。谓词逻辑则在命题逻辑基础上引入了【量词】的概念，使得我可以更简洁地描述某对象性质的语义

（1）谓词是指命题所具有的一个性质，如\(x>2~∧~x∈N\)如果用命题逻辑表述我需要创建无穷多的命题以此表述在某个自然数上是否满足性质，形如

\(p_0:0是否满足0>2 \\ p_1:1是否满足1>2 \\ ...\)

这无疑是绝望的，而谓词逻辑则有赋予性质的能力

（2）已知涉及\(n\)个变量的命题函数\(P(x_1,x_2,..,x_n)\)其中\(x_i\)为变量，n元组\((x_1,x_2,...,x_n)\)即为一种赋值，而P称作n元谓词（或命题函数）

此时上述例子可以表述为\(P(x):x>2~∧~x∈N\)

（3）量词是为了量化谓词中的赋值，在谓词逻辑中有两个最基础的量词。全称量词，用【\(∀\)】符号表示，表示对于某个谓词任意的赋值都使其为真\(∀xP(x)\)。存在量词，用【\(∃\)】符号表示，表示对于某个谓词存在一个赋值使其为真\(∃xP(x)\)

（4）任意、存在这两种量词并非是新概念，而是基于谓词结构和析取合取做的一种范式。其定义满足等式

■ \(∀xP(x)≡∧P(x_i)\)

■ \(∃xP(x)≡∨P(x_i)\)

（5）量词的优先级最高，如\(∀xP(x)∧Q\)是指\((∀xP(x))∧Q\)

（6）当量词作用于变量时称作该变量被【绑定】，而被绑定的变量是【约束变量】，未被绑定的变量是【自由变量】。如\(∀xP(x,y)∧∃xQ(x)\)，其中P谓词的y是自由的，x是被约束的；Q谓词的x虽然也是约束的但完全不同于第一个量词，可以随意替换为其他字母

谓词逻辑在自然语言的转换

与命题逻辑不同的是，谓词逻辑在转换自然语言一般需要遵守固定格式

■ \(∀x(P(x)→A(x))\)

如“书店里所有的书价格都20以上”其中量词需要绑定的是“书”，首先需要P命题表述绑定变量x为书店里的书，然后A去描述性质。不能使用\(∀x(P(x)∧A(x))\)，否则涵义变成了所有书都是书店里的书而且价格都20以上

■ \(∃x(P(x)∧A(x))\)

如“书店里有本书价格100以上”。如果表示为\(∃x(P(x)→A(x))\)涵义就包括了x不是书店里的书价格也全都100以上

受限量词

对于上面的语言专门你可能注意到了一个问题，我首先需要描述量词的性质其次才能描述它的本体命题\(A(x)\)，它的问题是在于约束变量虽然被量词约束，但它的域并未作限制，因此我需要一个命题\(P(x)\)去描述变量\(x\)的域。这里引入一种新的简写方法——【受限量词】，是指域被限制的变量，它一般这样表示

■ \(∀x∈CA(x)\)

■ \(∃x∈CA(x)\)

通过引入域表明约束变量被限制在\(C\)中，它本质上是逻辑等价上面两种范式转换的

■ \(∀x∈CA(x)≡∀x(x∈C→A(x))\)

■ \(∃x∈CA(x)≡∃x(x∈C∧A(x))\)

受限量词是非常常用的，如微积分对于极限的定义

用\(\lim \limits_{x→a}f(x)=L\)表示\(∀ε>0∃δ>0∀x(0<|x-a|<δ→|f(x)-L|<ε)\)

其中\(ε、δ\)就是受限量词，如果要展开整体式子是更加复杂的

嵌套量词的规则

上述微积分定义的例子其实涉及到了嵌套量词，它是指一组量词同时作用于某个命题的情况，它一般分为四种情况

■ \(∀x∀yP(x,y)\)表示任意x任意y满足P

■ \(∀x∃yP(x,y)\)表示任意x，使得存在y满足P

■ \(∃x∀yP(x,y)\)表示存在x，使得任意y满足P

■ \(∃x∃yP(x,y)\)表示存在x存在y满足P

其中它满足同量词下的交换律，但像上述二三就无法交换是完全不同的含义

■ \(∀x∀yP(x,y)≡∀y∀xP(x,y)\)

■ \(∃x∃yP(x,y)≡∃y∃xP(x,y)\)

例如：\(∀a∀b∃c∃d∃e∀f∀g\)其中ab一组cde一组fg一组，每组内的量词都是可以任意交换的但不能将任意存在交互，它可转换成\(∀b∀a∃d∃e∃c∀f∀g\)

唯一量词

在数学证明中往往有一类证明是【唯一性】，任意量词、存在量词并不能直接地表示，但可以构造性地定义唯一量词，一般记作【\(∃!\)】或【\(∃_1\)】

■ \(∃!xP(x)≡∃x∀y(P(y)←→x=y)\)

■ \(∃!x∈CP(x)≡∃x∀y∈C(P(y)←→x=y)\)

一阶逻辑中的逻辑等价式

消除量词

备注：仅限于有限域，无限涉及到是否可数的问题

■ \(∀xP(x)≡∧P(x_i)\)

■ \(∃xP(x)≡∨P(x_i)\)

量词的德摩根律

■ \(￢∀xA(x)≡∃x￢A(x)\)

■ \(￢∃xA(x)≡∀x￢A(x)\)

量词作用域的伸缩

■ \(∀x(A(x)∧B)≡∀xA(x)∧B\)

■ \(∃x(A(x)∧B)≡∃xA(x)∧B\)

■ \(∀x(A(x)∨B)≡∀xA(x)∨B\)

■ \(∃x(A(x)∨B)≡∃xA(x)∨B\)

■ \(∀x(A(x)→B)≡∃xA(x)→B\)

■ \(∃x(A(x)→B)≡∃xA(x)→B\)

■ \(∀x(B→A(x))≡B→∀xA(x)\)

■ \(∃x(B→A(x))≡B→∃xA(x)\)

嵌套量词顺序（略）

分配律

■ \(∀x(A(x)∧B(x))≡∀xA(x)∧∀xB(x)\)

■ \(∃x(A(x)∨B(x))≡∃xA(x)∨∃xB(x)\)

只要结合消除量词和之前的逻辑等价式即可证明

例：证明 \(∃x(A(x)∧B)≡∃xA(x)∧B\)

\(∃x(A(x)∧B)\)

\(≡∨(A(x)∧B)\)（消除量词）

\(≡(A(k_0)∧B)∨(A(k_1)∧B)∨...\)

\(≡【[(A(k_0)∧B)∨A(k_1)]∧[(A(k_0)∧B)∨B]】∨...\)（分配律）

\(≡【[(A(k_0)∧B)∨A(k_1)]∧B】∨...\)（第二式满足吸收律）

\(≡(A(k_0)∨A(k_1))∧(A(k_1)∨B)∧B∧...\)（再次分配律）

\(≡(A(k_0)∨A(k_1))∧B∧...\)（再次吸收律）

\(≡...\)

\(≡∨A(x)∧B\)

\(≡∃xA(x)∧B\)（再转回量词）

推理、CNF/DNF

所谓证明是指在给定前提（premise）且前提是真实性的情况下去推理出的有效性（valid）结论的结构，即前提→推理规则→结论的结构。

有效推理定义：\(∧p_i⇒q\)（备注，【\(⇒\)】符号同【\(→\)】，但以便区分推理和条件运算），而\(p_i\)为一组给定的前提，而\(q\)则是结论，若\(∧p_i⇒q\)为重言式则称是有效推理。但推理更关心的是它的模式，而不在意前提正确与否，也因此如果引入错误的前提套入推理规则可能会得到非常荒谬的结果。只有当所有前提都是真命题时，这时结论才为真命题，此时才能称这是【有效论证】。谬误或者说是诡辩，这些通常只犯了一个错误——前提为假命题。推理和证明的区别在于推理只关心结构，而证明需要带入前提，其中必须保证前提是真命题，否则会变得极其荒谬。例如“你不结婚没有孩子怎么办，你不结婚以后你养老怎么办，你应该早点结婚”

一般一个论证的通常是如下形式

\(p_1 \\ p_2 \\ ... \\ —— \\ q\)

范式：是指命题满足某种规则的形式，为的是将各种复杂形式的运算式以某种规则变得更加规范化以便作进一步地处理。范式如其名隐含的一个定理是对于任意的一个命题必然存在相等价的范式。如推理的前提是一种命题的合取形式，这也可以看成是一种范式（但不是下面所说的CNF）

这里首先要引入合取范式（CNF，Conjunctive Normal Form），这里不先对CNF和下面要讲的DNF作严格定义，简单来说就是一种合取运算为主析取、非运算为辅的形式。另外的也同样有析取范式（DNF，Disjunctive Normal Form）

定义：

（1）文字：已知命题\(p\)，则\(p、￢p\)统称为文字

（2）简单合取式：文字的合取运算称为是简单合取式，如\(p_1∧￢p_2∧p_3\)是简单合取式

（3）简单析取式：文字的析取运算称为是简单析取式，如\(p_1∨p_2∨￢p_3\)是简单析取式

（4）CNF：简单析取式的合取运算称为是CNF，如\(p_1∧(p_3∨￢p_5)∧(￢p_2∨￢p_3)\)是CNF

（5）DNF：简单合取式的析取运算称为是DNF

CNF/DNF范式的算法：

首先根据定义来说它只能包含析取、合取、非三种运算

（1）共同的步骤，将这三种运算以外其他所有运算转换为这三种运算，如\(p→q\)与\(￢p∨q\)等价以此转换

（2）共同的步骤，非运算不能运用于复杂的复合命题中，如\(￢￢p、￢(￢p∨q)、￢(p∧￢q∧r)\)等形式，需要用双重否定律、德摩根律进行简化（内移非运算）

（3）共同的步骤，简单析取式、简单合取式由于基础单位是文字，因此不能是复合命题、文字之间的析取/合取，如\(p∧￢(q∨(￢r∧s)∧t)\)。由于第一步将其他运算进行转换了也因此常常是析取、合取、非的嵌套形式，需要使用双重否定律、分配律将嵌套形式的运算“扁平化”

（4）CNF中不能出现合取范式的形式，DNF中不能出现析取范式的形式，因此需要采用分配律化为统一的形式（可以关注到分配律前后也是一次析取合取的转换过程，也因此CNF、DNF可以相互转换）

例：将\((p→q)←→r\)转为CNF、DNF的形式

\(≡(￢p∨q)←→r\)

\(≡((￢p∨q)→r)∧(r→(￢p∨q))\)

\(≡(￢(￢p∨q)∨r)∧(￢r∨￢p∨q)\)（转换运算）

\(≡((p∧￢q)∨r)∧(￢r∨￢p∨q)\)（德摩根律将非运算仅作用于文字）

\(≡(p∨r)∧(￢q∨r)∧(￢r∨￢p∨q)\)（分配律，扁平化）

这里实际上已经得出了CNF形式，对于DNF的形式可以用分配律转换，但分配律的运算实际上很复杂，这里介绍另外两种范式，以此进行更快速的转换

PCNF/PDNF

无论是CNF还是DNF首先观察到的是在不考虑交换律的情况下CNF、DNF并不唯一，如\((p∨r)∧(￢q∨r)∧(￢r∨￢p∨q)\)是与\((p∨r)∧(￢p∨￢q∨r)∧(￢r∨￢p∨q)\)等价的，因此为了追求范式的唯一性，通过新的概念【极小项】【极大项】去解决

（1）极小项：给定一些命题变量，包含所有命题变量的简单合取式称作是极小项，例子详见极大项

（2）极大项：给定一些命题变量，包含所有命题变量的简单析取式称作是极大项。如上述例子中\(p∨r\)显然不是极大项因为还有\(q\)，而\(￢r∨￢p∨q\)是极大项

（1）主合取范式（PCNF，Principal CNF），极大项的合取式且是唯一性的（唯一性见下述不严谨的说明）

（2）主析取范式（PDNF，Principal DNF），极小项的析取式且是唯一性的

要说明PCNF/PDNF相比于CNF/DNF是唯一性的，要以非极小项/非极大项向极小项/极大项的转变来解释

这里以\(p∨r\)为例

（1）我们可以使用同一律进行一种拓展，等价于\(p∨r∨0\)

（2）而0我们可以用排中律、矛盾律进行进一步拓展，等价于\(p∨r∨(q∧￢q)\)

（3）采用分配律，等价于\((p∨r∨q)∧(q∨r∨￢q)\)由此会发现将这样一个非极小项/非极大项转变为了极小项/极大项，而极小项/极大项你发现不了进一步转变的可能性，以此极小项、极大项的一种最为基础的元素，所谓的PCNF/PDNF便是基础元素的复合，而CNF/DNF并不完全由基础元素复合，而是复合元素、基础元素的复合

二进制转变：如果给定了N个命题变量，值得注意的是由于文字只存在两种情况\(p、￢p\)因此极小项/极大项只可能有\(2^N\)种情况。以给定三种变量情况你会发现一种规律

注：成真赋值是指对于给定公式下为永真式的一种赋值，成假赋值是指对于给定公式下为永假式的一种赋值，由于析取式、合取式的良好性质，极大项（简单析取式）的成假赋值是唯一性的，极小项（简单合取式）的成真赋值是唯一性的

极小项	成真赋值	极大项	成假赋值
￢p∧￢q∧￢r	000（指p为0，q为0，r为0）	p∨q∨r	111
￢p∧￢q∧r	001	p∨q∨￢r	110
￢p∧q∧￢r	010	p∨￢q∨r	101
￢p∧q∧r	011	p∨￢q∨￢r	100
p∧￢q∧￢r	100	￢p∨q∨r	011
p∧￢q∧r	101	￢p∨q∨￢r	010
p∧q∧￢r	110	￢p∨￢q∨r	001
p∧q∧r	111	￢p∨￢q∨￢r	000

同一赋值对于极小项、极大项都是完全相反的，如\(p∨q∨￢r\)和\(p∧q∧￢r\)

其次呈现出了可二进制编码的关系，以\((p∨r)∧(￢q∨r)∧(￢r∨￢p∨q)\)为例，会发现所谓的PCNF是一种罗列满足成真赋值的情况，即001、010、101、111

这里用字母【\(m\)】表示极小项，字母【\(M\)】表示极大项，因此这个例子的PCNF实际上是\(M_{001}∧M_{010}∧M_{101}∧M_{111}\)，而我们再将成真/成假赋值的二进制序列转成十进制便可进一步简写为\(M_{1}∧M_{2}∧M_{5}∧M_{7}\)。由于笔者并未介绍布尔代数，实际上布尔代数基本和命题逻辑类似，布尔代数中会将【∧】当作乘法【×】，【∨】当作加法【+】。进一步地简写方法便是采用累乘累加的记法，即\(∏(1,2,5,7)\)

简单来说，PCNF就是\(∏(k_0,...,k_n)\)的一种形式，而PDNF是\(∑(k_0,...,k_n)\)的一种形式（同理也有\(m_i∨...∨m_k\)的记法）

PCNF、PDNF的转换：PCNF、PDNF有着相当简洁的定理进行转换，给定N个变量和一个复合命题，那么对应的PCNF的项的十进制值在\(0\sim 2^{N-1}\)的范围内，而对应的PDNF为剩余的十进制值。（由极小项极大项的定理可得，这里不罗列其相关定理）如该例的\(∏(1,2,5,7)\)等价于\(∏(0,3,4,6)\)

主范式的算法：

（1）得到CNF或DNF

（2）根据得到的范式通过同一律→排中律、矛盾律→分配律将非极小也非极大项转为极小项极大项

（3）PCNF、PDNF相互转换

一般来说得到CNF直接罗列二进制序列即可，如\((p∨r)∧(￢q∨r)∧(￢r∨￢p∨q)\)这里我按照p、q、r的顺序二进制序列化，只需要参考每一简单析取式/简单合取式即可。如\(p∨r\)会记作1x1，其中x就是代表变量，而变量记作1，如果是变量的否定形式就记作0，以此可以记下1x1、x01、010而有x则分成0、1情况，这里便可以分成101、111、001（、101重复）、010，然后根据序列直接写出PCNF即可。

类似地，如pqrs有一项是1x0x那么有两处x最终会有1000、1001、1100、1101四种情况

逻辑函数化简

PCNF/PDNF向CNF/DNF的逆转换是否有意义？答案是肯定的，它经常用于数字电路中，可以将一项看成需要一个元器件，PCNF/PDNF虽然在理论上是一种唯一性的范式，但它罗列出了所有项，而CNF以上一例为例将101、111简写为了1x1，这可以理解为你原本需要两个电路元器件变成了只需要一个。这里问题就变成如何找到项最少的CNF/DNF

化简方法一般采用公式、卡诺图（格雷码）等方法，由于本篇定位，这里不介绍卡诺图方法

一般采用如下化简公式即可化简

■并项：\((A∧B)∨(A∧￢B)≡A\)

■吸收律（略）

■配项消项：\((A∧B)∨(￢A∧C)∨(B∧C)≡(A∧B)∨(￢A∧C)\)

注：从左到右是消项，从右到左是配项，关键在于找到两项内含变量和其否定形式，以此可以消除多余的项或是增加一项

命题推理规则

由于推理的前提是一种命题的合取，因此，在这里不再特意写【∧】而是写成【,】，除非∧作为项内的运算符

■前提引入：推理过程中可随时引入前提

■结论引用：推理出的结论可随时引用

■代入规则：对于重言式可用1替换

■置换规则：推理过程的子式可用等价式替换

■条件证明规则：若证\(p_1⇒p_2→p_3\)可证\(p_1,p_2⇒p_3\)，反之亦然

（证明，\(p_1⇒p_2→p_3≡￢p_1∨￢p_2∨p_3≡(p_1∧p_2)→p_3\)）

■假言推理（分离规则）：\(p,(p→q)⇒q\)

这是非常自然的模式，如果p正确而且p能推出q，那么q也正确

■拒取式：\(￢q,(p→q)⇒￢p\)

这是反证法，通过假设q不正确以此看待p→q，如果p→q正确最终只会推得矛盾￢p

■假言三段论：\((p→q),(q→r)⇒p→r\)

很经典的亚里士多德三段论

■析取三段论：\((p∨q),￢p⇒q\)

例如“这件事要么你干的（p）要么他干的（q），既然不是他干的（￢q），那肯定是你干的了（p）”

■附加律：\(p⇒p∨q\)

例如已知“韩国声称发现了室温超导材料”，可以附加为“p：韩国声称发现了室温超导材料，q：这可能是正确的，r：也可能是错误的，s：或者对错参半”

■化简：\(p,q⇒p\)

例如“他是凶手（p）因为地上有他的指纹（q）而且有作案动机（r），所以他是凶手（p）”

■合取：\(p,q⇒p∧q\)

例如“他是凶手（p）因为地上有他的指纹（q）而且有作案动机（r），他不仅是凶手（p）还有作案动机（r）”

■归结：\((p∨q),(￢p∨r)⇒q∨r\)（该规则之后会重点说明）

二难原理

数学证明中一般不用，详细参考【二难推理】【假言选言推理】，二难原理属于其中最简单的形式。假言选言推理是指结合多个假言推理（条件式）和选言推理（析取式）组合而成的推理。二难推理简单说因为两个假言推理和选言推理导致了最终难以抉择的两难处境。假言选言推理的基本规则是对前件肯定或对后件进行否定，其中对前件肯定的形式就是构造性的，对后件进行否定就是破坏性的。

■简单构造性二难：\(p→r,q→r,p∨q⇒r\)

电车难题，我换轨道（p）会杀人（r），我不换轨道（￢q）也会杀人（r），最终能推导我都会杀人（r），所以我选p还是￢p。由于p、q选择了特殊形式符合排中律，因此也有观点表明这是误用了排中律

■复杂构造性二难：\(p→q,r→s,p∨r⇒s∨q\)

选择困难症，如果我选A卡（p）我的战斗力能提升很多（q），如果我选B卡（r）我也能提高卡组运转能力（s），所以我该选什么？

■简单破坏性二难：\(p→q,p→r,￢q∨￢r⇒￢p\)

你不努力工作（p）怎么赚钱养家（q），你不努力工作怎么为公司做贡献（r），所以你应该努力工作

■复杂破坏性二难：\(p→q,r→s,￢q∨￢s⇒￢p∨￢r\)

量词推理规则

与联结词相关的蕴含式

■ \(∀xA(x)∨∀xB(x)⇒∀x(A(x)∨B(x))\)

■ \(∃x(A(x)∧B(x))⇒∃xA(x)∧∃xB(x)\)

■ \(∀x(A(x)→B(x))⇒∀xA(x)→∀xB(x)\)

■ \(∀x(A(x)←→B(x))⇒∀xA(x)←→∀xB(x)\)

量词消去/引入

■全称实例（US）：\(∀xA(x)⇒A(c)\)（c是域内的个体常项）

■全称引入(UG)：\(A(c)⇒∀xA(x)\)（c是域内任意一值且均满足命题A）

■存在实例(ES)：\(∃xA(x)⇒A(c)\)（c是域内的个体常项）

■存在引入(EG)：\(A(c)⇒∃xA(x)\)（c是域内某一值且满足命题A）

基本证明方法

定义：

（1）公理：人们普遍公认地认为一些命题，因为这些无法证明，但相信是真命题的命题称作是公理。《几何原本》中还区分出了【公设】特指尺规作图的公理系统

（2）假设：同公理暂时无法证明的命题但假设其为真

（3）定理：从公理系统通过推理规则得到的真命题；引理（推论），从定理进一步得到的真命题但通常引理在语义上被描述为次一级不是太重要的定理

（4）定义：是指对一种性质的描述或者说是简记

■直接证明法，前提\(p≡1\)通过一些定理得到\(q≡1\)此时即证\(p→q\)（适用条件命题）

■反证法，特别常用的一类证明方法，原理即逆证明否命题\(￢q→￢p\)为真因为其与\(p→q\)等价，在\(￢q≡1\)的前提下若能通过定理得到\(￢p≡1\)即证（适用条件命题）

■空证明，对于一个证明\(p→q\)如果\(p≡0\)能立马得到\(p→q\)是真命题，这一般是用在特例上去证明。如“若n>0，则2n>0”，显然能得知P(-1)为真（适用条件命题）

■平凡证明，对于一个证明\(p→q\)如果\(q≡1\)那么根据真值表\(p→q\)也是成立的无论\(p\)是否为真（适用条件命题）

■归谬法，相比于反证法其结构更加大。Ⅰ，若要证\(p→q\)，可以先假定\(p≡1,￢q≡1\)，如果此时通过一些定理证明了\(￢p≡1\)即\(￢q→￢p\)成立，那么就构成了\(￢q→(p∧￢p)\)，而后面的\((p∧￢p)≡0\)即证\(q≡1\)，满足\(p→q\)，这通常也被认为是“反证法”，但相比于反证法多了一个\(q≡1\)的前提，而归谬法的变种更多。Ⅱ，若要证\(p→q\)，同样假定\(p≡1,￢q≡1\)，但此时用直接证明，\(p→q\)因为此时也满足\(p→￢q\)就同样能将直接证明改写为归谬证明。Ⅲ，若要证\(p\)，可以假定存在一个命题\(r\)，而证明了\(p→(r∧￢r)≡1\)则证\(p≡1\)（适用条件命题、单命题）

■等价证明，即证明充分必要条件，需要从两个方面证明，将等价式转为条件式\(p←→q≡(p→q)∧(q→p)\)（适用等价命题）

■反例证明法，证明\(∀x∈C,P(x)\)不成立，那么只要找到一个反例不满足\(P(x)\)即可，形式化表述为\(￢∀xP(x)←→1≡∃x￢P(x)←→0\)（适用单命题）

■穷举证明法，简单来说列举所有可能情况，如果都满足就证明成功了，这种证明方法的关键在于（1）穷举只能是有限情况，哪怕是计算机超强算力也无法穷尽无限（2）穷举必须覆盖所有情况。不过无限情况的穷举也未必不可，例如按照费马的猜测，费马数\(F_n=2^{2^n}+1,n∈N_+\)必然是素数，然而第六个数\(F_5\)不是素数，因此在穷举过程中如果发现反例即宣告是不成立的（适用单命题）

■存在性证明（Existence Proof）

存在性最简单的证明是一种构造性（constructive）的证明，如上述的费马数，因为我简单计算了\(F_0\)是素数，因此我可以说存在费马数是素数

非构造性（nonconstructive）的证明和反例证明法的原理相同，\(∃xP(x)←→1≡∀x￢P(x)←→0\)，即任意值都不满足性质\(P\)是假命题，此时转换成了证明单命题，那么通过归谬法、穷举或反例就能证明。而相比于直接构造性的说明更有说服力，就比如证明存在费马数是素数不先说明\(F_0\)而是先假设不存在然后再找反例

■唯一性证明（Uniqueness Proof）

数学证明中同样存在了大量的唯一性证明，它包含了两部分

1.证明存在性

2.证明唯一性

它首先要依托于存在性的证明，其次根据之前唯一量词的定义\(∃!xP(x)≡∃x∀y(P(y)←→x=y)\)

需要假设两个元素\(x、y\)满足\(P(x),P(y)\)然后判定是否满足\(x=y\)如果满足，唯一性证毕

Peano公理系统与数学归纳法

皮亚诺（Peano）提出了自然数的公理系统，只有五条简单的规则。考虑到读者，这里不采用形式化以及集合论的表述

（1）0是自然数

（2）如果\(x\)是自然数，那么\(x+1\)也是自然数

前两条其实已经定性了自然数，0是自然数所以1也是自然数以此类推

（3）\(x+1≠0\)

（4）如果\(x+1=y+1\)那么\(x=y\)

这一条是在定义\(x+1\)这种最基本的运算性质，同时也确定了0是自然数中的最小数

（5）数学归纳法：已知任意公式\(P\)，如果满足\(P(0)\)，那么假定在任意k的情况下若能在\(P(k)≡1\)的前提下推出\(P(k+1)\)为真，则公式\(P\)对任意自然数成立

可以看到的是数学归纳法很明显的被框定在了自然数公理系统内，数学归纳法本身是证明任意情况下成立的命题，而且对象被限定为了自然数集，当然与自然数集同构的对象也是可以的，一般可以是整数集、有理数集、正整数等的同构集合，至于其同构性必须通过集合论才可证明，这里便不再说明。（备注，不可用作实数集、复数集等集合）

例：证明任意正整数\(n\)，\(n^3-n\)能被3整除

■完全归纳法（强归纳法、数学第二归纳法等名称），相比于第一归纳法而言，它更加灵活第一步同样是判断\(P(0)\)成立。但第二步不再假设唯一的\(P(k)\)成立，而是假设\(P(0)、P(1)、...、P(k)\)都成立再去判断\(P(k+1)\)是否成立。相比原本的数学归纳法，它提供了更多的假设条件可以去利用，但两者却完全等价的

例：证明算术基本定理——大于1的自然数必然可以分解为素数之积

显然\(2\)可以被分解为素数之积\(2=2^1\)

假设\(2,3,...,k\)都可以被分解为素数之积

那么k+1有两种情况，如果k+1是素数显然成立，如果k+1是合数，那么就\(∃a,b∈N∩[2,k]\)此时\(a,b\)由于假设前提满足，因此k+1也满足

这是完全归纳法可以证明而数学第一归纳法无法证明的例子