第一二章数理逻辑课件

第一篇数理逻辑一、数理逻辑（符号逻辑，现代逻辑）1.定义:用数学方法来研究人类推理过程的一门数学学科.逻辑：客观事物在主观意识中的反映；逻辑学：研究思维形式及思维规律的科学，它分为辩证逻辑和形式逻辑；判断：利用概念对事物是否具有某种属性进行肯定或否定的回答；推理：由一组前提推出某重结论。2．特点符号化，形式化即把逻辑所涉及的“概念、判断、推理”用符号来表示，依据推理规则和公里体系，并基于符号串形式的演算来描述推理的一般规律。3．数理逻辑的研究方法将自然语言符号化形成数学语言；（符号语言、形式语言）根据公理系统及推理规则进行逻辑推理。（数学演算）4.数理逻辑的应用及其发展人工智能（语音识别、机器人）形式语义学第一章命题逻辑

§1.1、命题和联结词一、命题proposition1、命题引入为避免自然语言的不确定性及二义性，引入目标语言和一些符号公式，用以表达语言中的判断和推理，从而形成数理逻辑的形式符号体系，符号化的对象是目标语言；目标语言：即我们的研究对象，也就是要研究无二义性的语言的范围，即具有明确是、非概念的陈述句，因为它是表达判断的。2、命题定义能判断其含义为真或假的陈述句，具有唯一的真值称为命题；一个命题具有唯一一个“值”，称为真值，他仅有真或假（不可兼）两种，记为true和false，简记为T/1和F/0。例1：亚洲比欧洲大。我正在说谎。（悖论，自相矛盾）生命是有限的，思想是无限的。起立！（非陈述句）你们听到了吗？（非陈述句）我在讲课。别的星球上有生物。毛泽东姥姥去世那天，天空正在下雪。X=23、命题表示法命题标识符：用大写英文字母表示。P：我是中国人。Q：离散数学不好学。4、命题常量和变元命题常量：表示确定命题的命题标识符；命题变元：只表示任意命题位置标志的命题标识符；因命题变元课表示任意命题，无所谓真假值，所以它不是命题；指派：当命题变元P用一特定命题取代时，P才能确定真值，称为对P~；5、原子命题与复合命题原子命题atomic：不能再分解为更简单陈述语句的命题；复合命题compound：由联结词、标点符号和原子命题复合构成的命题；二、常用逻辑联结词（5个）联接词的作用将原子命题联接成复合命题；相当于是对陈述句中的关联词的符号化处理。1、否定(┐)定义：设P为一命题，P的否定是一个新的命题，记为；若P为T，则为F，若P为F，则为T。与自然语言的关系：相当于不、否、非等；┐P真值表如表1.1所示。注意：否定的意义仅是修改命题的内容，没有构成复合命题，它是一元运算。p┐p0110

表1.1┐P真值表2、合取（∧）定义：两命题P、Q的合取是一复合命题，记为。当且仅当P、Q同时为T时，为T，其他情况为F。P∧Q真值表如表1.2所示。与自然语言的关系：相当于与、并且、和等，常表示递进、并列、转折这样的关系，但新的复合命题不一定有意义，这是数理逻辑命题与自然语言的区别。

P

QP∧

Q000010100111

表1.2P∧Q真值表3.析取（∨）定义：两命题P、Q的析取是一复合命题，记为。当且仅当P、Q同时为F时，为F，其他情况为T；与自然语言的关系：相当于可兼或，但新的复合命题不一定有意义；p∨

q真值表如表1.4所示。p

qp∨

q000011101111表1.3P∨Q真值表注：自然语言中的“或”是具有二义性的。自然语言中“或”的含义可以是“可兼或”，也可以是“排斥或”，还可以是“大约数量”，但数理逻辑中的“或”即析取指的是“可兼或”例3：毕业后，去西藏或去新疆。（排斥或）张三是党员或者是班长。（可兼或）我做了20道或30道数学题。（大约数量）

4.蕴涵（→）

设P、Q是任意两个命题，复合命题“如果P，则Q”称为P与Q的蕴涵式，记作：P→Q。P称为蕴涵式的前件，Q称为蕴涵式的后件，→称为蕴涵联结词。→经常表示自然语言的假设关系。P→Q的真值表如表1.4所示。P

QP→

Q001011100111表1.4P→Q真值表例4：如果我们再一次忽视日本人和美国人的野心，那么我们将不在有未来。如果摒弃了民族平等，那么我们将遭遇战争。张三（男）对李四说：我如果是女孩那么我肯定嫁给你。（永真）注：自然语言中“如果…那么…”这样的语句，当前件为假时，不管结论真假，整个语句的意义往往无法判断，但条件命题中，当前件为假时，条件命题为真，称为“善意的推定”。p

q001010100111表1.5与自然语言的关系：用于表达一种充分必要条件，相当于“当且仅当”；例5：万物生长，当且仅当有阳光普照。P:万物生长;Q:有阳光普照;三、语言的翻译1、符号语言翻译成自然语言例6：P：我爱祖国，Q：我爱人民，P∧Q：我不仅爱祖国并且也爱人民。例7：P：小王是班长，Q：小王是三好学生，P∨Q：小王是班长或三好学生。例8：P：好好学习，Q：考试及格，

P→Q:如果好好学习的话，那么考试肯定能及格。2、自然语言翻译成符号语言注意：先找出原子命题，再确定联结词例9：“我爱祖国也爱人民”可以先分解为两个原子命题；P：我爱祖国；Q：我爱人民。P∧Q例10：我们不能既唱歌又跳舞；P：我们唱歌；Q：我们跳舞。┐(P∧Q)例11：不是你没写信就是信在途中丢失了；P：你没写信；Q：信在途中丢失了。符号化见表1.6。注：在进行自然语言符号化时，能准确表达语意的联结词有时不易确定，可以利用真值表来帮助确定。PQ命题真值110101011000表1.6§1.2命题公式及其赋值

一、命题公式（合式公式）1、定义：命题公式（合式公式），即由命题变元和命题联结词按照特定的构造规则形成的串，称为命题公式，其中的命题变元称为命题公式的分量；单个命题变元本身是一个合式公式；如果A和B是合式公式，则A∧B,A∨B,A→B,都是合式公式；当且仅当能够有限次地应用（1）,（2）,（3）所得到的包含命题变元、联结词和括号的符号串称为合式公式。注意1、命题公式是没有真假值的，仅当在一个公式中命题变元用确定的命题代入时，才得到一个命题。这个命题的真值，依赖于变换变元的那些命题的真值；2、为了简化合式公式的书写，作了两点约定，其一是最外层括号可以省略，其二是合式公式中的联结词运算符优先次序为：┐∧∨→3、命题公式正确书写：括号配对，相邻的两个命题变元之间有二元联结词，二元联结词之间应该有命题变元。

二、真值表truthtable1、命题公式的赋值（解释）：设命题公式A(p1,p2…pn),其中p1,p2…pn为A中的命题变元，给p1,p2…pn各指派一个真值，称对A的一次赋值（解释）。如果指定的某组赋值使A的真值为1，则称这组值为A的成真赋值，否则称这组值为A的成假赋值。2、定义：在命题公式A(p1,p2…pn)中，对于分量（命题变元）指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，将其汇列成表，就是命题公式的真值表；命题公式中变元真值指派组合数目决定于变元分量的个数，一般说，n个命题变元组成的命题公式共有2n种真值组合情况。例1P→Q┐P∨QPQP→Q┐P∨Q1111100001110011例2(┐P∨Q)∧(┐Q∨P)

(P∧Q)∨(┐P∨┐Q)PQ11111100000100000111(┐P∨Q)∧(┐Q∨P)

(P∧Q)∨(┐P∨┐Q)例3：(P∧Q)→P;┐(

P→(P∨Q))4、应用(1)等价式的证明，两个命题公式等价iff对于分量的任一组真值指派对应的命题公式真值都相等。(2)命题公式类型的判断1）重言式（永真式）：在命题公式A(p1,p2…pn)中，对命题公式A的所有命题变元赋值（2n次赋值），命题公式的真值都为1，则称公式为重言式。2）矛盾式（永假式）：在命题公式A(p1,p2…pn)中，对命题公式A的所有变元赋值（2n次赋值），命题公式的真值都为0，则称公式为矛盾式。3）如果A(p1,p2…pn)不是矛盾式，则A称可满足式。⑶主范式的求取，推理证明等。§1.3、基本等值式（等价式）一、等价式logicaleguivalence1、WffA和WffB等价定义给定两个命题公式A和B，设p1,p2…pn为所有出现在A、B中的原子变元，若给定p1,p2…pn任一组真值指派，A、B的真值都相同，则称A、B等价或逻辑相等记作。2、基本等价式(P15)3、等价式的证明1）真值表法若要证明命题公式A、B等价，先分别列出A、B的真值表，若A、B命题公式对应的真值表中的所有真值指派真值均相同，即可证明。PQP→Q┐P∨Q11111000011100012）推导法利用基本等值式，可以对命题公式中的某些子公式用与其等价的命题公式进行等价代换，进而对原公式进行变换，最终使两命题公式变换为相同的命题公式。例1

P→(Q→R)Q→(P→R)左式P→（┐Q∨R）┐P∨(┐Q∨R)(┐P∨┐Q)∨R

(┐Q∨┐P)∨R

┐Q∨(┐P∨R)Q→(P→R)

例2P→(Q→R)(P∧Q)→R左式P→（┐Q∨R）┐P∨(┐Q∨R)(┐P∨┐Q)∨R┐(P∧Q)∨R

(P∧Q)→

R练习(P∨Q)→R(P→

R)∧(Q→

R)（PQ）（P∧Q)∨(┐P∧┐Q)4、命题公式化简

例3((P→Q)(┐Q→┐P))∧R((P→Q)(P→Q))∧RT∧RR练习(P∧Q∧R)∨(┐P∧Q∧R)(p→(P∨Q))∨(P→R)§1.4析取范式与合取范式

一、析取范式1、析取范式iffA(A1∨

A2∨

…∨An），其中A1，

A2，

…，An都是由A中出现的命题变元不可兼或其否定由∧联结词组成的合取式。2、析取范式求法(P31)1）将命题公式中联结词转换成┐∧∨。2）利用德摩根律把┐直接移入到每个命题变元之前。3）利用分配律或结合律将公式转换成析取范式，并进行化简。例1

(┐P∧R)∨┐(P→Q)(P∧

┐R)∨┐(┐P∨

Q)(P∧

┐R)∨

(P∧

┐Q)例2┐(P→R)∧(P∨┐Q)┐(┐P∨

R)∧(P∨┐Q)

(P∧┐R)∧(P∨┐Q)((P∧┐R)∧P)∨((P∧┐R)∧┐Q)

(P∧┐R)∨(P∧┐Q∧┐R)

二、合取范式1、合取范式iffA(A1∧

A2∧

…∧An），其中A1，

A2，

…，An都是由A中出现的命题变元不可兼或其否定由∨联结词组成析取式。2、合取范式求法(P31)1）将命题公式中联结词转换成┐∧∨。2）利用德摩根律把┐直接移入每个命题变元之前。3）利用分配律或结合律将公式转换成合取范式，并进行化简。注：合取范式求法和析取范式求法相同。例3

(┐P→R)∨

(P∧┐Q)

(P∨R)∨(P∧┐Q)

(P∨R)∨(P∧┐Q)((P∨R)∨P)∧((P∨R)∨┐Q)

(P∨R

∨P)∧(P∨R∨┐Q)

(P∨R)∧(P∨┐Q∨R)

三、主析取范式1、相关概念1）小项（布尔合取）设命题公式为A(p1,p2…pn)，n个命题变元不可兼或其否定，并由合取联结词组成的符号串，即：每个命题变元不能与其否定同时出现，但必须出现且仅出现一次。2）小项（布尔合取）与合取式区别。3）小项性质：所有小项的吸取为永真，任意不同两个小项的合取为永假。4）编码表示:m111P∧Q∧Rm101P∧┐Q∧R2主析取范式定义iffA(A1∨

A2∨

…∨An），其中A1,

A2,

…,An是小项（布尔合取）。求法

●真值表例4┐(P→R)∧(P∨┐Q)PQR(P→R)┐(P→R)(P∨┐Q)┐(P→R)∧(P∨┐Q)11110101100111101101010001110111000010100000110100001010主析取范式(P∧Q∧

┐R)∨(P∧

┐Q∧

┐R)2)推导法：先求析取范式，然后利用等价补项法求主析取范式，最后化简。如上例┐(P→R)∧(P∨┐Q)┐(┐P∨

R)∧(P∨┐Q)

(P∧┐R)∧(P∨┐Q)((P∧┐R)∧P)∨((P∧┐R)∧┐Q)

(P∧┐R)∨(P∧┐R∧┐Q）((P∧┐R)∧(Q∨┐Q))∨(P∧┐Q∧┐R）((P∧┐R)∧Q)∨((P∧┐R)∧┐Q))∨(P∧┐Q∧┐R）

(P∧┐R∧Q)∨(P∧┐R∧┐Q)∨(P∧┐Q∧┐R）

(P∧Q∧┐R)∨(P∧┐Q∧┐R)m110∨m100

∑4,6

四、主合取范式1、相关概念1）大项（布尔析取）：设A(p1，p2，…pn)，n个命题变元和其否定不可兼，由∧联结词组成的符号串，即：每个命题变元不能与其否定同时出现，但必须出现且仅出现一次。2）大项（布尔析取）与析取式区别。大项性质：所有大项的合取是永假，任意不同两个大项析取是永真。4）编码表示：M000=P∨Q∨R,M010=P∨┐Q∨R。2、主合取范式1）定义

iffA(A1∧

A2∧

…∧An）,其中A1,

A2…,An是大项（布尔析取）。2）求法●真值表

上例┐(P→R)∧(P∨┐Q)PQR(P→R)┐(P→R)(P∨┐Q)┐(P→R)∧(P∨┐Q)11110101100111101101010001110111000010100000110100001010主合取范式：

(┐P∨┐Q∨┐R)∧(┐P∨Q∨┐R)∧(P∧

┐Q∧

┐R)∧(P∧

┐Q∧R)∧(P∧Q∧┐R)∧(P∧Q∧R)●推导法上例┐(P→R)∧(P∨┐Q)(P∧┐R)∧(P

∨┐Q)P∧┐R∧(P∨┐Q)(P∨(Q∧

┐Q))∧(┐R∨(P∧

┐P))∧((P∨┐Q)∨

(R∧

┐R))

(P∨Q)∧(P∨

┐Q)∧(P∨┐R)∧(┐P∨┐R)∧(P∨┐Q

∨R)∧(P∨┐Q∨┐R)(P∨Q∨R)∧(P∨Q∨┐R)∧(┐P∨

┐Q∨┐R)∧

(┐P∨Q∨┐R)∧(P∨┐Q∨R)∧(P∨┐Q∨┐R)M000∧M001∧M111∧M101∧M010∧M011

∏0,1,2,3,5,7五、编码转换法设命题公式为：A(p1，p2，…pn)，其主合取范式编码集合为H1,主析取范式编码集合为H2,则H1∪H2＝{0,1,…2n-1}=H,H1∩H2＝φ

,H1H,H2H,H1和H2为集合H的一个划分。练习(P∧Q)∨┐(P→R)

(P→Q)→(P∧┐R)

(P→(Q∧R)∧(┐P→(┐Q∧┐R)§1.5、命题推理一、命题推理定义定义A→B为重言式iff,其中A是前提，B是A的有效结论，或B可由A逻辑的推出。对重言式定义推广，令，则称B是一组前提的有效结论，或B可由逻辑的推出，记作：。二、命题演算的公理化方法命题演算的公理化方法就是建立一个抽象更高概括性更强的形式化推理系统。1)字符表：命题变元、常用的5个联结词、括号和，。2)命题公式3)利用(1)基本等价式和蕴含式(P47):附加规则、化简规则、假言推理、假言三段论、合取规则;(2)推理规则：P规则，T规则。§1.6、自然语言推理系统一、命题推理的方法 1、真值表法:A→B为重言式iff,写出A→B的真值表，根据→的特殊性，有两种判断情况：A=1则B=1;B=0则A=0。例1：P→R,P∧QR∧QPQRP∧QP→RR∧Q1111111101001010101000000110110100100010100000102、证明法1)直接证明：利用PT规则和已知的等值式蕴含式，直接由前提推出结论。例2P→R,P∧QR∧Q(1)P∧QP(2)PT(1)(2)(3)P→RP(4)RT(2)(3)(4)(5)QT(1)(5)(6)

R∧QT(4)(5)(6)练习

P→QS∨RS→┐QR→┐Q┐P2)反证法：假设结论不成立，即结论的否定当做一个附加前提，最后推出矛盾。

例3P→Q,S∨R,S→┐Q,R→┐Q,┐P

(1)P

P(附加)(2)P→QP

(3)QT(1)(2)(3)(4)S→┐QP(5)Q→┐ST(4)(5)(6)┐ST

(3)(5)(6)(7)S∨RP(8)┐S→RT(7)(8)(9)RT(6)(8)(9)(10)R→┐QP(11)┐Q

T

(9)(10)(11)(12)Q∧┐QT

(3)(11)(12)练习P∨QP→RQ→S

┐S→R3)CP规则：仅限于结论中含有（可以转换成）条件联结词，条件的前项当作一个附加前提题，最后推出条件的后项。例4P∨Q,P→R,Q→S,┐S→R(1)┐SP(附加前提)(2)Q→S

P(3)┐S→┐QT(2)(3)(4)┐QT(1)(3)(4)(5)P∨QP(6)┐Q→PT(5)(6)(7)PT(4)(6)(7)(8)P→RP(9)RT(7)(8)(9)练习A→(B→C),┐D∨A,BD→C用CP规则和直接证明方法P

→(Q

∨R)，┐S→┐Q,P∧┐SR用直接证明和反正法应用应用1一家航空公司，为了保证安全，用计算机复核飞行计划。每台计算机能给出飞行计划正确或有误得回答。由于计算机也可能发生故障，因此采用三台计算机同时复核。由所给答案，再根据“少数服从多数”的原则作出判断，试将结果用命题公式表示。解设C1,C2和C3分别表示三台计算机的答案。S表示判断结果，根据题意写出真值表。C1C2C3S11111101101110000111010000000000

S

(C1∧C2∧C3)∨(C1∧C2∧┐C3)∨(C1∧┐C2∧C3)∨(┐C1∧C2

∧C3)应用2如果我上街了，我一定去新华书店。我没上街，所以我没去新华书店。推理是否正确。应用3一个公安人员审查一件盗窃案，根据如下查得的事实判断真正的作案人。张三或李四盗窃了笔记本电脑；若张三做案，则作案时间不会是午夜之前；若是李四证词是真的，则午夜时屋里有灯光；若李四证词是假，则作案时间发生在午夜之前；午夜时午里灯灭了。结论李四第二章谓词逻辑

§2.1、谓词与客体一谓词引入命题逻辑不足：解决不了牛顿三段论问题。例所有人都会死的，牛顿是人，所以牛顿会死的。P:人都要死的，Q:牛顿是人，R:牛顿会死的。P∧QR命题推理分析：无法揭示命题内部的结构和属性；无法表达命题之间的逻辑关系和特征。因此需要功能更强的逻辑语言。二、谓词与客体1、谓词逻辑：由命题定义（反映判断的陈述句）将命题分解成主语和谓语两部分。2、客体（主语）1）客体变元：用小写字母x,y等表示。2)客体常元：用小写字母a,b等表示。3）客体域：客体变元的取值范围。3、谓词(谓语)用P（）表示。1)一元谓词：P(x)描述客体的性质。例：张三是大学生。P(a)，a=张三2)多元谓词：P(x,y)描述客体之间的关系。张三和李四是同学。P(a,b)，a=张三，b=李四4、命题函数：简单命题函数和复合命题函数。命题函数不是命题，只有客体变元取特定值时才能是命题。三、量词1、全称量词（）1）（）表示客体域内所有的客体。（）P(x)2）意义：3）特性谓词当客体域用谓词表示时则称特性谓词，在全称量词里特性谓词以条件前项引入。例1：所有计算机学院的学生都是大学生。M(x)：计算机学院的学生，P(x)：x是大学生。()(M(x)→P(x))设客体域为计算机学院的学生，则翻译为：()P(x)例2：所有人都会死的。M(x)：x是人，P(x)：x会死的。()(M(x)→P(x))设客体域是人，x会死的。（）P(x)：

2、存在量词()1)()表示客体域内部分客体。()P(x)2)3)特性谓词以引入。例3：有些计算机学院的学生喜欢唱歌。M(x)：计算机学院的学生，P(x)：x喜欢唱歌。

设客体域为计算机学院的学生。()P(x)例4：有些人不怕死。M(x)：x是人，P(x)：x不怕死。设客体域为人，则翻译为：()P(x)

3、量词的作用域(辖域)1）指导变元/作用变元：量词后面紧跟的变元。2）约束变元与自由变元3）约束变元改名规则对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，及该量词作用域中所出现的该变元，在公式的其余部分不变。换名时不能引起新的重名。4）自由变元代入规则对于谓词公式中的自由变元，可以做代入，代入时需对公式中出现该自由变元的每一处进行。用以代入的变元与原公式中所有变元的名称不能相同。例5

2.2、谓词公式与翻译一、谓词翻译1、公式翻译成自然语言2、自然语言符号化1)确定谓词（一元，二元）；2）选择量词，注意量词顺序不能随意颠倒；3）若客体域以特性谓词形式给出，注意特性谓词引入方式；4）由于谓词刻画程度不一样，翻译结果不唯一。例1：所有人都会犯错误。M(x)：x是人，P(x)：x犯错误例2：并不是所有人都会犯错误。M(x)：x是人，P(x)：x犯错误。例3：有些人会犯错误。M(x)：x是人，P(x)：x犯错误。例4：没有人会犯错误。M(x)：x是人，P(x)：x犯错误。例5：有些人不犯错误。M(x)：x是人，P(x)：x犯错误。例6：所有人都不会犯错误。总结：例4和例6不仅语义等价而且公式也等价。例2和例5不仅语义等价而且公式也等价。例7：有些女孩比所有男孩都聪明。M(x)：x是女孩，P(x)：x是男孩，R(x，y):x比y聪明。

例8：所有学生都喜欢某些明星。M(x)：x是学生，P(x)：x是明星，R(x，y):x喜欢y。例9：存在唯一一个自然数x,满足x+5=7N(x):x是自然数,P(x):x+5=7,G(x,y):x=y设客体域为N练习自然语言符号化所有有理数都是实数，某些有理数是整数，因此某些实数是整数。任何人如果喜欢步行，他就不喜欢乘汽车，每一个人或者喜欢乘汽车或者喜欢骑自行车。有的人不爱骑自行车，因而有的人不爱步行。每个大学生不是文科生就是理工科学生，有的大学生是优等生，小张不是理工科学生，因而如果小张是大学生，他就是文科学生。有的兔子比所有乌龟跑得快。并不是所有的兔子都比乌龟跑得快。§2.3谓词公式与解释一、谓词的合式公式（合式公式）⑴原子公式（n元谓词公式）是合式公式；⑵若A是谓词公式，则┐A也是合式公式；⑶若A、B是谓词公式，则A∧B,A∨B,A→B,AB也是合式公式；⑷若A是谓词公式，则A,A也是合式公式;(5)只有经过有限次地应用规则(1)、(2)、(3)和(4)所得到的公式是合式公式。以后简称谓词公式。二、谓词公式解释1、基本概念封闭公式谓词公式中不含自由变元，简称闭式。对谓词公式变项用确定谓词代替（等值代换）即对谓词公式解释。谓词公式类型：永真式（重言式），永假式（矛盾式），可满足式2、谓词公式解释非空个体域D；D中一部分特定元素(用来解释个体常项)；D上一些特定函数(用来解释出现的函数变项)；D上一些特定谓词(用来解释谓词变项)。例1D={2,3};a=2;f(2)=3,f(3)=2;F(2)=0,F(3)=1G(2,3)=G(3,2)=1,G(2,2)=G(3,3)=0(1)(F(x)∨G(x,a))(F(3)∨G(3,2))∧(F(2)∨G(2,2))(1∨1)∧(0∨0)1∧00(2)(F(f(x))∧G(x,f(x)))(F(f(2))∧G(2,f(2)))∨(F(f(3))∧