离散数学习题答案
习题一
1、利用逻辑联结词把下列命题翻译成符号逻辑形式
（1）他既是本片的编剧，又是导演--- P∧ Q
（2）银行利率一降低，股价随之上扬--- P→ Q
（3）尽管银行利率降低，股价却没有上扬--- P∧ Q
（4）占据空间的、有质量而且不断变化的对象称为物质--- M ←→(S∧P∧T) （5）他今天不是乘火车去北京，就是随旅行团去了九寨沟--- P▽ Q
（6）小张身体单薄，但是极少生病，并且头脑好使--- P∧ Q ∧ R
（7）不识庐山真面目，只缘身在此山中--- P→ Q （解释：因为身在此山中，所以不识庐山真面目）
（8）两个三角形相似，当且仅当他们的对应角相等或者对应边成比例
--- S ←→(E∨T)
（9）如果一个整数能被6整除，那么它就能被2和3整除。如果一个整数能被3整除，那么它的各位数字之和也能被3整除
解：设 P –一个整数能被6整除Q –一个整数能被2整除 R –一个整数能被3整除S –一个整数各位数字之和能被3整除
翻译为：（P→（Q ∧ R））∧（R→ S）
2、判别下面各语句是否命题，如果是命题，说出它的真值
（1）BASIC语言是最完美的程序设计语言--- Y，T/F
（2）这件事大概是小王干的--- N
（3）x2 = 64 --- N
（4）可导的实函数都是连续函数--- Y，T/F
（5）我们要发扬连续作战的作风，再接再厉，争取更大的胜利--- N
（6）客观规律是不以人们意志为转移的--- Y，T
（7）到2020年，中国的国民生产总值将赶上和超过美国--- Y，N/A
（8）凡事都有例外--- Y，F
3、构造下列公式的真值表，并由此判别哪些公式是永真式、矛盾式或可满足式
（1）（P∨（～P∧ Q））→ Q
解：
4、利用真值表方法验证下列各式为永真式
（1）~（8）略
5、证明下列各等价式
（3）P→（Q∨ R）?（P→ Q）∨（P→ R）
证明：左式?～P∨Q∨ R
?～P∨Q∨～P∨ R
?（～P∨Q）∨（～P∨ R）
?（P→ Q）∨（P→ R）?右式
（4）（P∧ Q）∨（R∧ Q）∨（R∧ P）?（P∨ Q）∧（R∨ Q）∧（R∨ P）
证明：左式?(（P∨R）∧ Q）∨（R∧ P）
?(（P∨R）∨R))∧(（P∨R）∨P))∧（Q∨R）∧（Q∨P）
?（P∨ Q）∧（R∨ Q）∧（R∨ P）?右式
6、如果P∨ Q ? Q∨R,能否断定 P ? R ？如果P∧ Q ? Q∧R，能否断定 P ? R？如果～P ?～R，能否断定 P ? R？
解：（1）如果P∨ Q ?Q∨R，不能判断P ?R，因为如果 Q = P∨ R, 那么P∨ Q?P ∨P∨ R ? Q∨R，但P可以不等价于R.
（2）如果P∧ Q ?Q∧R，不能判断P ?R，因为如果 Q = P∧ R, 那么P∧ Q?P ∧P∧ R ? Q∧R，但P可以不等价于R.
（3）如果～P ?～R，那么有P ? R，因为～P ?～R，则～P <-> ～R为永真式，及有P <-> R为永真式，所以P ? R.
8、把下列各式用↑等价表示出来
（1）(P∧Q)∨～P
解：原式? ((P↑Q)↑(P↑Q))∨(P↑P)
? (((P↑Q)↑(P↑Q))↑((P↑Q)↑(P↑Q)))↑((P↑P)↑(P↑P))
9、证明：{ ～→}是最小功能完备集合
证明: 因为{～,∨}是最小功能完备集合,所以,如果{ ～→}能表示出∨,则其是功能完备集合。由于 P ∨ Q ? (～P)→Q ,所以{ ～→}是功能完备集合。因为～→不能相互表示，所以{ ～→}是最小功能完备集合；同理可证：{非，条件非}也能将或表示出来：P ∨ Q ?～(～P !→ Q)
8、分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式:
(3) P→(R∧(Q→P))
解：真值表法
主合取范式为 = (～P∨Q∨R)∧(～P∨～Q∨R) = M4∧M6
主析取范式为 = (～P∧～Q∧～R)∨(～P∧～Q∧R)∨(～P∧Q∧～R)∨(～P∧Q∧R)∨(P ∧～Q∧R)∨(P∧Q∧R) = m0∨m1∨m2∨m3∨m5∨m7
等价变换法（略）
(4) (P→(Q∧R))∧(～P→(～Q∧～R))
解：真值表法
主合取范式为 = (P∨Q∨～R)∧(P∨～Q∨R)∧(P∨～Q∨～R)∧(～P∨Q∨R)∧(～P∨Q ∨～R)∧(～P∨～Q∨R) = M1∧M2∧M3∧M4∧M5∧M6
主析取范式为 = (～P∧～Q∧～R)∨(P∧Q∧R) = m0∨m7
等价变换法（略）
14、从A,B,C,D 4个人中派2人出差，要求满足下列条件：如果A去，则必须在C或D中选一人同去；B和C不能同时去；C和D不能同时去。用构造范式的方法决定选派方案。
解：由题设 A：A去，B：B去，C：C去，D：D去则满足条件的选派应满足如下范式：
（A→（C?D））∧～（B∧C）∧～（C∧D）
构造和以上范式等价的主析取范式
（A→（C?D））∧～（B∧C）∧～（C∧D）
?（～A∧～B∧～C ∧D ）∨（～A∧～B∧～C∧～D）∨（～A∧～B∧C∧～D）∨（～A ∧B∧～C∧～D）∨（A∧～B∧C∧～D）∨（A∧～B∧～C∧D）∨（～A∧B∧～C∧D）∨（A ∧B∧～C∧D）
共有八个极小项，但根据题意，需派两人出差，所以，只有其中三项满足要求：
（A∧～B∧C∧～D），（A∧～B∧～C∧D），（～A∧B∧～C∧D）
即有三种方案：A和C去或者A和D去或者B和D去。
15、证明下列蕴含试：
（1）P→Q=>P →(P∧Q)
证明：P→Q ?～P∨Q ? T∧(～P∨Q) ? (～P∨P)∧(～P∨Q) ?～P∨(P∧Q)
? P →(P∧Q)
所以，这是个等价式，因此也是个蕴含式
（2）(P→Q) →Q=> (P∨Q)
证明：(P→Q) →Q ?～(～P∨Q) ∨Q ? (P∧～Q) ∨Q ? (P∨Q) ∧(Q∨～Q) ? (P∨Q) ∧T ? (P∨Q)
所以，这是个等价式，因此也是个蕴含式
（3）P∧～P∧R=>S
证明：P∧～P∧R ? F => S (F可蕴含任何命题公式)
（4）P=>Q∨R∨～R
证明：P=>T ?Q∨R∨～R （任何公式可蕴含永真式）
18、一个有钱人生前留下了一笔珍宝，藏在一个隐秘处。在他留下的遗嘱中指出寻找珍宝的线索如下：
（1）如果藏宝的房子靠近池塘，那么珍宝不会藏在东厢房。
（2）如果房子的前院栽有大柏树，那么珍宝就藏在东厢房。
（3）藏宝房子靠近池塘。
（4）要么前院栽有大柏树，要么珍宝埋在花园正中地下。
（5）如果后院栽有香樟树，珍宝藏在附近。
请利用蕴含关系找出藏宝处
解：根据给定的条件有下述命题：
P：珍宝藏在东厢房
Q：藏宝的房子靠近池塘
R：房子的前院栽有大柏树
S：珍宝藏在花园正中地下
T：后院栽有香樟树
M：珍宝藏在附近
根据题意，得出：
（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M）?？
（Q→～P）∧（R→P）∧Q∧（R∨S）∧（T→M）
?～P∧（R→P）∧（R∨S）∧（T→M）
?～R∧（R∨S）∧（T→M）
?S∧（T→M）
?S 即珍宝藏在花园正中地下
20、演绎证明下面各蕴含式：
（4）(R→Q)∧(R→S),(Q→E)∧(S→B),～(E∧B),(P→R) ?～P
证明：运用反证方法，将结论的非纳入前提，证明步骤如下
[1] P p(附加前提)
[2] P→R p
[3] R T [1,2] I
[4] (R→Q)∧(R→S) p
[5] Q∧S T [3,4] I
[6] (Q→E)∧(S→B) p
[7] E∧B T [5,6] I
[8] ～(E∧B) p
[9] F(矛盾式) T [7,8] E
（5）P→(Q→R),Q→(R→S) ? P→(Q→S)
证明：运用cp法，将结论条件式的前件作为前提，证明步骤如下
[1] P p(附加前提)
[2] P→(Q→R) p
[3] Q→R T [1,2] I
[4] Q→(R→S) p
[5] R→(Q→S) T [4] E
[6] Q→S T [3,5] I
[7] P→(Q→S) CP [1,6]
21、把下列句子演绎成逻辑形式，并给出证明
（2）某公司发生了一起盗窃案，经仔细侦察，掌握了如下一些事实：
●被盗现场没有留下任何痕迹
●失盗时，小花或则小英正在卡拉ok厅
●如果失窃时小胖正在附近，他就会习惯性地破门而入偷走东西后扬长而去
●如果失盗时小花正在卡拉ok厅唱歌，那么金刚是最大的嫌疑者
●如果失盗时小胖不在附近，那么他的女友小英会和他一起外出旅游
●如果失盗时小英正在卡拉ok厅唱歌，那么瘦子是最大的嫌疑者
根据以上事实，请通过演绎推理找出偷窃者
解：根据给定的条件有下述命题：
P：现场无任何痕迹
Q：失窃时，小花在OK厅
R：失窃时，小英在OK厅
S：失窃时，小胖在附近
T：金刚是偷窃者
M：瘦子是偷窃者
则根据案情有如下命题公式：
{P，Q∨R，S→～P，Q→T，～S→～R，R→M}
①P P
②S→～P P
③～S T①②I
④～S→～R P
⑤～R T③④I
⑥Q∨R P
⑦Q T⑤⑥I
⑧Q→T P
⑨T T⑦⑧I
即金刚是偷窃者
23、利用消解法证明下列各蕴含式：
（3）P→(Q→R),Q→(R→S)? P→(Q→S)
证明：P→(Q→R) ?～P∨～Q∨R
Q→(R→S) ?～Q∨～R∨S
～（P→(Q→S)）? P∧Q∧～S
因此子句集合 = { ～P∨～Q∨R，～Q∨～R∨S，P，Q，～S }
消解过程如下：
[1] ～P∨～Q∨R p
[2] P p
[3] ～Q∨R 由[1，2]归结
[4] Q p
[5] R 由[3，4]归结
[6] ～Q∨～R∨S p
[7] ～S p
[8] ～Q∨～R 由[6，7]归结
[9] ～R 由[4，8]归结
[10] FLASE □由[5，9]归结
导出空子句
习题二
1、把下列谓词翻译成谓词公式
（1）每个有理数都是实数，但是并非每个实数都是有理数，有些实数是有理数解：R(x) -- x是实数
Ra(x) -- x是有利数
翻译如下：?(x)( Ra(x)→R(x))∧～?(x)( R(x)→Ra(x))∧?(x)( R(x))∧Ra(x)）（2）直线a和b平行当切仅当a和b不相交
解：A(x) -- x是直线
F(x，y) -- x与y平行
G（x,y) -- ｘ与ｙ相交
翻译如下：?(ａ)?(ｂ)（A(ａ)∧A(ｂ)→(F(ａ，ｂ)?～G（ａ,ｂ)）)
（3）除非所有的会员都参加，这个活动才有意义
解：A(x) -- ｘ是会员
B(x) -- x有意义ａ-- 这个活动
F(x，y) -- ｘ参加ｙ
翻译如下：B（ａ）→?(x)（A(x)→F(x，ａ)）
或～?(x)（A(x)→F(x，ａ)）→～B（ａ）
（4）任何正整数不是合数就是质数
解：A(x) -- ｘ是正整数
Ｂ(x) -- ｘ是合数
Ｃ(x) -- ｘ是质数
翻译如下：?(x)（A(x)→Ｂ(x)?Ｃ(x)）
（6）凡是存钱的人都想有利息，如果没有利息，人们就不会存钱
解：A(x) -- ｘ是存钱的人
F(x，y) -- ｘ想有ｙ
P -- 存钱没有利息
Q: -- 人们不存钱
a: -- 利息
翻译如下：?(x)（A(x)→F(x，a)）∧（P→Q）
2、设论域D = {0, 1, 2}，把下列公式用不含量词的公式表示出来
（3）?(x)[～P(x)]∨?(x)Q(x)
解：上式?（～P(0)∧～P(1)∧～P(2)）∨Q(0)∨Q(1)∨Q(2)
3、指出下列公式中的约束变元和自由变元，并确定公式的辖域
解：略
5、把下列语句符号化，并确定相应谓词公式是永真式、可满足式、还是矛盾式
（1）如果两个数的积等于0，那么至少其中一个数为0，数x-1不等于0，所以数x-1和x+1的积也不等于0
解：设论域在任意数域集合，运用常规的数学符号，翻译如下
?(x)?(y)( xy = 0 →(x=0 ∨y=0)) ∧((x-1 ≠0) →((x-1)(x+1)≠0))
这是一个可满足式，但不是永真式，因为存在x=-1时，谓词公式不成立，但其它情况均成立，如果论域中不包含-1，为真，包含就不成立
（2）诚实的人都讲实话。小林不是诚实的，因而小林不讲实话
解：H(x) -- x诚实
T(x) -- x讲真话
a -- 小林
翻译如下：
（?(x)(H(x)→T(x))∧～H(a)）→～T(a)
这是一个可满足式，因为否定条件命题前件，不一定后件命题一定为假。及小林虽然不诚实，但也可能讲实话
6、对于题目给定的解释，求下列各公式相应的真值
（1）A = ?(x)[P(x)∨Q(x)]∧R(a)，解释D ={1,2,3}，P(x): x2+x=2; Q(x): x是素数；R(x): x<3;
a = 1
解：根据解释，A变为（P(1)∨Q(1)）∧（P(2)∨Q(2)）∧（P(3)∨Q(2)）∧R(1)，根据P(x), Q(x), R(x)的定义，显然P(1)∨Q(1) = 1，P(2)∨Q(2) = 1，P(3)∨Q(2) = 1，R(1) =1，所以整个公式解释为真
（2）A=P(a, f(b))∧P(b,f(a)), B=?(x)?(y)P(y,x), C = ?(y)?(x)P(y,x), E = ?(x)?(y)[P(x,y)→P(f(x),f(y))]，解释：D={2,3}, a = 3, b = 2, f(2)=3, f(3) =2，P(2,2)=0, P(2,3)=0, P(3,2)=P(3,3) = 1 解：根据解释，
A变为P( 3, 3 ) ∧P( 2, 2 ) = 1 ∧0 = 0 ，真值为假
B变为(P(2,2)∨P(2,3))∧(P(3,2)∨P(3,3)) = （0∨0）∧（1∨1）= 0，真值为假
C变为(P(2,2)∧P(2,3))∨(P(3,2)∧P(3,3)) = （0∧0）∨（1∧1）= 1，真值为真
E变为(P(2,2)→P(3,3))∧(P(2,3)→P(3,2))∧(P(3,2)→P(2,3))∧(P(3,3)→P(2,2)) = （0→1）∧（0→1）∧（1→0）∧（1→0）= 0，真值为假
7、设论域为整数集合Z，试判定下面各公式是否是永真式，矛盾式或可满足式
（1）?(x)[x>-10∧x2≥0]
答：为假命题
（2）?(x)[2x>8∧x2-6x+5≤0]
答：为真命题，当4，5使满足谓词公式
（3）?(x)?(y)[x+y=1024]
答：为真命题，对任意整数x，y取值为1024-x及可
（4）?(y)?(x)[xy<10∨x+y≥2]
答：为真命题，y=0及成立
9、证明下列各式成立：
（1）?(x)?(y)[P(x)→Q(y)] ??(x)P(x)→?(y)Q(y)
证明：右式??(x)?(y)[~P(x)∨Q(y)] ??(x)~P(x)∨?(y)Q(y)??(x)P(x)→?(y)Q(y)
10、判别?(x)[P(x) →Q(x)]??(x)P(x)→?(x)Q(x)是否成立，如果成立，请给出证明；如果不成立，找一个解释予以说明
解：?(x)[P(x)→Q(x)] ??(x)[～P(x)∨Q(x)] ??(x)～P(x)∨?(x)Q(x) ??(x)P(x)→?(x)Q(x) 显然和?(x)P(x)→?(x)Q(x)不等价，现构造如下解释
设论域为D={a,b}，P(a) = 0, P(b) = 1, Q(a) = 0, Q(b) = 0, 则?(x)[P(x)→Q(x)]解释为真，而?(x)P(x)→?(x)Q(x)解释为假，所以不等价
11、把下列公式化为等价的前束范式，再求出对应的SKolem范式
（4）?(x)[～P(x,0)→(?(y)P(y,f(x))∧?(z)Q(x,z))]
解：原式??(x)[P(x,0)∨(?(y)P(y,f(x))∧?(z)Q(x,z))] ??(x)?(y) ?(z) [P(x,0)∨(P(y,f(x))∧Q(x,z))]
其SKolem范式为：?(x)?(z) [P(x,0)∨(P(g(x),f(x))∧Q(x,z))]
13、证明下列各式成立
（1）?(x)?(y)[P(x)∧Q(y)]??(x)P(x)
证明：左式??(x)P(x)∧?(y)Q(y) ??(x)P(x)
（2）~(?(x)P(x)∧Q(a))??(x)P(x)→~Q(a)
证明：左式? ~?(x)P(x)∨~Q(a) ??(x)P(x)→~Q(a)
15、下面给出了对?(x) [P(x) ∨Q(x)]??(x) P(x) ∨?(x)Q(x)]的证明：
（原证明过程略）
试判断这个证明是否正确。你能给出一个证明吗？
答：这个证明不正确，因为：如果P ?Q 则~Q?~P 而~P ?~Q不一定成立，因此在这个证明过程中，第二步到第三步的蕴含不成立
17、判别下面各个推理是否正确，如果不正确，指出错在什么地方（题目不再重复）
（1）答：不正确，全称指定应该变为其他非x的变元，可修改为：P(y)→Q(x)
（2）答：正确
（3）答：不正确，全称指定应该使用相同的个体常量，可修改为：P(a)∨Q(a)
（4）答：题目不正确，存在量词的指导变元应该是另外的变元符号
（5）答：不正确，存在量词的辖域应该包含全部的谓词，可修改为：?(x)[P(x)→Q(x) ] （6）答：不正确，对不同的个体常元应该用不同的变元进行存在指定，可修改为：?(x)[P(x)→Q(b) ]
（7）答：不正确，推理过程中，应该先使用存在指定，然后使用全称指定
习题三
4、仔细区分集合中的关系符号∈和?，并判断下列各蕴含关系的真假
（题目内容，见课本）
（1）真，根据子集的定义，任何属于B集合的元素也属于C集合
（2）假，例如：A = {1,2} B = {{1,2}, 2, 3} C=B，1属于A，但并不是C集的元素
（3）假，例如：A={1,2} B={1,2,3} C={{1,2,3}}，A不是C的元素
（4）假，例如：A={1,2} B={1,2,3} C={{1,2,3}}，A不是C的子集
（5）假，例如：A=1 B={1,2,3} C={{1,2,3}}，A不是C的元素
（6）真，子集关系具有传递性
9、证明下列各式
（1）A∩(B-C) = (A∩B)-(A∩C)
证明：左式= A∩(B∩~C) = (A∩B∩~C) ∪(A∩B∩~A) = (A∩B) ∩(~C∪~A) = (A∩B) ∩~ (A∩C) = (A∩B)-(A∩C) =右式
（2）A - (B∪C) = (A-B) ∩(A-C)
证明：右式 = (A∩~B)∩(A∩~C) = A∩~B∩~C = A∩~(B∪C) = A - (B∪C) = 左式
（3）(A-B)-C = A-(B∪C)=(A-C)-B
证明：(A-B)-C = A∩~B∩~C = A∩~(B∪C) = A-(B∪C) = A∩~C∩~B = (A-C)-B
（4）A∩(B∪C)=(A∩B)∪C ?C?A
证明：充分性
∵A∩(B∪C)=(A∩B)∪C ?(A∩B)∪(A∩C) = (A∩B)∪C
假设C不是A的子集，则C中必存在元素c在C中而不在A中，那么c一定不在等式的左端集合中，而一定在右端集合中，矛盾
∴C?A
必要性
∵C?A ，∴A∩C = C ，等式两端同时并上另一个集合，等式成立
∴(A∩B)∪(A∩C) = (A∩B)∪C ?A∩(B∪C)=(A∩B)∪C
（5）A∩(B⊕C) = (A∩B)⊕(A∩C)
证明：左式= A∩（B ∪C-B∩C）= A∩（(B ∪C) ∩(~B∪~C)）= A∩(B ∪C) ∩(~B∪~C)=AB~C + AC~B
右式 = （(A∩B)∪(A∩C)）- （(A∩B)∩(A∩C)）= （A∩(B∪C)）∩~（A∩B∩C）=A ∩(B∪C)∩(~A∪~B∪~C) = AB~C + AC~B
所以，左式= 右式
10、下面三式中，哪个可得出B=C的结论
（1）A∪B=A∪C
答：不能得出此结论，因为如果B≠ C,但B,C都是A的子集，A∪B=A∪C成立
（2）A∩B=A∩C
答：不能得出此结论，因为B≠ C，但A是C∩B子集，A∩B=A∩C成立
（2）A⊕B=A⊕C
答：能，因为A⊕A = Φ,Φ⊕A = A⊕Φ=A,同时，（A⊕B）⊕C = A⊕（B⊕C）
所以，已知等式两端A⊕A⊕B=A⊕A⊕C ?Φ⊕B =Φ⊕C ? B=C
16、求A={?, a, {b}}的幂集
解：2A = {?, {?} , {a} , {{b}} , {?,a} , {?,{b}} , {a, {b}} , {?, a, {b}}}
17、设A,B是任意两集合，证明
（1）2A? 2B?2 A? B，给出等号成立的条件
证明：X ∈2A? 2B? X ∈2A∨ X ∈ 2B
? X ? A ∨ X ? B
=> X ? A ? B
? X ∈2 A? B
等号成立的条件: A ? B或B ? A
(因为若A和B没有子集关系, 必有a ∈A–B和 b ∈B–A，使{a, b} ∈2 A?B，但{a, b} ?2A?2B )
（2）2A? 2B = 2 A? B
证明：X ∈2A? 2B? X ∈2A∧ X ∈2B
? X ? A ∧ X ? B
? X ? A ? B
? X ∈2 A? B
附加题：
证明等式(A⊕B) ⊕C = A⊕(B⊕C)
证明：A⊕(B⊕C) = A⊕((B-C)∪(C-B)) = (A - ((B-C)∪(C-B))) ∪(((B-C)∪(C-B))- A) = ~AB~C + ~A~BC + A~B~C + ABC
(A⊕B) ⊕C = C⊕(A⊕B)
那么按上式的划简方式，就是把C替换为A, 把A替换为B,将B替换为C,所以
C⊕(A⊕B) = ~CA~B + ~C~AB + C~A~B + CAB = ~AB~C + ~A~BC + A~B~C + ABC习题四
1、设A={1,2,3,4},B={0,1,4,9,12}.分别把下面定义的从集合A到集合B的二元关系R用序偶的集合表示出来
（1）xRy ?x|y
解: R = {(1,0) ,(1,1),(1,4) ,(1,9) ,(1,12) ,(2,0) ,(2,4) ,(2,12) , (3,0) ,(3,9) ,(3,12) ,(4,0) ,(4,4) ,(4,12)}
（2）xRy ? x≡y(mod 3)
解: R ={(1,1), (1,4) , (3,0) , (3,9) , (3,12) , (4,1) , (4,4)}
（3）xRy ? y/x ≤∟(y-x)/2」
解: R ={(3,9), (3,12) , (4,9) , (4,12)}
2、用关系图和关系矩阵表示第1题中的各个关系
解：略
6、设在整数集Z上定义如下二元关系，试填写下表：
解：填表如下
(1)因为x|x成立，所以自反性成立；所以反自反性不成立；因为x≠0时，x|0成立，但
0|x不成立，所以对称性不成立，因为 1|-1，和-1|1成立，所以反对称性不成立；但x|y,y|z成立，就一定有x|z成立，所以传递性成立
(2)因为模m相等是整数集合上的等价关系，所以具有自反、对称、传递性
(3)因为00 = 0，所以自反性不成立；因为x ≠ 0时必有 xx>0,所以反自反性不成立；因
为xy >0 必有yx>0,所以对称性成立；因此反对称性不成立；因为xy>0,yz>0,能得到x,y,z同号且不为0，所以，xz>0,所以传递性成立
(4)因为xx≧0,所以自反性成立；因此，反自反性不成立；因为xy≧0,所以yx≧0，因此对
称性成立；因此，反对称性不成立；因为-1*0 ≧0，0*1≧0，但-1*1 < 0,所以传递性不成立
(5)因为 x=x，所以自反性成立；因此反自反性不成立；因为|x-y|=1，所以| y-x |=1，因
此对称性成立；所以反对称性不成立；因为|1-2|=1，|2-3|=1，但|1-3|=2，所以传递性不成立
因为 xx = xx，所以自反性不成立；反自反性成立；因为x2> y2成立，那么y2>x2就不成立，所以对称性不成立，反对称性成立；传递性成立
7、设R是集合A上的一个二元关系，合于xRy ∧ yRz => ~xRz,称R是A上的一个反传递关系。试举一个实际的反传递关系的例子
解：例如在人群集合上，建立父子关系，那么就是一个反传递关系，因为如果甲是乙的父亲，乙是丙的父亲，那么甲和丙就一定不存在父子关系；另外，在正整数域上建立的倍数关系，也是一个反传递关系，因为如果 a 是 b的2倍，b是c的2倍，那么a 一定不是c的2倍
8、设R和S都是集合A上的二元关系，它们经过关系运算后得到A上的一个新关系。试判别当R和S同时具有下表左列某种指定性质时，经过指定的运算后所得到新关系也仍保持这种性质，把所得结论以√，×的形式填在下表中相应的位置上
（1）自反性的保持情况说明：
因为R,S都具有自反性，所以I A?R,I A?S，
因此I A?R∩S,I A?R∪S,所以自反性在R∩S，R∪S上保持
因为I A?S，所以I A不是S补集的子集，因此也不是R∩-S的子集，所以自反性在R-S上不保持
因为R,S是自反的，所以对任意的a ∈A，（a,a）∈R,S，所以（a,a）∈R○S，因此自反性在R○S上保持
因为（a,a）∈R，所以（a,a）不属于-R,所以-R不具有自反性
因为（a,a）∈R，所以（a,a）∈R-1，因此R-1具有自反性
（2）反自反性的保持情况说明：
因为R,S都具有反自反性，等价于 I A∩R = Φ,I A∩S = Φ
因为I A∩R∩S =Φ，I A∩（R∪S）=Φ，所以R∩S，R∪S都是反自反的
因为I A∩R∩-S =Φ，所以 R-S也是自反的
对于R○S，假设（a,b）∈R,（b,a）∈S, 那么（a,a）∈R○S, 所以反自反在R○S上不一定保持
因为（a,a）不属于R，所以（a,a）一定属于-R，所以-R一定是自反的，一定不是反自反的因为（a,a）不属于R，所以（a,a）也不属于R-1，因此R-1一定是反自反的
（3）对称性的保持情况说明：
因为R,S是对称的，所以R=R-1,S=S-1，-R = (-R)-1=-R-1, -S = (-S)-1=-S-1
因为（R∩S）-1=R-1∩ S-1= R∩S, 所以R∩S具有对称性
因为（R∪S）-1=R-1∪ S-1= R∪S, 所以R∪S具有对称性
因为（R-S）-1=（R∩-S）-1=R-1∩（-S）-1= R-1∩ -S-1 = R∩-S，所以R-S具有对称性
因为(R○S)-1 = S-1○ R-1= S○R ,但S○R通常情况下与R○S不相同，所以对称性不一定保持，例如：R = {(a,b),(b,a)}, S = {(b,c),(c,b)},则R○S = {（a,c）},并不对称
因为（-R）-1 = -R-1= -R，所以R的补是对称的
因为 R逆的逆就是R，既等于R的逆，所以R的逆是对称的
（4）反对称性的保持情况说明：
因为R,S是反对称的，所以R∩R-1? I A S∩S-1? I A
因为（R∩S）∩（R∩S）-1= （R∩R-1）∩（S∩S-1）? I A，所以R∩S具有反对称性
因为如果R = {(a,b)} S = {(b,a)},都是反对称的，但 R∪S = {(a,b),(b,a)}是对称的，所以R∪S不一定再保持对称性
因为R是反对称的，而R-S在R的基础上减少集合元素，因此也一定是反对称的
因为如果 R = {(a,b),(c,a)}, S = {(b,c),(a,a)}, 那么R○S = {（a,c），（c,a）},变为对称的，所以反对称性，在复合运算下不一定保持
因为如果R = {（a,b）,(c,c)}是反对称的，但-R = {（a,a）,(b,b),(b,a),(a,c,),(c,a),(b,c),(c,b)},不是反对称的，所以反对称性在补集运算上不保持
因为R∩R-1? I A，有因为 R = (R-1)-1,所以R-1是反对称的
（5）传递性的保持情况说明：
因为R,S是传递的，所以R2?R, S2?S
因为（R∩S）2 = （R∩S）○（R∩S）? R2∩S2∩(R○S)∩(S○R)?R∩S，所以传递性保持如果R = {(a,b)}, S={(b,c)},都是传递关系，但R∪S = {(a,b),(b,c)}不再是传递关系，所以传递性在R∪S上不一定保持
如果R={(a,b),(b,c),(a,c)},S={(a,c)},分别是两个传递关系，但R-S = {(a,b),(b,c)}不再是传递关系，所以传递性在R-S上不一定保持
如果R={(a,b),(c,d)},S={(b,c),(d,e)},分别是两个传递关系，但R○S = {(a,c),(c,e)}不再是传递关系，所以传递性在R○S上不一定保持
如果A = {a,b,c}, R = {(a,b)}, 那么–R = A ×A – R,显然不是传递的，所以传递性在-R上不一定保持
因为R2?R，所以（R2）-1?R-1，即（R-1）2?R-1，所以传递性在逆运算下保持
10、设R是集合A上的一个二元关系，证明
（1）R是自反的? I A?R
证明:
R是自反的 => I A?R
因为，R是自反的，所以对任意的A中元素a，有（a,a）∈R，即I A中任意元素都属于R，所以I A?R
I A?R => R是自反的
因为，对任意的A中元素a，有（a,a）∈I A，又I A?R，所以（a,a）∈R，所以R是自反的综上所述，R是自反的? I A?R
（2）R是反自反的? I A∩R = Φ
证明：
R是反自反的 => I A∩R = Φ
因为，I A中的任意元素(a,a)，都不属于R，所以I A∩R = Φ
I A∩R = Φ=> R是反自反的
因为I A∩R = Φ，所以I A中的任意元素(a,a)，都不属于R，即对任意的A中元素a，有（a,a）∈I A，都不属于R，所以R是反自反的
综上所述，R是反自反的? I A∩R = Φ
（3）R是对称的? R = R-1
证明：
R是对称的 => R = R-1
因为对R中的任意元素（a,b）,因为R是对称的，所以（b,a）∈R，那么（a,b）∈R-1,所以R?R-1
因为对R-1中的任意元素（a,b）,那么（b,a）∈R，因为R是对称的，那么（a,b）∈R,所以R-1?R
所以 R = R-1
R = R-1 => R是对称的
对R中的任意元素（a,b），因为R = R-1 ,所以（a,b）也属于R-1，所以（b,a）∈R，因此R 是对称的
综上所述，R是对称的? R = R-1
（4）R是反对称的? R∩R-1?I A
证明:
R是反对称的 => R∩R-1?I A
因为对任意(a,b)∈R∩R-1,那么其就同时属于R和R-1，那么（b,a）也属于R，根据反对称的定义，a = b，所以（a,b）∈I A ,所以R∩R-1?I A
R∩R-1?I A => R是反对称的
假设R不是反对称的，那么必定存在 a ≠b∧(a,b)∈R ∧ (b,a)∈R，那么（a,b）∈R∩R-1,但（a,b）不属于I A，矛盾；因此R必是反对称的
综上所述，R是反对称的? R∩R-1?I A
（1）R是传递的? R2?R
证明：
R是传递的 => R2?R
因为对任意（a,b）∈R2,必存在c，使得（a,c）,(c,b)属于R，因为R是传递的，所以(a,b)属于R，因此R2?R
R2?R => R是传递的
因为对任意的R中的元素（a,b），(b,c)，那么(a,c)必定属于R2,也就属于R，所以R是传递的
综上所述，R是传递的? R2?R
11、设A={1,2,3,4},定义A上的关系 R = {(a,b)|a=b+2},S = {(x,y)|y=x+1∨x=2y} 求：R。S,R。S-1。R,R2,(S-1)2
解：根据题意，R={(3,1),(4,2)}，S={(4,2),(1,2),(2，3)，（3，4）}
所以：R。S = {（3，2），（4，3）}
S-1 = {（2，4），（2，1），（3，2），（4，3）}
所以：R。S-1 = {(4,4),(4,1)}
R。S-1。R = {(4,2)}
R2 = ?
(S-1)2 = {(2,3),(3,4),(3,1),(4,2)}
12、设A={a,b,c,d,e,f,g,h}，A上的二元关系R对应的关系图4-5所示，求使R m=R n的最小整数m和n(m < n)
答：R = R16；简要说明如下：本关系图分为两个部分，R = R1 ∪ R2,因为 R1。R2 = R2。R1 = ?, 所以R2 = R12∪ R22 ,同理R n = R1n∪ R2n ,又因为 I1 = R13,I2=R25；3，5的最小公倍数为15，所以I = R15 ,所以R = Io R15 = Ro R15 = R16
13、设R是集合A上的二元关系，证明：
（1）I A n = I A
证明：因为单位关系的关系矩阵为单位矩阵，而复合运算就是矩阵的乘法，根据单位矩阵的性质，I A n = I A
（2）I Ao R=RoI A =R
证明：同上，因为单位矩阵左乘、右乘一个矩阵，结果不变；所以I Ao R=RoI A =R
（3）(R∪I A)n=I A∪R∪R2∪R3…∪R n
证明：根据书中并集关系复合的定理（4.2），展开，并利用上述1，2的结论，及可得证（严格可用归纳法）
15、写出第12题中关系图对应的关系矩阵，并利用warshall算法求这个关系的传递闭包
解：
习题五
1、设 A = {(a,b)| a,b ∈ N}，定义A 上的一个二元关系 R = {((a,b),(c,d)) | ad = bc } 证明：R 是 A 上的等价关系
证明：
（自反性）因为 对任意（a,b ）∈ A, 都有：ab = ba, 既(（a,b ）,(a,b)) ∈ R ，所以R 是自反的
（对称性）如果（（a,b ）,(c,d)）∈ R ,那么ad = bc, 所以 cb = ad,既（（c,d ）,(a,b)）∈R, 所以R 是对称的 （传递性）如果（（a,b ）,(c,d)）∈ R, ((c,d),(e,f)) ∈ R, 那么 ad = bc ,cf = ed ,因此，adcf = bced (注：如果 0 ? N 中)， 那么af = eb, 所以（（a,b ）,(e,f)）∈ R,R 具有传递性
综上所证，R 是A 上的等价关系
3、集合 A = {1，2，3，4}的一个分化为 S 0={{1,2,4},{3}},求由S 0导出的A 上的一个等价关系R
解：等价关系R = {1，2，4}×{1，2，4}∪{3}×{3} = {（1，1），（2，2），（4，4），（1，2），（1，4），（2，1），（2，4），（4，1）,(4,2),(3,3)}
4、试确定在4个元素的集合上可以定义的等价关系数目 解：
在此集合上可以确定的4分划个数为：1
在此集合上可以确定的3分划个数为：c(4,2) = 6
在此集合上可以确定的2分划个数为：c(4,1) + c(4,2) /2 = 7 在此集合上可以确定的1分划个数为：c(4,4) = 1
所以共可定义15个等价关系
6、设R 是非空集合A 上的一个二元关系，具有对称性和传递性。证明：如果对每一个x ∈A ，
????????????
?
?
?=00
01100001000010000000000000 000000010000000000000000000101000010R M ????????????? ?
?=11
11111111111111 100010001000100011110000000000001000011101110111
)
(R t M
存在y ∈A 使xRy ，那么，R 是A 上的等价关系
证明：因为对每一个x ∈A ，存在y ∈A 使xRy ，由于R 是对称的，所以yRx ；又因为R 是传递的，当xRy 并且 yRx ，那么xRx 。所以R 是自反的。综上所述，R 是自反的，对称的和传递的，因此R 是A 上的等价关系
8、设A 是由54的正因子构成的集合，“|”表示整除。画出偏序集
解：先求出偏序集，然后求处相应的cover ，然后画出Hasse 图 A={1，2，3，6，9，18，27，54}
COVER(|)={(1,2), (1,3), (2,6), (3,6), (3,9),(6,18), (9,18), (9,27), (18,54), (27,54)} 最大元：54 最小元：1
有4个包含元素最多的全序子集: L1={54,27,9,3,1} L1={54,18,9,3,1} L1={54,18,6,3,1} L1={54,18,6,2,1}
9、设A={a,b,c},画出偏序集合对应的Hasse 图。试比较本题与上题Hasse 图的异同
2 54 1
27
解：
{a,b,c}
?
两图的相同点：都有最大（小）元不同点：最大线序一个为5，一个为4
11、设R是集合A上的一个等价关系。现在在等价类之间定义一个新关系S使得R的任何等价类[a]和[b]满足[a]S[b] aRb，判别S是一个什么关系
解:根据题目信息，猜测是等价关系，说明如下：
（1）因为对任意的a∈A，aRa成立（R是A上的等价关系，是自反的），所以[a] S [a],S 是自反的
（2）假设[a] S [b]成立，那么aRb；因为R是对称的，所以bRa,因此[b] S [a]成立，所以S是对称的
（3）假设[a]S[b],[b]S[c]成立，则aRb,bRc，因为R是传递的，所以aRc成立，因此[a]S[c]成立，所以S是传递的
综上所述，S是等价类集合上的等价关系
习题六
1、设A={1，2，3，4}，B=A×A,确定下述集合是否为A到B的全函数或部分函数
（1）{（1，（2，3）），（2，（2，2）），（3，（1，3）），（4，（4，3））}
答：根据本书全函数的定义，这是从A到B的全函数
（2）{（1，（1，2）），（1，（2，3）），（3，（2，4））}}
答：根据本书函数的定义，每个原像只能有一个像，所以此定义不是A到B的函数
（3）{（1，（3，3）），（2，（3，3）），（3，（2，1）），（4，（4，1））}
答：根据本书全函数的定义，这是从A到B的全函数
2、判别以下关系中哪些是全函数
（1）{（n1,n2）|n1,n2∈N,0<2n1-n2<5}
答：此关系不满足全函数的定义，因为（3，5），（3，4），（3，3），（3，2），（3，1）都属于此关系，但它违反了本书函数是单值的定义
（2）{（n1,n2）|n1,n2∈N,n1是n2的正因子个数}
答：如果N集合中不包含0，那么此关系是全函数，因为任意一个自然数按正因子个数的定义，都有确切的值，因此是全函数
（3）{（S1,S2）|S1,S2?{a,b,c,d} 且S1∩S2=?}
答：此关系不满足全函数的定义，因为（?，{a}）,(?,{b})等属于此关系，但它违反了本书函数是单值的定义
（4）{（a,b）|a,b ∈ N,gcd(a,b)=3}
答：此关系不满足全函数的定义，因为就1，2而言，3不是他们的因数；同时推论开，所有不是3的质数，3都不是他们的因数，因此他们就没有像，所以不是全函数
（5）{（x,y）|x,y ∈ Z,y=x2}
答：此关系是全函数，因为任意一个整数，都能求到唯一的平方数。所以按定义是全函数7、确定下列映射是否单射、满射或双射：
（1）f1: N→R,f1(n)=ln n
答：如果0不属于N,那么这是一个单射函数，因为任意一个自然数都可以求其自然对数，同时ln是单调函数，所以是单射函数。但是并非任意一个实数其原像都是自然数，所以不是满射
（2）f2:N→N,f2(n)为不超过n的素数数目
答：这是一个满射函数，但不是单射。因为f(3)=f(4)=3,及不超过3，4的素数都是1，2，3，个数为3；同时因为自然数中的素数有无穷多，所以对任意一个自然数m，都能找到从第m个素数起到第m+1个素数（但不包括第m+1个素数）的所有自然数，其函数值都等于m，所以是满射，但不是单射（注：7是第5个素数，11是第6个素数，所以f(7)=f(8)=f(9)=f(10)=5）
（3）f3:N×N→N,f3(n1,n2)=(n1+1)n2
答：这既不是单射，也不是满射（与0是否属于N无关，以下说明以0不属于N而言）；因为任意两个自然数，都能求到此函数值，所以是全函数。因为f(1,2)=f(3,1)=4,所以不是单射函数；同时1没有原像，所以不是满射函数
（4）f4：R→R,f4(x)=x2+2x-15
答：一元二次函数，既不是单射，也不是满射；其几何图像为抛物线
（5）f5：Z→Z，f5(x)=1+2x3
答：这是一个单射函数，但不是满射；因为3次曲线是单调函数，所以在定义域子集范围也是单调的，所以是单射函数。但任意一个整数像的原像却不一定是整数。所以不是满射（6）A是集合，f6:2A×2A→2A×2A,f6(x,y)=(x∪y,x∩y)
答：假设A = ?，那么这是一个双射函数（请同学思考）
假设A不是空集，那么此函数既不是单射，也不是满射；因为：对f(x,y)=f(y,x),所以不是单射；另外对于（?，A）,没有原像；所以不是满射
（7）f7:R×R→R,f7(x,y)=x+y,f8:R×R→R,f8(x,y)=xy
答：此两个函数，都不是单射，但都是满射函数
8、设X是有限集合，f:X→X,证明：
（1）如果f是单射，f必是双射
证明：假设f不是满射，那么就必定有元素没有原像，由于X是有限集合，根据鸽茏原理：原像元素个数（鸽子）就比像元素个数多（鸽笼），所以必定有多个原像会映射到相同的像上，所以不是单射。矛盾。所以f必定是满射，即是双射
（2）如果f是满射，f必是双射
证明：假设f不是单射，那么必定存在多个元素映射到相同的像上。由于X集合是有限的，那么因变量的个数就少于自变量个数，因此f就不是满射。与题设矛盾。因此f必是单射，既是双射
9、设f是有限集X上的一个函数，满足?x∈X,f2(x)=x；证明：f是双射
证明：因为f2(x) = f。f(x) = x, 既是f2 = Ix；所以f是自己的逆函数，根据逆函数的性质，f必是双射
18、证明下列集合A和B等势
（1）A = (0,1), B = (-2,2)
证明：如果能找到从A到B的双射函数，就能说明A和B等势，存在A到B上的这样的函数；例如：f(x) = 4x - 2 或 f(x) = 5x-3
（2）A = (-∞,+∞),B = (0,+∞)
证明：如果能找到从A到B的双射函数，就能说明A和B等势，存在A到B上的这样的函数；例如：f(x) = e x
（3）A = (0,1),B = (1/4,1/2)
证明：如果能找到从A到B的双射函数，就能说明A和B等势，存在A到B上的这样的函数；例如：f(x) = 1/4 x + 1/4
（4）A = N, B = {(m,n)|m,n ∈ N ∧ m≤n}
证明：如果将B集合写成如下的分化并集形式：B = B1∪B2∪B3……,这样B成为可数个集合的并集，其中Bi = {（i,i）,(i,i+1),(i,i+2)……},是一个可数集合，根据书中定理，可数个可数集合的并集合依然是可数集，那么就和N等势，证毕
习题八
26、证明：在任何人数不少于2的人群中，至少有2个人在其中有同样多的熟人
证明：设人群人数为n（≥），那么每个人有可能有的熟人数为（0，1，…n-1）n 种情况,但是，当有人没有熟人时，就不可能有人有n-1个熟人；同理，当有人认识其余的所有人时，就不存在有人没有熟人，因此每个人可能有的熟人数只有n-1种。而一共有n 个人，那么根据鸽笼原理，必存在至少有2个人在其中有同样多的熟人的情况
习题十
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作，
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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)均有可能
离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式
一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．． 命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．． 谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D ．???? ??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1?R 2的说法正确的是（ ） A ．一定是等价关系 B ．一定是相容关系
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 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）是，T （2）是，F （3）不是（4）是，T （5）不是（6）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。） 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死（命题的否定就是把命题前提中的量词“换成存在，换成”，然后将命题的结论否定，“且变或或变且”） 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校(2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P ?（注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的）（2）Q P→ ? P? ?（4）Q P? →（3）Q 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 (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2）F （同理）（3）F （同理）（4）T（对任一整数x存在整数y满足条件y=2x 很明显是正确的）
第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每
一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故
G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G
??????????????????????精品自学考料推荐?????????????????? 浙江省 2019 年 7 月高等教育自学考试 离散数学试题 课程代码： 02324 一、单项选择题 (在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在 题干的括号内。每小题 1 分，共 14 分 ) 1.给定如下 4 个语句 : (1) 我不会游泳。(2)如果天不下雨,我就去踢足球。 (3) 我每天都看新闻联播。(4)火星上有人吗? 其中不是复合命题的是()。 A.(1)(4) B.(1)(3)(4) C.(1)(3) D.(3)(4) 2.设 P,Q,R 是命题公式 ,则 P→ R， Q→ R， P∨Q ()。 A. P B. Q C. R D. ┐ R 3.下列公式中正确的等价式是()。 A. ┐ ( x)A(x)(x) ┐ A(x) B. ┐ ( x)A(x)(x)┐ A(x) C. ( x)( y)A(x,y)( y)( x)A(x,y) D. ( x)( (x)∧ B(x))( x)A(x) ∨ ( x)B(x) 4.谓词公式 ( x)(P(x) ∨ ( y)R(y)) → Q(x) 中的 x()。 A.只是约束变元 B.只是自由变元 C.既非约束变元又非自由变元 D.既是约束变元又是自由变元 5.设个体域为整数集 ,则下列公式中值为真的是 ()。 A. (y)(x)(x · y=2) B. (x)(y)(x · y=2) C. (x)(x · y=x) D. (x)(y)(x+y=2y) 6.设 A={a,b,c}, 则 A 中的双射共有 ()。 A.3 个 B.6 个 C.8 个 D.9 个 7.设 S={a,b,c}, 则 S 的幂集的元素的个数有()。 A.3 个 B.6 个 C.8 个 D.9 个 8.设 A={a,b,c}, 则 A ×A 中的元素有 ()。 A.3 个 B.6 个 1
本科高等数学离散数学试题及答案 一、填空题 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变成完全图。
作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G=
数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2
全国2018年7月高等教育自学考试 离散数学试题 课程代码：02324 一、单项选择题(在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填 在题干的括号内。每小题1分，共14分) 1.下列语句不是 ．．命题的是( )。 A.黄金是非金属。 B.要是他不上场，我们就不会输。 C.他跑100米只用了10秒钟，你说他是不是运动健将呢? D.他跑100米只用了10秒钟，他是一个真正的运动健将。 2.关于命题变元P和Q的大项M01表示( )。 A.┐P∧Q B.┐P∨Q C.P∨┐Q D.P∧┐Q 3.公式(?x)(?y)(P(x,z)→Q(y))S(x,y)中的(?x)的辖域是( )。 A.(?y)(P(x,z)→Q(y)) B.P(x,z)→Q(y) C.P(x,z) D.S(x,z) 4.下列等价式不成立 ．．．的是( )。 A.┐(?x)A(x)?(?x)┐A(x) B.┐(?x)A(x)?(?x)┐A(x) C.(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) D.(?x)(A(x)∨B(x))?(?x)A(x)∨(?x)B(x) 5.公式(?x)(?y)(P(x,y)∧Q(z))→R(x)中的x( )。 A.只是约束变元 B.只是自由变元 C.既是约束变元又是自由变元 D.既非约束变元又非自由变元 6.设A={a,{a}}，则下列各式正确的是( )。 A.{a}∈p(A)(A的幂集) B.{a}?p(A) C.{{a}}?p(A) D.{a,{a}}?p(A) 7.集合的以下运算律不成立 ．．．的是( )。 A.A∩B=B∩A B.A∪B=B∪A C.A⊕B=B⊕A D.A-B=B-A 8.设N是自然数集，R是实数集，函数f：Ｎ→R，f(n)=lgn是( )。 A.入射 B.满射 C.双射 D.非以上三种的一般函数 9.设实数集R上的二元运算o为：xoy=x+y-2xy,则o不满足( )。 A.交换律 B.结合律 1
全国2009年4月自学考试离散数学试题（附答案） 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 2．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟 C．如果1+2=3，那么雪是黑的D．如果1+2=5，那么雪是黑的 3．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q）D．?（? P∨? Q） 4．命题公式（P∧（P→Q））→Q是（） A．矛盾式B．蕴含式 C．重言式D．等价式 5．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 6．在公式（x ?）F（x，y）→（?y）G（x，y）中变元x是（） A．自由变元B．约束变元 C．既是自由变元，又是约束变元D．既不是自由变元，又不是约束变元 7．集合A={1，2，…，10}上的关系R={
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试
3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章
一、单项选择题(本大题共１５小题，每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是．． 命题的是( D ) A.中华人民共和国的首都是北京?B ．张三是学生 C.雪是黑色的? D.太好了! 2．下列式子不是．． 谓词合式公式的是（ Ｂ ) A.(?x ）P (x ）→R (y ） B.（?x ) ┐Ｐ（x ）?(?x )(P (x )→Q （x ）) Ｃ.(?x )(?y )(P (x )∧Q (y ))→（?ｘ)R (x ) D ．(?x )(P (x ，y )→Ｑ(x ，z ))∨(?ｚ）R (ｘ,z ） 3．下列式子为重言式的是( ） A ．（┐P ∧R )→Q ?B.Ｐ∨Q ∧R →┐Ｒ C ．P ∨(P ∧Q ）?D.(┐P ∨Q )?(P →Q ） 4．在指定的解释下，下列公式为真的是（ ) Ａ．(?x )(P （x )∨Q (ｘ)），P (x ）:x =1,Q (x ):x =2,论域:{1,2｝ B ．(?x )(P (x ）∧Q (x ))，P （ｘ):x =1,Ｑ(ｘ)：x =2,论域： {1，2} C ．(?x )(P (x ) →Q (ｘ))，Ｐ(x ):ｘ>2,Q (x )：x =０，论域:{3,4} Ｄ．(?x ）(P （ｘ)→Ｑ(x )）,P (ｘ):ｘ>２,Q （x ):x ＝0，论域：｛3，4} 5.对于公式(?x ) （?y )（Ｐ(x )∧Q (y ))→(?x ）Ｒ(x ,y )，下列说法正确的是（ ) A ．y 是自由变元? B ．y 是约束变元 Ｃ．（?x ）的辖域是R(x , ｙ) D.(?x )的辖域是(?ｙ）(Ｐ(x ）∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2},与公式(?x ）A (x )等价的是( ) Ａ．A (1)∨A (2)?B.A (1)→Ａ(2) C.Ａ(1）∧Ａ(2)?D ．A (2)→A （1) 7．设Z ＋是正整数集,R 是实数集，ｆ:Z ＋ →R , ｆ(n )=lo ｇ2n ,则f ( ） A ．仅是入射? B ．仅是满射 C ．是双射 Ｄ．不是函数 ８.下列关系矩阵所对应的关系具有反对称性的是（ ) Ａ.???? ??????001110101 B ．??????????101110001 C ．??????????001100100 D.???? ??????001010101 9.设R 1和R 2是集合A 上的相容关系,下列关于复合关系R １?R ２的说法正确的是( ) A.一定是等价关系? B.一定是相容关系
全国2018年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是 ．．命题的是（） A．中华人民共和国的首都是北京B．张三是学生 C．雪是黑色的D．太好了！ 2．下列式子不是 ．．谓词合式公式的是（） A．（?x）P(x)→R(y) B．(?x) ┐P（x）?(?x)(P(x)→Q(x)) C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x) D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z) 3．下列式子为重言式的是（） A．(┐P∧R)→Q B．P∨Q∧R→┐R C．P∨(P∧Q) D．(┐P∨Q)?(P→Q) 4．在指定的解释下，下列公式为真的是（） A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2} B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2} C．(?x)(P(x) →Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4} 5．对于公式(?x) (?y)(P(x)∧Q(y))→(?x)R(x,y)，下列说法正确的是（） A．y是自由变元B．y是约束变元 C．(?x)的辖域是R(x, y) D．(?x)的辖域是(?y)(P(x)∧Q(y))→(?x)R(x,y) 6．设论域为{1,2}，与公式(?x)A(x)等价的是（） A．A(1)∨A(2) B．A(1)→A(2) C．A(1)∧A(2) D．A(2)→A(1) 7．设Z+是正整数集，R是实数集，f:Z+→R, f(n)=log2n ,则f（） 1
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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
国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021
离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题
1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,3}， A B {1,2,3}} ，A B= {< 1,1>，<1,2>，<2，1>，<2，2>，<3，1>，<3， 2> } ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {< 2,2>，<2,3>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={
全国2010年7月自学考试离散数学试题 课程代码：02324 一、单项选择题（本大题共15小题，每小题1分，共15分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1．下列句子不是．．命题的是（ D ） A ．中华人民共和国的首都是北京 B ．张三是学生 C ．雪是黑色的 D ．太好了！ 2．下列式子不是．．谓词合式公式的是（ B ） A ．（?x ）P (x )→R (y ) B ．(?x ) ┐P （x ）?(?x )(P (x )→Q (x )) C ．(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D ．(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3．下列式子为重言式的是（ ） A ．(┐P ∧R )→Q B ．P ∨Q ∧R →┐R C ．P ∨(P ∧Q ) D ．(┐P ∨Q )?(P →Q ) 4．在指定的解释下，下列公式为真的是（ ） A ．(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B ．(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C ．(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D ．(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5．对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y )，下列说法正确的是（ ） A ．y 是自由变元 B ．y 是约束变元 C ．(?x )的辖域是R(x , y ) D ．(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6．设论域为{1,2}，与公式(?x )A (x )等价的是（ ） A ．A (1)∨A (2) B ．A (1)→A (2) C ．A (1)∧A (2) D ．A (2)→A (1) 7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ） A ．仅是入射 B ．仅是满射 C ．是双射 D ．不是函数 8．下列关系矩阵所对应的关系具有反对称性的是（ ） A ．???? ? ?????001110101 B ．???? ? ?????101110001