离散数学笔记.doc

  1. 1、本文档共46页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
第一章 命题逻辑 内容: 命题及命题联结词、命题公式的基本概念,真值表、基本等价式及永真蕴涵式,命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法 教学目的: 熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。 熟练掌握常用的基本等价式及其应用。 熟练掌握(主)析/合取范式的求法及其应用。 熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。 熟练掌握形式演绎的方法。 教学重点: 1.命题的概念及判断 2.联结词,命题的翻译 3.主析(合)取范式的求法 4.逻辑推理 教学难点: 1.主析(合)取范式的求法 2.逻辑推理 1.1命题及其表示法 1.1.1 命题的概念 数理逻辑将能够判断真假的陈述句称作命题。 1.1.2 命题的表示 命题通常使用大写字母A,B,…,Z或带下标的大写字母或数字表示,如Ai,[10],R等,例如 A1:我是一名大学生。 A1:我是一名大学生. [10]:我是一名大学生。 R:我是一名大学生。 1.2命题联结词 1.2.1 否定联结词﹁P 0 1 1 0 1.2.2 合取联结词∧ 0 0 0 0 1 0 1 0 0 1 1 1 1.2.3 析取联结词∨ 0 0 0 0 1 1 1 0 1 1 1 1 1.2.4 条件联结词→ 0 0 1 0 1 1 1 0 0 1 1 1 1.2.5 双条件联结词 0 0 1 0 1 0 1 0 0 1 1 1 1.2.6 与非联结词↑ 0 0 1 0 1 1 1 0 1 1 1 0 性质: P↑P﹁(P∧P)﹁P; (2)(P↑Q)↑(P↑Q)﹁(P↑Q) P∧Q; (3)(P↑P)↑(Q↑Q)﹁P↑﹁Q P∨Q。 1.2.7 或非联结词↓ 0 0 1 0 1 0 1 0 0 1 1 0 性质: (1)P↓P﹁(P∨Q)﹁P; (2)(P↓Q)↓(P↓Q)﹁(P↓Q)P∨Q; (3)(P↓P)↓(Q↓Q)﹁P↓﹁Q﹁(﹁P∨﹁Q)P∧Q。 1.3 命题公式、翻译与解释 1.3.1 命题公式 定义 命题公式,简称公式,定义为: (1)单个命题变元是公式; (2)如果P是公式,则﹁P是公式; (3)如果P、Q是公式,则P∧Q、P∨Q、PQ、 PQ都是公式; (4)当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 例如,下面的符号串都是公式: ((((﹁P)∧Q)R)∨S) ((P﹁Q)(﹁R∧S)) (﹁P∨Q)∧R 以下符号串都不是公式: ((P∨Q)(∧Q)) (∧Q) 1.3.2 命题的翻译 可以把自然语言中的有些语句,转变成数理逻辑中的符号形式,称为命题的翻译。 命题翻译时应注意下列事项: (1)确定所给句子是否为命题。 (2)句子中联结词是否为命题联结词。 (3)要正确的选择原子命题和合适的命题联结词。 例:假如上午不下雨,我去看电影,否则就在家里读书或看报。 解:设P:上午下雨;Q:我去看电影;R:我在家里读书;S:我在家里看报。 本例可表示为: (PQ)∧(P(R∨S))。 1.3.3 命题公式的解释 定义 设P1,P2,…,Pn是出现在命题公式G中的全部命题变元,指定P1,P2,…,Pn的一组真值,称这组真值为G的一个解释或赋值,记作I,公式G在I下的真值记作TI(G)。 例如,G=(P∧Q)R,则I: 1 1 0 是G的一个解释,在这个解释下G的真值为1,即TI(G)=1。 1.4 真值表与等价公式 1.4.1 真值表 定义 将公式G在其所有解释下所取得的真值列成一个表,称为G的真值表。 构造真值表的方法如下: (1)找出公式G中的全部命题变元,并按一定的顺序排列成P1,P2,…,Pn。 (2)列出G的2n个解释,赋值从00…0(n个)开始,按二进制递加顺序依次写出各赋值,直到11…1为止(或从11…1开始,按二进制递减顺序写出各赋值,直到00…0为止),然后从低到高的顺序列出G的层次。 (3)根据赋值依次计算各层次的真值并最终计算出G的真值。 例:G=( P→Q )∧Q 0 0 1 0 0 0 1 1 0 0 1 0 0 1 0 1 1 1 0 0 1.4.2 命题公式的分类 定义 设G为公式: (1)如果G在所有解释下取值均为真,则称G是永真式或重言式; (2)如果G在所有解释下取值均为假,则称G是永假式或矛盾式; (3)如果至少存在一种解释使公式G取值为真,则称G是可满足式。 1.4.3 等价公式 定义 设A和B是两个命题

文档评论(0)

kaku + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

版权声明书
用户编号:8124126005000000

1亿VIP精品文档

相关文档