阶段 2 · 仅逻辑章节

命题逻辑与
谓词逻辑

本页只覆盖离散数学的前两章：把自然语言转化为形式表达、判断真假与等价、完成推理和量词分析。

CHAPTER 01

命题逻辑 ⭐⭐⭐ 真值表 / 等值演算 / 范式

命题是有唯一真值的陈述句；原子命题不可再拆，复合命题由联结词连接。问句、命令和真值随对象变化的句子本身不是命题。

五个联结词

\(\neg P\) 否定；\(P\land Q\) 合取；\(P\lor Q\) 析取；\(P\to Q\) 蕴含；\(P\leftrightarrow Q\) 等价。

公式分类

永真式任意赋值真；永假式任意赋值假；可满足式至少有一个赋值为真。

真值表与核心等价式

\(P\)\(Q\)\(P\land Q\)\(P\lor Q\)\(P\to Q\)\(P\leftrightarrow Q\)
TTTTTT
TFFTFF
FTFTTF
FFFFTT
\(P\to Q\equiv\neg P\lor Q,\quad\neg(P\land Q)\equiv\neg P\lor\neg Q,\quad\neg(P\lor Q)\equiv\neg P\land\neg Q\)

为什么蕴含在前件假时为真？“若 \(P\) 则 \(Q\)”只禁止 \(P\) 真而 \(Q\) 假的反例；前件假时没有违反承诺。等价演算中先消去 \(\to,\leftrightarrow\)，再用德摩根律和分配律最稳定。

题型：判断等价/永真式。变量少时列真值表；变量多时做等值演算。两公式各行真值完全相同才逻辑等价；某公式最后化为 \(T\) 才是永真式。
例题：证明 \(\neg(P\to Q)\equiv P\land\neg Q\)。
\(\neg(P\to Q)\equiv\neg(\neg P\lor Q)\equiv\neg\neg P\land\neg Q\equiv\boxed{P\land\neg Q}\)。每一步分别使用蕴含等价、德摩根律、双重否定律。

对偶、范式与主范式

对偶式在不含否定的表达式中交换 \(\land\leftrightarrow\lor\)、\(T\leftrightarrow F\)。析取范式（DNF）是若干合取项的析取；合取范式（CNF）是若干析取项的合取。主析取范式取真值表中为真的行：每一行写一个最小项；主合取范式取为假的行：每一行写一个最大项。

m_i:\text{该行变量为 T 取本身、为 F 取否定；}\qquad M_i:\text{该行变量为 F 取本身、为 T 取否定}
练习 1（基础）：求 \((P\to Q)\land P\) 的等价简式

思路：先去蕴含。
\((\neg P\lor Q)\land P=(\neg P\land P)\lor(Q\land P)=F\lor(P\land Q)=\boxed{P\land Q}\)。
易错：分配后不能遗漏 \(\neg P\land P=F\)。

练习 2（提高）：写出 \(P\to Q\) 的主析取范式

仅 \(P=T,Q=F\) 时为假，真值行为 \(TT,FT,FF\)。对应最小项为 \(P\land Q,\ \neg P\land Q,\ \neg P\land\neg Q\)。
\(\boxed{(P\land Q)\lor(\neg P\land Q)\lor(\neg P\land\neg Q)}\)。最小项编号若按 \(PQ\) 二进制从 \(00\) 起，为 \(\Sigma m(0,1,3)\)。

KARNAUGH MAP

卡诺图化简 ⭐⭐⭐

卡诺图将相邻最小项排成 Gray 码顺序，使相邻格只改变一个变量。2 变量顺序为 \(0,1\)；3/4 变量的两位轴顺序为 \(00,01,11,10\)，不是普通二进制 \(00,01,10,11\)。

\(\text{圈组大小必须为 }1,2,4,8,\ldots;\quad\text{圈越大，组内变化的变量越多，被消掉的变量越多。}\)
规则原因 / 操作
边界相邻、四角相邻卡诺图的行列首尾相接，Gray 码只差一位
允许重叠圈一个 1 可服务于多个更大圈，获得更简表达式
无关项 \(d\)可按 0 或 1 使用；只在能扩大圈时纳入
例题：三变量函数在最小项 \(m(1,3,5,7)\) 为 1。二进制分别为 \(001,011,101,111\)，四格共同不变的只有 \(C=1\)，故 \(\boxed{F=C}\)。这说明四格圈消掉了 \(A,B\)。
练习 3（综合）：四变量图中一整行 \(AB=01\) 的四格为 1，化简结果？

该行固定 \(A=0,B=1\)，列变量 \(C,D\) 在四格中全变化，故均被消掉，\(\boxed{\neg A\land B}\)。边界两列仍相邻，不能因位置分开而拆成小圈。

易错：圈不能含 3、5、6 个格；优先最大圈、最少圈；主析取范式先来自真值表，不必先画卡诺图。
CHAPTER 02

谓词逻辑 ⭐⭐⭐ 符号化 / 量词否定 / 辖域

谓词 \(P(x)\) 含变量，给定个体域和变量值后才有真值；量词把变量约束为对域内全部或某些个体的断言。

基本对象

个体域：讨论范围；\(P(x)\)：谓词；\(\forall x\)：对所有；\(\exists x\)：至少存在一个。

变量与辖域

落在量词辖域内的同名变量是约束变量；不在任何同名量词辖域内的是自由变量。

\(\neg\forall x\,P(x)\equiv\exists x\,\neg P(x),\qquad\neg\exists x\,P(x)\equiv\forall x\,\neg P(x)\)

直观：“并非所有人都及格”只需找到“至少一人未及格”；“不存在人未及格”等价于“所有人都及格”。否定量词时必须翻转量词并否定谓词。

量词顺序：\(\forall x\exists y\,R(x,y)\) 表示每个 \(x\) 都可有自己的 \(y\)；\(\exists y\forall x\,R(x,y)\) 表示同一个 \(y\) 对所有 \(x\) 都适用。后者通常强得多。例如“每个学生有一本书”不推出“有一本书属于每个学生”。
自然语言符号化：先写清个体域和谓词含义；“所有”用 \(\forall\)，“存在/有一个”用 \(\exists\)；“仅当”注意方向；最后读回中文检查量词顺序与否定位置。
练习 4（基础）：写出“并非每个实数都有平方根是实数”的正确否定结构

若 \(P(x)\) 表示“\(x\) 有实平方根”，则“并非每个 \(x\) 有此性质”为 \(\boxed{\exists x\,\neg P(x)}\)。在实数域可取 \(x=-1\) 作为见证。易错：不能写成 \(\forall x\,\neg P(x)\)。

练习 5（提高）：在 \(\mathbb R\) 上，符号化“每个实数都有一个相反数”

令 \(R(x,y)\) 表示 \(x+y=0\)。同一个 \(y\) 不必服务所有 \(x\)，故 \(\boxed{\forall x\exists y\,(x+y=0)}\)，而不是 \(\exists y\forall x\,(x+y=0)\)。

练习 6：找出 \(\forall x(P(x,y)\to\exists yQ(x,y))\) 中的自由变量

最外层 \(\forall x\) 约束所有 \(x\)；右侧 \(\exists y\) 只约束 \(Q(x,y)\) 内的 \(y\)，而 \(P(x,y)\) 的 \(y\) 不在其辖域内。因此 \(\boxed{P\text{ 中的 }y\text{ 是自由变量}}\)。同一字母在不同辖域可同时有自由、约束出现。

STAGE 02 SUMMARY

阶段总结与考前速查

必须记忆必须理解必须会做
\(P\to Q\equiv\neg P\lor Q\)、德摩根律、量词否定蕴含的唯一假例；量词顺序决定含义；大圈消变量真值表、等值演算、主范式、卡诺图、符号化与辖域
本阶段易错：把 \(P\to Q\) 当作 \(Q\to P\)；Gray 码按普通二进制排；量词否定只翻量词不否定谓词；把 \(\forall x\exists y\) 与 \(\exists y\forall x\) 混同。