复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）20/32

数理逻辑 数理逻辑的内容可分为五部分 逻辑演算 ■证明论 公理集合论 递归论 模型论 介绍命题逻辑和谓词逻辑的逻辑演算

数理逻辑  数理逻辑的内容可分为五部分：  逻辑演算  证明论  公理集合论  递归论  模型论  介绍命题逻辑和谓词逻辑的逻辑演算

命题和联结词 命题是指客观上能够判断真或假的陈述 句。 n(2)3+4=8。 (4)明天是晴天。 (5)本句话是错的。 (7)走,到图书馆去! (8)你明天下午出去吗? (9)2既是素数又是偶数 (10雪不是白的

命题和联结词  命题 是指客观上能够判断真或假的陈述 句。  (2)3 + 4 = 8。  (4)明天是晴天。  (5)本句话是错的。  (7)走，到图书馆去！  (8)你明天下午出去吗?  (9)2既是素数又是偶数。  (10)雪不是白的

■基本的,原始的命题称为原子命题 n语句(9可由“2是素数”与“2是偶数” 这两个命题用“与”这个词联结组合而 成 由更小的命题组合而成的命题称为复合 命题。 ■将几个命题联结组合起来的方式称为张 结词

 基本的，原始的命题称为原子命题  语句(9)可由“2是素数”与“ 2是偶数”  这两个命题用“与”这个词联结组合而 成  由更小的命题组合而成的命题称为复合 命题。  将几个命题联结组合起来的方式称为联 结词

常用的联结词有下列5个: (1)联结词“非”,记为“-”,表示“否定 的意思 (2)联结词“合取”,记为“”,表示“并 且”的意思。 ■(③3)联结词“析取”,记为“√”,表示“或” 的意思。 (4)联结词“蕴含”,记为“→”,表示 “如果,则.”的意思。 (5)联结词“等价”,记为“<”,表示 “当且仅当”的意思

 常用的联结词有下列5个:  (1)联结词“非”，记为“”，表示“否定” 的意思。  (2)联结词“合取”，记为“”，表示“并 且”的意思。  (3)联结词“析取”，记为“”，表示“或” 的意思。  (4)联结词“蕴含”，记为“→”，表示 “如果…，则…”的意思。  (5)联结词“等价”，记为“”，表示 “当且仅当”的意思

■由于命题是能够判断真假的陈述句,因 此给定一个命题就可确定其是真或假。 真和假是命题的值或真/值。 P为真当且仅当P为假; aP∧Q为真当且仅当P、Q皆为真; PvQ为真当且仅当P、Q中至少有一个为 真 P→Q除P为真且Q为假这种情况外,皆为 真 PQ为真当且仅当P、Q有相同真假值

 由于命题是能够判断真假的陈述句，因 此给定一个命题就可确定其是真或假。 真和假是命题的值(或真假值)。  P为真当且仅当P为假；  PQ为真当且仅当P、Q皆为真；  PQ为真当且仅当P、Q中至少有一个为 真；  P→Q除P为真且Q为假这种情况外，皆为 真；  PQ为真当且仅当P、Q有相同真假值

把组成一个复合命题的若干个原子命题 用符号表示,那么就可用这些符号和联 结词符号一起来表达该复合命题,这样 的方式称为命题符号化 例:李明今天下午看电影或者看录像”, 用P表示“李明今天下午看电影”,用Q 表示“李明今天下午看录像”,则原语 句应表示成:PQ 明天中午12:00,他或者去北京或者去广州 ■只有在天晴时,我们才去郊游

 把组成一个复合命题的若干个原子命题 用符号表示，那么就可用这些符号和联 结词符号一起来表达该复合命题，这样 的方式称为命题符号化。  例: 李明今天下午看电影或者看录像”， 用P表示“李明今天下午看电影”，用Q 表示“李明今天下午看录像”，则原语 句应表示成：PQ  明天中午12:00,他或者去北京或者去广州  只有在天晴时，我们才去郊游

利用联结词我们可以把日常的命题写成 符号串那么是否任何符号串都是某个日 常命题的符号化呢?回答是否定的 例如:p,∧q就不是 那么什么样的符号串才是合适的呢? 通常采用递归的方式: p,q是命题则→p,p∧q,pq,p>q,p>q也 是命题 我们希望能够找到其他方式来定义

 利用联结词,我们可以把日常的命题写成 符号串.那么是否任何符号串都是某个日 常命题的符号化呢?回答是否定的.  例如:p,q就不是.  那么什么样的符号串才是合适的呢?  通常采用递归的方式:  p,q是命题,则p,pq,pq, p→q,pq也 是命题  我们希望能够找到其他方式来定义

如果把联结词看作为运算把p2q看作为日 常生活这个集合中的元素那么利用运算 的封闭性,可以发现所谓p,∧q不对应某 个日常命题实质是p,q不在日常生活 这个集合中 因此我们就可以考虑能否从代数角度来 引进有关逻辑的概念这就需要引进泛代 数的概念

 如果把联结词看作为运算,把p,q看作为日 常生活这个集合中的元素,那么利用运算 的封闭性, 可以发现所谓p,q不对应某 个日常命题,实质是p,q不在日常生活 这个集合中.  因此我们就可以考虑能否从代数角度来 引进有关逻辑的概念.这就需要引进泛代 数的概念

第十九章泛代数 §1引言

第十九章 泛代数 §1 引言

A上的n元运算实质上就是A→A的函数, t:AnA,n称为函数t的元。 ■例如:在群G中,可以定义一个一元运 算:G→G用来求逆元,即i(a)=a1。 集合A上的0元运算为从集合A(由于A0 只有一个元素,规定A={}到集合A的 函数,即t:{⑦}→A。 A上的0元运算实质上是唯一对应了A中 就是给出了A中的一个元素

 A上的n元运算实质上就是An→A的函数， t: An→A，n称为函数t的元。  例如：在群G中，可以定义一个一元运 算i: G→G用来求逆元，即i(a)=a-1 。  集合A上的0元运算为从集合A0 (由于A0 只有一个元素, 规定A0={})到集合A 的 函数，即t0 : {}→A。  A上的0元运算实质上是唯一对应了A中 的某个元素，即给出A上的一个0元运算 就是给出了A中的一个元素