数理逻辑-(2)命题逻辑
马殿富
北航计算机学院
马 帅
dfma@
计算机学院
-9
mashuai@
提纲
基本概念：集合、函数、归纳、数理逻辑
1.1命题和联结词
1.2公式和真值赋值
1.3等值演算
1.4对偶定理
1.5联结词的完全集 计算机学院
1.6范式
1.7逻辑推论
计算机学院 2
2
集合
定义 ：一些对象聚集为一个整体，称为集合 ，这些
对象称为集合的元素。
元素与集合的关系
• a是集合S 的元素，记为a S
• a不是集合S 的元素，记为a S
集合的特点 ：唯一性、无序性、确定性
集合的表示 ： 计算机学院
• 空集：
• 有穷集合：枚举法，S={x , x , …, x }
1 2 n
• 无穷集合：描述法{ x | x是自然数}
计算机学院 3
3
集合的外延/内涵
外延原则与概括原则
• 外延原则：一个集合由它的元素唯一地确定。
• 概括原则：每一性质(或谓词) 产生一个集合。
集合外延
• 集合所包含的元素全体。
集合内涵
• 集合元素所共有的性质。 计算机学院
示例- 非负偶数集合
• 外延—{ 0, 2, 4 , …}
• 内涵—{x | x是被2整除的自然数 }
计算机学院 4
4
集合的关系
包含关系：
• 如果集合A 的元素都是集合B 的元素，则称A
为B 的子集，记为A B
真包含关系 ：A B
不包含关系 ：A B
等价关系 ： 计算机学院
• 如果集合A和集合B包含相同元素，则称A和
B相等，记为A=B
计算机学院 5
5
集合的操作
集合的并：
• A ∪ B
集合的交 ：
• A ∩ B
集合的差 ：
• A –B 或者 A \ B 计算机学院
计算机学院
