离散数学 课件 1.2 联结词

CHAPTER01命题逻辑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）。注意符号位的