第1章-命题逻辑
第一章命题逻辑
1.1第7页
1. 给出下列命题的否定命题： （1）大连的每条街道都临海。
否命题：不是大连的每条街道都临海。 （2）每一个素数都是奇数。
否命题： 并非每一个素数都是奇数。 2. 对下述命题用中文写出语句： （1）()P R Q ?∧→
如果非P 与R ，那么Q 。 （2）Q R ∧ Q 并且R 。
4. 给出命题P Q →，我们把Q P →、P Q ?→?、Q P ?→?分别称为命题P Q →的逆命题、反命题、逆反命题。
（1）如果天不下雨，我将去公园。
解：逆命题：如果我去公园，则天不下雨； 反命题：如果天下雨，则我不去公园；
逆反命题：如果我不去公园，则天下雨了。 （2）仅当你去我才逗留。
解：（此题注意：p 仅当q 翻译成p q →） 逆命题：如果你去，那么我逗留。
反命题：如果我不逗留，那么你没去。 逆反命题：如果你没去，那么我不逗留。 （3）如果n 是大于2的正整数，那么方程n
n n x
y z +=无整数解。
解：逆命题：如果方程n
n n x
y z +=无整数解，那么n 是大于2的正整数。
反命题：如果n 不是大于2的正整数，那么方程n n n
x y z +=有整数解。
逆反命题：如果方程n n n
x y z +=有整数解，那么n 不是大于2的正整数。
7. 给P 和Q 指派真值T ，给R 和S 指派真值F ，求出下列命题的真值。 （1）(()(()()))P Q R Q P R S ?∧∨?∨??→∨?
=(()(()()))T T F T T F F ?∧∨?∨??→∨? =()T F T ?∨→ =T F ∨ =T
（2）()Q P Q P ∧→→
=()T T T T ∧→→
=T T T ∧→ =T T → =T
（3）((()))()P Q R P Q S ∨→∧??∨?
=((()))()T T F T T F ∨→∧??∨? =(())T T F T ∨→? =T T ? =T
（4）()()P R Q S →∧?→
=()()
T F T F →∧?→
=()F F F ∧→
=F
8． 构成下列公式的真值表： （1）()Q P Q P ∧→→
（2）()()()P Q R P Q P R ?∨∧?∨∧∨
（3）()P Q Q P P R ∨→∧→∧?
（4）()P P Q R Q R ?→∧?→∧∨?
9. 使用真值表证明：如果P Q ?为T ，那么P Q →和Q P →都是T ，反之亦然。
P Q ?为T 。故命题得证。
10. 使用真值表证明：对于P 和Q 的所有值，P Q →与P Q ?∨有同样的真值。
11. 一个有两个运算对象的逻辑运算符，如果颠倒其运算对象的次序，产生一逻辑等价命题，则称此逻辑运算符是可交换的。
（1）确定所给出的逻辑运算符哪些是可交换的：∧，∨，→，?。 （2）用真值表证明你的判断。 解：（1）∧，∨，?是可交换的。 （2）真值表如下：
12.设*是具有两个运算对象的逻辑运算符，如果()x y z **和()x y z **逻辑等价，那么运算符*是可结合的。
（1）确定逻辑运算符∧，∨，→，?哪些是可结合的？ （2）用真值表证明你的判断。 解：（1）,,∧∨?是可结合的。 （2）真值表如下：
13. 令P表示命题“苹果是添的”，Q表示命题“苹果是红的”，R表示命题“我买苹果”。试将下列命题符号化：
（1）如果苹果甜而红，那么我买苹果。
（2）苹果不是甜的。
（3）我没买苹果，因为苹果不红也不甜。
∧→
解：（1）P Q R
?
（2）P
?→?∧?
（3）R P Q
14．解：如何我问你是你是不是总说谎的，你会说是吗？回答不是的都是说实话的，回答是的都是说谎的。
1.2第15页
1. 指出下面命题公式哪些是重言式、永假式或可满足式。
解：
（1）重言式
∨?=
P P T
（2）永假式
P P F
∧?=
（3）重言式
→??=
P P T
()
（4）重言式
P Q P Q P Q P Q T
?∧??∨?=?∨???∨?=
()()()()
（5）重言式
?∨??∧?=?∧???∧?=
()()()()
P Q P Q P Q P Q T
（6）重言式
()()P Q Q P →??→?
=()()P Q Q P T ?∨?∨?= （7）重言式
(()())()P Q Q P P Q →∧→?? =()()P Q P Q T ???= （8）重言式 ()()P Q R P Q P R ∧∨→∧∨∧
=(()())()P Q P R P Q P R ∧∨∧→∧∨∧
=()()P Q P R P Q P R ∧∨∧→∧∨∧
=T
（9）重言式
P P Q ∧?→ =F Q T →= （10）可满足式 P Q Q ∨?→
=()P Q Q P Q Q ?∨?∨=?∧∨，当Q 为真时公式为真，Q 为假时公式为假。故为可
满足式。 （11）重言式
P P Q P P Q T →∨=?∨∨=
（12）重言式
()P Q P P Q P P Q P T ∧→=?∧∨=?∨?∨= （13）可满足式
()()P Q P P Q ∧???的真值表如下：
（14）可满足式 (()())(()())P Q R S P R Q S →∨→→∨→∨ =()()P Q R S P R Q S ?∨∨?∨→?∧?∨∨
=(()())(()())P R Q S P R Q S ?∨?∨∨→?∧?∨∨
当Q 或S 有一个为真时公式为真；当Q 和S 均为假时，若P 和R 真值相同时，公式
为真；真值不同时，公式为假。故公式是可满足式。
2. 写出与下面给出的公式等价并且仅含有联接词∧与?的最简公式。 （1）((()))P Q R P ??→∨
(((()))((())))(()(()))(())()()
P Q R P Q R P P P Q R P Q R P P T Q R P P Q R P P P P Q R ??→→∨∧→∨→???∨?∨∨∧?∨∨→??∧∧?∧?∨??∧?∧?∨??∧??∧∧?
（2）(())()P Q R P R ∨→→∨
(())()(())()(())()()(()())()()()
()P Q R P R P Q R P R P Q R P R P Q P R P R
P Q R P R P Q R R P R P Q R P Q R ??∨∨→∨???∨∨∨∨?∨∧?∨∨?∨∨∧?∨∨?∨∧?∨∨?∨∨∧?∨∨?∨∨???∧?∧?
（3）P Q R ∨∨? ()P Q R ???∧?∧ （4）()P Q R P ∨?∧→ (())()()P Q R P P Q R P P Q R P Q R ?∨??∧∨?∨∨?∨?∨∨????∧?∧
（5）()P Q P →→ ()()P Q P P Q P T
?→?∨??∨?∨? 3. 写出与下面的公式等价并且仅含联结词∨和?的最简公式。 （1）()P Q P ∧∧?
P Q P
F
?∧∧??
（2）(())P Q Q P Q →∨?∧?∧ ()()
P T P Q
T P Q
P Q P Q ?→∧?∧?∧?∧??∧??∨?
（3）()P Q R P ?∧?∧?→ ()
()()()()
P Q R P P Q R P Q P P Q R F P Q R P Q R ??∧?∧∨??∧?∧∨?∧?∧??∧?∧∨??∧?∧??∨∨? 4. 使用常用恒等式证明下列各式，并给出下列各式的对偶式。 （1）()()P Q P Q P ??∨?∨??∨? 证明：
离散数学第一章命题逻辑知识点总结
数理逻辑部分 第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 1．下列句子中那些是命题？ (1) 4是无理数. (2) 2+5＝8. (3) x+5＞3. (4) 你有铅笔吗？ (5) 这只兔子跑得真快呀！ (6) 请不要讲话！ (7) 我正在说谎话. 解：(1)(2)是命题。(7)是悖论。 2．判断下列语句是不是命题。若是，给出命题的真值。（1）北京是中华人民共和国的首都。 （2）陕西师大是一座工厂。 （3）你喜欢唱歌吗？ （4）若7+8＞18，则三角形有4条边。 （5）前进！ （6）给我一杯水吧！ 解：(1)(2)(4)是命题，真值分别是1,0,1。 3．写出下列命题的否定式： （1）存在一些人是大学生； （2）所有的人都是要死的； （3）并非花都有香味。 解：(1) 不存在一些人是大学生。 （2）并非所有的人都是要死的； （3）花都有香味。 4．设P：我生病，Q：我去学校，符号化下列命题。 (1) 只有在生病时，我才不去学校。 (2) 若我生病，则我不去学校。 (3) 当且仅当我生病时，我才不去学校。 (4) 若我不生病，则我一定去学校。 解：（1）Q→P （2）P→Q （3）P Q （4）P→Q 5．设p：李平聪明，q：李平用功。符号化下列命题。 (1) 李平既聪明又用功。 (2) 李平虽然聪明，但不用功。 (3) 李平不但聪明，而且用功。
(4) 李平不是不聪明，而是不用功。 (5) 张三或李四都可以做这件事。 解：（1）p ∧q （2）p ∧q （3）p ∧q （4）(p)∧q ，或p ∧q （5）设p ：张三可以做这件事，q ：李四可以做这件事。命题符号化为p ∨q 。 6．设p ：天下雨，q ：我骑车上班。符号化下列命题。 (1) 如果天不下雨，我就骑车上班。 (2) 只要天不下雨，我就骑车上班。 (3) 只有天不下雨，我才骑车上班。 (4) 除非天下雨，否则我就骑车上班。 (5) 如果天下雨，我就不骑车上班。 解：（1）p →q （2）p →q （3）q →p ，p →q （4）q →p ，p →q （5）p →q 7．将下列命题符号化。 (1) 小王是游泳冠军或百米赛跑冠军。 解：设p ：小王是游泳冠军，q ：小王是百米赛跑冠军。 原语句化为p ∨q 。 (2) 小王现在在宿舍或在图书馆。 解：设p ：小王在宿舍，q ：小王在图书馆。原语句化为p ∨q 。 (3) 选小王或小李中的一人当班长。 解：设p ：选小王当班长，q ：选小李当班长。 但因为p,q 不可能同时为真, 故应符号化为： (p ∧q)∨(p ∧q) (4) 如果我上街，我就去书店看看，除非我很累。 解：设ｐ：我上街，ｑ：我去书店看看，ｒ：我很累。 原语句化为ｒ→(ｐ→ｑ)或(ｒ∧ｐ)→ｑ。 (5) 小丽是计算机系的学生，她生于1982或1983年，她是三好生。 解：设p ：小丽是计算机系的学生，q ：小丽生于1982年，r ：小丽生于1983年，s ：小丽是三好生。原语句化为p ∧(q ∨r)∧s 。 (6) 我去镇上，当且仅当我有时间且天不下雪。 解：设p:我去镇上，q:我有时间，r:天下雪。原语句化为p ?q ∧r 。 (7) 我若去镇上则我有时间，并且我若有时间则去镇上。 解：设p:我去镇上，q:我有时间。原语句化为p ?q 。 (8) 我有时间或我去镇上，此话不对。 解：设p:我去镇上，q:我有时间。原语句化为(p ∨q)。 8.求下列命题公式的真值表。 (1)()p p q ∧→? (2)()()p q q p ?→→→?
第一章 命题逻辑
第一章命题逻辑 1.什么叫做命题？是陈述句子都是命题吗？请举例说明之。 2.命题的真值有几种？为什么？并说明这些真值的定义。 3.判断下面句子哪些是命题。如果是命题，说出它的真值。 1．离散数学是计算机科学与技术专业的理论基础。 2．2不是素数。 3．x＋y＝6 4．明天有雨吗？ 5．火星上也有过人类。 4.什么叫做简单命题？什么叫做复合命题？如何表示复合命题？ 5.命题逻辑中定义了几个逻辑联结词？都用什么符号表示？分别叫做什么名称？在自然语言中都表达什么含义？ 6.填空：P、Q是命题变元，则 P∧Q的真值为真，当且仅当( ) P∨Q的真值为假，当且仅当（） P∨Q的真值为假，当且仅当( ) P→Q的真值为假，当且仅当（） P?Q的真值为真，当且仅当( )
8.填空 已知P∧Q为T，则P为( )，Q为( )。 已知P∨Q为F，则P为( )，Q为( )。 已知P为F，则P∧Q为( )。 9.填空 已知P为T，则P∨Q为( )。 已知P∨Q为T，且P为F ，则Q为( )。 10.填空 已知P为F，则P→Q为( )。 已知Q为T，则P→Q为( )。 11.填空 已知P为T，P→Q为T，则Q为( )。 已知?Q为T, P→Q为T，则P为( )。 已知P?Q为T，P为T , 则Q为( )。 12.填空 已知P?Q为F，P为T , 则Q为( )。 P?P 的真值为( )。 P→P 的真值为( )。 13.设P,Q,R代表的意义如下： P：苹果是甜的。 Q：苹果是红的。 R：我买苹果。 试用自然语言说明下面复合命题所表示的含义。 1．(P∧Q)→R 2．(?P∧?Q)→?R 3．R?(P∧Q)
第1章-命题逻辑
第一章命题逻辑 1.1第7页 1. 给出下列命题的否定命题： （1）大连的每条街道都临海。 否命题：不是大连的每条街道都临海。 （2）每一个素数都是奇数。 否命题： 并非每一个素数都是奇数。 2. 对下述命题用中文写出语句： （1）()P R Q ?∧→ 如果非P 与R ，那么Q 。 （2）Q R ∧ Q 并且R 。 4. 给出命题P Q →，我们把Q P →、P Q ?→?、Q P ?→?分别称为命题P Q →的逆命题、反命题、逆反命题。 （1）如果天不下雨，我将去公园。 解：逆命题：如果我去公园，则天不下雨； 反命题：如果天下雨，则我不去公园； 逆反命题：如果我不去公园，则天下雨了。 （2）仅当你去我才逗留。 解：（此题注意：p 仅当q 翻译成p q →） 逆命题：如果你去，那么我逗留。 反命题：如果我不逗留，那么你没去。 逆反命题：如果你没去，那么我不逗留。 （3）如果n 是大于2的正整数，那么方程n n n x y z +=无整数解。 解：逆命题：如果方程n n n x y z +=无整数解，那么n 是大于2的正整数。 反命题：如果n 不是大于2的正整数，那么方程n n n x y z +=有整数解。 逆反命题：如果方程n n n x y z +=有整数解，那么n 不是大于2的正整数。 7. 给P 和Q 指派真值T ，给R 和S 指派真值F ，求出下列命题的真值。 （1）(()(()()))P Q R Q P R S ?∧∨?∨??→∨? =(()(()()))T T F T T F F ?∧∨?∨??→∨? =()T F T ?∨→ =T F ∨ =T （2）()Q P Q P ∧→→ =()T T T T ∧→→ =T T T ∧→ =T T → =T （3）((()))()P Q R P Q S ∨→∧??∨? =((()))()T T F T T F ∨→∧??∨? =(())T T F T ∨→? =T T ? =T （4）()()P R Q S →∧?→
第一章命题逻辑习题教学教材
第一章命题逻辑习题
第一章 命题逻辑 一、选择 1、下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好 看呀！。 2、下列语句不是命题的有（ ）。 A 、 x=13； B 、离散数学是计算机系的一门必修课； C 、鸡有三只 脚； D 、太阳系以外的星球上有生物； E 、你打算考硕士研究生吗？ 3、下列语句是命题的有（ ）。 A 、 明年中秋节的晚上是晴天； B 、0>+y x ； C 、0>xy 当且仅当x 和y 都大于0； D 、我正在说谎。 4、下列各命题中真值为真的命题有（ ）。 B 、 2+2=4当且仅当3是奇数；B 、2+2=4当且仅当3不是奇 数； C 、2+2≠4当且仅当3是奇数； D 、2+2≠4当且仅当3不是奇数 5、下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 6、下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、 P Q P ?→)( 7、下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则 B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 8、命题逻辑演绎的CP 规则为（ ）。
B 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎 出C ； D 、设)(A Φ是含公式A 的命题公式，A B ?，则可用B 替换)(A Φ中 的A 。 R Q P →→)(的合取范式为（ ）。 A 、R Q P ∨?∧)( ； B 、)()(R Q R P ∨?∧∨ ； C 、 ) ()()()()()(R Q P R Q P R Q P R Q P R Q P R Q P ∧?∧?∨∧∧?∨∧?∧∨∧∧∨?∧?∧∨∧?∧ D 、)()()()(R Q P R Q P R Q P R Q P ∨?∨?∧∨?∨∧∨?∨∧∨∨。 9、下列符号串是合式公式的有（ ） A 、Q P ?； B 、Q P P ∨?； C 、)()(Q P Q P ?∨∧∨?； D 、 )(Q P ??。 10、下列等价式成立的有（ ）。 A 、P Q Q P ?→??→； B 、R R P P ?∧∨)(； C 、 Q Q P P ?→∧)(； D 、R Q P R Q P →∧?→→)()(。 11、若n A A A Λ21,和B 为wff ，且B A A A n ?∧∧∧Λ21则（ ）。 A 、称n A A A ∧∧∧Λ21为 B 的前件； B 、称B 为n A A A Λ21,的有效结论 C 、当且仅当F B A A A n ?∧∧∧∧Λ21； D 、当且仅当 F B A A A n ??∧∧∧∧Λ21。 12、A ，B 为二合式公式，且B A ?，则（ ）。 A 、 B A →为重言式； B 、**B A ?； C 、B A ?； D 、**B A ?； E 、B A ?为重言式。 13、下述命题公式中，是重言式的为（ ）。
第一章命题逻辑习题
第一章 命题逻辑 一、选择 1、 下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 2、下列语句不是命题的有（ ）。 A 、 x=13； B 、离散数学是计算机系的一门必修课； C 、鸡有三只脚； D 、太阳系以外的星球上有生物； E 、你打算考硕士研究生吗？ 3、下列语句是命题的有（ ）。 A 、 明年中秋节的晚上是晴天； B 、0>+y x ； C 、0>xy 当且仅当x 和y 都大于0； D 、我正在说谎。 4、下列各命题中真值为真的命题有（ ）。 B 、 2+2=4当且仅当3是奇数；B 、2+2=4当且仅当3不是奇数； C 、2+2≠4当且仅当3是奇数； D 、2+2≠4当且仅当3不是奇数 5、下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 6、下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 7、下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 8、命题逻辑演绎的CP 规则为（ ）。 B 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ； D 、设)(A Φ是含公式A 的命题公式，A B ?，则可用B 替换)(A Φ中的A 。 R Q P →→)(的合取范式为（ ）。 A 、R Q P ∨?∧)( ； B 、)()(R Q R P ∨?∧∨ ； C 、 ) ()()()()()(R Q P R Q P R Q P R Q P R Q P R Q P ∧?∧?∨∧∧?∨∧?∧∨∧∧∨?∧?∧∨∧?∧
第1章命题逻辑练习题
第一章命题逻辑练习题 一、填空题 1 公式()()p q p q ∧?∨?∧的成真赋值为 2 公式p p q r →∨∨的成假赋值为 3 设A 为任意的公式，B 为重言式，则A B ∨的类型为 4 设B 为含命题变项,,p q r 的矛盾式，则(())B p q r ∧?→的公式类型是 5 设公式A 含命题变项,,p q r ，已知A 的成真赋值为000,011，100,110，则A 的 主析取范式为 6 设公式B 含命题变项,,,p q r s ，已知B 的成假赋值为0010，0100,1010,1001， 则B 的主合取范式为 7 已知公式A 是重言式，B 是矛盾式，则A B →的公式类型是 ， A B ??的公式类型是 二、将下列命题符号化 1. 小王既不怕吃苦，又很爱钻研。 2 2与4都是素数，这是不对的。 3 “2或4是素数，这是不对的”是不对的。 3 只能选张晓或王雷其中一个当班长。 4 托尔斯泰是俄罗斯人或英国人。 5 只要别人有困难，老王就帮助别人，除非困难解决了。 6 如果天不下雨且我有时间，我就去逛街。 三、判断下列公式的类型 1 (())()p q p r q ∧?→∧∧； 2 (()(()()))p q p q p q r ??→∧?∨?∧∨； 3 ()()p q p q ?∨?→?? 四 求下列公式的主析取范式和主合取范式 1 ((()))p p q q r ∨?→∨?→ 2 ()()p q q r p r ∨→∧→∧? 3 ()()q p p q →∧?∧ 4 ()p p q r →∨?∨ 五、 已知公式A 含命题变项,,p q r ，公式的成真赋值为011,100,101，求公式