离散数学与---命题 .pptVIP

离散数学 主讲教师：王 影 电话 信箱:Teacher_wy@163.com 第一章 命题逻辑 命题与合式公式 逻辑等值式 范式 推理理论 命题与合式公式 命题的定义：自然语言中能描述判断的陈述句；自然语言中有确切的肯定与否定的陈述句；具有唯一真值的陈述句。 例子：2不是素数。 木星上有水。 金字塔是外星人修建的。 今天是五四青年节。 张红和王兰都看过这部电影。 如果我是你，我决不答应。 命题的真值 真：1 ；T，t ；True－－真命题 假：0 ；F，f ；False－－假命题 命题是不考虑其内在的逻辑联系的 如果5＋3＝2，则鸟会飞。 命题的基本类型 简单命题：作为语句来讲是不可再分的（原子命题） 复合命题：从句（状语从句、表语从句、定语从句、宾语从句等），并列语句等，关键是联结词。复合命题是使用联结词将简单命题连接起来的命题。 5种联结词 ?P 或 not 、否、不 P∧Q and、和、与 P∨Q or、或、要么 P→Q if…then、如果…那么 P?Q 当仅当、充要条件 ?P，P∧Q，P∨Q ?P是P的否定式，not是一元联结词； P∧Q是P、Q的合取式；and P∨Q是P、Q的析取式。or 说明：“∧” 属于二元(binary)运算符. 合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。 自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”、 “…和…”、 “…与…”等都可以符号化为∧ 。 将下列命题符号化. (1) 李平既聪明又用功. (2) 李平虽然聪明, 但不用功. (3)李平不但聪明,而且用功. (4)李平不是不聪明,而是不用功. 解: 设 P:李平聪明. Q:李平用功. 则 (1) P∧Q (2) P∧ ┐Q (3) P∧Q (4) ┐(┐P)∧ ┐Q 例如: (1) 李敏和李华是姐妹。 （2）李敏和张华是朋友。 注意：不要见到“与”或“和”就使用联结词∧ ！ 例1. P: 天津是一个城市. Q: 3是偶数. 于是: ┐P: 天津不是一个城市. ┐Q: 3不是偶数. 例2. P:苏州处处清洁. Q:这些都是男同学. ┐P:苏州不处处清洁 (注意,不是处处不清洁). ┐Q:这些不都是男同学. 在电路图中的应用 但是并不是所有的或者都是“∨ ” 灯泡坏了或者开关坏了。 老王或者小李可以做这个工作。 今天下课后，我东行或者西行。 明天8点我上图书馆或者上教室。 （2）林芳学过英语或法语。 （可兼或） 设P：林芳学过英语。 Q：林芳学过法语。 则上述命题可符号化为： P ∨ Q （3）派小王或小李中的一人去开会。（排斥或） 设P：派小王去开会。Q：派小李去开会。 则上述命题可符号化为：(P∧? Q) ∨(? P∧Q) （4）人固有一死，或重于泰山或轻于鸿毛.(排斥或） （5）ab=0, 即a=0 或 b=0. （可兼或） 由此可见, “P ∨ Q”表示的是“可兼或”. 异或的真值表 蕴涵词 蕴涵词(Implication)：?，P ?Q，如果P，那么Q。IF P，then Q。P、Q的蕴涵式，P称为蕴涵式的前件，Q称为蕴涵式的后件。 P ?Q为假，只有在前件为1，后件为0时。 蕴涵式P → Q 如果我是你，我肯定不会答应。 如果下雪了，我们就去堆雪人。 P：下雪了；Q：我们去堆雪人； 原命题为： P → Q 现在，1.下雪了，并且我们堆了雪人，即是P、Q＝1；原命题为真； 2.下雪了，但是我们没有堆雪人，原命题为假； 3.没有下雪，…… 蕴涵式P → Q的说明 以下命题