离散数学[2]-数理逻辑基本概念

一、什么是数理逻辑

  • 逻辑学是探索、阐述和确立有效推理原则的学科,最早由古希腊学者亚里士多德创立。
  •  亚里士多德在逻辑学上最重要的工作是提出 三段论学说。
  •  只要符合三段论的推理就是正确的。
  •  一个三段论就是一个包括有大前提、小前提和结论三个部分的论证。

三段论有许多不同种类,其中最著名的例子:

  1. 凡是人都会死(大前提)
  2. 苏格拉底是人(小前提)
  3. 所以:苏格拉底会死(结论)

逻辑学还是以自然语言来表述,可能会因为自然语言的模糊性损害其准确和权威。 用数学的方法研究关于推理、证明等问题的学科就叫做数理逻辑(也叫做符号逻辑)。

数理逻辑的萌芽

  • 利用计算的方法来代替人们思维中的逻辑推理过程,这种想法早在十七世纪就有人提出过。
  • 莱布尼茨(Leibniz)就曾经设想能不能创造一种“通用的科学语言”,可以把推理过程象数学一样利用公式来进行计算,从而得出正确的结论。
  • 由于当时的社会条件,他的想法并没有实现。但是他的思想却是现代数理逻辑部分内容的 萌芽,从这个意义上讲,莱布尼茨的思想可以说是数理逻辑的先驱。

数理逻辑的开创

1847年,英国数学家布尔G.Boole发表了《逻辑的数学分析》,建立了“布尔代数”。布尔创造了一套符号系统,利用符号来表示逻辑中的各种概念。还建立了一系列的运算法则,利用代数的方 法研究逻辑问题,初步奠定了数理逻辑的基 础

数理逻辑的大发展

1884年,德国数学家弗雷格Frege出版了《数论的基础》一书,在书中引入量词的符 号,使得数理逻辑的符号系统更加完备。 美国人皮尔斯Peirce,他也在著作中引入了更多逻辑符号。从而使现代数理逻辑最基本的理论基础逐步 形成,成为一门独立的学科。

数理逻辑的四大分支

  • 数学史上的第三次大危机是由于发现了集合论的逻辑悖论引起的。
  • 悖论的提出,促使许多数学家去研究集合论的无矛盾性问题,从而产生了数理逻辑的一个重要分支—公理集合论。
  • 为了研究数学系统的无矛盾性问题,需要以数学理论体系的概念、命题、证明 等作为研究对象,研究数学系统的逻辑结构和证明的规律,这样又产生了另一 个分支—证明论。
  •  递归论主要研究可计算性的理论,它和计算机的发展和应用有密切的关系。
  •  模型论主要是研究形式系统和数学模型之间的关系。

我们课程中介绍的是数理逻辑各个分支的共同基础部分:命题演算谓词演算

二、命题(proposition)

  • 命题是数理逻辑中最基本的概念
  • 对确定的对象作出判断的陈述句称作命题
  • 如果判断正确,称命题真(true),否则称命题假(false)
  • “真、假”是命题的属性,称为“真值”

什么样的语句是命题?

  • 雪是白的。
  • 2+2=5。
  • 您贵姓? (No)
  • x+y<10。 (No,x和y不是确定的对象)

三个识别要点:

  • 陈述句
  • 判断
  • 确定的对象

识别命题

再来看看几个语句

  • 袁世凯称帝那天北京下雨。
  • 大于2的偶数均可分解为两个素数之和。
  • 请把脚挪一下! (No,祈使句,不是陈述句)
  • 谁拿走了桌上的杯子? (No,不是陈述句)
  • 2是偶数而且3也是偶数。

  • 真值是命题的固有属性

  • 不过,是否知道真值,能否知道真值是另一回事。

  • 悖论(自相矛盾)不能作为命题。如“这句 话是错的”

  • 命题非真即假,不能兼有之,也不能不真不假

  • 非真即假,是一个基本假设?

三、排中律(Law of Excluded Middle)

  • 排中律是传统逻辑的基本规律之一
  • “是非之间,必居其一”。
  • 墨子也说过:“辩也者,或谓之是,或谓之 非,当者胜也“——《经说下》。
  • 任一事物在同一时间里具有某属性或者不具 有某种属性,而无其它可能。

反证法与排中律

  • 传统数学证明中经常采用的“反证法”即利用了排中律:
  • 要证明一个命题为真,并不直接证明;
  • 而是假设命题不为真,推出矛盾;
  • 根据排中律,此命题非假,即真;
  • 从而间接证明命题为真。

反证法的著名范例

  • 欧几里德:素数有无穷多个 假设命题不真,那么素数就是有限个,把它们按照大小顺序排列起来,记为a1<a2<a3..<an 接下来,我们构造一个新的数 N=a1a2a3*…*an+1。 所有的这些素数ai(i=1,2…n)都不是N的因子 这样,就有两种可能:

1,N有另外的素数真因子

2,N本身就是一个素数 显然,N比所有的ai都要大,无论哪种情况,我们都 发现了ai之外的素数。 这跟假设矛盾,根据排中律,命题就是真的!

直觉主义对排中律的质疑

  • 但直觉主义认为,数学的基础和出发点是人类直觉所构造;
  • 数学理论可靠性依赖于心智上的可构造性;
  • 对命题真假的确定必须给出构造性证明;
  • 而反证法虽然对命题的反面推出矛盾;
  • 但不意味着命题本身具有构造性证明。

  • 直觉主义否定排中律的普遍有效性;

  • 从有穷事物中概括出来的排中律,不能贸然推广到对无穷事物适用;

  • 涉及到有穷事物全体的命题,可以通过逐个检验来验证其真假;

  • 但一旦涉及到无穷事物,一般是无法来做此种检验的。

四、命题符号化

原子命题和复合命题

我们回来再看看刚才的一个命题:

  • 2是偶数而且3也是偶数。
  • 这是由两个小命题和一个“而且”连接而成
  • 联结词“而且”将两个命题组合成新命题, 并产生了新的真值。

这样,我们有了三个新概念:

  • 逻辑联结词(logical connectives):连接命题,对真值进行运算的词;
  • 原子命题(atom proposition):不含有逻辑联结词的命题;
  • 复合命题(compound proposition):包含了原子命题和逻辑联结词的命题。

复合命题

逻辑联结词有哪些呢? 我们来看看更多的复合命题:

  • 雪不是白的
  • 今晚我去看书或者看电影
  • 你去了教室,我去了食堂(省略了“且”) 〉
  • 如果天气好,那么我去车站接你
  • 偶数a是素数,当且仅当a=2

接下来,我们要回到数理逻辑创立的初衷: 对逻辑和思维过程进行形式化,使之象算术那样简单明了,确切无误。

如何把命题变成“算式”?

  1. 形式化的第一步:抽象(abstraction): 仅关注命题的本质属性:真值,而抛弃其丰富的内涵; 仅关注逻辑联结词的本质属性:对真值的运算,而抛弃多变的语言表达方式。
  2. 然后是将这两者都变成符号,以规则相连接 真命题用t表示,假命题用f表示 原子命题一般用p, q, r, s或pi, qi, ri, si表示 逻辑联结词用特殊符号来表示: 并非(not):¬ 并且(and):∧;或(or):∨ 如果……那么……(if … then …):→ 当且仅当(if and only if):↔

符号的定义

  • 命题的真值
  • 为真(true)用1表示,为假(false)用0表示
  • 真命题的真值为1,假命题真值为0
  • 逻辑联结词用真值表来定义
  • 真值表列出了原子命题的真值组合(0、1) 〉 以及经过联结词作用后的真值

  • 符号体系对于数学乃至科学体系的发展至关 重要

  • 简洁清晰的符号能使人的抽象思维效率飞跃。

  • 想象一下全中文、竖排的微分方程?

  • 形式主义者甚至认为,数学就是符号变换的游戏。

五、联结词

1. 否定词(negation) “并非”(not):¬

¬p的逻辑关系为p不成立 如果p表示命题“雪是白的”,那么“雪不 是白的”应该表示为¬p

注意在包含多个对象判断的命题否定时,其 意义的变化:

  • “天鹅都是白的”,其否定并不是“天鹅都 不是白的”
  • 而是“天鹅不都是白的”或“并非所有天鹅 都是白的”

2. 合取词(conjunction) “并且”(and): ∧

p∧q的逻辑关系为:p和q同时成立

  • 自然语言中许多表示并列的连接词都 可以符号化为“∧”:
  • “既…又…”,“不但…而且…”, “虽然…但是…”
  • p:张三聪明;q:张三用功 张三既聪明又用功:p∧q 张三不仅聪明,而且用功: p∧q

张三虽然不太聪明,但他很用功:¬p∧q 张三不是不聪明,而是不用功: p∧¬q

我们看到形式化确实通过抽象,抛弃了原语句的很多内容:

  • 抛弃了倾向、语气、价值判断等,
  • 只留下命题的本质属性:真值

3.析取词(disjunction)”或”(or):∨

p∨q的逻辑关系为p和q中至少一个成立

自然语言中的“或”可以符号化为∨,但有时要注意原命题中的“或”可能表示排斥性 选择:

  • 李四学过德语或法语(相容或):p∨q p:李四学过德语,q:李四学过法语
  • 张三生于1972年或1973年(排斥或): p∨q p:张三生于1972年,q:张三生于1973年
  • 人固有一死,或重于泰山,或轻于鸿毛(排斥或) (p∧¬q)∨(¬p∧q):异或p:人死重于泰山,q:人死轻于鸿毛

4.蕴涵词(implication)”如果…那么…”(if…then…): →

p→q的逻辑关系是,p是q的充分条件,或者说q是p的必要条件

p→q中的p称作蕴涵前件,q称作蕴涵后件

  • 自然语言中的许多条件连接词都可以符号化 为→,但是要注意条件的顺序 “只要…就…”,“如果…那么…”,“只有…才…”
  • 自然语言中,条件语句一般都具有内在的联系,而数理逻辑中的蕴涵则仅是命题的一种 连接,不一定具有什么内在联系
  • 在蕴涵式中,只有p为真q为假时,p→q才 为假和(¬p∨q)真值表相同

  • 如果天气好,那么我去接你:p→q p: 天气好,q: 我去接你 只有p真q假算是食言

  • 只要2是偶数,雪就是黑的:p→q p: 2是偶数,q: 雪是黑的 p为真,q为假,本命题为假

  • 只有天黑了,夜猫子才出来活动:p→q 注意:p: 夜猫子出来活动,q: 天黑了

5.双向蕴含词(two-way implication)”当且仅当”(if and only if):↔

p↔q的逻辑关系是p与q互为充分必要条件,在p,q真值相同的情况下, p ↔q为真

  • 圆1和圆2面积相等当且仅当它们的半径相等: p↔q p: 圆1和圆2面积相等,q: 圆1和圆2半径相等 不管p和q的真值如何, p↔q为真
  • 2+3=5当且仅当5是有理数:p↔q p:2+3=5,q:5是有理数
  • 除非网断了,否则他一定QQ在线:p↔¬q p:网断了,q:他QQ在线

两个组合的例子 如果3是合数,则4是素数,并且如果 4是素数,则它不能被2整除:

〉 p:3是合数
〉 q:4是素数
〉 r:4能被2整除
〉 (p→q)∧(q→¬r)

如果2+3>5当且仅当5是合数,则2 和3都是有理数

〉 p:2+3>5
〉 q:5是合数
〉 r:2是有理数
〉 s:3是有理数
〉 (p↔q)→(r∧s)

符号组合的规则

〉 把符号组合起来,看起来开始象一个算式了
〉 算式的组合不是随意的;
〉 那么逻辑符号组合的规则是什么?
〉 逻辑符号组合成的算式具有什么意义?

六、命题公式

命题公式(proposition formula)的组成成分

  • 命题常元(propositionconstants) 表示具体命题及表示常命题的p, q, r, s 等和t,f
  • 命题变元(propositionvariables) 以“真,假”或者“1,0”为取值范围的 变量,仍用p, q, r, s等表示
  • 命题公式(propositionformula) 由命题常元、变元和联结词组成的形式更为 复杂的命题

命题公式( proposition formula )定义

  1. 命题常元和命题变元是命题公式,特别的称作原子公式或原子
  2. 如果A,B是命题公式,那么(¬A), (A∧B), (A∨B), (A→B), (A↔B)也是命题公式
  3. 只有有限步引用上述两条所组成的符号串是命题公式

命题公式简称做公式,采用大写A,B,C等表示

注意大小写符号的差别(A、B、C和p、q、r、s、t、f) 命题公式的这种定义方法称作归纳定义,在集合论中将会详细讨论归纳定义

命题公式的例子

根据定义:

(¬(p→(q∧r))) 是命题公式

以下式子都不是命题公式:

(qp) (p1∧(p2∧… p→r∧s

严格按照定义的命题公式太繁琐,简化约定

  1. 公式最外层的括号一律可以省略
  2. 约定逻辑联结词的优先级,进一步减少括号

逻辑联结词优先级

  • 联结词{¬,∧,∨,→,↔}中, ¬是一元联结词,其它都是连接两个命题的二元联结词
  • 我们定义优先级为:¬, [∧∨], →, ↔
  • 除非有括号,否则按照优先级从高到低,从左到右的次序结合

¬p∨q 等同于 ((¬p)∨q)

p→q∧r→s 并不是 ((p→q)∧(r→s)),其实是 ((p→(q∧r))→s)

命题公式的意义

  • 命题公式是一个按照归纳定义构成的字符串
  • 其形式上具有既定的规则
  • 那么其内容上具有什么意义呢?

七、真值函数

命题公式与真值函数(truth function)

  • 如果将联结词看作逻辑运算符,那么包含命题变元p1, p2, …pn的公式A 可以看作是关于p1, p2, …pn的一个真值函数
  • 每个变元的取值范围是{0,1}
  • 真值函数值的取值范围也是{0,1}

赋值

对任意给定的p1, p2, …pn的一种取值状况组合,称为指派或者赋值 (assignments)

  • 赋值用希腊字母α,β等表示
  • 对于每个赋值,公式A均有一个确定的真值
  • 这样,命题公式在形式上是一个规则 的字符串,内容上则对应一个真值函 数

真值表

(真值表略)

  • 对于所有可能的赋值,公式A的真值可以用真值表来确定
  • 当A(p1, p2, …pn)中包含有k个联结词时,公式A的真值表应为2n行、 k+n列
  • 前n列是所有变元的取值组合
  • 最后1列是公式A的真值

成真赋值和成假赋值

  • 当公式A对赋值α为真时 称α是A的成真赋值,或者α弄真A 〉 记做α(A)=1
  • 反之 称α是A的成假赋值,或者α弄假A 〉 记做α(A)=0

八、命题形式化

自然语言句子的形式化

由自然语言表述的命题,经过抽象,可以形式化为命题公式

  • 首先确定原子命题
  • 其次确定联结词
  • 最后处理命题之间的联结关系及顺序

  • 我和他既是兄弟又是同学(p:我和他是兄弟,q:我和他是同学) 形式化命题:p∧q

  • 狗急跳墙(p:狗急了,q:狗跳墙) 形式化命题:p→q

  • 如果他不来那么是生病了或者不在本地(p:他来,q:他生病,r:他在本地) 形式化命题:¬p→(q∨¬r) *无论是否下雨,我都去上学(p:天下雨,q:我去上学) 〉 形式化命题:(p→q)∧(¬p→q) 或者:(p∧q)∨(¬p∧q) 或者:q

自然语言句子的形式化:注意事项

  1. 要善于确定原子命题,如兄弟这个概念就无需进一步拆分;
  2. 要善于识别自然语言中的联结词;
  3. 对于涉及多个对象进行否定的否定词位置要准确;
  4. 不能省略必要的括号,另外,为了提高公式 的可读性,要保留一些括号;
  5. 有时候语句的形式化结果不是唯一的,可能具有不同形式,但是逻辑上是等价的。

参考资料

陈斌 北京大学地球与空间科学学院 gischen@pku.edu.cn

https://www.coursera.org/learn/dmathgen/home/info

个人公众号,比较懒,很少更新,可以在上面提问题:

更多精彩,请移步公众号阅读:

Sam avatar
About Sam
专注生物信息 专注转化医学