《离散数学第一章命题逻辑-1-4节.ppt》由会员分享，可在线阅读，更多相关《离散数学第一章命题逻辑-1-4节.ppt（68页珍藏版）》请在三一办公上搜索。
1、1,离 散 数 学,河南工业大学,信息科学与工程学院,第一章 命题逻辑,2,第一篇 数理逻辑,什么是逻辑（学）？研究人类思维的科学。研究思维形式及思维过程。公元前四世纪亚里斯多德工具论奠定了逻辑学的理论基础。中国最早的一部逻辑专著墨经也创造了一个比较完整的逻辑体系。,辩证逻辑,形式逻辑,3,什么是数理逻辑？,数理逻辑是用数学的方法研究逻辑。所谓“数学方法”：就是引进一套符号体系的方法。用数学理论、手段和技巧找出研究对象内在联系的数学表达式及其规范的方法，包括使用符号和公式，已有的数学成果和方法，特别是使用形式的公理方法。数理逻辑即引进一套符号体系的方法来研究概念、判断和推理，即对符号进行判断和
2、推理。所以数理逻辑也称为“符号逻辑”。数理逻辑属于形式逻辑。,它与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切联系。,数理逻辑的主要内容,数理逻辑内容丰富，但其主要包括“两个演算”加“四论”，即：逻辑演算。包括命题演算和谓词演算证明论。主要研究数学理论系统的相容性（即不矛盾、协调性）的证明。递归论（能行性理论）。自从电子计算机发明后，迫切需要在理论上弄清计算机能计算哪些函数。递归论研究能行可计算的理论，它为能行可计算的函数找出各种理论上精确化的严密类比物。模型论。主要是对各种数学理论系统建立模型，并研究各模型之间的关系以及模型与系统之间的关系。公理集合论。主要研究在消除已知集合论
3、悖论的情况下，用公理方法把有关集合的理论充分发展下去。,5,1、“甲在河南工业大学上学”,2、“甲在郑州上大学”,如果“甲在河南工业大学上学”真的，则显然“甲在郑州上大学”也是真的。,推理形式“如果甲在河南工业大学上学，则 甲在郑州上大学”；甲在河南工业大学上学；则可推出甲在郑州上大学。,符号化为：P表示“甲在河南工业大学上学”；Q表示“甲在郑州上大学”；P Q表示“如果甲在河南工业大学上学，则 甲在郑州上大学”。,推理形式可以表示为P Q为真；P为真；则可推出Q为真。可以抽象地写成(P Q)P Q,3、“如果甲在河南工业大学上学，则甲在郑州上大学”是成立的,例：,请根据下面事实，找出凶手：1
4、.清洁工或者秘书谋害了经理。2.如果清洁工谋害了经理，则谋害不会发生在午夜前。3.如果秘书的证词是正确的，则谋害发生在午夜前。4.如果秘书的证词不正确，则午夜时屋里灯光未灭。5.午夜时屋里灯灭了。问：谁是凶手？,秘书谋害了经理。,第一篇 数理逻辑,主要研究内容,第一章 命题逻辑研究的内容,命题逻辑也称为命题演算 研究以命题为基本单位构成的前提和结论之间的可推导关系。,1-1 命题与命题的真值1-2 联结词1-3 命题公式及翻译1-4 真值表与等价公式1-5 重言式与蕴含式1-6 其它联结词()1-7 对偶与范式1-8 命题推理理论,第一章 命题逻辑 学习要求,10,1-1.命题与命题的真值,本
5、节主要讨论四个问题：命题的概念命题的真值原子命题与复合命题命题的表示,11,一、命题的概念,陈述句：陈述一个事实或一个说话人的看法，句末用句号。祈使句：要求或者希望别人做什么事或者不做什么事时用的句子，句末用句号或感叹号。疑问句：提出问题的句子，句末用问号。感叹句：带有浓厚感情的句子，句末用感叹号。,请看下面给出的两个陈述句：,（1）2是个素数。（2）雪是黑色的。这两个陈述句都表示对事件性质的判断。第一句话表示的判断是正确的，第二句话表示的判断是错误的。像(1),(2)这样能够唯一确定所表达的判断是正确的还是错误的陈述句称为命题。,13,一、命题的概念,命题是一个能判断是真的或是假的陈述句。命
6、题一定是陈述句，但并非一切陈述句都是命题。真值：一个命题的值叫真值。一个命题的真值有两个：“真”或“假”真值为真:一个命题所作的判断与客观一致,则称该命题的真值为真,记作T(True)，真命题。真值为假:一个命题所作的判断与客观不一致,则称该命题的真值为假,记作F(False)，假命题。命题是具有唯一真值 的陈述句。命题可以是真的，或者是假的，但不能同时为真又为假。,例子,例1-1.1,(1)中华人民共和国的首都是北京。(2)大于4的偶数均可分解为两个质数的和(哥德巴赫猜想)。(3)所有质数都是奇数。(4)雪是黑色的。,真命题,真命题,假命题,假命题,判断语句是否为命题要注意的问题：,1、目前
7、无法确定真值，但从本质而言，真值存在的语句是命题。例：(1)别的星球上有生物。(2)2046年世界杯在中国举行。2、真值因时因地而异的判断性陈述句是命题。例：(1)2011年的元旦是晴天。(2)今天下雨。3、含有未确定内容的代词，不能判断真假的语句不是命题。例：(1)1+101=110。当1和101是二进制数，语句为真，为十进制数，语句为假。(2)x+y10。4、悖论不是命题。语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。例：我正在说慌。,如何判断一个句子是否为真命题？,1、是否为陈述句？2、其真值是否唯一？3、其真值是否为真。,命题,分子命题,原子命题,二、原子命题与复合命题,
8、简单命题(原子命题)：由最简单的陈述句构成的命题(该句再不能分解成更简单的句子了)。如：我是一位学生。复合命题(分子命题)：由若干个原子命题使用适当的联结词所组成的新命题。我是一位学生。他是一位教师。我是一位学生和他是一位教师，这些简单命题之间是通过如“或者”、“并且”、“不”、“如果.则.”、“当且仅当”等这样的关联词和标点符号复合而构成一个复合命题。,18,三、命题的表示,大写的带或不带下标的英文字母，如：A,A3,P例如：P：今天下雨。Q：张三在唱歌。表示命题的符号。表示确定命题的命题标识符。命题常量真值确定，是命题。可表示任意一个（原子或复合）命题的命题标识符，就称为命题变元。命题标识
9、符只表示任意命题的位置标志。注意：命题变元可以表示任意的命题，所以真值不确定，命题变元不是命题。当命题变元P用一个特定命题去取代或者是直接赋给命题变元真值“T”或“F”时，才能确定P的真值，该过程称对P进行指派。例：若P是命题变元，P：北京是中国的首都。（指派P为命题北京是中国的首都）,命题标识符：,表示方法：,对命题变元作指派(给命题变元一个解释)：,命题常量：,命题变元：,19,1-2 联结词,复合命题的构成：是用“联结词”将原子命题联结起来构成的。归纳自然语言中的联结词，定义了六个逻辑联结词，分别是：(1)否定“”(2)合取“”(3)析取“”(4)异或“”(5)条件“”(6)双条件“”,
10、20,一、否定“”一元运算,符号，读作：“非”，“否定”。设P为命题，在P的前面加否定词，变为P，P读作：“非P”或“P的否定”。P为一新的命题，定义：用真值表表示。P是P的否定式。例1-2.1 P：2是素数。（T）P：2不是素数。（F）P：上海是一个大城市。（T）P：上海不是一个大城市。或：上海是个不大的城市。（严格讲不建议）。,21,一、否定“”一元运算,P：咱班每个同学都大于18岁。P？咱班每个同学不都大于18岁咱班每个同学都不大于18岁。用真值表来判断。,P P,T F,F T,P：咱班每个同学不都大于18岁。不是每个同学不大于18岁。至少有一个同学不大于18岁。,对量化命题的否定，需
11、要同时对动词和量化词要加以否定。,二、合取“”二元运算,符号：设P，Q为两个命题，PQ 称为P与Q的合取，读作：“P合取Q”，“P与（并且）Q”，“P与Q的合取”等。P和Q的合取为一个复合命题。定义：由真值表给出。PQ的真值为真，当且仅当P和Q的真值均为真。,P和Q是互为独立的，地位是相等，P和Q的位置可以互换而不会影响PQ 的结果。,23,二、合取“”二元运算,相应的日常用语：“并且”、“既又”，“不但(仅)而且”，“虽然但是”，“尽管还”，例1-2.2 P：今天下雨。Q：明天下雨。PQ：今天下雨而且明天下雨（或者：今天与明天都下雨，或者：这两天都下雨）。P:我们去食堂吃饭。Q:教室里有三块
12、黑板。PQ:我们去食堂吃饭并且教室里有三块黑板。注：复合命题中的原子命题之间无需有一般逻辑意义上的关联。,下列语句不是合取联结词组成的命题,1）张丽和王芳是好朋友。2）他打开箱子然后（而后）拿出一件衣服来。,三、析取“”、异或“”二元运算1.析取“”,符号：设P，Q为两个命题，P Q 称为P与Q的析取，读作：“P或者Q”、“P析取Q”等。P和Q的析取为一个复合命题。定义：见真值表PQ的真值为F，当且仅当P与Q均为F。,区分“可兼或”与“不可兼或”,例1-2.3灯泡有故障或者线路有故障。今晚写字或看书。今天下雨或打雷。以上例子为可兼或。析取为可兼或。,2.异或“”,P Q的真值为F，当且仅当P与
13、Q的真值相同。例1-2.4他通过电视看足球比赛或到体育馆看体育比赛。他乘火车去郑州或乘汽车去郑州。以上例子为不可兼或。,四、双条件“”,符号：设P，Q为两个命题，P Q 读作：“P当且仅当Q”、“P是Q的充分必要条件”等。P和Q的双条件为一个复合命题。定义：见真值表PQ的真值为真，当且仅当P与Q的真值相同。例1-2.4：P：ABC是等边三角形。Q：ABC是等角三角形。PQ：ABC是等边三角形当且仅当它是等角三角形。,例：下面均为双条件联结词,平面上二直线平行，当且仅当这二直线不相交。春天来了，燕子飞回来了。（春天来了当且仅当燕子飞回来了）2+2=4当且仅当雪是白的。,P Q中，P和Q的地位是平
14、等的，P、Q交换位置不会改变真值表的值。,30,五、条件“”,符号：设P，Q为两个命题，P Q 读作：“P蕴含Q”、“如果P则Q”、“P条件Q”、“P是Q的充分条件”、“Q是P的必要条件”、“P仅当Q”、“Q当且P”等。P Q为一个复合命题。P：称为前件、条件、前提、假设，Q：称为后件、结论。定义：见真值表。,PQ的真值,PQ的真值为假，当且仅当P为真，Q为假。注意：当前件P为假时，PQ为T。,结论：P Q中，P和Q的地位是不平等的，P、Q交换位置将会改变真值表的值。,前件为假，PQ为真。后件为真，PQ为真。,一位父亲对儿子说：“如果星期天天气好，就一定带你去动物园。”问：在什么情况下父亲食言
15、？父亲的可能情况有如下四种：(1)星期天天气好，带儿子去了动物园；(2)星期天天气好，却没带儿子去动物园；(3)星期天天气不好，却带儿子去了动物园；(4)星期天天气不好，也没带儿子去动物园。,示例,没有食言,没有食言,没有食言,食言,33,书例：,前提与结论有联系的：如果某动物为哺乳动物，则它必胎生。如果我得到这本小说，那么我今夜就读完它。前提与结论可以没有联系的：如果雪是黑的，那么太阳从西方出来。,举例：,令：P：天气好。Q：我去公园。,1.如果天气好，我就去公园。,PQ,2.只要天气好，我就去公园。,PQ,3.天气好，我就去公园。,PQ,4.只有天气好，我才去公园。,Q P,5.仅当天气好
16、，我才去公园。,Q P,6.我去公园，仅当天气好。,Q P,7.除非天气好，否则我不去公园。,P Q,Q P,P Q，这类的联结词还有“只要P就Q”“因为P,所以Q”“P仅当Q”“只有Q才P”“除非Q,否则非P”等等,本节小结,要熟练掌握这六个联结词在自然语言中所表示的含义以及它们的真值表的定义。,均为真,至少一个为真,相同为真,不同为真,取反,1.复合命题的真值只取决于构成它们的原子命题的真值和命题联结词的定义，而与它们的内容、含义无关，与联结词所连接的两个原子命题之间是否有关系无关。2.，和具有可交换性，而，没有。,本节小结,联结词是命题与命题之间的联结，而非单纯的名词、数词等地联结。数理
17、逻辑中的联结词是自然语言中联结的逻辑抽象，应具有准确的逻辑含义和严格的单义性，使用时也应忠实地按定义使用。设P：天不下雨，Q：草木枯黄则 P：天下雨PQ：天不下雨且草木枯黄；PQ：天不下雨或草木枯黄；PQ：如果天不下雨，那么草木枯黄；PQ：天不下雨当且仅当草木枯黄。,37,本节小结,特别要注意“或者”的二义性，即要区分给定的“或”是“可兼取的或”还是“不可兼取的或”。特别要注意“”的用法，PQ的逻辑关系它既表示“充分条件”也表示“必要条件”，即要弄清哪个作为前件，哪个作为后件。PQ的真值 PQ的灵活的叙述方法作业：p8 3，4，5,38,练习：填空,1、已知PQ为T，则P为()，Q为()。2、
18、已知PQ为F，则P为()，Q为()。3、已知P为F，则PQ为()。4、已知P为T，则PQ为()。5、已知PQ为T，且P为F，则Q为()。6、已知PQ为F，则P为()，Q为()。7、已知P为F，则PQ为()。8、已知Q为T，则PQ为()。9、已知 PQ为F，则P为()，Q为()。10、已知P为T，PQ为T，则Q为()。11、已知Q为T,PQ为T，则P为()。12、已知PQ为T，P为T,则Q为().13、已知PQ为F，P为T,则Q为().14、PP 的真值为().15、PP 的真值为()。,析取和异或示例,指出下列命题中的“或”是析取还是异或。今晚我去看演出或在家里看电视现场转播。他是一百米冠军或
19、跳高冠军。派小王或小赵出差去上海。派小王或小赵中的一个出差去上海。2、3为析取，1、4为异或,40,1-3 命题公式及翻译,一.命题公式1、原子命题公式：单个命题变元或常元。2、命题演算合式公式(wff)(well formed formulas)简称命题公式（分子命题公式）：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。但并不是由这些符号任意组成的符号串都是命题公式。什么样的符号串才能表示命题公式？,41,1-3 命题公式及翻译,一.命题公式合式公式可以解释为合法的命题公式之意，也称之为命题公式，有时也简称公式。定义1-3.1：单个的命题变元是个合式公式。若A是合式公式，则A
20、是合式公式。若A和B是合式公式，则(AB)，(AB)，(AB)和(AB)都是合式公式。当且仅当有限次地应用，所得到的含有命题变元、联结词和括号的符号串是合式公式。上述定义方法称为递归定义法，递归法定义是离散数学中常用的方法。,基础,归纳,界限,例如,P，(PQ)，(PR)，(PQ)R)是合式公式(P Q)(Q)，PR，(PQ)R,应是二元运算符,括号不匹配,不是合式公式,的位置,命题公式,约定：（1）为方便，最外层括号可以不写，上面的(PQ)，(PR)，(PQ)R)合式公式可以写成：PQ，PR，(P Q)R（2）五个联结词的优先次序：否定合取析取条件双条件，凡符合此优先次序的，括号可省略。P(
21、Q R)可以写成PQR（3）相同的联结词按出现的先后次序运算，凡符合此要求的，括号可省去。P(Q R)可以写成PQ RP(Q R)不可以写成P Q R,命题公式的子公式,定义 如果X是合式公式A的一部分，且X本身也是一合式公式，则称X为公式A的子公式。如：A：(P Q)R中P、Q、R、P Q,45,二、命题符号化(即翻译),就是用命题公式的符号串来表示给定的命题。也称为翻译命题。命题符号化的基本步骤：如何将自然语言符号化注意：,1)分析出各原子命题，并逐个符号化；2)找出各联结词，把原子命题逐个联结起来。,简单命题复合命题句子段落篇章,1)必要时可以进行改述，即改变原来的叙述方式，但要保证表达
22、意思一致。2)需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。3)要注意语句的形式化未必是唯一的。,46,三、命题符号化例子,分析并符号化，强调在进行命题符号化以前，必须明确含义，删除歧义，这是命题翻译的关键之点。教材P10-P11例题1：（自学）例题2：（自学）例题3：（自学）例题4：（自学）例题5：（自学）例题6：（自学）,举例,例1.说离散数学无用且枯燥无味是不对的。例2.如果小张与小王都不去，则小李去。,首先用字母表示原子命题：P：离散数学是无用的。Q：离散数学是枯燥无味的。该命题符号化为：(PQ),首先用字母表示原子命题：P：小张去。Q：小王去。R：小李去。该
23、命题符号化为：(PQ)R,48,三、命题符号化,例3.人不犯我，我不犯人；人若犯我，我必犯人。,首先用字母表示原子命题：P：人犯我。Q：我犯人。该命题符号化为：(PQ)(PQ)或写成：PQ,49,三.命题符号化,例4.若天不下雨，我就上街；否则在家。首先用字母表示原子命题：P：天下雨。Q：我上街。R：我在家。该命题符号化为：(PQ)(P R)。注意：中间的联结词一定是“”，而不是“”因为原命题表示：“天不下雨时我做什么，天下雨我又做什么”的两种作法，其中有一种作法是假的，则我说的就是假话，所以中间的联结词一定是“”。如果写成(PQ)(P R)，就表明两种作法都是假的时候，我说的才是假话。这显然
24、不对。,命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。,50,练习,上海到北京的14次列车是下午五点半或六点半开除非你努力，否则你将失败P:你努力,Q:你成功,异或,QP或PQ,51,1-4 真值表与等价公式,一.命题公式的真值表定义1-4.2设A是命题公式，给所有命题变元指派一组真值，称为对A的一个赋值，也称为一个解释。将公式A在所有赋值之下的真值列成一张表，称为A的真值表。,构造真值表的步骤,找出给定命题形式中的所有命题变元，列出所有可能的赋值;按计算从前到后的顺序列出命题公式的子公式；计算各子公式的值，直至最后计算
25、命题形式的值。,命题变元,P Q P PQ T T F T T F F T F T T T F F T F,命题公式,命题子公式,例如命题 公式(PQ)的真值表如下所示：,53,命题变元的取值组合,由于对每个命题变元可以有两个真值(T,F)被指派，所以有n个命题变元的命题公式 A(P1,P2,Pn)的真值表有2n行。为了有序地列出公式的真值表，在对命题变元做指派时，可以按照二进制数的次序列表。补充：关于“二进制数”见下页。,54,关于二进制数简介：,为了有序地列出A(P1,P2,Pn)的真值表，可以将F看成0，将T看成1，按照二进制数111,1110,00010,0001,000(即十进制的2
26、n 1,2n 2,.,2,1,0)的次序进行指派列真值表。,十进制数 0 1 2 3 4 5 6 7 8 9,二进制 0 1 10 11 100 101 110 111 1000 1001,注:有效数字前加0不影响数值,如000=0，001=1，010=10，011=11,55,关于二进制数简介：,如A(P,Q)的真值表可按照如下次序指派：11(T,T)，10(T,F)，01(F,T)，00(F,F)如A(P,Q,R)的真值表可按照如下次序指派：111(T,T,T),110(T,T,F),101(T,F,T),100(T,F,F),011(F,T,T),010(F,T,F),001(F,F,T
27、),000(F,F,F),56,关于二进制数简介：,例如列出P(QR)的真值表,F,F,T,T,57,二、等价公式,1、例子 看下面三个公式的真值表从真值表可以看出，不论对P、Q作何指派，都使得PQ、PQ和QP的真值相同，即它们的真值表完全相同，表明它们之间彼此等价或逻辑相同。,58,2、定义1-4.2,A、B是含有命题变元P1,P2,Pn的命题公式，如不论对P1,P2,Pn作任何指派，都使得A和B的真值相同，则称之为A与B等价，记作AB。,显然 PQPQQP,59,首先，GH的结果仍是一个命题公式。G H 的结果不是命题公式。双条件词“”是一种命题联结词，公式GH是命题公式，其中“”是一种逻
28、辑运算，GH的结果仍是一个命题公式。逻辑等价“”则是描述了两个公式G与H之间的一种逻辑等价关系，G H表示“命题公式G等价于命题公式H”，G H 的结果不是命题公式。其次，如果要求用计算机来判断命题公式G、H是否逻辑 等价，即G H那是办不到的，然而计算机却可“计算”公式GH是否是永真公式。,“”与“”的区别,60,3、重要的等价公式,对合律 PP(双否律)幂等律 PPP PPP 结合律(PQ)R P(QR)(PQ)R P(QR)交换律 PQQP PQQP,下面给出一些常用的等值式，其中很多是通常所说的布尔代数或逻辑代数的主要组成部分。,61,二、等价公式,分配律 P(QR)(PQ)(PR)P
29、(QR)(PQ)(PR)吸收律 P(PQ)P P(PQ)P德-摩根定律(PQ)PQ(PQ)PQ 同一律 PFP PTP 零律 PTT PFF 互补律 PPT PPF,P：今天下雨，Q：今天刮风，(PQ)：今天下雨或刮风的否定，P Q：今天不下雨且今天不刮风，(P Q)：今天下雨且刮风的否定，P Q：今天不下雨或今天不刮风，,62,二、等价公式,P43 PQPQ PQQP PQ(PQ)(QP)PQ(PQ)(PQ)PQ(PQ)(PQ)(PQ)R(PQ)R(PQ)(PR),63,4、等价公式的证明方法-怎样证明公式是等价的,方法1：用真值表。方法2：用重言式证明（见下一节）方法3：用公式的等价变换。
30、定义1-4.3 如果X是合式公式A的一部分，且X本身也是一合式公式，则称X为公式A的子公式。如：A：(P Q)R中P、Q、R、P Q,64,定理1-4.1 置换定律（等价代换定理）：,设X是合式公式A的子公式，Y是一命题公式，若XY，如果将A中的X用Y来置换，则所得到公式B与公式A等价，即AB。从定理可见，一个命题公式A，经过多次的置换，所得到的新公式与原公式等价。等价代换定理的用途。1、验证两个命题公式等价。2、化简命题公式。3、判断命题公式的类型。（见第五节）,65,等价代换定理用于证明公式的等价,例题1.求证吸收律 P(PQ)P证明 P(PQ)(PF)(PQ)(同一律)P(FQ)(分配律
31、)PF(零律)P(同一律),66,等价代换定理用于证明公式的等价,例题2.求证(PQ)(PQ)P证明(PQ)(PQ)(PQ)(PQ)(公式E16)(PQ)(PQ)(摩根定律)(PQ)(PQ)(对合律)P(QQ)(分配律)PT(互补律)P(同一律),公式E16：PQPQ,67,补充：等价代换定理用于化简公式,化简语句：“不会休息的人也不会工作，没有丰富知识的人也不会工作”。解：设P：某人会工作，Q：某人会休息，R：某人有丰富的知识 语句符号化为：(QP)(RP)(QP)(RP)(Q P)(R P)P(QR)P(QR)与语句“工作得好的人一定会休息并且有丰富的知识”，具有相同的逻辑含义。,公式E16：PQPQ,68,练习,作业题：第12页：（5）、（7）第17页：（1）a)、d)第18页：（7）b)、d)，（8）,
