离散数学命题逻辑.ppt

《离散数学命题逻辑.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第一章命题逻辑命题与联结词逻辑研究人类思维的科学。公元前四世纪亚里斯多德《工具论》奠定了逻辑学的理论基础。中国最早的一部逻辑专著－－《墨经》也创造了一个比较完整的逻辑体系。形式逻辑辨证逻辑数理逻辑数理逻辑数理逻辑是一门用数学方法来研究推理规律的科学。所谓数学方法主要是指引进一套符号体系的方法，所以数理逻辑也称做符号逻辑。（创始人：十七世纪，德国数学家莱布尼兹）形式符号体系由于自然语言存在模棱两可、含糊的特性，所以有必要引入形式化语言。形式化语言在数理逻辑中称为目标语言。例如：今天晚上八点中央一台播放连续剧或纪录

2、片。我吃苹果或雪梨。[定义]目标语言：具有单一、明确的含义的语言。（基本元素是命题）[定义]形式符号体系：由目标语言和一些规定的公式与符号构成的体系为何学习数理逻辑程序=算法+数据结构算法=逻辑+控制数理逻辑的主要内容数理逻辑内容丰富，但其主要包括“两个演算”加“四论”，即：逻辑演算。包括命题演算和谓词演算证明论。主要研究数学理论系统的相容性（即不矛盾、协调性）的证明。递归论（能行性理论）。自从电子计算机发明后，迫切需要在理论上弄清计算机能计算哪些函数。递归论研究能行可计算的理论，它为能行可计算的函数找出各种理

3、论上精确化的严密类比物。模型论。主要是对各种数学理论系统建立模型，并研究各模型之间的关系以及模型与系统之间的关系。公理集合论。主要研究在消除已知集合论悖论的情况下，用公理方法把有关集合的理论充分发展下去。现代数理逻辑命题逻辑研究的内容命题逻辑也称为命题演算研究以命题为基本单位构成的前提和结论之间的可推导关系.(1)什么是命题？(2)如何表示命题？(3)如何由一些前提推导出一些结论?命题与联结词命题联结词命题的概念具有判断内容（非真即假）的陈述句称为命题。能够确定或分辨其真假的陈述句。命题有一个值，称为真值，真值

4、只有“真”和“假”两种，分别用“T”（或“1”）和“F”（或“0”）表示。命题中的判断正确，其真值为真，称为真命题，命题中的判断错误，真值为假，称为假命题。命题示例1中华人民共和国的首都是北京。我们在学习《离散数学》的数理逻辑部分。所有素数都是奇数。雪是黑色的。命题示例2某些感叹句、祈使句、疑问句等没有真假之分，所以不是命题。明天开会吗？多美妙啊！请进来。全体立正。判断语句是否为命题要注意的问题：目前无法确定真值，但从本质而言，真值存在的语句是命题。例：(1)别的星球上有生物。(2)2046年世界杯在中国举行。

5、真值因时因地而异的判断性陈述句是命题。例：(1)现在是上午。(2)今天下雨。含有未确定内容的代词，不能判断真假的语句不是命题。例：(1)1+101=110。当1和101是二进制数，语句为真，为十进制数，语句为假。(2)x+y>10。悖论不是命题。例：我正在说慌。命题的分类根据命题的构成形式，可以将命题分为：[定义]原子命题：不包含任何联结词的命题。[定义]复合命题：由原子命题和联结词组成的命题。连接词一般译为：“或者”、“并且”、“不”、“如果…则…”、“仅当”、“当且仅当”等。例如：“明天下雪”、“9是素数”

6、都是原子命题，“2不是素数”是复合命题“明天下雪或明天下雨”是复合命题。“中国获得2008奥运的主办权并且加入了WTO”是复合命题。“如果A和B是对顶角，则角A等于角B”是复合命题。命题的表示[定义]命题标识符：表示命题的符号，通常是大写英文字母。[定义]命题符号化：将表示命题的符号放在该命题的前面。例：P：北京是中国的首都。Q：北京承办2008年奥运。命题的表示（续）[定义]命题常量：表示确定命题的命题标识符。[定义]命题变元：可表示任意一个（原子或复合）命题的命题标识符，就称为命题变元。当命题变元表示原子命

7、题时，该变元称为原子变元。当命题变元P用一个特定命题去取代时，才能确定P的真值，这时也称对P进行指派。例：若P是命题变元，P：北京是中国的首都。（指派P为命题北京是中国的首都）命题——小结判断一句话是否是命题的步骤：1）看它是否是陈述句，如果是疑问句、感叹句和祈使句则不是命题；2）看它是否是悖论，悖论不是命题，如“我正在说谎”；3）看它真值是否唯一，如果不唯一，则不是命题。命题与联结词命题联结词命题联结词1.否定：┐2.合取：∧3.析取：∨4.排斥析取：▽5.条件（蕴含）：6.双条件：否定设P为命题，P的否

8、定也是一个命题，记作┐P当P为T时，┐P为F当P为F时，┐P为TP与┐P的关系如右表例：设P：上海是个大城市。则┐P：上海不是一个大城市。或：上海是个不大的城市。P┐PFTTF合取设P、Q是命题，P和Q的合取也是个命题，记作P∧Q当且仅当P、Q同时为T时，P∧Q为T其他情况下，P∧Q的真值都是F读作“P并且（与）Q”PQP∧QFFFFTFTFFTTT合取示例(1)P:我富有。Q:我快乐