计算思维导论（第2版）课件：逻辑思维与逻辑推理

逻辑思维逻辑思维是一种思维方式是指复合式事件，事物之间的关系的思维方式，它是一种确定的，而不是模棱两可的它是前后一贯的，而不是自相矛盾的它是有条理，有根据的思维，而不是主观臆断的掌握和运用思维形式和方式的程度，也就是逻辑思维的能力逻辑与诡辩逻辑与推理逻辑与幽默我从不给蠢货让路我恰恰相反7.1逻辑学与逻辑思维逻辑思维逻辑的概念：狭义上，逻辑可以理解为思维形式和规则。广义上，逻辑可以理解成：①客观事物的规律性；②某种理论、观点、行为方式；③思维的规律、规则；④一门学科，即逻辑学。逻辑学,

就是关于思维的逻辑形式及其规律的科学。逻辑思维，或称抽象思维，垂直思维，是人们在认识过程中借助于概念、命题、判断和推理等形式，运用分析、综合、归纳和演绎等方法，对丰富多彩的感性事物进行去粗取精、去伪存真、由此及彼、由表及里的加工制作以反映现实的过程。内涵：概念所反映的对象的本质属性或特有属性外延：概念所反映的思维对象的范围演绎推理：前提真，则结论真，必然性推理非演绎推理：前提真，但不保证结论真，或然推理判断必须对事物有所断定判断总有真假概念的特征1判断的特征2推理的特征3三种特征代表学派：墨家学代表人物：墨子代表著作：《墨经》（或称墨辩）古中国代表学派：胜论学派、正理学派代表人物：那坨、乔达摩代表著作：《胜论经》、《正理经》古印度代表学派：古希腊学学派代表人物：苏格拉底、柏拉图、亚里斯多德代表著作：《工具论》古希腊逻辑学发源地17世纪末，德国数学家莱布尼茨首先提出用演算符号表示逻辑语言的思想，把数学引入到形式逻辑之中。数理逻辑18世纪英国数学家乔治·布尔用数学方法来研究逻辑问题，建立了布尔代数。布尔代数所涉及的运算称为布尔运算，也称逻辑运算。布尔代数基本逻辑运算：与、或、非、同或、异或等基本逻辑运算数理逻辑概念数理逻辑内容概念数理逻辑内容Logic数学方法研究推理数学符号符号逻辑古典数理逻辑1、命题逻辑2、谓词逻辑现代数理逻辑1、公理集合2、证明论3、模型论4、递归论7.2命题及命题判断命题定义————能判断真假的陈述句命题真值————命题结论的值真值取值—————真：T（1）假：F（0）真值取值唯一性—————任何命题的真值都是唯一的真值唯一类型—————原命题、逆命题否命题、逆否命题命题类型命题判断是否是陈述句真值是否唯一100908070605040302018小于108大于10吗？8大于10一个自然数不是合数就是素数明年十一是晴天公元1100年元旦下雨TFF未知但确定无考但确定疑问句天空多漂亮！感叹句Y=X+5X没赋值，Y既不真，也不假，值不确定禁止喧哗命令句请把门关上祈使句11我在说谎悖论悖论解释什么是悖论？悖论是指同一命题中有两个对立结论，而两个结论都能自圆其说。即：p→

p，

p→p。假设“我在说谎”这一句话是真的，而说这句话是的人就是一个说谎者，这说明这句话是不可信的，这与我们的假定不符。反之，假设“我在说谎”这一句话是假的，这说明说这句话的人没在说谎，是一个诚实的君子，那么这句话就是可信的，这又与我们的假定有不符。8）今天是晴天。9）ｘ+y>010）把门关上。11）进来！12）你要出去吗？13）今天天气真好啊！14）这个语句是假的。1）太阳是圆的。2）成都是一个旅游城市。3）北京是中国的首都。4）我喜欢踢足球。5）3能被2整除。6）他在说谎。7）中国是世界上人口最多的国家。例：判断以下是否是命题，如果是，则求真值。TTTT/FFT/FTT/F不是命题NONONONONONO命题的取值真：T（1）假：F（0）命题的类型原命题、逆命题否命题、逆否命题真值命题结论的值命题的唯一性任何命题的真值都是唯一的命题的判断方法是否是陈述句真值是否唯一34562什么是命题能判断真假的陈述句17.3命题符号化和联结词案例一案例二案犯可能走陆路，也可能走水路逃离，对车站和公路的搜查表明，案犯没走陆路，则他一定走水路。设：P：案犯走陆路Q：案犯走水路结论：((P∧

Q)∨(

P∧Q)∧P)→Q两个内容相异、形式相同的推理刑侦推理1刑侦推理2这个案件的被害人是自杀或者是他杀，现场侦察证明他不是自杀，则此案为他杀。设P：被害人是自杀Q：被害人是他杀结论：((P∧

Q)∨(

P∧Q)∧P)→Q命题符号化示例今天天气很冷而且刮风。今天天气很冷而且刮风，但室内很暖和。复合命题简单命题用"或者","并且","不","如果...则...","当且仅当"等联结词连接而成的命题。原子命题又称简单命题，是不能再分解的命题。示例今天天气很冷。室内很暖和。示例今天天气很冷而且刮风。今天天气很冷而且刮风，但室内很暖和。复合命题简单命题用"或者","并且","不","如果...则...","当且仅当"等联结词连接而成的命题。复合命题可以分解为更为简单命题的命题示例今天天气很冷并且刮风。命题用符号表示称为命题符号化。命题符号化通常用大写的带或不带下标的英文字母表示命题。如：A、B、C、...P、Q、R、...Ai、Bi、Ci、...Pi、Qi、...表示方法逻辑联结词命题演算是通过逻辑联结词，由简单命题构成更复杂的命题（复合命题）。逻辑连接词类似于运算符号。联结词种类否定、合取、析取、蕴涵、等价。表示命题的符号称为命题标识符。命题标识符一个命题标识符如表示确定的命题，就称为命题常量。命题常量命题变元如果命题标识符只表示任意命题的位置标志，就称为命题变元。通常用大写的带或不带下标的英文字母表示命题，例如：

A、B、C、...P、Q、R、...Ai、Bi、Ci、...Pi、Qi、...例如：用P表示“2是素数”。联结词否定

、合取∧、析取∨、蕴含→

、等价

联结词主要包括：命题演算是通过逻辑联结词，由简单命题构成更复杂的命题（复合命题）。逻辑连接词类似于运算符号。否定设P是任一命题，复合命题“非P”(或“P的否定”)称为P的否定式，记作

P。定义

P为真，当且仅当P为假。规定非、

不、

并非。自然语言示例P:今天下雨。

P:今天不下雨。P

P0110定义规定自然语言示例合取设P、Q是任意两个命题，复合命题“P并且Q”(或“P和Q”)称为P与Q的合取式，记作P∧Q。P∧Q为真当且仅当P、Q同为真。P：3是素数；Q：3是奇数。则P∧Q：3既是素数又是奇数。和、与、并且、既...又...、不仅...而且...、虽然...但是...。PQP∧Q000010100111析取或、或者设P、Q是任两个命题，复合命题“P或者Q”称为P与Q的析取式，记作P∨Q。P∨Q为假，当且仅当P与Q同时为假。P∨Q为真，当且仅当P和Q中至少一个为真。相容或：灯泡或开关故障（可能同时发生）。P∨Q相异或：第一节课上数学课或英语课。(P∧

Q)∨(

P∧Q)PQP∨Q000011101111定义规定自然语言示例析取PQP∨Q000011101111相容或：P：张三考了90分；Q：李四考了90分。则P∨Q表示张三或者李四考了90分。示例相异或：P：小李正在家里看书；Q：小李正在剧场看戏。

小李正在家里看书或正在剧场看戏（不可能同时发生）表示为：(P∧

Q)∨(

P∧Q)示例示例PQP→Q001011100111蕴涵设P、Q是任意两个命题，复合命题“如果P，则Q”称为P与Q的蕴涵式，记作P→Q。P称为蕴涵式的前件，Q称为后件。定义规定自然语言P→Q为假，当且仅当P为真且Q为假。当P为假时，P

Q为真。P为Q的充分条件，Q为P的必要条件。“如果…，那么…”、“若…，则…”和“只有…，才…”、"只要…，就…"如果P，则Q。（P，Q可以不是因果关系）P：周末天气晴朗；Q：我们将到郊外旅游。P→Q：如果周末天气晴朗，则我们将郊外旅游。PQP→Q001011100111蕴涵在自然语言里，“如果P，则Q”中的前件P与后件Q往往具有某种内在联系。而在数理逻辑中，前件和后件未必是因果关系，P与Q可以无任何内在联系，只要可判断逻辑值真假即可。注意日常生活中，前件P为假时（P=0），P→Q没有意义；因为语句的意义无法判断，故人们只考虑P=1的情形。在数理逻辑中，前件P为假时（P=0），P→Q都为真（P→Q=1）。前提与结论这个命题在日常生活中是荒谬的，他们之间没有因果关系。但在数理逻辑中：P：关羽向秦琼叫阵Q：秦琼应声出战P→Q命题成立善意推定李逵对戴宗说："我去酒肆一定帮你带壶酒回来"P=李逵去酒肆，Q=带壶酒回来，P为真，P→Q命题成立。P为假，命题依然成立。应理解为李逵讲了真话，即：他要是去酒肆，相信他一定会带壶酒回来。PQP→Q001011100111蕴涵此类描述包括：只有…才…,除非…才…，没有…,就没有…,注意例如：P：只有我病了，Q：我才打车。Q→P理解：我打车→我病了。病了是打车的必要条件。只有P，才Q,翻译成Q→P。口诀：只有才，后推前除非P，否则Q。翻译成

Q→P。例如：除非疫情肆虐，否则特朗普赢P：疫情肆虐Q：特朗普赢：

Q→P等价设P、Q是任两个命题，复合命题“P当且仅当Q”称为P与Q的等价式，记作P

Q。P

Q为真当且仅当P、Q真值相同。PQ=(PQ)(QP)P与Q互为充分必要条件。“等价”、“当且仅当”、“充分必要”P：两个三角形全等；Q：两个三角形的三条对应边相等。P

Q：两个三角形全等，当且仅当它们的三条对应边分别相等。定义规定自然语言示例PQP

Q001010100111123456括号→否定→合取→析取→蕴涵→等价示例：优先级(Q

P)

Q

P

的真值表示例：

(

P

Q)

Q的真值表123456括号→否定→合取→析取→蕴涵→等价优先级命题符号化练习将下列命题符号化命题命题符号化命题表示四川不是人口最多的省份设P=四川是人口最多的省份

P骑白马的不一定是王子设P=骑白马的一定是王子

P教室的灯不亮可能是灯管坏了或者是停电了。Ｐ=教室的灯不亮可能是灯管坏了Ｑ=教室的灯不亮可能是停电了P∨Q相容或老张或者是山东人，或是山西人P=老张是山东人Q=老张是山西人(P∧Q)∧(P∧Q)相异或铁和氧化合，但铁和氮不化合P=铁和氧化合Q=铁和氮化合P∧(┐Q)命题命题符号化命题表示如果周末天气晴朗，那么我们就去石像湖春游。P=周末天气晴朗Q=我们就去石像湖春游Ｐ→Ｑ三角形是直角三角形当且仅当有一个角是90度P=三角形是直角三角形Q=三角形有一个角是90度Ｐ

Ｑ如果上午不下雨，我就去看电影，否则就在家看书。P=上午下雨，Q=我去看电影，R=我在家看书(┐P

Q)

∨(PR）人不犯我，我不犯人；人若犯我，我必犯人。P=人犯我，Q=我犯人(┐P→┐Q)∧(P→Q)原子命题命题命题表示P=李平聪明Q=李平用功李平既聪明又用功。

P

Q李平虽然聪明但不用功。P

Q李平不但聪明而且用功。P

Q李平不是不聪明而是不用功。(P)

QP：今天下雨Q：3+3=6今天下雨且3+3=6PQ“”可以连接两个完全没有联系的命题联结词说明命题案例命题读法命题含义┐非┐P非PP的否定（逻辑取反）∧与P∧QP并且QP和Q的合取（逻辑乘）∨或P∨QP或者QP和Q的析取（逻辑加）

如果…，则…..P

Q若P则QP蕴含Q（单向条件）

当且仅当P

QP当且仅当QP等价Q（双向条件）命题的前件与后件不同逻辑命题运算的真值PQ┐PP∧QP∨QP

QP

Q0010011011011010001001101111命题符号化的方法否定、析取、合取、蕴含、等价蕴含注意事项前提与结论、善意推定命题符号化命题用符号表示析取注意事项相容或与相异或联结词的优先级括号

否定

合取

析取

蕴含

等价34562原子命题和复合命题原子命题复合命题17.4真值表与等值演算真值表真值表

真值表构造步骤1）找出公式中所含的命题变项，并列出所有可能的取值。2）按低到高的顺序写出各层次。3）对应各取值，计算公式各层次的值，直到计算出公式的值。p真值表构造示例1）找出公式中所含的命题变项，并列出所有可能的取值。公式中变项有三项分别是p、q、r。2）按低到高的顺序写出各层次。三项，共8种可能情况。求命题公式(p∧

q)→r的真值表3）对应各取值，计算公式各层次的值，直到计算出公式的值。qr101101001001110111001001000001010011100101110111qp∧

q(p∧

q)→r用真值表判断

(q→p)与

p∧q公式是否等价pqq→p(q→p)

p

p∧q(q→p)

p∧q0001101110100111100010001111等值演算

永真式设A为一个命题公式，命题在各种赋值情况下取值均为真，则称A为永真式或重言式。永假式设A为一个命题公式，命题在各种赋值情况下取值均为假，则称A为矛盾式或永假式。等值由已知等式推演出另外一些等值式的过程称为等值演算。等值演算定律编号公式图解双重否定定律1A

A等幂律2,3AA∨A，AA∧A交换律4,5A∨BB∨A，A∧BB∧A结合律6,7(A∨B)∨CA∨(B∨C)(A∧B)∧CA∧(B∧C)分配律8,9A∨(B∧C)(A∨B)∧(A∨C)A∧(B∨C)(A∧B)∨(A∧C)德∙摩根律10,11

(A∨B)

A∧B

(A∧B)

A∨B矛盾律12A∧A0A={1，2，3}A∨A={1，2，3}A∧A={1，2，3}AA定律编号公式图解排中律13A∨A1吸收律14,15A∨(A∧B)AA∧(A∨B)A零律16,17A∨11，A∧00同一律18,19A∨0A，A∧1A蕴涵等值式20A→BA∨B等价等值式21A

B(A→B)∧(B→A)假言易位22A→BB→A等价否定等值式23AB

A

B归谬论24(A→B)∧(A→B)

AIAAB等价演算-真值表【例】判断下列命题公式是否等价？

(p

q)与

p

q主析取范式与主合取范式自学7.5逻辑推理01真值表法02等值演算法

03构造证明法反证法从A、B、C、D四个人之中派两个出去执行任务，按下列3个条件共有几种派法？如何派？（1）如果派A去，那么C和D之中至少要派一；（2）B和C不能同时都去；（3）如果派C去，那么D必须留下。设A：派A去，B：派B去，C：派C去，D：派D去根据题意，三种派法分别符号为：（1）A→(C∨D)（2）

(B∧C)（3）C→

D同时满足三个条件，(A→C∨D)∧(

(B∧C))∧(C→

D)=1ABCDC∧

D

C∧D(C∧

D)∨(C∧D)①B∧C②

D③总式0000000100100011010001010110011110001001101010111100110111101111真值表法——————总式：(A→((C∧

D)∨(C∧D))

∧(

(B∧C))

∧(C→

D)=1①②③四个变元，共2^4=16种情况是否能够精简一下真值表？如何精简？ABCDC∧

D

C∧D(C