首页数学离散数学离散数学 04 第3章-命题逻辑(上).pptx

04 第3章-命题逻辑(上).pptx

页数:129页文件大小:1.74 MB来源: 离散数学ppt课件

本课件从逻辑学与数理逻辑的发展历程讲起,界定命题与真值的判定标准,系统介绍常用联结词与命题符号化方法,并给出命题公式的类型判定、真值表构造与等值演算思路。

命题逻辑(上)章节封面页,标示离散数学课程与本章主题:逻辑与数理逻辑、命题与联结词、命题公式与真值表
第3章命题逻辑(上)标题页,位于命题逻辑(上)章首导览部分
命题逻辑(上)本章学习内容导览页,列出逻辑与数理逻辑、命题与联结词、命题公式与真值表等小节
查看本课件的文字版(共 129 页,供检索与复制)

第1页:命题逻辑(上) 课件封面

命题逻辑(上)课件封面

离散数学 Discrete Mathematics,本章为命题逻辑(上)。

第2页:第3章命题逻辑(上)

第3章命题逻辑(上)

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第3页:命题公式与真值表

命题逻辑(上)本章学习内容

  • 逻辑与数理逻辑
  • 命题与联结词
  • 命题公式与真值表

第4页:逻辑与数理逻辑

逻辑与数理逻辑

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第5页:逻辑与数理逻辑

逻辑的基本知识数理逻辑及其发展历程数理逻辑与计算机

第6页:逻辑学逻辑学--是一门研究思维形式和思维

规律的科学,包含:辩证逻辑:研究人的思维中的辩证法。例如:用全面的和发展的观点观察事物;具体问题具体分析;实践是检查事物正误的唯一标准;等等。形式逻辑:研究人的思维的形式和一般规律。本课程只关心形式逻辑。

第7页:人类的思维规律人类的思维过程

:通过学习掌握概念和判断,然后进行推理,即:概念判断推理推理:由若干个已知的判断(前提),推出新的判断(结论)的思维过程。正确的思维:概念清楚,判断正确,推理合乎逻辑

第8页:逻辑推理实例

公安人员审查一件盗窃案,已知的事实如下:甲或乙盗窃了录音机;若甲盗窃者,则作案时间不会发生在午夜前;若乙的证词正确,则午夜时屋里的灯光未灭;若乙的证词不正确,则作案时间发生在午夜前;午夜时屋里的灯光灭了。问:盗窃者是谁?

第9页:逻辑推理实例

逻辑推理实例

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第10页:学习逻辑的目的

各门科学都是在特殊领域的思维推理活动,故逻辑是一切科学的公共基础.逻辑思维能力是学习、工作乃至日常生活中的重要能力.

第11页:逻辑与数理逻辑

逻辑的基本知识数理逻辑及其发展历程数理逻辑与计算机

第12页:古典逻辑亚里士多德的三段论(syllog

ism)从两个前提推出一个结论的逻辑论证形式:1.大前提(major premise)人都是两足动物2.小前提(minor premise)希腊人都是人3.结论(conclusion)希腊人都是两足动物

第13页:数理逻辑数理逻辑的创始人德国数学家莱布尼

茨1646-1716英国数学家布尔1815-1864德国数学家弗雷格1848-1925

第14页:莱布尼茨Gottfried

Wilhelm Leibniz (1646-1716)首先使用“数理逻辑”这个术语Leibniz’s Dream:把推理归结为(符号)计算.提出“思维演算”的思想:“发生争论时我们可以简单地说:让我们计算一下吧,看谁正确.”

第15页:逻辑与数理逻辑

布尔George Boole (1815-1864)1847年的论文:逻辑的数学分析:论演绎推理的演算法.发明了布尔代数(逻辑代数,命题代数,布尔逻辑),初步实现了Leibniz梦想。布尔代数亦可解释成集合代数,开关代数,是计算机数字逻辑的基础。附注:Augustus de Morgan (1806-1871)几乎同时独立地做出重要贡献.

第16页:逻辑与数理逻辑

弗雷格Friedrich Ludwig Gottlob Frege (1848-1925)1879年的重要著作:概念文字:一种模仿算术语言构造的纯思维的形式语言是第一个公理化谓词逻辑系统是自Aristotle以来逻辑的最重要进展基本实现了Leibniz梦想

第17页:数理逻辑的概念用数学方法

研究演绎推理的一门数学学科数学方法——通过引进一整套形式化符号系统的方法。因此,数理逻辑有时候也称为符号逻辑数理逻辑的构成——一套符号体系+一组运算规则

第18页:数理逻辑的内容数理逻辑包括

:命题逻辑、谓词逻辑、公理化集合论、递归论、模型论、证明论本课程只讨论“命题逻辑”和“谓词逻辑”

第19页:命题逻辑命题逻辑也称命题演算,或语句逻辑

  • 。研究内容:
  • 研究以命题为基本单位构成的前提和结论之间的可推导关系
  • 研究什么是命题?
  • 研究如何表示命题?
  • 研究如何由一组前提推导一些结论?

第20页:逻辑与数理逻辑

逻辑的基本知识数理逻辑及其发展历程数理逻辑与计算机

第21页:数理逻辑与软件程序=算法

+数据算法=逻辑+控制

第22页:数理逻辑与硬件命题逻辑数字逻辑与门电路计

算机组成原理

第23页:命题逻辑(上) 本章小结

命题逻辑(上)小结

本节内容到此结束,谢谢大家!

第24页:命题公式与真值表

命题逻辑(上)本章学习内容

  • 逻辑与数理逻辑
  • 命题与联结词
  • 命题公式与真值表

第25页:命题与联结词

命题与联结词

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第26页:命题与联结词

命题的基本概念命题的运算联结词命题的符号化与应用

第27页:命题的概念

命题是一个或真或假的陈述句,但不能既真又假。确定命题语句真值的几点说明:1、时间性2、区域性3、标准性

第28页:命题举例(1)太阳是圆的

  • ;
  • 成都是一个旅游城市;
  • 北京是中国的首都;
  • 这个语句是假的;
  • 1+1=10;
  • x+y>0;
  • 我喜欢踢足球;
  • 3能被2整除;
  • 地球外的星球上也有人;
  • 中国是世界上人口最多的国家;

第29页:命题举例(12)把门关上

  • ;
  • 滚出去!
  • 你要出去吗?
  • 今天天气真好啊!

注意:一切没有判断内容的句子都不能作为命题,如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。

第30页:小结命题一定是陈述句

,但并非一切陈述句都是命题。命题的真值有时可明确给出,有时还需要依靠环境、条件、时间、实际情况才能确定其真值。

第31页:命题真值(Truth

Values)的表示:真:T、1;假:F、0命题的符号表示:大写英文字母:P、Q、R、…带下标的大写字母:A1、A2、A3、…数字:[1]、[2]、[3]、…命题的表示

第32页:简单命题(原子命题)例题

简单命题(原子命题):由最简单的陈述句构成的命题(该句不能再分解成更简单的句子)。

例:2是个素数。复合命题(分子命题):由若干个原子命题构成的命题。

例:四川不是一个国家命题的种类

第33页:命题与联结词

命题的基本概念命题的运算联结词命题的符号化与应用

第34页:联结词的概念

命题可以通过逻辑联结词(逻辑运算)构成新的命题——复合命题。复合命题的真值依赖于其中简单命题的真值。

第35页:联结词举例例题

联结词举例

例:(1)期中考试,张三没有考及格。(2)其中考试,张三和李四都考及格了。(3)期中考试,张三和李四中有人考了90分。(4)如果张三能考90分,那么李四也能考90分。(5)张三能考90分,当且仅当李四也能考90分。

第36页:五个常用联结词

:Negation(NOT)否定词∧:Conjunction(AND)合取词∨:Disjunction(OR)析取词:Implication(if–then)蕴涵词:Biconditional(if and only if)等价词

第37页:联结词“”称为否定词,表示“…不成立”P

3737联结词“”称为否定词,表示“…不成立”P:今天是星期二P:今天不是星期二P读着:“非P”当P为假时,非P为真;当P为真时,非P为假“非”运算

第38页:命题否定的真值表如下

3838命题否定的真值表如下:¬PPFTTF“非”运算

第39页:“与”运算

3939“与”运算联结词“”称为合取词,表示逻辑“与”运算;“”相当于自然语言中的“并且”,“与”的含义,但是又和自然语言中的“与”有所不同。P:小王能唱歌;Q:小王能跳舞。P∧Q:小王能歌善舞。当且仅当P和Q都为真时,PQ才为真

第40页:当且仅当P和Q都为真时

4040当且仅当P和Q都为真时,PQ才为真PQQPTTTFFTFTFFFF“与”运算

第41页:“(可兼)或”运算

联结词“”称为析取词,表示可兼或当且仅当P和Q都为假,PQ为假P:李明在教室。Q:米卢是个好教练。P∨Q:李明在教室或米卢是个好教练。

第42页:P∨Q的真值为F

,当且仅当P与Q均为FPQQPTTTTFTTTFFFF“(可兼)或”运算

第43页:“蕴涵”运算蕴涵(条件)“”

:若P则Q例:P表示:缺少水分。Q表示:植物会死亡。PQ:如果缺少水分,植物就会死亡。P是前提,Q是结论

第44页:当且仅当P为真且Q为假时

,PQ为假PQQPTTTFFTTTFTFF“蕴涵”运算

第45页:“”既表示充分条件也表示例题

注意:“”既表示充分条件也表示必要条件,它决定了哪个作为前件,哪个作为后件。

例:令:P:天气好。Q:我去公园。1.如果天气好,我就去公园。(充分)2.只要天气好,我就去公园。(充分)3.仅当天气好,我才去公园。(必要)4.只有天气好,我才去公园。(必要)命题1、2写成:PQ命题3、4写成:QP“蕴涵”运算

第46页:命题与联结词

4646“”:等价联结词PQ(P当且仅当Q):当p和q有着相同的真值时,pq为真)PQQPTTTFFTFTFTFF“等价”运算

第47页:小结设命题P,Q表示

4747小结设命题P,Q表示任意两个命题,则最常见的命题联结词有:真值结果记法读法复合命题记号联接词3.析取P或者QP与Q的析取PQP∨Q=1P=1或Q=12.合取∧P并且QP与Q的合取P∧QP∧Q=1P=1且Q=11.否定┐非PP的否定┐P┐P=1P=04.蕴涵→若P,则QP蕴涵QP→QP→Q=0P=1,Q=0↔5.等价P当且仅当QP等价于QP↔QPQ=1P=1,Q=1或P=0,Q=0

第48页:命题与联结词

4848小结P↔QP→QP∨QP∧Q┐PP Q110010 0011010 1001001 0111101 1设命题P,Q表示任意两个命题,则有:

第49页:命题与联结词

命题的基本概念命题的运算联结词命题的符号化与应用

第50页:命题符号化

1.首先要明确给定命题的含义。2.对于复合命题,找联结词,用联结词断句,分解出各个原子命题。3.设原子命题符号,并用逻辑联结词联结原子命题符号,构成给定命题的符号表达式。

第51页:若干要点联结词与自然语言之间的对应并非一

一对应

第52页:符号化下列命题说离散例题

例题

例:符号化下列命题说离散数学无用且枯燥无味是不对的。P:离散数学是有用的。Q:离散数学是枯燥无味的。该命题可写成:(P∧Q)人不犯我,我不犯人;人若犯我,我必犯人。P:人犯我。Q:我犯人。该命题可写成:(PQ)∧(PQ)或写成:PQ

第53页:符号化下列命题(1)例题

5353例题

例:符号化下列命题(1)四川不是人口最多的省份;(2)王超是一个德智体全面发展的好学生;(3)教室的灯不亮可能是灯管坏了或者是停电了;(4)如果周末天气晴朗,那么学院将组织我们到石象湖春游;(5)两个三角形全等当且仅当三角形三边对应相等。

第54页:符号化下列命题(1)例题

5454例题

例:符号化下列命题(1)除非明天不下雨且不下雪,否则我将不去学校;(2)只要明天不下雨或不下雪,我就去学校;(3)只有明天不是雨夹雪,我才去学校;(4)明天上午我将雨雪无阻一定去学校。

第55页:符号化下列命题⑴除非例题

5555例题

例:符号化下列命题⑴除非你陪伴我或代我叫车子,否则我将不出去。⑵如果你陪伴我并且代我叫辆车子,那么我将出去。⑶如果你不陪伴我或不代我叫辆车子,那么我将不出去。

第56页:联结词的应用

5656联结词的应用联结词“∧”、“∨”、“┐”同构成计算机的与门、或门和非门电路是相对应的,从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。

第57页:用复合命题表示例题

5757

例:用复合命题表示如下图所示的开关电路:设P:开关P闭合;Q:开关Q闭合。P∧QP∨QP应用实例

第58页:用复合命题表示例题

5858

例:用复合命题表示如下图所示的逻辑电路PQPQP

解:设P:输入端P为高电位,Q:输入端Q为高电位,则“与门”对应于P∧Q“或门”对应于P∨Q“非门”对应于P应用实例

第59页:逻辑难题一个岛上住着两类例题

5959

例:逻辑难题一个岛上住着两类人:骑士和流氓。骑士说的话都是实话,而流氓只会说谎。如果碰到两个人A和B,如果A说:“B是骑士”,B说:”我们两个不是一类人”。请判断:A、B两人到底是流氓还是骑士?应用实例

第60页:泥巴孩子难题父亲让两个孩例题

6060

例:泥巴孩子难题父亲让两个孩子(一个男孩,一个女孩)在后院玩,并让他们不要把身上搞脏。然而,在玩的过程中,两个孩子都在额头上沾了泥。孩子们回来后,父亲说“你们当中至少有一个人额头上有泥”,然后他问每一个孩子“你知道你额头上有没有泥吗?”同样的问题问两遍。假设每个孩子都可以看到对方的额头上是否有泥,但不能看见自己的额头,孩子们将会怎样回答呢?假设两个孩子都很诚实并且都同时回答每一次提问。应用实例

第61页:命题逻辑(上) 本章小结

命题逻辑(上)小结

本节内容到此结束,谢谢大家!

第62页:命题公式与真值表

命题逻辑(上)本章学习内容

  • 逻辑与数理逻辑
  • 命题与联结词
  • 命题公式与真值表

第63页:命题公式与真值表

命题公式与真值表

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第64页:命题公式与真值表

命题公式的基本概念命题公式的基本类型命题公式的等值演算命题公式的应用

第65页:命题变元如果命题标识符表示

6565命题变元如果命题标识符表示一个具体、确定的命题,称为命题常元。如果命题标识符表示任意一个命题,称为命题变元。命题是能判断真假的陈述句。命题变元代表任意的命题,其真值是不确定的,它的变域是集合{T,F}(或{0,1})。

第66页:命题公式与真值表

6666命题公式把命题常元,命题变元按照一定的逻辑顺序和规则,用命题联结词连接起来就构成了命题演算的合式公式,也叫命题公式。

第67页:命题公式的定义按下列规则

  • 6767命题公式的定义按下列规则构成的符号串称为命题演算的合式公式,也称为命题公式,简称公式。
  • 单个命题变元和常元是合式公式。
  • 如果A是合式公式,那么¬A是合式公式。
  • 如果A和B是合式公式,那么(A∧B)、(A∨B)、(A→B)和(A↔B)是合式公式。
  • 当且仅当有限次地应用了
  • 、
  • 、
  • 所得到的符号串是合式公式。

第68页:命题公式的定义上面的定义

  • 6868命题公式的定义上面的定义给出合式公式定义的方法称为归纳定义,它包括三部分:基础、归纳、界限其中
  • 是基础,
  • 和
  • 是归纳,
  • 是界限。以后将多次出现这种形式的定义。

第69页:命题公式举例例题

6969命题公式举例

例:下列符号串是合式公式:¬(p∨q),¬(p∨q),(p→(p∨¬q)),(((p→q)∧(q→r))↔(s↔t))

例:下列符号串不是合式公式:(p→q)→(∧q),(p→q,(p∧q)→q)

第70页:一些约定为方便

7070一些约定【约定】为方便,最外层括号可以不写,合式公式可以写成:P∧Q,PR,(P∨Q)∧R【约定】逻辑联接词优先级:¬、∧、∨、→、此时P∧QR也是合式公式

第71页:试用符号形式例题

7171例题

例:试用符号形式写出下列命题:(1)虽然今天天气晴朗,老陈还是不来;

解:设P:今天天气晴朗, Q:老陈要来,则有:P∧┐Q;(2)除非你陪伴我或代我叫车子,否则我将不出去;

解:设P:你陪伴我; Q:你代我叫车子; R:我出去。则有:R→P∨Q或┐P∧┐Q→┐R;

第72页:命题公式与真值表的定义

7272公式的解释

定义
设P1,P2,…,Pn是出现在公式G中的所有命题变元,指定P1,P2,…,Pn一组真值,例如(0,1, …,1),则称这组真值为对公式G的一个解释或赋值,记为I

第73页:赋值类型例题

7373赋值类型若指定的赋值使G的真值为T,则称这个赋值为G的成真赋值,若指定的赋值使G的真值为F,则称这个赋值为G的成假赋值。

例:给公式(p∨q→r)的赋值赋值011是指p=0,q=1,r=1,它是该公式的成真赋值;赋值110是指p=1,q=1,r=0,它是该公式的成假赋值。

第74页:真值表的概念若公式

7474真值表的概念若公式G中有n个不同的命题变元,则该公式应有2n个不同的解释。将公式G在其所有可能解释下的真值情况列成的表,称为G的真值表。

第75页:真值表的概念在命题公式

7575真值表的概念在命题公式G中,对G的每一个赋值,就确定了G的一个真值,把这些所有的真值汇列成表,称该表为命题公式G的真值表。(PQ)∨QPQPQPTTFTTTTFFTTTTTFFFTFF

第76页:真值表举例求下面公式例题

7676真值表举例

例:求下面公式真值表:G=(P→(PQ)∧R)∨Q其中,P、Q、R是G的所有命题变元。

第77页:真值表的说明

7777真值表的说明设P1,P2,…,Pn为命题公式P中命题变元,对于命题变元每一种真值指派的可能组合,都能唯一确定P的真值(即有2的n次幂种分布)。为有序列出公式的真值表,在对命题变元做指派时,可按二进制数次序列表。

第78页:真值表的说明

7878真值表的说明为有序列出G(P1,P2,…,Pn)的真值表,可以将F看成0,将T看成1,按照二进制数00…0, 00…01, 00…010, …,11…10, 11…1(即十进制的0,1,2,…. ,2n-1)的次序进行指派列真值表。如G(P,Q)的真值表可按照如下次序指派:00(F,F),01(F,T),10(T,F),11(T,T)如G(P,Q,R)的真值表可按照如下次序指派:000(F,F,F), 001(F,F,T), 010(F,T,F), 011(F,T,T)100(T,F,F), 101(T,F,T), 110(T,T,F), 111(T,T,T)

第79页:构造命题公式例题

7979例题

例:构造命题公式¬p∨q的真值表,并求成真赋值和成假赋值。

解:命题公式¬p∨q的真值表下表所示。00,01,11是成真赋值,10是成假赋值。¬ppq¬p∨q0011011110001101

第80页:构造命题公式例题

8080例题

例:构造命题公式(p∧q)∨(¬p∧¬q)的真值表,并求成真赋值和成假赋值。

解:命题公式(p∧q)∨(¬p∧¬q)的真值表如下表所示。00,11是成真赋值,01,10是成假赋值。pqp∧q¬p¬q¬p∧¬q(p∧q)∨(¬p∧¬q)0001111010100010001001110001

第81页:列出P(QR)的真值例题

8181例题

例:列出P(QR)的真值表P(QR)QRRQPTTFFF000TTTFF001TFFTF010TTTTF011TTFFT100TTTFT101FFFTT110TTTTT111

第82页:命题公式与真值表

命题公式的基本概念命题公式的基本类型命题公式的等值演算命题公式的应用

第83页:公式的分类求列公式例题

8383公式的分类

例:求列公式的真值表:G1=(P→Q)→P;G2=(P→Q)∧P;G3=(P∧Q)(P→Q)。

第84页:公式的分类从这三个真值表可以看到

8484公式的分类从这三个真值表可以看到:公式G1对所有可能的解释具有“真”值公式G3对所有可能的解释均具有“假”值公式G2则具有“真”和“假”值

第85页:公式的分类公式G称为永真公式

8585公式的分类公式G称为永真公式(重言式),如果在它的所有解释之下都为“真”。公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G称为可满足式,如果它不是永假的。

第86页:公式的分类

8686公式的分类如果A,B是永真式(永假式),则(A∧B)、(A∨B)、(AB)和(AB)也都是永真式(永假式)。

第87页:公式的分类1)永真式G的否定G是矛盾式

8787公式的分类1)永真式G的否定G是矛盾式;矛盾式G的否定G是永真式。2)永真式一定是可满足式;可满足式不一定是永真式3)可满足式的否定不一定是矛盾式三种特殊公式之间的关系:

第88页:公式的分类三种特殊公式之间的关系

公式的分类三种特殊公式之间的关系

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第89页:写出下列公式例题

8989例题

例:写出下列公式的真值表,并验证其公式是永真式、永假式、可满足公式。(1)G1=(P→Q)(P∨Q);(2)G2=(PQ)((P→Q)∨(Q→P));(3)G3=(P→Q)∨Q。

第90页:命题公式与真值表

命题公式与真值表

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第91页:命题公式与真值表

命题公式的基本概念命题公式的基本类型命题公式的等值演算命题公式的应用

第92页:观察下列真值表PQ(P∧Q)∨(¬P∧¬

Q)PQ¬P∨QQPTTTTFFFFTTTFFFFFFTTTTTTT是否发现什么问题?¬P∨Q=PQ?(P∧Q)∨(¬P∧¬Q)=PQ?公式的等值关系

第93页:命题公式A与B等价或等值的定义

公式等值的定义

命题公式A与B等价或等值
A、B是含有命题变元P1,P2,…, Pn的命题公式,如不论对P1, P2, …, Pn作任何指派,都使得A和B的真值相同,则称之为命题公式A与B等价或等值,记作AB。显然有:¬P∨QPQ(P∧Q)∨(¬P∧¬Q)PQ

第94页:等值的性质可以证明,命题公式

的等值关系有如下性质:(1)自反性,即对任意命题公式A,AA(2)对称性,即对任意命题公式A和B,若AB,则BA(3)传递性,即对任意命题公式A,B和C,若AB,BC,则AC(4)如果A(P1,P2,…,Pn)B(P1,P2,…,Pn),则:A(P1,P2,…,Pn)B(P1,P2,…,Pn)

第95页:A(P,Q)P→Q例题

例题

例:A(P,Q)P→Q ; B(P,Q)P∨Q则有:A(P,Q)B(P,Q)A(P,Q)P→QB(P,Q)P∨Q可见:A(P,Q)B(P,Q)

第96页:根据等值关系的定义例题

例题

例:根据等值关系的定义,用真值表证明p→(q→p)¬p→(p→¬q)pq¬p¬qq→pp→(q→p)p→¬q¬p→(p→¬q)00111111011001111001111111001101

第97页:命题公式与真值表的定理与性质

等值关系的判定

定理:命题公式A、B具有等值关系的充分必要条件是命题公式AB是永真式。

证明:(1)若AB,则A、B有相同的真值,即AB永为T.(2)若AB为重言式,则AB永为T,故A、B的真值相同,即AB

第98页:与的区别“”是一种逻辑运算

,命题公式GH的结果仍是一个命题公式。“”表示两个命题公式之间的逻辑等值关系,GH表示“命题公式G与命题公式H等值”,GH不是命题公式。此外,如果用计算机直接判断命题公式G、H是否逻辑等价或等值(即GH),是办不到的。但是,计算机可通过“计算”公式GH是否为永真式,来判别是否有:GH。

第99页:证明公式例题

例题

例:证明公式G1=(PQ)与公式G2=(P→Q)∧(Q→P)之间逻辑等价。【证】根据定理,只需判定公式G3=(PQ)((P→Q)∧(Q→P))为永真公式。

第100页:基本等值式

等值演算法证明两个命题公式之间等值或逻辑等价的另外一种方法叫做等值演算法。基本思路是:首先用真值表证明一组基本等值式,然后再它们为基础进行命题公式之间的等值演算。

第101页:基本等值式

基本等值式

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第102页:基本等值式

基本等值式

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第103页:基本等值式

基本等值式

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第104页:基本等值式

以上共24个等值式都可用真值表证明。下面仅验证德摩根律:¬(A∨B)¬A∧¬BA∨BAB¬A¬B¬A∧¬B¬(A∨B)0011101011001010010101100010

第105页:命题与集合

命题与集合

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第106页:∪、∩与∨、∧

∪、∩与∨、∧

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第107页:代入定理

代入定理

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第108页:代入定理

例:设G(P, Q)=(P∧(P→Q))→Q,证明公式G是一个永真公式。另有两个公式:H(P, Q)=P∨¬Q; S(P,Q)=PQ进一步验证代入定理的正确性。

解:由真值表易证G是一个永真公式。将H和S代入G中得到新公式G'为:G'(P, Q)= G(H, S)=(H∧(H→S))→S=((P∨¬Q)∧(P∨¬Q))→ (PQ)))→(PQ)由真值表易证G'是一个永真公式。

第109页:代入定理

替换定理

定理:设G1是G的子公式,H1是任一命题公式,在G中凡出现G1处都以H1替换后得到新的命题公式H,若G1H1,则GH。熟记24个基本等值公式理解代入定理和替换定理

第110页:公式的等值演算利用公式

的等值演算,可完成如下工作:

第111页:公式的等值演算利用公式

的等值演算,可完成如下工作:

第112页:公式的等值演算利用公式

的等值演算,可完成如下工作:

第113页:求证吸收律P∧(P∨例题

例题

例:求证吸收律P∧(P∨Q)P【证】(P∧(P∨Q)(P∨F)∧(P∨Q) (同一律)P∨(F∧Q) (分配律)P∨F (零律)P (同一律)

第114页:求证(P∨Q)→(P例题

例题

例:求证(P∨Q)→(P∧Q)P【证】(P∨Q)→(P∧Q)(P∨Q)∨(P∧Q) (常用等值式)(P∧Q)∨(P∧Q) (摩根定律)(P∧Q)∨(P∧Q) (对合律)P∧(Q∨Q) (分配律)P∧T (互补律)P (同一律)

第115页:命题公式与真值表例题

例题

例:化简(P∧Q)→(P∨(P∨Q))

解:原公式(P∧Q)∨((P∨P)∨Q) (常用等值式)(P∧Q)∨(P∨Q) (对合律,幂等律)(P∧Q)∨(Q∨P) (交换律)((P∧Q)∨Q)∨P (结合律)Q∨P (吸收律)

第116页:命题公式与真值表

命题公式的基本概念命题公式的基本类型命题公式的等值演算命题公式的应用

第117页:应用举例

1171171、试证语句:“不会休息的人也不会工作,没有丰富知识的人也不会工作”,与语句“工作得好的人一定会休息并且有丰富的知识”,具有相同的逻辑含义。分析:设P:某人会工作;Q:某人会休息;R:某人有丰富的知识,则有:(Q→P)∧(R→P)P→(Q∧R)用真值表或等值演算法易证这两个公式等值。应用举例

第118页:应用举例

1181182-1利用基本等价关系,化简下列电路图RPSQPSPQRP应用举例

第119页:应用举例

119119解:上述电路图可描述和化简为:(1)(P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S))((P∧Q∧(R∨S))∧(P∧(R∨S))P∧Q∧(R∨S);SRQP应用举例

第120页:应用举例

120120&&≥1≥1&TSRQP2-2利用基本等价关系,化简下列电路图应用举例

第121页:应用举例

121121解:上述电路图可描述和化简为:((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T)(P∨Q∨S)∧(P∧S∧T) = (P∨Q∨S)。PSQ≥1应用举例

第122页:应用举例

1221223、将下面程序语言进行化简。If A then if B then X else Y else if B then X else YTFFTFTStartAXYEndBB解:执行X的条件为:(A∧B)∨(A∧B)执行Y的条件为:(A∧B)∨(A∧B)应用举例

第123页:应用举例

123123执行X的条件可化简为:(A∧B)∨(A∧B)B∧(A∨A)B执行Y的条件可化简为:(A∧B)∨(A∧B)B∧(A∨A)BTXYEndStartBF程序可简化为:If B then X else Y应用举例

第124页:应用举例

1241244、一家航空公司,为了保证安全,用计算机复核飞行计划。每台计算机能给出飞行计划正确或有误的回答。由于计算机也有可能发生故障,因此采用三台计算机同时复核。由所给答案,再根据“少数服从多数”的原则作出判断,试将结果用命题公式表示,并加以简化,画出电路图。应用举例

第125页:应用举例

125125设C1,C2,C3分别表示三台计算机的答案。S表示判断结果。真值表和联结词的定义,S可用C1,C2,C3所对应的命题公式表示出来,可画出该命题公式所对应的电路图。SC1C2C300 0 000 0 100 1 010 1 101 0 011 0 111 1 011 1 1应用举例

第126页:应用举例

126126S(C1∧C2∧C3)∨(C1∧C2∧C3)∨(C1∧C2∧C3)∨(C1∧C2∧C3)((C1∨C1)∧C2∧C3)∨(C1∧(C2∨C2)∧C3)∨(C1∧C2∧(C3∨C3))(C2∧C3)∨(C1∧C3)∨(C1∧C2)C1C2C3S&&&≥1≥1应用举例

第127页:应用举例

应用举例

本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。

第128页:应用举例

分析:如果被问的是诚实战士且回答“对”,那么另外一名(说谎战士)应回答“是”,说明手指门不是死亡门;如果被问的是诚实战士且回答“不对”,那么另外一名(说谎战士)应回答“不是”,说明手指门是死亡门。

第129页:命题逻辑(上) 本章小结

命题逻辑(上)小结

本节内容到此结束,谢谢大家!

顶部目录