(A)P是真命题(B)P是假命题
(C)P是一阶逻辑公式,但不是命题(D)P不是一阶逻辑公式
ü对一阶逻辑公式的说法正确的是(B).
(A)x是约束的,y是约束的,z是自由的;
(B)x是约束的,y既是约束的又是自由的,z是自由的;
(C)x是约束的,y既是约束的又是自由的,z是约束的;
(D)x是约束的,y是约束的,z是约束的;
ün个命题变元可产生(D)个互不等价的布尔小项。
(A)n(B)n2(C)2n(D)2n
ü命题“没有不犯错误的人”符号化为(D)。
设是人,犯错误。
(A)(B)
(C)(D)
ü下列命题公式等值的是(C)
ü给定命题公式:
,则所有可能使它成真赋值为(B),成假赋值为(C)。
(A)111,011;000(B)111,011,100,101,110;
(C)000,010,001;(D)000,110,011,001,100。
ü给定前提:
,则它的有效结论为:
(B)。
(A)S;(B);(C)P;(D)。
ü命题:
“所有的马都比某些牛跑得快”的符号化公式为:
(C)。
假设:
:
x是马;:
x是牛;:
x比y跑得快。
(A);(B);
(C);(D)。
ü设P:
a是偶数,Q:
b是偶数.R:
a+b是偶数,则命题“若a是偶数,b是偶数,则a+b也是偶数”符号化为(C).
(A)PQR(B)PQR(C)PQR(D)PQR
ü表达式中的辖域是(B).
(A)P(x,y)(B)P(x,y)ÚQ(z)(C)R(x,y)(D)P(x,y)ÙR(x,y)
ü判断一个语句是否为命题,首先要看它是否为陈述句,然后再看它是否有唯一的真值。
ü命题公式(P∨Q)→R的只含联结词和∧的等值式为:
。
ü为假言推理规则。
ü在一阶逻辑中符号化命题“有会说话的机器人。
”设M(x):
x是机器人;S(x):
x是会说话的;上述句子可符号化为:
(x)(M(x)∧S(x))。
ü设p:
我们爬山,q:
我们划船,在命题逻辑中,命题“我们不能既爬山又划船”的符号化形式为(p∧q).
ü设p:
小王走路,q:
小王唱歌,在命题逻辑中,命题“小王边走路边唱歌”的符号化形式为(p∧q).
ü量词否定等值式。
ü设F(x):
x是人,H(x,y):
x与y一样高,在一阶逻辑中,命题“人都不一样高”的符号化形式为.
ü若含有n个命题变项的公式A是矛盾式,则A的主合取范式含2n个极小项。
ü取个体域为全体整数的集合,给出下列各公式:
(1)
(2)(3)
其中公式
(1)的真值为真,公式(3)的真值为假。
ü若含有n个命题变项的公式A是重言式,则A的主合取范式为1或T。
ü命题公式的所有成假赋值为000,001,010。
ü谓词公式的前束范式为。
ü在一阶逻辑中,将命题“没有不能表示成分数的有理数”符号化为
ü或(设:
x是有理数;:
x能表示成分数。
)
ü设个体域D={1,2},那么谓词公式消去量词后的等值式为A
(1)ÚA
(2)Ú(B
(1)ÙB
(2)).
ü设P,Q是两个命题,当且仅当P,Q的真值均为1时,的值为1。
(×)
ü谓词公式A是的代换实例,则A是重言式。
(×)
ü重言式的主析取范式包含了该公式的所有的极小项。
(√)
ü命题公式A→(B→C)与(A∧B)→C等价。
(√)
ü设A,B,C为命题公式,若,则。
(√)
ü在一阶谓词公式中,同一变元符号不能够既约束出现又自由出现。
(×)
ü在一阶逻辑中,公式的前束范式是唯一的。
(×)
计算
ü求命题公式(((p∨q)∧p)→q)∧r的主析取范式。
答案:
m1∨m3∨m5∨m7
ü用等值演算法求公式的主析取范式,并由主析取范式求主合取范式。
解:
主析取范式:
主合取范式为:
ü求公式(P∧Q)∨(﹁P∧R)的主析取范式,并由主析取范式求主合取范式。
解:
(P∧Q)∨(﹁P∧R)的真值表如下:
PQR
P∧Q﹁P∧R(P∧Q)∨(﹁P∧R)
000
001
010
011
100
101
110
111
000
011
000
011
000
000
101
101
故主析取范式为:
(﹁P∧﹁Q∧R)∨(﹁P∧Q∧R)∨(P∧Q∧﹁R)∨(P∧Q∧R)
主合取范式为:
(P∨R∨Q)∧(﹁Q∨P∨R)∧(﹁P∨Q∨R)∧(﹁P∨Q∨﹁R)
ü化公式为前束范式。
解:
原式
(或)
证明
ü构造下面推理的证明:
任何自然数都是整数;存在着自然数。
所以存在着整数。
个体域为实数集合R。
证明:
先将原子命题符号化:
设:
为自然数,:
为整数。
则
前提:
,
结论:
①前提引入
②①ES规则
③前提引入
④③US规则
⑤②④假言推理
⑥⑤EG规则
ü用自然推理系统中,证明下列推理:
(x)(A(x)→B(x))((x)A(x)→(x)B(x))
证明:
①(x)A(x)附加前提引入
②A(c)①
③(x)(A(x)→B(x))前提引入
④A(c)→B(c)③
⑤B(c)②④假言推理
⑥(x)B(x)⑤
⑦(x)A(x)→(x)B(x)①⑥CP规则
所以(x)(A(x)→B(x))((x)A(x)→(x)B(x))
ü判断下面推理是否正确,并证明你的结论。
如果他是计算机系本科生或者是计算机系研究生,那么他一定学过DELPHI语言而且学过C++语言。
只要他学过DELPHI语言或者C++语言,那么他就会编程序。
因此如果他是计算机系本科生,那么他就会编程序。
请用命题逻辑推理方法,证明该推理的有效结论。
证明:
令p:
他是计算机系本科生
q:
他是计算机系研究生
r:
他学过DELPHI语言
s:
他学过C++语言
t:
他会编程序
前提:
(p∨q)→(r∧s),(r∨s)→t
结论:
p→t
证①p附加前提
②p∨q①附加律
③(p∨q)→(r∧s)前提引入
④r∧s②③假言推理
⑤r④化简律
⑥r∨s⑤附加律
⑦(r∨s)→t前提引入
⑧t⑤⑥假言推理
ü在自然推理系统中构造下面推理的证明:
前提:
结论:
证明:
前提引入
前提引入
假言推理
前提引入
假言推理
附加律
ü判断下面推理是否正确,并证明你的结论。
如果小王今天家里有事,则他不会来开会。
如果小张今天看到小王,则小王今天来开会了。
小张今天看到小王。
所以小王今天家里没事。
解:
设p:
小王今天家里有事,q:
小王来开会,r:
小张今天看到小王
本题推理的形式结构是:
前提:
,
结论:
证明:
1.前提引入
2.前提引入
3.1,2假言推理
4.前提引入
5.3,4拒取式
集合论部分
选择、填空及判断
ü设集合A={1,2,3,4},B={2,4,6,9},那么集合A,B的对称差AÅB=(C).
(A){1,3}(B){2,4,6}(C){1,3,6,9}(D){1,2,3,4,6,9}
ü集合A={1,2,3,6},A上的小于等于关系具有的性质是(D)。
(A)自反的,对称的,传递的;(B)反自反的,对称的,传递的;
(C)反自反的,反对称的,传递的;(D)自反的,反对称的,传递的。
ü设A={a,b,c},R={,},则R具有性质(C).
(A)自反的(B)反自反的(C)反对称的(D)等价的
ü设A,B,C为任意集合,下面结论正确的是(D)
A.如果,则B=CB.如果,则A=B
C.D.
ü设,下列各式中(B)是正确的
A.domSBB.domSAC.ranSAD.domSranS=S
ü令A={1,2,3,4},R={<1,2>,<3,4>,<2,2>},则s(R)=(B)。
(A){<1,2>,<3,4>,<2,2>}(B){<1,2>,<2,1>,<3,4>,<4,3>,<2,2>}(C){<1,2>,<3,4>,<1,1>,<2,2>,<3,3>}(D){<1,2>,<2,2>}
ü设A={1,2,3},则A上的二元关系有(C)个。
(A)23(B)32(C)(D)
ü设集合A={1,2,3,5,6,8},A上的二元关系R={|a,b∈A∧a≡(bmod3)},则[2]R=(B)。
(A){1,2}(B){2,5,8}(C){3,6}(D){1}
ü偏序关系具有的性质是(D)
A.自反的,对称的,传递的B.反自反的,对称的,传递的
C.反自反的,反对称的,传递的D.自反的,反对称的,传递的
ü等价关系具有的性质是(A)。
A.自反的、对称的、传递的B.反自反的、对称的、传递的
C.反自反的、反对称的、传递的D.自反的、反对称的、传递的
ü集合A={1,2,…,10}上的关系R={|x+y=10,x∈A,y∈A},则R的性质是(B)。
A.自反的B.对称的C.传递的、对称的 D.反自反的、传递的
ü设A={1,2,3,4,5,6},B={a,b,c,d,e},以下哪一个关系是从A到B的满射函数(B)。
A.f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>}
B.f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>}
C.f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>}
D.f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>}
ü设R是集合A={a,b,c}上的二元关系,且R={,},下面命题哪些为真?
(B)
ⅠR是自反的且是传递的
ⅡR是对称的且是反对称的
ⅢR是A上的等价关系
A.只有ⅠB.只有ⅡC.Ⅰ和ⅡD.Ⅱ和Ⅲ
ü设是一个偏序集,其中,A={1,2,3,4,5,6},R是整除关系,下面说法不正确的是(C)
A.4,5,6全是A的极大元B.A没有最大元
C.6是A的上界D.1是A的最大下界
ü设和都是X上的双射函数,则为(C)
A.B.C.D.
ü集合A={1,2,3}上所有的等价关系的总数是(B)
A.2B.5C.9D.取决于元素是否为数值
ü设,则下面命题中唯一正确的是(D)
(A)f是从X到Y的二元关系,但不是从X到Y的函数
(B)f是从X到Y的函数,但不是满射,也不是单射
(C)f是从X到Y的满射,但不是单射
(D)f是从X到Y的双射
ü设X={a,b,c},R是X上的二元关系,其关系矩阵为MR=,则传递闭包t(R)的关系图为。
ü设集合A={1,2,3,4},B={a,b,c},则½A×B½=12.
ü设A={a,b,c},则A的幂集ρ(A)=。
ü设集合A={1,2},则A上的全域关系={<1,1>,<1,2>,<2,1>,<2,2>}。
ü设R是实数集合,则
ü设个体域D={1,2},那么谓词公式消去量词后的等值式为(A
(1)∨A
(2))∨(B
(1)∧B
(2))。
ü给定集合和这个集合上的整除关系.在这个关系下,该集合的最小元是不存在,而最大元是120
ü设A,B,C,D为任意集合,则的充要条件为。
(×)
ü非空集合A上的任意关系R不是对称的就是反对称的。
(×)
ü关系R是反对称的当且仅当。
(×).
ü集合的笛卡尔积运算满足交换律。
(×)
ü集合A上的恒等关系是一个双射函数。
(√)
ü若集合A上的关系R是对称的,则也是对称的。
(√)
ü设A,B为任意集合,如果A∪B=A,那么B=。
(×)
ü设命题“如果f是双射的,则”是真命题。
(√)
ü集合A上的全域关系是等价关系。
(√)
计算
ü某班有25个男生,其中14人会打篮球,12人会打排球,6人会打篮球和排球,5人会打篮球和网球,还有2人3种球都会打。
已知6个会打网球的人都会打篮球或排球。
求不会打球的人数。
答案:
利用包含排斥原理或文氏图可求得不会打球的有5人。
ü设,A上的关系R如下:
,
(1)证明:
R是A上的等价关系;
(2)求:
A上对应于R的划分。
解题要点:
(1)分别说明R的自反性、对称性和传递性。
(2){{1,6,11,16},{2,7,12,17},{3,8,13,18},{4,9,14,19},{5,10,15,20}}
详细解答:
(1)(k为整数)
R的自反性:
任意,,所以;
R的对称性:
任意,若则,
所以,
R的传递性:
任意,若,
有
所以,。
即R是A上的等价关系。
(2),,,
,。
所以,。
ü设,为上的关系,的关系图如下图所示,
·
·
·
·
·
·
1
6
5
4
3
2
(1)求的集合表达式;
(2)求的集合表达式。
解:
(1),
(2)
ü设集合A={1,2,3},R和S是A上的两个关系,它们的关系矩阵为:
(1)写出关系R和S的集合表达式,
(2)画出R和S的关系图,(3)说明R和S满足关系的哪些特性.
解:
(1)R={(1,1),(1,2),(2,1),(2,2),(2,3),(3,1),(3,3)};
S={1,1),(1,2),(2,3),(1,3)}
(2)R和S的关系图:
(2分)
(3)R满足自反性;S满足反对称性、传递性。
ü设A={1,2,3,4,5},A上偏序关系
R={〈1,2〉,〈3,2〉,〈4,1〉,〈4,2〉,〈4,3〉,〈3,5〉,〈4,5〉}∪IA;
(1)作出偏序关系R的哈斯图
(2)令B={1,2,3,5},求B的最大,最小元,极大、极小元,上界,下确界,下界,下确界。
答:
(1)偏序关系R的哈斯图为
(2)B的最大元:
无,最小元:
无;
极大元:
2,5,极小元:
1,3
下界:
4,下确界4;
上界:
无,上确界:
无
证明
ü设R是集合A上的二元关系,试证明R是反对称的当且仅当.
证明:
(1)R是反对称的,假定∈R∩Rc,则∈R∧∈Rc∈R∧∈R,因为R是反对称的,故x=y.所以=∈IA.即
(2)R是反对称的,若,设∈R并且∈R,则∈R∧∈Rc∈R∩Rc∈IA,故x=y,即R是反对称的。
ü如果集合A上的关系R和S是自反的、对称的和传递的,证明:
是A上的等价关系。
证明:
(1)
自反。
(2),若,则
由R,S对称,所以,,
所以对称。
(3),若
则
由R,S传递性知,从而
所以,传递。
综上所述,是A上的等价关系。
图论部分
选择、填空及判断
ü无向完全图K4是(B).
(A)欧拉图;(B)哈密顿图;(C)树;(D)非平面图。
ü下列编码是前缀码的是(C)
A.{1,11,101}B.{1,001,0011}C.{1,01,001,000}D.{0,00,000}
ü设T为n阶无向树,T有几条割边?
(C)
A.n条B.n-2条C.n-1条D.没有
ü具有4个结点的非同构的无向树的数目是(A)
A.2B.3C.4D.5
ü下列编码是前缀码的是(B)