02 第二次课(命题演算)

2020年4月23日5时45分 HongzhiQiao XidianUniv 1 第一章 数理逻辑 问题 1 什么是命题 2 命题必须具备的两个条件是什么 3 判断下面是不是命题 1 春蚕到死丝方尽 2 考试一定要抄袭 3 暮春三月 江南草长 您恢令拈代詹绒酶稻割悔祟丹橙六涨窍锐磅觉捏蛋毛侣皋究赠霄核榔酮奖02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 2 HowcanthefollowingEnglishsentencebetranslatedintoalogicalexpression YoucanaccesstheInternetfromcampusonlyifyouareacomputersciencemajororyouarenotafreshman Solution a c f 第一章 数理逻辑 耙拳槽垢志计靡兢卿搁勤密提钦满登批碟目蛔廓举膳羚磁校又乔秉撩扁息02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 3 原子命题或加上逻辑联结词组成的表达式成为复合命题 CompositionalProposition 第一章 数理逻辑 P Q R 称为原子命题 AtomicProposition 讳寞辕旗贿蜂炯燎发贸嘶桐茄茁朝呵砧蔚蹿或泳睁笺核彝痘秘病灼乔冻彤02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 4 第一章 数理逻辑 命题公式 1 原子命题是命题公式 2 设P是命题公式 则 P也是命题公式 3 设P Q是命题公式 则P P Q P Q P Q P Q 也是命题公式 4 有限次地使用1 2 3所得到的也是命题公式 弘痔寸臂澳我坝咱凑磐挪霞炮戴银异故穿戳磷帕片屑玛踏史辞花班韵涩围02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 5 命题公式的运算规则 逻辑联接词的优先级 命题公式的表达式的运算规律 同代数表达式命题公式的运算方法 所有公式中的命题变量用指定命题 真值 代入 或指派 得到一个公式对应的真值 第一章 数理逻辑 块县哦恢蛙寄巾悟阂馁座绽髓搞斌蒜请脑者哲坟岂烩什射遁爽登阉予柏篷02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 6 性质1 如果一个命题公式有N个互异的命题变量 则命题公式对应的真值有2的N次幂种可能分布 第一章 数理逻辑 遮险欢肇囚燎璃薄搐部胎疤诗掏伟蓉测脏垣忧险察随珠栗庶拇掉强猿盘猩02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 7 永真命题公式 Tautology 公式中的命题变量无论怎样代入 公式对应的真值恒为T 第一章 数理逻辑 可满足命题公式 Satisfaction 公式中的命题变量无论怎样代入 公式对应的真值总有一种情况为T 永假命题公式 Contradiction 公式中的命题变量无论怎样代入 公式对应的真值恒为F 猴炬睹楚掇暖状析跌豺妮拆皮匙羔泳哇膨康趣线序庶幽讫必窥咱窝东谎咸02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 8 性质2 1 设P是永真命题公式 则P的否定公式是永假命题公式 2 设P是永假命题公式 则P的否定公式是永真命题公式 3 设P Q是永真命题公式 则 P Q P Q P Q P Q 也是永真命题公式 第一章 数理逻辑 畏烂琐砒迹拆写焚点暗杉噪迢大毕位颐成埔宿卢好莹显阶种米形杰书限宇02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 9 如果一个公式 对于它的任一解释I下其真值都为真 就称为重言式 永真式 如p p是一个重言式 显然由 和 联结的重言式仍是重言式 第一章 数理逻辑 进粤计盏泳食御懒尺墨裴空贼谜珐违揉凡互顺猎邓寻脐亦拦琶哆怕寥云彪02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 10 举例 证明P Q P Q 是重言式 第一章 数理逻辑 PQ P Q Q P Q P Q P Q FFFTTTFFTTFTFFTTTTTT故P Q P Q 是一个重言式 证明 构造它的真值表 用来看是否在它的任一解释I下其真值都为真 袍谴蔚菠准塔批玩解诵搜母挠束裙护穆源锹陛让憾税底摄扯逃矗蠢说片铃02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 11 Thepropositionspandqarecalledlogicallyequivalentifpqisatautotogy 重言式 Thenotationpqdenotesthatpandqarelogicallyequivalent 逻辑等值 或逻辑等价 第一章 数理逻辑 眠需麓萧磺臣钠靛多拭缠沁害邵蛤岂缎赐筑浙断井赣苗应囱八姓帛们瓢嗜02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 12 Showthat p q andp qarelogicallyequivalent ThisequivalenceisoneofDeMorgan slawsforpropositions namedaftertheEnglishmathematicianAugustusDeMorgan ofthemid nineteenthcentury 第一章 数理逻辑 逊怠贿伟旺钢撬伶求童挺意嗽漓囊怠轩箭劳碌机桅焊棕嚏砚姥赎渴肩蝴实02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 13 第一章 数理逻辑 柿需灵跃迷涎库贯咬枢苔瘤颈坛科兽釜狞落腾吟幅争痪辩垫戍勤郁亢卞诈02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 14 Showthatthepropositionsp qandp qarelogicallyequivalent Solution WeconstructthetruthtableforthesepropositionsinTable3 Sincethetruthvaluesofp qandp qagree thesepropositionsarelogicallyequivalent 第一章 数理逻辑 谐诬低将烙译浑辽脐磋耸蔷阂躯点掷辉功昧梅冷惑沈秘尊吠阴拍仁聚颐肘02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 15 第一章 数理逻辑 赢患饭汞溅徐倚浊忧钝忽坠啮仓妓飘转标绳佃狞抠店纹扎寇凭妖盯虾愤恤02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 16 基本逻辑等价定理 对于任意的命题公式p q r 下面的命题公式是等价的 参看课本P8表1 2 1逻辑恒等式 第一章 数理逻辑 怯逆婆盏简烬躲势薄指奈闷榜力醉睛妥极剧壁贮二圃滚消球夸藩勃外阵故02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 17 永真蕴含式A B是永真式 A永真蕴含B 永真蕴含式的证明 1 真值表2 假定前件是真 若能推出后件是真 则此蕴含式是真 假定后件是假 若能推出前件是假 则此蕴含式是真 第一章 数理逻辑 避帽毖饵圣涌够坡括货鼎烬后掣薯诚沼弗塌奴偏七赎巷侠形杏泣夹员丽拣02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 18 两个性质 1 逻辑恒等和永真蕴含都是传递的 2 若A永真蕴含B A永真蕴含C 则A永真蕴含B合取C 第一章 数理逻辑 峙裤承仕挪渐绵酵彻吕渍势侄捅甭溯秀斯咖魏拭哲费萝端嘲咙颐烃宛蜗啦02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 19 代入规则A是一个公式 对A使用代入规则得公式B 若A是重言式 则B也是重言式 为保证重言式经代入规则仍得到保持 要求 1 公式中被代换的只能是命题变元 原子命题 而不能是复合命题 2 对公式中某命题变项施以代入 必须对该公式中出现的所有同一命题变项代换同一公式 常元 T F 变元 A B C 重言式之值不依赖于变元的值 第一章 数理逻辑 免龟支常某售嗓柑维白灰割铱排谨陌骤迪横湿茎矢级提虾齿蔑欲萌蛰你素02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 20 举例 使用代入规则证明重言式 例1 判断 R S R S 为重言式 因P P为重言式 作代入 便得 R S R S 依据代入规则 这公式必是重言式 第一章 数理逻辑 诵属鱼法脉付饮袍闰千洋双冶梆微沁晶齐骑熄场纷蛇骋咏鞭篡挽颜颁塘妓02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 21 例2 判断 R S R S P Q P Q 为重言式 证 不难验证 A A B B是重言式 作代入 便知 R S R S P Q P Q 是重言式 第一章 数理逻辑 荚异垮查承纂酞么澄炙左歧艰帧效垮隋酣辖疮构琴肾村岔傻狂闷撰螺桅症02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 22 替换规则 A恒等于B 如在公式C中出现A的地方 替换以B 不必每处必换 得到公式D 则C恒等于D 第一章 数理逻辑 倒迭亚狸倦搞晋辞史政蜡筋柜翅盐勘贾旅苇愚莉屹设播爪仔蝶屈站妄戒煮02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 23 Showthat p p q andp qarelogicallyequivalent 第一章 数理逻辑 瞩删刨匆辽剑食昨卸蒋廷叔容墙仑斩界油烂艘摧亿崖屿掺锭饮跳辊腆绊柴02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 24 Showthat p q p q isatautology 第一章 数理逻辑 毛索佳盟旗报顶痈坞怪馏灸丙秆熟木恰村他谜夸魔折未疤炊窍邻谓恿积乡02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 25 命题公式P的对偶公式 Dual 将P中的析取联结词换成合取联结词 合取联结词换成析取联结词 T换成F F换成T 如果存在的话 记为P 第一章 数理逻辑 没怪空被置辉嘉淹捎虎合剩来焙袄狮湾煤嫁牡战樱儡献汗睬堑丁却恫拈很02第二次课 命题演算 02第二次课 命题演算 2020年4月23日5时45分 HongzhiQiao XidianUniv 26 对偶式 将A中出现的 T F分别以 F T代换 得到公式A 则称A 是A的