离散数学1.1-1.2命题与联结词

1、第一部分 数理逻辑逻辑学是研究思维规律和思维的形式结构的一门学科 。数理逻辑是研究推理的科学，它运用数学的方法研究思维形式和规律，特别是研究数学中的思维形式和规律。 本部分只介绍数理逻辑的两个主要部分：命题逻辑和谓词逻辑。数理逻辑的其他内容，如证明论、模型论、递归论、公理集合论不在本课程范围。1.1 现代逻辑学现代逻辑学求助数学符号化现代逻辑学追随数学公理化现代逻辑学改造数学形式化逻辑发展历史三个阶段初始阶段：1660年代19世纪末将数学应用于逻辑 Aristotle：形式逻辑（主词和谓词逻辑）。 Leibniz：建立直观而又精确的思维演算。 George Boole: 逻辑代数。 De Mo

2、rgan: 关系逻辑。过渡阶段：19世纪末 1940前后, 逻辑应用于数学 非欧几何与公理化方法。 微积分与实数理论，Piano算术。 集合论与数学基础(1900年世界数学家大会) 悖论与第三次数学危机，Hilbert计划。成熟阶段：1930s 1970年,成为数学的独立分支 四个分支： 公理集合论：大基数，连续统问题 递归论（可计算性理论）：Turing机，不可解性 模型论：实数的非标准模型 证明论：超穷归纳法, Gentzen的数论和谐性证明逻辑与计算机科学的联系布尔电路：布尔逻辑。计算理论：可计算性，Turing机，形式语言，自动机，计算复杂性。程序语义与验证技术：Intel bug:

3、5亿美元。程序的自动生成与转换。SQL: 本质上等价于一阶逻辑。Prolog语言：以逻辑演算为基础。LISP语言：以演算为基础。人工智能：非单调推理，缺省推理。信息安全（知道问题）老师手中握有一副牌（黑桃5、4、8、J；红心A、Q、4；方块A、5；梅花K、Q、5、4），我想好一张牌，并将该牌的花色告述学生甲，将该牌的点数告述学生乙。甲说：我敢肯定你不知道这张牌。乙说：那么我现在知道了。甲说：那么我也知道了。请问这张牌是什么牌？先看著名物理学家爱因斯坦出过的一道题： 一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打

4、开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。这时，那两个应试者看到商人头上戴的是一顶红帽子，沉默几秒后其中一个人便喊道：“我戴的是黑帽子。”请问这个人说得对吗？他是怎么推导出来的呢？ 第一章 命题逻辑的基本概念1.1命题与联结词思考题1 命题逻辑中有： *是* *不是*两句话。例如，“高志华是讲师”和“高志华不是讲师”。若其中一句是正

5、确的，那么另一句就一定是不正确的。请你构造出同时为真的两个句子。 2 相传在古代有一个残酷的国王，为了不准别人进入他的领地而制定了一个法规：“凡进入者若讲真话则杀头，若讲假话则淹死”。并要求士兵严格执行上述命令。一天，一个人进来说了一句话，导致士兵无法执行命令。请问这个人说了什么？ 一、命题逻辑主要研究推理过程，而推理过程必须依靠命题来表达。在命题逻辑中，“命题”被看作最小单位。数理逻辑中最基本、最简单的部分。命题和联结词1。什么是命题？命题是陈述客观外界发生事情的陈述句。命题是或为真或为假的陈述句。特征： 陈述句 真假必居其一, 且只居其一.例1 下列句子都是命题4是素数。 是无理数。火星上

6、有水。2050年元旦是晴天。例2 下面的句子不是命题。x大于y，其中x和y是任意的两个数。 大于 吗？请不要吸烟！这朵花真美丽啊！我正在说谎话。是陈述句，但其真值可真可假，不唯一疑问句祈使句感叹句陈述句，悖论自相矛盾的陈述不是命题命题的抽象以p、q、r等表示命题。以1表示真，0表示假。 则命题就抽象为：取值为0或1 符号（p、q、r等）。若p取值1，则表示p为真命题；若p取值0，则表示p为假命题；现实生活中的各种论述和推理，出现的命题多数比 例1 中的命题更加复杂：（1）4是偶数且是2的倍数。（2）武汉不是个小城市。（3）小王或小李考试得第一。（4）如果你努力，则你能成功。（5）三角形是等边三

7、角形，当且仅当三边相等。 原子命题和复合命题原子命题：不能分解为更简单的命题复合命题：由简单命题通过联结词连接而成。 是有理数是不对的。2是偶素数。2或者4是素数。如果2是素数，则3也是素数。2是素数当且仅当3也是素数。二、联结词上述诸如“不”、“如果 则”等连词称为联结词。由联结词和命题连接而成的更加复杂命题称为复合命题；相对地，不能分解为更简单命题的命题称为简单命题。复合命题的真假完全由构成它的简单命题的真假所决定。否定联结词定义1：设p为一个命题, 复合命题“非p”称为p的否定式，记为p， “”称为否定联结词.“p”为真当且仅当p为假。例子1.2中，如果 p： 是有理数，则（1）可表示为

8、pPp0110合取联结词定义2 设p、q为两个命题，复合命题“p而且q”称为p、q的合取式，记为pq，“”称作合取联结词。pq真当且仅当p与q同时真。 例1。2的(2)可记为qr, 其中q代表“2是偶数”, r代表“2是素数”.pqpq000010100111析取联结词定义2 设p、q为两个命题，复合命题“p或者q”称为p、q的析取式，记为pq，“”称作析取联结词。 pq 假当且仅当p与q同时假. 例1。2的(2)可记为qt, 其中q代表“2是素数”, t代表“4是素数”.pqpq000011101111“相容或”与“相异或”自然语言中“或”有两种标准用法, 例1.4（P4）:(1) 张晓静爱

9、唱歌或爱听音乐.(2)张晓静只能挑选202或203房间.(3)张晓静是江西人或安徽人。(1)为“相容或”，(2)(3)为“相异或”。前者可表示为pq，后者却不能。注意：不能见了或就表示为pq。蕴涵联结词定义4 设p、q为命题, 复合命题“如果p, 则q”称为p对q的蕴涵式，记作p q。其中又称p为此蕴涵式的前件，称q为此蕴涵式的后件，“”称为蕴涵联结词。“p q” 假当且仅当p真而q假.pqp q001011100111蕴涵式有时也称为条件式，“如果p，那么q”，“若p，则q”，也称“q是p的必要条件”作为推理“如果p则q”的形式化，显然有p为1，q为0则p q为0p为1，q为1则p q为1但

10、是当p为0时，无论q是0或1，p q 都为1。例如“如果太阳从西边出来，我就不姓张”，这句话怎么都对。逻辑推理研究抽象推理，p与q可以无任何内在联系。等价联结词定义2.5 设p、q为命题, 复合命题“p当且仅当q”称作p、q的等价式, 记作pq, “”称作等价联结词。pq真当且仅当p、q同时为真或同时为假.(p q) (q p) 与 pq 的逻辑关系一样。pqpq001010100111注意上述五个联结词来源于日常使用的相应词汇,但并不完全一致，在使用时要注意：以上联结词组成的复合命题的真假值一定要根据它们的定义去理解, 而不能据日常语言的含义去理解。不能“对号入座”，如见到“或”就表示为“”

11、。有些词也可表示为这五个联结词，如“但是”也可表示为“”。在今后我们主要关心的是命题间的真假值的关系, 而不讨论命题的内容.例1.5将下列命题符号化，并指出各复合命题的真值：（1）如果3+36，则雪是白的。（2）如果3+36，则雪是白的。（3）如果3+36，则雪不是白的。（4）如果3+36，则雪不是白的。解 ： 令p：3+36，p的真值为T。q：雪是白色的，q的真值也为T。(1)到(4)的符号化形式分别为：pq，pq，pq，pq。真值分别为T，T，F，T。 例：将下列命题符号化，并指出各复合命题的真值：以下命题中出现的a是一个给定的正整数：只要a能被4整除，则a一定能被2整除。a能被4整除，仅当a能被2整除。除非a能被2整除，a才能被4整除。除非a能被2整除，否则a不能被4整除。只有a能被2整除，a才能被4整除。只有a能被4整除，a才能被2整除。？（思考）运算优先级约定运算次序：( ) 相同的运算符按从左至右的次序计算圆