（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）
升级会员 