离散数学课件 第一章 命题逻辑-2nd

《离散数学课件 第一章 命题逻辑-2nd》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、离散数学大连理工大学软件学院陈志奎教授办公室：综合楼411，Tel：87571525实验室：教学楼A318/A323，Tel：87571620/24Mobile:13478461921Email:zkchen@dlut.edu.cnzkchen00@hotmail.com1/33回顾•原子命题•复合命题–逻辑否定Negation–逻辑合取Conjunction–析取Disjunction–单条件Conditional–双条件Doubleconditional–异或ExclusiveorXor–联接词¬∧∨→↔▽•真值表PQ¬PP∧QP∨QP→QPQ

2、PQ▽0010011001101101100010011101111021.3命题变元和合式公式•原子命题–原子•命题变元–用P表示一个抽象的原子，而不是一个具体的命题时，称它为命题变元–命题变元可以表示任意命题，不能确定真值•合式公式–由命题变元、逻辑联接词及圆括号构成合式公式•合式公式递归定义（1）单个命题变元是合式公式。（2）如果A是合式公式，那么¬A是合式公式。（3）如果A和B均是合式公式，那么()AB→和()AB↔都是合式公式。（4）当且仅当有限次的应用(1)、(2)、(3)条规则由逻辑联结词、圆括号所组成的有意义的符号串是合式公式。上面

3、的定义成为递归定义法，(1)称为递归定义基础，（2）和（3）称为递归定义的归纳，（4）称为递归定义的界限。3/331.3命题变元和合式公式•判断下列字符串哪些是合式公式，哪些不是？P，¬P，P∧Q(PQ→→∧)()Q(PQ→((PQQR→∧→↔↔)())(ST)(PPQ→(∧¬))4/331.3命题变元和合式公式几个概念：命题命题变元命题公式——合式公式命题公式vs命题（命题公式与命题的关系）5/33真值表•设P是一个命题公式，PPP是出1，2，…，n现在P中的所有命题变元，对于这些命题变元真值指派的每一种可能的组合，都能唯一的确定P的真值。将这些

4、真值列成一个表，称为命题公式P的真值表。•给出命题公式¬∨∧((PQP))的真值表PQPQ∨())PQP∨∧¬∨∧((PQP))000010110110110111106/33应用•系统规范性说明–在说明硬件系统和软件系统时，将自然语言语句翻译成逻辑表达式是很重要的一部分。–系统和软件工程师从自然语言中提取需求，生成精确、无二义的规范说明，这些说明可以作为系统开发的基础。7/33应用•确定下列系统规范性说明是否一致“诊断消息存放在缓冲区中或是被重传”“诊断消息没有存储在缓冲区中”“如果诊断消息存储在缓冲区中，那么它被重传”•解：–P：诊断消息存储在

5、缓冲区中–Q：诊断消息被重传–三个命题分别是P∨Q，¬P,P→QPQP∨Q¬PP→Q000110111110100111018/33逻辑难题•侦探调查了罪案了四位证人，从证人的话侦探得出的结论是：如果男管家说的是真话，那么厨师说的也是真话；厨师和园丁说的不可能都是真话；园丁和杂役不可能都在说谎；如果杂役说真话，那么厨师在说谎。能判定四个人分别在说谎还是说真话吗？•解：首先架设M:男管家说真话C:厨师说真话G:园丁说真话Z:杂役说真话9/33公式的等价性•定义：设A、B是两个命题公式，P，P，12…，P是出现在A和B中的所有命题变元。n如果对于P，P

6、，…，P的2n个真值指派12n的每一组，公式A和B的真值相同，则称A和B等价。记作A⇔B。•显然，要判断两个公式是否等价，用真值表法即可以实现。但是当命题变元多时这种方法是不方便的。例如两个公式若含有4个变元，则真值表要列出24行。所以，我们一般不采用这种方法，而是采用等价变换的方法。下面列出的是常用的一组等价变换公式。10/33真值表判定公式等价性•利用真值表证明公式等价性–证明PQ↔与PQPQ∧∨¬∧¬是相互等价的。PQPQ↔PQPQ∧∨¬∧¬001101001000111111/33基本的等价公式EPQQP∨⇔∨1EPQQP∧⇔∧交换律

7、2EPQQP↔⇔↔3EPQRPQR(∨∨⇔∨∨)()4EPQRPQR(∧∧⇔∧∧)()结合律5EPQRPQR()↔↔⇔↔↔()6EPQR∧∨⇔∧∨∧()()PQPR()7EPQR∨∧⇔∨∧∨()()PQPR()分配律8EP()→→⇔→→→QR()PQ()PR912/33基本的等价公式EPP¬¬⇔双重否定律10E()¬∧PQ⇔¬∨¬PQ11德摩根律E(¬∨PQ)⇔¬∧¬PQ12E(¬↔⇔∇PQ)PQ13EPQQP→⇔¬→¬逆反律14EPQPQ¬↔¬⇔↔15EPPP∧⇔16等幂律EPPP∨⇔17EPPF∧¬⇔18

8、否定律EPPT∨¬⇔19EPTP∧⇔20同一律EPFP∨⇔2313/33基本的等价公式EPFF∧⇔21零律E