大连理工大学软件学院离散数学第一章命题逻辑-2nd

《大连理工大学软件学院离散数学第一章命题逻辑-2nd》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学第一章命题逻辑回顾原子命题复合命题逻辑否定Negation逻辑合取Conjunction析取Disjunction单条件Conditional双条件Doubleconditional异或ExclusiveorXor联接词真值表▽PQ¬PP∧QP∨QP→QPQPQ00100110011011011000100111011110ØÙÚ®«▽2/371.3命题变元和合式公式命题变元用P表示一个抽象的命题，而不是一个具体的命题时，称它为以表示任意命题命题变元不能确定真值合式公式由命题变元、逻辑联接词及圆括号构成

2、合式公式合式公式递归定义（1）单个命题变元是合式公式。（2）如果A是合式公式，那么¬A是合式公式。（3）如果A和B均是合式公式，那么A∧B,A∨B,A→B和AB都是合式公式。（4）当且仅当有限次的应用(1)、(2)、(3)条规则由逻辑联结词、圆括号所组成的有意义的符号串是合式公式。上面的定义成为递归定义法，(1)称为递归定义基础，（2）和（3）称为递归定义的归纳，（4）称为递归定义的界限。3/371.3命题变元和合式公式判断下列字符串哪些是合式公式，哪些不是？P，¬P，PQ4/371.3命题变元和合式公式几

3、个概念：命题命题变元命题公式——合式公式命题公式vs命题5/37命题公式：没有真假意义命题：有真假意义真值表设P是一个命题公式，P1，P2，…，Pn是出现在P中的所有命题变元，对于这些命题变元真值指派的每一种可能的组合，都能唯一的确定P的真值。将这些真值列成一个表，称为命题公式P的真值表。给出命题公式的真值表6/3700001011011011011110应用系统规范性说明在说明硬件系统和软件系统时，将自然语言语句翻译成逻辑表达式是很重要的一部分。系统和软件工程师从自然语言中提取需求，生成精确、无二义的规范说明

4、，这些说明可以作为系统开发的基础。7/378/37应用确定下列系统规范性说明是否一致“诊断消息存放在缓冲区中或是被重传”“诊断消息没有存储在缓冲区中”“如果诊断消息存储在缓冲区中，那么它被重传”解：P：诊断消息存储在缓冲区中Q：诊断消息被重传三个命题分别是P∨Q，¬P,P→QPQP∨Q¬PP→Q00011011111010011100逻辑难题侦探调查了罪案了四位证人，从证人的话侦探得出的结论是：如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁说的不可能都是真话；园丁和杂役不可能都在说谎；如果杂役说真话，那

5、么厨师在说谎。能判定四个人分别在说谎还是说真话吗？解：首先假设M:男管家说真话C:厨师说真话G:园丁说真话Z:杂役说真话9/37符号化并构造真值表：ＭＣＧＺＭＣ(ＣＧ)ＧＺＺＣ００００　１　　０　　０　　　１０００１　１　　１　１　　１００１０　１　　１　　１　　　１００１１　１　　１　　１　　１０１００　１　　１　　０　　　１１１１１　１　　０　　０　　　０10/37公式的等价性定义：设A、B是两个命题公式，P1，P2，，Pn是出现在A和B中的所有命题变元。如果对于P1，P2，，Pn的2n个

6、真值指派的每一组，公式A和B的真值相同，则称A和B等价。记作AB。判断公式等价方法：真值表法等价公式变换11/37真值表判定公式等价性利用真值表证明公式等价性证明与是相互等价的。001101001000111112/37基本的等价公式13/37基本的等价公式14/37基本的等价公式15/3716/37公式的等价性下面我们给出子公式，及关于公式等价的一个定理定义：设A是一个公式，A´是A的一部分，且A´也是一个命题公式，则称A´是A的子公式。替换规则：设A是公式A的子公式，B是一命题公式且AB，将A中

7、的A用B来取代，则所得到的是一个新公式，记为B，且AB。例1（P(QR))(PQR)P证明：左边(P(QR))(P(QR))P((QR)(QR))PTP.公式的等价性17/37公式的等价性18/3719/37将语句“情况并非如此，如果他不来，那么我也不去”化简。P：他来。Q：我去。符号化为：化简：化简后最终意思：我去了，他没来。公式的等价性如果电话号码数据库是打开的，那么监督程序被置于关闭状态，只要系统不在初态。P：电话号码数据库是打开的Q:监督程序被置于关

8、闭状态R:系统不在初态R(PQ)20/371.4重言式和永真蕴含式一个命题公式若含有N个变元，则应有2n种组合，所以证明两个命题公式的等价，当命题变元多时使用真值表法是不现实的，只能采用上面的等价变换的方法。有两种特殊的命题公式值得一提，即不依赖变元的真值指派总是取值为T的公式（称为永真式），不依赖变元的真值指派总是取值为F的公式（称为永假式），其余则情况则为可满足的式子。21/3