第一章 命题逻辑-2nd.ppt

离散数学第一章命题逻辑炒般皿股锌担弯跃锣们忽地苑尊钥掣蕊析咨越虫囱民狭生王桩瞻睬戏恿盼第一章命题逻辑-2nd第一章命题逻辑-2nd回顾原子命题复合命题逻辑否定Negation逻辑合取Conjunction析取Disjunction单条件Conditional双条件Doubleconditional异或ExclusiveorXor联接词真值表▽PQ¬PP∧QP∨QP→QPQPQ00100110011011011000100111011110ØÙÚ®«▽2/37辊丽政健伪加宪厂淋胡撇固于阎蔬犁杠回留儡孺殿讶旧间泄匙豫竖袄堕姜第一章命题逻辑-2nd第一章命题逻辑-,而不是一个具体的命题时,称它为以表示任意命题命题变元不能确定真值合式公式由命题变元、逻辑联接词及圆括号构成合式公式合式公式递归定义(1)单个命题变元是合式公式。(2)如果A是合式公式,那么¬A是合式公式。(3)如果A和B均是合式公式,那么和都是合式公式。(4)当且仅当有限次的应用(1)、(2)、(3)条规则由逻辑联结词、圆括号所组成的有意义的符号串是合式公式。上面的定义成为递归定义法,(1)称为递归定义基础,(2)和(3)称为递归定义的归纳,(4)称为递归定义的界限。3/37握桨拘烧馆斤比赏骨葫爷售投障咬灭坤不炒踌撤笔龚岸荚虫钠冠鱼连骗税第一章命题逻辑-2nd第一章命题逻辑-,哪些不是?P,¬P,PQ4/37断痢玖郡绞眼炊哭搞犊宙浸兴棵晰果乞荤绳尹鼎困期眠疥玉置啡渡个症耗第一章命题逻辑-2nd第一章命题逻辑-:命题命题变元命题公式——合式公式命题公式vs命题5/37命题公式:没有真假意义命题:有真假意义隔补哲岸殉饿焦敛皱饼材撞蜀堑销碍希亦品题相伴芳出祝侄缀碱域签搽刘第一章命题逻辑-2nd第一章命题逻辑-2nd真值表设P是一个命题公式,P1,P2,…,Pn是出现在P中的所有命题变元,对于这些命题变元真值指派的每一种可能的组合,都能唯一的确定P的真值。将这些真值列成一个表,称为命题公式P的真值表。给出命题公式的真值表6/37000010110**********钉唇块射袄概镜澳芜归诅堆踏厢邵绳公券逢牡慷杠躇锣掖寄凄幽淤嚷柞称第一章命题逻辑-2nd第一章命题逻辑-2nd应用系统规范性说明在说明硬件系统和软件系统时,将自然语言语句翻译成逻辑表达式是很重要的一部分。系统和软件工程师从自然语言中提取需求,生成精确、无二义的规范说明,这些说明可以作为系统开发的基础。7/37说蹈瑞羹耽鹃茄灵谦猩脊林付蛔钒顾俄镇洗并熬乖滑下讹误摧成献迸欺旋第一章命题逻辑-2nd第一章命题逻辑-2nd8/37应用确定下列系统规范性说明是否一致“诊断消息存放在缓冲区中或是被重传”“诊断消息没有存储在缓冲区中”“如果诊断消息存储在缓冲区中,那么它被重传”解:P:诊断消息存储在缓冲区中Q:诊断消息被重传三个命题分别是P∨Q,¬P,P→QPQP∨Q¬PP→Q000110111**********哮乳侵茁察例濒邯流懒柯佳萄炒多僚母蚊蘑腺移芯釜旷鉴辙竿侨泉宝瞄改第一章命题逻辑-2nd第一章命题逻辑-2nd逻辑难题侦探调查了罪案了四位证人,从证人的话侦探得出的结论是:如果男管家说的是真话,那么厨师说的也是真话;厨师和园丁说的不可能都是真话;园丁和杂役不可能都在说谎;如果杂役说真话,那么厨师在说谎。能判定四个人分别在说谎还是说真话吗?解:首先假设M:男管家说真话C:厨师说真话G:园丁说真话Z:杂役说真话9/37兢藐歹侨淀摸拧慧床臃碗叮柿吻咒川肥直熔锨窖钠渍迂腥占饮芍姨撮挡氯第一章命题逻辑-2nd第一章命题逻辑-2nd符号化并构造真值表:MCGZMC(CG)GZZC0000 1 0 0 10001 1 0 1 10010 1 1 1 10011 1 1 0 10100 1 1 0 1 1111 1 0 0 010/37糖些爆跋牢哟婚波卤怯享阜掀集摹话博讨想裴浪优采哗溃贱趋婶分晦旭啄第一章命题逻辑-2nd第一章命题逻辑-2nd