离散数学_命题逻辑

离散数学第2章 命题逻辑

2.1 命题逻辑概述 2.2 命题及命题连结词 2.3 命题公式及其赋值

2.4 命题公式描述实际问题

2.5 命题公式等值演算 2.6 公式的范式 2.7 命题逻辑的推理理论

2.8 命题逻辑的归结演绎推理

2.1 命题逻辑概述 【逻辑学】 形式逻辑产生于古希腊(亚里士多德),研究了 概念、 判断、三段论推理、证明与反驳的方法等重要课题。 【数理逻辑】 是现代逻辑，数理逻辑也称符号逻辑， 是用数学方法研究逻辑的一门学科。 创始人：十七世纪 莱布尼兹 寻找一种通用的、精确的符号语言，以此基础建立一种 逻辑演算，以便能用计算来解决争辩。 十八世纪 布尔 布尔运算 十九世纪 弗雷格 谓词演算 二十世纪 罗素 命题演算与谓词演算的完整的系统

命题逻辑 经典命题逻辑 非经典命题逻辑 一阶逻辑(谓词逻辑)

2.2 命题及命题联结词 形式语言：不属于自然语言，严谨的语法规则。 例如数学语言、程序设计语言。例如：我的车没琐 这张照片里是小明和小刚的爸爸 张三告诉李四他英语考试挂了

2.2 命题及命题联结词 定义2.1 能够判断真假的陈述句称为命题。

关键：陈述句、有唯一的真值 例2.1 请问下列语句中哪些是命题？哪些不是命题？ √ 北京是中国的首都。 √ 2+3=5. C语言是一种计算机程序设计语言。 √ 如果温度达到零度以下，则水会结成冰。 √ 鸟会飞，但鸡不会飞。 √ 猪八戒是猪么？ × × 香格里拉真是太美丽了！ × 杨七是高个子。

判断下列句子是否为命题√ (1) 4是素数。 √ (2)

5 是无理数 。

假命题 真命题

× (3) x 大于 y,其中x和y是任意的两个数。 √ (4) 火星上有水。 √ (5) 2050年元旦是晴天。 × (6) π大于 × (8)

2吗？ × (7) 请不要吸烟！这朵花真美丽啊！

理解“命题”概念应注意的问题 一个语句的真假常常与情境(时间和地点)、判断 技术、判断能力有关。 2012年1月1日是晴天 火星上有生命 我正在说假话

2012年是世界末日 以上3个都是命题。悖论

每个命题的真假称之为命题的“真值”。 真值可以表示为 (真、假)(T、F) (0、1) 例如： (1) 8是素数。 (2)5 是无理数 。

真值为0 真值为1

简单命题与复合命题 定义2.2 一个命题若不能分解为更简单的命题形式， 则称该命题为一个简单命题，或原子命题。 命题一般表示为p,q,r……

定义2.3 由命题联结词和其他命题组成的命题称为复 合命题。例如：

猪八戒不是猪孙悟空和唐僧都是神仙、

如果唐僧从西天取回真经，就会是神仙

命题连接

词----否定联结词 设p是一个命题，则 p 也是一个命题，读作 “非”,表示命题的否定p 0 1 p 1 0

否定联结词是一个一元运算. 例如 p :上海是一个大城市. p :上海不是一个大城市.

命题连接词----合取联结词 设p,q为二命题，复合命题 “p并且q” 称为p与 q的合取式，记作p q,称 为合取联结词. p q为真当且仅当p与q同时为真. p 0 0 1 1 q 0 1 0 1 p q 0 0 0 1

例如 ： p:2 2=5 q:雪是黑的. p q:2 2=5并且雪是黑的.

命题连接词----析取联结词 设p,q为二命题，复合命题 “p或q”称为p、q的 析取式，记作 p q ,称 为析取联结词. p q为真当且仅当p与q中至少一个为真. p 0 0 1 1 q 0 1 0 1 p q 0 1 1 1 r:今天下雨 s:今天刮风 r s:今天下雨或者刮风

命题连接词----蕴涵联结词 设p,q都是命题，则p q也是一个命题，称为蕴涵 式，读作“如果p,则q”; p称为前件， q称为后件。 p q为假当且仅当p为真q为假. p 0 0 1 1 q 0 1 0 1 p q 1 1 0 1

P:今天是星期三q:今天有英语课 p q表示如果今天是星期三 则今天有英语课

命题连接词----等价联结词 设p,q都是命题，则p q也是一个命题，称为与 的等价式，读作“p与q同真假”;

p 0 0 1 1

q 0 1 0 1

p q 1 0 0 1

u:燕子飞回北方 v:春天来了 u v:燕子飞回北方 春天来了.