就理迴辑 逻辑学:研究思维(或推理)的形式结构和规 律的学科。利用数学方法研究思维(或推理)的形式 结构和规律的学科,称作数理逻辑。 数理逻辑的基本内容:命题逻辑(演算) 谓词逻辑。它们对电子元件设计和性质分析 对逻辑程序设计语言的研制具有十分重要的 意义。 2021/2/24 离散数学
2021/2/24 离散数学 1 逻辑学:研究思维(或推理)的形式结构和规 律的学科。利用数学方法研究思维(或推理)的形式 结构和规律的学科,称作数理逻辑。 数理逻辑 数理逻辑的基本内容:命题逻辑(演算)、 谓词逻辑。它们对电子元件设计和性质分析, 对逻辑程序设计语言的研制具有十分重要的 意义
第一章命题逻 §11侴题与腺结 512命题公式及其赋值 513等值演算 514联结词的完备集 515对偶与范式 516推理理论 2021/2/24 离散数学
2021/2/24 离散数学 2 第一章 命题逻辑 §1.1 命题与联结词 §1.2 命题公式及其赋值 §1.3 等值演算 §1.4 联结词的完备集 §1.5 对偶与范式 §1.6 推理理论
81.1命题静号化及联結词 一、命题的概念 命题:能判断真假的陈述句。这种判断只有两种 可能,一种是正确的判断,一种是错误的 判断。 命题真值:判断为正确的命题称其命题真值为真(1); 判断为错误的命题称其命题真值为假(0); 命题是具有唯一真值的陈述句。 2021/2/24 离散数学
2021/2/24 离散数学 3 一、命题的概念 命题:能判断真假的陈述句。这种判断只有两种 可能,一种是正确的判断,一种是错误的 判断。 §1.1 命题符号化及联结词 命题真值:判断为正确的命题称其命题真值为真(1) ; 判断为错误的命题称其命题真值为假(0) ; 命题是具有唯一真值的陈述句
例1判断下列旬子中哪些是命题。 (1)4是素数。 (2)2+3=5。 (3)雪是黑色的 (4)3能被2整除。 是) (5)2050年元旦是晴天。[是) (6)5x+1>11。 (否 (7)这朵花真美丽呀 (否) (8明天下午开会吗? 5) (否 (9)我正在说假话。 (否) 2021/2/24 离散数学
2021/2/24 离散数学 4 例1 判断下列句子中哪些是命题。 (1) 4是素数。 (2) 2 + 3 = 5。 (3) 雪是黑色的。 (4) 3能被2整除。 (5) 2050年元旦是晴天。 (6) 5x + 1 > 11。 (7) 这朵花真美丽呀! (8) 明天下午开会吗? (9) 我正在说假话。 (是) (是) (是) (是) (是) (否) (否) (否) (否)
解题思想:判断一个句子是否为命题,首先看它 是否为陈述句,其次看它的真值是否唯一。 2021/2/24 离散数学
2021/2/24 离散数学 5 解题思想:判断一个句子是否为命题,首先看它 是否为陈述句,其次看它的真值是否唯一
与命题相关的几个概念 1、简单命题(原子命题): 命题为简单的陈述句,不能分解成更简单 的句子。一般用小写的英文字母p,q,r,…表示。 2、命题常项(命题常元): 由于简单命题的真值确定,故又称之为命题常项 或命题常元。 如例1中的陈述句(1)(2)(3)(4)(5)。 2021/2/24 离散数学
2021/2/24 离散数学 6 二、与命题相关的几个概念 1、简单命题(或原子命题): 命题为简单的陈述句,不能分解成更简单 的句子。一般用小写的英文字母p, q, r, …表示。 2、命题常项(或命题常元): 由于简单命题的真值确定,故又称之为命题常项 或命题常元。 如例1中的陈述句(1) (2) (3) (4) (5)
、与命题相关的几个概念(续) 3、命题变项(命题变元): 真值可以变化的简单陈述句,但它不是命题也可 以用qr等表示 如例1中的陈述句6)(5x+1>1) 、复合命题: 由简单命题用联结词联结而成的命题。 命题逻辑主要就是研究复合命题。 5、命题的符号化 用符号来表示命题。 2021/2/24 离散数学
2021/2/24 离散数学 7 二、与命题相关的几个概念(续) 3、命题变项(或命题变元): 真值可以变化的简单陈述句,但它不是命题,也可 以用p,q,r等表示。 如例1中的陈述句(6) (5x + 1 > 11)。 4、复合命题: 由简单命题用联结词联结而成的命题。 命题逻辑主要就是研究复合命题。 5、命题的符号化: 用符号来表示命题
三、联结词 先看一个例子 例2:判断下列命题是否为复台命题,说出其联结词 (1)3不是偶数 非) (2)2是偶素数。 (且) (3)2或4是素数。 (4)如果2是素数,3也是素数。(如果,则) (5)2是素数当且仅当3也是素数。(当且仅当) 2021/2/24 离散数学
2021/2/24 离散数学 8 三、联结词 先看一个例子: 例2:判断下列命题是否为复合命题,说出其联结词。 (1) 3不是偶数。 (2) 2是偶素数。 (3) 2或4是素数。 (4) 如果2是素数,3也是素数。 (5) 2是素数当且仅当3也是素数。 (非) (且) (或) (如果…,则…) (当且仅当)
三、联结词(续) 常见的基本联结词 1、否定联结词“-”,读作“非”。 复合命题“非”称作p的否定式,记作"-p” →p为真当且仅当为假。 在例2(1)中,设表示“3是偶数”,则p表示“3 不是偶数”。显然,p真值为0,→p真值为1 2021/2/24 离散数学 9
2021/2/24 离散数学 9 三、联结词(续) 常见的基本联结词: 1、否定联结词“ ”,读作“非”。 复合命题“非p ”称作p 的否定式,记作“ p ” 。 p 为真当且仅当p 为假。 在例2(1)中,设p 表示“3是偶数”,则 p 表示“3 不是偶数”。显然,p 真值为0, p 真值为1
三、联结词(续) 2、合取联结词“∧”,读作“合取” 复合命题"p并且q”称作与q的合取式,记“p∧q” PAq为真当且仅当与q同时为真。 在例2(2)中,设p表示“2是素数”,q表示“2是偶 数”,则p∧q表示“2是偶素数”。因为p和q的真值 均为1,所以pA∧q的真值为1。 联结词“既.又.”,“不但.而且.”,“虽然.但 是”等,都可符号化为A。 2021/2/24 离散数学 10
2021/2/24 离散数学 10 三、联结词(续) 2、合取联结词“ ”,读作“合取”。 复合命题“ p并且q ”称作p 与q 的合取式,记“ p q ” 。 p q 为真当且仅当p 与q 同时为真。 在例2(2)中,设 p 表示“2是素数”, q 表示“2是偶 数” ,则 p q 表示“2是偶素数”。因为 p和q 的真值 均为1, 所以 p q 的真值为1 。 联结词“既…又…”,“不但…而且…”,“虽然…但 是…”等,都可符号化为