1.9 数学基础知识
1.9.1**命题逻辑的基础知识**
1. 命题
命题表述为具有确定真假意义的陈述句_。_
命题必须具备二个条件：
其一，语句是陈述句；
其二，语句有唯一确定的真假意义_。_
2. 联结词
h“Ø”否定联结词：_P_是命题，Ø_P_是_P_的否命题_。_ 是由联结词 Ø 和命题_P_组成的复合命题_。_ 一元命题_。_
h “Ù”合取联结词，_P_Ù_Q_是命题_P_，_Q_的合取式，是“Ù”和_P_，_Q_组成的复合命题_。_ “Ù”在语句中相当于“不但…而且…”，“既…又…”。 PÙ_Q_取值1，当且仅当_P_，_Q_均取1；_P_Ù_Q_取值为0，只要_P_，_Q_之一取0_。_
h “Ú”析取联结词，“Ú`”不可兼析取(异或)联结词， _P_Ú_Q_是命题_P_，_Q_的析取式，是“Ú”和_P_，_Q_组成的复合命题。 PÚ`_Q_是联结词“Ú`”和_P_，_Q_组成的复合命题_。_ 联结词“Ú”或“Ú`”在一个语句中都表示“或”的含义，可以表示相容或，也可以表示排斥或_。_ Ú`表示不相容的或_。_ 即“_P_Ú`_Q_”«“Ø_P_Ù_Q_Ú_P_ØÙ_Q_”_。_ PÚQ取值1，只要P，Q之一取值1，PÚQ取值0，只有P，Q都取值0。
h “«” 等价联结词，_P_«_Q_是_P_，_Q_的等价式，是“«”和_P_，_Q_组成的复合命题_。_ “«”在语句中相当于“…当且仅当…”，_P_«_Q_取值1当且仅当_P_，_Q_取值相同_。_
h “®”蕴含联结词， _P_®_Q_是“®”和_P_，_Q_组成的复合命题。 P®_Q_取值为0，只有_P_取值为1，_Q_取值为0时；其余各种情况，均有_P_®_Q_取值为1，亦即1®0的真值为0，0®1，1®1，0®0的真值均为1。
3. 命题公式、永真性的判定或命题公式的分类
h命题公式与赋值，命题_P_含有_n_个命题变项_P_1，_P_2,…,Pn，给_P_1，_P_2,…,Pn各指定一个真值0或1，称为对_P_的一个赋值(真值指派)_。_ 若指定的一组值使_P_的值为1，则这组值为_P_的真指派；若使_P_的值为0，则称这组值称为_P_的假指派_。_
h命题公式分类，在各种赋值下均为真的命题公式_A_，称为重言式(永真式)；在各种赋值下均为假的命题公式_A_，称为矛盾式(永假式)；命题_A_不是矛盾式，称为可满足式；
判定命题公式类型的方法：其一是真值表法，对于任给公式，列出该公式的真值表，若真值表的最后一列全为1，则该公式为永真式；若真值表的最后一列全为0，则该公式是永假式；若真值表的最后一列既非全1，又非全0，则该公式是可满足式_。_ 其二是推导法_。_ 利用基本等值式(双重否定律、幂等律、交换律、结合律、分配律、吸收律、摩根律、同一律、零律、否定律、蕴含等值式、等价等值式、假言易位和等价否定等值式等)，对给定公式进行等值推导，若该公式的真值为1，则该公式是永真式；若该公式的真值为0，则该公式为永假式_。_
h定理1：设_F_(_A_)是含命题公式_A_的命题，_F_(_B_)是用命题公式_B_置换_F_(_A_)中的_A_之后得到的命题公式_。_ 如果_A_Û_B_，则_F_(_A_)Û_F_(_B_)_。_
4. 范式
h 析取(合取)范式，仅有有限个简单合取式(合取式)构成的析取式(合取式)，就是析取(合取)范式_。_
h 极小项(极大项),，_n_个命题变项，每个变项与它的否定不同时出现，但是两者必须出现且仅出现一次，而且第_i_个命题变项或者其否定出现在从左算起第_i_个位置上(无脚标时，按字典序排列)，这样的简单合取式(析取式)为极小项(极大项)_。_
极小项是_n_个变项的合取,_m_00=Ø_P_ØÙ_Q_，_m_01=Ø_P_Ù_Q_,…; 极大项是_n_个变项的析取,_M_00=_P_Ù_Q_，M01=_P_ØÙ_Q_,…;
h 主析取范式(主合取范式)，对于含有_n_个命题变项的命题公式如果有一个仅有极小项(极大项)的析取(合取)构成的等式，则该等式为原命题公式的主析取范式(主合取范式)_。_
每项含有n个命题变项(变项字母齐全)合取式(析取式)的析取(合取)为主析取(主合取)范式。
任意命题公式都存在与之等值的析取范式和合取范式，与之等值的主析取范式和主合取范式是惟一的_。_
求范式，包括求析取范式、合取范式、主析取范式和主合取范式_。_ 关键有两点：
其一是准确掌握范式定义；
其二是巧妙使用基本等值式中的分配律、同一律和摩根律，结果的前一步适当使用幂等律_。_
求析取(合取)范式的步骤：
① 将公式中的联结词都化成Ø，Ù，Ú(在析取(合取)范式中不能有联结词®，«，Ú`)；
② 将否定联结词Ø消去或移到各命题变项之前；
③ 利用分配律、结合律等，将公式化为析取(合取)范式_。_
求命题公式_A_的主析取(合取)范式的步骤
① 求公式_A_的析取(合取)范式；
② “消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如_P_ØÙ_P_(_P_ØÚ_P_)用0(1)替代_。_ 用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如_P_Ù_P_(_P_Ú_P_)用_P_替代，miÚmi(MiÙMi)用mi(Mi)替代_。_
③ 若析取(合取)范式的某个合取项(析取项)_B_不含有命题变项Pi或ØPi，则添加PiØÚPi(PiØÙPi)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全；
④ 将极小(极大)项按由小到大的顺序排列，用S(P)表示_。_
5. 命题演算的推理理论
掌握演绎或形式证明_。_ 要理解并掌握14个重言蕴含式(即_I_1～_I_14)，17个等值式(_E_1～_E_17)；二是会使用三个规则(_P_规则、_T_规则和_CP_规则)_。_
1.9.2 谓词逻辑、形式逻辑基础知识**
1**．谓词概念**：用以刻画客体的性质或关系的词；
用谓词表达命题必须包括两个部分：客体和谓词字母，其中客体表示的是对象而谓词字母表示的是客体之间的关系。可以分为一元谓词，记作A(b)，二元谓词，记作B(a ,b)等等。
单独一个谓词不是一个完整的命题，把谓词字母后填以客体所得的式子称为谓词填式。
有N个客体变元的谓词称为N元谓词
谓词命名式中客体变元的取值范围叫客体域
例：论述域a{人}，b{人，地名}，c{实数，实数，实数}
注意：空集不能作为论述域
若A代表一特定谓词，A称为谓词常元。
若A 代表任意谓词， A称为谓词变元。
注：(1)单独的客体或单独的谓词不能构成命题
(2)在谓词命名式中,若谓词是常元,个体变元代以 论述域中某客体才成为命题
(3)命题是0元谓词
2**．命题函数：**由一个谓词，一些客体变元组成的表达式称为简单命题函数，有0元和n元命题函数。
量词：分为全称量词和存在量词
全称量词：”x读作‘对任意x’， “xP(x)表示‘对一切x,P(x)为真’
┐”x┐P(x)表示，‘并非对任意x, ┐P(x)是真’
存在量词：$x读作‘至少有一x’，‘存在一x’
$x ┐P(x)表示，‘存在一x，使┐P(x) 为真’
┐$x ┐P(x)表示，‘并非存在一个x，使P(x)为真’
任意谓词中任意个体变元的所有个体域称全总个体域
注：使用全总个体域后，个体变元取值范围一致。
但不同论述对象须用不同的特性谓词加以刻划。
个体词：
个体域：
3**．不出现命题联结词和量词的谓词命名式P(X1, X2…Xn)称为谓词演算的原子公式。**
谓词演算的合式公式简称谓词公式，定义如下：
1)谓词演算的原子公式是谓词演算公式
2)若A， B是谓词演算公式，则
(┐A)，(AÙB)，(AÚB)，(A→B)，(A«B)，
(“XA)和($XA)是谓词演算公式
3)只有有限次应用步骤1）和2）构成的公式才是谓词演算公式
4**．自由变元与约束变元：**
定义：在量词”X，$X辖域内变元X的一切出现叫约束出现，称这样的X为约束变元。
变元的非约束出现称为自由出现,称这样的变元为自由变元。
谓词演算的永真公式：对公式A和B中的谓词变元（包括命题变元），指派任一在E上有定义的确定的谓词，指派E中任一确定的个体，若所得命题有相同的真值，称在E上AÛB。
例如：1.”XP(X)→$XR(X)Û ┐”XP(X) Ú $XR(X)
2．”XA Û A $XA Û A 这里A不含自由变元X
3． a.”XP(X) ÞP(Y)或”XP(X) ÞP(X)
b.P(Y) Þ$X P(X)或P(X) P(X)
c.”XP(X) Þ$XP(X)
4.a.”XA(X)ÚP Û”X(A(X)ÚP)
b.”XA(X)ÙP Û”X(A(X)ÙP)
c.$XA(X)ÚP Û$X(A(X)ÚP)
d.$XA(X)ÙP Û$X(A(X)ÙP)
5**．前束范式**：量词均在谓词公式开头，作用域延伸到整个谓词公式末尾的谓词公式称为前束范式。
例1：”x”y$z(Q(x，y) →R(z))
例2：”x”y(┐P(x，y) →Q(y))
例1把”x”y(┐($zP((x,y,z) ÙP(y,z)))→$uQ(x,y,u))化为前束范式。
解：原式
Û”x”y(┐($z(P(x，z) ÙP(y，z)) Ú$uQ(x，y，u))
Û”x”y(“z(┐P(x，z) Ú┐P(y，z)) Ú$uQ(x，y，u))
Û”x”y”z$u(┐P(x，y) Ú┐P(y，z) ÚQ(x，y，u))
定义：若谓词公式是前束范式且作用域为合取范式,则称为前束合取范式。
前束合取范式形式:(□u1)(□u2)…..(□un)((A11Ú………ÚA1m1) Ù…Ù (An1Ú…. ÚAnmn))
定义：若谓词公式是前束范式且作用域为析取范式,则称为前束析取范式。
前束析取范式形式:
(□u1)(□u2)…..(□un)((A11Ù………ÙA1m1) Ú… Ú (An1Ù…….. ÙAnmn))
6．推理规则与推理理论：
命题演算中的所有推理规则都是谓词演算中的推理规则，谓词演算的所有永真式也是谓词推理规则。
四条重要的推理规则
1.全称指定规则，简记为US：对一切x，P(x)为真,可推得任意一个确定的c，使P(c)为真。
2.存在指定规则，简记为EG：至少存在一个x使得A(x)为真.即可推得有一个确定的c,使P(c)为真。
3.存在推广规则，简记为EG：c是某个确定的个体,若P(c)为真,则$x P(x)为真注意：c不能出现在P(c)中的x的辖域中
4.全称推广规则，简记为UG：若对个体域中每一个客体c，P(c)断言为真则”x P(x)为真
