标签:   离散数学   电子   教案  
文档信息
上传用户 胡景邦      
文档格式 ppt
文档价格 7.6 元
文档大小 1009 KB
文档页数 87 页
相关文档推荐
ppt 离散数学第3章图的基本概念
ppt 《技能自我探索》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 含答案
doc 山东省重点小学三年级数学【上册】期中摸底考试试题 含答案
doc 山东省重点小学三年级数学【上册】开学考试试题 含答案
doc 云南省2020年实验小学一年级数学期中检测试题B卷 含答案
doc 云南省2020年实验小学一年级数学期末检测试卷A卷 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版A卷 附解析
doc 云南省2020年实验小学一年级数学期中测试试卷C卷 含答案
doc 山东省重点小学三年级数学【上册】期中摸底考试试题 (含答案)
doc 云南省2020年实验小学一年级数学期中考试试题(I卷) 含答案
doc 2019-2020年高三上学期期中调研测试数学试题
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) (附答案)
doc 实验小学二年级数学下学期开学考试试题沪教版(II卷) 附解析
ppt 离散数学基础(洪帆)第二章关系
doc 实验小学二年级数学下学期开学考试试题浙教版B卷 附答案
doc 2020年六年级数学【上册】期末考试试题上海教育版B卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 附解析
doc 山东省重点小学三年级数学【上册】开学考试试题 (附解析)
ppt 《技能鉴定培训》PPT课件
doc 云南省2020年实验小学一年级数学期末检测试卷B卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 (含答案)
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 附解析
doc 实验小学二年级数学下学期开学考试试题沪教版 附解析
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 附答案
doc 实验小学二年级数学下学期开学考试试题江西版(I卷) 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版B卷 含答案
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 (附答案)
doc 山东省重点小学三年级数学【上册】期中摸底考试试题 附答案
doc 实验小学二年级数学下学期开学考试试题浙教版(I卷) 附解析
doc 2020年六年级数学【上册】期末考试试卷长春版C卷 附解析
ppt 《技能考试题型总结》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 (附答案)
ppt 《把句子和被句子》PPT课件
doc 2020年六年级数学【上册】期末考试试卷长春版C卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 (附答案)
doc 2019-2020年高三上学期期中调研数学试题
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版B卷 附解析
doc 2020年六年级数学【上册】期末考试试题上海教育版 (含答案)
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 附答案
doc 2019-2020学年高二英语上学期第二次阶段考试试题
doc 山东省重点小学三年级数学【上册】开学考试试题 (含答案)
doc 云南省2020年实验小学一年级数学期中测试试卷A卷 含答案
doc 实验小学二年级数学下学期开学考试试题浙教版(II卷) 附解析
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) (附答案)
doc 2019-2020学年高二英语上学期第二次阶段性考试试题(含解析)
doc 云南省2020年实验小学一年级数学期中考试试题B卷 含答案
doc 2019-2020学年高二英语上学期第二次统练试题
doc 云南省2020年实验小学一年级数学期中检测试卷(I卷) 含答案
doc 山东省重点小学三年级数学【上册】期中摸底考试试题 (附答案)
doc 2019-2020年高三上学期期中调研测试数学试卷含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 附答案
doc 2019-2020年高三上学期期中调研考试 语文
doc 实验小学二年级数学下学期开学考试试题沪教版C卷 附解析
doc 2019-2020年高三上学期期中调研测试化学试题含解析
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版B卷 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版C卷 附答案
doc 2019-2020年高三上学期期中调研考试历史试题
ppt 《把句子写通顺》PPT课件
ppt 离散数学第11章格与布尔代数
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 (附解析)
doc 云南省2020年实验小学一年级数学期中考试试卷(II卷) 含答案
ppt 《把大海装进瓶子里》PPT课件
doc 2019-2020学年高二英语上学期第二次阶段性考试试题
doc 2019-2020年高三上学期期中调研考试政治试题含答案
doc 实验小学二年级数学下学期开学考试试题江西版(I卷) 附解析
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 (附解析)
doc 山东省重点小学三年级数学【上册】开学考试试题 (附答案)
doc 云南省2020年实验小学一年级数学期中检测试题C卷 含答案
doc 2019-2020年高三上学期期中调研考试化学试题含答案
ppt 离散数学图论-图的基本概念
doc 山东省重点小学三年级数学【上册】开学考试试题 附解析
doc 实验小学二年级数学下学期开学考试试题浙教版C卷 含答案
doc 实验小学二年级数学下学期开学考试试题浙教版(II卷) 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 附解析
doc 实验小学二年级数学下学期开学考试试题沪教版 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 (附答案)
doc 云南省2020年实验小学一年级数学期中考试试卷(I卷) 含答案
doc 云南省2020年实验小学一年级数学期中测试试题B卷 含答案
ppt 《技能大比武解读》PPT课件
doc 云南省2020年实验小学一年级数学期中检测试题A卷 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 含答案
doc 云南省2020年实验小学一年级数学期中考试试卷A卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 附解析
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 含答案
ppt 《抄袭系统检测》PPT课件
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 (附解析)
ppt 离散数学第2章关系
doc 云南省2020年实验小学一年级数学期中测试试题C卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题C卷 含答案
ppt 《技术部终总结》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 附解析
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 (含答案)
doc 2019-2020年高三上学期期中调研考试历史试题含答案
doc 实验小学二年级数学下学期开学考试试题沪教版(I卷) 附解析
doc 实验小学二年级数学下学期开学考试试题江西版(I卷) 附答案
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 附答案
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) (附解析)
ppt 离散数学期末试题seu
doc 实验小学二年级数学下学期开学考试试题浙教版(I卷) 含答案
doc 云南省2020年实验小学一年级数学期中测试试题(II卷) 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版A卷 附答案
doc 2019-2020学年高二英语上学期第二次统考试题
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) (含答案)
doc 云南省2020年实验小学一年级数学期末检测试卷(II卷) 含答案
doc 2019-2020年高三上学期期中调研生物试题 含答案
ppt 《技术部岗位职责新》PPT课件
doc 广东省重点小学四年级数学下学期期末摸底考试试卷C卷 (附答案)
doc 2020年一级建造师《建筑工程管理与实务》综合检测A卷 (含答案)
doc 云南省2020年实验小学一年级数学期中检测试卷C卷 含答案
ppt 《技术部岗位职责》PPT课件
doc 实验小学二年级数学下学期开学考试试题浙教版 附答案
doc 2019-2020年高三上学期期中调研测试地理试题
doc 实验小学二年级数学下学期开学考试试题沪教版(I卷) 附答案
doc 山东省重点小学三年级数学【上册】开学考试试题 附答案
ppt 《技术进步与发展》PPT课件
doc 2019-2020年高三上学期期中调研测试数学试题 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版C卷 附答案
doc 2020年六年级数学【上册】期末考试试题上海教育版A卷 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷C卷 (含答案)
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) 附解析
ppt 《抄税处理税控机》PPT课件
doc 云南省2020年实验小学一年级数学期中考试试卷C卷 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版(I卷) 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版B卷 附解析
ppt 离散数学第10章群与环
doc 实验小学二年级数学下学期开学考试试题浙教版 附解析
ppt 《技能给排水培训》PPT课件
doc 2019-2020年高三上学期期中调研政治试题含答案
doc 实验小学二年级数学下学期开学考试试题沪教版 附答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 附答案
ppt 离散数学第2章一阶逻辑
ppt 《技能鉴定业务知识》PPT课件
ppt 《把反问句改成》PPT课件
ppt 《把字句教学教案》PPT课件
doc 实验小学二年级数学下学期开学考试试题沪教版C卷 附答案
doc 实验小学二年级数学下学期开学考试试题浙教版B卷 含答案
doc 云南省2020年实验小学一年级数学期中测试试题(I卷) 含答案
doc 云南省2020年实验小学一年级数学期中测试试卷(II卷) 含答案
doc 2020年六年级数学【上册】期末考试试卷长春版(II卷) 附解析
doc 山东省重点小学三年级数学【上册】期中摸底考试试卷 (含答案)
doc 2020年六年级数学【上册】期末考试试卷长春版(I卷) 附解析
doc 实验小学二年级数学下学期开学考试试题浙教版A卷 附答案
doc 山东省重点小学三年级数学【上册】开学考试试卷 (含答案)
doc 2020年一级建造师《建筑工程管理与实务》练习题(II卷) (含答案)
doc 实验小学二年级数学下学期开学考试试题沪教版C卷 含答案
doc 山东省重点小学三年级数学【上册】开学考试试卷 含答案
doc 2020年六年级数学【上册】期末考试试题上海教育版C卷 含答案
doc 2019-2020年高三上学期期中调研测试物理试题
doc 2019-2020年高三上学期期中调研生物试题含答案
ppt 《把句子变漂亮》PPT课件
doc 2019-2020年高三上学期期中调研物理试题含答案
doc 云南省2020年实验小学一年级数学期中检测试题(I卷) 含答案
doc 实验小学二年级数学下学期开学考试试题浙教版(I卷) 附答案
doc 山东省重点小学三年级数学【上册】开学考试试卷 (附答案)
doc 2019-2020学年高二英语上学期第五次“周学习清单”反馈测试试题
ppt 《把句子写具体级》PPT课件
doc 云南省2020年实验小学一年级数学期中考试试卷B卷 含答案
doc 2020年一级建造师《建筑工程管理与实务》练习题D卷 (含答案)
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 (附答案)
doc 2019-2020年高三上学期期中调研测试语文试题 (I)
doc 实验小学二年级数学下学期开学考试试题沪教版(II卷) 附答案
doc 实验小学二年级数学下学期开学考试试题浙教版C卷 附答案
doc 2020年六年级数学【上册】期末考试试题上海教育版 含答案
doc 云南省2020年实验小学一年级数学期末检测试卷C卷 含答案
doc 云南省2020年实验小学一年级数学期中考试试题(II卷) 含答案
ppt 《技法总论短文改错》PPT课件
doc 实验小学二年级数学下学期开学考试试题浙教版(II卷) 附答案
doc 实验小学二年级数学下学期开学考试试题浙教版A卷 附解析
doc 2020年一级建造师《建筑工程管理与实务》练习题(I卷) 附答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷A卷 含答案
doc 2019-2020学年高二英语上学期第二次段考试题
doc 实验小学二年级数学下学期开学考试试题湘教版 含答案
doc 广东省重点小学四年级数学下学期期末摸底考试试卷B卷 附答案
doc 2019-2020年高三上学期期中调研测试数学理试题含答案
doc 云南省2020年实验小学一年级数学期中检测试题(II卷) 含答案
doc 2019-2020年高三上学期期中调研考试政治试题
doc 实验小学二年级数学下学期开学考试试题浙教版 含答案
doc 山东省重点小学三年级数学【上册】开学考试试卷 附答案
ppt 《把句子写具体》PPT课件
doc 云南省2020年实验小学一年级数学期中测试试卷B卷 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版A卷 含答案
doc 2019-2020年高三上学期期中调研考试化学试题 含解析
doc 2020年六年级数学【上册】期末考试试题上海教育版 (附解析)
doc 云南省2020年实验小学一年级数学期中检测试卷(II卷) 含答案
ppt 《技术进步与》PPT课件
doc 实验小学二年级数学下学期开学考试试题沪教版(II卷) 含答案
ppt 《技术问题总结》PPT课件
doc 实验小学二年级数学下学期开学考试试题沪教版A卷 附答案
ppt 《把人往好处想》PPT课件
doc 云南省2020年实验小学一年级数学期中测试试题A卷 含答案
ppt 《把关人与传播控制》PPT课件
doc 云南省2020年实验小学一年级数学期中考试试题A卷 含答案
doc 实验小学二年级数学下学期开学考试试题沪教版A卷 附解析
doc 2019-2020年高三上学期期中调研测试语文试题
doc 2019-2020学年高二英语上学期第二次质量检测试题
doc 2019-2020年高三上学期期中调研测试化学试题含答案

离散数学电子教案

 版权申诉  ppt " "课程性质" " Discrete Math. 离散数学 研究离散对象及其相互间关系的一门数学学科。 研究离散结构的数学分支。(辞海)" "计算机科学、信息科学、数字化科学的数学基础 " "离散数学主要内容" " 命题逻辑 谓词逻辑 集 合 二元关系 函 数 代数系统 群、环和域 格与布尔代数 图 论 " "" "数理逻辑(Mathematics Logic)" "" "集合论(Sets) " "" "代数结构(或代数系统) (Algebra Structure) " "图论(Graph Theory) " "" "哥尼斯堡七桥问题" "哈密尔顿周游世界问题" "四色定理" "离散数学课程设置: 计算机系核心课程 信息类专业必修课程 其它类专业的重要选修课程" " 离散数学的后继课程: 数据结构、编译技术、 算法分析与设计、人工智能与机器人、 数据库、网络和计算机图形学……" "教材及参考书" "左孝凌等,《离散数学》,上海科学技术文献出版社,1982 同济大学应用数学系《离散数学》编写组,离散数学,统计大学出版社,2003" "第1章 命题逻辑 " "逻辑学:研究思维形式及思维规律的科学。" "逻辑学 " "" "辩证逻辑:以辩证法的世界观为基础的逻辑学。 " "形式逻辑:对思维的形式结构和规律进行研究 的类似于语法的一门工具性学科。 " "思维的形式结构 " "" "概念:思维的基本单位。 " "判断:通过概念对事物是否具有某种属性进行肯定或否定的回答。 " "推理:由一个或几个判断推出另一判断的思维形式。 " "数理逻辑:用数学方法来研究推理的规律。 " " 数理逻辑包括逻辑演算、证明论、公理集合论、模型论和递归论。本课程只介绍逻辑演算中的命题逻辑和谓词逻辑。" "17世纪中叶:德国数学家莱布尼茨(G.W.Leibnitz)创立。 英国数学家布尔(G.Boole):布尔代数 德国数学家弗雷格(F.L.G.Frege):量词与约束变元 美国数学家歌德尔(K.Godel):完全性定理 意大利数学家皮亚诺(G.Peano) 英国数学家德摩根(A.DeMorgen)、罗素(B.A.Russell)。 " "所谓的数学方法,就是引进一套符号体系的方法,所以数理逻辑又称为符号逻辑。 " " 第1章 命题逻辑 1.1命题及联结词 1.1.1 命题的基本概念 在数理逻辑中把能判断真假的陈述句称为命题。一般用小写英文字母或小写英文字母带下标表示。 " " 命题的概念包含了以下3个要素: ⑴只有陈述句才有可能成为命题,而其它的语句,如:感叹句、祈使句、疑问句等都不是命题。 " "⑵一个语句虽是陈述句,但不能判断真假不是命题。 " " ⑶虽然要求命题能判断真假,但不要求现在就能确定真假,将来可以确定真假也可以。" " 一个命题表达的判断结果称为命题的真值。命题的真值有“真”和“假”两种,分别用True、T、1(真)和False、F、0(假)来表示。真值为真的命题称为真命题,真值为假的命题称为假命题。任何命题的真值是唯一的。" " 在命题逻辑中对命题不再细分,因而命题是命题逻辑中最基本的也是最小的研究单位。" " 【例1.1】判断以下语句是否为命题。若是命题,确定其真值。 ⑴上海是个小村庄。 ⑵存在外星人。 ⑶禁止吸烟! ⑷北京是中国的首都。 ⑸4是素数或6是素数。 ⑹今天你吃了吗? ⑺11+1=100 ⑻我正在说谎。 " "命题(F)" "命题(待定)" "不是命题(祈使句)" "命题(T)" "命题(F)" "不是命题(疑问句)" "命题(由上下文确定)" "不是命题(悖论)" " 表示命题的小写英文字母或带下标的小写英文字母常称为命题标识符。如果命题标识符表示一个具体、确定的命题,称为命题常元。如果命题标识符表示任意一个命题,称为命题变元。命题变元无确定的真值。 " " 命题是能判断真假的陈述句。而命题变元代表任意的命题,其真值是不确定的。因而不是命题。 " " 如果一个命题不能再分解成更简单的命题,则称该命题为原子命题。如果一个命题不是原子命题,称该命题为复合命题。如果命题变元表示原子命题时,该命题变元称为原子变元。 " " 在自然语言中,可以通过“如果…,那么…”,“不但…,而且…”这样的连词将简单的陈述句联结成复合语句,同样在命题逻辑当中,也可以通过命题联结词将原子变元联结起来表示复合命题。" " 1.1.2 命题联结词 常用的逻辑联结词有五种:否定联结词、合取联结词、析取联结词、条件联结词和双条件联结词。 " " p和¬p的关系如表1.1所示,表1.1叫做否定联结词“¬”的真值表(下同)。 " " 联结词“¬”也可以看作逻辑运算,它是一元运算。 【例1.2】否定下列命题。 p:王强是一名大学生。 " "¬p:王强不是一名大学生。" "1. 否定联结词 定义1.1.1 设p为命题,则p的否定是一个复合命题,记作:¬p,读作“非p”或“p的否定”。定义为:若P为T,则¬p为F;若p为F,则¬p的真值为T。" " 2. 合取联结词 定义1.1.2设p和q均为命题,则p和q的合取是一个复合命题,记作p∧q,读作“p与q”或“p合取q”。定义为:当且仅当p和q均为T时,p∧q的才为T。 联结词“∧”的真值表如表1.2所示。 联结词“∧”也可以看成逻辑运算,它是二元逻辑运算。 " " 【例1.3】设 p:2008年北京举办了奥运会。 q:中国是世界四大文明古国之一。 " "则p∧q:2008年北京举办了奥运会并且中国是世界四大文明古国之一。" " 3. 析取联结词 定义1.1.3 设p和q均为命题,则p和q的析取是一个复合命题,记作p∨q,读作“p或q”或者“p析取q”。定义为:当且仅当p和q均为F时,p∨q才为F。 联结词“∨”的真值表如表1.3所示。 联结词“∨”也可以看成逻辑运算,它是二元逻辑运算。 " " “∨”与汉语中的“或”相似,但又不相同。汉语中的或有可兼或与不可兼或(排斥或)的区分。 " "【例1.4】 ⑴我今天在电视上看这场杂技或在剧场里看这场杂技。 ⑵灯泡有故障或开关有故障。" "" " 4. 条件联结词 定义1.1.4 设p和q均为命题,其条件命题是个复合命题,记为:p→q。读作“如果p,那么q”或“若p,则q”。定义为:当且仅当p为T,q为F时,p→q才为F。p称为条件命题p→q的前件,q称为条件命题p→q的后件。 联结词“→”真值表如表1.4所示。 联结词“→”也可以看成逻辑运算,它是二元逻辑运算。 " " 【例1.5】 p:小王努力学习。q:小王学习成绩优秀。 " "p→q:如果小王努力学习,那么他的学习成绩就优秀。 " " 联结词“→”与汉语中的“如果…,那么…”或“若…,则…”相似,但又是不相同的。(“→”可不顾及前因后果)" "" " 5. 双条件联结词 定义1.1.5设p和q均为命题,其复合命题p↔q称为双条件命题,读作:“p双条件q”或者“p当且仅当q”。定义为:当且仅当p和q的真值相同时,p↔q为T。 联结词“↔”的真值表如表1.5所示。 联结词“↔”也可以理解成逻辑运算,它是二元逻辑运算。 " " 双条件联结词表示的是一个充分必 要关系,与前面所述相同,也可以不必顾及其前因后果,而只根据联结词的定义来确定其真值。 " "【例1.6】设p:张华是三好学生。 q:张华德、智、体全优秀。 " "p↔q:张华是三好学生当且仅当德、智、体全优秀。" " 1.2 命题公式与翻译 把命题常量,命题变量按照一定的逻辑顺序用命题联结词连接起来就构成了命题演算的合式公式,也叫命题公式。当使用联结词集¬,∧,∨,→,↔时,合式公式定义如下: " "定义1.2.1按下列规则构成的符号串称为命题演算的合式公式,也称为命题公式,简称公式。 " "⑴单个命题变元和常元是合式公式。 " "⑵如果A是合式公式,那么¬A是合式公式。 " "⑶如果A和B是合式公式,那么(A∧B)、(A∨B)、(A→B)和(A↔B)是合式公式。" "⑷当且仅当有限次地应用了⑴、⑵、⑶所得到的符号串是合式公式。" " 命题公式一般的用大写的英文字母A,B,C,…表示。 依照这个定义,下列符号串是合式公式:" " ¬(p∨q),¬(p∨q),(p→(p∨¬q)), (((p→q)∧(q→r))↔(s↔t)) " "下列符号串不是合式公式: (p→q)→(∧q),(p→q,(p∧q)→q) " " 定义1.2.1给出合式公式定义的方法称为归纳定义,它包括三部分:基础,归纳和界限。定义1.2.1中的⑴是基础,⑵和⑶是归纳,⑷是界限。下文中还将多次出现这种形式的定义。 " " 为方便起见,对命题公式约定如下: ⑴最外层括号可以省略。 ⑵规定联结词的优先级由高到低依次为¬,∧,∨,→,↔。按此优先级别,如果去掉括号,不改变原公式运算次序,也可以省掉这些括号。 " " 一般地说,命题公式中包含命题变元,因而无法计算其真值,所以不是命题。 命题公式中的命题变元,也叫命题公式的分量。" " 有了命题公式的概念,就可以用命题公式表示复合命题,常将这个过程称为命题的符号化。命题的符号化可按如下步骤进行: " "⑴找出复合命题中的原子命题。 ⑵用小写的英文字母或带下标的小写的英文字母表示这些原子命题。 ⑶使用命题联结词将这些小写的英文字母或带下标的小写的英文字母连接起来。 " "【例1.7】将下列命题符号化: 他今天上午或者骑自行车去学校,或者乘公共汽车去学校。 " "解:令 p:他今天上午骑自行车去学校。 q:他今天上午乘公共汽车去学校。 " " 此命题中的或是不可兼或,所以不能符号化为:p∨q。而要符号化为:¬(p↔q)或(¬p∧q)∨(p∧¬q)。" " 1.3真值表和等价公式 1.3.1命题公式的真值表 定义1.3.1 设pl,p2,…,pn是出现在公式A中的全部命题变元,给pl,p2,…,pn各指定一个真值,称为对公式A的一个赋值或解释。若指定的赋值使A的真值为T,则称这个赋值为A的成真赋值,若使A的真值为F,则称这个赋值为A的成假赋值。 " " 例如,给公式(p∨q→r)赋值011是指p=0,q=1,r=1,它是该公式的成真赋值;赋值110是指p=1,q=1,r=0,它是该公式的成假赋值。 " " 定义1.3.2 在命题公式A中,对A的每一个赋值,就确定了A的一个真值,把它们汇列成表,称该表为命题公式A的真值表。 " " 【例1.8】构造命题公式¬p∨q的真值表,并求成真赋值和成假赋值。 " " 【例1.9】构造命题公式(p∧q)∨(¬p∧¬q)的真值表,并求成真赋值和成假赋值。 " "解:命题公式(p∧q)∨(¬p∧¬q)的真值表如表1.7所示。00, 11是成真赋值,01,10是成假赋值。" " 1.3.2命题公式的等价 定义1.3.3 设A和B是两个命题公式,对A和B的任一赋值,A和B的真值都相同,则称A和B是等价的或逻辑相等的,记为AB " " 可以证明,命题公式等价有下面的三条性质: ⑴ 自反性,即对任意命题公式A, AA ⑵ 对称性,即对任意命题公式A和B,若AB,则BA ⑶ 传递性,即对任意命题公式A,B和C,若AB,BC,则AC " " 根据定义1.3.3,可以用真值表证明命题公式是等价的,请看下面的例题。 " " 【例1.12】根据等价的定义,用真值表证明 p→(q→p)¬p→(p→¬q) " "证明:构造p→(q→p)和p→(p→q)的真值表,如表1.10所示。p→(q→p)和¬p→(p→¬q)所在的列完全相同,它们具有相同的 真值表。所以p→(q→p)p→(p→¬q) " " 证明等价的另外一种方法叫做等价演算法,其基本思想是:先用真值表证明一组基本等价式,以它们为基础进行公式之间的演算。基本等价式常叫命题定律。下面是常用的命题定律。 1.双重否定律 A¬¬A 2.交换律 A∨BB∨A, A∧BB∧A 3.结合律 (A∨B)∨CA∨(B∨C) (A∧B)∧CA∧(B∧C)" " 4.分配律 A∧(B∨C)(A∧B)∨(A∧C) A∨(B∧C)(A∨B)∧(A∨C) 5.德摩根律 ¬(A∨B)¬A∧¬B ¬(A∧B)¬A∨¬B 6.幂等律 A∧AA,A∨AA " " 7.吸收律 A∨(A∧B)A, A∧(A∨B)A 8.零律 A∨11,A∧00 9.同一律 A∨0A, A∧1A 10.排中律 A∨¬A1 11.矛盾律 A∧¬A0 12.条件等价式 A→B¬A∨B 13.双条件等价式 A↔B(A→B)∧(B→A) 14.假言易位式 A→B¬B→¬A 15.双条件否定等价式 A↔B¬A↔¬B" " 以上共23个等价式,原则上说,这些公式都可以用真值表证明。下面仅验证德摩根律。 【例1.13】用真值表证明德摩根律 ¬(A∨B)¬A∧¬B 解:表1.11是¬(A∨B)和¬A∧¬B的真值表,从表中可以看出德摩根律成立。 " " 定义1.3.4如果X是合式公式A的一部分且X本身也是合式公式,则称X为公式A的子公式。 例如,Aq→(p∨(p∧q)),Xp∧q,则X是A的子公式。 " "定理1.3.1 设X是合式公式A的子公式,若XY,如果将A中的X用Y来置换,得到的公式记为B,则B与A等价,即AB " "证明:对A、B的任一赋值,X与Y的真值相同,而A、B的其它部分完全相同,公式B与公式A的真值必相同。AB 满足此定理的置换叫做等价置换。 " "【例1.17】用等价演算法证明 p↔q(p∧q)∨(p∧q) " "证明: p↔q(p→q)∧(q→p) (双条件等价式) " "(¬p∨q)∧(¬q∨p) (条件等价式) " "(¬p∧¬q)∨(¬p∧p)∨(q∧¬q)∨(q∧p)(分配律) " "(¬p∧¬q)∨0∨0∨(q∧p) (矛盾律) " "(¬p∧¬q)∨(q∧p) (同一律) " "(p∧q)∨(¬p∧¬q) (交换律) " "p↔q(p∧q)∨(¬p∧¬q) (等价的传递性)" " 1.4重言式 定义1.4.1 设A是任一命题公式。 ⑴若对A的任意赋值,其真值永为真,则称命题公式A为重言式或永真式。 ⑵若对A的任意赋值,其真值永为假,则称命题公式A为矛盾式或永假式。 ⑶若A不是矛盾式,则称命题公式A为可满足式。 " " 由定义1.4.1可以看出,任何重言式都是可满足式。 显然,重言式的真值表的最后一列全为1,矛盾式的真值表的最后一列全为0,可满足的公式真值表的最后一列至少有一个1。根据这个结论借助于真值表可以判断一个公式是否为重言式,矛盾式或可满足的。当然也可以用等价演算法判断公式的类型。 " "【例1.18】用等价演算法判断下列公式的类型。 ⑴ q∨¬ ((¬p∨q)∧p)" "解:⑴ q∨¬((¬p∨q)∧p) " "q∨¬((¬p∧p)∨(q∧p)) (分配律) " "q∨¬(0∨(q∧p)) (矛盾律) " "q∨¬(q∧p) (同一律) " "q∨(¬q∨¬p) (德摩根律) " "(q∨¬q)∨¬p (结合律) " "1∨¬p (排中律) " "1 (零律) 由此可知,⑴为重言式。 " " ⑵ (p∨¬p)→((q∧¬q)∧r) " "1→((q∧¬q)∧r) (排中律) " "1→(0∧r) (矛盾律) " "1→0 (零律)" "0 (条件联结词的定义)" " 由此可知,⑵为矛盾式。 " " ⑶ (p→q)∧¬p " "(¬p∨q)∧¬p (条件等价式) " "¬p (吸收律) 由此可知,⑶是可满足式。" " 定理1.4.1 任何两个重言式的合取或析取都是重言式。 " "证明:设A、B是重言式,对A和 B的任何赋值,总有A为1,B为1,所以 A∧B1,A∨B1,故A∧B和A∨B都是重言式。 " "推论 任何两个矛盾式的合取或析取是矛盾式。" "定理1.4.2 一个重言式,对同一分量出现的每一处都用同一合式公式置换,其结果仍是重言式。 " "推论:一个矛盾式,对同一分量出现的每一处都用同一合式公式置换,其结果仍是矛盾式。" " 【例1.19】利用定理1.4.2证明((p∨q)∧r)∨¬((p∨q)∧r)为重言式。 " " 证明:由排中律知p∨¬p为重言式,以((p∨q)∧r)去置换其中的p,得公式((p∨q)∧r)∨¬((p∨q)∧r),根据定理1.4.2,这是重言式。 " "定理1.4.3 设A、B为两个命题公式,AB当且仅当A↔B是重言式。 " "证明:设AB,下证A↔B是重言式。 给A,B的任何赋值,因为AB,所以A,B具有相同的真值,由双条件联结词的定义知A↔B为真,所以A↔B为重言式。 " "设A↔B为重言式,下证AB 给A,B的任何赋值,因为A↔B为重言式,故A,B的真值相同,由命题公式等价的定义知AB" "作业" "判断下列命题公式的类型 1)(P→Q) ↔ (¬Q→¬P) 2) (¬Q→P) → (P→Q) 3) ( (P∨Q)→R) →P 4) (P∧Q) ↔P 5) (P→¬P)→¬P" " 1.5范式 1.5.1析取范式与合取范式 定义1.5.1由一些命题变元或其否定构成的析取式称为基本和,也叫简单析取式。约定单个变元或其否定是基本和。 " "例如,¬p∨q、p∨¬q、p∨q、¬q、¬p、q都是基本和。" " 定义1.5.2由一些命题变元或其否定构成的合取式称为基本积,也叫简单合取式。约定单个变元或其否定是基本积。 例如,¬p∧q、p∧¬q、p∧q、¬p、¬q、p都是基本积。 " " 定义1.5.3由基本和的合取构成的公式叫做合取范式。约定单个基本和是合取范式。 " " 定义1.5.4由基本积的析取构成的公式叫做析取范式。约定单个基本积是析取范式。 " "1)基本和和基本积既是析取范式,又是合取范式。" "2)析取范式和合取范式都仅含联结词¬ ,∧,∨。" " ⑵利用双重否定律消去否定联结词“¬”或利用德摩根律将否定联结词“¬”移到各命题变元前(¬内移)。 " " ⑶利用分配律,结合律将公式归约为合取范式和析取范式。 " " 任何命题公式都可以化成与其等价的析取范式或合取范式。求析取范式和合取范式的步骤如下: " "⑴ 消去联结词“→”和“↔”" "【例1.21】求命题公式(p∨q)↔p的合取范式和析取范式。 " "解:⑴求合取范式 (p∨q)↔p " "((p∨q)→p)∧(p→(p∨q)) (消去↔) " "(¬(p∨q)∨p)∧(¬p∨(p∨q)) (消去→) " "((¬p∧¬q)∨p)∧(¬p∨(p∨q)) (内移) " "(¬p∨p)∧(¬q∨p)∧(¬p∨p∨q) (分配律)" "1∧(¬q∨p)∧(1∨q) (排中律) " "1∧(¬q∨p)∧1 (零律) " "(¬q∨p) (同一律,合取范式) " "←合取范式" " ⑵求析取范式 (p∨q)↔p " "((p∨q)∧p)∨(¬(p∨q)∧¬p) (消去↔) " "((p∨q)∧p)∨((¬p∧¬q)∧¬p) (内移) " "p∨(¬p∧¬q∧¬p) (吸收律) " "p∨(¬p∧¬p∧¬q) (交换律) " "p∨(¬p∧¬q) (幂等律,析取范式) " "由此例可以看出,命题公式的析取范式也不惟一。 " "←析取范式" "←析取范式" "1.5.2主析取范式 由于析取范式和合取范式不惟一,所以使用起来很不方便。为此,引入主析取范式和主合取范式的概念。当命题变元的顺序约定以后,主析取范式和主合取范式是惟一的。 " " 析取范式和合取范式的基本成分是基本积和基本和,而主析取范式和主合取范式的基本成分是极小项和极大项,它们分别是特殊的基本积和基本和。 " " p,q的极小项为:p∧q,p∧¬q,¬p∧q,¬p∧¬q " "定义1.5.5在基本积中,每个变元及其否定不同时存在,但两者之一必须出现且仅出现一次,这样的基本积叫做布尔合取也叫小项或极小项。" " 表1.12是两个变元p和q的极小项的真值表。极小项有下列的性质: " " 两个命题变元的极小项共4(=22)个, 三个命题变元的极小项共8(=23)个, …。一般地说,n个命题变元共有2n个极小项。" "⑴每个极小项只有一个成真赋值,且各极小项的成真赋值互不相同。极小项和它的成真赋值构成了一一对应的关系。可用成真赋值为极小项进行编码,并把编码作为m的下标来表示该极小项,叫做该极小项的名称。 " " 两个命题变元的极小项、成真赋值和名称如表1.13所示。 " " 三个命题变元的极小项,成真赋值和名称如表1.14所示。 " " 从表1.13和表1.14中可以看出,极小项与其成真赋值的对应关系为:变元对应1,而变元的否定对应0。" " ⑵ 任意两个不同的极小项的合取式为永假式。 例如: m001∧m100 (¬p∧¬q∧r)∧(p∧¬q∧¬r) ¬p∧¬q∧r∧p∧¬q∧¬r0 " "" " 定义1.5.6 对于给定的命题公式,如果有一个它的等价公式,仅由极小项的析取组成,称该公式为原公式的主析取范式。 " "" " 任何命题公式都存在着与之等价的主析取范式。一个命题公式的主析取范式可以由以下两种方法求得: ⑴等价演算法:即用基本等价公式推出。 " "⑶全体极小项的析取式为永真式。记为: " " 用等价演算法求主析取范式的步骤如下: " "【例1.22】用等价演算法求(p∧q)∨(¬p∧r)∨(q∧r)的主析取范式。 解:(p∧q)∨(¬p∧r)∨(q∧r) " "(p∧q∧(r∨¬r))∨(¬p∧r∧(q∨¬q))∨(q∧r∧(p∨¬p)) " "(p∧q∧r)∨(p∧q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r)∨ (p∧q∧r)∨(¬p∧q∧r) " "(p∧q∧r)∨(p∧q∧¬r)∨(¬p∧q∧r)∨(¬p∧¬q∧r) " "m111∨m110∨m011∨m001 " "m7∨m6∨m3∨m1∑1,3,6,7" "④在基本积中补入没有出现的命题变元,即添加∧(p∨¬p),再用分配律展开,最后合并相同的极小项。 " "①化归为析取范式。" "②除去析取范式中所有永假的基本积。" "③在基本积中,将重复出现的合取项和相同变元合并。" " ⑵ 真值表法:即用真值表求主析取范式。 用真值表求主析取范式的步骤如下: ① 构造命题公式的真值表。 ② 找出公式的成真赋值对应的极小项。 ③ 这些极小项的析取就是此公式的主析取范式。 " "【例1.24】用真值表法,求(p→q)→r的主析取范式。 解:表1.15是(p→q)→r的真值表,公式的成真赋值对应的极小项为: ¬p∧¬q∧r (成真赋值为001) ¬p∧q∧r (成真赋值为011) p∧¬q∧¬r (成真赋值为100) p∧¬q∧r (成真赋值为101) p∧q∧r (成真赋值为111) (p→q)→r 的主析取范式为:" " (p∧q∧r)∨(p∧¬q∧r)∨(p∧¬q∧¬r) ∨(¬p∧q∧r) ∨(¬p∧¬q∧r) m111∨m101∨m100∨m011∨m001m7∨m5∨m4∨m3∨m1 ∑1,3,4,5,7" " 因而主析取范式含2n (n为公式中命题变元的个数)个极小项。" "①矛盾式无成真赋值," "③可满足式的主析取范式中极小项的个数一定小于等于2n。" " 因而主析取范式不含任何极小项,将矛盾式的主析取范式记为0。" "②重言式无成假赋值," "1.5.3主合取范式 定义1.5.7在基本和中,每个变元及其否定不同时存在,但两者之一必须出现且仅出现一次,这样的基本和叫作布尔析取,也叫大项或极大项。 " "两个变元p,q构成的极大项为: p∨q,p∨¬q,¬p∨q,¬p∨¬q 三个命题变元p,q,r构成的极大项为: p∨q∨r, p∨q∨¬r, p∨¬q∨r, p∨¬q∨¬r, ¬p∨q∨r,¬p∨q∨¬r,¬p∨¬q∨r,¬p∨¬q∨¬r " "两个命题变元的极大项共4(=22)个, 三个命题变元的极大项共8(=23)个, …。一般地说,n个变元共有2n个极大项。" " 例如,两个变元p,q的极大项¬p∨¬q,它的成假赋值是11,表示为M11,把11理解为2进制数,它的10进制表示为3,所以M 11又表示为M3。 " " 两个命题变元的极大项,成假赋值及名称见表1.16,三个命题变元的极大项,成假赋值及名称见表1.17。 " "极大项有下列三个性质: ⑴ 每个极大项只有一个成假赋值,极大项不同,成假赋值也不同。极大项和它的成假赋值构成了一一对应的关系。故可用成假赋值为该极大项进行编码,并把编码作为M的下标来表示该极大项,叫做极大项的名称。" " 从表1.16和表1.17中可以看出,极大项与成假赋值的对应关系为:变元对应0,而变元的否定对应1。" "" "" "" " ⑶全体极大项的合取式为永假式。记为:" " 永真式 。 " "⑵任意两个不同的极 大项的析取式为" " 定义1.5.8 对于给定的命题公式,如果有一个它的等价公式,仅由极大项的合取组成,则该等价式称为原公式的主合取范式。 " "⑴等价演算法:即用基本等价公式推出。 其演算步骤如下: ①化归为合取范式。 ②除去所有永真的基本和。 ③在基本和中合并重复出现的析取项和相同的变元。 ④在基本和中补入没有出现的命题变元。即增加∨(p∧¬p),然后,应用分配律展开公式,最后合并相同的极大项。 " " 任何命题公式都存在着与之等价的主合取范式。主合取范式也可以由以下两种方法求得。" "【例1.25】用等价演算法求(p→q)→r的主合取范式。 解:(p→q)→r" " ¬(¬p∨q)∨r(p∧¬q)∨r(p∨r)∧(¬q∨r) " "(p∨r∨(q∧¬q))∧(¬q∨r∨(p∧¬p)) " "(p∨r∨q)∧(p∨r∨¬q)∧(p∨¬q∨r)∧(¬p∨¬q∨r) " "(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨¬q∨r) " "M000∧M010∧M110M0∧M2∧M6∏0,2,6 " "⑵ 真值表法:用真值表求主合取范式。 用真值表求主合取范式的步骤如下: ①构造命题公式的真值表。 ②找出公式的成假赋值对应的极大项。 ③这些极大项的析取就是此公式的主合取范式。 " "【例1.26】用真值表法求(p→q)→r的主合取范式。 " "解:(p→q)→r的真值表是表1.15。公式的成假赋值对应的大项为: p∨q∨r (成假赋值为000) p∨¬q∨r (成假赋值为010)" " ¬p∨¬q∨r (成假赋值为110) 主合取范式为:(p∨q∨r)∧(p∨¬q∨r)∧(¬p∨¬q∨r) M000∧M010∧M110M0∧M2∧M6∏0,2,6 " " 矛盾式无成真赋值,因而矛盾式的主合取范式含2n (n为公式中命题变元的个数)个极大项。而重言式无成假赋值,因而主合取范式不含任何极大项。将重言式的主合取范式记为1。至于可满足式,它的主合取范式中极大项的个数一定小于2n 。 " " 在例1.23和例1.24中求出(p→q)→r的主析取范式为: m7∨m5∨m4∨m3∨m1∑1,3,4,5,7 在例1.25和例1.26中求出该公式的主合取范式为: M0∧M2∧M6∏0,2,6 比较这两个结果,得出以下的结论:" " 同一公式的主析取范式中m的下标和主合取范式中M的下标是互补的。因此,知道了主析(合)取范式就可以写出主合(析)取范式。" "" "p" "q" "不可兼析取有下列的性质: ⑴ p qq p (交换律) " " ⑵ (p q) rp (q r) (结合律)" " ⑶ p∧(q r)(p∧q) (p∧r) (合取对异或的分配律) ⑷ p q(p∧q)∨(p∧q) ⑸ p q¬(p↔q) ⑹ p p0,0 pp,1 p¬p 定理1.6.1 设A,B,C为命题公式,如果A BC,则A CB,B CA,A B C为一矛盾式。 " " 定义1.6.2 设p和q是两个命题,复合命题p↑q称作p和q的与非。定义为:当且仅当p和q真值都是真时,p↑q才为假。 联结词“↑”称为与非联结词。 " "由定义可以看出下式成立: p↑q¬(p∧q) " " 联结词“↑”的真值表如表1.19所示。 “↑”也可以看成逻辑运算,它是二元逻辑运算。 " "联结词“↑”还有以下几个性质:" " ⑴ p↑p¬(p∧p) ¬p " "⑵(p↑q)↑(p↑q)" "⑶ (p↑p)↑(q↑q)" " ¬¬(p∧q)" " ¬(¬p∧¬q)" " ¬(p↑q)" "(¬p)↑(¬q)" "p∧q" "p∨q" "定义1.6.3 设p和q是两个命题,复合命题p↓q称作p和q的或非。定义为:当且仅当p、q的真值都为假时,p↓q的真值为真。联结词“↓”称为或非联结词。 " " 联结词“↓”的真值表如表1.20所示。 “↓”也可以看成逻辑运算,它是二元逻辑运算。" " 由此定义可得到下面的公式: p↓q¬(p∨q) " "联结词↓还有下面的几个性质: ⑴ p↓p¬(p∨p) ¬p ⑵ (p↓q)↓(p↓q) ¬(p↓q) ¬¬(p∨q)p∨q ⑶ (p↓p)↓(q↓q) ¬p↓¬q¬(¬p∨¬q)p∧q " " 至此已经学了8个联结词:¬,∧,∨,→,↔,,↑,↓。类似于定义1.2.1的方法,可以定义包含上述8个联结词的命题公式。 " " 定义1.6.4 设S是一个联结词集合,如果任何n(n≥1)个 变元组成的公式,都可以由S中的联结词来表示,则称S是 全功能联结词集。 " " 根据命题公式的定义¬,∧,∨,→,↔,,↑,↓ 是全功能联结词集。" " p q¬(p↔q) p↑q¬(p∧q) p↓q¬(p∨q) 所以¬,∧,∨,→,↔是全功能联结词集。 " "利用下列2个等价式可将任何命题公式中的命题联结词 “→”和“↔”去掉。 " " 用德摩根律可证明¬,∧和¬,∨是全功能联结词集。 " " 可以证明∧,∨,→,↔不是全功能联结词集。 " " 定义1.6.5 设S是全功能联结词集,如果去掉其中的任何联结词后,就不是全功能联结词集,则称S是最小全功能联结词集。" "p→q¬p∨q p↔q(p→q)∧(q→p)(¬p∨q)∧(¬q∨p) " "所以¬,∧,∨是全功能联结词集。" " 可以证明¬,∧,¬,∨,↑,↓是最小全功能联结词集。 " "" " 两个命题变元构成的命题公式的真值表的格式如表1.21所示。" " 现在讨论,n个命题变元可以构成多少个不等价的命题公式。 " " 两个命题变元可以构成多少个不等价的命题公式? " " 由等价的概念知道,等价的命题公式有相同的真值表,所以上述问题就转化为两个命题变元构成的命题公式有多少个不同的真值表?" " 真值表中每行公式的真值都有1,0两种可能,所以命题公式的真值有2×2×2×2=24= =16种可能,既有 个不同的真值表。故有 种不等价的公式。 " "" "" "1.7 对偶式与蕰含式 1.7.1对偶式 从1.3节的命题定律中可以看出,很多常用等价式是成对出现的,只要将其中的“∧”和“∨”分别换成“∨”和“∧”,就可以由一个得到另一个。例如,将命题定律 (A∨B) ∧ C(A∧ C)∨(B∧ C ) 中的“∨”换成“∧”, “∧”换成“∨”就得到了命题定律 (A∧B) ∨C(A∨C) ∧ (B ∨ C ) 这些成对出现的等价式反映了等价的对偶性。本节介绍对偶式和对偶原理。 " " 定义1.7.1在仅含联结词¬,∧,∨的命题公式A中,将联结词∨,∧,F,T分别换成∧,∨,T,F所得的公式称为公式A的对偶式,记为A*。 " "设A*是A的对偶式,将A*中的∨,∧,F,T分别换成" " 【例1.27】求p↑q和p↓q的对偶式。 " "解: p↑q¬(p∧q) " " ¬(p∧q)的对偶式是¬(p∨q)p↓q " " 故p↑q的对偶式是p↓q;同样的方法可以证明p↓q的对偶式是p↑q。 " " 根据例1.27,对偶式概念可以推广为:在仅含有联结词¬,∧,∨,↑,↓的命题公式中,将联结词∨,∧,↑,↓,F,T分别换成 ∧,∨,↓,↑,T,F,就得到了它的对偶式。 " "关于对偶式有以下两个结论。 定理1.7.1 设A*是A的对偶式,p1,p2,…,pn是出现在A和A*中的原子变元,则 ¬A(p1,p2,…,pn)A*(¬p1,¬p2,…,¬pn) A(¬p1,¬p2,…,¬pn)¬A*(p1,p2,…,pn)" "∧,∨,T,F,就会得到A。即A 是A*的对偶式,(A*)*A。所以说A*和A互为对偶式。 " " 【例1.28】设命题公式A(p,q,r)(p∨q)∧r,试用此公式验证定理1.7.1的有效性。 " "证明:⑴验证 ¬A(p,q,r)A*(¬p, ¬q, ¬r) " "A(p,q,r)(p∨q)∧r " "¬A(p,q,r)¬((p∨q)∧r)(¬p∧¬q)∨¬r " "A*(p,q,r)(p∧q)∨r " "A*(¬p, ¬q, ¬r)( ¬p∧¬q)∨¬r" "所以,¬A(p,q,r) A*(¬p,¬q,¬r) " "⑵验证 A(¬p,¬q,¬r)¬A*(p,q,r) " "A(¬p,¬q,¬r)(¬p∨¬q)∧¬r " "¬((p∧q)∨r)" "¬A*(p,q,r)" " 定理1.7.2 (对偶原理)设p1,p2,…,pn是出现在公式 A和B中的所有原子变元,如果AB,则A*B* " "根据定理1.4.2,在上述重言式中用¬pi置换 pi, i=1, …,n,所得的公式仍为重言式,即 A(¬p1,¬p2,…,¬pn)↔B(¬p1,¬p2,…,¬pn)是重言式。" "所以 A(¬p1,¬p2,…,¬pn)B(¬p1,¬p2,…,¬pn)" "由定理1.7.1¬A*(p1,p2,…,pn)¬B*(p1,p2,…,pn)" "即: ¬A*¬B*" "由双条件否定等价式知 A*B* " "定理1.7.2叫做对偶原理。对偶原理是数理逻辑中最基本的规律之一。 " "证明:因为 AB 所以 A(p1,p2,…,pn)↔B(p1,p2,…,pn)是重言式。" " 【例1.29】证明重言式的对偶式是矛盾式,矛盾式的对偶式是重言式。 " "证明:设A是重言式,即A1,因为1的对偶式是0,由对偶原理知A*0。所以A*是矛盾式;设A是矛盾式,即A0,而0的对偶式是1,所以A*1。所以A*是重言式。 " "1.7.2蕴含式 定义1.7.2 设A和B是命题公式,若A→B是重言式,则称A蕴含B,记为AB。 " "根据定义可以用真值表或等价演算证明AB。 " "AB定义为:A→B为重言式。又由条件命题的定义知,仅在AT,BF时,A→B为假,其余情况都为真。故要证明AB,只需排除AT,BF的情况。于是就有了证明AB的第二种方法:" " ⑴ 对A指定真值T,若由此推出B的真值不为F,而为T,则A→B是重言式,即AB。 ⑵ 对B指定真值F,若由此推出A的真值不为T,而为F,则A→B是重言式,即AB。 " "【例1.31】推证¬p∧(p∨q)q 解:证法1: " " 证法2: 假定q为F,则p可以为T或F。 " "假定¬p∧(p∨q)为T¬p为T且p∨q为Tp为F且p∨q为Tq为T。 所以 ¬p∧(p∨q)q" "① 当p为T时,¬p为F,所以¬p∧(p∨q)为F。 " "② 当p为F时,(p∨q)为F,所以¬p∧(p∨q)为F。 故 ¬p∧(p∨q)q" " 蕴含式是逻辑推理的重要工具。下面是一些重要的蕴含式。它们都可以用上述两种方法证明,其中A,B,C,D是任意的命题公式。 1.附加律 AA∨B, BA∨B 2.化简律 A∧BA, A∧BB 3.假言推理 A∧(A→B)B 4.拒取式 ¬B∧(A→B)¬A 5.析取三段论 ¬A∧(A∨B)B, ¬B∧(A∨B)A 6.假言三段论 (A→B)∧(B→C)(A→C) 7.等价三段论 (A↔B)∧(B↔C)(A↔C) 8.构造性二难 (A∨C)∧(A→B)∧(C→D)B∨D (A∨¬A)∧(A→B)∧(¬A→B)B 9.破坏性二难 (¬B∨¬D)∧(A→B)∧(C→D)(¬A∨¬C) " " 等价式和蕴含式有下面的关系。 定理1.7.3 设A,B为任意两个命题公式,则AB的充分必要条件是AB且BA 证明:设AB,下证AB且BA 因为AB,所以A↔BT 由双条件等价式得 (A→B)∧(B→A)A↔BT 因而A→B与B→A都是重言式,故有AB且BA。 设AB且BA,下证AB。 因为AB且BA,所以A→B与B→A都是重言式,重言 式的合取也是重言式,即 (A→B)∧(B→A)T 再由双条件等价式得 (A↔B)(A→B)∧(B→A)T 即A↔B为重言式,故有AB。 " " 根据此定理,以前学过的所有等价式都可以作两个蕴含式来使用。例如吸收律A∨(A∧B)A可以作两个蕴含式A∨(A∧B)A和AA∨(A∧B) 来使用。 " "证明:仅证明 ⑸。 因为AB,CB, 所以A→BT,C→BT " "(A∨C)→B¬(A∨C)∨B(¬A∧¬C)∨B " "(¬A∨B)∧(¬C∨B)(A→B)∧(C→B)T∧TT" "由等价的传递性,(A∨C)→BT,故A∨CB" "定理1.7.4 设A、B、C为合式公式。 ⑴ AA (即蕴含是自反的) ⑵ 若AB且A为重言式,则B必为重言式。 ⑶ 若AB且BC,则AC (即蕴含是传递的) ⑷ 若AB且AC,则AB∧C ⑸ 若AB且CB,则A∨CB ⑹ 若AB,C是任意公式,则 A∧CB∧C " "作业" "求主合取范式和主析取范式 1)(¬P ∨ ¬Q) ∨(P → ¬Q) 2) Q ∧ (P ∨ ¬Q) 3) P ∨ (¬P → (Q∨( ¬Q →R))) 4) (P →(Q ∧ R)) ∧(¬P → ( ¬Q ∧ ¬R)) " " 1.8 命题逻辑的推理理论 数理逻辑的主要任务是用逻辑的方法研究数学中的推理。所谓推理是指从前提出发,应用推理规则推出结论的思维过程。任何一个推理都由前提和结论两部分组成。前提就是推理所根据的已知命题,结论则是从前提出发通过推理而得到的新命题。 要研究推理,首先应该明确什么样的推理是有效的或正确的。 " " 定义1.8.1 设A1,A2,…,An和C是n+1个命题公式,若A1∧A2∧…∧AnC,则称C为A1,A2,…,An 的有效结论。也称C可由A1,A2,…,An 逻辑的推出。A1,A2,…,An叫做C的一组前提。 " " A1∧A2∧…∧AnC,亦可记为A1,A2,…,AnC。 " " 由定义1.8.1可以看出,要证明C是一组前提A1,A2,…,An 的有效结论,只需证明A1∧A2∧…∧An→C为重言式。 " "用真值表证明有效结论有以下两种方法:" " 证明一个公式为重言式,可以用真值表、等价演算、主析(合)取范式或已知的蕴含式等方法进行。用等价演算和主析(合)取范式证明重言式的方法前面已经讨论过了,我们已经非常熟悉了。这里仅对真值表法作简单说明。" "⑴ 用全真值表证明 要证明C为前提A1,A2,…,An 的有效结论,只需构造命题公式A1∧A2∧…∧An→C的真值表,证明它是重言式。 " "⑵ 用部分真值表证明 因为条件命题A1∧A2∧…∧An→C为假当且仅当它的前件A1∧A2∧…∧An为真,后件C为假。只要能排除前件为真,后件为假的情况,A1∧A2∧…∧An→C就是重言式。从而C为一组前提A1,A2,…,An 的有效结论。于是就有了下面方法: " "构造A1,A2,…,An与C的真值表,且作在一个表上。 ①找出A1,A2,…,An都为真的行,若C也为真,则A1∧A2∧…∧AnC,即C为前提A1,A2,…,An 的有效结论。" " ② 找出C为假的行,若在每个这样的行中,A1,A2,…,An的真值至少有一个为假,则A1∧A2∧…∧AnC,即C为一组前提A1,A2,…,An 的有效结论。 " "【例1.32】分析事实:“如果我有时间,那么我就去上街;如果我上街,那么我就去书店买书;但我没有去书店买书,所以我没有时间。”。试指出这个推理前提和结论,并证明结论是前提的有效结论。 " "解:令 p:我有时间。 q:我去上街。 r:我去书店买书。 " "根据题意,前提为:p→q,q→r,¬r 结论为:¬p 以下证明¬p是一组前提p→q,q→r,¬r的有效结论。 即证明:(p→q)∧(q→r)∧¬r¬p " " 下面用部分真值表进行证明。 作公式p→q,q→r,¬r,¬p的真值表,如表1.23所示。从表中可以看出: " "所以 (p→q)∧(q→r)∧¬r¬p" "¬p为0的行(赋值100,101,110,111的行) p→q, q→r,¬r至少有一个为0," "p→q,q→r,¬r都为1的行(赋值000的行),¬p也为1。" " 我们已经有了判断推理是否正确的4种方法,即真值表法、等值演算法、主范式法和蕴含演算法。当推理中包含的命题变元较多时,以上4种方法的演算量太大,给推理带来了困难。为此引入命题逻辑的推理理论。" " 命题逻辑的推理是一个描述推理过程的命题公式序列,其中的每个命题公式或者是已知前提,或者是由某些前提应用推理规则得到的结论(中间结论或推理中的结论)。它有两种方法:直接推理和间接推理。" "⑴ 直接推理 直接推理的基本思想是:由一组前提出发,利用一些公认的规则,根据已知的等价式或蕴含式,推演得到有效结论。 " "公认的推理规则有4条: P规则:前提在推导过程中的任何时候都可以引入使用。 T规则:推理中,如果一个或多个公式,蕴含了公式 S,则公式S可以引入到以后的推理之中。" " 置换规则:在推导过程的任何步骤上,命题公式中的子公式都可以用与之等价的公式置换。 合取引入规则:任意两个命题公式A,B可以推出A∧B" " 常用的等价式和蕴合式包括1.3节中的23个命题定律,以及1.7节中的13个重要的蕴含式。 " "【例1.34】用直接推理法证明(p→q)∧(q→r)∧pr " "证明: ⑴ p→q " "⑵ p" "⑶ q " "⑷ q→r " "⑸ r " "⑵间接推理 间接推理常有下列两种方法: ① CP规则 有时要证明的有效结论是一个条件命题,即要证明: " "P" "P" "P" "T⑴⑵假言推理" "T⑶⑷假言推理" " H1∧H2∧…∧Hn(A→B) 其中,H1,H2,…,Hn,A,B是命题公式。" "令 SH1∧H2∧…∧Hn 则上式可以简化为 S(A→B)" "而由S→(A→B)¬S∨(¬A∨B) (¬S∨¬A)∨B¬(S∧A)∨B (S∧A)→B  H1∧H2∧…∧Hn∧A→B" "所以,要证明H1∧H2∧…∧Hn (A→B),只需证明H1∧H2∧…∧Hn∧AB,其中A叫做附加前提。 " "由蕴含的定义知需要证明: S→(A→B)  1" "即需证明 H1∧H2∧…∧Hn∧AB" "这种间接推理方法称为CP规则。" " 【例1.37】用CP规则证明:p→(q→r),¬t∨p,qt→r 证明: " "⑴ t P(附加前提) " "⑵ ¬t∨p P " "⑶ p T⑴⑵析取三段论 " "⑷ p→(q→r) P " "⑸ q→r T⑶⑷假言推理 " "⑹ q P " "⑺ r T⑸⑹假言推理 " "⑻ t→r CP规则 " " ② 归谬法 设要证明H1∧H2∧…∧Hn C 其中,H1,H2,…,Hn,C是命题公式。" " 令 SH1∧H2∧…∧Hn 则上式可以简化为 SC" "由蕴含的定义有 1S→C¬S∨C" "两边否定 0S∧¬C H1∧H2∧…∧Hn∧¬C 即要证明C是前提H1,H2,…,Hn的有效结论,只须证明 H1∧H2∧…∧Hn∧¬C0 " "由定理1.7.3知,上式等价下面两式: 0H1∧H2∧…∧Hn∧¬C 和 H1∧H2∧…∧Hn∧¬C0 " "根据条件联结词的定义,前一式显然成立。所以只需证明 H1∧H2∧…∧Hn∧¬C0 其中,¬C叫做附加前提。 " " 这种间接推理方法称为归谬法,它就是常说的反证法。" " 【例1.38】用归谬法证明 (p∧q)→r,¬r∨s,¬s,p¬q " "⑽ q∧¬q(矛盾) T⑴⑼合取引入" "证明: ⑴ q P(附加前提)" "⑵ ¬r∨s P" "⑶ ¬s P" "⑷ ¬r T⑵⑶析取三段论" "⑸ (p∧q)→r P" "⑹ ¬(p∧q) T⑷⑸拒取式" "⑺ ¬p∨¬q T⑹德摩根律" "⑻ p P" "⑼ ¬q T⑺⑻析取三段论" " 【例1.39】用归谬法证明p→q,¬(q∨r)可逻辑推出¬p 证明: " " ⑴ p→q P " "⑺ q∧¬q (矛盾) T⑶⑹合取引入" "⑵ p P(附加前提)" "⑶ q T⑴⑵假言推理" "⑷ ¬(q∨r) P" "⑸ ¬q∧¬r T⑷德摩根律" "⑹ ¬q T⑸化简律" "作业: 1 甲、乙、丙、丁四人参加考试后,有人问他们谁的成绩最好,甲说“不是我”,乙说“是丁”,丙说“是乙”,丁说“不是我”,四人的回答只有一人符合实际,问成绩最好的人是谁? 2 某科研所要从3名科研骨干A,B,C中挑选出国进修者,由于工作需要,选派时要满足以下条件: 1) 若A去,则C同去 2) 若B去,则C不能去 3) 若C不去,则A或B可以去 问所里应如何选派他们?








































 版权投诉/申诉   非法内容举报    本页不提供全部页面预览,未展示部分请购买并下载后观看使用