数理逻辑复习题
数理逻辑复习题
复习要求：
掌握命题、逻辑联结词的概念；公式与解释的概念，用基本等价式化简其他公式；会用真值表法和主范式判断公式的类型；公式蕴涵与逻辑结果的概念；形式演绎方法.一阶逻辑的基本概念，一阶逻辑公式及其解释，等值演算，推理理论；一阶逻辑公式的三种类型，即逻辑有效式（永真式），矛盾式和可满足式；用联结词产生复合命题的方法；公式在解释下的真值；公式范式的概念；形式演绎和蕴涵的关系.命题逻辑与一阶逻辑推理理论.
一、命题逻辑部分
1、填空题.
⑴公式（p∧?q）∨（?p∧q）的成真赋值为01，10 .
⑵设p、r为真命题，q、s为假命题，则复合命题（p→q）?（?r→s）的真值为0 .
⑶设p、q为命题，在p、q 不能同时发生条件下，p与q的排斥或也可以写成p与q的相容或.
⑷设A为任意公式，B 为重言式，则A∨B的类型是重言式
⑸设A是含命题变项p、q、r的重言式，则公式A∨（（p∧q）→r）的类型为重言式.
⑹设B 是含命题变项p、q、r的矛盾式，则公式B∧（（p?q）→r）的类型为矛盾式.
⑺矛盾式的主析取范式是0 .
⑻重言式的主合取范式是 1 .
⑼设公式A含命题变项p、q、r已知A主合取范式是M
0∧M
2
∧M
5
∧M
6
，则A的主析取范式是.
⑽已知公式?（q→p）∧p是矛盾式，则公式?（q→p）∧p∧?r的成真赋值是成假赋值.
⑾已知公式（p→（p∨q））∧（（p∧q）→p）是重言式，公式p→（p∨q）及（p∧q）→p类型
是.
⑿已知公式（p∧q）→p是重言式，则公式（（p∧q）→p）∨r的成真赋值是成假赋值.
⒀（A→B）∧?B?为拒取式推理定律.
⒁（A∨?B）∧B?为析取三段论推理定律.
⒂（?A→B）∧（B→?C ）?为假言三段论推理定律.
⒃（?A→?B）∧?A?为假言推理定律.
2、将下列命题或语句符号化.
⑴. ??p（p）
⑵小刘既不怕苦，又很钻研. ?p∧q
⑶只有不怕困难，才能战胜困难q→?p
⑷只要别人有困难，老王就帮助别人，除非问题解决了. ?r→（p→q）；（?r∧p）→q或?q→（?p∨r）
⑸整数n是偶数当且仅当n能被2整除. p?q
⑹若地球上没有树木，则人类不能生存. q
p?
→
?
⑺若4
2
2=
+，则地球是静止不动的. q
p→
3、求下列复合命题真值.
P：2能整除5，q：旧金山美国的首都，r：一年有四季
⑴（（p∨q）→r）∧（r→（p∧q）
⑵（（?q?p）→（r∨p））∨（（?p∧?q）∨?r）
4、判断下面一段论述是否为真：“3是无理数.并且，如果3是无理数，则2也是无理数.另外，只有6能被2
整除，6才能被4整除.”
解设p：3是无理数，q：3是无理数，r：2是无理数，s：6能被2整除，t：6能被4整除.
则原命题为：)
(
)
(s
t
r
q
p→
∧
→
∧，这里0
,1
,1
,0
,1=
=
=
=
=t
s
r
q
p.
则)
(
)
(s
t
r
q
p→
∧
→
∧1
1
1
1
)1
0(
)1
0(
1?
∧
∧
?
→
∧
→
∧
?.
５、判断公式的类型.
⑴（?（q?p）→（（p∧?q）∨（（?p∧q）））∨r 重言式
⑵（p∧?（q→p））∧（r∧q）矛盾式
⑶（p??r）→（r?q）可满足式
６、求公式p→（（q∧r）∧（p∨（?q∧?r）））的主析取范式和主合取范式.
m
0∨m
1
∨m
2
∨m
3
∨m
7
７、求公式?（?（p→q）∨（?q→?p）的主合取范式.
８、将公式p→（q→r）化成与之等值的且仅含{?，∧}中联结词的公式. ?（p∧q∧?r）
９、用主析取范式或主合取范式判断两公式是否等值.
?（p?q）与（（p∨q）∧?（p∧q））等值
10、在自然推理系统P中，构造下面推理的证明.
⑴前提：?（p∧?q），q→?r，r 结论：?p
⑵前提：p→r，q→s，p，q 结论：（r∧s）∨t
11、在自然推理系统P中，用附加前提法证明下面推理.
⑴前提：?p∨（q→r），s→p，q 结论：?r→?s
⑵前提：?p→q，?p∨r，q→s 结论：?s→r
12、在自然推理系统P中，用归谬法证明下面推理.
前提：p→（q →r ），p∧q 结论：r∨s
13、在自然推理系统P中，构造下面用自然语言给出的推理.
若小张喜欢数学，则小赵或小李也喜欢数学. 若小李喜欢数学，他也喜欢物理.小张确实喜欢数学，可小李不喜欢物理，所以小赵喜欢数学.
P：小张喜欢数学q：小赵喜欢数学r：小李喜欢数学S：小李喜欢物理
前提：P→（q∨r），r→s，p，?s 结论：q
证明①r→s
②?s
③?r
④P→（q∨r）
⑤p
⑥q∨r
⑦ q
14、设p：A到过受害人房间q：A在11点以前离开房间r：A犯谋杀罪看门人看到A
则{p∧?q→r，p，q→s，?s}|=r
①?s 前提引入
②q→s前提引入
③?q ①②拒取
④p 前提引入
⑤p∧?q ③④合取
⑥ p ∧?q →r 前提引入 ⑦ r ⑤ ⑥假言推理 二、一阶逻辑部分
1.在一阶逻辑中将下列命题符号化.
⑴ 所有的整数，不是负整数，就是正整数，或者是零.
解 F （x ）：x 是整数G （x ）：x 是正整数H （x ）：x 是负整数L （x ）：x 是0
?x （F （x ）→ G （x ）∨H （x ）∨L （x ））或?x （F （x ）∧? G （x ）→H （x ）∨L （x ）） ⑵ 有的实数是有理数有的实数是无理数. 解 F （x ）：x 是实数 G （x ）：x 是有理数 H （x ）：x 是无理数
?x （F （x ）∧G （x ）
）∧?y （F （y ）∧ H （y ）） ⑶ 不存在能表示成分数无理数.
解 F （x ）：x 能表示成分数 G （x ）：x 是无理数
??x （G （x ）∧ F （x ）
）??x （G （x ）→? F （x ）） ⑷ 若x 、y 都是实数，且x>y ，则x+2>y+2. 解 F （x ）：x 是实数 H （x ，y ）：x>y
?x ?y （F （x ）∧F （y ）∧ H （x ，y ）→ H （x+2，y+2）） ⑸不存在最大的自然数.
解 F （x ）：x 是自然数 H （x ，y ）：x>y
??x （F （x ）∧?y
（F （y ）→ H （x ，y ））
⑹ 在北京卖菜的人不全是外地人.
解 设)(x M ：x 是外地人. )(x F ：x 在北京卖菜. 则符号化为))()((x F x M x ∧??. ⑺ 设：)(x M ：x 是火车. )(x H ：x 是轮船. )(x F ：x 是汽车. ),(y x G ：x 比y 快. 则“火车都比轮船快.”符号化为)),()()((y x G y H x M y x →∧??. 则“有的火车比有的汽车快.”符号化为)),()()((y x G y F x M y x ∧∧??.
则“不存在比所有火车都快的汽车.”符号化为)))),()(()(((y x G y M y x F x →?∧??. 4、 指出下列公式中的指导变元，量词的辖域，各个体变项的自由出现和约束出现： （1）)),()((y x G x F x →?
解 x ?的辖域：),()(y x G x F →.x 是指导变元. x 是约束出现，y 是自由出现. （2）),(),(y x yG y x xF ?→?
解 x ?的辖域：),(y x F .x 是指导变元. x 是约束出现，y 是自由出现.
y ?的辖域：),(y x G .y 是指导变元. x 是自由出现，y 是约束出现.
5、 证明下面公式既不是永真式也不是矛盾式： （1）))),()(()((y x H y G y x F x ∧?→?
证明 1解释1I ：R D =，)(x F ：x 是正数.)(y G ：y 是负数.),(y x H ：0=+y x .
))),()(()((y x H y G y x F x ∧?→?指对任意正数x ，
存在负数y ，使得0=+y x .在该解释下，命题为“真”.
2解释2I ：}3,2,1{-=D ，)(x F ：x 是正数.)(y G ：y 是负数.),(y x H ：0=+y x .则对1=x 时，不存
在负数D y ∈，使0=+y x ，故在该解释下，命题为“假”，所以（1）公式既不是永真式也不是矛盾式. （2）)),()()((y x H y G x F y x →∧??
6、设个体域},,{c b a D =，消去下列各式的量词： （1）))()((y G x F y x ∧??
)))()(((y G a F y ∧??)))()(((y G b F y ∧?∧)))()(((y G c F y ∧?∧
(
(
((a
G
∧))
F∨
(c
G
a
b
F∨
G
b
F
∨
(b
(
∧))
(
)
(
)
((a
G
a
F∨
(
)
∧
?))
(
∧))
)
a
∧)))
(
(
G
F∧
)
(
(b
G
(b
(
(
F)))
∧))
)
c
F∧
F∨
G
(c
)
(
(
c
(c
G
b
(
(
c
∧)))
F∨
)
∧
G
(
((a
∧))
(
)
（2）))
F
b
y∨
?
G
)
∧)))
(
(
(y
y∨
F
(
?
∧
c
G
)
(
(
(y
(
y∨
x
F
y
x∨
?)))
(y
(
)
(
?
G
G
F
?
?)))
(y
a
(
(
)
(
F∧
∨)))
a
(b
(
G
F
a
(
G
(c
(
)
∨))
)
(
(
?))
)
((a
∨
G
(
∧
a
F∧
F∧
∨)))
G
(b
(
b
(c
(
F
b
G
(
)
)
(
(
∨))
)
((a
∧
G
(
∨))
b
F∧
F)))
(
(b
G
c
(c
F∨
(
c
G
(
)
G
)
(
∨))
∧
)
(
(
((a
∨))
F∧
c
7、求前束范式
⑴??x?yF（x，y）（??x?y?F（x，y））
⑵（?xF（x，y）→?yG（x，y，z））→?z H（z）.
（??x?y?z（F（x，t）→G（u，y，v）→H（z）））
⑶?
)
(
(
?))
xF?
→
(y
,
G
?
?
?
x→
y
x
x
z
F
(
)
(y
,
→
yG
?
x
?)
)
yG
z
(
(y
x
,
xF)
⑷?
x))
,
(
F
)
,
x
,
y
yG
t
x
x→
y
F
(z
?
?
x
t
(z
y
x
G
(
?))
(
)
(z
y
x
(
,
(
?
→
,
yG
,
,
?))
,
(
)
→
,
x
F
x?
?
y
⑸?
,
(y
)
(
,
z
zG
?
xF?
x
t
xF)
?
,
(
?
?
x
)
?)
xG
,
x
y
(y
t
x
zG
y
zG
xF?
z
?
y
?
→
?
?
∧
→
z
,
(
(
)
(
xF
,
))
))
(t
x
,
(
,
(
)
t
s
x
sG
z
y
z
G
∧
?
?
?
→
→
?
x?
F
,
(
(
)
(
g
,
))
))
,
r
rF
(
(h
(
,
)
t
F
x
s
z
y
z
G
→
?
?
r
?
∧
?
?
x→
G
(
))
,
(
,
))
(
)
(
,
F
g
)
r
s
(h
,
(
F
s
r
t
y
z
G
z
x
∧
?
?
G
?
?
→
?
x→
,
(
(
s
)
(
)))
,
,
))
(
F
g
((h
r
(
)
,
中构造下面推理的证明.
8、在自然推理系统N
L
⑴前提：?xF（x）→?y（G（y）→H（y）），?xR（x）→?yG（y）
结论：?x（F（x）∧R（x））→?x H （x）
证明1 ⑴?x（F（x）∧R（x））
⑵F（c）∧R（c）
⑶F（c）
⑷R（c）
⑸?x F（x）
⑹?xF（x）→?y（G（y）→H（y））
⑺?y（G（y）→H（y））
⑻G（c）→H（c）
⑼R（c）
⑽?x R（x）
⑾?xR（x）→?yG（y）
⑿?yG（y）
⒀G（c）
⒁H（c）
⒂?x H （x）
证明2：⑴?x（F（x）∧R（x））
⑵?x F（x）∧?x R（x））
⑶?x F（x）
⑷?xF（x）→?y（G（y）→H（y））
⑸?y（G（y）→H（y））
⑹G（c）→H（c）
⑺?xR（x）→?yG（y）
⑻?x R（x））
⑼?yG（y）
⑽G（c）
⑾H（c）
⑿?x H （x）
⑵人都喜欢吃蔬菜.但说所有的人都喜欢吃鱼是不对的.所以存在只喜欢吃蔬
菜而不喜欢吃鱼的人.
F（x）：x是人G（x）：喜欢吃蔬菜H （x）：喜欢吃鱼
前提：?x（F（x）→G（x））??x（F（x）→H（x））
结论：?x（F（x）∧G（x）∧?H（x））
证明：⑴??x（F（x）→H（x））
⑵?x?（F（x）→H（x））
⑶?x（F（x）∧?H（x））
⑷F（c）∧?H（c）
⑸?x（F（x）→G（x））
⑹F（c）→G（c）
⑺F（c）
⑻G（c）
⑼F（c）∧?H（c）∧G（c）
⑽?x（F（x）∧G（x）∧?H（x））
⑶任意三角形的内角和等于1800，ABC三角形，则ABC的内角和等于1800.
证明设F（x）：x是三角形G（x）：x的内角和等于1800a：ABC
前提：?x（F（x）→G（x））F（a）
结论：G（a）
证明：⑴?x（F（x）→G（x））
⑵F（a）→G（a）
⑶F（a）
⑷G（a）
（4）每个喜欢步行的人都不喜欢骑自行车.每个人或者喜欢骑自行车或者喜欢乘汽车.有的人不喜欢乘汽车.所以有的人不喜欢步行.（个体域为人类集合）.
证明设F（x）：x喜欢步行G（x）：x喜欢骑自行车H（x）：x喜欢乘车
｛?x（F（x）→?G（x）），?x （G（x）∨H（x），?x ?H（x））→?x ?F（x）
①?x ?H（x）
②?H（c）
③?x （G（x）∨H（x））
④G（c）∨H（c）
⑤G（c）
⑥?x（F（x）→?G（x））
⑦F（c）→?G（c）
⑧?F（c）
⑨?x ?F（x）
(5)每个科学工作者都是刻苦钻研的，每个刻苦钻研而有聪明的人在他的事业中都将获得成功.王大海是科学工作者，并且是聪明的.所以王大海在他的事业中将获得成功.（个体域为人类集合）.
证明设F（x）：x是科学工作者G（x）：x喜欢钻研H（x）：x聪明
W（x）：x事业成功a：王大海
｛?x（F（x）→G（x）），?x（G（x）∧H（x）→W（x）），F（a），H（a）｝→W（a）
①?x（F（x）→G（x））
②F（a）→G（a））
③?x （G（x）∧H（x）→W（x））
④G（a）∧H（a）→W（a）
⑤F（a）
⑥G（a）
⑦H（a）
⑧G（a）∧H（a）
⑨W（a）
离散数学数理逻辑部分考试试
离散数学形成性考核作业（四） 数理逻辑部分 本课程形成性考核作业共4次，内容由中央电大确定、统一布置。本次形考作业是第四次作业，大家要认真及时地完成数理逻辑部分的形考作业，字迹工整，抄写题目，解答题有解答过程。 第6章命题逻辑 1．判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题． （1）8能被4整除． （2）今天温度高吗？ （3）今天天气真好呀！ （4）6是整数当且仅当四边形有4条边． （5）地球是行星． （6）小王是学生，但小李是工人． （7）除非下雨，否则他不会去． （8）如果他不来，那么会议就不能准时开始． 解：此题即是教材P.184习题6（A）1 （1）、（4）、（5）、（6）、（7）、（8）是命题，（2）、（3）不是命题。 其中（1）、（5）是简单命题，（4）、（6）、（7）、（8）是复合命题。 2．翻译成命题公式 （1）他不会做此事． （2）他去旅游，仅当他有时间． （3）小王或小李都会解这个题． （4）如果你来，他就不回去． （5）没有人去看展览． （6）他们都是学生． （7）他没有去看电影，而是去观看了体育比赛． （8）如果下雨，那么他就会带伞． 解：此题即是教材P.184习题6（A）2
会带伞。 ：如果下雨，那么他就：他会带伞。 ：天下雨。）（。是去观看了体育比赛。：他没有去看电影，而。 ：他去观看了体育比赛：他去看电影。）（：他们都是学生。 ）（：没有人去看展览。 ：有人去看展览。）（去。 ：如果你来，他就不回：他回去。：你来。）（道题。：小王或小李都会解这：小李会解这道题。 ：小王会解这道题。）（时间。 ：他去旅游，仅当他有：他有时间。 ：他去游泳。）（：他不会做此事。：他会做此事。）（Q P Q P Q P Q P P P P Q P Q P Q P Q P Q P Q P P P →∧???→∧→?87654321 3．设P ，Q 的真值为1；R ，S 的真值为0，求命题公式(P ∨Q )∧R ∨S ∧Q 的真值． 解：此题即是教材P.184习题6（A ）4（2） (P ∨Q )真值为1，(P ∨Q )∧R 真值为0，S ∧Q 真值为0， 从而(P ∨Q )∧R ∨S ∧Q 真值为0。 4．试证明如下逻辑公式 （1） ┐（A ∧┐B ）∧（┐B ∨C ）∧┐C ? ┐（A ∨C ） （2） (P →Q )∧(Q →R )∧┐R ??P （此题即是教材P.185习题6（A ）5（1）、（4）） ) 7() () 8()6)(5()7()4)(2()6()4)(3()5()4()3()1() 2()() 1()(), (),(由由由由由证明：结论：前提：T B A T B A T A T B P C P C B T B A P B A B A C C B B A ∨??∧????∨?∨??∧?∨??∨??∧? ) 4)(3() 5()4()2)(1()3() 2() 1(), (),(由由证明：结论：前提：T P P R T R P P R Q P Q P P R R Q Q P ??→→→??→→
形式逻辑-课后习题-答案(含原题)
第四章简单命题及其推理 一、下列命题是哪种直言命题？请指出命题的主项、谓项、联项、量项及主谓项的周延情况。 1．共产党员是无产阶级先进分子。答：这是个全称肯定命题（A），全称肯定量项省略；“共产党员”是主项；“是”为联项；“无产阶级先进分子”是谓项。主项周延，谓项不周延。 2．任何困难都不是不可克服的。答：这是个全称否定命题（E）。全称量项“任何”；主项“困难”；联项“不是”；谓项为负概念“不可克服的”。其主项、谓项都周延。 3．有些图书是线装书。答：这是特称肯定命题（I）。量项“有些”；主项“图书”；联项“是”；谓项“线装书”。其主项、谓项均不周延。 4．《女神》是郭沫若的诗集。答：这是个单称肯定命题。《女神》是主项；“是”是联项；“郭沫若的诗集”是谓项。其主项周延，谓项不周延。 5．有些学生不刻苦。答：这个命题一般理解为O命题：有些学生不是刻苦的。“学生”是主项；“刻苦的”是谓项；“不是”是联项；“有些”是量项。其主项不周延，谓项周延。 二、下列对当关系推理是否有效？为什么？ 1．由“有的植物不开花”真，推知“所有植物都开花”假。 答：正确。因为O与A是矛盾关系，由O真可推知A假。 2．由“凡环境污染都对人身体有害”真，推知“有的环境污染不对人身体有害”假。 答：正确。因为A与O是矛盾关系，由A真可推知O假。 3．由“有人生而知之”假，推知“有人不是生而知之”真。 答：正确。I与O是下反对关系，由I假可推知O真。 4．由“有的大学生是有理想的”真，推知“所有大学生都是有理想的”假。 答：不正确。I与A是从属（差等）关系，由I真推不出A假。 5．由“所有的古代散文都不押韵”假，推知“有的古代散文押韵”真。 答：正确。E与I是矛盾关系，由E假可推知I真。 6．由“所有的新诗都不押韵”假，推知“所有新诗都押韵”真。 答：不正确。E与A是反对关系，由E假推不出A真。 三、根据命题的对当关系，由已知下列命题的真假，断定同素材的其它三种命题的真 1．已知“某单位职工都买了电冰箱”为假。 答：这是个A命题。当A假时，同素材的E命题“某单位职工都没买电冰箱”真假不定；I命题“某单位职工有的买了电冰箱”真假不定；O命题“某单位有的职工没买电冰箱”为真。 2．已知“某班同学都不是会打桥牌的”为真。 答：这是个E命题。当E真时，A命题“某班同学都是会打桥牌的”为假；I命题“某班同学有的是会打桥牌的”为假；O命题“某班同学有的不是会打桥牌的”为真。 3．已知“有的科学家是自学成才的”为真。 答：这是个I命题。当I真时，A命题“所有的科学家是自学成才的”可真可假；E命题“所有的科学家不是自学成才的”为假；O命题“有的科学家不是自学成才的”可真可假。 4．已知“有的教授不是懂外语的”为假。 答：这是个O命题。当O假时，A命题“所有的教授都是懂外语的”为真；E命题“所有的教授都不是懂外语的”为假；I命题“有的教授是懂外语的”为真。 四、根据命题的对当关系，选择相应的命题来确定下列命题的虚假。 1．所有青年都是积极向上的。答：有的青年不是积极向上的。 2．有的理论是检验真理的标准。答：任何理论都不是检验真理的标准。
数理逻辑期末复习题
数理逻辑期末复习题 1. 符号化：我将去镇上，仅当我有时间。 答：设p：我将去镇上，q：我有时间。命题符号化为：p→q 2. 符号化：他13岁或14岁。 答：设p：他13岁，q：他14岁。命题符号化为：()()p q p q p q ∨ ∧?∨?∧或3. 利用等值演算验证： (())(())(())A B C D C A B D C A B D ∧∧→∧→∨∨?∧?→ 证明： (())(()) (())(()) ()(()[()()] ()[()()] ()[()()] ()[()()] ()() [()][(A B C D C A B D A B C D C A B D A B C D C A B D C D A B A B C D A B B A C D A B B A C D B A A B C D A B C A B D C ∧∧→∧→∨∨??∧∧∨∧?∨∨∨??∨?∨?∨∧?∨∨∨??∨∨?∨?∧∨??∨∨?∧∨?∧??∨∨?∨?∨?∨???∨∨?→∧→??∨∨????∨??∨??∧)][()]A B D C A B D ?∨?∧?→) p 4. 符号化下列命题并完成推理证明。 如果6是偶数，则7不被2整整除；或者5不是质数，或者7被2整除；但5是质数。所以，6是奇数。 解：设p:6是偶数；q：7被2整除；r:5是质数。 命题符号化为： ,,p q r q r →??∨??证明： （1）r P （2） P r q ?∨（3）q T(1)(2)I （4）p q →? P （5）q T(4)E p →?（6）p ? T(4)(5)I 5. 推理证明：(),,A B C D C D A B ∧→??∨??∨?
数理逻辑考试题及答案
“离散数学”数理逻辑部分考核试题答案 ━━━━━━━━━━━━━━━━━━★━━━━━━━━━━━━━━━━━━ 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：p∧q，其中，P：小刘怕吃苦；q：小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→p，其中，P：怕敌人；q：战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：r→(p→p)，其中，P：别人有困难；q：老张帮助别人；r：困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P：小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A：((p q)((p q) (p q))) r （1）B：(p(q p)) (r q) （2）C：(p r) (q r) （3）E：p(p q r) （4）F：(q r) r 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。 3、判断推理是否正确（总共2题，完成的题号为学号尾数取2的余，完成1题。共2分） （0）设y=2|x|，x为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，x为实数。令P：y在x=0处可导，q：y在x=0处连续。由此，p为假，q为真。本题推理符号化为：(p q) q p。由p、q的真值，计算推理公式真值为假，由此，本题推理不正确。 （1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令p:2是素数，q:3是素数，r:5是奇数，s:6是奇数。由此，p=1，q=1，r=1，s=0。本题推理符号化为： ((p q) →s) p q) →(r s)。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算（5分） 1、用等值演算法求下列公式的主析取范式或主合取范式（总共3题，完成的题号为学号尾数取3的余，完成1题。共2分） （0）求公式p→((q∧r) ∧(p∨(q∧r)))的主析取范式。 解：p→((q∧r) ∧(p∨(q∧r)))p∨(q∧r∧p) ∨(q∧r∧q∧r) p∨(q∧r∧p) ∨0 (p∧q∧r) ∨ (p∧1∧1) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨(q∧r∧p) (p∧(q∨q)∧(r∨r)) ∨m7 (p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)∨m7 m0∨m1∨m2∨m3∨m7. （1）求公式((p→q)) ∨(q→p)的主合取范式。 解：((p→q)) (q→p) (p→q) (p→q) (p→q) p q M2.
离散数学之集合论
第二篇集合与关系 集合论是现代各科数学的基础，它是德国数学家康托（Geog Cantor, 1845～1918）于1874年创立的，1876～1883年康托一系列有关集合论的文章，对任意元的集合进行了深入的探讨，提出了关于基数、序数和良序集等理论，奠定了集合论深厚的基础，19世纪90年代后逐渐为数学家们采用，成为分析数学、代数和几何的有力工具。 随着集合论的发展，以及它与数学哲学密切联系所作的讨论，在1900年前后出现了各种悖论，使集合的发展一度陷入僵滞的局面。1904～1908年，策墨罗（Zermelo）列出了第一个集合论的公理系统，它的公理，使数学哲学中产生的一些矛盾基本上得到了统一，在此基础上以后就逐渐形成了公理化集合论和抽象集合论，使该学科成为在数学中发展最为迅速的一个分支。 现在，集合论已经成为内容充实、实用广泛的一门学科，在近代数学中占据重要地位，它的观点已渗透到古典分析、泛函、概率、函数论、信息论、排队论等现代数学各个分支，正在影响着整个数学科学。集合论在计算机科学中也具有十分广泛的应用，计算机科学领域中的大多数基本概念和理论几乎均采用集合论的有关术语来描述和论证，成为计算机科学工作者必不可少的基础知识。集合论可作为数学学科的通用语言，一切必要的数据结构都可以利用集合这个原始数据结构而构造出来，计算机科学家或许也可以利用这种方法。 本篇介绍集合论的基础知识，主要内容包括集合及其运算、性质、序偶、关系、映射、函数、基数等。 第2-1章集合及其运算 §2-1-1 集合的概念及其表示 一、集合的概念 “集合”是集合论中的一个原始的概念，因此它不能被精确地定义出来。一般地说，把具有某种共同性质的许多事物，汇集成一个整体，就形成一个集合。构成这个集合的每一个事物称为这个集合的一个成员（或一个元素），构成集合的这些成员可以是具体东西，也可以是抽象东西。例如：教室内的桌椅；图书馆的藏书；全国的高等学校；自然数的全体；程序设计语言C的基本字符的全体等均分别构成一个集合。通常用大写的英文字母表示集合的名称；用小写的英文字母表示元素。若元素a属于集合A记作
数理逻辑练习题及答案-5
一阶逻辑等值式与置换规则 1．设个体域D={a,b,c}，消去下列各式的量词： (1) x y(F(x)∧G(y)) (2) x y(F(x)∨G(y)) (3) xF(x)→yG(y) (4) x(F(x,y)→yG(y)) 2．设个体域D={1,2}，请给出两种不同的解释I1和I2，使得下面公式在I1下都是真命题，而在I2下都是假命题。 (1) x(F(x)→G(x)) (2) x(F(x)∧G(x)) 3．给定解释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) x yF(x,y) (2) x yF(x,y) (3) x y(F(x,y)→F(f(x),f(y))) 4．构造下面推理的证明： (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) 5．证明下面推理： (1) 每个有理数都是实数，有的有理数是整数，因此有的实数是整数。 (2) 有理数、无理数都是实数，虚数不是实数，因此虚数既不是有理数、也不 是无理数。 (3) 不存在能表示成分数的无理数，有理数都能表示成分数，因此有理数都不 是无理数。
答案 1. (1) x y(F(x)∧G(y)) xF(x)∧yG(y) (F(a)∧F(b))∧F(c))∧(G(a)∨G(b)∨G(c)) (2) x y(F(x)∨G(y)) xF(x)∨yG(y) (F(a)∧F(b)∧F(c))∨(G(a)∧G(b)∧G(c)) (3) xF(x)→yG(y) (F(a)∧F(b)∧F(c))→(G(a)∧G(b)∧G(c)) (4) x(F(x,y)→yG(y)) xF(x,y)→yG(y) (F(a,y)∨F(b,y)∨F(c,y))→(G(a)∨G(b)∨G(c)) 2.(1) I1: F(x):x≤2,G(x):x≤3 F(1),F(2),G(1),G(2)均为真，所以 x(F(x)→G(x)) (F(1)→G(1)∧(F(2)→G(2))为真。 I2: F(x)同I1,G(x):x≤0 则F(1),F(2)均为真，而G(1),G(2)均为假， x(F(x)→G(x))为假。 (2)留给读者自己做。 3. (1) x yF(x,y)
数理逻辑测试题
玛 氏 食 品 ( 中国 ) 有 限 公 司 姓名：武英杰 性别：男 1-25 题均为选择题，只有一个正确答案。答案写在( ) 内 1-6 题根据下列数字规律，选择( )内应填数字： ( B ) 1、 2，9，16，23，30，（ ） A.35 B.37 C.39 D.41 ( C ) 2、 5，11，20，32，（ ） A ．43 B ．45 C ．47 D ．49 ( C )3、 1，2，3，5，（ ），13 A 9 B 11 C 8 D7 ( A )4、 5，7，（ ），19，31，50 A 12 B 13 C 10 D11 ( C )5、 8，4，2，2，（ ） A 、2 B 、3 C 、4 D 、5 ( C)6、 14，20，29，41，( ) A.45 B.49 C.56 D.72 ( A ) 7、. 15.025.053÷?的值是： A ．1 B ．1.5 C ．1.6 D ．2.0 ( C ) 8、 1994年第二季度全国共卖出汽车297600辆，与上年同期相比增长了 24%。上年同期卖出多少辆汽车?
A．714224 B．226176 C．240000 D．369024 ( D ) 9、甲、乙两地相距42公里，A、B两人分别同时从甲乙两地步行出发， A的步行速度为3公里/小时，B的步行速度为4公里/小时，问A、B步行几小时后相遇？ A. 3 B. 4 C. 5 D. 6 ( A)10、一根绳子长40米，将它对折剪断；再对剪断；第三次对折剪断，此时每根绳子长多少米？ A、5 B、10 C、15 D、20 ( B ) 11、如果一米远栽一棵树，则285米远可栽多少棵树？ A、285 B、286 C、287 D、284 (B ) 12、在一本300页的书中，数字“1”在书中出现了多少次？ A、140 B、160 C、180 D、120 ( D ) 13、自然数A、B、 C、 D的和为90，已知A加上2，B减去2，C乘以 2，D除以2之后所得结果相同，则B等于（） A、26 B、24 C、28 D、22 ( B ) 14、某人工作一年的报酬是18000元和一台全自动洗衣机,他干了7个月, 得到9500和一台全自动洗衣机,问这台洗衣机值多少元? A.8500元 B.2400元 C.2000元 D.1700元 ( B ) 15、橱窗：商品；相当于 A 电影：明星 B 书架：书籍 C 宇宙：星球 D 餐馆：厨师
浅谈数理逻辑在计算机科学中的应用
浅谈数理逻辑在计算机科学中的应用 文章整理编辑---论文文库工作室（QQ1548927986） 摘要：数理逻辑是离散数学课程中研究推理的逻辑学科，它为确定一个给出的论证是否有效提供各种法则和技巧，在计算机科学里用来检验程序的正确性，也可以验证定理和推论，同时在计算机模型、计算机程序设计语言、计算机硬件系统等方面有着重要作用。研究数理逻辑在计算机科学领域中的应用，必须从研究数理逻辑的符号化开始讨论、加以分析、验证结论。 关键词：数理逻辑；命题逻辑；一阶逻辑；推理理论 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。其内容大致包含数理逻辑、集合论、代数结构、组合数学、图论和初等数论6部分，这6部分从不同的角度出发，研究各种离散量之间数与形的关系。本文主要研究数理逻辑部分在计算机科学领域中的应用。 1.为计算机的可计算性研究提供依据 数理逻辑分为命题逻辑和一阶逻辑两部分，命题逻辑是一阶逻辑的特例。在研究某些推理问题时，一阶逻辑比命题逻辑更准确。数理逻辑中的可计算谓词和计算模型中的可计算函数是等价的,互相可以转化，计算可以用函数演算来表达，也可以用逻辑系统来表达。 某些自然语言的论证看上去很简单，直接就可以得出结论，但是通过数理逻辑中的两种符号化表达的结果却截然不同，让人们很难理解，这就为计算机的可计算性研究埋下伏笔。下面举一个简单例子加以说明。 例1 凡是偶数都能被2整除。6是偶数，所以6能被2整除。 可见，一个复杂的命题或者公式可以利用符号的形式来说明含义，来判断正确性，这使得计算机科学中的通过复杂文字验证的推理过程变得简单、明了了。 2.为计算机硬件系统的设计提供依据 数理逻辑部分在计算机硬件设计中的应用尤为突出，数字逻辑作为计算机科学的一个重要理论，在很大程度上起源于数理逻辑中的布尔运算。计算机的各种运算是通过数字逻辑技术实现的，而代数和布尔代数是数字逻辑的理论基础，布尔代数在形式演算方面虽然使用了代数的方法，但其内容的实质仍然是逻辑。范式正是基于布尔运算和真值表给出的一个典型公式。 下面以计算机科学中比较典型的开关电路的设计为实例说明数理逻辑中布尔代数和范式的应用。整个开关电路从功能上可以看做是一个开关，把电路接通的状态记为1（即结果为真），把电路断开的状态记为0（即结果为假），开关电路中的开关也要么处于接通状态，要么处于断开状态，这两种状态也可以用二值布尔代数来描述，对应的函数为布尔函数，也叫线路的布尔表达式。接通条件相同的线路称为等效线路，找等效线路的目的是化简线路，使线路中包含的节点尽可能地少。利用布尔代数可设计一些具有指定的节点线路，数学上既是按给定的真值表构造相应的布尔表达式，理论上涉及到的是范式理论，但形式上并不难构造。 例2 关于选派参赛选手，赵，钱，孙三人的意见分别是：赵：如果不选派甲，那么不选派乙。钱：如果不选派乙，那么选派甲；孙：要么选甲，要么选乙。以下诸项中，同时满足赵，钱，孙三人意见的方案是什么？ 解答：把赵，钱，孙三个人的意见看做三条不同的线路，对三条线路化简得到接通状态
自主招生数学专题一不等式(习题补充版)
自主招生数学专题一：不等式 不等式是初等代数研究的问题之一，常见的考点包括未必局限于均值不等式（AM-GM不等式）、Cauchy不等式、排序不等式、Jensen不等式、三角不等式…某些求导才能求得函数最值的题也可以用卡尔松不等式、赫尔德不等式.还有一些常用的技巧还包括构造局部不等式、裂项、换元、线性规划、调整法等等.在不等式的凑配过程中我们还会用到因式分解、待定系数法、主元法等方法，还需要时刻注意不等式的取等条件. 近年来，有些同学跟我反映夏令营、自主招生的不等式题不会做，为了部分缓解(看来受生物实验毒害不浅)大家对不等式的恐惧,提升大家的能力,我整理了这个专题.在选题的过程中参考了《自招宝典》《自主招生直通车》《数学奥林匹克小丛书》以及一些竞赛或学科营中的题目，和之前在“高思教育”“北京数学学校”的课堂笔记，在此对他们表示感谢. 面对一道不等式,为什么有人能想到换元?为什么有人会这么凑系数?为什么会想到如此放缩?巧夺天工的证明往往蕴含了自然而优美的逻辑.希望通过对以下例题的探讨等够带大家初步领略不等式的妙处，提升大家对不等式的感觉. 【知识梳理】 1证明均值不等式 2用不包括向量法在内的三种方法证明Cauchy不等式 3证明排序不等式
【重要例题】 1(2015北大体验营)1=++c b a 求) 1)(1)(1(c b a abc ---的最大值 21=++c b a 求证:1)9111≥++c b a 2)3 1 222≥++c b a 3)127≤abc 4)3≤++c b a 5)3311 1 ≥+ + c b a 6)63115≤+∑a 7)(2011江西预赛)最大值求32c ab 3(2016清华自主招生)12 ==∑∑x x 求xyz 最值(原题为不定项选择题) 4设0,,>c b a ,求证2≥+++c b c b a a c 5(2008南开)5262 +=+++a bc ac ab ,0,,>c b a 求c b a 23++的最小值 6(2009清华自招)设0,,>z y x ,a,b,c 是x,y,z 的一个排列，求证3 ≥++z c y b x a 7求2 211x y y x -+-的最大值 8(2010浙大),,11 +=∈=∑R x x i n i i 求证41 3 >-∑ i i x x
离散数学模拟试卷和答案
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个
数理逻辑心得
数理逻辑的心得 数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。是大四接触到的，现简单介绍一下数理逻辑的发展史，算是一点感悟吧 1数理逻辑的发展前期 ·前史时期——古典形式逻辑时期：亚里斯多德的直言三段论理论 ·初创时期——逻辑代数时期（17世纪末） ·资本主义生产力大发展，自然科学取得了长足的进步，数学在认识自然、发展技术方面起到了相当重要的作用。 ·人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。 ·莱布尼兹(Leibniz, 1646~1716)完善三段论，提出了建立数理逻辑或者说理性演算的思想： ·提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。 ·使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号的组合规律，而与其含义无关。 ·布尔(G. Boole, 1815~1864)代数：将有关数学运算的研究的代数系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。 数理逻辑的奠基时期 ·弗雷格(G. Frege, 1848~1925)：《概念语言——一种按算术的公式语言构成的纯思维公式语言》(1879)的出版标志着数理逻辑的基础部分——命题演算和谓词演算的正式建立。 ·皮亚诺(Giuseppe Peano, 1858~1932)：《用一种新的方法陈述的算术原理》(1889)提出了自然数算术的一个公理系统。 ·罗素(Bertrand Russell, 1872~1970)：《数学原理》(与怀特黑合著，1910, 1912, 1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义了类和关系的概念，建立了抽象的类演算和关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。 ·逻辑演算的发展：甘岑(G. Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。 ·各种各样的非经典逻辑的发展：路易斯(Lewis, 1883~1964)的模态逻辑，实质蕴涵怪论和严格蕴涵、相干逻辑等，卢卡西维茨的多值逻辑等。 集合论的悖论使得人们觉得数学产生了第三次危机，提出了数学的基础到底是什么这样的问题。 ·罗素等的逻辑主义：数学的基础是逻辑，倡导一切数学可从逻辑符号推出，《数学原理》一书是他们这一思想的体现。为解决悖论产生了逻辑类型论。 ·布劳维尔(Brouwer, 1881~1966)的直觉主义：数学是心灵的构造，只承认可构造的数学，强调构造的能行性，与计算机科学有重要的联系。坚持潜无穷，强调排中律不能用于无穷集合。海丁(Heyting)的直觉主义逻辑。 ·希尔伯特(D. Hilbert)的形式主义：公理化方法与形式化方法，元数学和证明论，提倡将逻辑演算和数学证明本身形式化，把用普通的语言传达的内容上的数学科学变为用数学符号和逻辑符号按一定法则排列的一堆公式。为了消除悖论，要数学建立在公理化基础上，将
离散数学模拟试卷和答案
北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个
数理逻辑与集合论作业二 - 参考解答
數理邏輯與集合論作業二 1. 解：該題應該理解為此列表中每一句都是形如“i: 在這個列表中，恰有i條語句為假”的形式。 a)思路：考慮這100句裡可能有幾句為真。是否可能沒有一句為真？是否可能 祗有一句為真，是哪一句？是否可能多餘等於兩句為真？ b)思路：“至少i+1句為假”蘊含“至少i句為假”，若第i句為真，則1…… i-1句都為真，所以第 100, 99, 98, ……句都為假，一直到第50句為真 c) 思路同上，但是…… 2. 解答：如果我說右邊的路通往遺跡你將回答“是”，對嗎？ 3.
解答： ))))a q p b p q c q p d q p →∧→?→? 4. 也就是上述描述是否自相矛盾？ 5. 解答： 条件符号化 ::::(1)(2)(C G)(3)(G W)G W (4)G W G W S C G W S C G W S C C G W C C S C S →?∧=?∨???∧?=∨→?????男管家廚師園丁雜役假設為真，則由（2）得：再由（1）得：但無法判定的真假 假設為假，則由（3）得：再由（4）得：由（1）得：綜上所述：和說了假話，，的話真假未知 6. 四个朋友被认定为非法进入某计算机系统的嫌疑人。他们已对调查员作了陈述。
艾丽斯说“卡罗斯干的” 约翰说“我没幹。” 卡罗斯说“戴安娜干的。” 戴安娜说“卡罗斯说是我幹的，他说谎。” a）如果调查员知道四个嫌疑人中恰有一人说真话，那么准幹的？解释你的推理。 b）如果调查员知道恰有一人说谎，谁干的？解释你的推理。 解：前提符號化為 （1）A: C （2）J: ? J （3）C: D （4）D: ? (C: D) a) 祗有一句話為真，而（3）（4）有且僅有一句為真，分別討論（3）（4）為真的情況。 b）分析步驟同上。 7. 用真值表證明德摩根律和吸收律。 解答略 8. 使用等值演算證明下列命題公式為永真式（不得用真值表） 解答： a
逻辑推理题常用的解法与解题思路
逻辑推理题常用的解法与解题思路 “逻辑思路”，主要是指遵循逻辑的四大基本规律来分析推理的思路。 【同一律思路】同一律的形式是：“甲是甲”，或“如果甲，那么甲”。它的基本内容是，在同一思维过程中，同一个概念或同一个思想对象，必须保持前后一致性，亦即保持确定性。这是逻辑推理的一条重要思维规律。运用这一规律来解题，我们把它叫同一律思路。 例1. 某公安人员需查清甲、乙、丙三人谁先进办公室，三人口供如下：甲：丙第二个进去，乙第三个进去。乙：甲第三个进去，丙第一个进去。丙：甲第一个进去，乙第三个进去。三人口供每人仅对一半，究竟谁第一个进办公室？ 分析（用同一律思路推理）；这一类问题具有非此即彼的特点。比如甲是否是第一个进办公室只有两种可能：是或非。我们用1表示“是”，0表示“非”，则可把口供列表处理。（1）若甲第一，则依据丙的口供见左表，这个表与甲的口供仅对一半相矛盾；（2）若甲非第一，则依据丙的口供，乙第三个进去，进行列表处理如右表，与“三人口供仅对一半”相符。从而可以判定，丙最先进入办公室。这个问题也可以不列表而用同一律推理。甲的话第一句对，第二句错，则丙第二，乙不是第三，又不是第二，自然乙第一，甲第二，这个结论与丙说的话“半对半错”不符。因此，有甲的第一句错，第二句对。即乙第三个进去，丙不是第二个，自然是第一个。这个结论与乙的话“半对半错”相符：甲不是第三，丙是第一。并且这个结论与丙的话“半对半错”也相符：甲不是第一，乙是第三。在整个思维过程中，我们对三人的话“半对半错”进行了一一验证，直到都符合题目给定的条件为止。 例2. 从前一个国家里住着两种居民，一个叫宝宝族，他们永远说真话；另一个叫毛毛族，他们永远说假话。一个外地人来到这个国家，碰见三位居民，他问第一个人：“请问你是哪个民族的人？”“匹兹乌图。”那个人回答。外地人听不懂，就问其他两个人：“他说的是什么意？”第二个人回答：“他说他是宝宝族的。”第三个人回答：“他说他是毛毛族的。” 请问，第一个人说的话是什么意思？第二个人和第三个人各属于哪个民族？ 分析（用同一律思路思考）：如果第一个人是宝宝族的，他说真话，那么他说的是“我是宝宝族的”。如果这个人是毛毛族的，他说假话，他说的还是“我是宝宝族的”。这就是说，第一个人不管是什么民族的，那句话的意思都是：“我是宝宝族的”。根据这一推理，那么第二个人回答“他说他是宝宝族的”这句话是真的，而从条件可知，说真话的是宝宝族人，因此可以判断第二个人是宝宝族人。不管第一个人是什么民族的，根据前面推理已知他说的话是“我是宝宝族的”，而第三个人回答“他说他是毛毛族的”显然是错的，而说假话的是毛毛族人，因此可以断定第三个人是毛毛族人 我们在分析本题时，始终保持了思维前后的一致性，这就是同一律思路的具体运用。 【不矛盾律思路】不矛盾律的形式是“甲不是非甲”。它的基本内容是：同一对象，在同一时间内和同一关系下，不能具有两种互相矛盾的性质，它是逻辑推理的又一重要规律，运用不矛盾律来推理、思考某些问题的解答，这种思路我们把它叫做不矛盾律思路。 例1.有三个和尚，一个讲真话，一个讲假话，另外一个有时讲真话，有时讲假话。一天，一位智者遇到这三个和尚，他先问左边的那个和尚：“你旁边的是哪一位？”和尚回答说
数理逻辑考试题及答案
“离散数学”数理逻辑部分考核试题答案 --------------------------- ★----------------------------- 一、命题逻辑基本知识（5分） 1、将下列命题符号化（总共4题，完成的题号为学号尾数取4的余，完成1题。共2分） （0）小刘既不怕吃苦，又爱钻研。 解：—p ∧q ,其中，P :小刘怕吃苦；q :小刘爱钻研。 （1）只有不怕敌人，才能战胜敌人。 解：q→-p ,其中，P :怕敌人；q :战胜敌人。 （2）只要别人有困难，老张就帮助别人，除非困难已经解决了。 解：—r→（P→P）,其中，P:别人有困难；q :老张帮助别人；r:困难解决了。 （3）小王与小张是亲戚。 解：p，其中，P:小王与小张是亲戚。 2、判断下列公式的类型（总共5题，完成的题号为学号尾数取5的余，完成1题。共1分） （0）A ：（-（p^q）_；（（P -q）（.p^q））） r （1）B : （P 一9一；P））（r q） （2）C: （P -r）＞（q r） （3）E : p-;（P q r） （4）F ：—（q-；r） r------------------------------------------------------------------------ 解：用真值表判断，A为重言式，B为矛盾式，C为可满足式，E为重言式，F为矛盾式。 3、判断推理是否正确（总共2题，完成的题号为学号尾数取.2的余，完成1题。共2分） （0）设y=2∣x∣，X为实数。推理如下：如y在x=0处可导，则y在x=0处连续。发现y在x=0处连续，所以，y在x=0处可导。 解：设y=2|x|，X为实数。令P: y在x=0处可导，q：y在x=0处连续。由此，P为假，q为真。本题推理符号化为：（p—；q） q—；P。由P、q的真值，计算推理公式真值为假，由此，本题推理不正确。 （1）若2和3都是素数，则6是奇数。2是素数，3也是素数。所以，5或6是奇数。 解：令P:2是素数，q:3是素数，r:5是奇数，S:6是奇数。由此，p=1，q=1，r=1，S=O。本题推理符号化为：（（P q）→ S） P q）→ （r S）。计算推理公式真值为真，由此，本题推理正确。 二、命题逻辑等值演算(5分) 1、用等值演算法求下列公式的主析取范式或主合取范式(总共3题，完成的题号为学号尾数取3的余，完 成1题。共2分) (0)求公式p→ ((q ∧r) ∧(P ∨(―q ∧-r)))的主析取范式。 解：p→((q ∧r) ∧(P ∨(—q ∧-「)))：= 一p∨(q ∧r∧P) ∨(q ∧r ∧一q ∧—r)二一P ∨(q ∧r∧P) ∨0 二(P ∧q∧r) ∨= (一p∧1 ∧1) ∨(q ∧r∧P) 二(—p ∧(q ∨-q) ∧(r ∨-r)) ∨(q ∧r∧P) U (~p ∧(q ∨-q) ∧(r ∨一r)) ∨m7 二(一P ∧—q ∧ F ∨ (一P ∧—q ∧r) ∨ (一P ∧q ∧_r) ∨ (一P ∧q ∧r) ∨m7 m0 ∨m1 ∨m2 ∨m3 ∨m7. (1)求公式一(一(P → q)) ∨(—q → 一P)的主合取范式。 解：一(一(P → q)) (—q →-p)二(P → q) (P →q) U (P → q)
数理逻辑与集合论试卷
2006年的考题 一、A={a,b,c},B={X|a∈X且X?A},求B-A, B-{A}, ∪B, ∩B。 二、A={1,2,3,5,9},R是A上的关系且R={
数理逻辑测试题
1.用真值表判断下列公式的类型（重言式、矛盾式还是普通式）： (1)p→(p∨q∨r) (2)(p→╕p)→╕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) (r s) 2.求下列公式的成真赋值 (1)╕p→q (2)p∨╕q (3)(p∧q)→╕p (4)╕(p∨q)→q 3.求下列公式的成假赋值 (1)╕(╕p∧q)∨╕r (2)(╕q∨r)∧(p→q) (3)(p→q)∧(╕(p∧r)∨p) 4.已知p→(p∨q)是重言式，╕(p→q)∧q是矛盾式，试判断(p→(p ∨q))∧(╕(p→q)∧q)及(p→(p∨q)) ∨(╕(p→q)∧q)的类型。
5.用等值演算法证明下列等值式 (1)p<=>(p∧q)∨(p∧╕q) (2)((p→q)∧(p→r))<=>(p→(p∧r)) (3)╕(p q)<=>(p∨q)∧╕(p∧q) (4)(p∧╕q)∨(╕p∧q)<=>(p∨q)∧╕(p∧q) 6.求下列公式的主析取范式和主和取范式 (1)(p∧q)∨r (2)(p→q)∧(q→r) (3)(p∧q)→q (4)(p q)→r (5)╕(r→p)∧p∧q 7.前提：╕p∨q，╕q∨r，r→s，p 结论：s 根据前提，证明结论 8.根据以下前提：p→(q→r)，q→(r→s)，证明：(p∧r)→s 9.前提：╕(p→q)∧q，p∨q，r→s 结论1：r
结论2：s 结论3：r∨s 证明从此前提出发，推出的结论1，结论2，结论3都是正确的。 10．证明下列各推理 (1)前提：p→(q→r)，p，q 结论：r∨s (2)前提：p→(q→r)，s→p，q 结论：s→r (3)前提：p→╕q，╕r∨q，r∧╕s 结论：╕p