第4章一阶逻辑基本概念离散数学

离散数学内容总结大纲第一篇 数理逻辑第1章 命题逻辑求命题公式的主析取范式及主合取范式例 求()()p r q p ∨⌝∧∨的主析取范式及主合取范式。

例 求(P →Q)∧R 的主析取范式及主合取范式。

例 求命题公式R Q P ∨∧)(的主析取范式和主合取范式。

例 求公式A =(p →⌝q )→r 的主析取范式与主合取范式。

例 求()r q p →→的主析取范式。

判断公式类型例 用等值演算法判断公式q ∧⌝ (p →q )的类型例 判断下列命题公式的类型（永真式、永假式、可满足式），方法不限。

(1)(2)证明例 证明：()()()r q r p r q p →∧→⇔→∨ 例 证明：r q p r q p →∧⇔→→)()( 例 推证：⌝Q ∧(P →Q)⇒⌝P例 前提：q p s q r p ∨→→,,，结论：s r ∨。

该结论是否有效？请说明原因。

在命题逻辑中构造下面推理的证明：例 如果小张守第一垒并且小李向B 队投球，则A 队获胜。

或者A 队未获胜，或者A 队成为联赛的第一名。

小张守第一垒。

A 队没有成为联赛的第一名。

因此小李没有向B 队投球。

解：先将简单命题符号化。

P：小张守第一垒；Q：小李向B队投球；R：A队取胜；S：A 队成为联赛第一名。

前提：(P∧Q)→R，R∨S，P，S结论：Q证明：(1) R∨S 前提引入(2) S 前提引入(3) R (1)(2)析取三段论(4) (P∧Q)→R 前提引入(5) (P∧Q) (3)(4)拒取式(6) P∨Q (5)置换(7) P 前提引入(8) Q (6)(7)析取三段论例一个公安人员审查一件盗窃案，已知下列事实：（1）甲或乙盗窃了录像机；（2）若甲盗窃了录像机，则作案时间不能发生在午夜前；（3）若乙的证词正确，则午夜时屋里灯光未灭；（4）若乙的证词不正确，则作案时间发生在午夜前；（5）午夜时屋里灯光灭了。

根据以上事实，推断谁是盗窃犯。

（在命题逻辑中构造推理证明。

《离散数学》-⼀阶逻辑-基本概念⼀阶逻辑这个⼀块属于离散数学的内容，它的功能就是将⾃然事物给符号化以为体系的确⽴奠定语⾔基础。

回想⽆论学汉语还是英语的语法，我们都是从句⼦的主⼲学起，那么数学作为⼀门语⾔，它的句⼦当然也有所谓的主⼲。

个体词：个体次是所研究对象可以独⽴存在的具体的或者抽象的客体。

具体⽽特定的客体个体成为个体常项，⼀般⽤⼩写字母a、b、c表⽰。

⽽将抽象或泛指的个体词成为个体变项，⼀般⽤英⽂字母x、y、z表⽰，并称个体变项的取值范围为个体域。

举例说明：(1)“5是素数”，5、素数都是个体词语，5是个体常项⽽素数是个体变项.(2)“x>y”，x、y都是个体变项.谓词：这⾥似乎类似于⾃然语⾔中谓语动词，往往是形容“⼀个动作”，但是在这⾥，谓词是形容“⼀种关系”，当然和个体词类似，根据这种描绘个体之间的关系的确定与否(具体或者抽象泛指)，我们也可以把谓词分为常项和变项。

举例说明:（1） X是有理数。

“是有理数”是常项谓词。

（2） X与y有具体关系L。

这⾥及其迷惑⼈的是语句“有具体关系L”，但是本质上关系L还是抽象的不确定的，因此这⾥“有具体关系L”是变项谓词。

下⾯要做的就是将这种描述关系的语句进⾏符号化，这⾥其实有点类似于函数的概念，因为谓词描述的是个体之间的关系，因此它必须依赖于个体。

我们⽤F、G、H来进⾏符号化的表⽰。

F(a)、F(x)分别表⽰个体常项a、个体变项x满⾜的性质F(a)和F(x).更⼀般的情况，P(x1,x2,x3…xn)表⽰个体x1,x2,…xn具有关系P。

对于不含个体变项的谓词，我们成为0元谓词。

Ex1：将下列命题在⼀阶逻辑中⽤0元谓词符号化，并讨论他们的真值(1) 只有2是素数，4才是素数。

G(2)表⽰2是素数，G(4)表⽰4是素数，则我们将这个命题符号化的结果： G(2) —> G(4)，由于命题的条件为假，因此该命题为真。

(2) 如果5⼤于4，则4⼤于6G(5,4)表⽰“5⼤于4”，命题符号化之后的结果： G(5,4) —> G(4,6)，条件为真结论为假，因此命题为假。

离散数学一阶逻辑离散数学是一门研究离散结构及其运算规律的学科，它涉及到数学中的逻辑、代数、集合论、图论等多个方面。

其中，一阶逻辑作为离散数学中的重要分支，具有广泛的应用和研究价值。

本文将从逻辑的基本概念、一阶逻辑的语法和语义、一阶逻辑的推理规则、一阶逻辑的应用等几个方面来介绍一阶逻辑，旨在帮助读者全面了解一阶逻辑的基本概念和使用方法，并为其后续学习和应用提供指导。

首先，我们来介绍逻辑的基本概念。

逻辑是研究判断的科学，它主要关注真理与推理的关系。

在逻辑中，我们使用语句来表示判断，语句可以是真或假。

同时，逻辑将语句分为简单语句和复合语句。

简单语句是指不能再分解为更简单语句的语句，而复合语句则由多个简单语句通过逻辑运算连接而成。

逻辑运算包括取反（¬）、合取（∧）、析取（∨）、蕴含（→）等。

接下来，我们进一步介绍一阶逻辑的语法和语义。

一阶逻辑是最基本且最常用的逻辑系统之一，它包括基本命题、谓词和量词。

基本命题是指具有真或假值的简单语句，如“今天是星期一”。

谓词是一种描述性的语句构造，它通过将一些对象与一些性质关联起来，来表示复杂的判断。

例如，“x是红色”的谓词可以表示成P(x)。

量词则用来表示概括性的判断，包括全称量词∀和存在量词∃。

例如，“对于任意x，P(x)”可以表示成∀xP(x)。

在一阶逻辑中，语义是根据给定的语句和模型来确定语句的真假值。

模型是一种对应关系，它将谓词与具体的对象元素相联系。

通过使用变元（变量）和量化符号（全称量词∀和存在量词∃），我们可以构造出不同的语句并进行语义推理，从而得到推理结论。

此外，一阶逻辑还有一些特殊的推理规则，例如代入规则和全称推广规则。

代入规则是指在一个语句中的某个位置用一个等价的语句替换。

全称推广规则是指在一个语句中添加一个全称量词，将一个具体对象概括为所有对象的性质。

最后，我们来介绍一阶逻辑的应用。

一阶逻辑在人工智能、计算机科学和数学等领域有着广泛的应用。

离散数学（微课版）第4章1. 引言在离散数学的第4章中，我们将讨论图论的基本概念和应用。

图论是研究图及其在现实生活中的应用的数学分支，它在计算机科学、网络设计、运筹学等领域中具有重要的应用价值。

本章将介绍图的定义、图的表示方法、图的遍历算法等内容。

2. 图的定义图由一组节点和一组节点之间的边构成。

节点通常表示现实世界中的对象，而边则表示对象之间的关系。

图可以用于描述各种问题，如社交网络中的用户关系、城市之间的交通网络等。

2.1 有向图和无向图图可以分为有向图和无向图两种类型。

在有向图中，边具有方向，表示节点之间的单向关系。

而在无向图中，边没有方向，表示节点之间的双向关系。

2.2 顶点和边图由顶点和边组成。

顶点是图的节点，用来表示对象。

边连接两个顶点，表示两个对象之间的关系。

2.3 路径和环路径是指在图中从一个顶点到另一个顶点的连接序列。

环是一条路径，其起点和终点相同。

3. 图的表示方法在计算机中，图可以用不同的数据结构来表示。

常见的表示方法包括：3.1 邻接矩阵邻接矩阵是用二维数组表示图的连接关系。

对于无向图，邻接矩阵是对称的，而对于有向图，则不对称。

A B CA010B101C010上述邻接矩阵表示了一个无向图，其中顶点A与顶点B相连，顶点B与顶点C相连。

3.2 邻接表邻接表是用链表表示图的连接关系。

对于每个顶点，邻接表保存了与其相连的其他顶点的信息。

A ->B -> NULLB -> A ->C -> NULLC -> B -> NULL上述邻接表表示了一个无向图，顶点A与顶点B相连，顶点B与顶点A、C相连，顶点C与顶点B相连。

4. 图的遍历算法图的遍历算法是指按照一定的方式访问图中的所有节点。

常见的图的遍历算法有深度优先搜索和广度优先搜索。

4.1 深度优先搜索深度优先搜索从起点开始，尽可能深地访问尚未访问的节点，直到无法继续深入为止，然后回溯到上一个节点，继续深入其他未访问的节点。