《 离散数学 》
同步测试1、命题逻辑
一．填空：
1．公式)()(s r q p ∨→∧的真值表中共有 16 种真值指派。
2．命题公式（?P →Q ）→（?Q ∨P ）的主析取范式为001011m m m ∨∨或（P ∧Q ）∨（P ∧? Q ）∨（?P ∧?Q ），主合取范式为：01M 或P ∨? Q 。
3．设A 、B 、C 和D 四个人中派两个人出差，需要满足下列条件：（1）若A 去，
则C 和D 中要去一人；（2）B 和C 不能都去；（3）C 去则D 要留下。则有3 种派法，分别为AC,AD,BD 。
4．给定命题公式：P ∨（?P →（Q ∨(? Q →R )）则它的成真指派为001，010，011，100，101，110，111，成假指派为000。
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
1、设A 、B 、C 为任意命题公式，若A ∨B ?B ∨ C ，则A ?B 。（×）
2、设A 、B 为任意命题公式，若?A ??B ，则A ?B 。（√）
3、公式)()(q p q p ∨→∧是重言式。（√）
4、公式P ∧Q 是合取范式，不是析取范式。（×）
5、所有极大项的析取为永真式。（√）
6、一个命题公式可以有多个与之等价的析取范式。（√）
7、任一命题的主合取范式是唯一的。（√）
8、下面推理是正确的：（×）
（1）P →Q P
（2）?P P
（3）?Q T(1)(2)
9、公式（P ∧Q ）→（R ∨?S ）的对偶式为（P ∨Q ）→（R ∧?S ）。（×）
10、公式（?P ∨Q ）∧（P →R ）与P →（Q ∧ R ）。（√）
三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内(多选不给分)。
1、给定命题公式如下：A ．（P ?Q ）?（P →Q ）∧（Q →P ）
B ．（P ∧?P ）?Q
C ．（P ∨?P ）→（（Q ∧?Q ）∧R ）
则重言式为：( A )，矛盾式为：( C )，可满足式为：( B )
2．给定命题公式如下：（?P →Q ）→（?P ∧Q ）
该命题公式的成真赋值个数是（D），成假赋值个数是（B），与它等价的主析取范式中极小项个数为（D），主合取范式中极大项个数为（B）
A．0 B．1 C．2 D．3 E. 4
3．给定命题公式：P∨（Q∧R）则它的成真赋值为（A），成假赋值为（C）A．111，011，100，101，110B．111，011
C．000，010，001D．000
4．给定真值表：
则F等价于（D）
A．P ∧Q B．P∨Q C．P→Q D．?P∨?Q
5．给定命题公式：（?P∨Q）∧（P→R），与之等价的是(C )
A．P→（?Q∧R）B．P→（Q∨R）
C．P→（Q∧R）D．?P→（Q∧R）
6．前提条件：P→（Q→S），Q, P∨?R,则它的有效推论为(B )
A．S B．R→S C．P D．R→Q
同步测试2、谓词逻辑
一．填空：
1．对谓词公式（（?x）P（x）∨（?y）Q（y））→（?x）R（x）中约束变元应用变换规则所得到的前束范式是（?x）（? y）（?z）（P（x）∨Q（y））→R（z））2．谓词公式（?x）（P（x）→Q（x））∧（?z）（R（x）∧S（z））中，量词（?x）的辖域为（P（x）→Q（x））。
3．给定命题“不存在两片完全一样的叶子”（假设L（x）：x是叶子，S（x，y）: x是y，T（x，y）:：x与y完全相同。），则该命题符号化后的公式为（?x）（? y）（（L（x）∧L（y））→（?S（x，y）→?T（x，y）））
4．谓词公式（?x）F（x）→（（?x）F（x）∨（?y）G（y））是逻辑有效式，?（F（x,y）∨R（x,y））∧R（x,y）是矛盾式，（?x）（?y）F（x,y）→（?x）（?y）F （x,y）是可满足式。
5．由前提（?x）（F（x）→H（x））,（?x）?H（x）可得出的有效结论是（?x）?F（x）。
二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。
1、（?x ）（A （x ）∨B （x ））?（?x ）A （x ）∨（?x ）B （x ）。（×）
2、（?x ）（?y ）A （x,y ）?（?y ）（?x ）A （x,y ）。（×）
3、（?x ）（A （x ）∧B （x ））?（?x ）A （x ）∧（?x ）B （x ）。（√）
4、谓词公式（?x ）（?y ）（P （x,y ）∨Q （y,z ））中，x,y 是约束变元，z 是自由变元。（√）
5、谓词公式（?y ）（?z ）（P （y ）∨Q （x,z ））中，无自由变元，是闭式。（×）
6、对谓词公式（?x ）（P （y ）∨Q （x,y ））∧ R （x,y ）中的自由变元进行代入后得到公式（?x ）（P （z ）∨Q （x,z ））∧ R （x,y ）。（×）
7、对谓词公式（?x ）（P （x ）∨Q （x,y ））∧ R （x,y ）中的约束变元进行换名后得到公式（?y ）（P （y ）∨Q （y,y ））∧ R （x,y ）（×）
8、谓词公式的前束范式不是唯一的。（√）
9、如下推理是正确的: 前提（?x ）（F （x ）→G （x ））, （?y ）F （y ）
结论（?y ）G （y ）（√）
10．（?x ）（A （x ）→B （x ））?（?x ）A （x ）→（?x ）B （x ）。（√）
11、（?y ）（?x ）A （x,y ）的斯柯林范式是（?x ）（?y ）A （x,y ）（×）
三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内(多选不给分)。
1、取个体域为整数集，则下列公式中真命题为（A ），假命题为（B ）。
A ．（?x ）（?y ）（x ×y=0）
B ．（?x ）（?y ）（x ×y=1）
C ．x y y x +-=-
D ．（?x ）（x ×y=x ）
2．给定公式（?x ）F （y ,x ）→（?y ）G （y ），它的前束范式（C ），
A ．(?x )(?y )(F (y ,x )→G (y ))
B ．(?x )(?y )(F (z ,x )→G (y ))
C ．(?x )(?y )(?F (z ,x )∨G (y ))
D ．(?x )(?y )(?F (z ,x )∨G (y ))
3．下列公式中，（A ）是逻辑有效式，（C ）是矛盾式。
A ．(?x ) F （x ）→(?y )F （y ）
B ．(?x ) (?y ) F(x,,y )→(?x ) (?y ) F(x,,y )
C ．?(P （x ）→((?y )G(x,,y )→P （x ）))
D ． (?x ) (?P （x ）→?P （a ）)
4．命题“所有的马都比某些牛跑得快”的符号化公式为（C ）
假设：H （x ）：x 是马，C （y ）：y 是牛，F （x ，y ）：x 跑得比y 快。
A ．(?x ) (H （x ）∧ (?y )((C （y ）∧ F(x,,y )))
B ．(?x ) (H （x ）→ (?y )((
C （y ）→ F(x,,y )))
C ．(?x ) (H （x ）→ (?y )((C （y ）∧ F(x,,y )))
D ．(?y ) (?x ) (H （x ）→((C （y ）∧ F(x,,y )))
5．由前提：(?x ) (P （x ）→（Q （x ）→?R （x ）），(?x ) (P （x ）→（R （x ）∨S （x ）））, (?x ) (P （x ）∧?S （x ））,则它的有效推论为 (C )
A ．(?x ) (P （x ）→?Q （x ））
B ．(?x ) (P （x ）∧?Q （x ））
C ．(?x ) (P （x ）∧?Q （x ））
D ．(?x ) (P （x ）∧Q （x ））
6．给定公式：(?x ) (A （x ）→B ），与之等价的公式是 (B )
A ．(?x )A （x ）→
B B ．(?x )A （x ）→B
C ．?B →(?x )A （x ）
D ．?B →(?x )?A （x ）
7．下面推理中，正确的是（D ）
A ．（1）(?x ) (F (x )∨G (x )) P
（2）F (a)∨G (b) US
B ．（1）F (a)→G (b)P
（2）(?x )(F (x )→G (x )) EG
C ．（1）F (x )→G (b)P
（2）(?x )(F (x )→G (x )) EG
D ．（1）(?x ) (F (x )→G (x )) P
（2）F (y )→G (y ) US
同步测试3、集合
一．填空：
1．设{}{}N k k x x x B N x x x A ∈=<<=∈<<=,2,151,,123，则=?B A {}10,8,6,4，
=?B A {}14,12,11,10,9,8,7,6,5,4,2，=-B A {}11,9,7,5，=⊕B A {}14,12,11,9,7,5,2。
2．设全集{
}10,9,8,7,6,5,4,3,2,1=E 的子集为{}10,8,6,4,2=A ，{}9,7,5,3,1=B ，{}9,6,3=C ，则=?B A Φ，=?C B {}9,3，=?B A ~~{}7,5,1，=?C A {}7,5,1，
=⊕B A {
}10,9,8,7,6,5,4,3,2,1，=⊕C B {}7,6,5,1 3．设A 、B 是集合，求A 、B 之间的关系：
A.如果{}{}{}b a a B a A ,,,==，则B A ?
B.如果{}Φ=Φ=B A ,，则B A ∈且B A ?
C.如果{}{}{}ΦΦ==,,,a B a A ，则B A ?
D.如果{}{}{}ΦΦ=Φ=,,B A ，则B A ∈且B A ?
4．设{}{}b a b a A ,,,,Φ=，求下列各式的结果：
{}=-b a A ,{}{}b a ,,Φ；{}=Φ-A {}{}b a b a ,,,；{}{}=-A b a ,Φ；=-ΦA Φ；=)(A ρ{}{} }}},{,,,{}},,{,,{},},,{,{},,,{},,,,{b a b a b a b a b b a c b a b a ΦΦΦΦ
{}{}}}},{,{}},,{,{},,{}},,{,{},,{},,{},,{},{},{},{,b a b b a a b a b a b a b a b a ΦΦΦΦΦ{}=-a A {}{}b a b ,,,Φ；{}{}=-b a A ,{}b a ,,Φ；{}=-A b a ,Φ
5．集合{}{
}{}{}{}{}{}c b a B c b a A ,,,,,==，试写出：=?B A {}{}{}}{},{,,,c b c b a ，=?B A {
}}{c ，=-B A {}{}b a ,，=⊕B A {}{}{}b a b a }{,,，=)(A ρ{}{}{}A c b a },{},,{,Φ，
=)(B ρ{}
{}{}B a c c b b a c b a }},{},{{}},{},{{}},{},{{},{}},{{},{,Φ 6．若集合A 的元素的个数为10=A ，则其幂集的元素的个数为()=A ρ1024210=
7．确定下列各式：
A.{}=Φ?ΦΦ
B.{}{}=Φ-ΦΦ,{}{}ΦΦ,
C.{}{}=Φ-ΦΦ}{,{}{}Φ
D.=Φ?Φ}{}{Φ
8．设{}{
}2,1,1,0==B A ，确定下面集合： A.{}
=??B A 1{<<0,1>,1>,<<0,1>,2>,<<1,1>,1>,<<1,1>,2>} B.=?B A 2{<<0,0>,1>,<<0,0>,2>,<<0,1>,1>,<<0,1>,2>, <<1,0>,1>,<<1,0>,2>,<<1,1>,1>,<<1,1>,2>}
C.=?2)(A B {<<1,0>,<1,0>>,<<1,0>,<1,1>>,<<1,0>,<2,0>>, <<1,0>,<2,1>>,<<1,1>,<1,0>>,<<1,1>,<1,1>>,<<1,1>,<2,0>>,<<1,1>,<2,1>>, <<2,0>,<1,0>>,<<2,0>,<1,1>>,<<2,0>,<2,0>>,<<2,0>,<2,1>>, <<2,1>,<1,0>>,<<2,1>,<1,1>>,<<2,1>,<2,0>>,<<2,1>,<2,1>>}
D.=?A B 2{<<1,1>,0>,<<1,1>,1>,<<1,1>,0>,<<1,1>,1>,}
9．设{}b a A ,=，确定下面集合：
A.=)(A ρ{}},{},{},{,b a b a Φ
B.=?A A )(ρ{}><><><>Φ {}><><><>Φ C.=?)()(A A ρρ{}>Φ<>Φ<>Φ<>ΦΦ<},{,,}{,,}{,,,b a b a {}><><><>Φ<},{},{,}{},{,}{},{,},{b a a b a a a a {}><><><>Φ<},{},{,}{},{,}{},{,},{b a b b b a b b {}><><><>Φ<},{},,{,}{},,{,}{},,{,},,{b a b a b b a a b a b a D.=?)(A A ρ{}><><><>Φ<},{,,}{,,}{,,,b a a b a a a a {}><><><>Φ<},{,,}{,,}{,,,b a b b b a b b 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 1、若C A B A ⊕=⊕，则C B =。（√） 2、若Φ==Q P Q Q P ,，则Φ=P 。（√） 3、{}{}{}ΦΦ∈Φ,且{}{}{}ΦΦ?Φ,。（√） 4、设{}Φ=A ，则有{}()()A ρρ∈Φ，且{}()()A ρρ?Φ。（√） 5、设A 、B 为任意集合，则=-)(B A ρ)()(B A ρρ-。（×） 6、若B B A ?-，则B A ?。（√） 7、对每一个集合A ，有()A A ρ∈（√） 8、对每一个集合A ，有()A A ρ?}{（√） 9、对每一个集合A ，有()A A ρ∈}{（×） 10、对每一个集合A ，有()A A ρ?（×） 11．若=?B A C A ?，则C B =（×） 12．若=B A C A ，则C B =（×） 13．对任意集合A 、B 、C ，有B C A C B A --=--)()(。（√） 14．对任意集合A 、B 、C ，有)()()(C B C A C B A ---=--。（√） 15．对任意集合A 、B 、C 、D ，若D C B A ??,，则D C B A ???。（√） 16．若C B B A ??,，则C A ?（√） 17．如果B A ?，且C B ∈，则C A ?（×） 18．如果B A ∈，且C B ?，则C A ?（×） 19．若B A ?，则C B C A ???（√） 20．若D C B A ??,，则C B C A ?（√） 21．若B A ?，则A B ~~?（√） 22．若Φ=?B A ，则A B B A ~,~??（√） 23．若E B A = ，则A B B A ??~,~（√） 24．设A 、B 、C 是任意集合，则)()()(C A B A C B A ⊕=⊕。（√） 25．设A 、B 、C 是任意集合，则)()()(C A B A C B A ⊕=⊕。（×） 26．设A 、B 是任意两个集合，若Φ=A 或Φ=B 则Φ=?B A 。（√） 27．设A 、B 、C 是任意三个集合，则C B A C B A ??=??)()(。（×） 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的括号内(多选不给分)。 1、对任意集合A 、B 、C ，下面论断正确的是( A ) A ．若C B B A ?∈,，则 C A ∈ B ．若 C B B A ?∈,，则C A ? C ．若C B B A ∈?,，则C A ∈ D ．若C B B A ∈?,，则C A ? 2．设{}{ }{}{}h g f e d c b a A ,,,,,,,=，下面选项正确的是( C ) A ．A a ∈B ．{}A c b a ?,,C ．{}{}A e d ?,D ．A ∈Φ 3．下列选项错误的是（B ） A ．Φ?Φ B ．Φ∈Φ C ．}{Φ?Φ D ．}{Φ∈Φ 4．在0（D ）Φ之间填上正确的符号。 A ．= B ．∈ C ．? D ．? 5．设Φ=-B A ，则( C ) A ．Φ=A B ．Φ≠B C ．B A ? D ．B A ? 6．设{}{ }1,1=A ，下列选项错误的是( B ) A ．{} ()A ρ∈1B ．{}()A ρ?1C ．{}()A ρ∈}1{ D ．{}()A ρ?}1{ 7．设{}Φ=A ，下列选项错误的是( D ) A ．()()A ρρ∈Φ B ．{}()()A ρρ∈Φ C ．{} ()()A ρρ∈Φ}{ D ．{}()A ρ∈ΦΦ},{ 8．幂集为()())(Φρρρ为( C ) A ．{}{}{ }ΦΦΦ,},{B ．{}{}{}{}ΦΦΦΦ,,, C ．{}{}{}{}{}{}ΦΦΦΦΦ,,,, D ．{}{}{}ΦΦΦ,, 9．对任意集合A 、B 、C 、D ，下列选项正确的是 ( D ) A ．)()()()(D B C A D C B A ??=? B ．)()()()(D B C A D C B A ?-?=-?- C ．)()()()( D B C A D C B A ?⊕?=⊕?⊕ D ．)()()(C B C A C B A ?⊕?=?⊕ 10．设(){}01==x f x M ，(){}02==x f x N ，则方程()()021=?x f x f 的解为( B ) A ．N M B ．N M C ．N M ⊕ D ．N M - 《 离散数学 》 同步测试卷4 关系 一．填空： 1．关系R 是自反的，当且仅当关系矩阵中主对角线的元素均为1 ，在关系图中每一个节点均有自环。 2．关系R 是反自反的，当且仅当关系矩阵中主对角线的元素均0 ，在关系图中每一个节点均无自环。 3．关系R 是对称的，当且仅当关系矩阵为对称阵，在关系图中两个节点间若有有向弧必成对出现。 4．关系R 是反对称的，当且仅当关系矩阵中若1ij r =，则0ji r =，在关系图中两个节点间若有有向弧必单条出现。 5．设集合{}1,2,3X =，设关系R 为X 上的小于关系，则R=_{<1，2>，<1，3>， <2，3>}_，()R R =_{2，3}_，()D R =_{1，2}_。 6．一个二元关系的表达方式有三种，分别是、__序偶的集合_、_关系图_、_关系矩阵_。 7．设集合{}1,2,3,4A =，R 和S 均为A 上的二元关系，且{}1,2,3,4,R =<><> {}2,3,4,1S =<><>，则R S = _{<1，3>，<3，1>}_，S R = _{<2，4>，<4，2>}，R S R = _{<1，4>，<3，2>}，S R S = _{<2，1>，<4，3>}，R S R = _Φ。 8．设{},,A a b c =上的二元关系R ={，，， R 具备__反对称性，可传递性__性质，不具备性质 _自反性，反自反性，对称性_。 9．设{},,,A a b c d =上的二元关系R ={，，， _{，，，，， 10．设集合A 仅含有三个元素，则： A. 在A 上可定义__512_______种不同的二元关系； B. 在A 上可定义___64______种不同的自反关系； C. 在A 上可定义___64______种不同的反自反关系； D. 在A 上可定义____64_____种不同的对称关系； E. 在A 上可定义____64_____种不同的反对称关系。 11. 设R 是集合{}1,2,3,4,5,6,7,8,9,10A =上的模7同余关系，则[2]R =_{2,9}_ 12．设{},,A a b c =上的偏序集(),A ρ，则()A ρ的子集B ={{a },{b }，{a ，b },{b,c}，{}}的极大元是{，}，最大元是_无_，上界是{a ，b ，c }_，下确界是Φ。 13．{2,3,4,5,6,8,10,12,24},A R =是A 上整除关系，则A 的极大元是 10，24 _，极小元是_2，3，5__ 14．{1,2,3,,12},A R = 是A 上整除关系。子集{2,4,6}B =，则B 的最大元是无_，最小元是_2_, 极大元是 4，6 _，极小元是_2__，上界是 12 _，下界是 1，2 _，上确界是_12__，下确界是_2_。 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 1. 一个不是自反的关系，一定是反自反的。（×） 2．集合{},,A a b c =上的任何二元关系R 都不可能既是对称的又是反对称的.(×) 3、集合{},,A a b c =上的二元关系R ={，}是不可传递的.(×) 4. 若集合A 上的关系R 是对称的，则R 也是对称的.(√) 5. 若R 和S 是集合A 上的任意两个自反关系，则R S 也是自反的.(√) 6．若R 和S 是集合A 上的任意两个反自反关系，则R S 也是反自反的.(×) 7. 若R 和S 是集合A 上的任意对称关系，则R S 也是对称的.(×) 8．若R 和S 是集合A 上的任意传递关系，则R S 也是转递的.(×) 9．设R:X →Y 的关系，S:Y →Z 的关系，若R 的值域与S 的定义域的交集是空集，即()()R R D S =Φ ，则R S =Φ (√) 10．设R:X →Y 的关系，S:Y →Z 的关系，若()()R R D S ≠Φ ，则R S ≠Φ (√) 11．设123:,:,:R X Y R Y Z R Y Z →→→，则1231213()()()R R R R R R R = (×) 12．有限集上的不同关系的数目是无限多个的。(×) 13．如果R 是反对称的，则()t R 也是反对称的。(×) 14．如果R 是可传递的，则()s R 也是可传递的。(×) 15．设A 和B 是任意两个集合，若{},A B B A - 是A B ?的一个划分，则有A B ?(√) 16．给定一个非空集合，则它的划分是不唯一的。(√) 17．若R 和S 是集合A 上的关系，则()()()r R S r R r S = 。(√) 18．若R 和S 是集合A 上的关系，则()()()s R S s R s S = 。(√) 19．．若R 和S 是集合A 上的关系，则()()()t R S t R t S = 。(×) 20．平面上的三角形集合上的三角形相似关系是等价关系。(√) 21．平面上的直线集合上的直线间的平行关系是等价关系。(√) 22．是等价关系一定是相容关系，反之亦然。(×) 23．若R 和S 是集合A 上的等价关系，则R S 一定是等价关系(×) 24．若R 和S 是集合A 上的两个相容关系，则R S 与R S 都是相容关系(×) 25．若R 和S 是集合A 上的等价关系，则R S 一定是等价关系(√) 26．设,P <≤>是一个偏序集合，若最大成员存在，则该最大成员必然是极大成员。(√) 27．设,P <≤>是一个偏序集合，最小成员不一定存在，且若最大成员存在的话也不一定唯 一。(×) 28．．设,P <≤>是一个偏序集合，极小成员是不唯一的，且极小成员之间是不可比的，它们处于哈斯图的同一层。(√) 29．设,P <≤>是一个偏序集合，P 的某一个子集Q 可能没有上界，如果有也是不唯一的。(√) 30．设,P <≤>是一个偏序集合，Q P ?，如果y 是Q 的最大成员，则y 必是Q 的最小上界。(√) 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．若X≠Φ，则X上的空关系不具有的性质是( A ) A．自反性B．反自反性C．对称性D．可传递性 2．若X=Φ，则X上的空关系不具有的性质是( D ) A．自反性B．对称性C．可传递性D．不可传递性 ρ上的包含关系不具有的性质是( B ) 3．设A为一非空集合，则()A A．自反性B．对称性C．反对称性D．可传递性 ρ上的真包含关系不具有的性质是( A ) 4．设A为一非空集合，则()A A．自反性B．反自反性C．反对称性D．可传递性 5．设A={1，2，3}上的关系如下，有传递性的有（ D ） A．{<1，2 >，<2，1 >，<1，3>，<3，1>} B．{<1 ,3>，<3 ,1>} C．{<1，2 >，<2, 3 >，<1，1>} D．{<1 ,2 >，<3，2 >} 6．设R和S都是集合X上的二元关系，则下述结论正确的是（A） A．若R和S都是自反的，则R S 也是自反的 B．若R和S都是对称的，则R S 也是对称的 C．若R和S都是反对称的，则R S 也是反对称的 D．若R和S都是可传递的，则R S 也是可传递的 7．集合A={1,2,3,6}上的整除关系具有的性质是（C） A．自反性，对称性，可传递性B．反自反性，对称性，可传递性 C．自反性，反对称性，可传递性D．反自反性，反对称性，可传递性 8．实数集合R上的小于关系所具有的性质是（A） A．反自反性，反对称性，可传递性B．自反性，反对称性，可传递性 C．反自反性，对称性，可传递性D．自反性，对称性，可传递性 9．设A={1，2，3}，关系R是A上的二元关系，且R={<1，2 >}，则关系R所具有的性质是（B） A．自反性，反对称性，可传递性B．反自反性，反对称性，可传递性 C ．自反性，对称性，可传递性 D ．反自反性，反对称性 10．集合X 上的恒等关系所具有的性质是（A ） A ．自反性，对称性，反对称性，可传递性 B ．反自反性，可传递性 C ．反自反性，反对称性，可传递性 D ．都不是 11．关系R 所具有的关系矩阵1010010100100001R M ?? ? ?= ? ??? ，则关系R 所具有的性质是（B ） A ．自反的，对称的，可传递的B ．自反的，反对称的，可传递的 C ．自反的，对称的 D ．都不是 12．关系R 的关系图如图所示（图略R={<1，2 >,<2，3 >,<3，1 >}），则关系R 所具有的性质是（B ） A ．反自反的，反对称的，可传递的 B ．反自反的，反对称的 C ．反自反的，对称的，可传递的 D ．都不是 13．设R 是集合A 上的偏序关系，R 是R 的逆关系，则R R 是（B ） A ．偏序关系B ．等价关系C ．相容关系D ．都不是 14．集合A 上的关系R 是相容关系的必要条件是（B ） A ．自反的，反对称的 B ．自反的，对称的 C ．反自反的，对称的 D ．自反的，可传递的 15．设R 是集合X 中的二元关系，则下列结论不正确的是（D ） A ．若R 是自反的，则R 也是自反的B ．若R 是对称的，则R 也是对称的 C ．若R 是可传递的，则R 也是可传递的D ．都不是 16．设1R 和2R 都是集合X 上的等价关系，则下列结论正确的是（A ） A ．12R R 也是X 上的等价关系 B ．12R R 也是X 上的等价关系 C ．12R R 也是X 上的等价关系 D ．都不是 17．设R 和S 是集合A 上的相容关系，则下列结论中不正确的是（C ） A ．R S 也是A 上的等价关系 B ．R S 也是A 上的等价关系 C ．R S 也是A 上的等价关系 D ．都不是 18.．设R 是集合A 上的关系，则下列结论中不正确的是（D ） A ．R 是A 上的偏序关系，则R 也是A 上的偏序关系 B ．R 是A 上的全序关系，则R 也是A 上的全序关系 C ．R 是A 上的拟序关系，则R 也是A 上的拟序关系 D ．都不是 同步测试卷5：函数 一．填空： 1．设{},,,{,,},,,:A a b c B x y z R S T A B ==→的关系，且{},,,, S a x a y =<><>{},,,,,,R a x b y c y =<><><>{},,,,,,T a x b x c x =<><><>则 R 和T 可定义为A 到B 的函数。 2．设{}{1,2,3},,,{,,},:,:A B a b C x y z f A B g A C ===→→的函数，且有 {}1,,2,,3,,f a b b =<><><>{}1,,2,,3,,g x y z =<><><>则f 是满射函数，g 是双射函数。若有C h →B :的函数，且{},,,,h a x b x =<><>，则h 是既非单射也非满射。 3．设R 是实数集合，R R f →:，R R g →:，且()()x x g x x f 2,2==，则=f g 22x ，=g f x 4。 4．设},,{}2,1,0{:c b a f →的函数，且{}0,,1,,2,,f c a b =<><><>，则=-1f {},0,,1,,2c a b <><><>。 5．设{}1,2,3,,,A f g h =均为A 到A 的函数，即A A h g f →:,,，其中 {}1,1,2,1,3,1,f =<><><>{}1,1,2,3,3,2,g =<><><> {}1,3,2,1,3,1,h =<><><>则g 是单射，g 是满射，g 是双射。 6．设{}1,2,3,,,A R S T =是A 上的二元关系，且{}1,1,1,2,1,3R =<><><>， {}1,1,2,2,3,3S =<><><>，{}1,1,2,3,3,2T =<><><>，则这三个二元关系的逆关系中_S 和T__可以定义为A 到A 的函数。 7．设{}{1,2,3,4,5},,A B a b ==集，则可定义3225=种不同的从A 到A 的函数。 8．设I 是整数集合，I I f →:，且()x x x f 2-=，则f 是__单射___函数 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 2. 若f 和g 均为从X 到Y 的函数，则g f 也是从X 到Y 的函数。（×） 2．设Y X f →:的函数，Z Y g →:的函数，若()1-f g 是从X 到Z 的函数，则f 和g 均为单射函数。.(×) 3、设}1,0{},,,{==Y c b a X ，则从X 到Y 的函数共有32个。.(√) 4. 当X 和Y 都是有限集合时，若Y X f →:是满射函数，则Y X ≥.(√) 5. 当X 和Y 都是有限集合时，若Y X f →:是单射函数，则Y X ≤ (√) 6．当X 和Y 都是有限集合时，若Y X f →:是双射函数，则Y X = .(√) 7. ．设X X f X →=:},4,3,2,1{的关系，且 {}1,4,2,1,2,3,3,2,4,4,f =<><><><><>，则f 是函数.(×) 8设X X f X →=:},4,3,2,1{的关系，且给定{}1,1,3,1,4,2,f =<><><>，则f 不是从X 到X 的函数.(√) 9．设N 是自然数集合，N N f →:，且()22 +=j j f ，则f 是单射函数(√) 10．设N 是自然数集合，N N f →:，且())3(mod j j f =，则f 是满射函数.(×) 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．函数的复合运算满足( B ) A ．交换律 B ．结合律 C ．等幂律 D ．分配律 2．若f 和g 是满射函数，则f g 必是 ( C ) A ．函数 B ．单射 C ．满射 D ．双射 3．若f g 是满射函数，则( C ) A ．f 必是满射 B ．f 必是单射 C ．g 必是满射 D ．g 必是单射 4．若f g 是单射函数，则( B ) A ．f 必是满射 B ．f 必是单射 C ．g 必是满射 D ．g 必是单射 5．若f g 是双射函数，则( D ) A ．f ，g 必是满射 B ．f ，g 必是单射 C ．f 必是满射，g 必是单射 D ．f 必是单射，g 必是满射 6．设Y X f →:的函数，当f 是（ C ），f 才有反函数1-f 。 A ．单射 B ．满射 C ．双射 D ．函数 7．设N 是自然数集合，R 是实数集合，R N f →:，且给定()j j f 10log =，则（A ） A ．f 是单射 B ．f 是满射 C ．f 是双射 D ．都不是 8．设X 和Y 都是有穷集合，且n Y m X ==,，则从X 到Y 有（D ）种不同的双射函数。（要设满足存在双射的前提条件！） A ．n m +B ．n m ?C ．m n D ．!m 同步测试卷6：代数系统初步 一．填空： 1．如果A 是任意一个集合，*是一个二元运算，如果运算*对集合A 封闭，则称 2．设*是一个二元运算，如果运算*对集合A 封闭，则*是集合A 上的二元运算。 3．如果运算*是集合A 上的二元运算，则意味着运算*对集合A 封闭。 4．如果二元运算运算*对集合A 封闭，则意味着对任意的A b a ∈,有A b a ∈*。 5．设非空集合A 的幂集为)(A ρ，则在代数系统中>< ,),(A ρ，对于运算∩的 幺元是__A ，零元是Φ；对于∪运算的幺元是Φ，零元是_A_； 6．在代数系统中，其中I 是整数集合，运算“＋”是整数集I 上的普通 加法，则对于运算“＋”存在幺元_0_，对任意的元素的i I i ,∈的逆元为i -。 7．在代数系统中，其中I 是整数集合，×是普通的乘法，则对于运算× 存在幺元_1__，只有元素 1__和_-1_是可逆的。 8．设>< ,X 和><,*Y 是两个代数系统，其中 和*都是二元运算。若存在函数 Y X f →:且对任意的X b a ∈,有()()()b f a f b a f * ，则称f 是从>< ,X 到><,*Y 的同态。 9．给定代数系统>=<,*X U ，其中*是二元运算，E 是X 中的等价关系。如果等价关系E 对运算*满足_代换_性质，则称E 是代数系统U 中的_同余_关系。 10．设 11．设 12．设>=< ,X U 和>=<,*Y V 是两个代数系统，如果在U 和V 之间存在一个同构影射，则代数系统U 和V 的性质完全相同。 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 1．设 2．设 3、非空集合A 上的二元运算*封闭，则意味着对任意的A b a ∈,，有A b a ∈*。.( √ ) 4. 如果A 是任意非空集合，*是一个二元运算，则称 5. 如果A 是任意非空集合，*是集合A 上的一个二元运算，则称 6．设*是非空集合A 上的一个二元运算，A b ∈且对任意的A a ∈有b a b =*，则b 是A 中关于运算*的左幺元。( ×) 7.．设 8 设 9．在一个代数系统中，若每个元素都是等幂的，则运算一定是可结合的。 ( ×) 10．在一个代数系统中，若每个元素都是等幂的，则运算一定是可交换的。( ×) 11．若代数系统 12．设*是A 中可结合的二元运算，若A a ∈且是可逆的，则元素a 一定是可约的。.( √ ) 13．在整数集合I 上定义一个二元运算*为：2)(*-+=b a b a ，其中I b a ∈,，则 14．在整数集合I 上定义一个二元运算*为：2)(*-+=b a b a ，其中I b a ∈,，则运算*具有幺元。.( √ ) 15．设A 为任意非空集合，则联合运算 对集合A 的幂集)(A ρ是封闭的且A 是个幺元。( ×) 16．是个具有么元1的代数系统，其中I 是整数集.，则I 中任何元素都是不可逆的。( ×) 17．设 18．设f 是代数系统>< ,X 到><,*Y 同态，若运算 是可交换的，则运算*也是可交换的。( ×) 19．设E 是代数系统>< ,X 的关系，若E 对*满足代换性质，则E 必是>< ,X 上的同余关系。( ×) 20．设Q 是有理数集合，Q 上的二元运算*的定义为：Q b a ab b a b a ∈-+=,,*，则运算*是可结合的。.( √ ) 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．设A={1,2,…,10},下面的哪种运算对于集合A 是不封闭的？ ( C ) A ．),max (*b a b a = B ．),min(*b a b a = C ．b a b a -=* D ．)10)(mod (*b a b a += 2．在自然数N 中，下列哪种运算是可结合的？( B ) A ．b a b a -=* B ．),max (*b a b a = C ．b a b a 2*+= D ．||*b a b a -= 3．设A={0,1,2,3},下列的哪种运算是不可交换的？ ( D ) A ．)3)(mod (*b a b a += B ．),max (*b a b a = C ．),min(*b a b a = D ．b a b a -=* 4．设A={0,1},下列哪种运算可使 A ．b a b a -=* B ．)2,max (*b a b a = C ．b a b a +=* D ．||*b a b a -= 5．设A={0,1},下列哪种运算不能使 A ．)2)(mod (*b a b a += B ．b a b a -=* C ．b b a =* D ．),max (*b a b a = 6．设U=<{0,1},×>是一个代数系统，则（A ）是U 的子代数系统。 A ．<{1},×> B ．<{1},+> C ．<{0},+> D ．<Φ,×> 7．设A={1,2,…,10},下面的哪种运算对于集合A 是不封闭的？ ( D ) A ．),max (*b a b a = B ．),min(*b a b a = C ．b a b a ,*=的最大公约数 D ．b a b a ,*=的最大公倍数 8．在自然数N 中，下列哪种运算是不可结合的？( C ) A ．3*++=b a b a B ．),min(*b a b a = C ．b a b a 2*+= D ．)3)(mod (*ab b a = 9．设Q 是有理数集合，Q 上的运算*的定义为：Q b a ab b a b a ∈-+=,,*，则运算*（B ）。 A ．不可交换的 B ．可交换且可结合的 C ．不可结合的 D ．可交换但不可结合 10．设>< ,X 到><,*Y 是两个代数系统，f 是>< ,X 到><,*Y 的同态，则（D ） A ．运算 与运算*性质完全相同 B ．运算 具有的性质，运算*不一定具有 C ．运算*与运算 性质完全相同 D ．运算*具有的性质，运算 不一定具有 《 离散数学 》 同步测试卷7:半群、独异点与群 一．填空： 1．设 的子半群。 2．设 e>是 3．给定一个半群U= 4．设 5．设 数幂，则把 6．设 8．集合{[0],[1],[2],,[1]}m Z m =- ，在m Z 上定义运算m +为：对任意的[],[]m i j Z ∈ 有：[][][()(mod )]m i j i j m +=+则,m m Z <+>幺元是_0_，[]m i Z ∈逆元是[]m i -。 9．设H 是有限群G 的子群，则H 的阶必__整除__G 的阶。 10．一个由a 生成的循环群 二．判断下列命题的对错。正确的在括号内填√,错误的在括号内填×。 3. 设 义为*a b a =，则 2．设 3、设 4. 设 5. 设 6．设 7. 设 8．若半群 9．若半群 10．若半群 11．若半群 12．循环半群 13．如果 14．设 15．如果 16．如果 17．设:f X Y →是群,*U X =<>到,*V Y =<>的群同态。 则有：如果U 是个阿贝尔群，则V 也一定是个阿贝尔群。(√) 18．设:f X Y →是群,*U X =<>到,*V Y =<>的群同构。 则有：如果U 是个阿贝尔群，则V 也一定是个阿贝尔群。(√) 19．非循环群的每一个子群也必是个非循环群。(×) 20．设I 为整数集合，定义I 上的二元运算为：对任意的,x y I ∈有*2x y x y =+-，则 三、在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内(多选不给分)。 1．下列运算中，哪种运算关于整数集合不能构成半群？( D ) A ．*max(,)a b a b = B ．*a b b = C ．*2a b ab = D ．*||a b a b =- 2．R 为实数集合，运算*的定义为：对任意的,x y R ∈有*||x y x y =?，则代数系统,*R <>是( A ) A ．半群 B ．独异点 C ．群 D ．阿贝尔群 3．设集合A={0，1}，下列哪种运算可使 A ．*a b a b =- B ．*max(,2)a b a b = C ．*a b ab = D ．*||a b a b =- 4．在自然数N 上，下列哪种运算可使 A ．*a b a b =- B ．*max(,)a b a b = C ．*a b ab = D ．*||a b a b =- 5．设Q 是有理数集合，Q 上的运算*定义为*2a b a b =+-，则,*Q <>不能构成（ C ） 第二章 命题逻辑 习题．解 ⑴不是陈述句，所以不是命题。 ⑵x 取值不确定，所以不是命题。 ⑶问句，不是陈述句，所以不是命题。 ⑷惊叹句，不是陈述句，所以不是命题。 ⑸是命题，真值由具体情况确定。 ⑹是命题，真值由具体情况确定。 ⑺是真命题。 ⑻是悖论，所以不是命题。 ⑼是假命题。 2．解 ⑴是复合命题。设p ：他们明天去百货公司；q ：他们后天去百货公司。命题符号化为q p ∨。 ⑵是疑问句，所以不是命题。 ⑶是悖论，所以不是命题。 ⑷是原子命题。 ⑸是复合命题。设p ：王海在学习；q ：李春在学习。命题符号化为p q 。 ⑹是复合命题。设p ：你努力学习；q ：你一定能取得优异成绩。p q 。 ⑺不是命题。 ⑻不是命题 ⑼。是复合命题。设p ：王海是女孩子。命题符号化为：p 。 3．解 ⑴如果李春迟到了，那么他错过考试。 ⑵要么李春迟到了，要么李春错过了考试，要么李春通过了考试。 ⑶李春错过考试当且仅当他迟到了。 ⑷如果李春迟到了并且错过了考试，那么他没有通过考试。 4．解 ⑴p (q r )。⑵p q 。⑶q p 。⑷q p 。 习题 1．解 ⑴是1层公式。 ⑵不是公式。 ⑶一层： p q ，p 二层： p q 所以，)()(q p q p ??→∨是3层公式。 ⑷不是公式。 ⑸(p q )(q ( q r ))是5层公式，这是因为 一层：p q ，q ，r 二层：q r 三层：q ( q r ) 四层： (q ( q r )) 2．解 ⑴A =(p q )q 是2层公式。真值表如表2-1所示： 表2-1 p q q p ∨ A 0 0 0 0 0 1 1 1 1 0 1 0 1 1 1 1 ⑵p q p q A →→∧=)(是3层公式。真值表如表2-2所示： 一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。 9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 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 的关系图为 一、单项选择题(本大题共15小题，每小题1分，共15分)在每小题列出的四个选 项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。 1.一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它具有一条( ) A.汉密尔顿回路 B.欧拉回路 C.汉密尔顿通路 D.初级回路 2.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是( ) A.10 B.12 C.16 D.14 3.在布尔代数L中，表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是( ) A.b∧(a∨c) B.(a∧b)∨(a’∧b) C.(a∨b)∧(a∨b∨c)∧(b∨c) D.(b∨c)∧(a∨c) 4.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的子群是( ) A.<{1},·> B.〈{-1},·〉 C.〈{i},·〉 D.〈{-i},·〉 5.设Z为整数集，A为集合，A的幂集为P(A),+、-、/为数的加、减、除运算，∩为集合的交 运算，下列系统中是代数系统的有( ) A.〈Z，+，/〉 B.〈Z，/〉 C.〈Z，-，/〉 D.〈P(A)，∩〉 6.下列各代数系统中不含有零元素的是( ) A.〈Q，*〉Q是全体有理数集，*是数的乘法运算 B.〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合，*是矩阵乘法运算 C.〈Z， Z是整数集， 定义为x xy=xy,?x,y∈Z D.〈Z，+〉，Z是整数集，+是数的加法运算 7.设A={1,2,3}，A上二元关系R的关系图如下： R具有的性质是 A.自反性 B.对称性 C.传递性 D.反自反性 8.设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) A.R∪I A B.R C.R∪{〈c,a〉} D.R∩I A 9.设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}∪R为X上的 等价关系，R应取( ) A.｛〈c,a〉，〈a,c〉｝ B.{〈c,b〉，〈b,a〉} C.{〈c,a〉，〈b,a〉} D.{〈a,c〉，〈c,b〉} 10.下列式子正确的是( ) A. ?∈? B.??? C.{?}?? D.{?}∈? 11.设解释R如下：论域D为实数集，a=0,f(x,y)=x-y,A(x,y):x 离散数学（课件上习题） 第一章 例1-1.1 判定下面这些句子哪些是命题。 ⑴2是个素数。 ⑵雪是黑色的。 ⑶2013年人类将到达火星。 ⑷如果a>b且b>c，则a>c 。（其中a,b,c都是 确定的实数） ⑸x+y<5 ⑹请打开书！ ⑺您去吗？ ⑴⑵⑶⑷是命题 例1-2.1 P：2是素数。 ?P：2不是素数。 例1-2.2 P：小王能唱歌。 Q：小王能跳舞。 P∧Q：小王能歌善舞。 例1-2.3. 灯泡或者线路有故障。（析取“∨”） 例1-2.4. 第一节课上数学或者上英语。（异或、排斥或。即“?”） 注意：P ?Q 与(P∧?Q)∨(Q∧?P ) 是一样的。 归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：（1）否定“?”(2) 合取“∧”(3) 析取“∨”(4) 异或“?”(5) 蕴涵“→”(6) 等价“?” 例1-2.5：P表示：缺少水分。 Q表示：植物会死亡。 P→Q：如果缺少水分，植物就会死亡。 P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”。 也说成P是P→Q 的前件，Q是P→Q的后件。 还可以说P是Q的充分条件，Q是P的必要条件。 以下是关于蕴含式的一个例子 P：天气好。Q：我去公园。 1.如果天气好，我就去公园。 2.只要天气好，我就去公园。 3.天气好，我就去公园。 4.仅当天气好，我才去公园。 5.只有天气好，我才去公园。 6.我去公园，仅当天气好。 命题1.、2.、3.写成：P→Q 命题4.、5.、6.写成：Q→P 例1-2.6：P：△ABC 是等边三角形。Q ：△ABC是等角三角形。 P?Q ：△ABC 是等边三角形当且仅当它是等角三角形。 离散数学考试试题（A卷及答案） 一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？ 1)((P→Q)∧Q)?((Q∨R)∧Q) 2)?((Q→P)∨?P)∧(P∨R) 3)((?P∨Q)→R)→((P∧Q)∨R) 解：1)永真式；2）永假式；3)可满足式。 二、（8分）个体域为{1，2}，求?x?y（x+y=4）的真值。 解：?x?y（x+y=4）??x（（x+1=4）∨（x+2=4）） ?（（1+1=4）∨（1+2=4））∧（（2+1=4）∨（2+1=4）） ?（0∨0）∧（0∨1） ?1∧1?0 三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？ 解：因为|P(A×B)|=2|A×B|=2|A||B|=2mn，所以A到B的二元关系有2mn个。因为|BA|=|B||A|=mn，所以A到B的函数mn个。 四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。 解：r(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<2,2>,<3,3>,<4,4>,<5,5>} s(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<3,2>,<4,3>,<4,5>} t(R)={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>,<1,1>,<1,3>,<2,2>,<2,4>,<1,4>} 五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。 解设A、B、C分别表示骑旋转木马、坐滑行铁道、乘宇宙飞船的儿童组成的集合，|A∩B∩C|＝20，|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|＝55，|A|＋|B|＋|C|＝70/0.5＝140。 由容斥原理，得 |A∪B∪C|＝|A|＋|B|＋|C|―|A∩B|―|A∩C|―|B∩C|＋|A∩B∩C| 所以 |A∩B∩C|＝75－|A∪B∪C|＝75－(|A|＋|B|＋|C|)＋(|A∩B|＋|A∩C|＋|B∩C|－2|A∩B∩C|)＋|A∩B∩C|＝75－140＋55＋20＝10 没有乘坐过其中任何一种的儿童共10人。 六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R ∩S=[a]R∩[a]S。 解：?x∈A，因为R和S是自反关系，所以 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明: 《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (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 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。 离散数学练习题 1、图中度为零的结点称为孤立结点。 A. 正确 B. 错误 正确：【A】 2、域是整环。 A. 正确 B. 错误 正确：【A】 3、有限格都是有界格。 A. 正确 B. 错误 正确：【A】 4、连通且不含圈的图称为树。 A. 正确 B. 错误 正确：【A】 5、“如果1+1≠3，则2+2≠4”是真命题。 A. 正确 B. 错误 正确：【B】 6、无向图G为欧拉图，则G是连通的。 A. 正确 B. 错误 正确：【A】 7、若A和B都是谓词公式，则(A∧B)、(A∨B)、(A→B)、(A<->B)都是谓词公式。 A. 正确 B. 错误 8、设A, B, C是命题公式，则AVBV﹁C 也是命题公式。 A. 正确 B. 错误 正确：【A】 9、设〈L，≤〉是格，则格的交∧和并∨运算满足等幂律。 A. 正确 B. 错误 正确：【A】 10、“x+3>1。”是命题。 A. 正确 B. 错误 正确：【B】 11、半群满足交换律。 A. 正确 B. 错误 正确：【B】 12、在任何图中，奇数度的结点数必是偶数。 A. 正确 B. 错误 正确：【A】 13、在格〈L，∨，∧〉中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的。 A. 正确 B. 错误 正确：【A】 14、完全图Kn没有割集，它的连通性能是最好的。 A. 正确 B. 错误 15、对任意集合A，都有??A。 A. 正确 B. 错误 正确：【A】 17、强连通图一定是单向连通图。 A. 正确 B. 错误 正确：【A】 18、代数系统〈G，°〉为群的条件是存在零元素。 A. 正确 B. 错误 正确：【B】 19、对应日常生活中的“任意的”，“所有的”，“一切的”等词，用符号“任意”表示。 A. 正确 B. 错误 正确：【A】 20、如果a是集合A中的元素，则称a属于A，记作a?A。 A. 正确 B. 错误 正确：【B】 21、A,B是集合,P（A），P（B）为其幂集,且,则P(A)∩P(B)为（） A. B. C. D. 正确：【B】 22、设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)?f2(x)=0的解 一、单项选择题：（每小题1分，本大题共10分） 1．命题公式)(P Q P ∨→是（ ）。 A 、 矛盾式； B 、可满足式； C 、重言式； D 、等价式。 2．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。 3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。 A 、自由变元； B 、约束变元； C 、既是自由变元又是约束变元； D 、既不是自由变元又不是约束变元。 4．在0 Φ之间应填入（ ）符号。 A 、= ； B 、? ； C 、∈ ； D 、? 。 5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。 A 、 B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一； C 、B 的上界B b ∈且不唯一； D 、B 的上确界A b ∈且唯一。 6．在自然数集N 上，下列（ ）运算是可结合的。 （对任意N b a ∈,） A 、b a b a -=* ； B 、),max(b a b a =* ； C 、b a b a 5+=* ； D 、b a b a -=*。 7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则 离散数学命题逻辑练习 题 TTA standardization office【TTA 5AB- TTAK 08- TTA 2C】 一、选择题 1. 设命题公式) ?，记作G，使G的真值指派为1的P，Q，R的真值是( ) P∧ → (R Q 2. 与命题公式P（QR）等价的公式是( ) A () →→ D () P Q R P Q R →∨ P Q R ∨→ B () P Q R ∧→ C () 3. 下列各组公式中，哪组是互为对偶的 ( ) A ,P P B ,P P A A** D ,A A ? C ,() (其中P为单独的命题变元，A为含有联结词的公式) 4. 命题公式(P∧(P→Q))→Q是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中，哪个是最小联结词 ( ) A {,} ∧→ ?∧∨ C {}↑ D {,} ? B {,,} 6. 命题公式() ?∧→的主析取范式种含小项的个数为 ( ) P Q R A 8 B 3 C 5 D 0 7. 如果A B ?成立，则以下各种蕴含关系哪一个成立 ( ) A B A ?? ??? D A B ??? C B A ? B A B 8. 命题公式()() →∧→的主析取范式中包含小项 ( ) P Q P R A P Q R ∧?∧? ∧?∧ D P Q R ∧∧? C P Q R ∧∧ B P Q R 9. ,, A B C为任意命题公式，当（）成立时，有A B ?。 A A B ∧?∧ D C A C B →?→??? B A C B C ∨?∨ C A C B C 10. 下面4个推理定律中，不正确的是 ( ) A () ∨∧?? A B A B A A B ?∧ B () C () →∧??? A B B A A B A B →∧? D () 一、选择题 1. 设命题公式)(R Q P ∧→?，记作G ，使G 的真值指派为1的P ，Q ，R 的真值是( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 2. 与命题公式P ?（Q ?R ）等价的公式是( ) A ()P Q R ∨→ B ()P Q R ∧→ C ()P Q R →→ D ()P Q R →∨ 3. 下列各组公式中，哪组是互为对偶的 ( ) A ,P P B ,P P ? C ,()A A ** D ,A A (其中P 为单独的命题变元，A 为含有联结词的公式) 4. 命题公式(P ∧(P →Q))→Q 是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5. 下面命题联结词集合中，哪个是最小联结词 ( ) A {,}? B {,,}?∧∨ C {}↑ D {,}∧→ 6. 命题公式()P Q R ?∧→的主析取范式种含小项的个数为 ( ) A 8 B 3 C 5 D 0 7. 如果A B ?成立，则以下各种蕴含关系哪一个成立 ( ) A B A ? B A B ??? C B A ??? D A B ?? 8. 命题公式()()P Q P R →∧→的主析取范式中包含小项 ( ) A P Q R ∧∧ B P Q R ∧∧? C P Q R ∧?∧ D P Q R ∧?∧? 9. ,,A B C 为任意命题公式，当（ ）成立时，有A B ?。 A A B ??? B A C B C ∨?∨ C A C B C ∧?∧ D C A C B →?→ 10. 下面4个推理定律中，不正确的是 ( ) A ()A A B ?∧ B ()A B A B ∨∧?? C ()A B A B →∧? D ()A B B A →∧??? 11. 下列命题公式是等价公式的为（ ）． A ．?P??Q ?P?Q B ．A?(?B?A) ??A?(A?B) C ．Q ?(P?Q )??Q ?(P?Q ) D ．?A?(A?B) ?B 离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（） 模拟试卷一 一、判断选择题（共 10 分，每小题 1 分） ( ) 1.（?pú?q）?(p??q)不是重言式 ( ) 2.设 A，B，C 是Q 的子集，则有 A′(B?C)1（A′B）?（A′C）。 ( ) 3. 命题函数是命题。（ ） ( ) 4. 设无向图G 具有割点，则G 中一定不存在汉密尔顿回路； ( ) 5. 有向图 G是单侧连通； （G） 6 1) 一个命题公式的对偶式是唯一的 2) 一个命题公式的摄取范围是唯一的 3) 一个命题公式的真值表示唯一的 4) 一个命题公式的重叠式是唯一的 哪些命题式正确的 A 1)与 4) B 2)与 3) C 1)与 3) D 3)与 4) 7 下列叙述中错误的是（ ） A 若 AUB=AUC，则 B=C B 若 7A∩B=7A∩C，则 B=C C 若 CU(A∩C)=B∩(BU7A)，则 B=C D 若 A x B = B x C，则 B=C 8 下列叙述中错误的是（ ） A 有些关系既是对称，又是反对称的 B 有些关系既是自反的，又是反自反的 C 有些关系既不对称，又不反对称的 D 有些关系既不是自反的，又不是反自反的 9 在一个代数系统中( ) A 单位元可能也是零元 B 独异点中，所有元素都没有逆元 C 有左单位元就不可能有右单位元 D 某个元素有多个左逆元，就不可能有右逆元 10 一个简单连通无向图有 n个结点，它的边数至少有（ ） A 一条 B n-1 条 C n条 D n+1 条 二、逻辑推证 （1）?（P?Q）?? (RúS)，((Q?P) ú?R) ，?(R?P) T P?Q 若 S={1，2，3，…… ，19，20}，设 R 为 S 上的等价关系，且由 xoy (mod 5) 所定义，即 x- y 能被 5 整除。写出由 R 导出的 S 的划分和商集 S/R。 十二. 设（S,*）是一个有单位元的半群，a∈S，且有左逆元 u 和右逆元 v，证明 u=v。 十三. 证明：设（G，*）是一个半群，如果对于G 中任意 a, b, 方程a*y=b 和 y*a=b 在 G 中都有解，则G 是一个群。 十四. 设 G 是有 n-1 条边的图（n 是 G 的顶点数）。证明：如果 G 中无圈，那么 G 是一棵树。 离散数学试题 第一部分选择题 一、单项选择题 1．下列是两个命题变元p，q的小项是（ C ） A．p∧┐p∧q B．┐p∨q C．┐p∧q D．┐p∨p∨q 2．令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ D ）A．p→┐q B．p∨┐q C．p∧q D．p∧┐q 3．下列语句中是命题的只有（ A ） A．1+1=10 B．x+y=10 C．sinx+siny<0 D．x mod 3=2 4．下列等值式不正确的是（ C ） A．┐(?x)A?(?x)┐A B．(?x)(B→A(x))?B→(?x)A(x) 02324# 离散数学试题第1 页共4页 C．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) D．(?x)(?y)(A(x)→B(y))?(?x)A(x)→(?y)B(y) 5．谓词公式(?x)P(x,y)∧(?x)(Q(x,z)→(?x)(?y)R(x,y,z)中量词?x的辖域是（ C ）A．(?x)Q(x,z)→(?x)(?y)R(x,y,z)) B．Q(x,z)→(?y)R(x,y,z) C．Q(x,z)→(?x)(?y)R(x,y,z) D．Q(x,z) 6．设A={a,b,c,d}，A上的等价关系R={ 一、填空 1．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶数） 则 =?B A {0，1，2，3，4，6}； 。 2．A ，B ，C 表示三个集合，文图中阴影部分的集合表达式为 A C B -⊕)( 。 3．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 1 。 4．公式P R S R P ?∨∧∨∧)()(的主合取范式为 )()(R S P R S P ∨?∨?∧∨∨? 。 5．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 {<1,1>, <1,3>, <2,2>, <2,4> } 。 6. P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 Q P →?； ；“虽然你努力了，但还是失败了”的翻译为 Q P ∧ 。 7.论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 T 。 二、选择 1、下列是真命题的有（ C D ） A ． }}{{}{a a ?； B ．}}{,{}}{{ΦΦ∈Φ； C ． }},{{ΦΦ∈Φ； D ． }}{{}{Φ∈Φ。 2、下列集合中相等的有（B 、C ） A ．{4，3}Φ?； B ．{Φ，3，4}； C ．{4，Φ，3，3}； D ． {3，4}。 3、设全集U 是实数集R ，，，则图 中阴影部分所表示的集合是( C ). A. B. C. D. 4、在下述公式中是重言式为（ B 、D ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→。 5、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（D ），成真赋值的个数为（ D ）。 A ．0； B ．1； C ．2； D ．3 。 6、给定推理 ①))()((x G x F x →? P ②)()(y G y F → ③)(x xF ? P ④)(y F ⑤)(y G ⑥)(x xG ? )())()((x xG x G x F x ??→?∴ 推理过程中错在（ C ）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤; E 、⑤->⑥ 三、逻辑判断 1. 用等值演算法和真值表法判断公式)())()((Q P P Q Q P A ??→∧→=的类型。 离散数学实验报告 1．【实验题目】 实验一命题逻辑（1） 2．【实验目的】 熟悉掌握命题逻辑中的联接词，实现二元合取、析取、蕴涵和等价表达式的计算，熟悉连接词逻辑运算规则，利用程序语言实现其逻辑运算。 3．【实验内容】 从键盘输入两个命题变元P和Q的真值，求它们的合取、析取、条件和双条件的真值。 4. 【实验要求】 通过以下界面提示实现相应逻辑运算，给出具体逻辑值 **************************************************************** 请输入变量命题P和Q的值（1或0）： 请选择（1—5）要进行的逻辑运算： 1.合取运算（P∧Q） 2.析取运算（P∨Q） 3.条件运算（P→Q） 4.双条件运算（P←→Q） 5.继续/退出（y/n） **************************************************************** 5. 【算法描述】 1.合取运算（P∧Q），P、Q同真时为真，其余为假。 2.析取运算（P∨Q），P、Q同假时为假，其余为真。 3.条件运算（P→Q），P为真，Q为假时，为假，其余为真。 4.双条件运算（P←→Q），P、Q同真同假是为真。 6. 【源程序（带注释）】 #include class math { char p,q; int result; public: math(char x,char y); int pdp(char x); int pdq(char y); hequ(char x,char y,int t); xiqu(char x,char y,int t); tiaojian(char x,char y,int t); shuangtiaojian(char x,char y,int t); caidan(); }; //判断p是否为1或0 int math::pdp(char x) { int a; p=x; if(x!='0'&&x!='1') { //cout<<"错误"< 一、选择题 1、 设命题公式)(R Q P ∧→?,记作G ,使G 的真值指派为1的P ,Q ,R 的真值就是( ) 0,0,1)D (0,1,0)C (1,0,0)B (0,0,0)A ( 2、 与命题公式P →(Q →R )等价的公式就是( ) A ()P Q R ∨→ B ()P Q R ∧→ C ()P Q R →→ D ()P Q R →∨ 3、 下列各组公式中,哪组就是互为对偶的 ( ) A ,P P B ,P P ? C ,()A A ** D ,A A (其中P 为单独的命题变元,A 为含有联结词的公式) 4、 命题公式(P ∧(P →Q))→Q 就是_____式。 A 重言 B 矛盾 C 可满足 D 非永真的可满足 5、 下面命题联结词集合中,哪个就是最小联结词 ( ) A {,}?€ B {,,}?∧∨ C {}↑ D {,}∧→ 6、 命题公式()P Q R ?∧→的主析取范式种含小项的个数为 ( ) A 8 B 3 C 5 D 0 7、 如果A B ?成立,则以下各种蕴含关系哪一个成立 ( ) A B A ? B A B ??? C B A ??? D A B ?? 8、 命题公式()()P Q P R →∧→的主析取范式中包含小项 ( ) A P Q R ∧∧ B P Q R ∧∧? C P Q R ∧?∧ D P Q R ∧?∧? 9、 ,,A B C 为任意命题公式,当( )成立时,有A B ?。 A A B ??? B A C B C ∨?∨ C A C B C ∧?∧ D C A C B →?→ 10、 下面4个推理定律中,不正确的就是 ( ) A ()A A B ?∧ B ()A B A B ∨∧?? C ()A B A B →∧? D ()A B B A →∧??? 11、 下列命题公式就是等价公式的为( ). A.?P ∧?Q ?P ∨Q B.A →(?B →A) ??A →(A →B) C.Q →(P ∨Q )??Q ∧(P ∨Q ) D.?A ∨(A ∧B) ?B 离散数学试题(B卷答案1） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R) ?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R) ?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R ?T∧R(置换)?R 2) ?x (A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x)) ??x?A(x)∨?xB(x) ???xA(x)∨?xB(x) ??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分）。 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D，(C∨D)→?E，?E→(A∧?B)，(A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)，I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 第二章 命题逻辑 习题2、11.解 ⑴不就是陈述句,所以不就是命题。 ⑵x 取值不确定,所以不就是命题。 ⑶问句,不就是陈述句,所以不就是命题。 ⑷惊叹句,不就是陈述句,所以不就是命题。 ⑸就是命题,真值由具体情况确定。 ⑹就是命题,真值由具体情况确定。 ⑺就是真命题。 ⑻就是悖论,所以不就是命题。 ⑼就是假命题。 2.解 ⑴就是复合命题。设p :她们明天去百货公司;q :她们后天去百货公司。命题符号化为q p ∨。 ⑵就是疑问句,所以不就是命题。 ⑶就是悖论,所以不就是命题。 ⑷就是原子命题。 ⑸就是复合命题。设p :王海在学习;q :李春在学习。命题符号化为p ∧q 。 ⑹就是复合命题。设p :您努力学习;q :您一定能取得优异成绩。p →q 。 ⑺不就是命题。 ⑻不就是命题 ⑼。就是复合命题。设p :王海就是女孩子。命题符号化为:?p 。 3.解 ⑴如果李春迟到了,那么她错过考试。 ⑵要么李春迟到了,要么李春错过了考试,要么李春通过了考试。 ⑶李春错过考试当且仅当她迟到了。 ⑷如果李春迟到了并且错过了考试,那么她没有通过考试。 4.解 ⑴?p →(q ∨r )。⑵p →q 。⑶q →p 。⑷q → p 。 习题2、2 1.解 ⑴就是1层公式。 ⑵不就是公式。 ⑶一层: p ∨q ,?p 二层:?p ?q 所以,)()(q p q p ??→∨就是3层公式。 ⑷不就是公式。 ⑸(p →q )∧?(?q ?( q →?r ))就是5层公式,这就是因为 一层:p →q ,?q ,?r 二层:q →?r 三层:?q ?( q →?r ) 四层:?(?q ?( q →?r )) 2.解 ⑴A =(p ∨q )∧q 就是2层公式。真值表如表2-1所示: 表2-1 ⑵p q p q A →→∧= )(就是3层公式。真值表如表2-2所示:离散数学答案命题逻辑
离散数学试卷及答案(2)
离散数学试卷及答案
离散数学(命题逻辑)课后总结
离散数学考试试题(A卷及答案)
离散数学考试试题(A、B卷及答案)
离散数学第一章命题逻辑知识点总结
《离散数学》练习题和参考答案
离散数学练习题
离散数学试卷及答案7
的幺元为（ ）。 A 、a ； B 、b ； C 、1； D 、0。
离散数学命题逻辑练习题
离散数学命题逻辑练习题
离散数学期末练习题 (带答案)
离散数学模拟试卷一
最新离散数学练习题(含答案)
离散数学小测试题及答案
离散数学实验一：命题逻辑(1).
离散数学命题逻辑练习题
离散数学期末考试题及答案
离散数学答案命题逻辑
相关主题
文本预览