1命题演算及其形式系统
1.1 命题与联结词
内容提要
1.1.1 命题
我们把对确定的对象作出判断的陈述句称作命题（propositions），当判断正确或符合客观实际时，称该命题真（true），否则称该命题假（false）。“真、假”常被称为命题的真值。
自然语言中“并非、或者、并且、如果…，那么…、当且仅当” 这样的联结词称为逻辑联结词（logical connectives）。通常把不含有逻辑联结词的命题称为原子命题或原子（atoms），而把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositive propositions）。1.1.2 联结词
否定词(negation)“并非”（not），用符号┐表示。设p表示一命题，那么┐p表示命题p 的否定。p真时┐p假，而p假时┐p真。┐p读作“并非p”或“非p”。
合取词(conjunction)“并且”（and），用符号∧表示。设p，q表示两命题，那么p∧q表示合取p和q所得的命题，即p和q同时为真时p∧q真，否则p∧q为假。p∧q读作“p并且q”或“p 且q”。
析取词(disjunction)“或”（or）用符号∨表示。设p，q表示两命题，那么p∨q表示p和q 的析取，即当p和q有一为真时，p∨q为真，只有当p和q均假时p∨q为假。p∨q读作“p或者q”、“p或q”。
蕴涵词(implication)“如果……，那么……”（if…then…），用符号→表示。设p，q表示两命题，那么p→q表示命题“如果p，那么q”。当p真而q假时，命题p→q为假，否则均认为p →q为真。p→q中的p称为蕴涵前件，q称为蕴涵后件。p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的必要条件”，“q当p”，“p仅当q”等等。数学中还常把q→p，┐p→┐q，┐q→┐p分别叫做p→q的逆命题，否命题，逆否命题。
双向蕴涵词(two-way implication)“当且仅当”（if and only if），用符号表示之。设p，q为两命题，那么p q表示命题“p当且仅当q”，“p与q等价”，即当p与q同真值时p q 为真，否则为假。p q读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。由于“当且仅当”“等价”常在其它地方使用，因而用第一种读法更好些。
1.1.3 命题公式及其真值表
我们把表示具体命题及表示常命题的p，q，r，s与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。
定义1.1 以下三条款规定了命题公式（proposition formula）的意义：
（1）命题常元和命题变元是命题公式，也称为原子公式或原子。
（2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A B）也是命题公式。
（3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。
如果公式A含有命题变元p1，p2，…，p n，记为A(p1,…,p n)，并把联结词看作真值运算符，那么公式A可以看作是p1,…,p n的真值函数。对任意给定的p1,…,p n的一种取值状况，称为指派（assignments），用希腊字母，等表示，A均有一个确定的真值。当A对取值状况为真时，称指派弄真A，或是A的成真赋值，记为 (A) = 1；反之称指派弄假A，或是A的成假赋值，记为 (A) = 0。对一切可能的指派,公式A的取值可能可用一张表来描述,这个表称为真值表（truth table）。当A(p1,…,p n)中有k个联结词时，公式A的真值表应为2n行、k+n列（不计表头）。
1.1.4 语句的形式化
用我们已有的符号语言，可以将许多自然语言语句形式化。
语句形式化要注意以下几个方面。
要善于确定原子命题，不要把一个概念硬拆成几个概念，例如“弟兄”是一个概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一个原子命题。
要善于识别自然语言中的联结词（有时它们被省略）。例如“风雨无阻，我去上学”一句，可理解为“不管是否刮风、是否下雨我都去上学”。
否定词的位置要放准确。
需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。
另外要注意的是,语句的形式化未必是唯一的。
习题解答
练习1.1
1、判断下列语句是否是命题，若是命题则请将其形式化：
（1）a+b
（2）x>0
（3）“请进！”
（4）所有的人都是要死的，但有人不怕死。
（5）我明天或后天去苏州。
（6）我明天或后天去苏州的说法是谣传。
（7）我明天或后天去北京或天津。
（8）如果买不到飞机票，我哪儿也不去。
（9）只要他出门，他必买书，不管他余款多不多。
（10）除非你陪伴我或代我雇辆车子，否则我不去。
（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。
（12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。
（13）不管你和他去不去，我去。
（14）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》）
（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：《荀子劝学》）
解（1）a+b 不是命题
（2）x>0 不是命题（x是变元）
（3）“请进！”不是命题
（4）所有的人都是要死的，但有人不怕死。是命题
可表示为p∧┐q，其中p：所有的人都是要死的，q：所有的人都怕死
（5）我明天或后天去苏州。是命题
可表示为p∨q，其中p：我明天去苏州；q：我后天去苏州
（6）我明天或后天去苏州的说法是谣传。是命题
可表示为┐(p∨q)，其中p、q同（5）
（7）我明天或后天去北京或天津。是命题
可表示为p∨q∨r∨s，其中p：我明天去北京，q：我明天去天津，r：我后天去北
京，s：我后天去天津
（8）如果买不到飞机票，我哪儿也不去。是命题
可表示为┐p→┐q，其中，p：我买到飞机票，q：我出去
（9）只要他出门，他必买书，不管他余款多不多。是命题
可表示为(p∧q→r)∧(┐p∧q→r)或q→r，其中p：他余款多，q：他出门，r：他
买书
（10）除非你陪伴我或代我雇辆车子，否则我不去。是命题
可表示为(p∨q) r，其中p：你陪伴我，q：你代我雇车，r：我去
（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。是命题
可表示为(p→q) ∧(q→p )或p q，其中p：你充分考虑了一切论证，q：你得
到了可靠见解
（12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。是命题
可表示为(q→p ) →┐q，其中p：我懂得希腊文，q：我了解柏拉图
（13）不管你和他去不去，我去。是命题
可表示为(p→r) ∧(q→r) ∧( ┐p→r) ∧( ┐q→r)或r，其中p：你去，q：
他去，r：我去
（14）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》）是命题
可表示为((p∧q)→r) ∧((┐p∧┐q)→┐r)，其中p：你奢侈，q：你懒惰，r：
你贫困
（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。（荀况：《荀子劝学》）是命题
可表示为(p→┐q) ∧(s→r) ∧(m∧n→┐o) ∧(m∧┐n→v)，其中p：骐骥一
跃，q：骐骥一跃十步，r：驽马行千里，s：驽马不断奔跑，m：你雕刻，n：你
放弃，o：将朽木折断，v：金石可雕刻
2、判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点（公式中省略了可以省略的括号）：
（1）┐(p)（p为原子命题）
（2）(p∨qr)→s
（3）(p∨q)→p
（4）p→(p∨q)
（5）┐(p∨┐p)
（6）p∧(p→q)→q
（7）p∧(p→q)∧(p→┐q)
（8）(p→q) (┐q→┐p)
（9）┐(p∨q) ┐q∧┐p
（10）┐p∨q (p→q)
（11）(p→q)∧(q→r)→(p→r)
（12）(p∨q→r) (p→r)∧(q→r)
解（1）┐(p) 不是公式
（2）(p∨qr)→s 不是公式
（4）p→(p∨q) 是公式（真值表见上表，恒真）
（5
（6
（7
（8
(p→q) (┐q→┐p)
（9
┐(p∨q) ┐q∧┐
p
（10
┐p∨q (p→q)
（11
（
(p∨q→r) (p
→r)∧(q→r)
*3、A国的人只有两种，一种永远说真话，一种永远说假话。你来到A国，并在一个二叉路口不知如何走才能到达首都。守卫路口的士兵只准你问一个问题，而且他只答“是”或“不是”。你应该如何发问，才能从士兵处获知去首都的道路。
解设p：你是说真话的；q：我应当向右走去首都
你应当问：p q ?
当回答“是 (真)”，你选择向右走；当回答“不（假）”时，你选择向左走。因为
p q真，当且仅当p真且q真（士兵说真话且应当向右走）
或p假且q假（士兵说假话且应当向左走）
p q假，当且仅当p真且q假（士兵说真话且应当向左走）
或p假且q假（士兵说假话且应当向右走）
1.2 重言式
内容提要
1.2.1 重言式概念
定义1.2命题公式A称为重言式（tautology），如果对A中命题变元的一切指派均弄真A，因而重言式又称永真式；A称为可满足式（satisfactable formula），如果至少有一个指派弄真A，否则称A为不可满足式或永假式、矛盾式。
1.2.2 逻辑等价式和逻辑蕴涵式
定义1.3 当命题公式A B为永真式时，称A逻辑等价于B，记为A┝┥B，它又称为逻辑等价式(logically equivalent)。
以下是一些重要的逻辑等价式，其中A，B，C表示任意命题公式：
E1┐┐A┝┥A 双重否定律
E2 A∨A┝┥A 幂等律
E3 A∧A┝┥A 幂等律
E4 A∨B┝┥B∨A 交换律
E5 A∧B┝┥B∧A 交换律
E6 (A∨B)∨C┝┥A∨(B∨C) 结合律
E7 (A∧B)∧C┝┥A∧(B∧C) 结合律
E8 A∧(B∨C)┝┥(A∧B)∨(A∧C) 分配律
E9 A∨(B∧C)┝┥(A∨B)∧(A∨C) 分配律
E10┐(A∨B)┝┥┐A∧┐B 德摩根律
E11┐(A∧B)┝┥┐A∨┐B 德摩根律
E12 A∨(A∧B)┝┥A 吸收律
E13 A∧(A∨B)┝┥A 吸收律
E14 A→B┝┥┐A∨B
E 15 A B┝┥(A→B)∧(B→A)
E16 A∨t┝┥t
E17 A∧t┝┥A
E18 A∨f┝┥A
E19 A∧f┝┥f
E20 A∨┐A┝┥t
E21 A∧┐A┝┥f
E22┐t┝┥f, ┐f┝┥t
E23 A∧B→C┝┥A→(B→C)
E24 A→B┝┥┐B→┐A
E25 (A→B)∧(A→┐B)┝┥┐A
定义1.4当命题公式A→B为永真式时，称A逻辑蕴涵B，记为A┝ B，它又称为逻辑蕴涵式(logically implication)。
我们也列出一些十分重要的逻辑蕴涵式：
I1 A┝ A∨B，B┝ A∨B
I2 A∧B┝ A，A∧B┝ B
I3 A∧(A→B)┝ B
I4 (A→B)∧┐B┝┐A
I5┐A∧(A∨B)┝ B，┐B∧(A∨B)┝ A
I6 (A→B)∧(B→C)┝ A→C
I7 (A→B)∧(C→D)┝ (A∧C)→(B∧D)
I 8 (A B)∧(B C)┝ A C
逻辑等价式与逻辑蕴涵式有如下明显性质。
定理1.1对任意命题公式A，B，C，A'，B'，
（1）A┝┥B当且仅当┝ A B
（2）A┝ B当且仅当┝ A→B
（3）若A┝┥B，则B┝┥A
（4）若A┝┥B，B┝┥C，则A┝┥C
（5）若A┝ B，则┐B┝┐A
（6）若A┝ B，B┝ C，则A┝ C
（7）若A┝ B，A┝┥A'，B┝┥B'，则A'┝ B'
定理1.2设A为永真式，p为A中命题变元，A(B/p)表示将A中p的所有出现全部代换为公式B 后所得的命题公式（称为A的一个代入实例），那么A(B/p)亦为永真式。
定理1.3设A为一命题公式，C为A的子公式（A的一部分，且自身为一公式），且C┝┥D。若将A中子公式C的某些（未必全部）出现替换为D后得到公式B，那么A┝┥B。
定理1.2常被称为代入原理（rule of substitution），简记为RS。
定理1.3常被称为替换原理（rule of replacement）简记为RR。
△1.2.3 对偶原理
定义1.5设公式A仅含联结词┐，∧，∨，A*为将A中符号∧，∨，t，f分别改换为∨，∧，f，t后所得的公式，那么称A*为A的对偶（dual）。
显然A与A*互为对偶，即(A*)*=A
定理1.4 设公式A中仅含命题变元p1,…,p n，及联结词┐，∧，∨，那么
A┝┥┐A*(┐p1/p1,…, ┐p n/p n)
这里A*(┐p1/p1,…, ┐p n/p n)表示在A*中对p1,…,p n分别作代入┐p1,…, ┐p n后所得的公式。
定理1.5设A，B为仅含联结词┐，∧，∨和命题变元p1,…,p n的命题公式，且满足A┝B，那么有B*┝ A*。进而当A┝┥B时有A*┝┥B*。常把B*┝ A*，A*┝┥B*称为A┝ B和A┝┥B的对偶式。
习题解答
练习1.2
1、试判定以下各式是否为重言式：
（1）(p→q)→(q→p)
（2）┐p→(p→q)
（3）q→(p→q)
（4）p∧q→(p q)
（5）(p→q)∨(r→q)→((p∨r)→q)
（6）(p→q)∨(r→s)→((p∨r)→(q∨s))
解（1）否
（2）是
（3）是
（4）是
（5）否
（6）否
2、试用真值表验证E6，E8，E10，E11，E23。
证
6
（8
（3
10
11
23
3、不用真值表，用代入、替换证明E 12，E 13，E 24。
证 （1）E 12： A ∨(A ∧B) ┝┥A
A ∨(A ∧B) ┝┥(A ∧t)∨(A ∧B) 据E 17用RR
┝┥A∧ (t∨B) 对E8用RS
┝┥A∧t 据E16用RR
┝┥A 据E17
（2）E13： A∧(A∨B) ┝┥ A
A∧(A∨B) ┝┥(A∨f)∧(A∨B) 据E18用RR
┝┥A∨(f∧B) 对E9用RS
┝┥A∨f 据E19用RR
┝┥A 据E18
（3）E24： A→B ┝┥┐B→┐A
┐B→┐A┝┥┐┐B∨┐A 对E14用RS
┝┥B∨┐A 据E1用RR
┝┥┐A∨B 对E4用RS
┝┥ A→B 据E14
4、试用真值表验证I3，I4，I5，I6。
证（1 3
（2 4
（3 5
（4 6
5、不用真值表，用代入、替换证明I7，I8。
证（1）I7：(A→B)∧(C→D)┝ (A∧C)→(B∧D)
(A→B)∧(C→D)┝┥(┐A∨B)∧(┐C∨D)
(A∧C)→(B∧D)┝┥(┐A∨┐C)∨(B∧D)
┝┥(┐A∨┐C∨B)∧(┐A∨┐C∨D)
由于
(┐A∨B)∧(┐C∨D)┝ (┐A∨┐C∨B)∧(┐A∨┐C∨D)
故(A→B)∧(C→D)┝ (A∧C)→(B∧D)。
（2）I 8：(A B)∧(B C)┝ (A C)
(A B)∧(B C)┝┥(A→B)∧(B→A)∧(B→C)∧(C→B)
┝┥((A→B)∧(B→C)) ∧ ((C→B)∧(B→A))
┝ (A→C)) ∧ (C→A)
┝┥(A C)
6、用三种不同方法证明下列逻辑等价式：
（1）A B┝┥(A∧B)∨(┐A∧┐B)
（2）A→(B→C)┝┥B→(A→C)
（3）A→(A→B)┝┥A→B
（4）A→(B→C)┝┥(A→B)→(A→C)
A B
┝┥(┐A∨B)∧(┐B∨A)
┝┥(┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A)
┝┥(A∧B)∨(┐A∧┐B)
证法3：先证A B┝ (A∧B)∨(┐A∧┐B) (a)
设为任一指派，使(A B)=1，那么(A)= (B)=1或(A)= (B)=0，从
而(A∧B)=1或(┐A∧┐B)=1，即((A∧B)∨(┐A∧┐B))=1。(a)得证；
再证(A∧B)∨(┐A∧┐B)┝ A B (b)
设为任一指派，使(A B)=0，那么(A)=1，(B)=0，或者(A)=0，(B)=1，
从而(A∧B)=0且(┐A∧┐B)=0，即((A∧B)∨(┐A∧┐B))=0。(b)得证。
（2
┝┥(┐A∨┐B)∨C
┝┥(┐B∨┐A)∨C
┝┥┐B∨(┐A∨C)
┝┥B→(A→C)
证法3：先证A→(B→C)┝ B→(A→C) (a)
设为任一指派，使(A→(B→C))=1，那么
ⅰ）(A)= 0，则( A→C)=1，从而( B→(A→C))=1
ⅱ）(A)= 1，(B)=0，则( B→(A→C))=1
ⅲ）(A)=(B)=(C)=1，则( B→(A→C))=1
综上，(a)得证；同理可证B→(A→C)┝ A→(B→C)。
（3
(A→(A→B)) (A→B)
┝┥(┐A∨┐A)∨B
┝┥┐A∨B
┝┥A→B
证法3：先证A→(A→B)┝ A→B (a)
设为任一指派，使( A→B)=0，那么(A)=1，(B)=0，从而( A→(A→
B))=0。(a)得证；
再证A→B┝ A→(A→B) (b)
设为任一指派，使(A→(A→B))=0，那么(A)=1，(A→B)=0。(b)得证。（
┝┥(A∧┐B) ∨ (┐A∨C)
┝┥( (A∧┐B)∨┐A)∨C
┝┥((A∨┐A)∧(┐B∨┐A) )∨C
┝┥(t∧(┐A∨┐B) )∨C
┝┥(┐A∨┐B)∨C
┝┥┐A∨(┐B∨C)
┝┥A→(B→C)
证法3：先证A→(B→C)┝ (A→B)→(A→C) (a)
设为任一指派，使((A→B)→(A→C))=0，那么( A→B)=1，( A→C)=0，
即(A)= (B)=1，(C)=0，从而( B→C)=0，( A→(B→C))=0。(a)
得证；
再证(A→B)→(A→C)┝ A→(B→C) (b)
设为任一指派，使( A→(B→C))=0，那么(A)=1，(B→C)=0，即
(B)=1，(C)=0，从而(A→B)=1，( A→C)=0，((A→B)→(A→C))=0。
(b)得证。
7、用三种不同方法证明下列逻辑蕴涵式：
（1）A∧B┝ A B
（2）(A→B)→A┝ A
（3）A→B┝ ((A B)→A)→B
（4）(A∨B)∧(A→C)∧(B→C)┝ C
证（1
A B (A∧B) → (A B)
┝┥A B
证法3：设为任一指派，使(A∧B)=1，则(A)= (B)=1，从而( A B)=1。
A∧B┝ A B得证。
（2
┝┥ (A∧┐B) ∨ A
┝┥ (A∨ A)∧(┐B∨A)
┝┥ A∧(┐B∨A)
┝ A
证法3：设为任一指派，使(A)=0，则(A→B)= 1，从而((A→B)→A)=0。
(A→B)→A┝ A得证。
A B (A B)→A ((A B)→A)→B (A→B)→
(((A B)→A)→B)
((A B)→A)→B┝┥┐((A B)→A)∨B
┝┥((A B) ∧┐A)∨B
┝┥(((A∧B)∨(┐A∧┐B))∧┐A)∨B
┝┥(┐A∧┐B)∨B
┝┥┐A∨B
∴ A→B┝ ((A B)→A)→B
证法3：设为任一指派，使( A→B)=1，则（ⅰ）(A)= 0；（ⅱ）(B)= 1。
对（ⅱ）显然有( ((A B)→A)→B)=1；
对（ⅰ）则可令(B)= 0（(B)= 1的情况已证），于是(A B)=1，((A B)
→A)=0，(((A B)→A)→B) =1。
A→B┝ ((A B)→A)→B得证。
┝┥(A∨B∨C)∧(A∨B∨┐C)∧(┐A∨B∨C)∧(┐A∨┐B∨C)∧(A∨
┐B∨C)
┝ (A∨B∨C)∧(A∨┐B∨C)∧(┐A∨B∨C)∧(┐A∨┐B∨C)
┝┥(A∨C) ∧(┐A∨C)
┝┥C
证法3：设为任一指派，使((A∨B)∧(A→C)∧(B→C))=1，则(A∨B)= ( A →C)= ( B→C)=1。由(A∨B)=1有两种情况：
（ⅰ）(A)=1，由( A→C)=1得(C)=1；
（ⅱ）(B)= 1，由( B→C)=1得(C)=1。
(A∨B)∧(A→C)∧(B→C)┝ C得证。
△8、验证下列逻辑等价式和逻辑蕴涵式，并写出它们的对偶式：
（1）┐(┐A∨┐B)∨┐(┐A∨B)┝┥A
（2）(A∨┐B)∧(A∨B)∧(┐A∨┐B)┝┥┐(┐A∨B)
（3）B∨┐((┐A∨B)∧A)┝┥t
（4）┐A∨(┐B∨C)┝┐(┐A∧B)∨(┐A∨C)
（5）┐(A∨B)∨C┝ A∨(┐B∨C)
解（1）┐(┐A∨┐B)∨┐(┐A∨B)┝┥(A∧B)∨(A∧┐B)
┝┥A∧(B∨┐B)
┝┥A
对偶式：┐(┐A∧┐B)∧┐(┐A∧B)┝┥A
（2）(A∨┐B)∧(A∨B)∧(┐A∨┐B)┝┥A∧(B∨┐B)∧(┐A∨┐B)
┝┥A∧(┐A∨┐B)
┝┥A∧┐B
┝┥┐(┐A∨B)
对偶式：(A∧┐B)∨(A∧B)∨(┐A∧┐B)┝┥┐(┐A∧B)
（3）B∨┐((┐A∨B)∧A)┝┥B∨((A∧┐B)∨┐A)
┝┥B∨(┐B∨┐A)
┝┥t
对偶式：B∧┐((┐A∧B)∨A)┝┥f
（4）┐A∨(┐B∨C)┝ A∨┐B∨┐A∨C
┝┐(┐A∧B)∨(┐A∨C)
对偶式：┐(┐A∨B)∧(┐A∧C)┝┐A∧(┐B∧C)
（5）┐(A∨B)∨C┝ (┐A∧┐B)∨C
┝ (┐A∨C)∧(┐B∨C)
┝┐B∨C
┝ A∨(┐B∨C)
对偶式：A∧(┐B∧C)┝┐(A∧B)∧C
1.3 范式
内容提要
1.3.1 析取范式和合取范式
文字(letters)：指命题常元、变元及它们的否定，前者又称正文字，后者则称负文字。
析取子句(disjunctive clauses)：指文字或若干文字的析取。例如, p , p∨┐q , ┐p ∨┐q∨r .
合取子句(conjunctive clauses)：指文字或若干文字的合取。例如, ┐p , ┐p∧┐q , p ∧┐q∧r .
互补文字对(complemental pairs of letters) ：指形如L，┐L（L为文字）的一对字符。
定义1.6 命题公式A'称为公式A的析取范式（disjunctive normal form），如果
（1）A'┝┥A
（2）A'为一合取子句或若干合取子句的析取。
定义1.7命题公式A'称为公式A的合取范式（conjunctive normal form）如果
（1）A'┝┥A
（2）A'为一析取子句或若干析取子句的合取。
1.3.2 主析取范式与主合取范式
定义1.8设A为恰含命题变元p1,…,p n的公式。公式A'称为A的主析（合）取范式（majordisjunctive（conjunctive）normal form），如果A'是A的析（合）取范式，并且其每个合（析）取子句中p1,…,p n均恰出现一次。
△1.3.3 联结词的扩充与归约
n个变元的真值表可以有
n
2
2张，因而可以定义n22个n元的真值函数或联结词。这就是说，
我们可以规定
1
2
2=4个一元联结词，222=16个二元联结词。
定义1.9称n元联结词h是用m 个联结词g1, g2,…, g m可表示的，如果
h(p1, p2,. . ., p n ) ┝┥A
而A中所含联结词仅取自g1, g2,. . ., g m。
定义1.10当联结词组g1, g2,. . ., g m可表示所有一元、二元联结词时，称其为完备联结词组（complete group of connectives）。
习题解答
练习1.3
1、求下列公式的析取范式、合取范式及主析取范式、主合取范式，并据主析（合）取范式直接确定弄真该公式的指派和弄假该公式的指派：
（1）(┐p∨┐q)→(p┐q)
（2）q∧(p∨┐q)
（3）p∨(┐p→(q∨(┐q→r)))
（4）(p→(q∧r))∧(┐p→(┐q∧┐r))
（5）p→(p∧(q→r))
解（1）(┐p∨┐q)→(p┐q)┝┥┐(┐p∨┐q)∨((┐p∨┐q)∧(p∨q))
┝┥(p∧q)∨(┐p∧q)∨(p∧┐q) （主析取范式）
┝┥q∨(p∧┐q) （析取范式）
┝┥p∨q （合取范式、主合取范式）
弄真指派：p 1 0 1 弄假指派：p 0
q 1 1 0 q 0
（2）q∧(p∨┐q)┝┥q∧(p∨┐q) （合取范式）
┝┥((p∧┐p)∨q)∧(p∨┐q)
┝┥(p∨q)∧(┐p∨q)∧(p∨┐q) （主合取范式）
┝┥p∧q （析取范式、主析取范式）
弄真指派：p 1 弄假指派：p 0 1 0
q 1 q 0 0 1
（3）p∨(┐p→(q∨(┐q→r)))┝┥p∨(p∨(q∨(q∨r)))
┝┥p∨q∨r （合取范式、主合取范式）┝┥(p∧(q∨┐q)∧(r∨┐r))∨(q∧(p∨┐p)∧(r∨┐r))∨(r∧(p∨┐p)∧(q∨┐q))
┝┥(p∧q∧r)∨(p∧q∧┐r)∨(p∧┐q∧r)∨(p∧┐q∧┐r)∨(┐p∧q∧r)∨(┐p∧q∧┐r)∨(┐p∧┐q∧r) （析取范式、主析取范式）弄真指派：p 1 1 1 1 0 0 0 弄假指派：p 0
q 1 1 0 0 1 1 0 q 0
r 1 0 1 0 1 0 1 r 0
（4）(p→(q∧r))∧(┐p→(┐q∧┐r))┝┥(┐p∨(q∧r ))∧(p∨(┐q∧┐r))
┝┥(┐p∨q)∧(┐p∨r )∧(p∨┐q)∧(p∨┐r) （合取范式）
┝┥(┐p∨q∨r)∧(┐p∨q∨┐r)∧(┐p∨┐q∨r )∧(p∨┐q∨r)∧(p∨┐q∨┐r)∧(p∨q∨┐r) （主合取范式）
┝┥(┐p∧p)∨(q∧r∧p)∨(┐p∧┐q∧┐r)∨(q∧r∧┐q∧┐r) （析取范式）
┝┥(p∧q∧r)∨(┐p∧┐q∧┐r) （主析取范式）
弄真指派：p 1 0 弄假指派：p 1 1 1 0 0 0
q 1 0 q 0 0 1 1 1 0
r 1 0 r 0 1 0 0 1 1
（5）p→(p∧(q→r))┝┥┐p∨(p∧(┐q∨r ))
┝┥┐p∨(p∧┐q)∨(p∧r ) （析取范式）
┝┥(┐p∧q∧r)∨(┐p∧q∧┐r)∨(┐p∧┐q∧r)∨(┐p∧┐q∧┐r)∨(p∧┐q ∧r)∨(p∧┐q∧┐r)∨(p∧q∧r) （主析取范式）
┝┥(┐p∨p)∧(┐p∨┐q∧r ) （合取范式）
┝┥┐p∨┐q∧r （主合取范式）
弄真指派：p 0 0 0 0 1 1 1 弄假指派：p 1
q 1 1 0 0 0 0 1 q 1
r 1 0 1 0 1 0 1 r 0
2、主析取范式的两个不同析取项可能在同一指派下均真吗？为什么？主合取范式的两个不同合取项可能在同一指派下均假吗？为什么？
答主析取范式的两个不同析取项不可能在同一指派下均真。因为给定命题公式，其每个命题变元p1, …,p n在每个析取项中均恰出现一次，要使某个析取项在某指派下为真，则该指派下p1, …,p n的取值完全确定，而两个析取项又不相同，所以一个指派最多弄真一个析取项。同理可知主合取范式的两个不同合取项不可能在同一指派下均假。
3、利用范式证明下列公式为永真式（证明合取范式的每一个合取项中含有互补文字、或其主析取范式中含有2n个析取项，n是公式中变元的个数）
（1）(p→q)∧p→q
（2）((p→q)→(┐p→┐q)) →(( ┐q→┐p) →(q→p))
（3）(p q) ((p∧q)∨(┐p∧┐q))
（4）(p q) ((r∧p) (r∧q))∧((r∨p) (r∨q))
（5）┐(p q) ┐p┐q
（6）┐(p q) ┐p┐q
证（1）(p→q)∧p→q┝┥┐((┐p∨q)∧p)∨q
┝┥┐(┐p∨q)∨┐p∨q
┝┥(p∧┐q)∨┐p∨q
┝┥(p∨┐p∨q)∧(┐q∨┐p∨q)
∵合取范式的每一个合取项中均含有互补文字
∴原式为永真式
（2）((p→q)→(┐p→┐q)) →(( ┐q→┐p) →(q→p))
┝┥┐(┐(┐p∨q)∨(p∨┐q)) ∨ (┐( q∨┐p)∨(┐q∨p))
┝┥( (┐p∨q)∧(┐p∧q)) ∨ ((┐q∧p)∨(┐q∨p))
┝┥(┐p∧┐p∧q)∨(q∧┐p∧q)∨(┐q∧p)∨(┐q∧p)∨(┐q∧┐p)∨(p∧q)∨(p∧┐q)
┝┥(┐p∧q)∨(┐q∧┐p)∨(p∧q)∨(p∧┐q)
∵主析取范式中含有22个析取项
∴原式为永真式
（3）(p q) ((p∧q)∨(┐p∧┐q))
┝┥(((p→q)∧(q→p))→((p∧q)∨(┐p∧┐q))) ∧ (((p∧q)∨(┐p∧┐q))→((p→q)∧(q→p)))
┝┥(┐((┐p∨q)∧(┐q∨p)) ∨((p∧q)∨(┐p∧┐q))) ∧ (┐((p∧q)∨(┐p ∧┐q)) ∨((┐p∨q)∧(┐q∨p)))
┝┥((p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)) ∧ (((┐p∨┐q)∧(p∨q)) ∨((┐p∨q)∧(┐q∨p)))
┝┥((p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)) ∧ ((┐p∨┐q∨┐p∨q)∧(p ∨q∨┐p∨q)∧(┐p∨┐q∨┐q∨p)∧(p∨q∨┐q∨p))
┝┥(p∧┐q)∨(q∧┐p)∨(p∧q)∨(┐p∧┐q)
∵主析取范式中含有22个析取项
∴原式为永真式
（4）(p q) ((r∧p) (r∧q))∧((r∨p) (r∨q))
┝┥(p→q)∧(q→p) (((r∧p)→(r∧q))∧((r∧q)→(r∧p)))∧(((r∨p)→(r ∨q))∧((r∨q)→(r∨p)))
┝┥(┐p∨q)∧(┐q∨p) ((┐(r∧p)∨(r∧q))∧(┐(r∧q)∨(r∧p)))∧((┐(r∨p) ∨(r∨q))∧(┐(r∨q)∨(r∨p)))
┝┥(p∧q)∨(┐p∧┐q) (┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧(┐p ∨q∨r)
┝┥(┐((p∧q)∨(┐p∧┐q))∨((┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧(┐p∨q∨r))) ∧ (┐((┐p∨q∨┐r)∧(p∨┐q∨┐r)∧(p∨┐q∨r)∧
(┐p∨q∨r))∨((p∧q)∨(┐p∧┐q)))
┝┥((┐p∨┐q∨q∨r)∧(p∨q∨┐p∨r)∧(┐p∨┐q∨p∨r)∧(p∨q∨┐q∨r) ∧(┐p∨┐q∨p∨┐r)∧(p∨q∨┐q∨┐r)∧(┐p∨┐q∨q∨┐r)∧(p∨q∨
┐p∨┐r)) ∧ ((p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧
r)∨(p∧q)∨(┐p∧┐q))
┝┥(p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q)∨(┐p ∧┐q)
┝┥(p∧┐q∧┐r)∨(┐p∧q∧┐r)∨(┐p∧q∧r)∨(p∧┐q∧r)∨(p∧q∧┐r)∨(p∧q∧r)∨(┐p∧┐q∧┐r)∨(┐p∧┐q∧r)
∵主析取范式中含有23个析取项
∴原式为永真式
（5）┐(p q) ┐p┐q┝┥┐┐(p∨q) ┐(┐p∧┐q)
┝┥p∨q p∨q
┝┥(┐(p∨q)∨(p∨q)) ∧ (┐(p∨q)∨(p∨q))
┝┥ (┐p∨p∨q) ∧ (┐q∨p∨q)
∵合取范式的每一个合取项中均含有互补文字
∴原式为永真式
（6）┐(p q) ┐p┐q┝┥┐┐(p∧q) ┐(┐p∨┐q)
┝┥p∧q p∧q
┝┥(┐(p∧q)∨(p∧q)) ∧ (┐(p∧q)∨(p∧q))
┝┥(┐p∨┐q∨p) ∧ (┐p∨┐q∨q)
∵合取范式的每一个合取项中均含有互补文字
∴原式为永真式
4、把公式(p→q) (┐q→┐p)变换为与之等价的、只含联结词或的公式。
解(p→q) ( ┐q→┐p)┝┥(┐(┐p∨q)∨( q∨┐p)) ∧ (┐( q∨┐p)∨(┐p∨q))
┝┥((┐p q)∨┐( q┐p)) ∧ ( ( q┐p)∨┐(┐p q))
┝┥┐(┐((┐p q)∨┐( q┐p)) ∨┐(( q┐p)∨┐(┐p q)))
┝┥ ((┐p q) ┐( q┐p)) (( q┐p) ┐(┐p q))
┝┥
(((p p)q)((q(p p))(q(p p))))((q(p
p))(((p p)q) ((p p)q))) (p→q) ( ┐q→┐p)┝┥(┐(┐p∨q)∨( q∨┐p)) ∧ (┐( q∨┐p)∨(┐p∨q))
┝┥┐(┐(p∧┐q)∧(┐q∧p)) ∧┐(┐(┐q∧p)∧(p∧┐q))
┝┥┐(((p┐q) ┐(┐q p)) ((┐q p) ┐(p┐q))) ┝┥(((p(q q))(((q q)p)((q q)p))(((q q)p)((p(q q))
(p(q q)))))(((p(q q)) (((q q)p) ((q q)p))
(((q q)p)((p(q q)) (p(q q)))))
△5、求证┐, →及Δ1,→都是完备联结词组。你还能找到恰由两个联结词组成的完备联结词组吗？
证利用已知完备联结词组┐,∧,∨证明
（1）┐, →
p∨q┝┥┐┐p∨q┝┥┐p→q
p∧q┝┥┐(┐p∨┐q)┝┥┐(p→┐q)
∵完备联结词组┐,∧,∨中的任一个都可以用┐, →表示
∴┐, →构成完备联结词组
（2）Δ1, →
┐p┝┥p→f┝┥p→Δ1(p)
∵完备联结词组┐, →中的任一个都可以用Δ1, →表示
∴Δ1, →构成完备联结词组
其他恰由两个联结词组成的完备联结词组还有(┐,∧)，(┐,∨),( Δ4, →)等。
46、求证┐, ∨不是完备联结词组。
证利用已知不完备联结词组┐, 证明
p∨q┝┥(p∨q)∧┐(p∧q)┝┥┐(p q)
∵┐, ∨中的任一个都可以用┐, 表示
∴┐, ∨不是完备联结词组。否则┐, 也是完备联结词组,矛盾。
7、证明：联结词和满足交换律但不满足结合律。
证∵ p q┝┥┐(p∨q)┝┥┐(q∨p) ┝┥q p
p q┝┥┐(p∧q)┝┥┐(q∧p) ┝┥q p
∴和满足交换律
又∵ (p q) r┝┥┐(┐(p∨q) ∨r)┝┥(p∨q)∧┐r （1） p (q r)┝┥┐(p∨┐(q∨r))┝┥┐p∧(q∨r) （2）
（1）、（2）两式不等价（0，0，1弄假（1），但弄真（2））
∴不满足结合律
同理可知也不满足结合律
8、化简下列各式：
（1）p∨p ，（2）p∨t ，（3）p∨f
（4）p p ，（5）p t ，（6）p f
（7）p p ，（8）p t ，（9）p f
解（1）p∨p┝┥(p∨p)∧┐(p∧p)┝┥f
（2）p∨t┝┥(p∨t)∧┐(p∧t)┝┥┐p
（3）p∨f┝┥(p∨f)∧┐(p∧f)┝┥p
（4）p p┝┥┐(p∨p)┝┥┐p
（5）p t┝┥┐(p∨t)┝┥f
（6）p f┝┥┐(p∨f)┝┥┐p
（7）p p┝┥┐(p∧p)┝┥┐p
（8）p t┝┥┐(p∧t)┝┥┐p
（9）p f┝┥┐(p∧f)┝┥t
* 1.4 命题演算形式系统
内容提要
1.4.1 证明、演绎和推理
定义1.11公式序列A1,A2,…,A m称为A m的一个证明（proof），如果A i(1≤i≤m)或者是公理，或者由A j1…,A jk(j1,…,jk i)用推理规则推得。当这样的证明存在时，称A m为系统的定理（theorems），记为├*A m, ( 为所讨论的系统名),或简记为├A m 。
定义1.12设为一公式集合。公式序列A 1,A2,…,A m称为A m的以为前提的演绎（diduction），如果A i(1≤i≤m)或者是中公式，或者是公理，或者由A j1…,A jk(j1,…,jk i)用推理规则导出。当有这样的演绎时，A m称为的演绎结果，记为├*A m, ( 为所讨论的系统名)，或简记为├A m。称和的成员为A m的前提(hypothesis)。
显然，证明是演绎在为空集时的特例。
△1.4.2 命题演算形式系统PC
讨论的第一个命题演算形式系统命名为PC（formal system of Proposition Calculus）。
PC的语言有下列基本成分：
命题变元：p , q , r , s , p1 , q1 , r1 , s1,…
命题常元：t , f
联结词：┐,→（注意：它们是完备的）
括号：(,)
公式：（1）命题变元与命题常元是公式。
（2）如果A，B是公式，则（┐A），（A→B）均为公式（联结词结合能力约定与括号省略约定同前）。
（3）除有限次使用（1），（2）条款所得的符号串外，没有别的东西是公式。
PC的公理(其中A，B，C表示任意公式)：
A1：A→(B→A)
A2：(A→(B→C))→((A→B) →(A→C))
A3：(┐A→┐B)→(B→A)
PC的推理规则（其中A，B为任意公式）：
B B
A
A→
,
（分离规则）
定理1.6（合理性，sondness）若公式A是系统PC的定理，则A为永真式。若A是公式集的演绎结果，那么A是的逻辑结果。即
若├PC A，则┝ A .
若├PC A，则┝ A .
定理1.7 PC是一致的，即没有公式A使得├PC A与├PC┐A同时成立。
定理1.8 （完备性，completeness）若公式A永真，则A必为PC的定理；若公式A是公式集
的逻辑结果，那么A必为的演绎结果。即
若┝ A，那么├PC A .
若┝ A，那么├PC A .
定理1.9（演绎定理）对任意公式集和公式A，B，├A→B当且仅当
A├ B
（当 = 时，├A→B当且仅当A├ B，或A├ B）
定理1.10 （归谬定理）对任何公式集和公式A，B ,若
┐A├┐B，┐A├ B，
那么├A 。
定理1.11（穷举定理）对任何公式集，公式A，B，若{┐A}├ B，{A}├ B，则
├ B。
1.4.3 自然推理系统ND
ND的描述语言除了使用五个连接词符号以外，与PC系统相同。
ND只用一条公理A∨┐A（A为任意公式）
ND的推理规则可分为三类：
Ⅰ、一般规则：
┐┐规则
A
A A
A
????
,
∧规则
A
B
A
B
B
A
A
B
A,
,
,
∧
∧
∨规则
C
C
B
C
A
B
A
B
A
B
B
A
A→
→
∨
∨
∨
,
,
,
,
→规则B B
A
A→,
规则
B
A
A
B
B
A
A
B
B
A
B
A
B
A
?
→
→
→
?
→
?,
,
,
武大信息安全专业课程简介(一)(2007-05-27 13:18:33) 武大信息安全专业课程简介(一)(2007-05-27 13:18:33) 武大信息安全专业课程简介(一)(2007-05-27 13:18:33) 武大信息安全专业课程简介(一) 2006-12-27 13:12 课程名称（中、英文） 计算机导论 Introduction to Computer 7、课程简介 主要讲授计算机科学与技术学科体系、课程体系、知识结构（包括计算机软件与理论、计算机硬件与网络、计算机应用与信息技术等）、计算机法律、法规和知识产权，计算机学生的择业与职业道德等内容。使学生对所学专业及后续课程的学习有一个整体性、概括性的了解，树立专业学习的信心和自豪感，为今后的学习打下良好的基础。 11、参考书 1）Roberta Baber, Marilyn Meyer,《计算机导论》，汪嘉Min译，清华大学出版社，2000。 2 ) Tony Greening 主编，《21世纪计算机科学教育》，麦中凡等译，高等教育出版社，2001。 3）姚爱国等，《计算机导论》，武汉大学出版社，2003 4) 黄国兴，陶树平，丁岳伟，《计算机导论》，清华大学出版社，2004。 2、课程名称（中、英文） 计算机应用基础
An Introduction to Computer 7、课程简介 本课程是计算机科学与技术、信息安全专业的专业基础必修课。目的是使学生掌握必须的计算机基础知识与基本技能，为后续专业基础和专业课程的学习打下良好的基础。 10、指定教材 《计算机导论》，姚爱国、杜瑞颖、谭成予等编著，武汉大学出版社，2003年。 2、课程名称（中、英文） 电路与电子技术 Circuit and Electrical Technology 7、课程简介 本课程是计算机科学与技术、信息安全专业的专业基础必修课，是学生学习专业知识和从事工程技术工作的理论基础。通过对该课程的学习，让学生掌握各种电路尤其是电路的组成及基本分析方法，为系统学习专业基础和专业知识打下坚实的基础。 10、参考书目 《电路原理》，江缉光主编，清华大学出版社。 《电路原理》，范承志等编，机械工业出版社。 《模拟电子技术基础》，童诗白等主编，清华大学出版社。
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。
武大信息安全专业课程简介(一) 课程名称（中、英文） 计算机导论Introduction to Computer 1、课程简介 主要讲授计算机科学与技术学科体系、课程体系、知识结构（包括计算机软件与理论、计算机硬件与网络、计算机应用与信息技术等）、计算机法律、法规和知识产权，计算机学生的择业与职业道德等内容。使学生对所学专业及后续课程的学习有一个整体性、概括性的了解，树立专业学习的信心和自豪感，为今后的学习打下良好的基础。 2、参考书 1）Roberta Baber, Marilyn Meyer,《计算机导论》，汪嘉Min译，清华大学出版社，2000。 2 ) Tony Greening 主编，《21世纪计算机科学教育》，麦中凡等译，高等教育出版社，2001。3）姚爱国等，《计算机导论》，武汉大学出版社，2003 4) 黄国兴，陶树平，丁岳伟，《计算机导论》，清华大学出版社，2004。 计算机应用基础An Introduction to Computer 1、课程简介 本课程是计算机科学与技术、信息安全专业的专业基础必修课。目的是使学生掌握必须的计算机基础知识与基本技能，为后续专业基础和专业课程的学习打下良好的基础。 2、指定教材 《计算机导论》，姚爱国、杜瑞颖、谭成予等编著，武汉大学出版社，2003年。 电路与电子技术Circuit and Electrical Technology 1、课程简介 本课程是计算机科学与技术、信息安全专业的专业基础必修课，是学生学习专业知识和从事工程技术工作的理论基础。通过对该课程的学习，让学生掌握各种电路尤其是电路的组成及基本分析方法，为系统学习专业基础和专业知识打下坚实的基础。 2、参考书目 《电路原理》，江缉光主编，清华大学出版社。 《电路原理》，范承志等编，机械工业出版社。 《模拟电子技术基础》，童诗白等主编，清华大学出版社。 《电子技术基础》，康华光主编，高等教育出版社。 数字逻辑Digital Logic 1、课程简介 本课程是计算机科学与技术、信息安全专业的专业基础必修课。目的是使学生了解逻辑器件与数字逻辑电路的基本工作原理，能灵活运用逻辑代数、卡诺图、状态理论来研究和分析由逻辑器件构成的数字逻辑电路，掌握计算机应用系统中基本逻辑部件的分析与设计方法，并能熟练选择和使用基本逻辑器件及常用功能器件。本课程是一门实验性较强的课程。 2、指定教材 《电子技术基础》数字部分（第四版），华中理工大学电子学教研室编，高等教育出版 3、参考书目 《逻辑设计》（第二版），毛法尧、欧阳星明、任宏萍编著，华中理工大学出版社。 《数字逻辑与数字系统》，白中英、岳怡、郑岩编，科学出版社，1998。 《数字电子技术基础》（第四版），阎石主编，高等教育出版社。 《数字逻辑》，周南良编，国防科技大学出版社，1992。 计算机组成原理Principles of Computer Construction 本课程是计算机科学与技术、信息安全专业的专业基础必修课。本课程的学习将使学生了解
试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不就是对称的又不就是反对称的关系 R= ;A 上既就是对称的又就是反对称的关系R= 。 5、设代数系统
二、选择 1、在下述公式中就是重言式为( ) A.)()(Q P Q P ∨→∧; B.))()(()(P Q Q P Q P →∧→??; C.Q Q P ∧→?)(; D.)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为 ( )。 A.0; B.1; C.2; D.3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A.3; B.6; C.7; D.8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有( )个分块。 A.4; B.5; C.6; D.9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A.自反性、对称性、传递性; B.反自反性、反对称性; C.反自反性、反对称性、传递性; D.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】
一、填空题 1设集合A,B，其中A＝{1,2,3},B={1,2},则A-B＝____________________; (A)-(B)＝__________________________. 2.设有限集合A,|A|=n,则|(A×A)|=__________________________. 3.设集合A={a,b},B={1,2},则从A到B的所有映射是 _______________________________________,其中双射的是 __________________________. 4.已知命题公式G＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则
常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={
1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设
《现代密码学》教学大纲 课程英文名称：Modern Cryptology 课程编号：010A3350 学时：54 学分：3.0 一、课程教学对象 本课程教学对象为五邑大学数学与计算科学学院信息与计算科学专业和数学与应用数学专业的本科学生。 二、课程性质、目的和任务 课程性质：现代密码学是五邑大学数学与计算科学学院信息与计算科学专业和数学与应用数学专业本科学生选修的专业模块课程。信息化是当今世界经济与社会发展的大趋势，其安全性也成为人们日益关切问题。密码学技术为现代电子商务、网络安全等的必备工具。 目的和任务：本课程旨在介绍流密码学、分组密码学、公钥密码学、数字签名、消息认证和密码协议等，使学生对密码学有一个清晰完整的认识。在本课程的学习过程中，学生要掌握一定的相关的理论基础知识；同时通过阅读参考文献，了解密码学的新发展、新动态，加强知识的深度和广度。通过本课程的学习，学生要了解现代密码学的基本概念，建立信息安全的模型；掌握单钥、公钥密码体制，密钥管理，消息认证和杂凑算法，数字签名和密码协议等密码学的主要内容。 三、对先修课的要求 学生在学习本课之前，应先修课程：数学分析、高等代数、离散数学、概率论与数理统计、初等数论。 四、课程的主要内容、基本要求和学时分配建议（总学时数: 54） 本课程授课计划54学时，其中理论部分44学时，实验10学时。理论部分（44学时）基本要求和安排如 下： 第1章现代密码学概论（5学时） 1.1 信息安全面临的威胁1.2 信息安全的模型 1.3 密码学基本概念 1.4 几种古典密码（C）（C）（A）（A） 第2章流密码（9学时） 2.1 流密码的基本概念 2.2 线性反馈移位寄存器 2.3 线性移位寄存器的一元多项式表示2.4 m序列的伪随机性 2.5 m序列密码的破译 2.6 非线性序列（A）（A）（A）（C）（B）（C） 第3章分组密码体制（4学时） 3.1 分组密码概述 3.2 数据加密标准 3.3 差分密码分析与线性密码分析（A）（C）（C）
离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
习题1.1 1、（1）否 （2）否 （3）是，真值为0 （4）否 （5）是，真值为1 2、（1）P：天下雨 Q：我去教室┐P → Q （2）P：你去教室 Q：我去图书馆 P → Q （3）P，Q同（2） Q → P （4）P：2是质数 Q：2是偶数 P∧Q 3、（1）0 （2）0 （3）1 4、（1）如果明天是晴天，那么我去教室或图书馆。 （2）如果我去教室，那么明天不是晴天，我也不去图书馆。 （3）明天是晴天，并且我不去教室，当且仅当我去图书馆。 习题1.2 1、（1）是 （2）是 （3）否 （4）是 （5）是 （6）否 2、（1）(P → Q) →R，P → Q，R，P，Q （2）(┐P∨Q) ∨（R∧P），┐P ∨ Q，R∧P，┐P，Q，R，P （3）((P → Q) ∧ (Q → P)) ∨┐(P → Q))，(P → Q) ∧(Q → P)，┐(P → Q)，P → Q，(Q → P)，P → Q，P，Q，Q，P，P，Q 3、（1）((P → Q) → (Q → P)) → (P → Q) （2）((P → Q) ∨ ((P → Q) → R))→ ((P → Q) ∧ ((P → Q) → R)) （3）(Q → P∧┐P) → (P∧┐P → Q) 4、(P → Q) ∨ ((P∧Q) ∨ (┐P∧┐Q)) ∧ (┐P∨Q) 习题1.3
1、（1）I(P∨(Q∧R)) = I(P)∨(I(Q)∧I(R)) = 1∨(1∧0) = 1 （2）I((P∧Q∧R)∨(┐(P∨Q)∧┐(R∨S))) = (1∧1∧0)∨(┐(1∨1)∧┐(0∨1)) = 0∨(0∧0) = 0 （3）I((P←→R)∧(┐Q→S)) = (1←→0)∧(┐1→1) = 0∧1 = 0 （4）I((P∨(Q→R∧┐P))←→(Q∨┐S)) = (1∨(1→(0∧┐1)))←→(1∨┐1) = 1←→1 = 1 （5）I(┐(P∧Q)∨┐R∨((Q←→┐P)→R∨┐S)) = ┐(1∧1)∨┐0∨((1←→┐1)→(0∨┐1)) = 0∨1∨1 = 1 3、（1）原式 <=> F→Q <=> T 原式为永真式 （2）原式 <=> ┐T∨(┐(┐P∨Q)∨(┐┐Q∨┐P)) <=> (P∧┐Q)∨(Q∨┐P)
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q →P (2)?Q=>P →Q (3)P=>P →Q (4)?P ∧(P ∨Q)=>?P 答：（1），（4） 2、下列公式中哪些是永真式？( ) (1)(┐P ∧Q)→(Q →?R) (2)P →(Q →Q) (3)(P ∧Q)→P (4)P →(P ∨Q) 答：（2），（3），（4） 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P ∧Q (2) P ∧Q=>P (3) P ∧Q=>P ∨Q (4)P ∧(P →Q)=>Q (5) ?(P →Q)=>P (6) ?P ∧(P ∨Q)=>?P 答：（2），（3），（4），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！
离散数学 1.在自然推理系统P 中构造下面推理的证明： 前提：,,p q r q r s ?∨∨?→ 结论：p s →. 3设一阶逻辑公式 ((,)(()()))G x yP x y zQ z R x =???→?→ 试将G 化成与其等价的前束范式。 4.判断下面推理是否正确，并证明你的结论。 如果小王今天家里有事，则他不会来开会。 如果小张今天看到小王，则小王今天来开会了。 小张今天看到小王。所以小王今天家里没事。 5、构造下面推理的证明 前提： ))()(()),()()((x R x F x x H x G x F x ∧?∧→? 结论: ))()()((x G x R x F x ∧∧? 6用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ??→∧→=的类型。 7分别用真值表法和公式法求(P →(Q ∨R ))∧(?P ∨(Q ?R ))的主析取范式 ，并写出其相应的成真赋值和成假赋值。 8用逻辑推理证明： 所有的舞蹈者都很有风度，王华是个学生且是个舞蹈者。因此有些学生很有风度。 9、设A ＝{?，1，{1}}，B ＝{0，{0}}，求P (A )、P (B )－{0}、P (B )⊕B 。 10、设X ＝{1，2，3，4}，R 是X 上的二元关系，R ＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)画出R 的关系图。 (2)写出R 的关系矩阵。 (3)说明R 是否是自反、反自反、对称、传递的。 11、集合X={<1,2>, <3,4>, <5,6>,… }，R={<
这个问题与空气动力学有关，飞行器说白了就是纸飞机... 1.飞机前端叠的尖,减少阻力 2.外纸的选择很重要，要硬些，有弹性为好，动力要想快，就必须有足够的重量，所以要选弹性好，硬度好的纸张来做！这个它又没说标准A4，呵 3.飞行原理： 飞机机翼，横切来看下面是平的，上面较弯曲，这样一来当飞机高速运动时机翼上空气流动的速度就比机翼下方要快。这样一来，机翼下面的气压就比上面的大，从而产生一股上升的力把飞机托起。 一个好的纸飞机，一般需要加上“升降板”也就是2个标签贴（机翼上折出的小块“多余”－用来调整机翼上下气流的速度），用来调整飞机的飞行。如果左边升降版高，飞机则倾向左边飞，反之亦然。一般把升降版调成45度，太高了飞机会上升太快，最后“坠毁”，太低了飞机则无法向上飞行，坠落也很快。一架好的纸飞机，无论什么形状，最重要的是对称，平滑（阻力小），机翼和升降版的角度正确。如果机翼比较宽大，能飞行的时间就会常一些，当然，前提是你要把它抛高一点，升降板也要稍微调高一点，但是如果太高了，飞机就会打转了。如果把机翼调整得窄一点，短一点，阻力就大大地减小了，飞行的速度就会变快。在这种情况下，要想飞远一点，飞久一点就挺考验人的了，一般是把升降版调得稍低一点点，掷飞机时的力度也要掌握好，这可就是看经验了。 4.航向尽可能笔直等，多参考纸飞机如何飞的远， 比赛成绩既然是按飞行垂直距离乘以飞行时间作为单次分数...那么你就要多做 几个，多实验，根据上面的原理多做几个不同的飞机，多次实验投掷角度，投掷力度，争取达到最好的效果... 纸张：飞机 标签贴：升降板 回形针：固定 吸管：我估计和航向有关 小小游戏富含深刻道理，就是这些了，楼主悬赏多多哦.......... 64 向TA求助 回答者：775901421|三级采纳率：33% 擅长领域：暂未定制 参加的活动：暂时没有参加的活动 提问者对于答案的评价： 能具体点怎么做吗第一次做看得不太懂
编 号 题目 答案 题型 分值 大纲 难度 1 1 设集合A={a ，b ，c ，d}上的关系R={ ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R 的传递闭包t (R)。 答: ?? ? ???? ??=0000100001010010R M ， ???? ?? ? ??==00000000101 0010 12R R R M M M ?? ? ?? ? ? ? ?==000000000101 1010 23R R R M M M ?? ? ?? ? ? ? ?==000000001010 0101 3 4R R R M M M ?? ? ? ? ? ? ? ?=+++=0000100011111111 4 32)(R R R R R t M M M M M ∴t (R)={ , , < a , c> , , , < b ,b > , < b , c . > , < b , d > , < c , d > } 简答题 8 4.3 3 2 如下图所示的赋权图表示某七个城市721,,,v v v 及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 答: 用Kruskal 算法求产生的最优树。算法略。结果如图： 树权C(T)=23+1+4+9+3+17=57即为总造价。 简答题 8 7.2 3
3设
计算机科学与技术专业书名册 大学一年级： 基础课以及通识课包括：高等数学、现性代数、大学英语、计算机导论等。 大学二年级： 课程名称专业性质教材名称 C++程序设计专业选修《面向对象程序设计（C++语言）》 Linux原理与应用专业选修《Linux原理与应用》 Oracle数据库应用专业选修《Oracle 11g应用与认证教程》 Windows原理与应用专业选修《Windows原理与应用》 编译原理专业必修《编译原理》 操作系统设计专业必修 大型应用软件设计专业必修 计算机安全保密专业选修《计算机安全与实用密码学》 计算机图形学专业选修交互式计算机图形学--基于OpenGL的自顶向下计算机外部设备专业选修《微机硬件基础》 计算机网络与通信原理专业必修《计算机网络》 计算机系统结构专业必修《计算机系统结构》 面向对象软件工程专业选修《面向对象软件工程》 数据库系统实现专业选修《数据库系统实现（英文版）》 算法设计与分析专业选修《算法设计技巧与分析》 大学三年级： 课程名教材 计算机组成原理《计算机组成与结构》（第4版）王爱英离散数学《离散数学》刘玉珍 数据结构《数据结构教程(第4版)》李春葆 C++程序设计《面向对象程序设计（C++语言）》李爱华Linux原理与应用《Linux原理与应用》郑鹏 Oracle数据库应用《Oracle 11g应用与认证教程》宋钰、汪洋编译原理《编译原理》何炎祥传感器微操作系统原理与设计《无线传感器网络操作系统TinyOS》潘浩、存储技术基础《信息存储与管理：数字信息的存储、管理和 计算机安全保密《计算机安全与实用密码学》李克洪
计算机图形学交互式计算机图形学--基于OpenGL的自顶向下计算机外部设备《微机硬件基础》宁闽南 计算机网络与通信原理《计算机网络》黄传河计算机系统结构《计算机系统结构》高辉 面向对象程序设计《面向对象与java程序设计》朱福喜 面向对象软件工程面向对象软件工程:使用UML、模式与Java(第3版)》清华版叶俊民， 汪望珠等译 嵌入式系统《嵌入式系统原理与应用技术》袁志勇 软件安全《计算机病毒分析与对抗（第二版）》傅建? 数据库系统实现《数据库系统实现（英文版）》 算法设计与分析《算法设计技巧与分析》吴伟昶网络安全《网络安全》黄传河 物联网控制原理与技术《自动控制原理》孟庆明物联网软件设计《实用软件设计模式教程》徐宏喆 信息系统安全《计算机系统安全第二版》曹天杰 信息隐藏技术《信息隐藏技术与应用》王丽娜 智能卡技术《智能卡技术》王爱英
15.设D的结点数大于1，D=
数理逻辑习题 判断题 1．任何命题公式存在惟一的特异析取范式 （ √ ） 2． 公式)(q p p →?→是永真式 （ √ ） 3．命题公式p q p →∧)(是永真式 （ √ ） 4．命题公式r q p ∧?∧的成真赋值为010 （ × ） 5．))(()(B x A x B x xA →?=→? （ √ ） 6．命题“如果1＋2＝3，则雪是黑的”是真命题 （ × ） 7．p q p p =∧∨)( （ √ ） 8．))()((x G x F x →?是永真式 （ × ） 9．“我正在撒谎”是命题 （ × ） 10． )()(x xG x xF ?→?是永真式（ √ ） 11．命题“如果1＋2＝0，则雪是黑的”是假命题 （ × ） 12．p q p p =∨∧)( （ √ ） 13．))()((x G x F x →?是永假式 （ × ） 14．每个命题公式都有唯一的特异（主）合取范式 （ √ ） 15．若雪是黑色的:p ，则q →p 公式是永真式 （ √ ） 16．每个逻辑公式都有唯一的前束范式 （ × ） 17．q →p 公式的特异（主）析取式为q p ∨? （ × ） 18．命题公式 )(r q p →∨?的成假赋值是110 （ √ ） 19．一阶逻辑公式)),()((y x G x F x →?是闭式（ × ） 单项选择题 1． 下述不是命题的是（ A ）
A ． 花儿真美啊! B ． 明天是阴天。 C ． 2是偶数。 D ． 铅球是方的。 2．谓词公式（?y ）（?x ）（P （x ）→R （x,y ））∧?yQ （x,y ）中变元y （ B ） A ． 是自由变元但不是约束变元 B ． 是约束变元但不是自由变元 C ． 既是自由变元又是约束变元 D ． 既不是自由变元又不是约束变元 3．下列命题公式为重言式的是（ A ） A ．p→ （p ∨q ） B ．（p ∨┐p ）→q C ．q ∧┐q D ．p→┐q 4． 下列语句中不是．．命题的只有（ A ） A ．花儿为什么这样红？ B ．2+2=0 C ．飞碟来自地球外的星球。 D ．凡石头都可练成金。 5．在公式),()())(),()()((z y P y z Q y x P y x ?→∧??中变元y 是（ B ） A ．自由变元 B ．约束变元 C ．既是自由变元，又是约束变元 D ．既不是自由变元，又不是约束变元 6．下列命题公式为重言式的是（ A ） A ．p→ （p ∨q ） B ．（p ∨┐p ）→q C ．q ∧┐q D ．q→┐p 7．给定如下4个语句: （1）我不会唱歌。 （2）如果天不下雨,我就上街。 （3）我每天都要上课。 （4）火星上有人吗? 其中不是复合命题的是（ B ） A ．（1）（4） B ．（3）（4） C ．（1）（3） D ．（1）（3）（4） 8．下列含有命题p ，q ，r 的公式中，是特异（主）析取范式的是 （ D ） A ．（p ∧ q ∧ r ） ∨ （?p ∧ q ） B ．（p ∨ q ∨ r ） ∧ （?p ∧ q ） C ．（p ∨ q ∨ r ） ∧ （?p ∨ q ∨ r ） D ．（p ∧ q ∧ r ） ∨ （?p ∧ q ∧ r ） 9．设个体域为整数集,则下列公式中值为真的是（ A ）。 A ． （?y ）（?x ）（x ·y=2） B ．（?x ）（?y ）（x ·y=2） C ． （?x ）（x －y=x ） D ．（?x ）（ ?y ）（x+y=2y ） 10． 下述不是命题的是（ D ）