最后更新: 2025-11-08 14:49 查看: 236 次纠错评论(0) 课件开VIP

等值演算

## 等值演算
两个公式在什么情况下代表了同一个命题呢？抽象地看，**它们的真值完全相同时即代表了相同的命题**。

**定义1.11** 设 $A$ 和 $B$ 为两个命题公式，若 $A, B$ 构成的等价式 $A \leftrightarrow B$ 为重言式，则称 $A$与 $B$ 是等值的，记作 $A \Leftrightarrow B$ ．

设 $A, B, C$ 为任意的公式，公式之间的等值关系具有如下性质：
（1）自反性：$A \Leftrightarrow A$ ．
（2）对称性：若 $A \Leftrightarrow B$ ，则 $B \Leftrightarrow A$ ．
（3）传递性：若 $A \Leftrightarrow B, B \Leftrightarrow C$ ，则 $A \Leftrightarrow C$ ．
设公式 $A, B$ 共含有 $n$ 个命题变项，可能 $A$ 或 $B$ 有哑元，若 $A$ 与 $B$ 有相同的真值表，则说明在 $2^n$ 个赋值的每个赋值下，$A$ 与 $B$ 的真值都相同，于是等价式 $A \leftrightarrow B$ 应为重言式。

例如：$(p \rightarrow q) \Leftrightarrow((\neg p \vee q) \vee(\neg r \wedge r)), r$ 为左边公式的亚元。

注意 定义中给出的符号 $\Leftrightarrow$ 不是联结词符，它是用来说明 $A$ 与 $B$ 等值 $(A \leftrightarrow B$ 是重言式）的一种记法．读者不要将 $\Leftrightarrow$ 与 $\leftrightarrow$ 混为一谈，同时也要注意它与一般等号 $(=)$ 的区别．

可以用真值表的方法判别两个公式是否等值，即列出 $A \leftrightarrow B$ 的真值表，判断 $A \leftrightarrow B$ 是否为重言式．若 $A \leftrightarrow B$ 为重言式，则 $A \Leftrightarrow B$ ，否则 $A \Leftrightarrow B$ ．

例 1.10 判断下列各组公式是否等值．
（1）$\neg(p \vee q)$ 与 $\neg p \wedge \neg q$ 。
（2）$p \rightarrow(q \rightarrow r)$ 与 $(p \rightarrow q) \rightarrow r$ ．
（3）$p \rightarrow(q \rightarrow r)$ 与 $(p \wedge q) \rightarrow r$ ．
解（1）列出 $\neg(p \vee q) \leftrightarrow(\neg p \wedge \neg q)$ 的真值表如表1．11所示．

根据真值表1．11可知 $\neg(p \vee q) \leftrightarrow(\neg p \wedge \neg q)$ 为重言式，故 $\neg(p \vee q) \Leftrightarrow \neg p \wedge \neg q$ ．其实在用真值表法判断 $A \leftrightarrow B$ 是否为重言式时，真值表的最后一列（即 $A \leftrightarrow B$ 的真值表的最后结果）可以省略．若 $A$ 与 $B$ 的真值表相同，则 $A \Leftrightarrow B$ ，否则 $A \Leftrightarrow B$ ．

![图片](/uploads/2025-11/688df9.jpg)
 
 
 （2）列出 $p \rightarrow(q \rightarrow r)$ 与 $(p \rightarrow q) \rightarrow r$ 的真值表如表 1.12 所示．
 
![图片](/uploads/2025-11/8dc131.jpg)
  
  
  
 由于 $p \rightarrow(q \rightarrow r)$ 与 $(p \rightarrow q) \rightarrow r$ 的真值表不相同，所以 $p \rightarrow(q \rightarrow r) \Leftrightarrow(p \rightarrow q) \rightarrow r$ ．
（3）列出 $p \rightarrow(q \rightarrow r)$ 与 $(p \wedge q) \rightarrow r$ 的真值表如表 1.13 所示．

![图片](/uploads/2025-11/b94132.jpg)
 
 
 由于 $p \rightarrow(q \rightarrow r)$ 与 $(p \wedge q) \rightarrow r$ 的真值表相同，所以 $p \rightarrow(q \rightarrow r) \Leftrightarrow(p \wedge q) \rightarrow r$ ．
虽然用真值法可以判断任何两个命题公式是否等值，但是当命题变项较多或公式的层次比较复杂时，工作量是很大的．我们可以先利用真值表验证一组基本的、重要的重言式，然后以它们为基础进行公式之间的演算，从而判断公式之间是否等值．

表 1.14 给出一些基本的等值式，也称为命题定律．

![图片](/uploads/2025-11/5c563e.jpg)

读者可以利用真值表验证以上等值式，并牢牢记住它们．需要注意的是以上等值式中出现的 $A, B, C$ 可以代表任意的命题公式，我们把这些等值式称为等值式模式，以它们为基础进行演算，可以证明公式等值．

由已知的等值式推演出新的等值式的过程称为等值演算．在等值演算中，需要使用如下的重要规则．

##  置换规则

置换规则 设 $\tau(A)$ 是含公式 $A$ 的命题公式，$\tau(B)$ 是用公式 $B$ 置换 $\tau(A)$ 中的 $A$ 后得到

`例`的命题公式，若 $A \Leftrightarrow B$ ，则 $\tau(A) \Leftrightarrow \tau(B)$ ．
  用等值演算法证明 $p \rightarrow(q \rightarrow r) \Leftrightarrow(p \wedge q) \rightarrow r$ ．
证明

$$
\begin{aligned}
p \rightarrow(q \rightarrow r) & \Leftrightarrow \neg p \vee(q \rightarrow r) & & \text { (蕴涵等值式, 置换规则) } \\
& \Leftrightarrow \neg p \vee(\neg q \vee r) & & \text { (蕴涵等值式, 置换规则) } \\
& \Leftrightarrow(\neg p \vee \neg q) \vee r & & \text { (结合律, 置换规则) } \\
& \Leftrightarrow \neg(p \wedge q) \vee r & & \text { (德•摩根律, 置换规则) } \\
& \Leftrightarrow(p \wedge q) \rightarrow r & & \text { (蕴涵等值式, 置换规则) }
\end{aligned}
$$

所以 $p \rightarrow(q \rightarrow r) \Leftrightarrow(p \wedge q) \rightarrow r$ 成立。
公式之间的等值关系具有自反性、对称性和传递性，所以上述演算中得到的 5 个公式彼此之间都是等值的。由于在演算的每一步都用到了置换规则，因而在以后的等值演算中，置换规则均不必写出．另外用等值演算不能直接证明两个公式不等值．要证明两个公式不等值，可以列出真值表来检查这两个公式的真值是否完全相同，也可以看是否能找到一个真值赋值，使得两个公式的真值不相同来证明。

除此以外，等值演算法还可以判断公式类型。设 $A$ 为命题公式，$A$ 为矛盾式当且仅当 $A \Leftrightarrow 0 ; A$ 为重言式当且仅当 $A \Leftrightarrow 1 . A$ 为可满足式当且仅当 $A \Leftrightarrow A^{\prime}$ ，而 $A^{\prime}$ 是一个可满足式．

`例` 用等值演算法判断下列公式的类型．
（1）$q \wedge \neg(p \rightarrow q)$ ．
（2）$(p \rightarrow(p \vee q)) \wedge r$
（3）$((p \wedge q) \vee(p \wedge \neg q)) \wedge r$ ．
解:(1)
$$
\begin{aligned}
  q \wedge \neg(p \rightarrow q) & \Leftrightarrow q \wedge \neg(\neg p \vee q) & & (\text { 蕴涵等值式 }) \\
& \Leftrightarrow q \wedge(\neg \neg p \wedge \neg q) & & (\text { 德•摩根律 }) \\
& \Leftrightarrow q \wedge(p \wedge \neg q) & & (\text { 双重否定律 }) \\
& \Leftrightarrow(q \wedge \neg q) \wedge p & & (\text { 交换律、结合律 }) \\
& \Leftrightarrow 0 \wedge p & & (\text { 矛盾律 }) \\
& \Leftrightarrow 0 & & (\text { 零律 })
\end{aligned}
$$

所以 $q \wedge \neg(p \rightarrow q)$ 为矛盾式．

（2）

$$
\begin{array}{rlr}
(p \rightarrow(p \vee q)) \wedge r & \Leftrightarrow(\neg p \vee(p \vee q)) \vee r & (\text { 蕴涵等值式 }) \\
& \Leftrightarrow((\neg p \vee p) \vee q) \vee r & (\text { 结合律 }) \\
& \Leftrightarrow 1 \vee q \vee r & (\text { 排中律 }) \\
& \Leftrightarrow 1 \vee(q \vee r) & (\text { 结合律 }) \\
& \Leftrightarrow 1 & (\text { 零律 })
\end{array}
$$

所以 $(p \rightarrow(p \vee q)) \wedge r$ 为重言式．

（3）$((p \wedge q) \vee(p \wedge \neg q))$

$$
\begin{aligned}
& \wedge r \Leftrightarrow p \wedge(q \vee \neg q) \wedge r  （分配律）\\
& \Leftrightarrow p \wedge 1 \wedge r （排中律） \\
& \Leftrightarrow p \wedge r （同一律）
\end{aligned}
$$

从上述的等值演算结果可以知道，$(p \wedge q) \vee(p \wedge \neg q) \wedge r$ 为可满足式， 101 和 111 是公式的成真赋值， $000 、 001 、 010 、 011 、 100 、 110$ 是公式的成假赋值．

`例`  试证：$P \rightarrow(Q \rightarrow R) \Leftrightarrow(P \wedge Q) \rightarrow R$ 。
证明

$$
\begin{aligned}
& P \rightarrow(Q \rightarrow R) \\
& \Leftrightarrow P \rightarrow(\neg Q \vee R) \\
& \Leftrightarrow \neg P \vee \neg Q \vee R \\
& \Leftrightarrow \neg(P \wedge Q) \vee R \\
& \Leftrightarrow(P \wedge Q) \rightarrow R
\end{aligned}
$$

`例`试证：$(P \rightarrow Q) \wedge(R \rightarrow Q) \Leftrightarrow(P \vee R) \rightarrow Q$ 。
证明

$$
\begin{aligned}
& (P \rightarrow Q) \wedge(R \rightarrow Q) \\
& \Leftrightarrow(\neg P \vee Q) \wedge(\neg R \vee Q) \\
& \Leftrightarrow(\neg P \wedge \neg R) \vee Q \\
& \Leftrightarrow \neg(P \vee R) \vee Q \\
& \Leftrightarrow(P \vee R) \rightarrow Q
\end{aligned}
$$

`例`试证：$(P \wedge Q) \rightarrow R \Leftrightarrow(P \rightarrow R) \vee(Q \rightarrow R)$ 。
证明

$$
\begin{aligned}
& (P \wedge Q) \rightarrow R \\
& \Leftrightarrow \neg(P \wedge Q) \vee R \\
& \Leftrightarrow \neg P \vee \neg Q \vee R \\
& \Leftrightarrow(\neg P \vee R) \vee(\neg Q \vee R) \\
& \Leftrightarrow(P \rightarrow R) \vee(Q \rightarrow R)
\end{aligned}
$$

科数题库(单机版) 会议室预约系统(book)

今日还可看 0 篇未注册用户每天查看4篇，注册用户每天8篇，开通VIP会员无限制查看。

免费注册

《高等数学》难点解析

高数教程 泰勒公式切线与法线切平面与法平面驻点·拐点·极值点·零点间断点渐进线瑕积分欧拉方程伯努利方程 Abel 收敛定理偏导数的几何意义偏导数的几何意义梯度数量场与向量场多元函数极值拉格朗日算子通量与散度环流量与旋度格林公式高斯公式斯托克斯公式三大公式比较傅里叶级数极坐标微元点法式方程变上限定积分 X型计算面积 Y型计算面积微分的意义渐近线间断点 y''+py'+qy=f(x)方程高斯黎曼傅里叶变换(复数) 拉普拉斯变换(复数)

《线性代数》难点解析

线代教程 近世代数对数学的整体思考线性的意义矩阵乘法(列视角) 矩阵乘法(行视角) 矩阵左乘矩阵右乘逆矩阵求解方程组阶梯形矩阵的求法方程组解的判定四阶行列式的计算线性变换的意义线性空间向量组的等价线性空间的几何意义基础解系的求法施密特正交化特征值与特征向量的意义矩阵相似的几何意义矩阵可对角化的理解秩的意义(向量版) 秩的意义(方程版) 二次型的意义

《概率论与数理统计》难点解析

概率教程 置信区间与上a分位数概率中的“取”与“放” 贝叶斯公式全概率公式泊松分布指数分布伽玛分布二维密度图的意义卷积的意义相关系数的意义 k阶矩是与矩母函数卡方分布的作用单正态区间估计理解假设检验理解切比雪夫不等式中心极限定理

上一篇：命题公式的赋值与真值表(重言式/矛盾式)

下一篇：利用等值演算简化逻辑推理

本文对您是否有用？有用 (0) 无用 (0)