离散数学第一章命题逻辑知识点总结.doc

.
实用文档.
数理逻辑局部
第1章 命题逻辑
命题符号化及联结词
命题: 判断结果惟一的陈述句
命题的真值: 判断的结果
真值的取值: 真与假
真命题: 真值为真的命题
假命题: 真值为假的命题
注意: 感慨句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。
简单命题(原子命题)：简单陈述句构成的命题
复合命题：由简单命题与联结词按一定规那么复合而成的命题
简单命题符号化
用小写英文字母 p, q, r, … ,pi,qi,ri (i≥1〕表示
简单命题
用“1〞表示真，用“0〞表示假
例如，令 p： 是有理数，那么 p 的真值为 0
q：2 + 5 = 7，那么 q 的真值为 1
联结词与复合命题
“Ø〞
定义 设p为命题，复合命题 “非p〞〔或 “p的否认〞〕称
为p的否认式，记作Øp. 符号Ø称作否认联结词，并规定Øp 为真当且仅当p为假.
“∧〞
定义 设p,q为二命题,复合命题“p并且q〞(或“p与q〞)称为p与q的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p与q同时为真
注意：描述合取式的灵活性与多样性
分清简单命题与复合命题
例 将以下命题符号化.
(1) 王晓既用功又聪明.
(2) 王晓不仅聪明，而且用功.
(3) 王晓虽然聪明，但不用功.
(4) 张辉与王丽都是三好生.
(5) 张辉与王丽是同学.
解 令 p：王晓用功，q：王晓聪明，那么
(1) p∧q
(2) p∧q
(3) p∧Øq.
令 r : 张辉是三好学生，s :王丽是三好学生
(4) r∧s.
(5) 令 t : 张辉与王丽是同学，t 是简单命题 .
说明:
.
实用文档.
(1)~(4)说明描述合取式的灵活性与多样性.
(5) 中“与〞联结的是两个名词，整个句子是一个简单命题.
“∨〞
定义 设 p,q为二命题，复合命题“p或q〞称作p与q的析取式，记作p∨q. ∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.
例 将以下命题符号化
(1) 2或4是素数.
(2) 2或3是素数.
(3) 4或6是素数.
(4) 小元元只能拿一个苹果或一个梨.
(5) 王晓红生于1975年或1976年.
解 令 p:2是素数, q:3是素数, r:4是素数, s:6是素数,
那么 (1), (2), (3) 均为相容或.
分别符号化为: p∨r , p∨q, r∨s,
它们的真值分别为 1, 1, 0.

而 (4), (5) 为排斥或.
令 t :小元元拿一个苹果，u:小元元拿一个梨，
那么 (4) 符号化为 (t∧Øu) ∨(Øt∧u).
令v :王晓红生于1975年,w:王晓红生于1976年,那么 (5) 既可符号化为 (v∧Øw)∨(Øv∧w), 又可符号化为 v∨w , 为什么?
“®〞
定义 设 p,q为二命题，复合命题 “如果p,那么q〞 称作p与q的蕴涵式，记作p®q，并称p是蕴涵式的前件，q为蕴涵式的后件. ®称作蕴涵联结词，并规定，p®q为假当且仅当 p 为真 q 为假.
p®q 的逻辑关系：q 为 p 的必要条件
“如果 p，那么 q 〞 的不同表述法很多：
假设 p，就 q
只要 p，就 q
p 仅当 q
只有 q 才 p
除非 q, 才 p 或 除非 q, 否那么非 p.
当 p 为假时，p®q 为真
常出现的错误：不分充分与必要条件
.
实用文档.
“«〞
定义 设p，q为二命题，复合命题 “p当且仅当q〞称作p与q的等价式，记作p«q. ««q为真当且仅当p与q同时为真或同时为假.
说明:
(1) p«q 的逻辑关系:p与q互为充分必要条件
(2) p«q为真当且仅当p与q同真或同假
.
实用文档.
联结词优先级:( ),Ø, Ù, Ú, ®, «
同级按从左到右的顺序进行
以上给出了5个联结词：Ø, Ù, Ú, ®, «，组成