离散数学第一章命题演算基础命题和联结词

离散数学第一章命题演算基础命题和联结词第一页，共六十页，2022年，8月28日逻辑学:研究推理的科学早期创始人亚里士多德(公元前384—322)柏拉图(公元前429—348),首先把逻辑学的思想方法引入几何学苏格拉底（前470—前399年）第二页，共六十页，2022年，8月28日亚里士多德（Aristotole，公元前384-322）亚里士多德有170多部著作，留传于世的仅47种。他的科学著作构成当时的科学知识百科全书。世界古代史上最伟大的哲学家、科学家和教育家。他创立了形式逻辑学，丰富和发展了哲学的各个分支学科。第三页，共六十页，2022年，8月28日孔子（前551-479）中国春秋末期伟大的思想家和教育家，儒家学派的创始人。孔子被尊为圣人，无法超越，后代的人们只有沿袭与膜拜。学而不思则罔思而不学则殆

第四页，共六十页，2022年，8月28日数理逻辑——数学化的逻辑学在17世纪莱布尼兹（Leibniz）已经提出仿数学的方法发展逻辑的思想。1930年，Godel完全性定理的证明完善了数理逻辑基础，建立了逻辑演算，成为现代科学特别是计算机科学不可缺少的基础理论之一。第五页，共六十页，2022年，8月28日数理逻辑发展史中的代表人物德国G.W.Leibniz(1626-1716)把数学引入形式逻辑，明确提出用数学方法研究推理。英国G.Boole(1815-1864)等创立了逻辑代数，1847年Boole实现了命题演算。德国G.Frege(1848-1925)在1879年建立了第一个谓词演算系统。英国B.Russell(1872-1970)等从逻辑学的基本法则建立了自然数理论、实数理论及解析几何学等。奥地利K.Godel(1906-1978)在1931年提出Godel不完全性定理。英国AlanM.Turing(1912-1954)在1936年提出一种抽象计算模型（数学逻辑机），引入图灵机——一种理想的计算机。第六页，共六十页，2022年，8月28日数理逻辑的学习“我现在年纪大了，搞了这么多年的软件，错误不知犯了多少，现在觉悟了。我想，假如我早年在数理逻辑上好好下点工夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说过了，可是我不知道。要是我能年轻二十岁的话，我就去学逻辑。” ——Edsger.W.Dijkstra1972年Turing奖获得者(1930-2002)带权图的最短通路算法第七页，共六十页，2022年，8月28日A.M.TuringAward

2010Leslie

G

Valiant

2009

Thacker,

Charles

P2008BarbaraLisko（女）2007

Clarke,

Edmund

M

Emerson,

E

Allen

Sifakis,

Joseph

2006

Allen,

Frances

E（女）2005

Naur,

Peter

2004

Cerf,

Vinton

G.

Kahn,

Robert

E.

2003

Kay,

Alan

2002

Adleman,

Leonard

M.

Rivest,

Ronald

L.

Shamir,

Adi

2001

Dahl,

Ole-Johan

Nygaard,

Kristen

2000

Yao,

Andrew

Chi-Chih1999

Brooks,

Frederick

P.

1998

Gray,

Jim

1997

Engelbart,

Douglas

1996

Pnueli,

Amir

1995

Blum,

Manuel

1994

Feigenbaum,

Edward

Reddy,

Raj

1993

Hartmanis,

Juris

Stearns,

Richard

E

1992

Lampson,

Butler

W.

1991

Milner,

A

J

1990

Corbato,

Fernando

J.

1989

Kahan,

William

1988

Sutherland,

Ivan

1987

Cocke,

John

1986

Hopcroft,

John

E

Tarjan,

Robert

E

1985

Karp,

Richard

M.

1984

Wirth,

Niklaus

E

1983

Ritchie,

Dennis

M.

Thompson,

K。

Lane1982

Cook,

Stephen

A.

1981

Codd,

Edgar

F.1980

Hoare,

C.Antony

R.

1979

Iverson,

Kenneth

E.

1978

Floyd,

Robert

W

1977

Backus,

John

1976

Rabin,

Michael

O.

Scott,

Dana

S

1975

Newell,

Allen

Simon,

Herbert

A.1974

Knuth,

Donald

E.

1973

Bachman,

Charles

W.

1972

Dijkstra,

E.

W.

1971

McCarthy,

John

1970

Wilkinson,

J.

H.

1969

Minsky,

Marvin

1968

Hamming,

Richard

1967

Wilkes,

Maurice

V

1966

Perlis,

A.

J.

姚期智Dijkstra第八页，共六十页，2022年，8月28日LeslieValiant,HarvardUniversity

Valiant'sgreatestsinglecontributionmaybehis1984paper"ATheoryoftheLearnable,"whichlaidthefoundationsofcomputationallearningtheory.Heintroducedageneralframeworkaswellasconcretecomputationalmodelsforstudyingthelearningprocess,includingthefamous"probablyapproximatelycorrect"(PAC)modelofmachinelearning.Thishasdevelopedintoavibrantresearchareaandhashadenormousinfluenceonmachinelearning,artificialintelligence,andmanyareasofcomputingpractice,suchasnaturallanguageprocessing,handwritingrecognition,andcomputervision.ProfessorofComputerScienceandAppliedMathematicsSchoolofEngineeringandAppliedSciences第九页，共六十页，2022年，8月28日目录（数理逻辑）第一章命题演算基础（6学时）第二章命题演算的推理理论（4学时）第三章谓词演算基础（5学时）第四章谓词演算的推理理论（5学时）第五章递归函数论（4学时）第十页，共六十页，2022年，8月28日第一章命题演算基础1.1命题和联结词

1.1.1命题1.1.2联结词1.1.3合式公式1.2真假性1.3范式及其应用第十一页，共六十页，2022年，8月28日(一)命题定义定义1：凡是可以判断真假的陈述句称为命题。命题真值

真:用T(或1)表示假:用F(或0)表示第十二页，共六十页，2022年，8月28日命题——可以判断真假的陈述句特征陈述句

真假性:可决定真或假，且真假不可兼

非经典逻辑不接受排中律第十三页，共六十页，2022年，8月28日例：下列句子都是命题吗？雪是白的。✔雪是黑的。✔好大的雪啊！✘8大于12。✔1+101=110。✔第十四页，共六十页，2022年，8月28日例：下列句子都是命题吗？上海世博会开幕时天晴✔21世纪末，人类将住在月球✔大于2的偶数可表示成两个素数之和（哥德巴赫猜想）✔X<0✘A>B✘如果x大于3，则x2大于9。✔第十五页，共六十页，2022年，8月28日例：下列句子都是命题吗？8大于12吗？✘请勿吸烟。✘姚明很帅。✔南京很美。✔我正在说谎。✘这种自指谓的语句往往会产生自相矛盾的结论，即所谓的悖论第十六页，共六十页，2022年，8月28日具体命题的真假问题在数理逻辑的学习中，不能去纠缠各种具体命题的真假问题，而是将命题当成数学概念来处理，看成一个抽象的形式化的概念，把命题定义成非真必假的陈述句．公説公有理婆説婆有理

第十七页，共六十页，2022年，8月28日带联结词的命题今晚我看书。今晚我玩网络游戏。今晚我不看书。今晚我不玩网络游戏。今晚我不看书，我玩网络游戏。今晚我看书，或者我玩网络游戏。否定并且或者第十八页，共六十页，2022年，8月28日(二)原子命题和复合命题

原子命题——不可剖开或分解为更简单命题的命题，也称为简单命题。本书约定用大写字母表示。复合命题——由原子命题利用联结词构成的命题第十九页，共六十页，2022年，8月28日复合命题例子下列命题都是复合命题，其中红字为逻辑联结词：（1）雪不是白的（并非雪是白的）（2）今晚我看书或者去看电影。（3）如果天气好，那么我去接你。（4）偶数a是质数，当且仅当a=2（a是常数）。（5）2是偶数且3也是偶数。

（6）你去了学校，我去了工厂。（省略了逻辑联结词“且”）第二十页，共六十页，2022年，8月28日(三)命题变元定义2：如果当P表示任意命题时，P称为命题变元。字母P表示命题——具体的、特定的命题，有确定的真值

命题变元——任意命题，没有确定的真值

第二十一页，共六十页，2022年，8月28日第一章命题演算基础1.1命题和联结词

1.1.1命题1.1.2联结词1.1.3合式公式1.2真假性1.3范式及其应用第二十二页，共六十页，2022年，8月28日五种常用的联结词否定词﹃合取词∧析取词∨蕴含词等价词第二十三页，共六十页，2022年，8月28日﹃P，非P设P是一个命题。显然，如下这句话也是命题：“P是不对的”称之为P的否定。PPTFFT日常语句中有：

非，不，并非，……真值表第二十四页，共六十页，2022年，8月28日否定词的例子例P：上海是中国的城市。﹁P：上海不是中国的城市。

例P：雪是黑色的。

﹁P：雪不是黑色的。

第二十五页，共六十页，2022年，8月28日否定联结词使用的原则将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例P:这些都是学生。

﹃P：这些不都是学生≠这些都不是学生

第二十六页，共六十页，2022年，8月28日阿契贝难题例下述两命题都是真命题：

A:“本句是六字句”

B:“本句不是六字句”

看似矛盾的根本原因，在于两个命题的前提条件是否统一的问题。第二十七页，共六十页，2022年，8月28日P∧Q，P合取Q设P，Q是两个命题。显然，如下这句话也是命题：“P并且Q”称之为P和Q的合取。PQPQTTTTFFFTFFFF日常语句中有：且，与，……第二十八页，共六十页，2022年，8月28日合取词的例子P:2×2＝5Q：雪是白的。

P∧Q：2×2＝5并且雪是白的。

P:今天刮风。

Q：今天下雨。

P∧Q：今天刮风并且今天下雨。

第二十九页，共六十页，2022年，8月28日P∨Q，P析取Q设P,Q是两个命题。显然，如下这句话也是命题：“P或者Q”称之为P和Q的析取。PQPQTTTTFTFTTFFF日常语言中有：或，……

第三十页，共六十页，2022年，8月28日析取词的例子P:2×2＝5Q：雪是白的。

P∨Q：2×2＝5或者雪是白的。

P:今天刮风。

Q：今天下雨。

P∨Q

：今天刮风或者今天下雨。

第三十一页，共六十页，2022年，8月28日可兼的“或”PQP∨QTTTTFTFTTFFF他会英语或法语。今天刮风或者今天下雨。第三十二页，共六十页，2022年，8月28日不可兼的“或”PQP∨Q

(P∧﹁

Q)∨(﹁P∧Q)TTTFTFTTFTTTFFFF人固有一死，或重于泰山，或轻于鸿毛。

今天晚上我去看电影，或去看球赛。异或XOR第三十三页，共六十页，2022年，8月28日P→Q,P蕴含Q设P,Q是两个命题。显然，如下这句话也是命题：“如果P则Q”称之为P蕴含Q。日常语言中有：

如果…则…,只要…就…，……PQPQTTTTFFFTTFFT第三十四页，共六十页，2022年，8月28日蕴含词的例子P：2×3＝6Q：(2×3)+1=6+2

P→Q:如果2×3＝6，则（2×3）＋1＝6+2

P:天气不好

Q：我去接你

P→Q:如果天气不好，那么我去接你。第三十五页，共六十页，2022年，8月28日注1.前件为假时，命题为真如果蕴含前件P是假命题，那么不管Q是什么命题，命题

“如果P则Q”在逻辑中都被认为是真命题。例：

如果张三能及格，那太阳从西边升起。第三十六页，共六十页，2022年，8月28日注2.前件、后件可以毫不相关在日常语言中“如果……则……”所联结的句子之间表现的是一种因果关系，但在数理逻辑中，尽管说前件蕴涵后件，但两个命题可以是毫不相关的。例：P：2×3＝5Q：雪是黑色的P→Q：如果2×3＝5，则雪是黑色的第三十七页，共六十页，2022年，8月28日注3.充分条件、必要条件p→q为真命题的逻辑关系是：p是q的充分条件，q是p的必要条件。“q是p的必要条件”的叙述方式还有：

p仅当q（仅当q，则p）只有q才p只要p就q除非q，否则非p（非p，除非q）第三十八页，共六十页，2022年，8月28日蕴含词的例子用→表示下列命题：（1）只要天下雨，我就回家。（2）只有天下雨，我才回家。（3）除非天下雨，否则我不回家。（4）仅当天下雨，我才回家。解设p：天下雨。

q：我回家。则（1）符号化为p→q。（2）符号化为q→p，或：﹃p→﹃q （3）符号化为q→p，或：﹃p→﹃q（4）符号化为q→p，或：﹃p→﹃q第三十九页，共六十页，2022年，8月28日PQ，P等价于Q设P，Q是两个命题。显然，如下这句话也是命题：“P当且仅当Q”称之为P等价于Q。

PQPQTTTTFFFTFFFT日常语言中有：当且仅当，……第四十页，共六十页，2022年，8月28日等价词的例子P:2×2＝4Q：雪是白色的。PQ：2×2＝4当且仅当雪是白色的。

P:2×2＝5Q：雪是黑色的。

PQ：2×2＝5当且仅当雪是黑色。

第四十一页，共六十页，2022年，8月28日等价词的例子三角形△ABC为等腰三角形当且仅当三角形△ABC有两条边相等。ABC第四十二页，共六十页，2022年，8月28日非复合命题的例子（1）Tom和John是兄弟。（2）如果x>0，则x2>0。（3）如果两个三角形全等，则它们的面积相等。（4）一个三角形为等腰三角形当且仅当三角形有两条边相等。未指定第四十三页，共六十页，2022年，8月28日注4.充要条件pq为真命题的逻辑关系是：p是q的充分条件，p是q的必要条件。第四十四页，共六十页，2022年，8月28日中学《数学》选修2-1：四种命题第四十五页，共六十页，2022年，8月28日中学《数学》选修2-1：充分、必要第四十六页，共六十页，2022年，8月28日真值函项定义：以真假为定义域并以真假为值域的函数称为真值函项。需要集合与映射的知识才能够讲透!{T,F}{T,F}{T,F}{(T,T),(T,F),(F,T),(F,F)}第四十七页，共六十页，2022年，8月28日一元联结词的真值表一元联结词有一个命题变项P，它取真和假两种，可定义四个不同的一元联结词f0，f1，f2，f3，或称为真值函项。其真假关系可用下图表示：Pf0(P)

f1(P)

f2(P)

f3(P)

TTTFFFTFTF永真恒等否定P永假第四十八页，共六十页，2022年，8月28日f1为与非：PQ=（PQ）f7为异或：PQ=（PQ）f14为或非：PQ=（PQ）二元联结词PQf0

f1

f2

f3

f4

f5

f6

f7

f8

f9

f10

f11

f12

f13

f14

f15TTTFTTTFFFTTTTFFFFTFTTFTTFTTFFTFTFFFFTTTTFTTFTFTFFFTFFFFTTTTFTTFTFFFFFTFf2为蕴含f4为析取f8为等价f11为合取第四十九页，共六十页，2022年，8月28日三元联结词共有多少个？28f0f1f2…………f?(0,0,0)010…………1(0,0,1)001…………1(0,1,0)000…………1(0,1,1)000…………1(1,0,0)000…………1(1,0,1)000…………1(1,1,0)000…………1(1,1,1)000…………1第五十页，共六十页，2022年，8月28日第一章命题演算基础1.1命题和联结词1.1.1命题1.1.2联结词

1.1.3合式公式1.2真假性1.3范式及其应用第五十一页，共六十页，2022年，8月28日合式公式(Wellformedformulae)

合式公式为如下定义的式子，简称为公式：任何命题变元均是公式；如果P为公式，则P为公式；如果为P，Q为公式，则

PQ,PQ,PQ,PQ为公式；当且仅当经过有限次使用①、②、③所组成的符号串才是公式，否则不为公式。第五十二页，共六十页，2022年，8月28日n元公式若公式中有n个不同的命题变元，就说为n元公式。例

一个3元公式：

（（PQ）R）（PQ）第五十三页，共六十页，2022年，8月28日命题符号化将复合命题符号化的步骤是分析出简单命题，符号化用联结词联结简单命题提示：根据命题的实际含义，不拘泥于原句形式地确定原子命题和选用联结词。第五十四页，共六十页，2022年，8月28日例1(p5)将下列各命题符号化:

只有努力学习、认真复习，才能取得好成绩。解：令P表示“努力学习”；

Q表示“认真复习”；

R表示“取得好成绩”。则原句译为