第1章命题逻辑 ●数理逻辑是用数学方法来硏究推理的形式结构和 推理规律的数学学科。 ●现代数理逻辑可分为逻辑演篁、证明论、公理集 合论、递归论和模型论。 ●本课程介绍的是数理逻辑最基本的内容,也是与 计算机科学关系最为密切的:命题逻辑和谓词逻 辑(一阶逻辑)
第1章 命题逻辑 ⚫ 数理逻辑是用数学方法来研究推理的形式结构和 推理规律的数学学科。 ⚫ 现代数理逻辑可分为逻辑演算、证明论、公理集 合论、递归论和模型论。 ⚫ 本课程介绍的是数理逻辑最基本的内容，也是与 计算机科学关系最为密切的：命题逻辑和谓词逻 辑（一阶逻辑）
主要内容 1.1命题符号化及联结词 1.2命题公式及分类 1.3等值演算 14联结词全功能集 1.5对偶与范式 1.6推理理论
主要内容 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 联结词全功能集 1.5 对偶与范式 1.6 推理理论
1.1命题符号化及联结词 ●命题:能判断真假的陈述句。 ●真值:一个命题表达的判断结果称为命题的真值 命题的真值有“真”和“假”两种,分别用Tue T、1(真和 False、F、0(假)来表示。真值为真的 命题称为真命题,真值为假的命题称为假命题。 任何命题的真值是惟一的。 ●注:一切没有判断内容的句子,无所谓是非的句子, 如感叹句、疑问句、祈使句等都不是命题
1.1 命题符号化及联结词 ⚫ 命题：能判断真假的陈述句。 ⚫ 真值：一个命题表达的判断结果称为命题的真值。 命题的真值有“真”和“假”两种，分别用True、 T、1(真)和False、F、0(假)来表示。真值为真的 命题称为真命题，真值为假的命题称为假命题。 任何命题的真值是惟一的。 ⚫ 注: 一切没有判断内容的句子，无所谓是非的句子， 如感叹句、疑问句、祈使句等都不是命题
例1 1.2是素数。 2.雪是黑色的。 3.2+3=5 4.明年十月一日是晴天。 5.这朵花多好看呀! 6.3能被2整除 7.明天下午有会吗? 8.请关上门! 9Xy>5
例1： 1. 2是素数。 2. 雪是黑色的。 3. 2+3=5 。 4. 明年十月一日是晴天。 5. 这朵花多好看呀！ 6. 3能被2整除. 7. 明天下午有会吗？ 8. 请关上门！ 9. x+y>5
命题判断的关键: 1是否是陈述句 2真值是否是唯一的 ●简单命题(原子命题):不能分解为更简单的陈述句。 简单命题又称为命题常项或命题常元。对于真值可以变化的简单陈述句称 为命题变项或命题变元。 复合命题:由联结词把几个原子命题联结起来的命题
命题判断的关键： 1.是否是陈述句； 2.真值是否是唯一的。 ⚫ 简单命题（原子命题）：不能分解为更简单的陈述句。 ⚫ 简单命题又称为命题常项或命题常元。对于真值可以变化的简单陈述句称 为命题变项或命题变元。 ⚫ 复合命题：由联结词把几个原子命题联结起来的命题
表示法 表示法 例子 有关概念 简单命题PqE…,p2是素数 命题符号化:将命题 P2qr2…q雪是黑色的的号放在该命题的 前面 命题常项同上 同上 真值确定的简单命题 (常元) 命题变项同上|px+y>5 真值可以变化的筒单 (变元) 陈述句 复合命题|p∧q2是素数和偶数 注:一个符号表示的是命题常项还是命题变项由上下文决定
表示法： 表示法 例子 有关概念 简单命题 p,q,r,…, pi ,qi ,ri ,… p: 2是素数 q:雪是黑色的 命题符号化：将命题 的符号放在该命题的 前面 命题常项 （常元） 同上 同上 真值确定的简单命题 命题变项 （变元） 同上 p: x+y>5 真值可以变化的简单 陈述句 复合命题 p∧q 2是素数和偶数 注：一个符号表示的是命题常项还是命题变项由上下文决定
例2:将下列各命题符号化 1.3不是偶数 2.2是素数和偶数 3.林芳学过英语或日语. 4.如果角A和角B是对顶角,则角A等于角B
例2：将下列各命题符号化 1. 3不是偶数. 2. 2是素数和偶数. 3. 林芳学过英语或日语. 4. 如果角A和角B是对顶角,则角A等于角B
命题联结词 常用的逻辑联结词有五种:否定联结词、合取 联结词、析取联结词、蕴涵联结词和等价联结词。 否定联结词 表1.1 定义11设p为命题,则p的否 定是一个复合命题,记作:vp,读P 作“非p”或“p的否定”。-为否 定联结词。v为真当且仅当p为假。 【例】否定下列命题 p:王强是一名大学生。 p:王强不是一名大学生
1. 否定联结词 定义1.1 设p为命题，则p的否 定是一个复合命题，记作：¬p，读 作“非p ”或“ p的否定” 。 ¬为否 定联结词。¬p为真当且仅当p为假。 表1.1 p ¬p 0 1 1 0 【例】否定下列命题。 p：王强是一名大学生。 ¬p：王强不是一名大学生。 •命题联结词 常用的逻辑联结词有五种：否定联结词、合取 联结词、析取联结词、蕴涵联结词和等价联结词
2.合取联结词 表12 定义1,2设p和q均为命题, 则D和的合取是一个复合命题, g p/q 记作p∧q,读作p与q”或"p 合取q”。∧为合取联结词 p∧q为真当且仅当p和q同时为 真 【例】设p:北京成功举办了第29届夏季奥运会 q:今年10月1日是我国国庆60周年。 则p∧q:北京成功举办了第29届夏季奥运会并且今年10 月1日是我国国庆60周年
2. 合取联结词 定义1.2 设p和q均为命题， 则p和q的合取是一个复合命题， 记作p∧q，读作“ p与q ”或“ p 合取q ” 。 ∧为合取联结词。 p∧q为真当且仅当p和q同时为 真。 表1.2 p q p∧q 0 0 0 0 1 0 1 0 0 1 1 1 【例】设 p：北京成功举办了第29届夏季奥运会。 q：今年10月1日是我国国庆60周年。 则p∧q：北京成功举办了第29届夏季奥运会并且今年10 月1日是我国国庆60周年
例3:将下列各命题符号化 李平既聪明又用功 2.李平虽然聪明,但不用功 3.李平不但聪明,而且用功 4.李平不是不聪明,而是不用功
⚫ 例3：将下列各命题符号化 1. 李平既聪明又用功. 2. 李平虽然聪明，但不用功. 3. 李平不但聪明，而且用功. 4. 李平不是不聪明，而是不用功