第1章命题逻辑课件.pptVIP

第一篇 数理逻辑 数理逻辑是用数学方法研究形式逻辑中推理规律的一种理论。 著名计算机软件大师狄克斯特(Dijkstra) 曾经说：“我现在年纪大了，搞了这么多年软件，错误不知犯了多少，现在觉悟了。我想假如我早年在数理逻辑上好好下点功夫的话，我就不会犯这么多的错误。不少东西逻辑学家早就说了，可我不知道。要是我能年轻20岁的话，我要回去学逻辑”。由此可见，数理逻辑对于计算机工作者来说是多么的重要。 第一章 命题逻辑 1.1 命题符号化及联结词 1.2 命题公式及分类 1.3 等值演算 1.4 联结词全功能集 1.5 对偶与范式 1.6 推理理论 1.7 命题演算的自然推理形式系统N 1.8 例题选解 习 题 一 1.1 命题符号化及联结词 命题逻辑是数理逻辑的基础，它以命题为研究对象，研究基于命题的符号逻辑体系及推理规律，也称为命题演算。命题是研究思维规律的科学中的一项基本要素，它是一个判断的语言表达。 一、命题 【例1.1.1】 下述各句均为命题： （1）4是偶数。 （2）煤是白色的。 （3）《几何原本》的作者是欧几里德。 （4）2190年人类将移居火星。 （5）地球外也有生命存在。 上述命题中（1）、（3）是真命题，（2）是假命题，其中的（3）可能有人说不出它的真假，但客观上能判断真假。（4）的结果目前谁也不知道，但到了时候则真假可辨，即其真值是客观存在的，因而是命题。同样，（5）的真值也是客观存在的，只是我们地球人尚不知道而已，随着科学技术的发展，其真值是可以知道的，因而也是命题。 【例1.1.2】 下列语句不是命题： （1）你好吗？ （2）好棒啊！ （3）请勿吸烟。 （4）x＞3。 （5）我正在说谎。 （1）、（2）、（3）均不是陈述句，因而不是命题。（4）是陈述句，但它的真假取决于变量x的取值，例如取x为4时其值为真，取x为2时其值为假，即其真值不唯一，因此不是命题。（5）也是陈述句，但它是悖论，因而也不是命题。 从上面讨论可以看出，判断一个语句是否是命题的关键是： (1)语句必须是陈述句。 (2)陈述句必须具有唯一的真值。要注意两点： ①一个陈述句在客观上能判断真假，而不受人的知识范围的限制。 ②一个陈述句暂时不能确定真值，但到了一定时候就可以确定，与一个陈述句的真值不能唯一确定是不同的。 以上所讨论的命题均是一些简单陈述句。在语言学中称为简单句，其结构均具有“主语+谓语”的形式，在数理逻辑中，我们将这种由简单句构成的命题称为简单命题，或称为原子命题，用p、q、r等符号表示。如： p：4是偶数。 q：煤是白的。 r：《几何原本》的作者是欧几里德。 【例1.1.3】 下列命题不是简单命题： （1）4是偶数且是2的倍数。 （2）北京不是个小城市。 （3）小王或小李考试得第一。 （4）如果你努力，则你能成功。 （5）三角形是等边三角形，当且仅当三内角相等。 上面的命题除（3）的真假需由具体情况客观判断外，余者的真值均为1。但是它们均不是简单命题，分别用了“且”、“非”、“或”、“如果……则……”、“当且仅当”等联结词。 由命题和联结词构成的命题称为复合命题。构成复合命题的可以是原子命题，也可以是另一个复合命题。一个复合命题的真值不仅与构成复合命题的命题的真值有关，而且也与所用联结词有关。下面我们给出几个基本的联结词。 二、命题联结词（或逻辑运算符） 【例1.1.4】 (1) p：4是偶数。其真值为1。 ?p ：4不是偶数。其真值为0。 (2) q：这些都是学生。 ?q ：这些不都是学生。 注：否定联结词使用的原则：将真命题变成假命题，将假命题变成真命题。但这并不是简单的随意加个不字就能完成的。例如上例中的（2），q的否定式就不能写成“这些都不是学生”。不过，一般地，自然语言中的“不”、“无”、“没有”、“并非”等词均可符号化为 “?” 2、合取“∧” 设 p、q 是任意两个命题，复合命题 “p且q” 称为p与q的合取式，记作：p ∧q。“∧”是合取联结词。P ∧q的真值表如下表所示 【例1.1.