离散数学DISCRETE2A

第二讲 数理逻辑

一、命题逻辑(Propositional Logic)

1. 内容概述

·简单命题与复合命题：什么是命题？命题联结词及其含义。 ·命题公式与赋值：命题逻辑公式的归纳定义，命题公式的真值表。 ·等值演算：命题公式的等值赋值，重要的等值式。

·命题联结词的完备集：通过等值演算得到命题联结词的完备集和极小完备集。

·命题公式的范式：析取范式与合取范式。

·命题演算系统：使用命题逻辑公式进行推理的形式系统。

·命题演算系统的语义与命题演算系统的元性质：注意区别形式系统的语法和语义。

2. 简单命题与复合命题

·命题(proposition)：经典命题逻辑中，称能判断真假但不能既真又假的陈述句为命题。 ·命题对于命题逻辑来说是一个原始的概念，不能在命题逻辑的范围内给出它的精确定义，只能描述它的性质。

·命题必须为陈述句，不能为疑问句、祈使句、感叹句等，例如下述句子为命题：

1. 是有理数 2. 8小于10

3. 2是素数 4. 乌鸦是黑色的 下列句子不是命题：

1. 这个小男孩多勇敢啊！ 2. 乌鸦是黑色的吗？

3. 但愿中国队能取胜。 4. 请把门开一开！ 下列句子不可能判断其为真或为假，所以也不是命题：

1. x + y > 10 2. 我正在撒谎

·命题必须具有真假值，从某种意义上来说，疑问句、祈使句、感叹句没有真假之分。但能判断真假，并不意味着现在就能确定其是真还是假，只要它具有能够唯一确定的真假值即可，例如下述陈述句是命题：

1. 明年的中秋节的晚上是晴天 2. 地球外的星球上存在生物

3. 21世纪末，人类将居住在太空 4. 哥德巴赫猜想是正确的

·经典命题逻辑不区分现在已确定为真，还是将来可能确定为真这种情况，处理与时间有关的真值问题是时态逻辑的任务。经典命题逻辑也不区分是在技术上可以确定为真，还是现在的技术条件下不可以确定为真的这种情况，只承认在技术上，或者说能给出某种方法确定为真的那些东西才为真是直觉逻辑的观点。

·真命题和假命题：命题是为真或为假的陈述句，称这种真假的结果为命题的真值。如果命题的真值为真，则称为真命题，否则称为假命题。

·命题常量与命题变量：使用符号来表示命题，通常用p, q或带下标来表示命题常量或者变量。如果命题符号p代表命题常量则意味它是某个具体命题的符号化，如果p代表命题变量则意味着它可指代任何具体命题。如果没有特别指明，通常来说命题符号p等是命题变量，即可指代任何命题。