唐磊的个人博客

软考:计算机系统知识(四)

1.9 数学基础知识

1.9.1**命题逻辑的基础知识**

1. 命题

命题表述为具有确定真假意义的陈述句

命题必须具备二个条件:

其一,语句是陈述句;

其二,语句有唯一确定的真假意义

2. 联结词

h“Ø”否定联结词:P是命题,ØPP的否命题 是由联结词 Ø 和命题P组成的复合命题 一元命题

h “Ù”合取联结词,PÙQ是命题PQ的合取式,是“Ù”和PQ组成的复合命题 “Ù”在语句中相当于“不但…而且…”,“既…又…”。 PÙQ取值1,当且仅当PQ均取1;PÙQ取值为0,只要PQ之一取0

h “Ú”析取联结词,“Ú`”不可兼析取(异或)联结词, PÚQ是命题PQ的析取式,是“Ú”和PQ组成的复合命题。 PÚ`Q是联结词“Ú`”和PQ组成的复合命题 联结词“Ú”或“Ú`”在一个语句中都表示“或”的含义,可以表示相容或,也可以表示排斥或 Ú`表示不相容的或 即“PÚ`Q”«“ØPÙQÚPØÙQ PÚQ取值1,只要P,Q之一取值1,PÚQ取值0,只有P,Q都取值0。

h “«” 等价联结词,P«QPQ的等价式,是“«”和PQ组成的复合命题 “«”在语句中相当于“…当且仅当…”,P«Q取值1当且仅当PQ取值相同

h “®”蕴含联结词, P®Q是“®”和PQ组成的复合命题。 P®Q取值为0,只有P取值为1,Q取值为0时;其余各种情况,均有P®Q取值为1,亦即1®0的真值为0,0®1,1®1,0®0的真值均为1。

3. 命题公式、永真性的判定或命题公式的分类

h命题公式与赋值,命题P含有n个命题变项P1P2,…,Pn,给P1P2,…,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(AF(B)

4. 范式

h 析取(合取)范式,仅有有限个简单合取式(合取式)构成的析取式(合取式),就是析取(合取)范式

h 极小项(极大项),,n个命题变项,每个变项与它的否定不同时出现,但是两者必须出现且仅出现一次,而且第i个命题变项或者其否定出现在从左算起第i个位置上(无脚标时,按字典序排列),这样的简单合取式(析取式)为极小项(极大项)

极小项是n个变项的合取,m00PØÙQm01PÙQ,…; 极大项是n个变项的析取,M00=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个重言蕴含式(即I1I14),17个等值式(E1E17);二是会使用三个规则(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)为真

tanglei wechat
欢迎扫描二维码关注我的微信公众号