离散数学习题
- 格式:doc
- 大小:425.50 KB
- 文档页数:82
离散数学试题第一部分选择题一、单项选择题1.下列是两个命题变元p,q的小项是( C )A.p∧┐p∧q B.┐p∨qC.┐p∧q D.┐p∨p∨q2.令p:今天下雪了,q:路滑,则命题“虽然今天下雪了,但是路不滑”可符号化为( D )A.p→┐q B.p∨┐qC.p∧q D.p∧┐q3.下列语句中是命题的只有( A )A.1+1=10 B.x+y=10C.sinx+siny<0 D.x mod 3=24.下列等值式不正确的是( C )A.┐(∀x)A⇔(∃x)┐AB.(∀x)(B→A(x))⇔B→(∀x)A(x)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={<a,b>,<b,a>,<c,d>,<d,c>}∪I A,则对应于R的A的划分是( D )A.{{a},{b,c},{d}} B.{{a,b},{c},{d}}C.{{a},{b},{c},{d}} D.{{a,b},{c,d}}7.设A={Ø},B=P(P(A)),以下正确的式子是( A )A.{Ø,{Ø}}∈B B.{{Ø,Ø}}∈BC.{{Ø},{{Ø}}}∈B D.{Ø,{{Ø}}}∈B8.设X,Y,Z是集合,一是集合相对补运算,下列等式不正确的是( A )A.(X-Y)-Z=X-(Y∩Z)B.(X-Y)-Z=(X-Z)-YC.(X-Y)-Z=(X-Z)-(Y-Z)D.(X-Y)-Z=X-(Y∪Z)9.在自然数集N上,下列定义的运算中不可结合的只有( D )A.a*b=min(a,b)B.a*b=a+bC.a*b=GCD(a,b)(a,b的最大公约数)02324# 离散数学试题第1 页共4页02324# 离散数学试题 第 2 页 共4页D .a*b=a(mod b)10.设R 和S 是集合A 上的关系,R ∩S 必为反对称关系的是( A ) A .当R 是偏序关系,S 是等价关系; B .当R 和S 都是自反关系; C .当R 和S 都是等价关系; D .当R 和S 都是传递关系11.设R 是A 上的二元关系,且R ·R ⊆R,可以肯定R 应是( D ) A .对称关系; B .全序关系; C .自反关系; D .传递关系第二部分 非选择题二、填空题1.设论域是{a,b,c},则(∀x)S(x)等价于命题公式 S(a)∧S(b)∧S(c) ;(x ∃)S(x)等价于命题公式 S(a)∨S(b) ∨S(c) 。
离散数学一、选择题1△O Y C3A^Q un ㊉iv1.设:P:张三可以作这件事,Q:李四可以作这件事,命题“张三或李四都可以做这件事”的符号化为()A、PVQB、PVi QC、P—QD、-P V -Q2.谓词公式V x(P(x)V m yR(y))fQ(x)中量词V x的作用域是()A. V x(P(x) V3yR(y))B.P(x)C. (P(x) V3yR(y)) D,P(x), Q(x)3.若个体域为整体域,下列公式中哪个值为真?()A. V x 3y(x+y=0)B. 3y V x(x+y=0)C. V x V y(x+y=0)D. n 3x 3y(x+y=0)4.空集①的幂集P (①)的基数是()A. 1B.2C.3D.45.设R、S是集合A上的任意关系,则下面命题是真命题的是()。
A.若R、S是自反的,则R・S是自反的B.若R、S是反自反的,则R・S是反自反的C.若R、S是对称的,则R・S是对称的D.若R、S是传递的,则R・S是传递的6.集合 A={1, 2,…,10}上的关系 R={(x, y)|x+y=10 且x, y£A},则 R 的性质为()A.自反的B.对称的C.传递的,对称的口.非自反的,传递的7.含有5个结点,3条边的不同构的简单图有()A.2个B.3个C.4个D.5个8.设G (n, m),且G中每个结点的度数不是K就是K+1,则G中度数为K的结点数()A.2/nB.n(n+1)C.nkD.n(k+1)-2m9.设谓词P(x) :x是奇数,Q(x):x是偶数,谓词公式m(x) (P(x) AQ(x))在下面哪个论域中是可满足的。
()A自然数集 B整数集 C实数集 D以上均不成立10.设C(x): x是运动员,G(x): x是强壮的。
命题“没有一个运动员不是强壮的”可符号化为()A. n V x(C(x) A n G(x))B. iV xOx) — G(x))C. _|m x(C(x)A_|G(x))D. im x(C(x) - 1 G(x))11.设集合 M={x|f (x) =0}, N={x|g (x) =0},则方程 f (x)・g (x) =0 的解集是()A.MANB.MUNC.M ㊉ ND.M-N12.设A=/"a}},下列选项错误的是()A. {a} e p(A)B. {a}U p(A)C. {{a}} e p(A)D. {{a}} e p(A)13.设A={1,2,3,4,5},p{<i,j>|i<j,i,j £ A}则 p 逆的性质是()A.对称的B.自反的C.反对称的D.反自反,反对称,传递的14.设R和S是集合A上的等级关系,则RUS的对称性()A. 一定成立B.一定不成立C.不一定成立D.不可能成立15. K4中含有3条边的不同构生成子图有()A.1个B.3个C.4个D.2个16.设G=<V,E>为无向图,u,v £V,若u,v连通,则()A.d(u,v)>0B.d(u,v)=0C.d(u,v)<0D.d(u,v)三0二、填空题1.命题公式I(P-Q)的主析取范式为(),主合取式的编码表示为().2.设Q(x): x是奇数,Z(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,z5、判断下列语句是不是命题。
若是,给出命题的真值。
( )北京是中华人民共和国的首都。
(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)PQ→⌝(2)QP⌝→(3)QP⌝↔(4)QP→⌝8、设个体域为整数集,则下列公式的意义是( )。
(1) ∀x∃y(x+y=0) (2) ∃y∀x(x+y=0)答:(1)对任一整数x存在整数 y满足x+y=0(2)存在整数y对任一整数x满足x+y=09、设全体域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)T10、设谓词P(x):x是奇数,Q(x):x是偶数,谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答:(1)11、命题“2是偶数或-3是负数”的否定是()。
离散数学练习题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的解为()A. M∩NB. M∪NC. MND. M-N正确:【B】23、设集合A={1,2,3},下列关系R中不是等价关系的是()A. R={<1,1>,<2,2>,<3,3>}B. R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}C. R={<1,1>,<2,2>,<3,3>,<1,2>}D.R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>} 正确:【C】24、设<A,?,*>是环,则下列说法不正确的是()A. <A,?>是交换群B. <A,*>是半群C. *对?是可分配的D. ?对*是可分配的正确:【D】25、平面图(如下)的三个面的次数分别是()A. 11,3,4B. 11,3,5C. 12,3,6D. 10,4,3正确:【A】26、下列命题正确的是()A. {l,2} {{1,2},{l,2,3},1}B. {1,2} {1,{l,2},{l,2,3},2}C. {1,2} {{1},{2},{1,2}}D. {1,2}∈{1,2,{2},{l,2,3}}正确:【B】27、设D的结点数大于1,D=<V,E>是强连通图,当且仅当()A. D中至少有一条通路B. D中至少有一条回路C. D中有通过每个结点至少一次的通路D. D中有通过每个结点至少一次的回路正确:【D】28、下列等价式正确的是()A. ┐┐AB.C. ┐┐AD.正确:【C】29、设P={x|(x+1)2≤4},Q={x|x2+16≥5x},则下列选项正确的是()A. PQB. PQC. QPD. Q=P正确:【C】30、设,则有()A. B.C. D.正确:【C】31、下列各图中既是欧拉图,又是汉密尔顿图的是()A. B.C. D.正确:【C】32、无向图G是欧拉图当且仅当G是连通的且()A. G中各顶点的度数均相等B. G中各顶点的度数之和为偶数C. G中各顶点的度数均为偶数D. G中各顶点的度数均为奇数正确:【C】33、下列式子正确的是()A. (A-B)-C = A-(B∪C)B. A-(B∪C)=(A-B)∪CC. ~(A-B)= ~(B-A)D.正确:【A】34、设有代数系统G=〈A,*〉,其中A是所有命题公式的集合,*为命题公式的合取运算,则G的幺元是()A. 矛盾式B. 重言式C. 可满足D. 公式p∧q正确:【B】35、设P:天下大雨,Q:他在室内运动,命题“除非天下大雨,否则他不在室内运动”可符合化为()A. ┐P∧QB. ┐P→QC. ┐P→┐QD. P→┐Q正确:【C】36、集合A={1,2,…,10}上的关系R={<x,y>|x+y=10,x∈A,y ∈A},则R的性质是()A. 自反的B. 对称的C. 传递的、对称的D. 反自反的、传递的正确:【B】37、设集合A={a,b, c}上的关系如下,具有传递性的是()A. R={<a,c>,<c,a>,<a,b>,<b,a>}B. R={<a,c>,<c,a>}C. R={<a,b>,<c,c>,<b,a>,<b,c>}D. R={<a,a>}正确:【D】38、下列等价式不正确的是()A. B.C. D.正确:【A】39、设M(x):x是人;F(x):x要吃饭。
离散数学习题集合论1.A={?,1},B={{a}}求A的幂集、A×B、A∪B、A+B。
2.A={1,2,3,4,5},R={(x,y)|x3.A={a,b,c},R={(a,a),(b,a)},求R-1,R2,R-I A,I A-R,r(R),s(R),t(R),st(R),ts(R)。
4.A={a,b,c},R= I A∪{(a,b),(b,a)},求a和b关于R的等价类。
5.R是A上的等价关系,A/R={{1,2},{3}},求A,R。
6.请分别判断以下结论是否一定成立,如果一定成立请证明,否则请举出反例。
①如果A∪B?C,则A?C或者B?C。
②如果A×B=A×C且A≠?,则B=C。
7.如果R是A上的等价关系,R2,r(R)是否一定是A上的等价关系?证明或举例。
8.已知A∩C?B∩C,A-C?B-C,证明:A?B。
9.证明:A X(B∩C)=(A X B)∩(A X C)10.证明:P(A)∪P(B)?P(A∪B)11.证明:R[sym] iff R=R-112.证明:r(R)=R∪I A,S(R)=R∪R-1,t(R)=R∪R2∪...13.证明:s(R∪S)=s(R)∪s(S)14.R是A上的关系,证明:如果R是对称的,则r(R)也是对称的。
15.I是整数集,R={(x,y)|x-y是3的倍数},证明:R是I上的等价关系。
16.如果R是A上的等价关系,则A/R一定是A的划分。
17.R是集合A上的自反关系,S是A上的自反和对称关系,证明t(R∪S)是A上的等价关系。
18.I是正整数集合,R是I×I上的二元关系,R={<,>|xv=yu},证明:R是等价关系。
19.f:A→B,R是B上的等价关系,令S={|x∈A且y∈A且∈R},证明:S是A上的等价关系。
20.R是集合A上的自反关系,S是A上的自反和对称关系,证明t(R∪S)是A上的等价关系。
页眉内容《离散数学》试题及答案一、选择或填空(数理逻辑部分)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,z5、判断下列语句是不是命题。
若是,给出命题的真值。
( )(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)PP⌝P→⌝↔(4)QQ→⌝(2)QP⌝→(3)Q8、设个体域为整数集,则下列公式的意义是( )。
(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)T10、设谓词P(x):x是奇数,Q(x):x是偶数,谓词公式∃x(P(x)∨Q(x))在哪个个体域中为真?( )(1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答:(1)11、命题“2是偶数或-3是负数”的否定是()。
离散数学练习题(含答案)题目1. 对于集合 $A={1,2,3,...,10}$ 和 $B={n|n是偶数,2<n<8}$,求 $A \cap B$ 的元素。
2. 存在三个可识别的状态A,B,C。
置换群 $S_3$ 作用在状态集上。
定义四个动作:$α: A → C, β: A → B, γ: C→ A, δ: B→ C$。
确定式子,描述 $\{α,β,γ,δ\}$ 的乘法表。
3. 证明 $\forall n \in \mathbb{N}$,合数的个数不小于$n$。
4. 给定一个无向带权图,图中每个节点编号分别是$1,2,...,n$,证明下列结论:a. 如果从节点$i$到$j$只有一条权值最小的路径,则这条路径的任意子路径都是最短路径。
b. 如果从节点$i$到$j$有两条或两条以上权值相等的路径,则从$i$到$j$的最短路径可能不唯一。
答案1. $A \cap B = \{2,4,6\}$。
2. 乘法表:3. 对于任意$n$,我们可以选择$n+1$个连续的自然数$k+1,k+2,...,k+n,k+n+1$中的$n$个数,其中$k \in \mathbb{Z}$。
这$n$个数构成的$n$个正整数均为合数,因为它们都至少有一个小于它自身的因子,所以不是质数。
所以合数的个数不小于任意$n$。
4.a. 根据题意,从$i$到$j$只有一条权值最小的路径,即这条最短路径已被确定。
如果从这条路径中任意取出一段子路径,假设这段子路径不是这个节点到$j$的最短路径,那么存在其他从$i$到$j$的路径比这段子路径更优,又因为这条路径是最短路径,所以这段子路径也一定不优于最短路径,矛盾。
所以从这条路径中任意取出的子路径都是最短路径。
b. 如果从节点$i$到$j$有多条权值相等的路径,则这些路径权值都是最短路径的权值。
因为所有最短路径的权值相等,所以这些路径的权值就是最短路径的权值。
所以从$i$到$j$的最短路径可能不唯一。
离散数学-习题集《离散数学》习题集第⼀部分判断题⼀、第⼀章—集合1、()已知集合A的元素个数为10,则集合A的幂集的基=102。
2、()已知两个集合A、B,若A中的元素都是B中的元素,则记为A∈B。
2、()已知集合A的元素个数为n,则集合A的幂集P(A)的元素个数为n2。
3、( ) 已知两个集合A={Ф,{Ф}},B={Ф},则A∩B={Ф}。
4、()已知两个集合A={Ф,{Ф}},B={Ф},则A∩B=Ф。
5、()已知两个集合A、B,若A中的元素都是B中的元素,则记为A∈B。
6、()已知集合A的元素个数为n,则集合A的幂集P(A)的元素个数为n2。
7、()已知集合A的元素个数为n,则A×A的幂集的元素个数为n2。
8、()已知两个集合A、B,则A-B是由属于B但不属于A的元素构成的集合。
⼆、第⼆章—⼆元关系1、()若R是A上的⼆元关系,I A是A上的恒等关系,则当且仅当I A∈R时,R是A上的⾃反关系。
2、(√)若R是集合A上的⼆元关系,且当(a,b)∈R且(a,c)∈R时,就有(b,c)∈R,则R是A 上的可传递关系。
3、()设A是集合,A1、A2、...A n都是A的⾮空⼦集,令S={A1,A2,...,A n},则如果S是集合A的⼀个划分,那么S⼀定是集合A的⼀个完全覆盖;反之亦然。
5、()R是⾮空集合A上的等价⼆元关系,则A关于R的商集A/R是集合A的⼀个划分,但不是A的⼀个完全覆盖。
6、()已知集合A有4元素,易知集合A共有24个互不相同的⼦集合,所以在集合A上⼀共可定义24个互不相同的⼆元关系。
7、()若R1和R2都是集合A上的可传递⼆元关系,则R1∪R2也是A上的传递关系。
8、()设R是有限的⾮空集合A上的偏序关系,则A必有极⼤(⼩)元和最⼤(⼩)元。
9、()若R1和R2都是集合A上的相容关系,则R1∩R2也是A上的相容关系。
10、()若R1和R2都是集合A的可传递⼆元关系,则R1∩R2也是A上的传递关系。
第二部分:.集合1.若集合A 上的关系R 是对称的,则1R -也是对称的。
( )2.数集合上的不等关系()≠可确定A 的一个划分。
( )3.设A ,B ,C 为任意集合,若A B A C ⨯=⨯,则 B C =。
( )4.函数的复合运算“。
”满足结合律。
( )5.A ,B ,C 为任意集合,若 A B A C ⋃=⋃ 则B C =。
( )6.设R 是实数集,R 上的关系R (){},2,,x y x y x y R =-<∈,则R 是相容关系。
() 7.设,A ≤是偏序集,B A ⊆,则B 的极大元b B ∈且唯一。
( )8.设{}1,2A =,{}B a =,则()222A B A B ⋃⋃=。
(注 其中 2A 为()A ϕ) ( )9.设 {}0,1A =,{}1,2B =, 则{}20,1,1,0,1,2,1,0,1,1,0,2A B ⨯=。
( )10.集合A 上的恒等关系是一个双射函数。
( )11.设A ,B 为任意集合,不能A B ⊂ 且A B ∈。
( )12.设R 是集合A 上的关系,若12,R R 是对称的, 则 12R R 也是对称的。
( )1. 设A ={}∅,B =(())P P A ,下列各式中哪个是错的 ( )A. B ∅⊆B. {}B ∅⊆C. {{}}B ∅∈D. {,{}}()P A ∅∅⊆2. 设Z 为整数集,下面哪个序偶不构成偏序集 ( )A. Z,<〈〉 (<:小于关系)B. Z,〈≤〉 (≤:小于等于)C. Z,=〈〉 (=:等于关系)D. Z,|〈〉 (|:整除关系)3. 设集合{}4,3,2,1=A ,A 上的二元关系{},4,3,4,2,3,2,1,1=R则R 具有 ( )A.自反性B.对称性C.传递性D. 以上答案都不对4. 设{}d c b a A ,,,=,下面哪一个是A 的划分 ( )A.{}{}{}d c b a ,,,,ΦB. {}{}d c b a ,,,C. {}{}{}{}d a c b a ,,,,D. {}{}{}c b a ,,5. 设A =∅,B={∅,{∅}},则B A -是 ( )A. {{∅}}B. {∅}C. {∅,{∅}}D. ∅6. 下图描述的偏序集中,子集{b,e,f}的上界为 ( )A. b,cB. a,bC. bD. a,b,c7. 设集合{}{}ΦΦ=,A , 则A 的幂集为: ( )A. {}{}ΦΦ, B. {}{}{}{}{}{}ΦΦΦΦΦ,,,, C. {}{}{}{}ΦΦΦ,, D. {}{}{}{}{}{}{}ΦΦΦΦΦ,,,, 8. 若Q P Q P ⋃=⋂, 则P, Q 要满足的条件为 ( )A. Q P ⊆B. P Q ⊆C. Q 为空集D. P=Q``````````````````````````````9. 在0 ∅之间应填入的符号为 ( )A. =B. ⊂C. ∈D. ∉10. 设,A 〈≤〉是偏序集,B A ⊆,下面结论正确的是 ( )A. B 的极大元b B ∈且唯一B. B 的极大元b A ∈且不唯一C. B 的上界b B ∈且不唯一D. B 的上确界b A ∈且唯一11. 集合{}4,3,2,1=I , I 上的关系 R={4,43,44,1,3,3,3,2,23,1,1,1,则R 是 ( )A. 反对称的B. 传递的C.反自反的D. 自反的12. 设S A B ⊆⨯,下列各式中哪个是正确的 ( )A. domS B ⊆B. domS A ⊆C. ranS A ⊆D. domS ranS S ⋃=13. 设A ={1,2,3,4,5},下面哪个集合等于A ( )A. {1,2,3,4,5,6}B. {x |x 是整数且225x ≤}C. {x |x 是正整数且5x ≤}D. {x |x 是正有理数且5x ≤}14. 设A ={{1,2,3},{4,5},{6,7,8}},下列各式中哪个是错的 ( )A. A ∅⊆B. {6,7,8}A ∈C. {{4,5}}A ⊂D. {1,2,3}A ⊂15. 设集合X ≠∅,则空关系X ∅不具备的性质是 ( )A. 自反性B. 反自反性C. 对称性D. 传递性``````````````````````````````````````````````16. 集合A 的一个划分,确定A 的元素间的关系为 ( )A. 全序关系B. 等价关系C. 偏序关系D. 拟序关系17. 设{}d c b a A ,,,=,下面哪一个是A 的划分 ( )(A) {}{}{}d c b a ,,,,Φ (B){}{}d c b a ,,, (C) {}{}{}{}d a c b a ,,,, (D) {}{}{}c b a ,,18. 设集合A ={0, b }, B ={1, b , 3}, 则A ⋃B 上的恒等关系是 ( )(A) {<0, 0>, <1, 1>, <3, 3>} (B){<0, 0>, <1, 1>, <b , b >,<3, 3>}(C) {<1, 1>, <b , b >, <3, 3>} (D) {<0, 1>,<1, b > , <b , 3>, <3, 0>}19. 设A ={1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B ⋂C )= ( )(A) {<1,c >,<2,c >} (B) {<c ,1>,<2,c >}(C) {<c ,1><c ,2>,} (D) {<1,c >,<c ,2>}20. 设A , B , C 都是集合,如果A ⋂C =B ⋂C ,则有 ( )(A) A =B (B) A ≠B(C) 当A -C =B -C 时,有A =B (D) 当C =E 时, 有A ≠B21. 设集合A ={∅,a },则幂集P (A )= ( )(A){,{},{,}}a a ∅∅ (B){{},{},{,}}a a ∅∅(C){,{},{},{,{}}},}a a A ∅∅∅ (D){,{},{},{,}}a a ∅∅∅22. 集合A 上的等价关系R ,决定了A 的一个划分,该划分就是 ( )A. 并集A RB. 交集A RC. 差集A R -D. 商集/A R23. 设1R 和2R 是集合A 上的任意关系,则下列命题为真的是 ( )A. 若1R 和2R 是自反的,则12R R 也是自反的B. 若1R 和2R 是反自反的,则12R R 也是反自反的C. 若1R 和2R 是对称的,则12R R 也是对称的D. 若1R 和2R 是传递的,则12R R 真也是传递的24. 设A ={1,2},B ={a ,b ,c },C ={c ,d }, 则A ×(B ⋂C )= ( )(A) {<1,c >,<2,c >} (B) {<c ,1>,<2,c >}(C) {<c ,1><c ,2>,} (D) {<1,c >,<c ,2>}25. 设A , B , C 都是集合,如果A ⋂C =B ⋂C ,则有 ( )(A) A =B (B) A ≠B(C) 当A -C =B -C 时,有A =B (D) 当C =E 时, 有A ≠B26. 设集合A ={∅,a },则幂集P (A )= ( )(A){,{},{,}}a a ∅∅ (B){{},{},{,}}a a ∅∅(C){,{},{},{,{}}},}a a A ∅∅∅ (D){,{},{},{,}}a a ∅∅∅27. 集合A 上的关系R 是相容关系的必要条件是 ( )A. 自反的,反对称的B. 反自反的,对称的C. 传递的,自反的D. 自反的,对称的28. 集合{1,2,,10}A = 上的关系R={x,y |x+y=10 x,y }A ∈且则R 的性质为 ( )A. 自反的B. 对称的C. 传递的,对称的D. 反自反的,传递的29. 下面关于集合的表示中,正确的是 ( )A. 0φ=B. {}φφ∈C. φφ∈D. {,}a b φ∈30. 设{}c b a A ,,=,{}2,1=B ,则从A 到B 的所有函数集合中有 个函数。
一、填空题1、集合的表示方法有两种: 法和 法。
请把“奇整数集合”表示出来{ }。
1、列举;描述;}12|{Z k k x x ∈+=,2、无向连通图G 含有欧拉回路的充分必要条件是不含有奇数度结点.2*、连通有向图D 含有欧拉回路的充分必要条件是D 中每个结点的入度=出度. 3、设R 是集合A 上的等价关系,则R 所具有的关系的三个特性是 、自反性、对称性、传递性.4、有限图G 是树的一个等价定义是:连通无回路(或任一等价定义).5、设N (x ):x 是自然数,Z (y );y 是整数,则命题“自然数都是整数,而有的整数不是自然数”符号化为∀x (N (x )→Z (x ))∧∃x (Z (x )∧⌝N (x ))6、在有向图的邻接矩阵中,第i 行元素之和,第j 列元素之和分别为 、结点v i 的出度和结点v j 的入度. 7、设A ,B 为任意命题公式,C 为重言式,若C B C A ∧⇔∧,那么命题B A ↔是重言式的真值是 1 .8、命题公式)(Q P →⌝的主析取范式为P ∧⌝Q .9、 设图G =<V ,E >和G '=<V ',E '>,若 ,则G '是G 的真子图,若V '=V ,E '⊆E ,则G '是G 的生成子图. E E V V E E V V ⊆'='⊂'⊂',;或 10、在平面图>=<E V G ,中,则∑=ri ir 1)deg(=2∣E ∣,其中r i(i =1,2,…,r )是G 的面.11、设}2,1{},,{==B b a A ,则从A 到B 的所有映射是11、σ1={(a ,1),(b ,1)};σ2={(a ,2),(b ,2)};σ3={(a ,1),(b ,2)};σ4={(a ,2),(b ,1)}12、表达式∀x ∃yL (x ,y )中谓词的定义域是{a ,b ,c },将其中的量词消除,写成与之等价的命题公式为 12、(L (a ,a )∨L (a ,b )∨L (a ,c ))∧(L (b ,a )∨L (b ,b )∨L (b ,c ))∧(L (c ,a )∨L (c ,b )∨L (c ,c )) 12*、设个体域D ={a ,b },公式)),()((y x yH x G x ∃→∀消去量词化为 (G (a )→(H (a ,a )∨H (a ,b )))∧ (G (b )→(H (b ,a )∨H (b ,b )))13、含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式是 14、设R ,S 都是集合A 上的等价关系,则对称闭包s (R ⋂S )= R ⋂S15、设G 是连通平面图,v ,e ,r 分别表示G 的结点数,边数和面数,则v ,e 和r 满足的关系式是2=-+e r v16、设G 是n 个结点的简单图,若G 中每对结点的度数之和≥n ,则G 一定是哈密顿图. 17、一个有向树T 称为根树,若 ,其中 ,称为树根,称为树叶. 若有向图T 恰有一个结点的入度为0,其余结点入度为1;入度为0的结点;出度为0的结点.18、图的通路中边的数目称为 . 结点不重复的通路是 通路. 边不重复的通路是 通路. 通路长度;初级;简单. 19、设A 和B 为有限集,|A|=m ,|B|=n ,则有 个从A 到B 的关系,有 个从A 到B 的函数,其中当m ≤n 时有 个入射,当m=n 时,有 个双射。
1. (单选题) 一棵无向树的顶点数n与边数m关系是。
( B)(本题2.0分)A、n =mB、m=n-1C、n =m -1D、不能确定2. (单选题) 设G是有n个结点m条边的连通平面图,且有k个面,则k等于。
( A)(本题2.0分)A、m-n+2B、n-m-2C、n+m-2D、m+n+2。
3. (单选题) 有n个结点的树,其结点度数之和是(A )。
(本题2.0分)A、2n-2B、n-2C、n-1D、2n。
4. (单选题) A={a,b},B={c},则A B=(D )。
(本题2.0分)A、{a}B、{b}C、{a,c}D、{a,b,c}。
5. (单选题) 设A={a, b},则P (A)= (D )。
(本题2.0分)A、{a}B、{{a},{b}}C、{{a},{b},{a,b}}D、{,{a},{b},{a,b}6. (单选题) 公式yP(y)∧x(R(x)→Q(x))中,y约束出现了次(B )。
(本题2.0分)B、 1.0C、 2.0D、3。
7. (单选题) 设A={a},B={0,1},求A×B=(A )。
(本题2.0分)A、{<a,0 style="box-sizing: border-box;">,<a,1 style="box-sizing:border-box;">}B、{<a,0 style="box-sizing: border-box;">}C、{,<a,1 style="box-sizing: border-box;">}D、{<0,a >,<1,a >}8. (单选题) 下图中结点V3的出度是(B )。
(本题2.0分)B、 1.0C、 2.0D、 3.09. (单选题) 下面给出的集合中,哪一个不是前缀码( C)。
第一篇 绪论内容:(三句话)典型题例:1、离散数学是计算机科学所涉及的 和 的总称。
2、离散数学是数学中的一个分支,它以 作为其主要研究对象,非常重视 问题的研究。
3、要解决一个问题,首先要证明此问题解的 ,还需要找出得到此问题的步骤来,而且其步骤必须是 ,有规则的,这就是所谓“能行性”问题的研究。
第二篇 集合论内容:典型题例:1、设集合{}{}2,4,3,a B =,那么下列命题中正确的是 。
A 、B a ∈ B 、{}{}B a ⊆4,3,,2C 、{}B a ⊆D 、{}B ⊆φ2、设A ,B 是集合,如果{}}}2,1{,1{,1==B A ,则 。
A 、B A B A ⊆∈且 B 、B A B A ⊄∈但C 、B A B A ⊆∉且D 、B A B A ⊄∉且3、设集合{}{}4,3,,2a A =,那么下列命题中错误的是___。
A 、{}A a ∈ B 、{}{}A a ⊆3,4, C 、{}A a ⊆ D 、A ⊆φ 4、设集合{}Zx x x A ∈<=,3,{}Z k k x x B ∈==,2,{}5,4,3,2,1=C ,则=-+)(B C A 。
A 、{}5,3,1 B 、{}6,4,2 C 、{}8,7,6,0 D 、{}8,7,6,4,2,05、设{}4,3,2,1=A ,{}9,6,4,2=B ,那么集合A ,B 的对称差A+B= 。
A 、{}3,1 B 、{}6,4,2 C 、{}9,6,3,1 D 、{}9,6,4,3,2,1 6、集合{}e d c b a X ,,,,=,X 上的一个划分{}}}{,{},,{e d c b a =π,那么π所对应的等价关系R 应有有 个序偶。
A 、8B 、9C 、10D 、13 7、设集合{}3,2,1=B 上的二元关系{})3,3(),1,1(=R ,则R 不具有___。
A 、传递性B 、自反性C 、对称性D 、反对称性8、设集合{}4,3,2,1=X ,X 上的关系{})4,3(),4,2(),3.2(),1,1(=R ,则R 具有 。
数理逻辑习题判断题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)→qC.q∧┐q D.p→┐q4.下列语句中不是..命题的只有(A )A.花儿为什么这样红?B.2+2=0C.飞碟来自地球外的星球。
可编辑修改精选全文完整版离散数学习题答案习题一:P121.判断下列句子哪些是命题?在是命题的句子中,哪些是简单命题?哪些是真命题?哪些命题的真值现在还不知道?(1)中国有四大发明。
(2)5是无理数。
(3)3是素数或4是素数。
(4)x2+3<5,其中x是任意实数。
(5)你去图书馆吗?(6)2与3都是偶数。
(7)刘红与魏新是同学。
(8)这朵玫瑰花多美丽呀!(9)吸烟请到吸烟室去!(10)圆的面积等于半径的平方乘π。
(11)只有6是偶数,3才能是2的倍数。
(12)8是偶数的充分必要条件是8能被3整除。
(13)2025年元旦下大雪。
1、2、3、6、7、10、11、12、13是命题。
在上面的命题中,1、2、7、10、13是简单命题;1、2、10是真命题;7的真值现在还不知道。
2.将上题中是简单命题的命题符号化。
(1)p:中国有四大发明。
(2)q:5是无理数。
(7)r:刘红与魏新是同学。
(10)s:圆的面积等于半径的平方乘π。
(1)t:2025年元旦下大雪。
3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值。
“5是有理数”的否定式是“5不是有理数”。
解:原命题可符号化为:p:5是有理数。
其否定式为:非p。
非p的真值为1。
4.将下列命题符号化,并指出真值。
(1)2与5都是素数。
(2)不但π是无理数,而且自然对数的底e也是无理数。
(3)虽然2是最小的素数,但2不是最小的自然数。
(4)3是偶素数。
(5)4既不是素数,也不是偶数。
a:2是素数。
b:5是素数。
c:π是无理数。
d:e是无理数。
f:2是最小的素数。
g:2是最小的自然数。
h:3是偶数。
i:3是素数。
j:4是素数。
k:4是偶数。
解:(1)到(5)的符号化形式分别为a∧b,c∧d,f∧非g,h∧i,非j∧非k。
这五个复合命题的真值分别为1,1,1,0,0。
5.将下列命题符号化,并指出真值。
a:2是偶数。
b:3是偶数。
c:4是偶数。
习 题 一一、 将下列命题符号化:1、蓝色和黄色可以调配成绿色。
2、蓝色和黄色都是常用的颜色。
3、52和之和是无理数。
4、52和都是有理数。
5、小丽一边吃苹果,一边看电视。
6、王大力不仅是百米冠军,而且是500米冠军。
7、李冰只能选学英语或只能选学法语。
8、种瓜得瓜,种豆得豆。
9、经一事,长一智,并且不经一事,不长一智。
10、 经一事,长一智,并且不长一智,不经一事。
11、 李和平是山西人或陕西人。
12、 王小红虽然没上过大学,但她自学成才。
二、 求复合命题的真值:设p :4是素数,q :南京在北京的北边,r :苹果树是落叶乔木。
1、()r q p ⌝∧∧⌝2、()()r p q p ↔→∧⌝3、()()q p q p ⌝↔⌝∨↔三、求下列公式的成真赋值和成假赋值:1、()r q p ⌝∧∧⌝2、()()r p q p ↔→∧⌝3、()()q p q p ∧⌝∨⌝∧四、判断公式的类型:1、()p q r p →⌝∧∧2、()()()r p q q p ∨⌝→⌝→→3、()()r p q p →↔→4、()()()()()r q p q p q p ∨∧⌝∨⌝∧→↔⌝5、()()r q r p ↔→⌝↔6、()()()q r p q p ∧∧→⌝∧五、将下列复合命题符号化,并求真值:1、若π是无理数,自然对数的底e 也是无理数。
只有3是偶数,4才是素数。
2是无理数,仅当5不是无理数。
5是无理数。
2、若2和3都是素数,则5是奇数。
2是素数,3也是素数,所以5或6是奇数。
3、设x y 2=,x 为实数。
推理如下:若y 在x=0可导,则y 在x=0连续。
y 在x=0连续,所以y 在x=0可导。
六、用等值演算法证明:1、()1⇔∨⌝∨→r q p p2、()()()()1⇔∧⌝∨⌝∧↔↔⌝q p q p q p3、()()0⇔→⌝∧∨⌝q p q p4、()()()q p q p q p ↔⌝⇔∧⌝∧∨5、()()r q p r p q →∧⇔→→6、()()()()()()r p q r q p r q p q p ∧⌝∨∧∧∨⇔∧∧⌝∨∧七、求主析取范式和主合取范式,成真赋值和成假赋值:()()()()()()()()()()()()()()()()()q p p q q p q p p q q p r q p r q p q r q p r p q r q p ↔→↔→∧∨⌝→⌝∨→⌝⌝⌝∧⌝∨∧∧→→⌝∧∨⌝∧⌝∨∧∧∨、、、、、、654321 八、将已知的命题公式等值地化成给定的联结词完备集中的公式: (){}()}{()}{()}{}{(){}中的公式。
第一章习题1.1判断下列语句是否为命题,若是命题请指出是简单命题还是复合命题。
(1)2是无理数。
(2)5能被2整除。
(3)现在开会吗?(4)x+5>0(5)这朵花真是好看!(6)2是素数当且仅当三角形有三条边。
(7)雪是黑色的当且仅当太阳是从东方升起。
(8)2000年10月1日天气晴好。
(9)太阳系以外的星球上有生物。
(10)小李在宿舍里。
(11)全体起立。
(12)4是2的倍数或是3的倍数。
(13)4是偶数且是奇数。
(14)李明和王华是同学。
(15)蓝色和黄色可以调配成绿色。
1..2 将上题中的命题符号化,并讨论他们的真值。
1.3判断下列各命题的真值。
(1)若2+2=4,则3+3=6;(2)若2+2=4,则3+3≠6;(3)若2+2≠=4,则3+3=6;(4)若2+2≠=4,则3+3≠=6;(5)2+2=4,当且仅当3+3=6;(6)2+2=4,当且仅当3+3≠6;(7)2+2≠4,当且仅当3+3=6;(8)2+2≠4,当且仅当3+3≠6;1.4将下列命题符号化,并讨论其真值。
(1)如果今天是1号,则明天是2号;(2)如果今天是1号,则明天是3号;1.5将下列命题符号化。
(1)2是偶数不是素数;(2)小王不但聪明而且用功;(3)虽然天气冷。
老王还是来了;(4)他一边吃饭,一边看电视;(5)如果天下大雨,他就乘公交汽车来;(6)只有天下大雨,他才乘公交汽车来;(7)除非天下大雨,否则他不乘公交汽车来;(8)不经一事,不长一智;1.5设p,q的真值为0 ,r,s的真值为1,求下列命题公式的真值。
(1)p∨(q∧r);(2)(p↔r)∧(⌝p∨s);(3)(p∧(q∨r)→((p∨q)∧(r∧s);(4)⌝(p∨(q→r∧⌝p)))→(r∨⌝s);设p:2+3=5。
q:大熊猫产在中国。
r:复旦大学在广州。
求下列复合命题的真值:(1)(p q)→r(2)(r→(p∧q))┐p (3)┐r→(┐p∨┐q∨r)(4)(p∧q∧┐r)((┐p∨┐q)→r).用真值表判断下列公式的类型:方法不限。
(1)p→(p∨q∨r)(2)(p→┐q)→┐q(3)┐(q→r)∧r(4)(p→q)→(┐q→┐p)(5)(p∧r)(┐p∧┐q)(6)((p→q)∧(q→r))→(p→r)(7)(p→q)(rs)1.8用等值演算法证明下列等值式。
(1)(p∧q)∧(p∧⌝q)⇔p;(2)((p→q)∧(p→r))⇔(p→(q∧r));(3)⌝(p↔q)⇔(q∨p)∧⌝(p∧q))1.9设 A,B,C 为任意的命题公式。
(1)已知A∨C⇔B∨C,问A⇔B吗?(2)已知A∧C⇔B∧C,问A⇔B吗?(3)已知⌝A⇔⌝B, 问A⇔B吗?求下列命题公式的主析取范式,主合取范式,成真赋值,成假赋值。
1(()();2()();3();p q v p q r p q q p p q q r ∨∧→∧∧⌝→→⌝∨⌝→∧∧()()()通过求主析取范式判断下列各组命题公式是不是等值。
();2();2;2;p q r q p r p q p q →→→→↑↓(1)1,,()1,,有一探测队有3名队员,有一天取得一块矿样,3人的判断如下:甲说:这不是铁,也不是铜;已说:这不是铁,是锡;丙说:这不是锡,是铁;经实验鉴定后发现,其中一人两个判断是正确的,一个人判断对一半,一个人的判断全错了,根据以上的情况判断矿样的种类。
判断下列的推理是不是正确,先将命题符号化,在写出前提和结论,然后在进行判断。
(1)如果今天是1号,则明天是5号,今天是1号,所以明天是5号。
(1)如果今天是1号,则明天是5号,明天是5号,所以今天是1号。
(1)如果今天是1号,则明天是5号,明天不是5号,所以今天不是1号。
(1)如果今天是1号,则明天是5号,今天不是1号,所以明天不是5号。
构造下面的推理的证明。
(),,..(2)34p p q q r r p ⌝∧⌝⌝∨⌝⌝→→∨⌝→→→∧→↔↔∧∧∧∧(1)前提:结论:前提:p (q s),q,p r;结论:r s.()前提:p q.结论:p (p q)()前提:q p,q s,s t,t r.结论:p q r s.如果他是理科学生,他必学好数学,如果他不是文科学生,他必是理科学生,他没有学好数学,所以他不是文科学生。
判断上面的推理是不是正确,并且证明你的结论。
给定命题公式如下;上述公式的成真赋值A ,成假赋值为B ,公式的类型为C 。
供选择的答案:① 无 ② 全体赋值 ③ 010,100,101,111 ④010,100,101,110,111 B: ① 无 ② 全体赋值 ③000,001,011, ④000,010,110C: ①重言式 ②矛盾式 ③ 可满足式给定命题公式如下;上述公式的主析取范式中含的极小项的个数为A ,主合取范式含的极大项的个数为B ,成真值的赋值为C供选择的答案A ① 2 ② 3 ③ 5 ④ 0 ⑤ 8B ① 0 ② 8 ③ 5 ④ 3C ① 000,001,110; ②001,011,101,110,111; ③全体赋值 ④ 无给定下列三组前提。
(),,(2)(),,(3),,p q q r rp q r r s sp q q r r s ⌝∧⌝⌝∨⌝∧→⌝∨⌝⌝∨⌝∨→(1)上述前提中,(1)的逻辑结论(有效结论)为A ,(2)的逻辑结论为B ,(3)的逻辑结论C 。
供选择的答案A,B,C:① r ② q ③p ⌝ ④ s ⑤p q ⌝∨⌝ ⑥p s → ⑦p q ∧设计一个符合下列要求的室类照明控制的线路,在房间的门外、门类及其床头分别装一个可以控制同一个电灯F 的3个开关A,B,C, 当且仅当一个开关的搬键向上或3 个开关的搬键都向上时候电灯亮,则F 的逻辑关系式可以化简为A 供选择的答案A:① A B C ∨∨ ②()A B C A B C ∨∨∨∧∧.某电路中有一个灯泡和三个开关A,B,C 。
已知在且仅在下述四种情况下灯亮:(1)C 的扳键向上,A,B 的扳键向下。
(2)A 的扳键向上,B,C 的扳键向下。
(3)B,C 的扳键向上,A 的扳键向下。
(4)A,B 的扳键向上,C 的扳键向下。
设F 为1表示灯亮,p,q,r 分别表示A,B,C 的扳键向上。
(a )求F 的主析取范式。
(b )在联结词完备集{┐,∧}上构造F.(c )在联结词完备集{┐,→,}上构造F. .一个排队线路,输入为A,B,C ,其输出分别为F A ,F B ,F C 。
本线路中,在同一时间内只能有一个信号通过,若同时有两个和两个以上信号申请输出时,则按A,B,C 的顺序输出。
写出F A ,F B ,F C 在联结词完备集{┐,∨}中的表达式。
第二章习题在一阶逻辑中将下列命题符号化.(1)鸟都会飞翔.(2)并不是所有人都爱吃糖.(3)有人爱看小说.(4)没有不爱看电影的人.在一阶逻辑中将下列命题符号化,并指出个命题的真值.个体域分别为 (a )自然数集合N (N 中含O ).(b )整数集合Z.(c )实数集合R.(1)对于任意的x ,均由()22121x x x +=++(2 )存在x ,使得x+2=0.(3 ) 存在x ,使得5x=1.在一阶逻辑中将下列命题符号化.(1)每个大学生不是文科生就是理科生.(2)有些人喜欢所有的花.(3)没有不犯错误的人.(4)在北京工作的人未必就是北京人.(5)任何金属都可以溶解在某种液体中.(6)凡对顶角都相等. 在一阶逻辑中将下面命题符号化,并分别讨论个体域限制为(a),(b)时命题的真值:(1)对于任意的x ,均有x 2-2=(x+)(x-)。
(2)存在x ,使得x+5=9。
其中(a)个体域为自然数集合,(b)个体域为实数集合。
将下列各式翻译成自然语言,然后再不同领域中却定它们的真值.(1)(.0)(2)(.0)(3)(.1)(4)(.1)(5)(.)(6)(.)(7)()x y x y x y x y x y x y x y x y x y x y x x y x y x x y z x y z ∀∃=∃∀=∀∃=∃∀=∀∃=∃∀=∀∀∃-=个体域分别为(a )实数集合(b)整数集合(c)正整数集合(d)(非0 实数集合)设个体域D={a,b,c},消去下列各式的量词:(1)xy(F(x)∧G(y))(2)xy(F(x)∨G(y)) (3)xF(x)→yG(y) (4)x(F(x,y)→yG(y)).设个体域D={1,2},请给出两种不同的解释I1和I2,使得下面公式在I1下都是真命题,而在I2下都是假命题。
(1) x(F(x)→G(x))(2) x(F(x)∧G(x).给定解释I如下:(a) 个体域D={3,4}。
(b) (x)为(3)=4,(4)=3。
(c) (x,y)为(3,3)=(4,4)=0,(3,4)=(4,3)=1。
试求下列公式在I下的真值:(1)xyF(x,y) (2)xyF(x,y) (3)xy(F(x,y)→F(f(x),f(y)).在自然推理系统F中构造下面推理的证明:(1) 前提:x(F(x)→(G(a)∧R(x))),xF(x)结论:x(F(x)∧R(x))(2) 前提:x(F(x)∨G(x)),┐xG(x)结论:xF(x)(3) 前提:x(F(x)∨G(x)),x(┐G(x)∨┐R(x)),xR(x)结论:xF(x).在自然推理系统F 中,证明下面推理:(1) 每个有理数都是实数,有的有理数是整数,因此有的实数是整数。
(2) 有理数、无理数都是实数,虚数不是实数,因此虚数既不是有理数、也不是无理数。
(3) 不存在能表示成分数的无理数,有理数都能表示成分数,因此有理数都不是无理数。
(1) 试给出解释,使得(()())(()())x F x G x x F x G x ∀→∀∧与在下具有不同的真值(2)试给出解释,使得(()())(()())x F x G x x F x G x ∃∧∃→与在下具有不同的真值给出解释,使下面的两个公式在解释下面为假,从而说明这两个公式都不是逻辑有效式(用真式)(1)(()())(()())(2)(()())(()())x F x G x xF x xG x xF x xG x x F x G x ∀∨→∀∨∀∃∧∃→∃∧ 设个体域,在D={a,b,c }下D 验证量词否定等值式(1)()()(2)()()xA x x A x xA x x A x ⌝∀⇔∃⌝⌝∃⇔∀⌝ 2.14在一阶逻辑中将下面的命符号化,并且要求只能使用全称量词(1)没有人长绿色的头发(2)有的北京人没有去过香山设个体域,在D={a,b,c },消去下列公式中的量词。
∀→∃∀∧∃∃∀(1)xF(x)yG(y)(2)x(F(x)yG(y))(3)y xH(x,y)求下列各式的前束范式,要求使用自由变换换名规则。