离散数学-1-8推理理论

2
第1章 数理逻辑
例 1.1 - 1 下述都是命题: (1) 今天下雪; (2) 3+3=6; (3) 2 是偶数而 3 是奇数; (4) 陈涉起义那天，杭州下雨; (5) 较大的偶数都可表为两个质数之和。
3
第1章 数理逻辑
以上命题中，(1)的真值取决于今天的天气; (2)和(3)是真; (4)已无法查明它的真值，但它是或真或假的， 故将它归属于 命题; (5)目前尚未确定其真假，但它是有真值的，应归属于 命题。
6
第1章 数理逻辑
从以上分析，我们得出他必须既非说谎也不是讲真话。 这 样，断言“我正在说谎”事实上不能指定它的真假，所以不是命 题。 这种断言叫悖论。
若一个命题已不能分解成更简单的命题，则这个命题叫原子 命题或本原命题。 例1.1 - 1中(1)、(2)、(4)、(5)都是本原命 题，但(3)不是，因为它可写成“2 是偶数”和“3 是奇数”两 个命题。
译为P∧Q，但“林芬和林芳是姐妹”就不能翻释成两个命题的合
取，它是一个原子命题。
34
第1章 数理逻辑
1.1.3 命题变元和命题公式 通常，如果P代表真值未指定的任意命题，我们就称P为命题
变元; 如果P代表一个真值已指定的命题，我们就称P为命题常元。 但由于在命题演算中并不关心具体命题的涵义，只关心其真假值， 因此，我们可以形式地定义它们。
以“真”、“假”为其变域的变元，称为命题变元; T和F称 为命题常元。
35
第1章 数理逻辑
习惯上把含有命题变元的断言称为命题公式。 但这样描述 过于表面，它没能指出命题公式的结构。 因为不是由命题变元、 联结词和一些括号组成的字符串都能成为命题公式，因此在计算 机科学中常用以下定义。
单个命题变元和命题常元叫原子公式。 由以下形成规则生 成的公式叫命题公式(简称公式):

21
一、自然推理系统P
自然推理系统P由三个部分组成：
1.
字母表：命题变项符号；联结词符号；括
号和逗号。
2.
命题公式。
3.
推理规则。
22
二、推理规则
(1) 前提引入规则 (2) 结论引入规则 (3) 置换规则 (4) 假言推理规则 AB A \B (5) 附加规则 A \AB (6) 化简规则 AB \A (7) 拒取式规则 AB B \A (8) 假言三段论规则 AB BC \AC
30
四、附加前提证明法
例6：用附加前提证明法构造证明下面的推
理： 2是素数或合数。若2是素数，则 2 是 无理数。若 2 是无理数，则4不是素数。所 以，如果4是素数，则2是合数。
31
四、附加前提证明法
解： 设 p：2是素数， q：2是合数，
r： 2 是无理数，s：4是素数 推理形式结构 前提：pq, pr, rs 结论：sq
40
五、归谬法
解：命题符号化
p：小张守第一垒 q：小李向B队投球
r：A队取胜
s：A队成为联赛第一名
推理的形式结构如下：
( p q ) r , r s , s , p 结论： q
前提：
41
五、归谬法
证一：归谬法（略） 证二：直接法 ① r s 前提引入
② s
③r
前提引入
5
前提是有限个公式的集合，而不是序列 。
二、推理的有效性
A1A2… Ak
0 0
B
0 1
推理的有效性 有效 有效
1
1

0
有效
无效
6
二、推理的有效性
定义：若对于每组赋值，当 A1A2…Ak

P 0 0 1 1 Q 0 1 0 1 P∧Q 0 0 0 1
例4
设P：我们去看电影。Q：房间里有十张桌子。则
P ∧ Q表示“我们去看电影并且房间里有十张桌子。”
10
3. 析取“∨”（相容或）[讲解教材P3-5关于或]
4. 定义1.3
由命题P和Q利用“∨”组成的复合命题，称 为析取式复合命题，记作“P∨Q”（读作“P或Q”）。 当且仅当P和Q至少有一个取值为真时，P∨Q取值为真。
练习1-1
1. 判断下列语句哪些是命题，若是命题，则指出其真值。
（1） （2） 只有小孩才爱哭。 X+6=Y ( 是 假 ) ( 不是 ) (是 真) ( 不是 )
（3）
银是白的。
（4） 起来吧，我的朋友。 2． 将下列命题符号化
（1） 我看见的既不是小张也不是老李。 解 令P：我看见的是小张；Q：我看见的是老李。 则该命题可表示为¬ P∧¬ Q （2） 如果晚上做完了作业并且没有其它的事，他就会 看电视或听音乐。 解 令 P：他晚上做完了作业；Q：他晚上有其它的事； R：他看电视； S：他听音乐。 则该命题可表示为（P∧¬ Q）→（R∨S）
28
1.3 等值演算
• 定义1.10 设A和B是两个命题公式, 若等价式A↔B 是重言式，则称公式A 和B等值，记为A B,称 AB为等 值式。
• 注意： （1）符号“”与“↔”的区别与联系 “”不是联结词，AB不表示一个公式， 它表示两个公式间的一种关系，即等值关系。 “↔”是联结词，A↔B是一个公式。 AB 当且仅当 A↔B 是永真公式。
1 0 1 0 1 0 1 0
0 0 1 1 1 1 1 1
0 0 0 1 0 0 0 1
1 1 0 1 0 0 0 1

离散数学-----命题逻辑逻辑：是研究推理的科学。

公元前四世纪由希腊的哲学家亚里斯多德首创。

作为一门独立科学，十七世纪，德国的莱布尼兹(Leibniz)给逻辑学引进了符号, 又称为数理逻辑(或符号逻辑)。

逻辑可分为：1. 形式逻辑（是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。

）→数理逻辑（是用数学方法研究推理的形式结构和规律的数学学科。

它的创始人Leibniz，为了实现把推理变为演算的想法，把数学引入了形式逻辑中。

其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。

）2. 辩证逻辑（是研究反映客观世界辩证发展过程的人类思维的形态的。

）一、命题及其表示方法1、命题数理逻辑研究的中心问题是推理,而推理的前提和结论都是表达判断的陈述句，因而表达判断的陈述句构成了推理的基本单位。

基本概念：命题：能够判断真假的陈述句。

命题的真值：命题的判断结果。

命题的真值只取两个值:真（用T(true)或1表示）、假（用F(false)或0表示）。

真命题：判断为正确的命题，即真值为真的命题。

假命题：判断为错误的命题，即真值为假的命题。

因而又可以称命题是具有唯一真值的陈述句。

判断命题的两个步骤：1、是否为陈述句；2、是否有确定的、唯一的真值。

说明：（1）只有具有确定真值的陈述句才是命题。

一切没有判断内容的句子，无所谓是非的句子，如感叹句、祁使句、疑问句等都不是命题。

（2）因为命题只有两种真值，所以“命题逻辑”又称“二值逻辑”。

（3）“具有确定真值”是指客观上的具有，与我们是否知道它的真值是两回事。

2、命题的表示方法在书中，用大写英文字母A,B,…,P,Q或带下标的字母P1,P2,P3 ,…,或数字(1),*2+, …,等表示命题，称之为命题标识符。

命题标识符又有命题常量、命题变元和原子变元之分。

命题常量：表示确定命题的命题标识符。

命题变元：命题标识符如仅是表示任意命题的位置标志，就称为命题变元。