下载文档原格式
离散数学第一章1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。
1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。
A1:我是一名大学生.[10]：我是一名大学生。
R：我是一名大学生。
1.2命题联结词1.2.1 否定联结词﹁PP P0 11 01.2.2 合取联结词∧P∧P Q Q0 0 00 1 01 0 01 1 11.2.3 析取联结词∨P∨P Q Q0 0 00 1 11 0 11 1 11.2.4 条件联结词→P Q Q0 0 10 1 11 0 01 1 11.2.5 双条件联结词?P?P Q Q0 0 10 1 01 0 01 1 11.2.6 与非联结词↑P↑P Q Q0 0 10 1 11 0 11 1 0性质：（1）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 或非联结词↓P↓P Q Q0 0 10 1 01 0 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、P→Q、P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。
例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）?（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。
第1章命题逻辑数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科。
这里所指的数学方法就是引进一套符号体系的方法。
所以数理逻辑又称符号逻辑，它是从量的侧面来研究思维规律的。
计算机及计算机科学与数理逻辑有着十分密切的关系。
人们说数字电子计算机是数理逻辑与电子学结合的产物，这话不假。
现代数理逻辑可分为逻辑演算、证明论、公理集合论、递归论和模型论。
本课程介绍的是数理逻辑最基本的内容，也是与计算机科学关系最为密切的：命题逻辑和谓词逻辑（一阶逻辑）1.1 命题符号化及联结词1.1.1 命题及其表示法命题：能判断真假的陈述句。
真值：一个命题总具有一个“值”，即“真”（用T或1表示）或“假”（用F或0表示），称为真值。
一切没有判断内容的句子，无所谓是非的句子，如感叹句、疑问句、祈使句等都不是命题。
例1：（1）2是素数（2）雪是黑色的（3）2+3=5（4）明年十月一日是晴天。
（5）这朵花多好看呀！（6）明天下午有会吗？（7）请关上门！（8）x+y>5（9）地球外的星球上也有人。
（10）我学英语，或者我学日语。
判断的关键：1.是否是陈述句；2.真值是否是唯一的。
简单命题（原子命题）：不能分解为更简单的陈述句。
复合命题：由联结词、标点符号把几个原子命题联结起来的命题。
表示法：一个符号表示的是命题常项还是命题变项由上下文决定。
1.1.2 联结词（也称真值联结词或逻辑联结词或逻辑运算符）p,q为两个命题否定非p(p的否定) ⌝p p为假 1合取p并且q(p和q)p∧q∧p与q同时为真 2 既…又…,不仅…而析取P或q p∨q∨p与q至少一个为真 3 相容或蕴涵如果p则q p→q→⌝(P为真且q为假) 4 只要p就q，p仅当等价P当且仅当q p↔q↔p，q真值相同 5将复合命题符号化的步骤是1）分析出简单命题，符号化2）用联结词联结简单命题例2：将下列各命题符号化（1）3不是偶数（2）李平即聪明又用功（3）李平虽然聪明，但不用功（4）李平不但聪明，而且用功（5）李平不是不聪明，而是不用功（6）李文与李武是兄弟（7）王燕学过法语或英语（8）派小王和小李中的一人去开会（9）只要不下雨，我就骑自行车上班（除非下雨，否则我就骑自行车上班）（10）只有不下雨，我才骑自行车上班（如果下雨，我是不骑自行车上班）（11）若2+2=4，则太阳从东方升起（12）若2+2≠4，则太阳从东方升起（13）若2+2=4，则太阳从西方升起（14）若2+2≠4，则太阳从西方升起（15）燕子飞回南方，春天来了。
