《数学部分第1章 逻辑代数(上)：命题演算》由会员分享，可在线阅读，更多相关《数学部分第1章 逻辑代数(上)：命题演算（32页珍藏版）》请在金锄头文库上搜索。
1、 离散数学教程教案与习题解析 理工学院 段景辉第第 1 1 章章 逻辑代数（上）：命题演算逻辑代数（上）：命题演算1.11.1 逻辑联结词与命题公式逻辑联结词与命题公式1.1.11.1.1 逻辑联结词逻辑联结词否定词否定词(negation)“并非”(not)，用符号 （或 ）表示。设 p 表示一命题，那么p 表示命题 p 的否定。当 p 真时p 假，而当 p 假时p 真。p 读作“并非 p”或“非p” 。用类似表 1.1 的真值表真值表(truth table)规定联结词的意义。表 1.1p p0110合取词合取词(conjunction)“并且”(and)，用符号表示。设 p，q 表示两命
2、题，那么pq 表示合取 p 和 q 所得的命题，即当 p 和 q 同时为真时 pq 真，否则 pq 为假。pq读作“p 并且 q”或“p 且 q” 。合取词的意义和命题 pq 的真值状况可由表 1.2 来刻划。表 1.2p q pq001101010001析取词析取词(disjunction)“或”(or)用符号表示。设 p，q 表示两命题，那么 pq 表示p 和 q 的析取，即当 p 和 q 有一为真时，pq 为真，只有当 p 和 q 均假时 pq 为假。pq读作“p 或者 q” ， “p 或 q” 。析取词的意义及复合命题 pq 的真值状况由表 1.3 描述。表 1.3p q pq0011
3、01010111蕴涵词蕴涵词(implication)“如果，那么”(ifthen)，用符号表示。设离散数学教程教案与习题解析 理工学院 段景辉p，q 表示两命题，那么 pq 表示命题“如果 p，那么 q” ，它常被称作条件命题。当 p 真而 q 假时，命题 pq 为假，否则均认为 pq 为真。pq 中的 p 称为蕴涵前件，q 称为蕴涵后件。pq 的读法较多，可读作“如果 p 则 q” ， “p 蕴涵 q” ， “p 是 q 的充分条件” ， “q是 p 的必要条件” ， “q 当 p” ， “p 仅当 q”等等。数学中还常把 qp，pq，qp 分别叫做 pq 的逆命题，否命题，逆否命题。蕴涵
4、词的意义及复合命题 pq 的真值状况规定见表 1.4。表 1.4pqpq001101011101双向蕴涵词双向蕴涵词(two-way implication)“当且仅当” （if and only if） ，用符号表示之。设 p，q 为两命题，那么 pq 表示命题“p 当且仅当 q” ， “p 与 q 等价” ，即当 p 与 q 同真值时 pq 为真，否则为假。pq 读作“p 双向蕴涵 q” ， “p 当且仅当 q” ， “p 等价于 q” 。由于“当且仅当” “等价”常在其它地方使用，因而用第一种读法更好些。双向蕴涵词的意义及 pq 的真值状况由表 1.5 给出。表 1.5p q pq001
5、1010110011.1.21.1.2 命题公式命题公式定义定义 1.11.1 归纳定义命题公式命题公式（简称公式公式 proposition formula）：（1）命题常元和命题变元是命题公式，也称为原子公式或原子。（2）如果 A，B 是命题公式，那么(A)，(AB)，(AB)，(AB)，(AB)也是命题公式。（3）只有有限步引用条款（1） ， （2）所组成的符号串是命题公式。定义定义 1.21.2 设公式 A 含有命题变元 p1，p2，pn（有时用 A(p1，p2，pn)表示这一离散数学教程教案与习题解析 理工学院 段景辉状况） ，称 p1，p2，pn每一取值状况为一个指派指派(assi
6、gnments)，用希腊字母，等表示，当 A 对取值状况 为真时，称指派弄真弄真 A，或是 A 的弄真弄真指派指派，记为(A) = 1；反之称指派弄假弄假 A，或是 A 的弄假弄假指派指派，记为(A) = 0。1.1.31.1.3 语句形式化语句形式化 将自然语言表述的命题“翻译”成命题公式，常称为语句形式化。语句形式化要注意以下几个方面：要善于确定原子命题，不要把一个概念硬拆成几个概念，例如“弟兄”是一个概念，不要拆成“弟”和“兄” 、 “我和他是弟兄”是一个原子命题。要注意语句的语用，不同的语用有不同的逻辑含义。例如“狗急跳墙”可能说的是一个规律，也可能说的是一个现象。要善于识别自然语言中
7、的联结词（有时它们被省略） 。例如“风雨无阻，我去北京”一句，可理解为“不管是否刮风、是否下雨我都去北京” 。否定词的位置要放准确。需要的括号不能省略；而可以省略的括号，在需要提高公式可读性时亦可不省略。注意“只要，就” “只有，才”的正确理解。因果关系也常常用蕴涵词来表示，这一点是有争议的。语句的形式化的结果未必是唯一的。 练习练习 1.11.1 题解题解1、选择题（1）设 P:我将去镇上，Q:我有时间。命题“我将去镇上，仅当我有时间”符号化为（ ）APQ ； B. QP ； C. PQ ； D. QP.。【答案】：A（2）设 P:张三可以做这件事，Q 李四可以做这件事。命题“张三或李四可以
8、做这件事”符号化为（ ）APQ ； B.PQ； C. PQ ； D. (PQ)【答案】：A（3）设 P:我们划船，Q:我们跑步。命题“我们不能既划船又跑步”符号化为（ ）离散数学教程教案与习题解析 理工学院 段景辉APQ ； B.PQ ； C.(PQ) ； D. PQ【答案】：B（4）下列语句中哪个是真命题（ ）A我正在说谎B. 如果 1+2=3，那么雪是黑的C. 如果 1+2=5，那么雪是黑的D. 严禁吸烟【答案】：C（5）PQ 的逆命题是（ ）A .QP B. PQ C.QP D.PQ【答案】：A（6）下面哪一个命题是命题“2 是偶数或3 是负数”的否定（ ）A2 是偶数或3 不是负数B.
9、 2 是奇数或3 不是负数C. 2 不是偶数且3 不是负数D. 2 是奇数且3 不是负数【答案】：C2、填空题（1）下列句子中，是命题的有 .（a）我是教师。（b）禁止吸烟。（c）蚊子是鸟类动物。（d）上课去！【答案】：（a） ， （c）（2）设 P：我生病，Q：我去学校（a）命题“我虽然生病但我仍去学校”可符号化为 。（b）命题“只有我生病的时候，我才不去学校” 可符号化为 。（c）命题“只要我生病，我就不去学校” 可符号化为 。（d）命题“当且仅当我生病，我才不去学校” 可符号化为 。离散数学教程教案与习题解析 理工学院 段景辉【答案】：（a）PQ；（b）.QP；（c）PQ；（d）PQ（3
10、） “a0”表示 a0 a=0 ；“a 是非负实数”表示 a0 a 是实数（在空格中填上适当的命题联结词） 。【答案】：；（4）在空格中填上表（表 1.6）各列所定义的命题联结词：表 1.6P Q P QP Q0 0110 1101 0001 111【答案】：；（5）P，Q 为两个命题，当且仅当 时，PQ 的真值为 0。【答案】：P 真且 Q 假（6）公式 PQ 的否命题为 ，逆否命题为 。【答案】：PQ； QP3将下列命题形式化：（1）你是博士，但我是硕士。【答案】：可表示为 (pq)， 其中p：你是博士；q：我是硕士（2）我今天或明天去泰山的说法是谣传。【答案】：可表示为 (pq)，其中
11、p：我今天去泰山；q：我明天去泰山（3）如果买不到飞机票，我不去海南岛。【答案】：可表示为pq，其中，p：我买到飞机票，q：我去海南岛（4）只要他出门，他必买书，不管他带的钱多不多。【答案】：可表示为(pqr)(pqr)或 qr，其中 p：他带的钱多，q：他出门，r：他买书。（5）除非你陪伴我或代我雇辆车子，否则我不去。【答案】：可表示为(pq) r，其中 p：你陪伴我，q：你代我雇车，r：我去（6）只要充分考虑一切论证，就可得到正确见解；必须充分考虑一切论证，才能得到正确离散数学教程教案与习题解析 理工学院 段景辉见解。【答案】：可表示为(pq) (qp )或p q，其中p：你充分考虑了一切
12、论证，q：你得到了正确见解（7） 除非你是成年人，否则只要你身高不超过 1 米 3，就能到儿童游乐场玩耍。 r (st)，其中r：你是成年人，s：你身高超过1米3，t: 你到儿童游乐场玩耍（8）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。【答案】：可表示为(qp ) q，其中 p：我懂得希腊文，q：我了解柏拉图（9）侈而惰者贫，而力而俭者富。 （韩非：韩非子显学 ）【答案】：可表示为(pq)r) (pq)r)，其中p：你奢侈，q：你懒惰，r：你贫困（10）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。 （荀况：荀子劝学 ）【答案】：可表示为(pq)
13、(sr) (mno) (mnv)，其中p：骐骥一跃，q：骐骥行十步，r：驽马行千里，s：驽马不断奔跑，m：你雕刻，n：你放弃，o：你将朽木折断，v：你将金石雕刻4根据命题公式的定义和括号省略的约定，判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点（p,q,r,s 为原子命题）：（1） (p) 【答案】： (p) 不是公式（2）(pqr)s【答案】：(pqr)s 不是公式（3）(pq)p【答案】：(pq)p 是公式，其真值表如表1.7所示：表1.7pqpq(pq)p00010110离散数学教程教案与习题解析 理工学院 段景辉10111111（4）p(pq)【答案】：p(
14、pq) 是公式，其真值表如表 1.8 所示（恒真）：表1.8pqpqp(pq)0001011110111111（5）p(pq)q【答案】：p(pq)q 是公式，其真值表如表 1.9 所示（恒真）：表1.9pqpqp(pq)p(pq)q00101011011000111111（6）p(pq)(pq)【答案】：p(pq)(pq) 是公式，其真值表如表 1.10 所示（恒假）：表1.10pqqpqp(pq)pqp(pq)(pq)0011010010101010100101101100（7） (pq) qp离散数学教程教案与习题解析 理工学院 段景辉【答案】： (pq) qp 是公式，其真值表如表 1.11 所示（恒真）：表1.11pq p qpq (pq)qp(pq) ( q p)00110111011010011001100111001001（8） pq (pq)【答案】： pq(pq) 是公式，其真值表如表 1.12 所示（恒真）：表1.12
