计算机科学中的数理逻辑 全套课件 第1-8章 集合论基础：概念与运算-模型检测

1.1集合的基本概念2026年4月第1章集合论基础：概念与运算计算机科学中的数理逻辑目录CONTENTS01集合的概念介绍集合概念，以及集合概念的三个核心内涵：确定性、互异性和整体性。02集合的表示与特殊集合讲解列举法和描述法两种表示方法，并介绍空集、全集、有限集、无限集和基数等特殊集合。03外延性公理阐述外延性公理，并在此基础上讲解集合的相等关系与包含关系。04核心概念总结汇总本节学习的关键定义、符号和定理，巩固理解。01集合的概念BASICCONCEPTSOFSETS集合论·基础理论集合的概念什么是集合(Set)？集合是由确定的、互相区别的对象汇聚而成的一个整体。简单来说，它就是我们要研究的“一堆东西”的总称，具有整体性和确定性。什么是元素(Element)？组成集合的每一个独立的、不可分割的“个体”对象，就称为该集合的元素。元素与集合是部分与整体的关系，元素是集合存在的基础。属于关系(∈)如果对象a是集合A的一个元素，我们就称“a属于A”。记作：a∈A不属于关系(∉)如果对象a不是集合A的元素，我们就称“a不属于A”。记作：a∉A逻辑辨析：排中律根据集合的“确定性”，对于任意对象和集合，二者之间要么是“属于”，要么是“不属于”，不存在第三种可能。集合概念的三个核心内涵集合是数学中最基本的概念之一，理解它的关键在于把握其三个核心特性：确定性、互异性与整体性。这三点共同构成了集合的严谨定义，也是判断一个对象能否构成集合的根本依据。01“确定的”(Deterministic)一个对象是否属于某个集合必须是明确的、可判定的，不存在模棱两可的情况。反例：“高个子的人”不能构成集合，因为日常生活中“高”没有绝对、明确的量化标准，无法准确判断谁是“高个子”。02“互相区别的”(Distinct)集合中的元素是独一无二的，重复出现的元素在集合中只算作一个。示例：集合{a,b,b}实际上等同于集合{a,b}，因为第二个b是重复的，会被自动剔除。03“整体识别的”(Integrated)集合本身是一个不可分割的整体，具有独立于其内部元素的属性，不同于其内部的任何一个元素。辨析：元素a并不等于集合{a}。前者是个体，后者是包含这个个体的整体，二者分属不同的逻辑层级。02集合的表示与特殊集合REPRESENTATIONANDSPECIALSETS集合的表示方法01/列举法(RosterMethod)将集合中的所有元素一一列出，并用大括号{}括起来。这种方法直观易懂，适用于元素个数有限且较少的集合，或元素具有明显规律的无限集合。【示例】方程x(x²-2x+1)=0的根组成的集合表示为{0,1}。02/描述法(Set-builderNotation)通过描述元素共同满足的性质来定义集合，一般形式为{x|P(x)}，其中x是代表元素，P(x)是元素x满足的特征性质。当集合元素很多或为无限集时，通常使用描述法。【示例】所有偶数的集合可表示为：

{x|x是整数且x能被2整除}特殊集合：空集与全集特殊集合在集合论的理论体系中，存在两个具有奠基意义的特殊集合。它们是逻辑的两个极端，分别代表了元素的“无”和“全”，是构建复杂集合运算的基础。概括原理(ComprehensionPrinciple)集合论有一个核心约定：对于任何描述事物性质的语句（即“谓词”），都存在一个集合，它恰好包含所有满足该性质的对象。空集与全集正是基于这一原理定义的。空集(EmptySet)∅不含任何元素的集合，是所有集合的子集。例：方程x²+1=0在实数范围内的解集合。全集(UniversalSet)U在特定研究范围内，包含所有研究对象的集合。全集不是绝对的，它取决于我们研究的上下文和论域。关键认知空集虽然“空”，但它本身是一个实实在在的集合对象，不是“无”。理解这两个概念对于后续学习补集、幂集等集合运算至关重要。特殊集合：有限集、无限集集合是数学的基础，按元素数量性质可分为有限集和无限集。基数则是刻画有限集合元素“多少”的量化概念。有限集

FiniteSet包含有限个元素的集合。例:{a,b,c}无限集

InfiniteSet包含无限个元素的集合。例:全体自然数{1,2,3...}基数

Cardinality有限集合中元素的个数，

记作|A|。例:|{a,b,c}|=303外延性公理AXIOMSANDRELATIONS外延性公理(ExtensionalityPrinciple)▍公理集合A和集合B相等，当且仅当它们包含的元素完全相同。这是判断集合相等的唯一依据。形式化描述：A=B⇔(∀x)(x∈A↔x∈B)例1.1：核心推论与应用场景从外延性公理出发，我们可以直接推导出集合的两个重要特征：无序性与表示多样性。●无序性(Non-ordering)集合{0,1}与{1,0}是严格相等的。因为它们包含的元素完全一样，元素书写顺序不影响集合的本质。●表示多样性(DiverseRepresentation)描述法{x|x(x²-2x+1)=0}与列举法{0,1}描述的是同一个集合。即便定义方式不同，只要元素完全一致，集合就相等。集合包含：子集(Subset)子集的定义(Definition)如果集合A的每一个元素都是集合B的元素，那么集合A就是集合B的子集。符号表示(Notation)记作：A⊆B读作：“A包含于B”或“B包含A”。形式化描述对于任意的元素x，若x属于A，则x必属于B：A⊆B⇔(∀x)(x∈A→x∈B)重要结论I“空集是任何集合的子集”∅⊆A(A为任意集合)重要结论II“任何集合都是其自身的子集”A⊆A(A为任意集合)关键区别：隶属关系vs.包含关系01/隶属关系(∈)表示“元素”与“集合”之间的关系。即一个对象是否存在于一个集合之中。•正确示例：a∈{a,b}，因为a是集合{a,b}中的一个元素。•生活类比：“苹果”是“水果篮”里的一个具体物品。02/包含关系(⊆)表示“集合”与“集合”之间的关系。即一个集合的所有元素，都是另一个集合的元素。•正确示例：{a}⊆{a,b}，因为集合{a}的唯一元素a也在集合{a,b}中。•常见误区：a⊆{a,b}(❌)。因为a是一个元素，不是集合，不能作为“包含关系”的主体。04核心概念总结核心概念总结集合论的基石在于对基本关系的清晰界定。理解以下三个核心概念是构建严谨集合思维的第一步。准确区分元素与集合、集合与集合之间的关系至关重要。G1·集合相等(A=B)元素完全相同集合A中的每一个元素都在B中，反之亦然。是集合相等的判定标准。G2·子集(A⊆B)A包含于B集合A的所有元素都是集合B的元素。描述了两个集合间的包含与被包含关系。G3·隶属关系(a∈A)a属于A元素a是集合A中的一个成员。这是个体与整体之间的归属关系，不同于子集。关键提示：严谨区分概念与符号注意区分“元素与集合”的关系（隶属∈），以及“集合与集合”的关系（包含⊆/相等=）。集合论的严谨性，正是建立在对这些基本概念的精确理解之上，切勿混淆。1.2集合的运算2026年4月第1章集合论基础：概念与运算计算机科学中的数理逻辑目录CONTENTS01交并差补运算介绍集合的并、交、差、补四种基本运算的定义、性质，并通过文氏图直观理解。02幂运算讲解幂集的定义，即一个集合所有子集构成的集合，并探讨其基数性质。03笛卡尔积运算引入序偶概念，定义集合的笛卡尔积，并学习其相关性质。04核心概念总结汇总本章学习的关键运算、符号和定理，巩固理解。01交并差补运算BASICSETOPERATIONS集合论·基础理论基本运算定义集合的基本运算集合运算是指以已知集合为基础，通过特定规则构造出新集合的过程。主要包含四种基本类型：并(Union)、交(Intersection)、差(Difference)、补(Complement)01.并运算(Union)定义：由所有属于集合A或属于集合B的元素组成的集合。A∪B={x|x∈A或x∈B}02.交运算(Intersection)由所有同时属于集合A和集合B的元素组成的集合。A∩B={x|x∈A且x∈B}03.差运算(Difference)由所有属于集合A但不属于集合B的元素组成的集合。A-B={x|x∈A且x∉B}04.补运算(Complement)

基本运算与文氏图文氏图(VennDiagram)文氏图是理解集合运算的直观工具。图中展示了全集U下，集合A和B的各种运算结果：A∪B(并集)、A∩B(交集)、A-B(差集)以及Ā(补集)。不同颜色的区域清晰对应了不同运算包含的元素范围。补运算(Complement)集合运算的重要组成部分，描述“不属于”的关系▌定义与符号设U为全集，集合A的补集定义为：Ā=U-A={x|x∉A}补集是一个相对概念，始终是相对于“全集U”而言的。它包含了全集中所有不属于集合A的元素。💡关键点：补集将全集划分为互斥的两部分：集合A和它的补集Ā，二者的交集为空集，且二者的并集为全集。运算性质（一）01/交换律(CommutativeLaw)并运算和交运算满足交换律，即交换两个集合的位置，运算顺序不影响最终结果。A∪B=B∪AA∩B=B∩A02/结合律(AssociativeLaw)并运算和交运算满足结合律，即对于三个及以上集合的连续运算，无论以何种方式组合运算顺序，最终结果保持一致。(A∪B)∪C=A∪(B∪C)(A∩B)∩C=A∩(B∩C)运算性质（二）01/吸收律(AbsorptionLaw)一个集合与它和另一个集合的交集做并运算，结果还是它本身。同理，一个集合与它和另一个集合的并集做交运算，结果也是它本身。◈公式一：A∪(A∩B)=A◈公式二：A∩(A∪B)=A

02集合的幂运算POWERSETOPERATION幂集的定义与性质定义：幂集(PowerSet)集合A的幂集记作ρ(A)，是由A的所有子集组成的集合。其数学描述为：ρ(A)={x|x⊆A}性质：基数(Cardinality)设集合A的元素个数为|A|=n，则其幂集的元素个数为|ρ(A)|=2ⁿ。这表明幂集的规模随原集合元素数量呈指数级增长。示例：集合A={a,b}首先列出A的所有子集（包含空集和自身）：∅,{a},{b},{a,b}计算结果与验证将上述子集收集构成幂集：ρ(A)={∅,{a},{b},{a,b}}(共4个元素，即2²，符合性质)03集合的笛卡尔积运算CARTESIANPRODUCT序偶与笛卡尔积01.序偶(OrderedPair)序偶<x,y>是一个有序对。两个序偶相等当且仅当它们对应的元素都相等，即：<x,y>=<x',y'>⇔x=x'且y=y'02.笛卡尔积(BinaryProduct)集合A与B的笛卡尔积由所有第一个元素来自A，第二个元素来自B的序偶构成：A×B={<u,v>|u∈A,v∈B}03.n元笛卡尔积通过递归方式定义多个集合的笛卡尔积，即前n-1个集合的笛卡尔积与第n个集合的二元笛卡尔积：A₁×A₂×…×Aₙ=(A₁×…×Aₙ₋₁)×Aₙ笛卡尔积示例题目设定给定三个集合：•A={2,4},B={3,4,5},C={a,b}请计算：A×C,C×A和A×∅笛卡尔积（CartesianProduct）是将两个集合中的元素进行有序配对的运算，记作A×B。其本质是所有有序二元组<x,y>的集合，其中x来自集合A，y来自集合B。计算结果解析•A×C={<2,a>,<2,b>,<4,a>,<4,b>}•C×A={<a,2>,<a,4>,<b,2>,<b,4>}•A×∅=∅×A=∅(空集与任何集合的笛卡尔积均为空集)💡重要性质：笛卡尔积通常不满足交换律。即一般情况下，A×C≠C×A，因为有序对的顺序是不可交换的。笛卡尔积的性质笛卡尔积也有一些重要的性质。特别地，它对于并、交、差运算满足分配律。01与并运算的分配律A×(B∪C)=(A×B)∪(A×C)A与“B和C的并集”的笛卡尔积，等于“A与B的笛卡尔积”和“A与C的笛卡尔积”的并集。02与交运算的分配律A×(B∩C)=(A×B)∩(A×C)A与“B和C的交集”的笛卡尔积，等于“A与B的笛卡尔积”和“A与C的笛卡尔积”的交集。03与差运算的分配律A×(B-C)=(A×B)-(A×C)A与“B和C的差集”的笛卡尔积，等于“A与B的笛卡尔积”和“A与C的笛卡尔积”的差集。核心概念总结集合论是现代数学的基石，本节课我们梳理了集合的三大核心运算模块。G1·基本运算并(∪)·交(∩)·差(-)·补(̄)集合间最基础的二元操作，熟练掌握其严格定义及直观的文氏图表示方法。G2·幂运算幂集ρ(A)，|ρ(A)|=2ⁿ由集合A的所有子集构成的集合，其元素个数呈指数级增长。G3·笛卡尔积A×B={<u,v>|u∈A,v∈B}构建“序偶”的关键运算，为定义关系、函数、以及后续代数结构奠定基础。💡关键提示：运算定律是解题的“核武器”

集合运算的交换律、结合律、分配律和德摩根律，是将复杂集合表达式化简、以及进行逻辑证明的有力工具，务必熟练记忆并灵活运用。1.3关系2026年4月第1章集合论基础：概念与运算计算机科学中的数理逻辑目录CONTENTS01关系的定义与表示介绍二元关系和n元关系的定义，以及关系图和关系矩阵两种直观表示方法。02关系的特性与闭包学习关系的自反、对称、传递等五大特性，并掌握如何构造关系的闭包。03等价关系深入理解等价关系的定义、等价类的概念，以及它与集合划分的一一对应关系。04序关系学习序关系的定义，掌握用哈斯图表示序关系，并了解其中的特殊元素。01关系的定义与表示DEFINITIONANDREPRESENTATIONOFRELATIONS集合论·基础理论关系的定义01.什么是关系？从集合论的角度来看，关系本质上是笛卡尔积的子集。02.二元关系(BinaryRelation)在离散数学中，最常见、应用最广泛的是二元关系。•它是两个集合笛卡尔积A×B的子集，直观描述了集合A中元素与集合B中元素之间的配对联系。定义域与值域•定义域Dom(R):关系R中所有序偶的第一分量构成的集合。•值域Ran(R):关系R中所有序偶的第二分量构成的集合。三种特殊关系•全关系：笛卡尔积A×B本身。•空关系：不包含任何序偶的空集∅。•相等关系：集合中元素与自身相等的关系E_A。核心洞察关系不仅仅是数据的罗列，而是对“联系”的数学抽象化描述。二元关系奠定了关系型数据库、图论以及逻辑推理的基础。关系的表示：关系图▍关系图的定义在离散数学中，关系图是一种直观的图形化表示方法：•用结点(Vertex)表示集合中的元素。

•用有向边(Edge)表示元素之间的二元关系（序偶）。场景示例：学生选课系统构建一个从“学生集合”到“课程集合”的二元关系R1.定义集合：•学生集合A={a,b,c,d,e,f}

•课程集合B={α,β,γ,δ,η}2.选课关系R：R={<𝑎,𝛼>,<𝑎,𝛿>,<𝑏,𝛼>,<𝑏,𝛽>,<𝑐,𝛾>,<𝑒,𝛼>,<𝑓,𝛾>}

💡核心价值：关系图能够清晰、直观地展示元素之间的映射与关联，一眼就能看出“谁选了哪门课”，解决了纯符号表示不够直观的问题。关系的表示：关系矩阵📐核心定义1.矩阵维度：设关系R是从集合A到集合B的关系，则关系矩阵M_R的维度为|A|×|B|，即行数等于集合A的元素个数，列数等于集合B的元素个数。2.元素取值规则：对于矩阵中第i行第j列的元素M_R[i,j]，若A中的第i个元素与B中的第j个元素满足关系R，则值为1；否则为0。🎓经典示例：学生选课关系假设集合A代表“学生”（如：张三、李四、王五），集合B代表“课程”（如：离散数学、计算机组成、人工智能）。若张三选修了离散数学和人工智能，在关系矩阵中对应的两行位置标记为1，其余位置标记为0。矩阵结构清晰地记录了所有学生的选课状态。💡核心对应关系：关系矩阵中的“1”，与关系图中的“边”存在精确的一一对应关系。这种数字化的表达方式非常利于计算机存储和处理。关系的逆运算(InverseRelation)关系的逆运算是集合论中关系的基本运算之一，通过反转关系中序偶的元素位置，构建从原值域到原定义域的新关系。定义设R为A到B的关系，则R的逆关系R⁻¹(或R~)是B到A的关系：R⁻¹={<y,x>|<x,y>∈R}性质•(R⁻¹)⁻¹=R

•(A×B)⁻¹=B×A

•∅⁻¹=∅关系矩阵逆关系的矩阵是原关系矩阵的转置。关系图将原关系图中所有边的方向反转。关系的合成运算(Composition)01/合成关系的定义设R为A→B的关系，S为B→C的关系，则R与S的合成关系R∘S是A→C的关系：R∘S={<x,z>|∃y∈B,使<x,y>∈R且<y,z>∈S}02/合成关系的性质●结合律：(R∘S)∘T=R∘(S∘T)●逆运算：(R∘S)⁻¹=S⁻¹∘R⁻¹03/关系矩阵的合成合成关系R∘S的关系矩阵，等于R的矩阵与S的矩阵的布尔积(BooleanProduct)。即：M(R∘S)=M(R)⊙M(S)（按矩阵乘法规则，最后将“和”改为“或”）02关系的特性与闭包PROPERTIESANDCLOSURESOFRELATIONS关系的五大特性在集合论中，经常讨论关系的以下五种基本特性：自反的对任意的x∈A，均有xRx。反自反的对任意的x∈A，xRx均不成立。对称的如果xRy，则yRx。反对称的若xRy且yRx，则x=y。传递的若xRy且yRz，则xRz。特性的判定01/关系图与矩阵●自反性：在关系图中，每个顶点都有自环；在关系矩阵中，主对角线上的所有元素均为1。●对称性：在关系图中，任意两个顶点间如果有边则边都成对出现（无单向边）；在关系矩阵中，矩阵为对称矩阵。●传递性：在关系图中，若存在路径a→b和b→c，则一定存在直接边a→c；在矩阵运算中满足相应的包含关系。02/集合刻画设R是集合A上的二元关系，我们可以通过集合的包含与相等关系来严谨刻画其性质：▪自反：全域关系的对角线集合EA⊆R｜对称：R=R⁻¹(R的逆关系)｜传递：R²⊆R💡判定方法总结在实际应用中，“关系图与矩阵”方法直观、易操作，适合快速判断；“集合刻画”方法则更精确、严谨，常用于理论证明与推导，二者互为补充。特性闭包：关系的最小完备化闭包是集合论中的核心概念。如果一个二元关系R不具备某种特定性质（如自反性、对称性或传递性），我们往往需要构造一个包含R的、且具有该性质的“最小”关系，这个关系就称为R关于该性质的闭包。01自反闭包r(R)定义：包含关系R的最小自反关系。构造方法：在原关系中加入所有的“自环”。公式：r(R)=R∪Eₐ

（Eₐ为集合A上的恒等关系）02对称闭包s(R)定义：包含关系R的最小对称关系。构造方法：将所有单向关系变为双向关系。公式：s(R)=R∪R⁻¹

03传递闭包t(R)定义：包含关系R的最小传递关系。构造方法：添加所有隐含的间接路径。公式：t(R)=R∪R²∪R³∪...

03等价关系EQUIVALENCERELATIONS等价关系与等价类定义：等价关系设R是集合A上的一个二元关系，如果R同时满足：1.自反性(∀x∈A,xRx)；2.对称性(若xRy，则yRx)；3.传递性(若xRy且yRz，则xRz)，则称R为A上的等价关系。定义：等价类设R是集合A上的等价关系，对于任意元素a∈A，集合[a]ₐ={x|x∈A且aRx}称为元素a关于R的等价类。直观地说，这是A中所有与a“等价”的元素的集合。▍经典示例：整数集上的“模4相等”在整数集合Z上定义关系R：对于任意整数x,y，当且仅当(x-y)能被4整除时，xRy。容易验证R满足自反、对称和传递性，因此它是Z上的一个等价关系，通常记作x≡y(mod4)。▍模4等价关系的划分结果这个关系将所有整数分成了4个互不相交的等价类：[0]={...,-8,-4,0,4,8,...}|[1]={...,-7,-3,1,5,9,...}

[2]={...,-6,-2,2,6,10,...}|[3]={...,-5,-1,3,7,11,...}等价关系与划分01/等价关系→划分一个等价关系的所有等价类的集合，构成了原集合的一个划分。简单来说，我们将具有相同等价关系的元素归为一类，每一个这样的类就是一个“划分块”，所有互不相交的划分块组合起来，恰好完整覆盖了整个原集合。02/划分→等价关系给定一个集合的划分，我们可以反过来定义一个等价关系。定义规则：两个元素之间存在等价关系，当且仅当它们属于同一个划分块。这样定义的关系，自然满足自反性、对称性和传递性。04序关系ORDERRELATIONS序关系与哈斯图定义：序关系(PartialOrder)集合A上的二元关系R，如果同时满足以下三个性质，则称R为一个序关系，通常用符号“≤”表示：

1.自反性：对所有a∈A，有a≤a

2.反对称性：若a≤b且b≤a，则a=b

3.传递性：若a≤b且b≤c，则a≤c哈斯图(HasseDiagram)一种用于可视化表示偏序集（Poset）的简化图。核心简化规则：1.省略自反环：由于序关系天然满足自反性，图中每个顶点的自反环无需画出。

2.省略传递边：如果关系可以通过中间节点间接推出，则省略该直接边，使图形更简洁。

3.利用位置表顺序：节点按“从下到上”的位置关系来表示元素间的“≤”关系，，省略向上箭头，避免了大量箭头的使用。用途：哈斯图是离散数学中分析偏序集结构的重要工具，能帮助我们直观地识别极大元、极小元、最大元、最小元等关键元素。序关系中的特殊元素01.特殊元素(Overview)在一个有序集（如偏序集、全序集）中，元素之间存在“先后”或“大小”关系。我们常常关注一些具有特殊地位的元素，它们是分析集合结构与层级关系的基础。02.最大元/最小元(Greatest/Least)定义在子集B上：若存在元素b，使得B中所有元素都“小于等于”b，则b是子集B的最大元。同理可得最小元。💡特点：最大元必须与子集内所有元素“可比”，且若存在则唯一。03.极大元/极小元在子集B中，若没有任何元素比该元素更“大”，则为极大元；若没有比它更“小”的元素，则为极小元。≠最大元：不要求与所有元素可比，且可以有多个。04.上界/下界(Bounds)在包含子集B的整个集合A中寻找。B中所有元素都“小于等于”a，则a是B的上界；同理可得下界。⚠️注意：上界/下界不一定属于子集B本身。💡核心辨析•范围差异：极大/最大元在子集B内；上/下界在全集A中。•数量差异：最大元唯一；极大元可以有多个。1.4函数2026年4月第1章集合论基础：概念与运算计算机科学中的数理逻辑目录CONTENTS01函数的概念与合成介绍函数的定义、表示方法、合成运算以及函数的映像。02特殊函数：单射、满射与双射深入解析单射、满射和双射的定义与关键性质。03函数的逆探讨逆函数的严谨数学定义，并详细分析左逆、右逆的区别以及函数逆像的计算方法。04核心概念总结系统汇总本章学习的关键定义、重要定理与基本性质，通过梳理强化理解，巩固学习成果。01函数的概念与合成CONCEPTANDCOMPOSITIONOFFUNCTIONS集合论·基础理论函数的定义什么是函数？函数是一种特殊的二元关系，核心在于“输入”与“输出”的确定性映射关系。它为集合中每一个有效的输入值，都严格地分配了唯一的一个输出值。常用表示法在数学和计算机科学中，我们最常用的形式是：y=f(x)x：自变量（输入）|y：因变量/函数值（输出）|f：映射规则关键性质I：全域性函数的定义域必须是集合X的全部元素，不存在“被遗漏”的输入值。关键性质II：单值性在映射关系中，每一个输入值x都必须且只能对应唯一一个输出值y。核心总结如果一个关系不满足全域性或单值性，那么它就不能被称为“函数”，而只是一个普通的“关系”。函数的表示方法函数描述了自变量与因变量之间的对应关系，为了满足不同场景下的描述与分析需求，主要包含以下几种经典的表示方法：列表法将自变量与函数值一一对应排列成表，直观清晰，常用于定义域有限的情况。图像法利用坐标平面上的点或有向图表示函数关系，能够直观展示函数的变化趋势与几何特征。解析法用数学公式y=f(x)精确描述，便于进行严格的理论推导和数值计算，是最常见的表示形式。函数的合成运算映射关系图示图中直观展示了集合X、Y、Z之间的映射路径：元素x首先通过函数f映射到集合Y，接着作为输入，通过函数g映射到集合Z。这一完整的“流水线”过程，即为合成函数g∘f。数学定义FormalDefinition前提：设函数f:X→Y，g:Y→Z合成函数构造规则：1.运算符号：g∘f，读作“f合成g”。2.定义域与值域：g∘f:X→Z，即输入来自X，输出归于Z。3.映射法则：∀x∈X，有(g∘f)(x)=g(f(x))。关键理解：合成运算满足“右结合律”的计算顺序，即“由内向外”：先计算内部的f(x)，再将结果作为参数代入外部函数g中进行计算。函数的映像定义：设映射f:X→Y，若A是X的子集(A⊆X)，则集合A的映像f'(A)定义为：A中所有元素通过映射f得到的像点所构成的集合。示例：观察下方函数映射图，我们可以得到：单元素子集{a}的映像是{1}；全集{a,b,c,d}的映像是{1,4,5}。重要性质空集的映像依然是空集：f'(∅)=∅此图直观展示了定义域集合到陪域集合的映射关系。通过观察可以清晰地理解“子集映像”的概念。02特殊函数：单射、满射与双射SPECIALFUNCTIONS:INJECTION,SURJECTION,BIJECTION特殊函数的定义：单射、满射与双射在数学集合论中，单射、满射和双射是描述两个集合之间映射关系的三种最基本的函数类型。01单射(Injection)定义：一对一函数(One-to-one)

若函数定义域中任意两个不同的元素，其映射到值域中的像也一定不同，则该函数为单射。即x₁≠x₂⇒f(x₁)≠f(x₂)。02满射(Surjection)定义：映上函数(Onto)

若函数的值域完全等于其陪域，即陪域中的每一个元素都能找到至少一个原像，则该函数为满射。03双射(Bijection)既是单射又是满射，实现了集合间完美的“一一对应”。特殊函数的性质01/合成性质在函数的复合运算∘下，特殊映射的性质具有很好的“保持性”：●单射保持：若函数f和g均为单射，则其合成g∘f也必为单射。●满射保持：若函数f和g均为满射，则其合成g∘f也必为满射。●双射保持：若函数f和g均为双射，则其合成g∘f也必为双射。02/反向推断➜如果合成函数g∘f是单射⇒参与合成的第一个函数f必是单射。➜如果合成函数g∘f是满射⇒参与合成的第二个函数g必是满射。💡核心启示这些规则为我们分析复杂函数关系提供了逻辑捷径。在不知道函数具体定义时，仅通过合成结果的映射类型，即可反推原始函数的性质。置换(Permutation)▍核心定义设X是一个有限集合。若函数p:X→X满足：既是单射(Injective)又是满射(Surjective)，则称p为集合X上的一个置换。通俗理解：置换本质上是对集合中的元素进行“重新排列”，且每一个元素都有唯一的去处，不重不漏。标准表示法：两行式第一行列出集合中的全部原元素，第二行对应列出其映射后的像点，直观展示元素的去向。4次置换的经典例子p=(1234)(2413)解释：该置换将集合{1,2,3,4}中的元素1映射到2，元素2映射到4，元素3映射到1，元素4映射到3。03函数的逆INVERSEOFFUNCTIONS逆函数与左右逆01/逆函数(InverseFunction)只有双射函数(Bijection)才有逆函数f⁻¹。双射同时具备单射与满射的性质，保证了每一个输入有且仅有一个输出，且每一个输出都有对应的输入。➤核心特点：完美还原对于任意x∈定义域，若y=f(x)，则必有x=f⁻¹(y)。02/左逆与右逆(Left/RightInverse)当函数不满足双射条件时，我们引入“单侧逆”的概念来实现部分反向操作。•左逆(LeftInverse)：单射函数拥有左逆。•右逆(RightInverse)：满射函数拥有右逆。函数的逆像定义：设f:X→Y,A⊆Y，集合A的逆像f‘’(A)是所有“像点落在A中”的源点的集合，即f‘’(A)={x∈X|f(x)∈A}。示例：观察函数映射关系图：f‘’({1})={a}，因为只有a映射到1；而f‘’({4,5})={b,c,d}，因为b,c,d的像点都落在集合{4,5}中。关键注意：即使函数f不是双射，没有逆函数，依然可以讨论集合的“逆像”。这是“逆函数”概念的集合论推广，适用范围更广。2.1集合的归纳定义2026年4月第2章集合论基础：归纳计算机科学中的数理逻辑目录CONTENTS01集合的归纳定义介绍归纳定义的概念，并通过非负偶数集的例子来理解其结构。02归纳定义的三个条款详细解析基础条款、归纳条款和终极条款的定义、形式化及其作用。03核心概念总结汇总归纳定义的关键概念，包括完备性和纯粹性。04应用示例通过一个具体的例子展示如何应用归纳定义来证明一个元素属于某个集合。01集合的归纳定义INDUCTIVEDEFINITIONOFSETS集合论·基础理论归纳定义的概念▍什么是归纳定义？一种通过指定初始元素和生成规则，来系统性地描述和构造集合的数学方法。它通过“基础”与“归纳”的逻辑，清晰界定集合的范围。▍典型应用场景它是定义具有递归结构的无限集合的标准工具。例如：所有合法的算术表达式、编程语言中的语法树、自然数集以及计算机科学中的各类形式语言等。▍核心优势相比列举法或描述法，归纳定义表达能力更强，能精准刻画复杂的结构特征。它是计算机科学、数理逻辑和形式化验证领域中广泛应用的理论基石。▍经典结构三要素1.基础条款：规定集合中最基本的初始元素。

2.归纳条款：规定如何从已知元素生成新元素的规则。

3.终极条款：限定集合中仅包含前两条所生成的元素。示例：非负偶数集E⁺▍归纳定义(InductiveDefinition)①基础条款(BaseClause)：0∈E⁺，规定集合中最基本的元素。②归纳条款(InductiveClause)：若x∈E⁺，则x+2∈E⁺。这是生成新元素的构造规则。③终极条款(ExtremalClause)：只有通过以上两条规则有限步推导得到的数，才属于E⁺。它排除了所有“意外”的元素。核心思想：从“原点”出发，逐步生成这种定义方法广泛应用于数学和计算机科学（如定义表达式、数据结构等）。结论：从0开始，每步加2，可穷尽所有非负偶数。推导过程示例：证明6∈E⁺证明目标：验证数字6是否满足非负偶数集E⁺的归纳定义，即通过有限步骤推导证明6属于该集合。步骤1：基础条款应用根据非负偶数集的定义，基础条款明确规定：0是E⁺的初始元素。因此我们直接得出结论：0∈E⁺。步骤2：归纳条款递推1.作用于0：0+2=2⇒2∈E⁺

2.作用于2：2+2=4⇒4∈E⁺

3.作用于4：4+2=6⇒6∈E⁺

(每一步均遵循归纳规则：若x∈E⁺，则x+2∈E⁺)结论：终极条款确认根据终极条款，E⁺中的所有元素都必须能通过基础条款和有限次应用归纳条款得到。

由于数字6已通过有限步骤被生成，因此我们最终证明了：6∈E⁺02归纳定义的三个条款THREECLAUSESOFINDUCTIVEDEFINITION三个条款的定义一个完整的归纳定义由三个条款构成。这三个条款各司其职，共同完成了对集合元素的严谨定义，缺一不可。01基础条款(BaseItem)指定集合的初始元素，是整个定义的逻辑起点。02归纳条款(InductiveItem)定义从已有元素生成新元素的规则，决定了集合如何扩展。03终极条款(TerminalItem)限定集合的范围，确保集合中的所有元素都能通过基础条款和归纳条款被有限步推导出来。基础条款与归纳条款01/基础条款▍作用

指定被定义集合的基本元素，是定义的起点，确保集合非空。▍形式

对任意给定的s，如果C(s)为真，那么s∈S。

即：明确列举或通过判定条件给出集合的“种子”元素。02/归纳条款▍作用

描述如何从集合的已知成员出发，通过构造规则生成新成员的过程，决定了集合的“生长”方式。▍形式

如果s₁,s₂,...,sₖ∈S，且f是一个k元构造函数，那么f(s₁,...,sₖ)∈S。

即：通过构造规则不断扩充集合成员。终极条款(ClosureClause)▍条款作用规定集合中的每一个元素都必须是通过有限次应用基础条款和归纳条款推导出来的。它在归纳定义中起到“封顶”或“收尾”的关键作用。▍形式化描述对任意给定的s，s∈S当且仅当它可以通过有限次应用上述基础条款与归纳条款被构造出来。▍核心目的：保证定义的精确性与完备性通过明确界定集合元素的来源，严格限制集合的范围，防止引入不相关的、无法通过规则生成的“外来”元素，确保我们定义的集合“不多不少”，正好包含所有想要的合法元素。没有此条款，归纳定义在逻辑上是不完整的。三个条款的作用总结基础条款(BaseClause)“定义的基石”提供了基础元素。确立了集合中必须包含的初始对象，是一切扩展的前提。归纳条款(InductiveClause)“扩展的动力”提供了生成新元素的机制。通过规则从已知元素构造出新元素，赋予集合生长与扩展的能力。终极条款(ExtremalClause)“定义的边界”提供了定义的边界，确保了集合的范围。明确规定了集合仅包含由前两条规则生成的元素，排除一切冗余。三者相辅相成，缺一不可这三个条款共同构成了一个严谨、精确且功能强大的集合定义工具，既保证了集合元素的完备性，又保证了其纯粹性。完备性与纯粹性01/完备性(Completeness)由基础条款和归纳条款共同保证。这两条规则从“初始”和“生成”两个维度构建集合。✅核心作用：确保所有我们期望在集合中的元素，都能被有限步推导出来，不存在“该有却没有”的情况。02/纯粹性(Purity)由终极条款保证。❌核心作用：确保集合中只包含那些可以被推导出来的元素。🔑逻辑结论完备性与纯粹性共同确保了归纳定义能够唯一地、精确地刻画一个集合。这是数学归纳法有效性的逻辑基石。应用示例：定义合法括号串🔍归纳定义(InductiveDefinition)▸基础条款(BaseCase):空字符串""是合法括号串。▸归纳条款(InductiveStep):若A,B是合法串，则(A)和AB也是合法串。▸终极条款(ExtremalClause):只有通过有限次使用以上两条生成的串才是合法的。🧩推导示例(DerivationExamples)1.空串""：根据“基础条款”直接判定为合法。2.串"()"：对空串""应用归纳规则(A)，得到合法串。3.串"(())"：对合法串"()"应用归纳规则(A)得到。4.串"()()"：将两个合法串"()"和"()"应用归纳规则AB连接。2.2归纳法及其应用2026年3月第2章集合论基础：归纳计算机科学中的数理逻辑目录CONTENTS01结构归纳法介绍结构归纳法的核心思想、推导过程。02归纳法在计算机科学中的应用通过列表和树的例子，展示归纳定义和归纳法在计算机科学中的应用。03数学归纳法学习第一、第二数学归纳法，理解其与结构归纳法的关系。04核心概念总结汇总归纳法的关键概念和证明要点，巩固对归纳法整体框架的理解。01结构归纳法STRUCTURALINDUCTION集合论·基础理论结构归纳法的核心思想❓什么是结构归纳法？它是一种基于集合归纳定义的数学证明方法。🎯证明目标证明一个由归纳定义生成的集合S中的所有元素都满足某种给定的性质P。🔑核心步骤将“证明元素属于集合S”的构造逻辑，完全映射并变换为“证明该元素满足性质P”的逻辑过程。🔄关键变换把集合归纳定义中的条款，一一对应地转化为证明中的“引理”或“子命题”，逐一证明。推导过程的变换从“s∈S”到“P(s)”在形式化证明中，我们常常需要将“证明一个元素属于某个集合”的逻辑链条，系统地转化为“证明该元素满足某个特定性质”的推导过程。▌核心变换规则将证明的每一步进行对应替换，保证逻辑严密性不丢失①结果栏替换：将断言部分的“s∈S”直接替换为“P(s)”。②理由栏替换：将引用依据从定义集合的“条款(i)”替换为定义性质的“引理(i)”。结构归纳法定理定理2.1核心表述：若对集合S的归纳定义中所有基础条款和归纳条款变换后得到的“引理(1)”、“引理(2)”...均成立，则“集合S中的任意元素都满足性质P”这一命题成立。基础引理(BaseCase)：严格证明“基础条款”中所指定的所有初始元素，都无一例外地满足性质P。▍归纳引理(InductiveStep)这是归纳的关键步骤。需要证明：如果已知集合中的某些元素已经满足性质P（归纳假设），那么通过集合定义中的“归纳条款”由这些已知元素生成的所有新元素，也必然满足性质P。▍逻辑闭环与结论只要上述两个引理（基础引理和归纳引理）都能被严格证明，根据定理2.1，我们可以确定：集合S中的每一个元素都满足性质P。02归纳法在计算机科学中的应用APPLICATIONSINCOMPUTERSCIENCE列表(List)的归纳定义列表作为最基础的数据结构，其定义由“基础”、“归纳”和“终极”三个部分组成。01基础条款(BaseCase)定义了最基本的列表形式：[]∈'alist含义：空列表（EmptyList）是所有同类型列表的基石，它不包含任何元素。02归纳条款(InductiveStep)定义了生成更长列表的规则：x::xs∈'alist含义：如果xs是一个列表，那么在其头部“::”一个元素x，得到的结果依然是同类型的列表。通过反复应用，可生成任意长度的列表。03终极条款(ExtremalClause)隐式地定义了列表的范围边界：“有限步生成原则”含义：所有合法的列表对象，都必须且仅能通过有限次应用“基础条款”和“归纳条款”来生成。列表操作：长度函数len01/递归定义■len([])=0■len(x::xs)=1+len(xs)说明：递归定义与列表的归纳定义结构一一对应，通过分解列表的表头(x)与尾部(xs)，将求长度的问题转化为求解更小规模的子问题。02/正确性证明·基础情况空列表是列表的基本构成单元，其长度在直觉上即为0。len([])=|[]|=0，显然成立。03/正确性证明·归纳步骤假设len(xs)=|xs|成立（归纳假设），那么对于任意列表元素x::xs：len(x::xs)=1+len(xs)=1+|xs|=|x::xs|即对于所有列表，长度函数定义均成立。列表操作：连接操作`@`01/递归定义空列表与任意列表连接：[]@ys=ys非空列表与任意列表连接：(x::xs)@ys=x::(xs@ys)02/正确性证明我们可以使用结构归纳法(StructuralInduction)来严格证明该递归定义的正确性。通过对列表左侧操作数的结构进行归纳，可以确保这个定义在任何有限长度的列表上都能正确计算，并符合我们对“连接”这一操作的直观理解。💡直观理解示例假设xs=[1,2],ys=[3,4]，根据定义展开：

(1::[2])@[3,4]=1::([2]@[3,4])=1::(2::([]@[3,4]))=[1,2,3,4]树(Tree)的归纳定义与遍历图示：命题公式树结构右图直观展示了逻辑公式p→(p∧¬q)的树状结构▍归纳定义(InductiveDefinition)树是一种典型的递归数据结构。它可定义为：要么是一个不可再分的“原子节点”，要么是由若干子树组合而成的“复合节点”。命题逻辑公式是树结构的经典应用场景。▍先序遍历(Pre-orderTraversal)一种最基础的树遍历算法，遵循严格的递归顺序：“访问根节点→递归遍历左子树→递归遍历右子树”。💡核心要点：结构归纳法是证明这类算法正确性的标准工具。03数学归纳法MATHEMATICALINDUCTION第一数学归纳法第一数学归纳法是一种用于证明与自然数相关的命题成立的核心逻辑工具。01归纳基础证明当自然数取第一个值（通常取0）时，命题P(0)成立。这是整个归纳的起点，必须保证基础情况绝对正确，否则后续的递推将毫无意义。02归纳过程假设对于任意自然数k，命题P(k)成立（这一假设称为“归纳假设”）。在归纳假设的前提下，利用逻辑推导证明P(k+1)也成立，从而建立递推关系。03得出结论当归纳基础和归纳过程两步都被严格证明后，根据数学归纳法原理，可以得出结论：所有自然数都具有性质P数学归纳法的变形：起始于r个值01/归纳基础对于数学归纳法的这种变形，归纳基础不再仅仅是验证一个初始值，而是需要验证前r个初始值都成立。具体来说，我们需要证明：P(0),P(1),...,P(r-1)都成立。02/归纳过程假设当n=k时命题P(k)成立，利用这个前提条件，推导出当n=k+r时，命题P(k+r)也成立。从而建立递推链条。💡典型示例求证：使用面值为3分和5分的硬币，可以组成8分以上的任何币值。分析：在此例中，我们需要先验证8、9、10分这三个基础情况均能被组合出来，再进行归纳推导。强数学归纳法01/归纳基础证明命题P(0)成立。这是强归纳法证明的基石，用于确立整个逻辑链条的起点。02/归纳过程(核心差异)与第一数学归纳法不同，强数学归纳法的假设更强：假设对于所有满足0≤i<k的自然数i，命题P(i)均成立（强归纳假设）。在此基础上，证明P(k)必然成立。▍典型应用场景：取棋子博弈策略证明证明：在两堆数量完全相同的棋子中，两人轮流取棋子（每次只能从一堆取任意数量），规定最后取完棋子者获胜。在该规则下，后取者拥有必胜策略。归纳证明的关键归纳基础(BaseCase)证明的起点，必须进行严格验证。通常选取自然数的初始值（如n=0或n=1）来确认命题在该情况下成立，为整个证明提供根基。归纳过程(InductiveStep)证明的核心，逻辑必须严密。核心在于证明“若对任意k成立，则对k+1也成立”，从而实现从“有限”到“无限”的逻辑跨越。缺一不可仅有归纳基础，无法将结论推广到所有自然数，只能证明孤立的个别情况。逻辑严谨仅有归纳过程，缺少基础支撑，会导致“空中楼阁”式的逻辑谬误。核心概念总结本章介绍了归纳法相关的核心概念，理解这些概念对于掌握逻辑证明与算法验证至关重要：结构归纳法通用的证明方法，适用于所有归纳定义的集合。数学归纳法结构归纳法在自然数集上的一个重要特例。归纳基础归纳证明的逻辑起点，用于验证最小结构单元的性质。归纳过程证明的核心环节，建立递推链条以推导整体结构性质。3.1命题演算基本概念计算机科学中的数理逻辑2026年4月第3章命题演算目录CONTENTS01命题与联接词了解命题的定义，掌握五种基本的逻辑联结词及其含义。02命题公式及其真值学习如何构建合法的命题公式，并理解公式在不同指派下的真值。03范式掌握将任意命题公式转化为范式（合取范式与析取范式）的方法。04联结词的扩充与规约探讨联结词的完备集，理解如何用最少的联结词表达所有逻辑关系。01命题与联接词PROPOSITIONSANDCONNECTIVES什么是命题？📝命题的定义(Proposition)命题是指对确定事物作出判断的陈述句。它的关键特征是拥有明确的真值(TruthValue)：•要么为真(True,1)，要么为假(False,0)，非真即假，非假即真。🚫非命题示例(Non-Proposition)若语句无法确定真假，或非陈述句，则不是命题。例如：•变量不确定：“x+y<0”(x,y未知)•逻辑悖论：“我说的这句话不对”•非陈述句：“你吃饭了吗？”（疑问）/“请保持安静”（祈使)01/原子命题(Atom)最基本的、不可再分的命题，不包含任何逻辑联结词。例：“雪是白的。”、“太阳从东方升起。”02/复合命题(Composite)由一个或多个原子命题，通过“与、或、非、如果...那么...”等联结词组合而成。例：“2是质数，且2是偶数。”基本真值联结词(1/3)01/否定词(¬)符号：¬(not)定义：设p为命题，¬p表示对p的真值取反。真值表：解读：p为真时，¬p必为假；p为假时，¬p必为真。02/合取词(∧)符号：∧(and)定义：设p,q为命题，p∧q表示“p并且q”。真值表：解读：只有当p和q同时为真时，p∧q才为真。基本真值联结词(2/3)01/析取词(∨)符号：∨(逻辑“或”，inclusiveor)定义：设p,q为任意命题，p∨q表示p和q的析取式，读作“p或q”。真值表：

核心解读：只要p和q中“至少有一个”为真，整个析取式的结果就为真。只有当p、q同时为假时，结果才为假。02/蕴涵词(→)符号：→(如果...那么.../条件命题)定义：设p,q为任意命题，p→q表示“若p，则q”，其中p称为前件，q称为后件。💡关键提醒：蕴涵词的逻辑判定这是逻辑中最容易产生直觉偏差的联结词：只有当“前件为真，后件为假”时，p→q才是假的。除此之外的所有情况，包括“前件为假”时，整个蕴涵式都为真。基本真值联结词(3/3)：双向蕴涵词(↔)符号定义设p,q为两个命题，p↔q表示复合命题“p当且仅当q”。该命题也常被称作“双条件命题”。真值表2.语义解读“当且仅当”表明两个命题在逻辑上是完全等价的。

即：p与q同真，或同假时，复合命题为真；若一真一假，则为假。3.逻辑等价式双向蕴涵词可拆解为两个单向蕴涵词的合取：

p↔q

(p→q)∧(q→p)典型应用常用于数学定义、定理证明及编程中的条件判断，以精确表达“充要条件”关系。02命题公式及其真值PROPOSITIONFORMULASANDTHEIRTRUTHVALUES命题公式的定义定义3.1：命题公式(propositionformula)是由命题常元、变元及逻辑联结词，通过有限次规则组合而成的符号串，其合法性由以下三条递归规则严格定义。G1·基础条款命题常元t,f、变元p,q,r...是原子公式。构成公式的最小单元，是定义的基石，不可再分。G2·归纳条款若A,B是公式，则(¬A),(A∧B),(A∨B),(A→B),(A↔B)也是公式。通过联结词组合已知公式，生成更复杂的新公式。G3·终极条款仅有限步引用前两条规则得到的符号串，才是公式。排除其他可能，确保公式可构造、可验证。括号省略约定

为简化书写，可省略公式最外层括号。联结词结合力强弱顺序为：¬>(∧,∨)>→>↔，遵循此约定可减少冗余括号并提升可读性。递归定义的意义

该定义是典型的归纳定义，从原子公式出发层层嵌套，既清晰描述了公式的构造过程，也为公式性质的归纳法证明提供了逻辑基础。公式的真值与指派▍指派(Assignment)对公式中所有命题变元的一种取值。一个含有n个变元的公式有2ⁿ种可能的指派。▍弄真/弄假若公式A在指派α下取值为真，则称α弄真A；反之，若取值为假，则称α弄假A。▍真值表(TruthTable)列出公式在所有可能指派下的真值的表格，是分析公式真值特征的有效工具。示例：公式¬p→(q∨r)的真值表观察：该公式仅有1种弄假指派，其余7种均为弄真指派。公式的分类永真式Tautology/重言式定义：对任意指派α，公式A的真值均为1，即α(A)=1。无论公式中的命题变元取何值，公式始终为真。永假式Unsatisfiable/矛盾式定义：对任意指派α，公式A的真值均为0，即α(A)=0。无论公式中的命题变元取何值，公式始终为假，也被称为“不可满足式”。可满足式Satisfiable定义：存在至少一个指派α，使得公式A的真值为1，即α(A)=1。公式在某种情况下为真。值得注意的是，永真式是特殊的可满足式。逻辑蕴涵与逻辑等价01/逻辑蕴涵(⊨)定义：公式A逻辑蕴涵公式B(记为A⊨B)，当且仅当所有弄真A的指派也必弄真B。等价描述：A→B是一个永真式(Tautology)。02/逻辑等价(┝┥)定义：公式A逻辑等价公式B(记为A┝┥B)，当且仅当A逻辑蕴涵B且B逻辑蕴涵A。等价描述：A↔B是一个永真式(Tautology)。03范式NORMALFORMS范式基本概念在介绍范式前，先明确几个基本术语：文字(Literal)原子公式或原子公式的否定。

如：p,¬q合取子句由若干个文字的合取组成的公式。

如：p∧¬q∧r析取子句由若干个文字的析取组成的公式。

如：p∨¬q∨r合取范式形如C₁∧C₂∧...∧Cₘ的公式，

其中每个Cᵢ都是一个析取子句。析取范式形如D₁∨D₂∨...∨Dₘ的公式，

其中每个Dᵢ都是一个合取子句。注：范式是命题逻辑中的标准形式，在定理证明和逻辑电路设计中有着广泛的应用。求范式的步骤定理3.4：对任一命题公式，均可作出它的合取范式和析取范式。我们可以通过一套标准化的流程，将任意公式转化为这两种标准形式。01消去→和↔利用逻辑等价式将公式中的蕴含词和双向蕴含词全部替换为基础联结词：•蕴含消除：A→B┝┥¬A∨B•等价消除：A↔B┝┥(A→B)∧(B→A)02否定深入与化简将否定联结词向内深入，直至作用于单个命题变元，并消除冗余：•德摩根定律：¬(A∨B)┝┥¬A∧¬B；¬(A∧B)┝┥¬A∨¬B•双重否定：¬(¬A)┝┥A03应用分配律根据目标范式的不同，应用相应的分配律进行转换：•求合取范式：利用∨对∧的分配律

A∨(B∧C)┝┥(A∨B)∧(A∨C)•求析取范式：利用∧对∨的分配律

A∧(B∨C)┝┥(A∧B)∨(A∧C)主范式与定理主范式定义：在普通范式的基础上，要求每个子句都包含公式中所有的命题变元（或其否定）一次且仅一次。主范式分为两类：主合取范式和主析取范式，它们是命题公式的标准化形式。定理3.5：等价类划分n元命题公式的全体可以划分为2^(2^n)个等价类。每一类中的公式逻辑上相互等价，并且等价于它们共同的、唯一的主合取范式（或主析取范式）。命题公式等价类示意图中展示了所有公式最终都被“规约”到有限的等价类盒子中，每个盒子对应唯一的主范式，代表一种确定的逻辑功能。04联结词的扩充与规约EXPANSIONANDREDUCTIONOFCONNECTIVES完备联结词组当一个联结词组可表示所有一元、二元联结词时，称为完备联结词组

。常见的完备集•{¬,∨,∧}：最常用的集合，包含否定、析取与合取。•{¬,∨}/{¬,∧}：利用德摩根定律，仅需两个联结词即可互相转换。单元素完备集•{↑}(与非词):p↑q≡¬(p∧q)，可表达所有逻辑关系。•{↓}(或非词):p↓q≡¬(p∨q)，同样具备完备表达力。非完备集示例联结词组{∨,∧}不具备完备性。原因：仅通过析取与合取的有限次组合，无法推导出否定联结词“¬”。理论意义：表达的最小化

完备性保证了逻辑语言的表达能力无遗漏，而单元素完备集揭示了逻辑构造的最小化原理：理论上仅需一个逻辑运算即可构建所有复杂逻辑关系。工程价值：硬件实现

在数字电路设计中，“与非门”或“或非门”可作为通用逻辑门使用，极大地简化了集成电路的制造工艺，降低了硬件成本。3.2命题演算形式系统PC计算机科学中的数理逻辑2026年4月第3章命题演算目录CONTENTS01PC系统的组成详细解析PC系统的语言构成和推理规则。02PC中的推理学习证明、定理、演绎等核心概念，并通过实例掌握推理方法。03PC的语义探讨PC系统的语义解释，建立语法与语义的联系。04关于PC的重要元定理深入理解合理性、一致性、完备性和紧致性等元理论性质。01PC系统的组成SYSTEMCOMPOSITIONOFPC形式系统·核心架构语言部分：符号与公式什么是PC的语言？PC（命题演算形式系统）的语言是一种严格定义的形式语言，不包含歧义。它的构成极其简洁，仅由两部分组成：语言部分和推理部分。语言部分基本符号集定义为：∑={(,),¬,→,p₁,p₂,p₃,⋯}公式的定义如下：推理部分：公理与规则PC系统的推理能力由三条公理模式和一条推理规则赋予，它们共同构成了形式推演的基石。A1·肯定后件律A→(B→A)这条公理表明，如果A为真，那么任何公式B都能推出A，体现了蕴含的单调性。A2·蕴含词分配律(A→(B→C))→((A→B)→(A→C))这条公理是蕴含词的分配律，是进行复杂逻辑推演的核心工具。A3·换位律(¬A→¬B)→(B→A)这条公理体现了逆否命题与原命题逻辑等价的思想，是反证法的基础。推理规则：分离规则(modusponens,rₘₚ)

若公式A和公式A→B均成立，则可推出公式B成立。这是PC系统唯一的推理规则，是驱动所有证明的“核心引擎”。02PC中的推理REASONINGINPC基本定义：证明、定理与演绎形式推理的核心概念：1.证明(Proof)一个公式序列，其中每个公式要么是公理，要么是由前面的公式通过分离规则得到。2.定理(Theorem)如果一个公式A存在一个证明，则称A为定理，记作⊢ₚcA。3.演绎(Deduction)在证明的基础上，允许使用一个额外的公式集Γ作为前提进行推导。4.演绎结果(Consequence)若公式A存在以Γ为前提的演绎，则称A是Γ的演绎结果，记作Γ⊢ₚcA。注：这些定义构成了命题演算（PC）中逻辑推导的基础，区分了从公理出发和从假设出发的不同推导模式。推理示例：证明A→A是定理💡证明思路这是命题演算形式系统PC中最基础的定理之一，虽然直觉上显而易见，但在形式系统中必须严格遵循公理和推理规则。我们的目标是构造一个有限的公式序列，使得序列的最后一项恰好是公式A→A。为此，我们巧妙地组合使用公理A1和公理A2，并两次应用分离规则(ModusPonens,rₘₚ)来完成推导。🎯待证目标：⊢ₚcA→A证明工具：公理A1、公理A2、分离规则(rₘₚ)📝证明序列(ProofSequence)1.(A→((A→A)→A))→((A→(A→A))→(A→A))(公理A2)2.A→((A→A)→A)(公理A1)3.(A→(A→A))→(A→A)(对1,2应用分离规则rₘₚ)4.A→(A→A)(公理A1)5.A→A(对3,4应用分离规则rₘₚ)✅结论：公式序列最后一项即为目标公式，因此定理A→A在PC中得证。推理示例：证明⊢ₚc¬B→(B→A)证明：证明公式¬B→(B→A)是命题演算形式系统PC的定理。其逻辑含义为：从一个假的前提（矛盾）可以推导出任何结论。证明思路：该证明严格遵循PC的推理规则，巧妙结合公理A1、A2、A3，并多次应用分离规则推导出最终结论，完整展示了PC处理逻辑否定与蕴含关系的能力。证明序列(Step1-4)：1.¬B→(¬A→¬B)——公理A12.(¬A→¬B)→(B→A)——公理A33.((¬A→¬B)→(B→A))→(¬B→((¬A→¬B)→(B→A)))——公理A14.¬B→((¬A→¬B)→(B→A))——分离规则rₘₚ(2,3)证明序列(Step5-7)：5.(¬B→(¬A→¬B)→(B→A))→((¬B→(¬A→¬B))→(¬B→(B→A)))——公理A26.(¬B→(¬A→¬B))→(¬B→(B→A))——分离规则rₘₚ(4,5)7.¬B→(B→A)——分离规则rₘₚ(1,6)（得证）03PC的语义SEMANTICSOFPC语法与语义的初步联系01/公理的永真性PC的语义：联结词意义的规定、真值指派、命题真值意义的规定、永真式、逻辑等价、逻辑蕴涵的概念PC的三条公理A1,A2,A3都是永真式(tautology)。无论其中的命题变元被赋予什么真值，整个公式的真值永远为真。这一性质至关重要，它保证了我们推理的出发点是绝对可靠的，为整个演绎系统奠定了坚实的逻辑基础。02/分离规则的保真性分离规则(Modus