页数:129页文件大小:1.74 MB来源: 离散数学ppt课件
本课件从逻辑学与数理逻辑的发展历程讲起,界定命题与真值的判定标准,系统介绍常用联结词与命题符号化方法,并给出命题公式的类型判定、真值表构造与等值演算思路。
命题逻辑(上)课件封面
离散数学 Discrete Mathematics,本章为命题逻辑(上)。
第3章命题逻辑(上)
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
命题逻辑(上)本章学习内容
逻辑与数理逻辑
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
逻辑的基本知识数理逻辑及其发展历程数理逻辑与计算机
规律的科学,包含:辩证逻辑:研究人的思维中的辩证法。例如:用全面的和发展的观点观察事物;具体问题具体分析;实践是检查事物正误的唯一标准;等等。形式逻辑:研究人的思维的形式和一般规律。本课程只关心形式逻辑。
:通过学习掌握概念和判断,然后进行推理,即:概念判断推理推理:由若干个已知的判断(前提),推出新的判断(结论)的思维过程。正确的思维:概念清楚,判断正确,推理合乎逻辑
公安人员审查一件盗窃案,已知的事实如下:甲或乙盗窃了录音机;若甲盗窃者,则作案时间不会发生在午夜前;若乙的证词正确,则午夜时屋里的灯光未灭;若乙的证词不正确,则作案时间发生在午夜前;午夜时屋里的灯光灭了。问:盗窃者是谁?
逻辑推理实例
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
各门科学都是在特殊领域的思维推理活动,故逻辑是一切科学的公共基础.逻辑思维能力是学习、工作乃至日常生活中的重要能力.
逻辑的基本知识数理逻辑及其发展历程数理逻辑与计算机
ism)从两个前提推出一个结论的逻辑论证形式:1.大前提(major premise)人都是两足动物2.小前提(minor premise)希腊人都是人3.结论(conclusion)希腊人都是两足动物
茨1646-1716英国数学家布尔1815-1864德国数学家弗雷格1848-1925
Wilhelm Leibniz (1646-1716)首先使用“数理逻辑”这个术语Leibniz’s Dream:把推理归结为(符号)计算.提出“思维演算”的思想:“发生争论时我们可以简单地说:让我们计算一下吧,看谁正确.”
布尔George Boole (1815-1864)1847年的论文:逻辑的数学分析:论演绎推理的演算法.发明了布尔代数(逻辑代数,命题代数,布尔逻辑),初步实现了Leibniz梦想。布尔代数亦可解释成集合代数,开关代数,是计算机数字逻辑的基础。附注:Augustus de Morgan (1806-1871)几乎同时独立地做出重要贡献.
弗雷格Friedrich Ludwig Gottlob Frege (1848-1925)1879年的重要著作:概念文字:一种模仿算术语言构造的纯思维的形式语言是第一个公理化谓词逻辑系统是自Aristotle以来逻辑的最重要进展基本实现了Leibniz梦想
研究演绎推理的一门数学学科数学方法——通过引进一整套形式化符号系统的方法。因此,数理逻辑有时候也称为符号逻辑数理逻辑的构成——一套符号体系+一组运算规则
:命题逻辑、谓词逻辑、公理化集合论、递归论、模型论、证明论本课程只讨论“命题逻辑”和“谓词逻辑”
逻辑的基本知识数理逻辑及其发展历程数理逻辑与计算机
+数据算法=逻辑+控制
算机组成原理
命题逻辑(上)小结
本节内容到此结束,谢谢大家!
命题逻辑(上)本章学习内容
命题与联结词
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
命题的基本概念命题的运算联结词命题的符号化与应用
命题是一个或真或假的陈述句,但不能既真又假。确定命题语句真值的几点说明:1、时间性2、区域性3、标准性
注意:一切没有判断内容的句子都不能作为命题,如命令句、感叹句、疑问句、祈使句、二义性的陈述句等。
,但并非一切陈述句都是命题。命题的真值有时可明确给出,有时还需要依靠环境、条件、时间、实际情况才能确定其真值。
Values)的表示:真:T、1;假:F、0命题的符号表示:大写英文字母:P、Q、R、…带下标的大写字母:A1、A2、A3、…数字:[1]、[2]、[3]、…命题的表示
简单命题(原子命题):由最简单的陈述句构成的命题(该句不能再分解成更简单的句子)。
例:2是个素数。复合命题(分子命题):由若干个原子命题构成的命题。
例:四川不是一个国家命题的种类
命题的基本概念命题的运算联结词命题的符号化与应用
命题可以通过逻辑联结词(逻辑运算)构成新的命题——复合命题。复合命题的真值依赖于其中简单命题的真值。
联结词举例
例:(1)期中考试,张三没有考及格。(2)其中考试,张三和李四都考及格了。(3)期中考试,张三和李四中有人考了90分。(4)如果张三能考90分,那么李四也能考90分。(5)张三能考90分,当且仅当李四也能考90分。
:Negation(NOT)否定词∧:Conjunction(AND)合取词∨:Disjunction(OR)析取词:Implication(if–then)蕴涵词:Biconditional(if and only if)等价词
3737联结词“”称为否定词,表示“…不成立”P:今天是星期二P:今天不是星期二P读着:“非P”当P为假时,非P为真;当P为真时,非P为假“非”运算
3838命题否定的真值表如下:¬PPFTTF“非”运算
3939“与”运算联结词“”称为合取词,表示逻辑“与”运算;“”相当于自然语言中的“并且”,“与”的含义,但是又和自然语言中的“与”有所不同。P:小王能唱歌;Q:小王能跳舞。P∧Q:小王能歌善舞。当且仅当P和Q都为真时,PQ才为真
4040当且仅当P和Q都为真时,PQ才为真PQQPTTTFFTFTFFFF“与”运算
联结词“”称为析取词,表示可兼或当且仅当P和Q都为假,PQ为假P:李明在教室。Q:米卢是个好教练。P∨Q:李明在教室或米卢是个好教练。
,当且仅当P与Q均为FPQQPTTTTFTTTFFFF“(可兼)或”运算
:若P则Q例:P表示:缺少水分。Q表示:植物会死亡。PQ:如果缺少水分,植物就会死亡。P是前提,Q是结论
,PQ为假PQQPTTTFFTTTFTFF“蕴涵”运算
注意:“”既表示充分条件也表示必要条件,它决定了哪个作为前件,哪个作为后件。
例:令:P:天气好。Q:我去公园。1.如果天气好,我就去公园。(充分)2.只要天气好,我就去公园。(充分)3.仅当天气好,我才去公园。(必要)4.只有天气好,我才去公园。(必要)命题1、2写成:PQ命题3、4写成:QP“蕴涵”运算
4646“”:等价联结词PQ(P当且仅当Q):当p和q有着相同的真值时,pq为真)PQQPTTTFFTFTFTFF“等价”运算
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
4848小结P↔QP→QP∨QP∧Q┐PP Q110010 0011010 1001001 0111101 1设命题P,Q表示任意两个命题,则有:
命题的基本概念命题的运算联结词命题的符号化与应用
1.首先要明确给定命题的含义。2.对于复合命题,找联结词,用联结词断句,分解出各个原子命题。3.设原子命题符号,并用逻辑联结词联结原子命题符号,构成给定命题的符号表达式。
一对应
例题
例:符号化下列命题说离散数学无用且枯燥无味是不对的。P:离散数学是有用的。Q:离散数学是枯燥无味的。该命题可写成:(P∧Q)人不犯我,我不犯人;人若犯我,我必犯人。P:人犯我。Q:我犯人。该命题可写成:(PQ)∧(PQ)或写成:PQ
5353例题
例:符号化下列命题(1)四川不是人口最多的省份;(2)王超是一个德智体全面发展的好学生;(3)教室的灯不亮可能是灯管坏了或者是停电了;(4)如果周末天气晴朗,那么学院将组织我们到石象湖春游;(5)两个三角形全等当且仅当三角形三边对应相等。
5454例题
例:符号化下列命题(1)除非明天不下雨且不下雪,否则我将不去学校;(2)只要明天不下雨或不下雪,我就去学校;(3)只有明天不是雨夹雪,我才去学校;(4)明天上午我将雨雪无阻一定去学校。
5555例题
例:符号化下列命题⑴除非你陪伴我或代我叫车子,否则我将不出去。⑵如果你陪伴我并且代我叫辆车子,那么我将出去。⑶如果你不陪伴我或不代我叫辆车子,那么我将不出去。
5656联结词的应用联结词“∧”、“∨”、“┐”同构成计算机的与门、或门和非门电路是相对应的,从而命题逻辑是计算机硬件电路的表示、分析和设计的重要工具。
5757
例:用复合命题表示如下图所示的开关电路:设P:开关P闭合;Q:开关Q闭合。P∧QP∨QP应用实例
5858
例:用复合命题表示如下图所示的逻辑电路PQPQP
解:设P:输入端P为高电位,Q:输入端Q为高电位,则“与门”对应于P∧Q“或门”对应于P∨Q“非门”对应于P应用实例
5959
例:逻辑难题一个岛上住着两类人:骑士和流氓。骑士说的话都是实话,而流氓只会说谎。如果碰到两个人A和B,如果A说:“B是骑士”,B说:”我们两个不是一类人”。请判断:A、B两人到底是流氓还是骑士?应用实例
6060
例:泥巴孩子难题父亲让两个孩子(一个男孩,一个女孩)在后院玩,并让他们不要把身上搞脏。然而,在玩的过程中,两个孩子都在额头上沾了泥。孩子们回来后,父亲说“你们当中至少有一个人额头上有泥”,然后他问每一个孩子“你知道你额头上有没有泥吗?”同样的问题问两遍。假设每个孩子都可以看到对方的额头上是否有泥,但不能看见自己的额头,孩子们将会怎样回答呢?假设两个孩子都很诚实并且都同时回答每一次提问。应用实例
命题逻辑(上)小结
本节内容到此结束,谢谢大家!
命题逻辑(上)本章学习内容
命题公式与真值表
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
命题公式的基本概念命题公式的基本类型命题公式的等值演算命题公式的应用
6565命题变元如果命题标识符表示一个具体、确定的命题,称为命题常元。如果命题标识符表示任意一个命题,称为命题变元。命题是能判断真假的陈述句。命题变元代表任意的命题,其真值是不确定的,它的变域是集合{T,F}(或{0,1})。
6666命题公式把命题常元,命题变元按照一定的逻辑顺序和规则,用命题联结词连接起来就构成了命题演算的合式公式,也叫命题公式。
6969命题公式举例
例:下列符号串是合式公式:¬(p∨q),¬(p∨q),(p→(p∨¬q)),(((p→q)∧(q→r))↔(s↔t))
例:下列符号串不是合式公式:(p→q)→(∧q),(p→q,(p∧q)→q)
7070一些约定【约定】为方便,最外层括号可以不写,合式公式可以写成:P∧Q,PR,(P∨Q)∧R【约定】逻辑联接词优先级:¬、∧、∨、→、此时P∧QR也是合式公式
7171例题
例:试用符号形式写出下列命题:(1)虽然今天天气晴朗,老陈还是不来;
解:设P:今天天气晴朗, Q:老陈要来,则有:P∧┐Q;(2)除非你陪伴我或代我叫车子,否则我将不出去;
解:设P:你陪伴我; Q:你代我叫车子; R:我出去。则有:R→P∨Q或┐P∧┐Q→┐R;
7272公式的解释
7373赋值类型若指定的赋值使G的真值为T,则称这个赋值为G的成真赋值,若指定的赋值使G的真值为F,则称这个赋值为G的成假赋值。
例:给公式(p∨q→r)的赋值赋值011是指p=0,q=1,r=1,它是该公式的成真赋值;赋值110是指p=1,q=1,r=0,它是该公式的成假赋值。
7474真值表的概念若公式G中有n个不同的命题变元,则该公式应有2n个不同的解释。将公式G在其所有可能解释下的真值情况列成的表,称为G的真值表。
7575真值表的概念在命题公式G中,对G的每一个赋值,就确定了G的一个真值,把这些所有的真值汇列成表,称该表为命题公式G的真值表。(PQ)∨QPQPQPTTFTTTTFFTTTTTFFFTFF
7676真值表举例
例:求下面公式真值表:G=(P→(PQ)∧R)∨Q其中,P、Q、R是G的所有命题变元。
7777真值表的说明设P1,P2,…,Pn为命题公式P中命题变元,对于命题变元每一种真值指派的可能组合,都能唯一确定P的真值(即有2的n次幂种分布)。为有序列出公式的真值表,在对命题变元做指派时,可按二进制数次序列表。
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)
7979例题
例:构造命题公式¬p∨q的真值表,并求成真赋值和成假赋值。
解:命题公式¬p∨q的真值表下表所示。00,01,11是成真赋值,10是成假赋值。¬ppq¬p∨q0011011110001101
8080例题
例:构造命题公式(p∧q)∨(¬p∧¬q)的真值表,并求成真赋值和成假赋值。
解:命题公式(p∧q)∨(¬p∧¬q)的真值表如下表所示。00,11是成真赋值,01,10是成假赋值。pqp∧q¬p¬q¬p∧¬q(p∧q)∨(¬p∧¬q)0001111010100010001001110001
8181例题
例:列出P(QR)的真值表P(QR)QRRQPTTFFF000TTTFF001TFFTF010TTTTF011TTFFT100TTTFT101FFFTT110TTTTT111
命题公式的基本概念命题公式的基本类型命题公式的等值演算命题公式的应用
8383公式的分类
例:求列公式的真值表:G1=(P→Q)→P;G2=(P→Q)∧P;G3=(P∧Q)(P→Q)。
8484公式的分类从这三个真值表可以看到:公式G1对所有可能的解释具有“真”值公式G3对所有可能的解释均具有“假”值公式G2则具有“真”和“假”值
8585公式的分类公式G称为永真公式(重言式),如果在它的所有解释之下都为“真”。公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。公式G称为可满足式,如果它不是永假的。
8686公式的分类如果A,B是永真式(永假式),则(A∧B)、(A∨B)、(AB)和(AB)也都是永真式(永假式)。
8787公式的分类1)永真式G的否定G是矛盾式;矛盾式G的否定G是永真式。2)永真式一定是可满足式;可满足式不一定是永真式3)可满足式的否定不一定是矛盾式三种特殊公式之间的关系:
公式的分类三种特殊公式之间的关系
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
8989例题
例:写出下列公式的真值表,并验证其公式是永真式、永假式、可满足公式。(1)G1=(P→Q)(P∨Q);(2)G2=(PQ)((P→Q)∨(Q→P));(3)G3=(P→Q)∨Q。
命题公式与真值表
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
命题公式的基本概念命题公式的基本类型命题公式的等值演算命题公式的应用
Q)PQ¬P∨QQPTTTTFFFFTTTFFFFFFTTTTTTT是否发现什么问题?¬P∨Q=PQ?(P∧Q)∨(¬P∧¬Q)=PQ?公式的等值关系
公式等值的定义
的等值关系有如下性质:(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)
例题
例: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)
例题
例:根据等值关系的定义,用真值表证明p→(q→p)¬p→(p→¬q)pq¬p¬qq→pp→(q→p)p→¬q¬p→(p→¬q)00111111011001111001111111001101
等值关系的判定
定理:命题公式A、B具有等值关系的充分必要条件是命题公式AB是永真式。
证明:(1)若AB,则A、B有相同的真值,即AB永为T.(2)若AB为重言式,则AB永为T,故A、B的真值相同,即AB
,命题公式GH的结果仍是一个命题公式。“”表示两个命题公式之间的逻辑等值关系,GH表示“命题公式G与命题公式H等值”,GH不是命题公式。此外,如果用计算机直接判断命题公式G、H是否逻辑等价或等值(即GH),是办不到的。但是,计算机可通过“计算”公式GH是否为永真式,来判别是否有:GH。
例题
例:证明公式G1=(PQ)与公式G2=(P→Q)∧(Q→P)之间逻辑等价。【证】根据定理,只需判定公式G3=(PQ)((P→Q)∧(Q→P))为永真公式。
等值演算法证明两个命题公式之间等值或逻辑等价的另外一种方法叫做等值演算法。基本思路是:首先用真值表证明一组基本等值式,然后再它们为基础进行命题公式之间的等值演算。
基本等值式
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
基本等值式
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
基本等值式
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
以上共24个等值式都可用真值表证明。下面仅验证德摩根律:¬(A∨B)¬A∧¬BA∨BAB¬A¬B¬A∧¬B¬(A∨B)0011101011001010010101100010
命题与集合
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
∪、∩与∨、∧
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
代入定理
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
例:设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'是一个永真公式。
替换定理
定理:设G1是G的子公式,H1是任一命题公式,在G中凡出现G1处都以H1替换后得到新的命题公式H,若G1H1,则GH。熟记24个基本等值公式理解代入定理和替换定理
的等值演算,可完成如下工作:
的等值演算,可完成如下工作:
的等值演算,可完成如下工作:
例题
例:求证吸收律P∧(P∨Q)P【证】(P∧(P∨Q)(P∨F)∧(P∨Q) (同一律)P∨(F∧Q) (分配律)P∨F (零律)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 (同一律)
例题
例:化简(P∧Q)→(P∨(P∨Q))
解:原公式(P∧Q)∨((P∨P)∨Q) (常用等值式)(P∧Q)∨(P∨Q) (对合律,幂等律)(P∧Q)∨(Q∨P) (交换律)((P∧Q)∨Q)∨P (结合律)Q∨P (吸收律)
命题公式的基本概念命题公式的基本类型命题公式的等值演算命题公式的应用
1171171、试证语句:“不会休息的人也不会工作,没有丰富知识的人也不会工作”,与语句“工作得好的人一定会休息并且有丰富的知识”,具有相同的逻辑含义。分析:设P:某人会工作;Q:某人会休息;R:某人有丰富的知识,则有:(Q→P)∧(R→P)P→(Q∧R)用真值表或等值演算法易证这两个公式等值。应用举例
1181182-1利用基本等价关系,化简下列电路图RPSQPSPQRP应用举例
119119解:上述电路图可描述和化简为:(1)(P∧Q∧R)∨(P∧Q∧S))∧((P∧R)∨(P∧S))((P∧Q∧(R∨S))∧(P∧(R∨S))P∧Q∧(R∨S);SRQP应用举例
120120&&≥1≥1&TSRQP2-2利用基本等价关系,化简下列电路图应用举例
121121解:上述电路图可描述和化简为:((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T)(P∨Q∨S)∧(P∧S∧T) = (P∨Q∨S)。PSQ≥1应用举例
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)应用举例
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应用举例
1241244、一家航空公司,为了保证安全,用计算机复核飞行计划。每台计算机能给出飞行计划正确或有误的回答。由于计算机也有可能发生故障,因此采用三台计算机同时复核。由所给答案,再根据“少数服从多数”的原则作出判断,试将结果用命题公式表示,并加以简化,画出电路图。应用举例
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应用举例
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应用举例
应用举例
本页源文件仅提取到标题文字,正文以图示呈现,建议对照原课件图片补充本页要点说明。
分析:如果被问的是诚实战士且回答“对”,那么另外一名(说谎战士)应回答“是”,说明手指门不是死亡门;如果被问的是诚实战士且回答“不对”,那么另外一名(说谎战士)应回答“不是”,说明手指门是死亡门。
命题逻辑(上)小结
本节内容到此结束,谢谢大家!
下载地址:{{downurl}}
{{{a}}}
{{#b}}{{{b}}}
{{/b}} {{/title}} {{#nolog}}登陆注册
{{/nolog}} {{#djsx}}点我刷新
{{/djsx}} {{#gocz}} {{/gocz}} {{#ffqr}} {{/ffqr}}