离散数学 课件 第1章 命题逻辑

CHAPTER01命题逻辑1.1命题及其表示课程大纲CONTENTS01引言为何需要数理逻辑？02命题的定义什么是命题？03命题的核心特征如何判断一个句子是否为命题？04命题的分类原子命题与复合命题05例题分析判断句子是否为命题06命题的表示命题标识符、常元与变元07小结|核心概念回顾与总结引言：为何需要数理逻辑？01/核心挑战日常使用的自然语言（如中文、英文）往往存在歧义性和不精确性。这类语言缺陷会导致逻辑表达的模糊，在需要绝对严谨的数学证明与逻辑推理中是致命的障碍。02/解决方案引入一种人工定义的“目标语言”(ObjectLanguage)。它由一系列能够精确表达判断的语句，以及一套严格定义的公式符号系统构成，以消除自然语言的模糊性。03/本节目标掌握数理逻辑大厦最底层的两块基石：•命题的定义与判定规则

•命题的符号化表示方法这是后续学习逻辑运算与推理的基础。定义1.1：命题的定义能够判断真假的陈述句称为命题(Proposition)。注意：祈使句、疑问句、感叹句和悖论通常都不是命题。核心要素：真值(TruthValue)•真(True)：逻辑判断为正确，记为T(或1)•假(False)：逻辑判断为错误，记为F(或0)•一个命题的真值是唯一的，非真即假。命题分类•真命题：判断结果为真的命题。

例：“2是有理数”。•假命题：判断结果为假的命题。

例：“太阳从西边升起”。“Apropositionisadeclarativesentencethatiseithertrueorfalse,butnotboth.”命题的核心特征：如何判断？01/两步检验法1.是否为陈述句？排除：疑问句、祈使句、感叹句。这类句子无法陈述事实，故不是命题。2.能否判断其真假？排除：悖论、没有确定真值的句子。无客观判断标准的句子不是命题。02/核心特征详解陈述性(Declarative)必须是陈述句，用于客观地陈述事实或表达观点。可判定性(Determinable)在原则上必须具有确定的真值（要么为真，要么为假）。非自毁性(Non-paradoxical)不能是逻辑悖论，也不能产生自相矛盾的结论。核心特征详解：非自毁性（悖论）什么是悖论？悖论是一种特殊的陈述或逻辑命题，它在逻辑上可以推导出互相矛盾的结论。简单来说，其“真”与“假”两种判断都会导致自相矛盾的逻辑死结。经典案例解析“这句话是假的。”•如果这句话是真的，那么它陈述的“这句话是假的”即为真，导致它本身是假的。•如果这句话是假的，那么它陈述的“这句话是假的”即为假，导致它本身是真的。关键结论这种自指性的矛盾，使得悖论在逻辑系统中无法被赋予一个确定的、唯一的真值（True或False）。因此，悖论≠命题定义1.2：命题的分类根据命题的结构形式，可以将命题分为两大类：原子命题(SimpleProposition)不能被分解为更简单的陈述语句的命题。它是命题逻辑中最基本的单位，不包含任何联结词。复合命题(CompoundProposition)由联结词(Connectives)、标点符号和原子命题组合而成的命题。其真值取决于其组成部分的真值。图1.2.1简单命题与复合命题逻辑关系示例复合命题与原子命题辨析核心判别标准：“语义完整性”的分解测试判断一个命题是“原子”还是“复合”，唯一的关键在于：分解后的更小语句是否还能保持原有的语义完整性，且能独立表达判断。例1：复合命题(CompoundProposition)🔹原句：“小王和小李都去公园。”🔹分解尝试：“小王去公园。”+“小李去公园。”✅结论：两个分解后的句子均逻辑通顺，且合并后语义与原句完全一致。因此，这是一个可拆解的复合命题。例2：原子命题(AtomicProposition)🔹原句：“北京和天津的距离很近。”🔹分解尝试：“北京的距离很近”+“天津的距离很近”(语义不通)❎结论：拆分后的语句丧失了原有的判断意义，无法独立成立。因此，这是一个不可拆解的最小单位，即原子命题。例题1.1：判断句子是否为命题请逐一判断下列句子是否为命题，若是命题，请进一步指出其真值（真/假）。01.北京是中国的首都。02.请勿吸烟!03.雪是黑的。04.明天开会吗?05.x+y>0。06.我正在说谎。07.9+5≤12。08.1+101=110。09.今天天气多好啊!10.别的星球上有生物。11.我们正在上课。12.我学英语，或者我学法语。13.如果天气晴朗，那么我就去郊外旅行。14.这句话是错的。15.3既是素数又是奇数。16.我们要努力学习。17.认真看这本书。例题1.1解答：是命题的句子(1)北京是中国的首都。是命题，客观事实确定，真值为真(T)。(3)雪是黑的。是命题，客观事实确定，真值为假(F)。(7)9+5≤12。是命题，数学运算结果确定，真值为假(F)。(8)1+101=110。是命题，真值取决于上下文（二进制为真，十进制为假）。(10)别的星球上有生物。是命题，客观存在唯一真假，目前未知但存在。(11)我们正在上课。是命题，真假判断依赖具体的时间和场景。(12)我学英语，或者我学法语。是复合命题，由“或”连接两个原子命题构成。(13)如果天气晴朗，那么我就去郊外旅行。是复合命题，由“如果...那么...”连接两个原子命题。(15)3既是素数又是奇数。是复合命题，且真值为真(T)。例题1.1解答：不是命题的句子祈使句(2),(16),(17)用于表达请求、命令或建议，不表达对事物的判断，因此不属于命题。疑问句(4)用于提出问题、询问情况，没有做出任何肯定或否定的判断，因此不是命题。感叹句(9)用于抒发强烈的感情或情绪，并未对事物的真假进行判断，所以不是命题。无确定真值的陈述句(5)x+y>0虽然是陈述语气，但由于变量x,y的值未被指定，其真假性无法确定，随取值变化而变化，因此不构成命题。逻辑悖论(6),(14)这类陈述会导致逻辑上的自相矛盾，无法确定其真值（既不能为真，也不能为假），因此不是命题。定义1.3：命题的表示定义原文表示原子命题的符号称为命题标识符(Identifier)。作用：将自然语言中的具体命题抽象为符号，以便进行形式化的逻辑演算与推理。常用符号•大写字母：A,B,C,...,P,Q,R...•小写字母：p,q,r,s,...•带下标大写：A₁,A₂,B₃...•方括号数字：[12],[5],...应用示例P：今天下雨。q：张红很聪明。注：命题标识符本身没有真假值，只有赋予它具体的命题内容后才有真假之分。命题标识符的分类01.命题常元PropositionalConstant一个表示确定命题的标识符，它具有确定的真值（真或假）。💡示例：当我们定义P：北京是中国的首都。此时P就代表一个“真”的命题，因此P是一个命题常元。02.命题变元PropositionalVariable•仅作为任意命题的位置标志，本身未被指定具体内容。•可以代表任何命题，但自身没有确定的真值。⚠️重要结论：命题变元不是命题。只有当用一个具体的确定命题去“指派”它时，才能成为一个具有确定真值的命题。本节小结：核心概念回顾01/命题(Proposition)具有明确判断结果的陈述句，是数理逻辑中最基本的研究单位。02/真值(TruthValue)命题的判断结果。只有两种取值：“真”（T/1）和“假”（F/0）。03/原子命题(Atomic)不能再分解为更简单陈述句的基本命题，又称“简单命题”。04/复合命题由两个或多个原子命题，通过逻辑联结词组合而成的新命题。05/命题标识符用符号（通常是大写英文字母如P,Q）来代替具体的命题，方便逻辑推演。06/命题常元代表特定、具体命题的标识符，其真值是确定不变的。07/命题变元代表任意命题的符号占位符，其本身不是命题，只有被赋予确定内容时才有真值。思考与讨论01“这句话是真的。”

是命题吗？为什么？提示：请从命题的“判断性”与“真值唯一性”两个基本特征出发进行分析。这句话能否确定地判断真假？02“我所说的都是假话。”

是悖论吗？请分析。提示：假设这句话为真，会推导出什么矛盾？假设这句话为假，又会推导出什么矛盾？这体现了逻辑悖论怎样的特征？03尝试分解复合命题“如果明天下雨，我就待在家里看书或者看电影。”请识别出其中的原子命题、逻辑连接词，并指出命题的逻辑结构形式。感谢观看THANKSFORWATCHINGCHAPTER01命题逻辑1.2联结词PROPOSITIONALLOGIC·LOGICALCONNECTIVES课程大纲CONTENTS01引言什么是逻辑联结词？

引入与基本定义02常用联结词详解否定、合取、析取

条件、双条件03其他联结词介绍不可兼析取

与非、或非04联结词的实际应用开关电路、逻辑电路

网页检索、位运算05总结与回顾核心要点总结

重点难点回顾引言：什么是逻辑联结词？核心概念(CoreConcept)逻辑联结词（LogicalConnectives）是用于将一个或多个原子命题连接起来，构成更复杂的复合命题的符号。它是逻辑语言的“粘合剂”，让简单的陈述转化为有深度的逻辑表达。构建复杂命题通过联结词，可将简单的原子命题组合成能够表达更复杂逻辑关系的复合命题，拓展语言的表达边界。精确表达逻辑关系有效消除自然语言中常有的歧义，用形式化的符号系统精确表达“非”、“且”、“或”、“如果...那么...”等逻辑关系。进行逻辑推理它是进行命题演算、逻辑证明和推理的基础工具，是数理逻辑大厦的基石之一。五种常用联结词概览¬否定(Negation)读作：“非”用于对一个命题的真值进行取反，改变原命题的真假性。∧合取(Conjunction)读作：“与”/“且”用于表示两个命题同时为真，只有当两个支命题都为真时，整体才为真。∨析取(Disjunction)读作：“或”用于表示两个命题中至少有一个为真，即逻辑“或”关系。→条件(Conditional)读作：“若...则...”/“蕴含”用于表示一种因果或推导关系，只有当前件为真且后件为假时，整个命题才为假。↔双条件(Biconditional)读作：“当且仅当”/“等价于”用于表示两个命题的真值完全相同，即互为充要条件，逻辑上完全等价。1.否定(¬)定义1.4设P为一个命题，P的否定(Negation)是一个新的命题，记作¬P，读作“非P”。逻辑关系：

若P为T，则¬P为F；

若P为F，则¬P为T。真值表(表1.1)P¬PTFFT核心性质否定是一个一元运算。它仅需一个命题作为操作数，

就能生成一个新命题。否定(¬)的例题解析例题1.2：否定的多种自然语言表达P：伦敦是个多雾的城市。¬P：伦敦并非是个多雾的城市。¬P：伦敦不是个多雾的城市。💡逻辑分析：这两个中文表述虽然用词不同，但它们表达的逻辑意义完全相同。这说明在自然语言中，同一个逻辑否定关系可以有多种等价的表达方式。例题1.3：全称判断的否定陷阱命题R：所有的天鹅都是白色的。❓请问以下哪项是¬R的错误表述？❌A.所有天鹅都不是白色的。（错误）✅B.并非所有天鹅都是白色的。（正确）✅C.天鹅不都是白色的。（正确）💡逻辑分析：否定全称判断“所有A都是B”时，不要错误地理解为“所有A都不是B”。正确的逻辑否定应该是“存在至少一个A不是B”，即日常语言中的“不都”或“并非所有”。2.合取(∧)定义1.5设P和Q是两个命题，P与Q的合取(Conjunction)是一个复合命题，记作P∧Q，读作“P合取Q”，含义为“P并且Q”。逻辑规则：当且仅当P、Q同时为真(T)时，P∧Q为真(T)；否则为假(F)。真值表(表1.2)PQP∧QTTTTFFFTFFFF核心性质1.二元运算合取联结词必须作用于两个命题之上，是一种二元逻辑运算。2.交换律(对称性)合取的结果与命题顺序无关，即满足：

P∧Q≡Q∧P合取(∧)的例题解析例题1.5设定：P：3是素数。

Q：3是奇数。命题符号化：P∧Q解释：3既是素数又是奇数。两个简单事实同时成立。例题1.7自然语言：“今天天气很冷，但室内暖和。”符号化：P∧Q💡关键分析：自然语言中的转折词“但”，在逻辑上与“和”含义相同，均表示前后两个命题同时成立。例题1.8设定：P：2+2=4(数学真理)

Q：我去看电影(生活琐事)符号化：P∧Q💡关键分析：数理逻辑中，合取不要求两个命题在语义上有任何内在联系，它只关注两个命题的“真值”是否同时为真。3.析取(∨)定义1.6两个命题P和Q的析取(Disjunction)是一个复合命题，记作P∨Q，读作“P析取Q”，在日常语言中含义为“P或Q”。其逻辑规则是：当且仅当P、Q同时为假(F)时，P∨Q的真值为假(F)；其余任何情况下，P∨Q的真值均为真(T)。真值表(表1.3)PQP∨QTTTTFTFTTFFF核心性质•二元运算：析取联结词连接且仅连接两个命题变元。•对称性：命题变元的先后顺序不影响最终结果，满足交换律。P∨Q≡Q∨P析取(∨)的两种含义：兼或vs.异或相容“或”(Inclusiveor/可兼或)允许两个命题同时为真，这是逻辑联结词∨的标准定义。只要两个命题中有一个为真，整个“或”命题即为真。💡示例：

“选修过微积分或计算机科学的学生可以选修本课程。”

(学生如果两门课都修过，依然符合条件。)不相容“或”(Exclusiveor/异或)不允许两个命题同时为真，二者只能择其一。这在自然语言中也很常见，但不能直接等同于逻辑析取∨。🍽️示例：“餐馆的开胃菜：汤或沙拉。”

(通常不允许同时选汤和沙拉。)🔢符号化：(P∧¬Q)∨(¬P∧Q)4.条件(→)定义1.7给定两个原子命题P和Q，其条件(Conditional)命题是一个复合命题，记作P→Q，读作“P条件Q”，含义为“如果P，那么Q”。当且仅当P的真值为T，且Q的真值为F时，P→Q的真值为F；其余所有情况下，P→Q的真值均为T。真值表(表1.4)PQP→QTTTTFFFTTFFT核心性质•二元运算条件联结词将两个原子命题组合成一个新的复合命题，属于二元逻辑运算。•不具有对称性一般情况下，“P条件Q”并不等价于“Q条件P”，即：

P→Q≢Q→P条件(→)的深入理解：善意的推定01/关键观察从逻辑命题的真值表中，我们能发现一个有趣且反直觉的现象：当条件命题的前件P为假时，无论其后件Q是真是假，整个复合命题P→Q的逻辑真值都为真(True)。02/善意的推定这一现象背后的逻辑基石被称为“善意的推定”(PrincipleofCharity)。它的核心在于：如果一个论证的前提本身是虚假的，那么我们无法通过逻辑来证伪其结论，因此在逻辑上认为该命题是“空洞地”成立的。03/生活实例：法律类比这与现代法律体系中的无罪推定原则非常相似：判定嫌疑人有罪(P为真)，必须要有充分的证据。若检方无法提供有效证据证明其有罪(即P为假)，无论我们有多大的怀疑，在法律逻辑上都必须推定其无罪(P→Q为真)。条件(→)的多种自然语言表达例题1.16：设P：张红学习离散数学，Q：张红是大学一年级学生。以下所有自然语言句子都可以形式化表示为逻辑表达式P→Q1.如果P，那么Q。(最直接的表达方式)2.因为P，所以Q。/只要P，就Q。(强调P是Q的充分条件)3.P仅当Q。(PonlyifQ:即P为真时Q必须为真)4.只有Q，才P。(QisnecessaryforP:强调Q是P的必要条件)5.除非Q，才P。(除非满足Q，否则P不能成立)6.除非Q，否则¬P。(UnlessQ,notP:逻辑上等价于P→Q)5.双条件(↔)定义1.8给定两个命题P和Q，其复合命题P↔Q称作双条件(Biconditional)命题。它读作：“P双条件Q”或“P等价于Q”。在逻辑语境下，其含义等同于：“P当且仅当Q”(PifandonlyifQ)。逻辑判定规则：当且仅当P和Q的真值完全相同时，P↔Q的真值为T(真)，否则为F(假)。真值表(表1.5)PQP↔QTTTTFFFTFFFT核心性质1.二元运算

双条件联结词必须作用于两个命题之上，不能单独使用。2.对称性(交换律)

P与Q的位置可以互换，逻辑意义保持不变。即：

P↔Q≡Q↔P双条件(↔)的例题解析例题1.18：自然语言的双条件命题①两个三角形全等，当且仅当它们的三组对应边相等。②函数y=f(x)在x=a处连续，充分必要条件是：当x→a时，f(x)→f(a)。💡逻辑分析：上述两例均为典型的双条件命题。若设条件为P，结论为Q，则此类命题均可统一符号化为逻辑表达式：P↔Q例题1.19：复合命题的真值判定📋已知前提：逻辑变量p=假(F)，逻辑变量q=真(T)1.合取否定式：p∧¬q

➔F∧¬T➔F∧F➔False(假)2.蕴含式：p→q

➔F→T➔True(真)（注：前件为假时，蕴含式恒真，即“善意推定”）3.双条件式：¬p↔q

➔¬F↔T➔T↔T➔True(真)其他联结词介绍不可兼析取(⊽)-异或定义：P⊽Q的真值为T，当且仅当P和Q的真值不相同。即两个命题的真假性相反时，结果才为真。等价表达式P⊽Q≡¬(P↔Q)与非(↑)定义：P↑Q的真值为F，当且仅当P和Q都为T。即只有当两个命题同时为真时，结果才为假，其余情况均为真。等价表达式P↑Q≡¬(P∧Q)或非(↓)定义：P↓Q的真值为T，当且仅当P和Q都为F。即只有当两个命题同时为假时，结果才为真，其余情况均为假。等价表达式P↓Q≡¬(P∨Q)应用一：开关电路串联电路(图1.2(a))两个开关S1和S2必须同时闭合，灯才会亮。逻辑关系对应：合取(P∧Q)并联电路(图1.2(b))只要有一个开关S1或S2闭合，灯就会亮。逻辑关系对应：析取(P∨Q)单开关电路(图1.2(c))开关S1断开时，灯不亮；闭合时，灯亮。逻辑关系对应：否定(¬P)应用二：逻辑电路计算机硬件的核心基石是逻辑门电路，而逻辑门的工作原理与我们在逻辑学中学习的逻辑联结词存在完美的一一对应关系。基本逻辑门•与门(ANDGate)：对应合取关系`∧`，仅当所有输入为真时输出为真。•或门(ORGate)：对应析取关系`∨`，只要任一输入为真则输出为真。•非门(NOTGate)：对应否定关系`¬`，将输入信号的逻辑值取反。复杂电路构建逻辑门虽然简单，但通过灵活组合与门、或门和非门，理论上可以构建出能实现任何复杂逻辑功能的数字电路，从简单的加法器到复杂的CPU，本质上都是这些基本逻辑门的排列组合。结论：逻辑联结词是计算机硬件设计的数学基础。应用三：网页检索现代搜索引擎广泛使用布尔检索来提高搜索精度，通过逻辑运算符组合关键词，实现高效精准的信息筛选，让海量互联网信息检索变得可控。AND操作·合取(∧)使用AND(或+)连接两个关键词，表示检索结果中必须同时包含这两个词，用于缩小检索范围。检索示例："NewMexico"ANDuniversitiesOR操作·析取(∨)使用OR(或|)连接两个关键词，表示检索结果中至少包含其中一个词，用于扩大检索范围。检索示例：("NewMexico"OR"Arizona")ANDuniversitiesNOT操作·否定(¬)使用NOT(或-)排除特定关键词，表示检索结果中一定不包含该词，用于排除无关信息。检索示例："apple"NOT"fruit"应用四：位运算背景原理：计算机底层所有信息均以二进制位（0和1）的形式存储和处理。在逻辑视角下，位可直接看作逻辑变量的真值：0代表False，1代表True。位运算本质上就是对二进制位直接进行逻辑操作。按位与(AND)逻辑上对应“合取”∧。规则：两个对应位都为1时，结果才为1，否则为0。常用于掩码操作。按位或(OR)逻辑上对应“析取”∨。规则：只要有一个对应位为1，结果即为1。常用于设置标志位。按位取反(NOT)逻辑上对应“否定”¬。规则：将每一位取反（0变1，1变0）。注意符号位的影响。核心应用场景位运算极其高效且占用资源少，广泛应用于底层系统编程、网络通信协议解析、游戏开发中的碰撞检测、以及图像处理与数据压缩等领域。核心联结词总结对比表否定¬读法：非何时为真：当命题为假时对称性：一元运算合取∧读法：与/且何时为真：两个命题都为真对称性：是析取∨读法：或(包含性)何时为真：至少一个命题为真对称性：是条件→读法：若...则...何时为真：前件假，或后件真对称性：否双条件↔读法：当且仅当(IFF)何时为真：两个命题真值相同对称性：是异或⊽读法：异或(XOR)何时为真：两个命题真值不同对称性：是关键要点回顾构建复合命题逻辑联结词是连接简单命题、构建复杂逻辑关系的基石，是逻辑语言的核心组成部分。掌握真值表理解并熟记每个逻辑联结词对应的真值表，是判断复合命题真假、掌握命题逻辑的关键钥匙。区分“或”的含义自然语言中的“或”需注意语境差异，严格区分为兼或（包含或）与异或（排斥或）两种情况。“善意的推定”原则在条件命题P→Q中，若前件P为假，无论后件Q真假，整个命题恒为真，这是逻辑上的“善意推定”。广泛的应用场景逻辑联结词不仅是数学工具，更在数字电路设计、数据库信息检索、计算机编程等领域有重要的实用价值。感谢观看THANKYOUFORWATCHINGCHAPTER01命题逻辑1.3命题公式与翻译PROPOSITIONALFORMULASANDTRANSLATION1.3命题公式与符号化1.3.1命题公式▌合式公式的定义

由命题变元、联结词和圆括号，按照一定规则组成的字符串，是命题逻辑中合法的表达式。▌联结词的优先级

规定运算的先后顺序：否定(¬)>合取(∧)>析取(∨)>蕴含(→)>等价(↔)。1.3.2命题符号化▌符号化步骤

1.分析自然语言中的原子命题与联结词；

2.用命题变元表示原子命题；

3.依据语义，用联结词连接变元构成公式。▌实例讲解

将复杂的自然语言陈述句（如“如果明天下雨，那么我就待在家里看书”）转化为严谨的逻辑公式。1.3.3公式的赋值▌赋值的定义

给公式中的每一个命题变元指定一个确定的真值（真T或假F），构成该公式的一个“解释”。▌两类特殊赋值

•成真赋值：使公式真值为真的赋值

•成假赋值：使公式真值为假的赋值定义1.13：命题演算的合式公式(wff)01基础(Basis)单个命题变元本身是一个合式公式。例如：P,Q,R均为最简单的合式公式。02归纳1(InductionI)如果A是合式公式，那么¬A(A的否定)也是合式公式。例如：若P是合式公式，则¬P也是合式公式。03归纳2(InductionII)如果A和B是合式公式，那么(A∧B),(A∨B),(A→B),(A↔B)都是合式公式。例如：若P、Q是合式公式，则(P∧Q)、(P→Q)等也是。04界限(Boundary)当且仅当能够有限次地应用(1)、(2)、(3)所得到的，包含命题变元、联结词和括号的符号串，才是合式公式。辨别合法的命题公式合法的命题公式(Well-Formed)•(P∧Q)→(P∨Q)•¬(P↔Q)•P→(Q∨R)•P∧¬Q→R(根据运算优先级，括号可省略)•P∨Q→R(根据运算优先级，括号可省略)非法的“公式”(Ill-Formed)•P∧→Q(错误：缺少命题变元，联结词使用不当)•(P∧¬Q)∨¬P)↔R(错误：左右括号数量不匹配)•¬P∨(Q,R)(错误：包含不合法的符号“,”)•PQ→T(错误：缺少必要的二元联结词)核心思想：必须严格遵守合式公式(WFF)的递归定义规则，避免语法错误。联结词的运算优先级优先级顺序1.¬(否定)-最高优先级2.∧(合取)-"且"运算3.∨(析取)-"或"运算4.→(条件)-"如果...则..."5.↔(双条件)-"当且仅当"同级处理规则当公式中出现同一优先级的联结词时，遵循“从左到右”的运算顺序进行计算。例如：p∧q∧r等价于(p∧q)∧r括号的作用1.强制优先：括号内的子公式，无论联结词优先级如何，总是最先进行运算。2.改变顺序：利用括号可以打破默认的优先级规则，明确指定运算逻辑。3.书写简化：公式最外层的括号，通常在书写时可以省略。例题1.21：运算顺序解析题目描述：请结合逻辑运算符的优先级规则，分步解析公式¬P∨¬Q→R∧S↔T的运算步骤。01最高优先级：否定¬P和¬Q

(先处理所有单目否定运算)02次高：析取(¬P)∨(¬Q)

(左结合律，处理析取运算)03次高：合取R∧S

(处理右侧的合取运算)04再次：条件((¬P)∨(¬Q))→(R∧S)

(处理蕴含关系)05最低：双条件[上一步结果]↔T

(最后处理等价关系)最终加括号形式：(((¬P)∨(¬Q))→(R∧S))↔T例题1.22：运算顺序解析题目：分析复合命题公式T↔¬P∨(¬Q→R)∧S的运算优先级与加括号步骤。01¬P、¬Q第一步：处理最高优先级的否定(¬)02(¬Q→R)第二步：优先计算括号内的条件运算(→)03((¬Q→R)∧S)第三步：处理合取运算(∧)，高于析取04(¬P)∨((¬Q→R)∧S)第四步：处理低优先级的析取运算(∨)05T↔((¬P)∨((¬Q→R)∧S))第五步：最后处理最低优先级的双条件(↔)最终加括号形式：T↔((¬P)∨((¬Q→R)∧S))如何将自然语言翻译成命题公式？定义：命题的符号化把一个文字描述的命题，写成由命题标识符、逻辑联结词和圆括号表示的标准命题形式，这一转换过程就称为“命题的符号化”。核心原则符号化后的表达式⇌原句语义必须保证二者在逻辑上完全一致，无歧义一般化符号化步骤01明确语义准确理解自然语言

所表达的逻辑关系02拆分原子命题提取基本陈述句

用P,Q,R等符号表示03选择联结词根据逻辑关系连接

原子命题公式例题1.23：命题符号化(1)如果我有智能手机，那么2+3=8。设P：我有智能手机。Q：2+3=8。形式化表示为：P→Q(2)A集合中没有元素，A是空集。设P：A集合中没有元素。Q：A是空集。形式化表示为：P↔Q(3)如果3是合数，则4是素数，并且如果4是素数，则它不能被2整除。设P：3是合数。Q：4是素数。R：4能被2整除。形式化表示为：(P→Q)∧(Q→¬R)(4)如果2+3>5当且仅当5是合数，则2和3都是有理数。设P：2+3>5。Q：5是合数。R：2是有理数。S：3是有理数。形式化表示为：(P↔Q)→(R∧S)例题1.24：复杂句式的符号化背景设定：P：你陪伴我|Q：你代我叫车子|R：我将出去命题01如果你陪伴我并且代我叫辆车子，则我将出去。符号化表达(P∧Q)→R命题02如果你不陪伴我或不代我叫辆车子，我将不出去。符号化表达(¬P∨¬Q)→¬R命题03除非你陪伴我或代我叫车子，否则我将不出去。语义等同：非(P∨Q)→¬R方法一(¬P∧¬Q)

→¬R方法二

(逆否命题)R→(P∨Q)定义1.14：命题公式的赋值设A是一个命题公式，P₁,P₂,...,Pₙ是出现在A中的所有命题变元，给P₁,P₂,...,Pₙ指定一组真值，称为对公式A的一个赋值(也称翻译、解释、指派)。成真赋值(SatisfiedAssignment)若指定的一组值使公式A的值为T(真)，则称这组值为A的成真赋值。成假赋值(FalsifiedAssignment)若指定的一组值使公式A的值为F(假)，则称这组值为A的成假赋值。思考：一个含有n个命题变元的公式，共有多少组不同的赋值？答案：2ⁿ组。(每个变元有真/假2种可能，n个变元总组合数为2×2×...×2(n次))例题1.25：赋值实例设逻辑公式：G=P→(¬Q∧R)赋值1：P=0，Q=1，R=0G=0→(¬1∧0)=0→(0∧0)=0→0=1(真/True)结论：该组赋值为公式G的成真赋值赋值2：P=1，Q=0，R=0G=1→(¬0∧0)=1→(1∧0)=1→0=0(假/False)结论：该组赋值为公式G的成假赋值例题1.26：赋值实例题目：设有命题公式A=¬(P∨Q)→R赋值1：{P=T,Q=T,R=F}A=¬(T∨T)→F=¬T→F=F→F=T(真)结论：{T,T,F}是该公式的成真赋值赋值2：{P=F,Q=F,R=F}A=¬(F∨F)→F=¬F→F=T→F=F(假)结论：{F,F,F}是该公式的成假赋值本节核心要点回顾01.命题公式(wff)由命题变元、联结词和括号按递归规则构成的合法表达式。它是进行逻辑推理的基础语言单位。02.联结词优先级从高到低依次为：¬(否定)>∧(合取)>∨(析取)>→(蕴含)>↔(等价)。

括号可以改变运算的优先级顺序，在复杂公式中起到关键作用。03.命题符号化将自然语言描述的命题转换为形式化的命题公式的过程。

关键在于：准确理解自然语言的逻辑语义，并正确选择与语义匹配的逻辑联结词。04.公式赋值对公式中的所有命题变元指派确定的真值。

•分类：成真赋值(结果为真)与成假赋值(结果为假)。

•数量：含有n个变元的公式，共有2^n种不同的赋值组合。感谢观看THANKSFORWATCHING第一章·命题逻辑1.4真值表及其意义1.4真值表：定义、构造与意义1.4.1真值表的定义与构造▌定义：表征逻辑事件输入和输出之间全部可能状态的表格。它以表格形式直观展示了命题公式在其变元的所有真值组合下的取值情况。▌构造步骤：1.列出所有命题变元的真值组合；2.由简至繁列出公式的子公式；3.计算各子公式的真值，最终得到主公式的真值。▌应用：通过经典例题，掌握复杂公式的构造技巧。1.4.2真值表的核心意义▌命题公式的分类判定根据公式在所有赋值下的真值情况，可将其划分为三类：•重言式（永真式）|矛盾式（永假式）|可满足式▌证明公式的逻辑等价若两个公式在任何赋值下真值均相同，则二者逻辑等价。真值表法是验证逻辑等价最直观的判定依据。定义1.15：真值表定义原文在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表(TruthTable)。逻辑分析通过穷举所有可能的命题赋值组合，系统地验证命题的真假规律，是逻辑学中分析命题公式等价性、永真性的基础手段。工程应用是数字电路设计、程序条件判断优化、算法逻辑验证等计算机科学与电子工程领域的核心分析与实现工具。真值表构造四步法01列变量在表格第一行列出所有命题变元，明确分析对象与基本要素。02排组合系统排列所有变元的真值组合，确保穷尽所有逻辑可能性（共2ⁿ种，n为变元个数）。03逐层算遵循联结词优先级顺序¬>∧>∨>→>↔，从最内层子公式开始，逐步计算出整个复合命题公式的真值。04验结果仔细核对每一步的计算过程，确保没有遗漏任何一种真值组合或计算错误，保证最终结论的准确性。例题1.27：构造公式¬P∨Q的真值表▍真值表构造PQ¬P¬P∨QTTFTTFFFFTTTFFTT▍逻辑分析成真赋值(TrueAssignments)使公式结果为真的赋值组合：TT,FT,FF成假赋值(FalseAssignments)使公式结果为假的赋值组合：TF例题1.28：永真式与永假式(1)P∧Q→PPQP∧QP∧Q→PTTTTTFFTFTFTFFFT分析：所有赋值均为成真赋值（此命题公式为永真式/重言式）(2)¬(P→Q)∧QPQP→Q¬(P→Q)¬(P→Q)∧QTTTFFTFFTFFTTFFFFTFF分析：所有赋值均为成假赋值（此命题公式为永假式/矛盾式）例题1.29：构造复合命题(P∨¬Q)→(P∧Q)的真值表PQ¬QP∨¬QP∧Q(P∨¬Q)→(P∧Q)TTFTTTTFTTFFFTFFFTFFTTFF成真赋值使命题为真的P,Q组合：TT,FT成假赋值使命题为假的P,Q组合：TF,FF结论：该复合命题既非重言式，也非矛盾式，而是一个可满足式。例题1.30：多公式对比PQG₁=¬(P→Q)→PG₂=(P→Q)∧PG₃=¬(P∧¬Q)↔¬(P→Q)FFTFFFTTFFTFTFFTTTTFG₁：永真式(Tautology)无论命题变元P和Q取何真值，公式G₁的结果始终为真。这种公式也称为“重言式”。G₂：可满足式(Satisfiable)公式G₂并非恒真或恒假。它仅在特定的赋值下为真，即当且仅当P=T且Q=T时，G₂才为真。G₃：永假式(Contradiction)无论命题变元P和Q取何真值，公式G₃的结果始终为假。这种公式也称为“矛盾式”或“不可满足式”。例题1.31：三元公式的真值表G=R→¬(P∨Q)PQRP∨Q¬(P∨Q)R→¬(P∨Q)000011001011010101011100100101101100110101111100成真赋值(0,0,0)、(0,0,1)、(0,1,0)、(1,0,0)、(1,1,0)成假赋值(0,1,1)、(1,0,1)、(1,1,1)真值表的意义：命题公式分类定义1.16：重言式Tautology/永真公式若无论对命题分量作怎样的真值指派，其对应的命题公式真值永为T，则称该公式为重言式或永真公式。注：重言式在逻辑推理中具有基础地位，它的真不依赖于任何前提。定义1.17：矛盾式Contradiction/永假公式若无论对命题分量作怎样的真值指派，其对应的命题公式真值永为F，则称该公式为矛盾式或永假公式。注：矛盾式的否定即为重言式，反之亦然。它是逻辑推理中的归谬依据。定义1.18：可满足公式SatisfiableFormula如果一个命题公式不是永假的（即至少存在一组分量的真值指派使其结果为真），则称该命题公式为可满足公式。注：重言式一定是可满足的，但可满足公式不一定是重言式。三种特殊公式之间的关系包含关系•所有的永真式都是可满足式，反之不一定成立。

•矛盾式都不是可满足式。否定关系•公式A是永真的，当且仅当¬A(非A)是永假的。

•反之亦然：若¬A是可满足的，则A不是永真的。通过真值表判断•永真公式：最后一列全为T；永假公式：最后一列全为F。

•可满足公式：最后一列至少有一个T。真值表的意义：公式的等价什么是“公式等价”？两个不同的命题公式，可能在所有相同的变元赋值情况下，计算结果都相等。这时，我们在逻辑上称这两个公式是等价(Equivalent)的。核心判断方法列出两个公式的完整真值表进行对比。若对于所有可能的变元赋值，两个公式的最终真值始终保持一致，则二者逻辑等价。图示：真值表与逻辑判断通过穷举所有变元组合来验证逻辑一致性例题1.32：证明两公式等价P↔Q⇔(¬P∨Q)∧(¬Q∨P)PQP↔Q¬P¬Q¬P∨Q¬Q∨P(¬P∨Q)∧(¬Q∨P)TTTFFTTTTFFFTFTFFTFTFTFFFFTTTTTT结论：比较真值表中P↔Q列与(¬P∨Q)∧(¬Q∨P)列的结果，可以观察到：在所有可能的指派（共4种）下，两个公式对应的逻辑真值完全相同。根据逻辑等价的定义，可以确定这两个公式是逻辑等价的。∴证毕(Q.E.D.)例题1.33：判断命题公式是否等价：¬(P∨Q)与¬P∨¬QPQP∨Q¬(P∨Q)¬P¬Q¬P∨¬QTTTFFFFTFTFFTTFTTFTFTFFFTTTT结论：比较表格中第4列¬(P∨Q)和第7列¬P∨¬Q的真值，我们可以清晰地看到：在赋值组合为“TF”和“FT”时，两个公式的计算结果并不一致。因此，命题公式¬(P∨Q)与¬P∨¬Q是不等价的。本节核心要点回顾01.真值表的构造掌握“列变量、排组合、逐层算、验结果”四步法，能够逻辑严密、步骤完整地为任意命题公式构造真值表，准确反映公式在不同赋值下的真假情况。02.命题公式的分类•重言式(永真式)：无论命题变元取何值，公式真值恒为真。•矛盾式(永假式)：无论命题变元取何值，公式真值恒为假。•可满足式：至少存在一个赋值，使得公式的真值为真。03.公式的等价判断两个公式是否等价的核心方法是比较它们的真值表。若对于所有可能的命题变元赋值，两个公式的真值始终保持一致，则它们是逻辑等价的。感谢观看THANKYOUFORWATCHING第一章·命题逻辑1.5等价公式逻辑世界的化简魔法本节内容概览01.等价公式的定义与基本性质•等价公式的定义与相关定理

•常用的基本等价关系（命题定律）02.等值演算的核心规则•代入规则：重言式中命题变元的统一替换

•置换规则：公式子公式的等价替换03.等价公式的应用场景•判断公式的类型（重言式/矛盾式/可满足式）

•证明两个公式的等价性与逻辑化简问题04.联结词的全功能集•冗余联结词与独立联结词的概念

•全功能集的定义与极小联结词组定义1.19：等价公式定义内容给定两个命题公式A和B，设P₁，P₂，…，Pₙ是所有出现于A和B中的原子变元，若给P₁，P₂，…，Pₙ任一组真值指派，A和B的真值都对应相同，则称A和B是等价的或逻辑相等(Equivalence)，记作A⇔B。定理1.1：充要条件对于任意两个公式G和H，G⇔H的充分必要条件是公式G↔H是永真公式(Tautology)。💡提示：判断两个公式是否等价，可转化为证明其双条件命题是重言式。关键区分⇔等价符号属于关系符号，用于描述两个公式之间的逻辑等价关系，不能用于构造公式。↔双条件联结词属于逻辑联结词，是一个运算符，用于连接两个原子公式以构造新的复合命题公式。常用基本等价关系（命题定律）E1.¬¬P⇔P——对合律E2.P∨P⇔P——幂等律E3.P∧P⇔P——幂等律E4.(P∨Q)∨R⇔P∨(Q∨R)——结合律E5.(P∧Q)∧R⇔P∧(Q∧R)——结合律E6.P∨Q⇔Q∨P——交换律E7.P∧Q⇔Q∧P——交换律E8.P∨(Q∧R)⇔(P∨Q)∧(P∨R)——分配律E9.P∧(Q∨R)⇔(P∧Q)∨(P∧R)——分配律E10.P∨(P∧Q)⇔P——吸收律E11.P∧(P∨Q)⇔P——吸收律E12.¬(P∨Q)⇔¬P∧¬Q(德摩根律)E13.¬(P∧Q)⇔¬P∨¬Q(德摩根律)常用基本等价关系（续）E14P∨F⇔P同一律E15P∧T⇔P同一律E16P∨T⇔T零律E17P∧F⇔F零律E18P∨¬P⇔T否定律(排中律)E19P∧¬P⇔F否定律(矛盾律)E20P→Q⇔¬P∨Q条件等价式E21P→Q⇔¬Q→¬P假言易位E22P↔Q⇔(P→Q)∧(Q→P)双条件等价式E23P↔Q⇔¬P↔¬Q等价否定式E24(P→Q)∧(P→¬Q)⇔¬P归谬论等值演算的核心规则定理1.2：代入规则(SubstitutionRule)在一个永真式A中，任何一个原子命题变元R出现的每一处用另一个公式代入，所得的公式B仍为永真式。💡示例：`R∨¬R`是经典的永真式。若将变元R全部用公式`P→Q`代入，得到新公式`(P→Q)∨¬(P→Q)`，该公式依然是永真式。定理1.3：置换定理(ReplacementTheorem)设X是命题公式A的一个子公式，且已知X⇔Y。如果将A中X的一处或多处出现替换为Y，所得到的新公式B与原公式A逻辑等价，即A⇔B。🔍示例：已知蕴含等值式`P→Q⇔¬P∨Q`。若将公式中的P置换为合取式`R∧S`，可直接推出：`(R∧S)→Q⇔¬(R∧S)∨Q`。代入规则vs置换规则01.代入规则(Substitution)对象：原子命题变元(AtomicPropositionalVariables)范围：必须处处代入，不可遗漏任何一处相同的变元目的：保持公式的逻辑永真性(Tautology)02.置换规则(Replacement)对象：子公式(Subformulas)，即复合命题中的任何部分范围：具有灵活性，可进行部分或全部替换目的：保持公式间的逻辑等价性(LogicalEquivalence)例题1.36：证明(P∧Q)∨(P∧¬Q)⇔P(P∧Q)∨

(P∧¬Q)逻辑原式P∧(Q∨¬Q)分配律(Dist./E9)P∧T否定律(Neg./E18)P同一律(Id./E15)结论：通过上述三步等值演算，我们成功地将一个包含两个变元和多个连接词的复杂合式公式，化简为了单一的命题变元P，直观且严谨地验证了二者的逻辑等价关系。这展示了逻辑代数在简化逻辑电路与推理中的核心价值。例题1.37：证明P→(Q→R)⇔Q→(P→R)证明过程P→(Q→R)⇔¬P∨(¬Q∨R)(蕴含式等价转换，参考E20)⇔¬Q∨(¬P∨R)(利用逻辑或的结合律E4与交换律E6调整顺序)⇔Q→(P→R)(还原为蕴含式，参考E20)结论通过上述等值演算，我们成功证明了两个逻辑公式是完全等价的。这揭示了一个重要的逻辑性质：在多重蕴含式的逻辑结构中，前提命题的出现顺序是可以交换的，而不会改变整个复合命题的逻辑含义。应用一：判断公式类型方法：等值演算法利用命题逻辑中的一系列等价公式，对目标公式进行逻辑化简，根据最终的最简形式判断其类型。化简结果=T(真)→重言式(永真式)无论命题变元取何值，公式真值恒为真化简结果=F(假)→矛盾式(永假式)无论命题变元取何值，公式真值恒为假例题1.40：证明(P→Q)∧P→Q是重言式(P→Q)∧P→Q⇔(¬P∨Q)∧P→Q(蕴含表达式E₂₀)⇔¬((¬P∨Q)∧P)∨Q(蕴含表达式E₂₀)⇔(¬(¬P∨Q)∨¬P)∨Q(德摩根律E₁₃)⇔((P∧¬Q)∨¬P)∨Q(德摩根律E₁₂)⇔((P∨¬P)∧(¬Q∨¬P))∨Q(分配律E₉)⇔(T∧(¬Q∨¬P))∨Q(排中律E₁₈)⇔(¬Q∨¬P)∨Q(同一律E₁₅)⇔(¬Q∨Q)∨¬P(结合律、交换律)⇔T∨¬P(排中律E₁₈)⇔T(零律E₁₆)，故该式为重言式。应用二：证明公式等价方法：等值演算法利用已知的基本等价公式（如蕴含表达式、结合律、德摩根律等），通过一系列的等值演算步骤，将一个逻辑公式变换为另一个逻辑公式，从而证明二者逻辑等价。该方法比真值表法更高效。例题1.41：证明公式等价——P→(Q→R)⇔(P∧Q)→RP→(Q→R)(原始公式)⇔¬P∨(¬Q∨R)(蕴含式E20，再次应用)⇔¬(P∧Q)∨R(德摩根律E13，反向应用)⇔¬P∨(Q→R)(蕴含式E20：A→B⇔¬A∨B)⇔(¬P∨¬Q)∨R(结合律E4：(A∨B)∨C⇔A∨(B∨C))⇔(P∧Q)→R(蕴含式E20，最终形式)应用三：化简自然语言语句01问题描述请化简如下自然语言语句，使其表达更清晰、简洁：“情况并非如此，如果他不来，那么我也不去。”02逻辑符号化首先定义原子命题：•P：他来。

•Q：我去。将语句转化为命题公式：¬(¬P→¬Q)03等值演算化简¬(¬P→¬Q)

⇔¬(¬¬P∨¬Q)(蕴含式E20)

⇔¬(P∨¬Q)(对合律E1)

⇔¬P∧Q(德摩根律E12)注：利用蕴含式、对合律、德摩根律逐步消去多余连接词与否定词。04最终结论将最终公式转换回自然语言：“我去了，但他没来。”应用四：化简程序逻辑原程序逻辑IfAthen

ifBthenXelseY

else

ifBthenXelseY执行X的条件推导(A∧B)∨(¬A∧B)⇔(A∨¬A)∧B(分配律E9)⇔T∧B(排中律E18)⇔B(同一律E15)结论：执行X仅取决于条件B最终化简结果IfBthenXelseY代码可读性与效率显著提升应用五：化简开关电路01/原电路逻辑表达式((P∧Q∧R)∨(P∧Q∧S))

∧((P∧R)∨(P∧S))02/等值演算化简过程⇔(P∧Q∧(R∨S))∧(P∧(R∨S))

(分配律DistributiveLaw)⇔P∧Q∧(R∨S)∧P∧(R∨S)

(结合律AssociativeLaw)⇔P∧Q∧(R∨S)

(幂等律IdempotentLaw)03/化简后逻辑表达式P∧Q∧(R∨S)核心价值：通过逻辑代数化简，可显著减少电路中逻辑门的数量和连线复杂度，在实现相同逻辑功能的前提下，有效降低硬件成本并提高系统运行的可靠性。应用六：化简逻辑电路🔧电路状态：复杂冗余包含多个逻辑门与分支，信号路径长，存在大量可合并的逻辑单元，增加了电路的物理面积与功耗。✨电路状态：极简高效逻辑结构被压缩，去除了所有冗余逻辑，仅保留实现功能的最小逻辑单元，显著提升运行效率。📝布尔代数化简推演原逻辑表达式：F=((P∧Q∧R)∨(P∨Q∨S))∧(P∧S∧T)①运用吸收律(E11):(P∧Q∧R)∨(P∨Q∨S)⇔(P∨Q∨S)②再次运用吸收律(E11):(P∨Q∨S)∧(P∧S∧T)⇔P∧S∧T结论：电路被极大简化，仅需三个逻辑门(与门)即可实现原有功能。应用七：解决智力问题例题1.47：侦探推理问题四位证人（男管家P,厨师Q,园丁R,杂役S）的证词存在逻辑冲突，侦探需要利用逻辑规则，找出所有可能的真相组合。已知证词逻辑关系：1.若管家(P)诚实，则厨师(Q)也诚实→P→Q2.厨师(Q)与园丁(R)不可能同时诚实→¬(Q∧R)3.园丁(R)与杂役(S)不可能同时说谎→¬(¬R∧¬S)4.若杂役(S)诚实，则厨师(Q)在说谎→S→¬Q求解：构建真值表，筛选有效解PQRSP→Q¬(Q∧R)¬(¬R∧¬S)S→¬QFFFTTTTTFFTFTTTTFFTTTTTT结论：真相只有一个（部分）在所有满足条件的逻辑解中：1.男管家(P)和厨师(Q)必然在说谎。2.园丁(R)与杂役(S)至少一人说真话，但无法确定具体是谁。联结词的全功能集定义1.21冗余联结词与独立联结词在一个联结词集合D中，如果一个联结词可以由集合中的其他联结词定义和表示，则称此联结词为冗余联结词；否则，若无法由其他联结词定义，则称为独立联结词。定义1.22全功能集与极小联结词组•全功能集：任意真值函数都能用该集合中的联结词公式表示。•极小联结词组：在满足“全功能集”的前提下，集合内不含任何冗余联结词。核心逻辑推导若联结词集合S是全功能集，且从中删去任意一个联结词后就不再是全功能集，则S必为极小联结词组。经典极小联结词组举例数理逻辑中最常见的极小联结词组：{¬,∧}与{¬,∨}。所有的逻辑运算都可由“非”与“且”或“非”与“或”实现。常见的全功能集与极小联结词组全功能集(FunctionalCompleteness)S₁={¬,∧,∨,→,↔}——逻辑演算中最常用的集合S₂={¬,∧,∨}——布尔代数的基础集合，足以表达所有命题公式S₇={¬,→}——仅包含否定和蕴含联结词极小联结词组(MinimalSets)•经典组合：S₃={¬,∧}，S₄={¬,∨}•单元素完备集：S₅={↑}(与非/NAND)，S₆={↓}(或非/NOR)注：极小联结词组是指本身是全功能集，但去掉其中任何一个联结词后，就不再是全功能集。逻辑联结词真值表参考通过真值表可以验证不同联结词组的表达能力与等价性。例题1.50：公式转换目标：将公式P∧¬Q转化为只含指定联结词集合的等值公式。(1)联结词集合{¬,∨}P∧¬Q⇔¬(¬P∨Q)(根据德摩根律)(2)联结词集合{¬,→}P∧¬Q⇔¬(¬P∨Q)⇔¬(P→Q)(根据蕴含等值式)(3)联结词集合{↑}(与非联结词)P∧¬Q⇔P∧(Q↑Q)⇔¬(P↑(Q↑Q))⇔(P↑(Q↑Q))↑(P↑(Q↑Q))(4)联结词集合{↓}(或非联结词)P∧¬Q⇔¬(¬P∨Q)⇔(¬P)↓Q⇔(P↓P)↓Q本节核心要点回顾01等价公式定义A⇔B当且仅当

A↔B是永真式。

这是逻辑等价性判断的根本依据。02基本等价关系掌握德摩根律、蕴含式

假言易位、分配律等

逻辑运算的核心定律。03等值演算规则熟练运用“代入规则”

和“置换规则”

对复杂公式进行推演和变形。04等价公式应用判断公式类型、证明等价

以及化简逻辑程序

和数字电路的重要工具。05全功能集理解冗余联结词与独立联结词

掌握全功能集

和极小联结词组的概念。感谢观看THANKSFORWATCHINGCHAPTER01命题逻辑1.6蕴含公式深入理解命题逻辑中的蕴含关系本节内容概览01定义与核心概念•蕴含公式的定义与详细解读

•关键逻辑符号辨析：

区分`⇒`与`→`的含义与用法02证明方法与实例•证明蕴含关系的两种核心思路

•通过经典逻辑题进行实例解析

•掌握推导过程中的常见技巧03常用基本蕴含关系•构建常用蕴含定律速查表

•逻辑推理过程的形式化表达

•学会灵活运用定律进行转换04蕴含的性质与总结•总结蕴含关系的传递性与反身性

•梳理易错点与常见误区

•归纳本章核心知识点，建立知识体系定义1.23：蕴含公式的严格定义定义内容对于任意两个公式G和H，当且仅当G→H是一个重言式的时候，称“G蕴含H”，记作G⇒H。逻辑本质`G⇒H`表示的是一种逻辑推导关系，而非一个命题公式。它断言：“只要前提G为真，那么结论H必然为真”。判定准则`G⇒H`成立的充分必要条件是：在任何解释下，条件命题`G→H`的真值永远为真（T），即`G→H`是一个重言式。辨析：蕴含符号⇒与条件联结词→蕴含符号⇒●名称：蕴含关系符号●性质：表示两个命题公式之间关系的元语言符号。●含义：断言一个逻辑真理：A的真值永远“强于”或“等于”B的真值。条件联结词→●名称：条件联结词(Implication)●性质：用于构造命题公式的标准逻辑联结词。●含义：本身具有真值，其真值完全依赖于P和Q的具体取值。核心区别`P→Q`是一个公式，它本身可以为真或为假；而`P⇒Q`是一个断言，它要么成立，要么不成立。当且仅当公式`P→Q`是逻辑永真式时，断言`P⇒Q`才成立。证明A⇒B的两种核心思路01/正向推导(肯定前件ModusPonens)📝方法描述直接假定前提A的真值为真(True)，严格依据逻辑公理与推理规则进行演绎，最终推导出结论B的真值也必然为真(True)。🔑逻辑原理基于蕴含式A→B的真值表定义：A→B为假，当且仅当A=T且B=F。若能证明在A=T的情况下，B不可能为F，则该蕴含式即为重言式。02/反向推导(否定后件ModusTollens)📝方法描述利用逻辑等价式A→B⇔¬B→¬A（逆否命题等价）。先假设结论B为假(False)，再推导出前提A也必须为假(False)。🔑逻辑原理这是“反证法”的一种应用形式。若“结论不成立”的假设导致“前提不成立”，则说明原蕴含关系在逻辑上必然成立。例题1.51：推证¬Q∧(P→Q)⇒¬P方法一：正向推导法1假设前提为真：假定命题公式¬Q∧(P→Q)的真值为T(True)。2分解合取式：根据合取运算的定义，必须同时满足¬Q为T且(P→Q)为T。3推导Q的值：因为¬Q为T，根据否定运算的定义，Q的真值必为F(False)。4推导P的值：根据蕴含词“→”的真值表，当后件Q为F且(P→Q)为T时，前件P必须为F。5得出结论：P为F，故¬P为T，结论得证。推导结论上述推导严格遵循了逻辑运算的真值表规则。成功证明了：只要前提合取式为真，结论必然为真。¬Q∧(P→Q)⇒¬P例题1.51：推证¬Q∧(P→Q)⇒¬P方法二：反向推导法（反证法）1.假设与推导●假设结论为假：假定结论¬P的真值为F。●推导前提：若¬P为F，则P的真值必为T。接下来分析在此条件下，前提是否成立。2.前提逻辑分析(P=T)✦情况1(Q=F):P=T且Q=F→(P→Q)=F→合取式¬Q∧(P→Q)=F。✦情况2(Q=T):Q=T→¬Q=F→合取式¬Q∧(P→Q)=F。无论Q取何值，前提结果均为假。结论：如果结论¬P为假，那么前提¬Q∧(P→Q)必然为假。∴根据“逆否命题等价”的逻辑原理，原蕴含关系¬Q∧(P→Q)⇒¬P成立。例题1.52：判断推理P→Q,P⇒Q是否有效方法一：真值表技术为了验证推理的有效性，将前提与结论构成蕴含式：((P→Q)∧P)→Q。若该公式对所有真值指派结果均为真，则它是重言式，推理有效。PQP→Q(P→Q)∧P整体结果TTTTTTFFFTFTTFTFFTFT结论与逻辑意义1.逻辑判定：从左侧真值表可见，最后一列的结果在所有四种情况下均为T(真)。这证明了公式((P→Q)∧P)→Q是一个逻辑重言式。2.推理有效性：根据重言式的性质，推理形式(P→Q)∧P⇒Q在逻辑上是绝对有效的。这就是经典逻辑中著名的假言推理(ModusPonens)，

也被称为“分离规则”，是构建逻辑证明的基石。例题1.52：公式转换法证明方法二：公式转换法（等值演算）((P→Q)∧P)→Q⇔((¬P∨Q)∧P)→Q(蕴含表达式E₁₄:A→B⇔¬A∨B)⇔¬((¬P∨Q)∧P)∨Q(蕴含表达式E₁₄)⇔¬(¬P∨Q)∨¬P∨Q(德摩根定律E₁₀:¬(A∧B)⇔¬A∨¬B)⇔¬(¬P∨Q)∨(¬P∨Q)(结合律与交换律整理)⇔T

(互补律E₆:¬A∨A⇔T)💡证明结论通过上述的等值演算，将原命题公式一步步化简，最终推导出逻辑真（T）。结论：该命题公式是一个重言式(Tautology)，故蕴含关系成立。例题1.52：主析取范式法证明方法三：主析取范式法将逻辑公式转换为主析取范式。若范式包含所有极小项，则公式为重言式，原蕴含关系得证。((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)//整理合并⇔m₀∨m₁∨m₂∨m₃结论上述主析取范式包含了两个命题变元下所有可能的极小项（共4个）。这说明，无论对P和Q赋予何种真值（0或1），该逻辑公式的取值都为真。因此，该公式为重言式，蕴含关系成立。常用基本蕴含关系（表1.22）序号逻辑表达式命题蕴含定律/规则名称I1P∧Q⇒P简化规则(Simplification)I2P∧Q⇒Q简化规则(Simplification)I3P⇒P∨Q添加规则(Addition)I4Q⇒P∨Q添加规则(Addition)I5P∨Q,¬P⇒Q选言三段论(DisjunctiveSyllogism)I6P∨Q,¬Q⇒P选言三段论(DisjunctiveSyllogism)I7P,Q⇒P∧Q合取引入规则(Conjunction)I8P→Q,P⇒Q假言推理/分离规则(ModusPonens)I9P→Q,¬Q⇒¬P