离散数学第1章命题公式与翻译-真值表与等价公式.ppt

第一章 命题逻辑第2讲 课程回顾 练习 判断是否命题？ 黄岛是个大城市。 我们要努力学习。 练习 只有具有确定真值的陈述句才是命题。 黄岛是个大城市。是命题，其真值为假。 我们要努力学习。 祈使句，不是命题。 ??????? 第一章 命题逻辑 第2讲 §1—3 命题公式与翻译  §1—4真值表与等价公式 §1—3 命题公式与翻译 一、合式公式 前面已经提到，不包含任何联结词的命题叫做原子命题，至少包含一个联结词的命题称作复合命题。 设P和Q是任意两个命题，则┐P， P∨Q，(P∨Q）→(F∨Q），P (Q ∨┐P)等都是复合命题。 若P和Q是命题变元，则上述各式均称作命题公式。P和Q称作命题公式的分量。 定义1-3.1 命题演算的合式公式(wff)，规定为： (1)单个命题变元本身是一个合式公式。 (2)如果A是合式公式，那么┐A是合式公式。 (3)如果A和B是合式公式，那么(A∧B)，(A∨B)， (A→B）和(A B)都是合式公式。 (4)当且仅当能够有限次地应用(1)、(2)、(3)所得到 的包含命题变元，联结词和括号的符号串是合式公式。 按照定义，下列公式都是合式公式： ┐(P∧Q），┐(P→Q)，(P→(P∨┐Q)， (((P→Q）∧(Q→R)) （S T)) 而 (P→Q）→(∧Q)，(P→Q，(P∧Q）→Q） 等都不是合式公式。 联结词的优先级 目的：减少使用括号的数量 约定：命题公式外层的括号可以省略； 联结词的优先级：┐、∧、∨、→、?。 利用加括号的方法可以提高优先级。 二、命题的翻译 翻译（符号化） 有了联结词的合式公式概念，我们可以把自然语言中的有些语句，翻译成数理逻辑中的符号形式。 把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。 符号化应该注意下列事项： ① 确定给定句子是否为命题。 ② 句子中联结词是否为命题联结词。 ③ 要正确地表示原子命题和适当选择命题联结词。 例题 解 若设 P：他聪明。 Q：他用功。 在自然语言中这个“既……又……”显然与“且”的意义一样，故本例可记为： P∧Q 。 解 这里“虽……但……”这个词不能用前述联结词表达，但其实际意义是：他聪明且不用功。若设 P：他聪明。 Q：他用功。 本例可表示为： P∧┐Q 解 P：上海到北京的14次列车是下午五点半开。 Q：上海到北京的14次列车是下午六点开。 在本例中，汉语的“或”是不可兼或，而逻辑联结词∨是“可兼或”，因此不能直接对两命题析取。构造表如表1-3.1所示。 解 这个命题的意义，亦可理解为：如果你 不努力则你将失败。 若设 P：你努力。 Q：你失败。 本例可表示为： ┐P→Q 解 这个命题的意义是： 张三可以做这件事，并且李四也可以做这件事。 若设 P：张三可以做这事。 Q：李四可以做这事。 本例可表示为： P∧Q 例题 解 找出各原子命题，并用命题符号表示： A：我们要做到身体好。 B：我们要做到学习好。 C：我们要做到工作好。 P：我们要为祖国四化建设而奋斗。 思考 A：我们要做到身体好。 A：我们要努力学习。 祈使句，不是命题。 从上面的例子中可以看到，自然语言中的一些联结词，如：“与”“且”“或”“除非…则…”等等都各有其具体含义，因此需分别不同情况，根据实际含义，翻译成适当的逻辑联结词。 为了便于正确表达命题间的相互关系，有时也常常采用列出“真值表”的方法，进一步分析各原命题，以此寻找逻辑联结词，使原来的命题能够正确地用形式符号予以表达。 §1—4 真值表与等价公式 1.真值表 定义1-4.1 在命题公式中，对于分量（命题变元）指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。 例题2 给出(P∧Q）∧┐P的真值表。 解 （见表1-4.2） 例题3 给出(P∧Q）∨（┐P∧┐Q）的真值表。 解