离散数学笔记（1）命题逻辑

1.命题符号化及联结词

基本概念

命题的定义：能够判断真假的陈述句称为命题。

备注：感叹句、疑问句、祈使句和类似于x+y>5之类真值不唯一的句子都不是命题。

真值的真假性：判断正确的命题的真值为真，被称为真命题；判断错误的命题的真值为假，被称为假命题。因此又可以说命题是具有唯一真值的陈述句。常用1表示真命题，0表示假命题。

备注：命题的真假性可能目前是不确定的，但是一定存在且唯一。

简单命题（原子命题）：不能分解成更简单的句子的命题被称为简单命题。由于简单命题的真值是确定的，因此也被称为命题常项或命题常元。

命题符号化：用小写的英文字母表示简单命题，被称为命题符号化。

命题变元：真值可以变化的简单陈述句被称为命题变项或命题变元。注意命题变元不是命题。

复合命题：由简单命题用联结词联结而成的命题被称为复合命题。

联结词：

• 否定联结词：设p为任一命题。复合命题“非p”称为p的否定式，记作 ┐p。 ┐为否定联结词。
• 合取联结词：设p、q为两个命题。复合命题“p并且q”称作p和q的合取式，记作p∧q。p∧q为真当且仅当p和q都为真。
• 析取联结词：设p、q为两个命题。复合命题“p或q”称为p与q的析取式，记作p∨q。∨被称为析取联结词。p∨q为真当且仅当p与q中至少有一个为真。

备注：析取表示的是一种相容性的或运算，并非非此即彼。需要注意在使用排斥或时不能直接用析取式。

• 蕴含联结词：设p、q为两个命题。复合命题“如果p，则q”称作p与q的蕴含式，记作p→q，称p为蕴含式的前件，q为蕴含式的后件。→称作蕴含联结词。p→q为假当且仅当p为真且q为假。

p蕴含q的基本逻辑关系是：q是p的必要条件，或p是q的充分条件。

• 等价联结词：设p、q为两个命题。复合命题“p当且仅当q”称作p和q的等价式，记作p↔q。↔称为等价联结词。p↔为真当且仅当p和q真值相同。

联结词的运算优先级：否定＞合取＞析取＞蕴含＞等价。如果有括号需要先计算括号里的。

本节题型

• 判断一个句子是否是命题；
• 判断一个命题属于简单命题还是复合命题；
• 将命题符号化（带有各种联结词）；
• 判断一个命题的真假性（带有各种联结关系）；

2.命题公式及分类

基本概念

合项公式（命题公式/公式）的定义：

• 单个命题变项：单个命题变项是合式公式。
• 联结词短语：对一个或多个合式公式使用联结词进行联结，所得到的也是合式公式。要求联结的次数是有限次。
• 1和0：把1看作某个恒取1的公式的缩写，把0看作某个恒取0的公式的缩写。

命题公式的层次的定义：

• 若A是单个命题变项，则称A是0层公式。
• 当B是n层公式，且A=┐B时，A是n+1层公式。
• 当B、C分别是i层和j层公式，且max(i,j)=n。如果A=B∧C或A=B∨C或A=B→C或A=B↔C，则A是n+1层公式。

命题公式的真值：命题公式的真值往往是不确定的，只有对它的每个命题变项用指定的命题常项代替后，命题公式才会成为命题，其真值此时也会唯一确定。

命题公式的赋值：设A是一个命题公式，p1p2…pn为出现在A中的所有的命题变项，给p1,p2…pn指定一组真值，称为对A的一个赋值或解释。如果指定的一组值使A的值为真，则称这组值为A的成真复制；若使A的值为假，则称这组值为A的成假赋值。

真值表的概念：将某个命题公式的所有赋值情况下的取值列成表，称为该命题公式的真值表。

构造真值表的步骤：

1. 找出命题公式中所含的所有命题变项p1,p2…pn（如果无下角标就按照字典顺序给出）；
2. 按照从低到高的顺序写出各个层次；
3. 列出所有可能的赋值。从00…0（n位）开始，每次加一，直到11…1为止。
4. 对应每个赋值，计算命题公式各个层次的值，直到最后计算出命题公式的值。

命题公式的分类：

• 重言式（永真式）：在所有赋值下取值都为真的命题公式。
• 矛盾式（永假式）：在所有赋值下取值都为假的命题公式。
• 可满足式：至少存在一组成真赋值的命题公式。

真值函数的概念：一个n(n≥1)阶笛卡尔积到{0,1}的函数被称为一个n元真值函数。

本节题型

• 命题公式的真值判断；
• 命题公式的类型判断；