(北大)数理逻辑.ppt

(北大)数理逻辑.ppt离散数学
1
数理逻辑部分
命题逻辑
2
第1章命题逻辑
命题符号化及联结词
命题公式及分类
等值演算
对偶与范式
推理理论
3
命题符号化及联结词
命题与真值
原子命题
复合命题
命题常项
命题变项
联结词
4
命题与真值
命题: 能判断真假的陈述句
命题的真值: 判断的结果
真值的取值: 真与假
真命题: 真值为真的命题
假命题: 真值为假的命题
注意:
、祈使句、疑问句都不是命题;
;

5
例:下列句子中哪些是命题?
(1) 是无理数.
(2) 2 + 5 =8.
(3) x + 5 > 3.
(4) 你有铅笔吗?
(5) 这只兔子跑得真快呀!
(6) 请不要讲话!
(7) 我正在说谎话.
真命题
假命题
真值不确定
疑问句
感叹句
祈使句
悖论
(3)~(7)都不是命题
6
例:下列句子中那些是命题?
(8)明年10月1日是晴天.
(9) 地球外的星球上也有人.
(10)11+1=100.
(8)、(9)的真值虽然现在还不知道,但它的真值是唯一的,因而是命题。
(10)在二进制中为真,在十进制中为假,需根据上下文才能确定其真值,因而不是命题。
7
命题的分类
(原子命题)
简单构成的命题(不能分解成更简单的陈述句)
简单命题的真值是确定的,又称为命题常项或命题常元

由简单命题与联结词按一定规则复合而成的命题
(命题变元)
真值不确定的陈述句,如:x+3>5
注意:命题变元不是命题!
8
简单命题符号化
用小写英文字母 p, q, r, …,pi,qi,ri (i≥1)表示
简单命题
用“1”表示真,用“0”表示假
例如,令
p: 是有理数,则 p 的真值为 0
q:2 + 5 = 7,则 q 的真值为 1
命题变项:
也用小写英文字母 p, q, r, …,pi,qi,ri (i≥1)表示
9
联结词与复合命题
“”
定义设p为命题,复合命题“非p”(或“p的否定”)称
为p的否定式,记作p,符号称作否定联结词
p 为真当且仅当p为假
“∧”
定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称
为p与q的合取式,记作p∧q,∧称作合取联结词,并规
定 p∧q为真当且仅当p与q同时为真
注意:描述合取式的灵活性与多样性
分清简单命题与复合命题
10