命题逻辑

主讲教师

李 辉

命题和逻辑联结词

数理逻辑用数学方法(引入一套符号体系)来研究逻辑, 又称为符号逻辑.

数理逻辑广泛应用于机器证明、人工智能、程序设计等领域.

人工智能是在计算机诞生之后才出现的新兴学科, 继承了数理逻辑和统计学, 目的是让机器实现接近人的思考和逻辑推理的能力.

数理逻辑在计算机相关学科中的应用

计算机硬件系统设计的基础

  • 计算机的运算通过数字逻辑技术实现, 布尔代数和范式是数字逻辑的基础理论.

  • 计算机科学中开关电路的设计也用到数理逻辑中的布尔代数和范式.

例: 银行的金库装有自动报警装置.仅当总经理室的一个人工控制开关合上时, 它才能动作.如果这个人工开关已合上, 那么当金库的门被撬、或者当工作人员未切断电源并且通向金库的通道上有人, 就要发出警报.试设计这个控制电路.

设 \(p\): 人工开关合上. \(q\): 金库的门被撬. \(r\): 工作人员尚未切断电源. \(s\): 通向金库的通道有人. \(F\):自动报警装置报警. \[F{\Leftrightarrow}P{\wedge}(Q{\vee}(R{\wedge}S)).\]

人工智能的基础

人工智能是以计算数学、图灵机为理论基础, 对问题进行推理和求解, 让机器完成智能工作的科学.

逻辑推理是人工智能研究中最持久的子领域之一.

逻辑则是所有数学推理的基础.

阿兰·图灵 (Alan Turing, 1912.6.23－1954.6.7)

  • 英国数学家, 逻辑学家.

  • 1931年图灵本科就读于剑桥大学国王学院, 在普林斯顿大学获得博士学位.二战期间回到剑桥, 协助军方破解德国的著名密码系统Enigma, 帮助盟军取得二战胜利.

  • 在人工智能方面, 图灵提出一种用于判定机器是否具有智能的试验方法, 即图灵试验.

  • 此外, 图灵提出的图灵机模型是现代计算机的理论原型.

数理逻辑在现实生活中的应用

人员安排和指派问题

例: \(A\), \(B\), \(C\)和\(D\)四个人中要派两个人去出差, 根据以下三个条件该如何指派？

  1. 若\(A\)去则\(C\)和\(D\)要去一人.

  2. \(B\)和\(C\)不能都去.

  3. \(C\)去则\(D\)要留下.

离散数学中的数理逻辑主要包括命题逻辑和谓词逻辑(一阶逻辑).

研究中心问题:推理.

推理(前提\({\rightarrow}\)结论)的基本要素是命题.

命题

命题:具有真假意义或能判断真假的陈述句.

两个条件:(1)陈述句(2)能判断真假

真值:命题的取值.

任何一个命题的真值都是唯一的.

  • 真命题:命题真值为真(\(T\), 1)

  • 假命题:命题真值为假(\(F\), 0)

例: 判断下列语句是否是命题.

  1. 您好吗？

  2. 请勿吸烟!

  3. \(x+y>5\).

  4. 台湾是中国的一部分.

解:

(1), (2)不是陈述句, 所以不是命题.

(3)虽然是陈述句, 但它的值要随x和y的取值而变, 不确定, 因此也不是命题.

(4)是真命题.

  1. 人能活到一千岁.

  2. 月球上有生物存在.

  3. 理发师给且仅给那些不给自己理发的人理发.

解: (5)是假命题.

(6)的真值是什么, 现在谁也说不出来, 但是”月球上有生物存在”这个命题肯定有唯一答案(存在或不存在, 即命题为真或为假是确定的), 它具有真假意义, 它是命题.

(7)是陈述句, 但无法断定其真值.这是一个悖论.

理发师悖论:

  • 理发师不给自己理发\({\Rightarrow}\)理发师应该给自己理发

  • 理发师要给自己理发\({\Rightarrow}\)理发师不应该给自己理发

命题分简单命题和复合命题.

简单命题:由简单句构成的命题(也称原子命题).

简单命题不能再进行细分. 简单命题一般用小写英文字母\(p, q, r{\cdots}\)及其带下标的小写英文字母\(p_i, q_i, r_i, {\cdots}\)表示. 这些表示简单命题的符号称为命题标识符.

例:

  • \(p\): 海南是个美丽的岛屿

  • \(q\): 今天是晴天

复合命题:由若干原子命题和联结词联结而成的命题(也称分子命题).

例:

  • 如果我有一双翅膀, 那么我能在蓝天上飞翔.

  • 明天下雪或者明天下雨.

复合命题的表示和真值依赖于其中各原子命题和所使用的联结词, 这些联结词又称为逻辑联结词.

逻辑联结词

定义:设\(p\)为一命题, 则\(p\)的否定称为命题\(p\)的否命题, 记作\({\lnot}p\)(或\({\sim}p\)).

符号\({\lnot}\)称为否定联结词.

在自然语言中，表示”不是”, “并非”, “不成立”, “没有”, “是不对的”都可以符号化为\({\lnot}\).

复合命题\({\lnot}P\)的真值由下表给出, \({\lnot}P\)为真当且仅当\(P\)为假.

  \[ \begin{array}{cc} p & {\lnot}p \\ 0 & 1 \\ 1 & 0 \\ \end{array} \]

设\(p\): 杭州是一个城市

则\({\lnot}p\):杭州不是一个城市

设\(q\): 每个实数都可表示成分数

则\({\lnot}q\):并非每个实数都可表示成分数

定义:设\(p\), \(q\)为命题, 复合命题“\(p\)并且\(q\)”称为\(p\)和\(q\)的合取式复合命题, 记作\(p{\wedge}q\).

符号\({\wedge}\)称为合取联结词.

在自然语言中, 表示“并且”意思的联结词, 如: “既\({\cdots}\)又\({\cdots}\)”,

“不但\({\cdots}\)而且\({\cdots}\)”,

“一面\({\cdots}\)一面\({\cdots}\)”,

“\({\cdots}\)和\({\cdots}\)”,

“\({\cdots}\)与\({\cdots}\)”

等都可以符号化为\({\wedge}\).

复合命题\(p{\wedge}q\)的真值由下表给出.

  \[ \begin{array}{ccc} p & q & p{\wedge}q \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \]

 

\(p{\wedge}q\)的真值为真当且仅当\(p\)和\(q\)同时为真.

设\(p\): 李明在看电影, \(q\): 张华在看电影,

则\(p{\wedge}q\):李明和张华都在看电影.

定义:设\(p\), \(q\)为命题, 复合命题“\(p\)或\(q\)”称为\(p\)和\(q\)的析取式复合命题, 记作\(p{\vee}q\).

符号\({\vee}\)称为析取联结词.

复合命题\(p{\vee}q\)的真值由下表给出.\(p{\vee}q\)真值为真当且仅当\(p\), \(q\)至少有一个为真.

  \[ \begin{array}{ccc} p & q & p{\vee}q \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 1 \\ \end{array} \]

在自然语言中, “或者\({\cdots}\)或者”, “要么\({\cdots}\)要么”都可符号为“\({\vee}\)”.

设\(p\): 他现在在上海, \(q\): 他现在在广州.

则\(p{\vee}q\):他现在在上海或者在广州.

设\(r\): 我们第一节课上离散数学课, \(s\): 我们第一节课上高等数学课.

则\(r{\vee}s\):我们第一节课上离散数学课或高等数学课.

定义:设\(p\), \(q\)为命题, 复合命题“如果\(p\)则\(q\)”称为\(p\)和\(q\)的蕴含式复合命题, 记作\(p{\rightarrow}q\).

符号\({\rightarrow}\)称为蕴含联结词(条件联结词).

其中\(p\)称为条件式的前件, \(q\)称为条件式的后件.

复合命题\(p{\rightarrow}q\)的真值由下表给出.

  \[ \begin{array}{ccc} p & q & p{\rightarrow}q \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \]

设\(p\): 他有时间, \(q\): 他会帮助你,

则\(p{\rightarrow}q\):如果他有时间, 那么他会帮助你.

设\(p\): 如果鲨鱼会飞, \(q\): 长城位于中国北方,

则\(p{\rightarrow}q\):如果鲨鱼会飞, 则长城位于中国北方.

因为命题\(p\)为假, 命题\(q\)为真, 故命题\(p{\rightarrow}q\)为真.

 

在自然语言中, “如果\({\cdots}\)”和“则\({\cdots}\)”之间通常存在某种内在的联系.

而在数理逻辑中, 对于\(p{\rightarrow}q\)来说, 只要\(p\)和\(q\)是命题, \(p{\rightarrow}q\)就有意义, 而不要求\(p\)和\(q\)一定有什么关系.

\(p{\rightarrow}q\)的逻辑关系为\(q\)是\(p\)的必要条件, 或\(p\)是\(q\)的充分条件.

在自然语言里, 特别是在数学中, \(q\)是\(p\)的必要条件有很多不同的叙述方式:

  • “只要\(p\), 就\(q\)”

  • “只有\(q\)才\(p\)”

  • “如果\(p\), 那么\(q\)”

  • “除非\(q\)才\(p\)”

  • “因为\(p\), 所以\(q\)”

以上各种叙述方式表面上有所不同，但都表达的是\(q\)是\(p\)的必要条件，因而所用联结词均应符号化为\(p{\rightarrow}q\)

例:

  1. 如果天下雨, 那么我就骑自行车上学.

  2. 只要天下雨, 我就骑自行车上学.

  3. 天下雨, 所以我骑自行车上学.

设\(p\): 天下雨, \(q\): 我骑自行车上学, 上述命题可符号化为:\(p{\rightarrow}q\).

定义:设\(p\)和\(q\)为命题, 复合命题“\(p\)当且仅当\(q\)”称为\(p\)和\(q\)的等价式复合命题, 记作\(p{\leftrightarrow}q\).

符号\({\leftrightarrow}\)称为等价联结词(双条件联结词).

复合命题\(p{\leftrightarrow}q\)的真值由下表给出.

  \[ \begin{array}{ccc} p & q & p{\leftrightarrow}q \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 1 \\ \end{array} \]

在自然语言中, “当且仅当”, “等价于”, “同\(\cdots\)一样”等都可以符号化为\({\leftrightarrow}\).

双条件式表示的基本逻辑关系为\(p\)与\(q\)互为充分必要条件.

设\(p\): 两圆面积相等, \(q\): 两圆半径相等,

则\(p{\leftrightarrow}q\):两圆面积相等当且仅当两圆半径相等.

复合命题的真值只取决于各原子命题的真值, 而与它们的内容无关.

总结一下

 

\[ \begin{array}{ccccccc} p & q & {\lnot}p & p{\wedge}q & p{\vee}q & p{\rightarrow}q &p{\leftrightarrow}q \\ 0 & 0 & 1&0&0&1&1 \\ 0 & 1 & 1&0&1&1&0 \\ 1 & 0 & 0&0&1&0&0 \\ 1 & 1 & 0&1&1&1&1 \\ \end{array} \]

 

其中:0代表\(F\)(假), 1代表\(T\)(真)

命题公式和真值表

在命题逻辑中, 有命题常元和命题变元之分.

命题常元表示一个特定的命题; 命题变元表示任意命题.

命题常元表示一个特定的命题, 所以它有确定的真值.

命题变元没有确定的真值, 它不是命题, 仅当用一个特定命题取代它时, 才能确定真值.

这个取代操作称为对命题变元的真值指派, 赋值或解释(Intepretation).

命题公式递归定义如下:

  1. 命题常元和命题变元(如\(p, q, r, {\cdots}, T, F\))是命题公式;

  2. 如果\(A\)是命题公式, 那么(\({\lnot}A\))也是命题公式;

  3. 如果\(A, B\)是命题公式, 那么\((A{\wedge}B)\), \((A{\vee}B)\), \((A{\rightarrow}B)\)和\((A{\leftrightarrow}B)\)也是命题公式;

  4. 规则(1)-(3)的有限次使用得到的由命题常元, 命题变元, 逻辑联结词和括号组成的符号串也是命题公式.

当命题公式比较复杂时, 常常使用很多圆括号, 为了减少圆括号的使用量, 可作以下约定:

  1. 规定联结词的优先级由高到低的次序为\({\lnot}{\wedge}{\vee}{\rightarrow}{\leftrightarrow}.\)

  2. 相同的联结词按从左至右次序计算时, 圆括号可省略.

  3. (\({\lnot}A\))两端的括号和任一命题公式最外层的圆括号可以省略.

  4. 定义中引入的\(A, B\)等符号表示任意命题公式, 而不是某个具体的公式.

例: \[p{\wedge}q\] \[(p{\rightarrow}(q{\rightarrow}r)){\vee}r\] \[(p{\rightarrow}q{\rightarrow}r){\vee}r\] \[(p{\wedge}q{\wedge}r){\rightarrow}(p{\vee}(q{\wedge}s))\] 是命题公式.

而 \[(p{\wedge}q){\rightarrow}({\rightarrow}r){\wedge}r{\vee}p\] \[(p{\vee}q){\rightarrow}r)\] 不是命题公式.

如果\(A_{1}\)是命题公式\(A\)的一个组成部分, 且\(A_{1}\)本身也是一个命题公式, 称\(A_{1}\)是\(A\)的子命题(子公式).

对命题公式\[(p{\wedge}q){\rightarrow}(r{\vee}(q{\wedge}s))\]而言,

\[p{\wedge}q, q{\wedge}s, r{\vee}(q{\wedge}s)\]都是它的子公式.

命题的符号化

将自然语言描述的命题表示成命题公式的形式, 称为命题的翻译或命题的符号化.

命题符号化的步骤:

  1. 找出命题中各原子命题, 将其符号化.

  2. 找出命题中各联结词, 将联结词符号化.

  3. 把符号化的原子命题和符号化的联结词联结起来.

将下列命题符号化:

  1. 派小王或小李出差.

令\(p\): 派小王出差; \(q\): 派小李出差, 那么命题符号化为: \(p{\vee}q\).

  1. 我们不能既划船又跑步.

令\(p\): 我们划船; \(q\): 我们跑步, 那么命题符号化为: \({\lnot}(p{\wedge}q)\).

  1. 如果你来了, 那么他唱不唱歌将看你是否伴奏而定.

令\(p\): 你来了; \(q\): 他唱歌; \(r\): 你伴奏, 那么命题符号化为: \(p{\rightarrow}(q{\leftrightarrow}r)\).

  1. 假如上午不下雨, 我去看电影, 否则就在家里看书.

令\(p\): 上午下雨; \(q\): 我去看电影; \(r\): 我在家读书, 那么命题符号化为: \(({\lnot}p{\rightarrow}q){\wedge}(p{\rightarrow}r)\).

  1. 在公式\((p{\wedge}{\lnot}q){\rightarrow}{\lnot}r\)中:

令\(p\): 李强是体育爱好者; \(q\): 李强是文艺爱好者; \(r\): 李强是文体爱好者,

则公式\((p{\wedge}{\lnot}q){\rightarrow}{\lnot}r\)表示:

如果李明是体育爱好者, 但不是文艺爱好者, 那么李明不是文体爱好者.

命题符号化时应注意以下几点:

  1. 确定句子是否为命题, 不是就无法进行命题符号化;

  2. 确定句中联结词是否能对应于哪一个逻辑联结词;

  3. 正确表示原子命题和选择逻辑联结词;

  4. 要按逻辑关系进行命题符号化，而不能凭字面翻译.

 

令\(p\): 林芬做作业; \(q\): 林芳做作业, 则“林芬和林芳同在做作业”可符号化为\(p{\wedge}q.\)

但是, “林芬和林芳是姐妹”不能符号化为\(p{\wedge}q\), 这是一个原子命题.

真值表

设\(A\)是一个命题公式, \(p_{1}, p_{2}, {\cdots}, p_{n}\)是出现在\(A\)中的所有命题变元(可以用\(A(p_{1}, p_{2}, {\cdots}, p_{n})\)来表示含有\(n\)个命题变元\(p_{1}, p_{2}, {\cdots}, p_{n}\)的命题公式\(A\)), 给变元\(p_{1}, p_{2}, {\cdots}, p_{n}\)指定一组真值, 称为对\(A\)的一个真值指派, 赋值或解释.

 

\[ \begin{array}{ccccc} p_1 & p_2 & {\cdots} & p_n & A(p_{1}, p_{2}, {\cdots}, p_{n}) \\ 0&0&{\cdots}&0& v_1 \\ 0&0&{\cdots}&1& v_2 \\ {\vdots}&{\vdots}&{\cdots}&{\vdots}&{\vdots}\\ 1&1&{\cdots}&1&v_{2^n} \\ \end{array} \]

 

含有\(n\)个变元的命题公式有\(2^{n}\)组不同的解释, 每个解释对应一个确定的真值.

对于命题公式\(A\), 由\(A\)所有可能的解释和\(A\)在其所有可能解释下所得真值列成的表, 称为命题公式\(A\)的真值表.

一个命题公式的真值表由两部分组成:

  1. 表的左边列出命题公式的每一个解释.对于一个含有\(n\)个命题变元的命题公式, 不同的解释共有\(2^{n}\)个.

  2. 表的右边部分列出对应于每个解释的命题公式真值.

计算命题公式\(({\lnot}p{\wedge}q){\vee}p\)的真值表.

解:

\[ \begin{array}{ccccc} p & q & {\lnot}p & {\lnot}p{\wedge}q & ({\lnot}p{\wedge}q){\vee}p \\ 0 & 0 & 1&0&0 \\ 0 & 1 & 1&1&1 \\ 1 & 0 & 0&0&1 \\ 1 & 1 & 0&0&1 \\ \end{array} \]

计算命题公式\((p{\rightarrow}q){\rightarrow}r\)的真值表.

解:

\[ \begin{array}{ccccc} p & q & r & p{\rightarrow}q & (p{\rightarrow}q){\rightarrow}r \\ 0&0&0&1&0 \\ 0&0&1&1&1 \\ 0&1&0&1&0 \\ 0&1&1&1&1 \\ 1&0&0&0&1 \\ 1&0&1&0&1 \\ 1&1&0&1&0 \\ 1&1&1&1&1 \\ \end{array} \]

给定命题公式\(A\).若\(A\)的所有解释都使\(A\)的真值为真, 则称命题公式\(A\)为永真式(重言式);

若\(A\)的所有解释, 都使\(A\)的真值为假, 则称命题公式\(A\)为永假式(矛盾式);

若\(A\)至少有一个解释使\(A\)的真值为真, 则称命题公式\(A\)为可满足式.

对于给定的命题公式, 判断它的类型(永真式, 永假式或可满足式)问题, 称为命题公式的判定问题.

用真值表判定命题公式\((p{\wedge}(p{\vee}q)){\leftrightarrow}{\lnot}p\)的类型.

解: \[ \begin{array}{ccccccc} p & q & p{\vee}q & p{\wedge}(p{\vee}q) & {\lnot}p & p{\wedge}(p{\vee}q){\leftrightarrow}{\lnot}p\\ 0 & 0 & 0&0&1&0 \\ 0 & 1 & 1&0&1&0 \\ 1 & 0 & 1&1&0&0 \\ 1 & 1 & 1&1&0&0 \\ \end{array} \]

 

可知, \((p{\wedge}(p{\vee}q)){\rightarrow}{\lnot}p\)为永假式.

用真值表判定命题公式\(p{\wedge}{\lnot}p\)的类型.

解:

  \[ \begin{array}{ccc} p & {\lnot}p & p{\wedge}{\lnot}p\\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{array} \]

 

可知, \(p{\wedge}{\lnot}p\)为永假式.

用真值表判定命题公式\(p{\vee}{\lnot}p\)的类型.

解:

  \[ \begin{array}{ccc} p & {\lnot}p & p{\vee}{\lnot}p\\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ \end{array} \]

 

可知, \(p{\vee}{\lnot}p\)为永真式.

用真值表判定命题公式\((p{\rightarrow}q){\rightarrow}r\)的类型.

解: \[ \begin{array}{ccccc} p & q & r & p{\rightarrow}q & (p{\rightarrow}q){\rightarrow}r \\ 0&0&0&1&0 \\ 0&0&1&1&1 \\ 0&1&0&1&0 \\ 0&1&1&1&1 \\ 1&0&0&0&1 \\ 1&0&1&0&1 \\ 1&1&0&1&0 \\ 1&1&1&1&1 \\ \end{array} \]

 

可知, \((p{\rightarrow}q){\rightarrow}r\)为可满足式.

等价式

命题定律

设\(A\)和\(B\)是两个命题公式, 若对\(A\)和\(B\)的任何相同解释, \(A\)和\(B\)总是取得相同的真值, 则称命题公式\(A\)和\(B\)是逻辑等价(或称等值)的. 记做\(A{\Leftrightarrow}B\), \(A{\Leftrightarrow}B\)称为等价式(等值式).

符号“\({\Leftrightarrow}\)”与“\({\leftrightarrow}\)”的区别与联系:

“\({\Leftrightarrow}\)”不是联结词, \(A{\Leftrightarrow}B\)不表示一个公式, 它表示两个公式间的逻辑等价关系.

“\({\leftrightarrow}\)”是联结词, \(A{\leftrightarrow}B\)是一个公式.

\(A{\Leftrightarrow}B\)当且仅当\(A{\leftrightarrow}B\)是永真式.

两命题公式是否等价, 可通过:

  1. 真值表来判断, 若命题公式\(A\)和\(B\)的真值表相同, 则命题公式\(A\)和\(B\)等价;

  2. 采用公式推演法(等值演算法)来证明.

求证: \(p{\wedge}q{\Leftrightarrow}q{\wedge}p\).

证明: 构造\(p{\wedge}q\)和\(q{\wedge}p\)的真值表如下:

  \[ \begin{array}{cccc} p & q & p{\wedge}q & q{\wedge}p\\ 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 1 \\ \end{array} \]  

因为\(p{\wedge}q\)与\(q{\wedge}p\)的真值表相同, 所以两命题公式等价.

也可通过证明\((p{\wedge}q){\leftrightarrow}(q{\wedge}p)\)为永真式.

\(p{\wedge}q{\Leftrightarrow}q{\wedge}p\).\((p{\wedge}q){\leftrightarrow}(q{\wedge}p)\)的真值表如下:

  \[ \begin{array}{ccccc} p & q & p{\wedge}q & q{\wedge}p&(p{\wedge}q){\leftrightarrow}(q{\wedge}p) \\ 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 \\ \end{array} \]

 

因为\((p{\wedge}q){\leftrightarrow}(q{\wedge}p)\)为永真式, 所以\(p{\wedge}q{\Leftrightarrow}q{\wedge}p.\)

求证: \((p{\vee}q){\rightarrow}r{\Leftrightarrow}({\lnot}p{\vee}r){\wedge}({\lnot}q{\vee}r).\)

证明: 构造\((p{\vee}q){\rightarrow}r\)和\(({\lnot}p{\vee}r){\wedge}({\lnot}q{\vee}r)\)的真值表如下.

 

\[ \begin{array}{ccccc} p & q & r & (p{\vee}q){\rightarrow}r & ({\lnot}p{\vee}r){\wedge}({\lnot}q{\vee}r) \\ 0&0&0&1&1 \\ 0&0&1&1&1 \\ 0&1&0&0&0 \\ 0&1&1&1&1 \\ 1&0&0&0&0 \\ 1&0&1&1&1 \\ 1&1&0&0&0 \\ 1&1&1&1&1 \\ \end{array} \]  

两真值表相同, 故两命题公式等价.

等价式的性质

自反性: 对任意命题公式\(A\), 有\(A{\Leftrightarrow}A.\)

对称性: 对任意命题公式\(A\)和\(B\), 若\(A{\Leftrightarrow}B\), \(B{\Leftrightarrow}A.\)

传递性: 对任意命题公式\(A\), \(B\)和\(C\), 若\(A{\Leftrightarrow}B\)且\(B{\Leftrightarrow}C\), 则\(A{\Leftrightarrow}C\).

在判定公式之间是否等价时, 可以参考一些常用的等价式. 这些常用的等价式称为命题定律.

双重否定律 (Double negation law)

\[{\lnot}{\lnot}A{\Leftrightarrow}A\]

等幂律 (Idempotent laws)

\[A{\vee}A{\Leftrightarrow}A\] \[A{\wedge}A{\Leftrightarrow}A\]

结合律 (Associative laws)

\[(A{\vee}B){\vee}C{\Leftrightarrow}A{\vee}(B{\vee}C)\] \[(A{\wedge}B){\wedge}C{\Leftrightarrow}A{\wedge}(B{\wedge}C)\]

交换律 (Commutative laws)

\[A{\vee}B{\Leftrightarrow}B{\vee}A\] \[A{\wedge}B{\Leftrightarrow}B{\wedge}A\]

分配律 (Distributive laws)

\[A{\vee}(B{\wedge}C){\Leftrightarrow}(A{\vee}B){\wedge}(A{\vee}C)\] \[A{\wedge}(B{\vee}C){\Leftrightarrow}(A{\wedge}B){\vee}(A{\wedge}C)\]

吸收律 (Absorption laws)

\[A{\vee}(A{\wedge}B){\Leftrightarrow}A\] \[A{\wedge}(A{\vee}B){\Leftrightarrow}A\]

德\(\cdot\)摩根律 (De Morgan’s laws)

\[{\lnot}(A{\wedge}B){\Leftrightarrow}{\lnot}A{\vee}{\lnot}B\] \[{\lnot}(A{\vee}B){\Leftrightarrow}{\lnot}A{\wedge}{\lnot}B\]

同一律 (Identity laws)

\[A{\vee}F{\Leftrightarrow}A\] \[A{\wedge}T{\Leftrightarrow}A\]

零律 (Domination laws)

\[A{\vee}T{\Leftrightarrow}T\] \[A{\wedge}F{\Leftrightarrow}F\]

补余律 (Negation laws)

\[A{\vee}{\lnot}A{\Leftrightarrow}T\] \[A{\wedge}{\lnot}A{\Leftrightarrow}F\]

条件转化律 (Conditionals, Material Implication)

\[A{\rightarrow}B{\Leftrightarrow}{\lnot}A{\vee}B\] \[A{\rightarrow}B{\Leftrightarrow}{\lnot}B{\rightarrow}{\lnot}A\] \[{\lnot}(A{\rightarrow}B){\Leftrightarrow}A{\wedge}{\lnot}B\]

归缪律 (Reductio ad absurdum)

\[(A{\rightarrow}B){\wedge}(A{\rightarrow}{\lnot}B){\Leftrightarrow}{\lnot}A\]

输入输出律(Exportation, Importation)

\[(A{\wedge}B){\rightarrow}C{\Leftrightarrow}A{\rightarrow}(B{\rightarrow}C)\]

双条件转化律 (Biconditionals, Material Equivalence)

\[A{\leftrightarrow}B{\Leftrightarrow}(A{\rightarrow}B){\wedge}(B{\rightarrow}A)\] \[A{\leftrightarrow}B{\Leftrightarrow}(A{\wedge}B){\vee}({\lnot}A{\wedge}{\lnot}B)\] 以上14组等价式共包括24个重要的等价式.

由于\(A\), \(B\), \(C\)可以代表任意命题公式, 因此称这些等价式为等价式模式.

每个基本等价式都可衍生出无穷多个同类型的等价式.

例: 在条件转化律\(A{\rightarrow}B{\Leftrightarrow}{\lnot}A{\vee}B\)中, 当取\(A=p, B=q\)时, 可得等价式 \[p{\rightarrow}q{\Leftrightarrow}{\lnot}p{\vee}q.\] 当取\(A=p{\vee}q\), \(B=r\)时, 可得等价式 \[(p{\vee}q){\rightarrow}r{\Leftrightarrow}{\lnot}(p{\vee}q){\vee}r.\]

 

 

命题定律均可采用真值表法加以证明.

求证: 德\(\cdot\)摩根定律\({\lnot}(p{\wedge}q){\Leftrightarrow}{\lnot}p{\vee}{\lnot}q\).

证明:

  \[ \begin{array}{ccccccc} p & q & p{\wedge}q & {\lnot}p & {\lnot}q & {\lnot}(p{\wedge}q) & {\lnot}p{\vee}{\lnot}q\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \end{array} \]  

因为\({\lnot}(p{\wedge}q)\)与\({\lnot}p{\vee}{\lnot}q\)的真值表相同, 所以两命题公式等价.

公式推演法

设\(A(p_{1}, p_{2}, {\cdots}, p_{n})\)是一个命题公式, \(p_i\)是\(A(p_{1}, p_{2}, {\cdots}, p_{n})\)中的命题变元.

用某命题公式取代\(A\)中\(p_i\)的所有出现, 由此从命题公式\(A\)得到命题公式\(B\), 称\(B\)为\(A\)的代入实例.

对命题公式: \[A(p, q)=(p{\vee}q){\rightarrow}q\]

若用\(r{\wedge}s\)取代\(q\), 可得代入实例: \[B(p, r, s)=(p{\vee}(r{\wedge}s)){\rightarrow}(r{\wedge}s).\]

定理(代入规则): 设命题公式\(A\)为永真式, 若\(B\)为\(A\)的代入实例, 则命题公式\(B\)也是永真式.

对永真式: \[(p{\rightarrow}q){\leftrightarrow}({\lnot}q{\rightarrow}{\lnot}p)\]

若用公式\(r{\wedge}s\)代换命题变元\(p\)得公式: \[((r{\wedge}s){\rightarrow}q){\leftrightarrow}({\lnot}q{\rightarrow}{\lnot}(r{\wedge}s))\] 仍是永真式.

定理(置换规则): 设\(A_{1}\)为命题公式\(A\)的子公式, \(B_{1}\)为另一命题公式.

以\(B_{1}\)取代命题公式\(A\)中的\(A_{1}\), 得命题公式\(B\). 若\(A_{1}{\Leftrightarrow}B_{1}\), 则\(A{\Leftrightarrow}B\).

对命题公式: \[(p{\rightarrow}q){\wedge}r\]

若用公式\({\lnot}p{\vee}q\)取代公式\(p{\rightarrow}q\)可得公式 \[({\lnot}p{\vee}q){\wedge}r.\] 因为: \[(p{\rightarrow}q){\Leftrightarrow}({\lnot}p{\vee}q)\] 所以: \((p{\rightarrow}q){\wedge}r{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}r.\)

有了代入规则和置换规则, 就可以利用已知等价式来推演出一些更为复杂的等价式.

这种利用已知等价式、代入规则和置换规则来推演复杂等价式的方法称为公式推演法, 又称等值演算法.

求证: \(r{\rightarrow}(p{\rightarrow}q){\Leftrightarrow}r{\rightarrow}{\lnot}(p{\wedge}{\lnot}q).\)

证明: \[r{\rightarrow}(p{\rightarrow}q){\Leftrightarrow}r{\rightarrow}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}r{\rightarrow}{\lnot}({\lnot}{\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}r{\rightarrow}{\lnot}(p{\wedge}{\lnot}q)\] 故\(r{\rightarrow}(p{\rightarrow}q){\Leftrightarrow}r{\rightarrow}{\lnot}(p{\wedge}{\lnot}q)\).

求证: \((p{\rightarrow}q){\wedge}(r{\rightarrow}q){\Leftrightarrow}(p{\vee}r){\rightarrow}q\).

证明: \[(p{\rightarrow}q){\wedge}(r{\rightarrow}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}({\lnot}r{\vee}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}r){\vee}q\] \[{\Leftrightarrow}{\lnot}(p{\vee}r){\vee}q\] \[{\Leftrightarrow}(p{\vee}r){\rightarrow}q\] 所以\((p{\rightarrow}q){\wedge}(r{\rightarrow}q){\Leftrightarrow}(p{\vee}r){\rightarrow}q\).

求证: \((p{\wedge}q){\vee}({\lnot}p{\vee}({\lnot}p{\vee}q)){\Leftrightarrow}{\lnot}p{\vee}q\).

证明: \[(p{\wedge}q){\vee}({\lnot}p{\vee}({\lnot}p{\vee}q))\] \[{\Leftrightarrow}(p{\wedge}q){\vee}(({\lnot}p{\vee}{\lnot}p){\vee}q)\] \[{\Leftrightarrow}(p{\wedge}q){\vee}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}{\lnot}p{\vee}(q{\vee}(p{\wedge}q))\] \[{\Leftrightarrow}{\lnot}p{\vee}q\]

求证: \(((p{\vee}q){\wedge}{\lnot}({\lnot}p{\wedge}({\lnot}q{\vee}{\lnot}r))){\vee}(({\lnot}p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}r)){\Leftrightarrow}T\).

证明: \[((p{\vee}q){\wedge}{\lnot}({\lnot}p{\wedge}({\lnot}q{\vee}{\lnot}r))){\vee}(({\lnot}p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}r))\] \[{\Leftrightarrow}((p{\vee}q){\wedge}{\lnot}({\lnot}p{\wedge}({\lnot}q{\vee}{\lnot}r))){\vee}({\lnot}(p{\vee}q){\vee}{\lnot}(p{\vee}r))\] \[{\Leftrightarrow}((p{\vee}q){\wedge}(p{\vee}(q{\wedge}r))){\vee}({\lnot}(p{\vee}q){\vee}{\lnot}(p{\vee}r))\]

\[{\Leftrightarrow}((p{\vee}q){\wedge}((p{\vee}q){\wedge}(p{\vee}r))){\vee}({\lnot}(p{\vee}q){\vee}{\lnot}(p{\vee}r))\] \[{\Leftrightarrow}((p{\vee}q){\wedge}((p{\vee}q){\wedge}(p{\vee}r))){\vee}{\lnot}((p{\vee}q){\wedge}(p{\vee}r))\] \[{\Leftrightarrow}(((p{\vee}q){\wedge}(p{\vee}q)){\wedge}(p{\vee}r)){\vee}{\lnot}((p{\vee}q){\wedge}(p{\vee}r))\] \[{\Leftrightarrow}((p{\vee}q){\wedge}(p{\vee}r)){\vee}{\lnot}((p{\vee}q){\wedge}(p{\vee}r))\] \[{\Leftrightarrow}T\]

一个小学生考试后回家跟他的爸爸, 妈妈和阿姨说:“我今天数学, 语文考试的成绩都排在班级前三名”, 他让三人猜猜他具体排在第几名.三人猜测结果如下:

  • 爸爸:数学第一, 语文第三;

  • 妈妈:数学第二, 语文第三;

  • 阿姨:数学第一, 语文第二.

听完猜测后, 小学生不紧不慢地说:“你们有一人说的全对, 另两人各说对了一个”, 试用推演法分析小学生的两科成绩排名.

解: 设命题

  • \(p\): 数学第一;

  • \(q\): 数学第二;

  • \(r\): 语文第二;

  • \(s\): 语文第三.

\(p, q, r, s\)中必有两个真命题, 两个假命题.设:

  • 爸爸的判断为:\(A_{1}=p{\wedge}s\)

  • 妈妈的判断为:\(A_{2}=q{\wedge}s\)

  • 阿姨的判断为:\(A_{3}=p{\wedge}r\)

爸爸的判断全对:\(B_{1}=p{\wedge}s\)

爸爸的判断对一个:\(B_{2}=(p{\wedge}{\lnot}s){\vee}({\lnot}p{\wedge}s)\)

妈妈的判断全对:\(C_{1}=q{\wedge}s\)

妈妈的判断对一个:\(C_{2}=(q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s)\)

阿姨的判断全对:\(D_{1}=p{\wedge}r\)

阿姨的判断对一个:\(D_{2}=(p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r)\)

于是,

\[Z=(B_{1}{\wedge}C_{2}{\wedge}D_{2}){\vee}(C_{1}{\wedge}B_{2}{\wedge}D_{2}){\vee}(D_{1}{\wedge}B_{2}{\wedge}C_{2})\] 为真命题.

而: \[B_{1}{\wedge}C_{2}{\wedge}D_{2}\] \[{\Leftrightarrow}(p{\wedge}s){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}((p{\wedge}s{\wedge}q{\wedge}{\lnot}s){\vee}(p{\wedge}s{\wedge}{\lnot}q{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(F{\vee}(p{\wedge}{\lnot}q{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}s){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}s{\wedge}p{\wedge}{\lnot}r){\vee}(p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}p{\wedge}r)\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}r){\vee}F\] \[{\Leftrightarrow}p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}r\]

\[C_1{\wedge}B_2{\wedge}D_2\] \[{\Leftrightarrow}(q{\wedge}s){\wedge}((p{\wedge}{\lnot}s){\vee}({\lnot}p{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}((q{\wedge}s{\wedge}p{\wedge}{\lnot}s){\vee}(q{\wedge}s{\wedge}{\lnot}p{\wedge}s)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(F{\vee}(q{\wedge}s{\wedge}{\lnot}p)){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\] \[{\Leftrightarrow}(q{\wedge}s{\wedge}{\lnot}p){\wedge}((p{\wedge}{\lnot}r){\vee}({\lnot}p{\wedge}r))\]

\[{\Leftrightarrow}(q{\wedge}s{\wedge}{\lnot}p{\wedge}p{\wedge}{\lnot}r){\vee}(q{\wedge}s{\wedge}{\lnot}p{\wedge}{\lnot}p{\wedge}r)\] \[{\Leftrightarrow}F{\vee}(q{\wedge}s{\wedge}{\lnot}p{\wedge}r)\] \[{\Leftrightarrow}q{\wedge}s{\wedge}{\lnot}p{\wedge}r\]

语文排名不能既是第二名又是第三名, 所以\(r, s\)必有一个 假命题, 即:

 

\[q{\wedge}s{\wedge}{\lnot}p{\wedge}r{\Leftrightarrow}F.\]

\[D_{1}{\wedge}B_{2}{\wedge}C_{2}\] \[{\Leftrightarrow}(p{\wedge}r){\wedge}((p{\wedge}{\lnot}s){\vee}({\lnot}p{\wedge}s)){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s))\] \[{\Leftrightarrow}((p{\wedge}r{\wedge}p{\wedge}{\lnot}s){\vee}(p{\wedge}r{\wedge}{\lnot}p{\wedge}s)){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s))\] \[{\Leftrightarrow}((p{\wedge}r{\wedge}{\lnot}s){\vee}F){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s))\]

\[{\Leftrightarrow}(p{\wedge}r{\wedge}{\lnot}s){\wedge}((q{\wedge}{\lnot}s){\vee}({\lnot}q{\wedge}s))\] \[{\Leftrightarrow}(p{\wedge}r{\wedge}{\lnot}s{\wedge}q{\wedge}{\lnot}s){\vee}(p{\wedge}r{\wedge}{\lnot}s{\wedge}{\lnot}q{\wedge}s)\] \[{\Leftrightarrow}(p{\wedge}r{\wedge}{\lnot}s{\wedge}q){\vee}F\] \[{\Leftrightarrow}p{\wedge}r{\wedge}{\lnot}s{\wedge}q\]

数学排名不能既是第一名又是第二名, 所以\(p, q\)必有一个假命题, 即:

 

\[p{\wedge}r{\wedge}{\lnot}s{\wedge}q{\Leftrightarrow}F.\]

所以 \[Z=(B_{1}{\wedge}C_{2}{\wedge}D_{2}){\vee}(C_{1}{\wedge}B_{2}{\wedge}D_{2}){\vee}(D_{1}{\wedge}B_{2}{\wedge}C_{2})\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}r){\vee}F{\vee}F\] \[{\Leftrightarrow}p{\wedge}{\lnot}q{\wedge}s{\wedge}{\lnot}r\]

 

为真命题, 即: 小学生的数学排名第一, 语文排名第三.

永真蕴含式

给定命题公式\(A{\rightarrow}B\),

称命题公式\(B{\rightarrow}A\)为它的逆换式.

命题公式\({\lnot}A{\rightarrow}{\lnot}B\)为它的反换式.

命题公式\({\lnot}B{\rightarrow}{\lnot}A\)为它的逆反式.

这四个命题公式有如下的关系: \[A{\rightarrow}B{\Leftrightarrow}{\lnot}B{\rightarrow}{\lnot}A, \]

\[B{\rightarrow}A{\Leftrightarrow}{\lnot}A{\rightarrow}{\lnot}B\]

设\(A, B\)为两个命题公式, 若\(A{\rightarrow}B\)是永真式, 即\(A{\rightarrow}B{\Leftrightarrow}T\), 则称\(A{\rightarrow}B\)为永真蕴含式. 也称命题公式\(A\)永真蕴含命题公式\(B\), 记作\(A{\Rightarrow}B.\)

符号”\({\Rightarrow}\)“和”\({\rightarrow}\)“的区别和联系:

  • “\({\Rightarrow}\)”不是联结词, “\(A{\Rightarrow}B\)”不是公式, 它表示公式\(A\)与\(B\)之间存在永真蕴含关系.

  • “\({\rightarrow}\)”是联结词, \(A{\rightarrow}B\)是一个公式.

  • \(A{\Rightarrow}B\)当且仅当\(A{\rightarrow}B\)是永真式.

证明\(A{\Rightarrow}B\)可采用以下几种方法:

  1. 真值表法: 使用真值表法证明\(A{\Rightarrow}B\), 即通过真值表证明\(A{\rightarrow}B\)为永真式.

  2. 前件真推证后件真方法: 设\(A\)为真, 若能推证\(B\)为\(T\), 则\(A{\rightarrow}B\)为永真式, 即\(A{\Rightarrow}B\).

  3. 后件假推证前件假方法: 设\(B\)为\(F\), 若能推证\(A\)为\(F\), 则\(A{\rightarrow}B\)为永真式, 即\(A{\Rightarrow}B\).

  4. 公式推演法.

求证: \({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p\).

证明: (真值表法)

欲证明\({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p\), 则要证明命题公式\(({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p\)为永真式.

计算\(({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p\)的真值表:

 

\[ \begin{array}{cccccc} p & q & {\lnot}q & p{\rightarrow}q & {\lnot}q{\wedge}(p{\rightarrow}q) & {\lnot}q{\wedge}(p{\rightarrow}q){\rightarrow}{\lnot}p \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 1 & 0 & 1 \\ \end{array} \]

 

因为\(({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p\)为永真式, 所以\({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p.\)

(前件真推证后件真方法) \[({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p)\]

 

假定前件: \({\lnot}q{\wedge}(p{\rightarrow}q)\)为\(T\), 则有\({\lnot}q, p{\rightarrow}q\)均为\(T\)

从而有\(q\)为\(F\). 又因\(p{\rightarrow}q\)为\(T\), 必有\(p\)为\(F\), 故\({\lnot}p\)为\(T\).

所以\[{\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p.\]

(后件假推证前件假方法) \[({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p)\]

 

假定后件: \({\lnot}p\)为\(F\), 则有: \(p\)为\(T\).

若\(q\)为\(T\), 则\({\lnot}q\)为\(F\), 从而\({\lnot}q{\wedge}(p{\rightarrow}q)\)为\(F\); 若\(q\)为\(F\), 因\(p\)为\(T\), 故\(p{\rightarrow}q\)为\(F\).

于是, \({\lnot}q{\wedge}(p{\rightarrow}q)\)为\(F\). 因此\[{\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p.\]

求证: \({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q\).

证明: (真值表法)

欲证\({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q\), 则需证\(({\lnot}p{\wedge}(p{\vee}q)){\rightarrow}q\)为永真式.

计算\(({\lnot}p{\wedge}(p{\vee}q)){\rightarrow}q\)的真值表.

 

\[ \begin{array}{cccccc} p & q & {\lnot}p & p{\vee}q & {\lnot}p{\wedge}(p{\vee}q) & {\lnot}p{\wedge}(p{\vee}q){\rightarrow}q \\ 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 \\ \end{array} \]

 

因为\({\lnot}p{\wedge}(p{\vee}q){\rightarrow}q\)为永真式.所以\({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q.\)

(前件真推证后件真方法) \[({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q)\] 假设前件\({\lnot}p{\wedge}(p{\vee}q)\)为\(T\), 则有\({\lnot}p, p{\vee}q\)均为\(T\).

从而有\(p\)为\(F\), 故\(q\)为\(T\).

所以\[{\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q.\]

(后件假推证前件假方法) \[({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q)\] 假定后件\(q\)为\(F\),

  • 若\(p\)为\(T\), 则\({\lnot}p\)为\(F\), 于是\({\lnot}p{\wedge}(p{\vee}q)\)为\(F\);

  • 若\(p\)为\(F\), \(p{\vee}q\)为\(F\), 于是\({\lnot}p{\wedge}(p{\vee}q)\)为\(F\).

因此\[{\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q\]

设\(A\), \(B\), \(C\)和\(D\)是命题公式, 以下给出9组基本蕴含式.

这些蕴含式均可采用上述方法给出证明, 利用这些蕴涵式通过公式推演法可证明其它更为复杂的蕴含式.

 

化简式 (Simplification)

\[A{\wedge}B{\Rightarrow}A\] \[A{\wedge}B{\Rightarrow}B\]

附加式 (Addition)

\[A{\Rightarrow}A{\vee}B\] \[B{\Rightarrow}A{\vee}B\]

假言推理 (Modus ponens)

\[A{\wedge}(A{\rightarrow}B){\Rightarrow}B\]

拒取式 (Modus tollens)

\[{\lnot}B{\wedge}(A{\rightarrow}B){\Rightarrow}{\lnot}A\]

析取三段论 (Disjunctive syllogism)

\[{\lnot}A{\wedge}(A{\vee}B){\Rightarrow}B\]

假言三段论 (Hypothetical syllogism)

\[(A{\rightarrow}B){\wedge}(B{\rightarrow}C){\Rightarrow}(A{\rightarrow}C)\]

双条件三段论

\[(A{\leftrightarrow}B){\wedge}(B{\leftrightarrow}C){\Rightarrow}(A{\leftrightarrow}C)\]

构造性二难 (Constructive dilemma)

\[(A{\rightarrow}B){\wedge}(C{\rightarrow}D){\wedge}(A{\wedge}C){\Rightarrow}B{\wedge}D\] \[(A{\rightarrow}B){\wedge}(C{\rightarrow}D){\wedge}(A{\vee}C){\Rightarrow}B{\vee}D\]

二难推论 (Disjunction elimination)

\[(A{\rightarrow}B){\wedge}(C{\rightarrow}B){\wedge}(A{\wedge}C){\Rightarrow}B\] \[(A{\rightarrow}B){\wedge}(C{\rightarrow}B){\wedge}(A{\vee}C){\Rightarrow}B\]

 

以上9组基本蕴含式共包括13个重要的蕴含式, 由于\(A\), \(B\), \(C\)和\(D\)可以代表任意命题公式, 因此称这些蕴含式为永真蕴含式模式. 每个基本蕴含式都可衍生出无穷多个同类型的蕴含式.

在假言推理\(A{\wedge}(A{\rightarrow}B){\Rightarrow}B\)中, 当取\(A=p, B=q\)时, 得蕴涵式\(p{\wedge}(p{\rightarrow}q){\Rightarrow}q;\) 当取\(A=p{\rightarrow}q\), \(B=r\)时, 得蕴含式\((p{\rightarrow}q){\wedge}((p{\rightarrow}q){\rightarrow}r){\Rightarrow}r\).

求证: \({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p\).

证明: (证法一) \[{\lnot}q{\wedge}(p{\rightarrow}q)\] \[{\Leftrightarrow}{\lnot}q{\wedge}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}({\lnot}q{\wedge}{\lnot}p){\vee}({\lnot}q{\wedge}q)\] \[{\Leftrightarrow}({\lnot}q{\wedge}{\lnot}p){\vee}F\] \[{\Leftrightarrow}{\lnot}q{\wedge}{\lnot}p\] \[{\Rightarrow}{\lnot}p\] 因此\[{\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p.\]

(证法二) 对\({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p\), 仅需证\(({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p\)为永真蕴含式.

\[({\lnot}q{\wedge}(p{\rightarrow}q)){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}({\lnot}q{\wedge}({\lnot}p{\vee}q)){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}(({\lnot}q{\wedge}{\lnot}p){\vee}({\lnot}q{\wedge}q)){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}(({\lnot}q{\wedge}{\lnot}p){\vee}F){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}({\lnot}q{\wedge}{\lnot}p){\rightarrow}{\lnot}p\] \[{\Leftrightarrow}{\lnot}({\lnot}q{\wedge}{\lnot}p){\vee}{\lnot}p\] \[{\Leftrightarrow}(q{\vee}p){\vee}{\lnot}p\] \[{\Leftrightarrow}T\] 因此, \({\lnot}q{\wedge}(p{\rightarrow}q){\Rightarrow}{\lnot}p.\)

求证: \({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q\).

证明: \[{\lnot}p{\wedge}(p{\vee}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}p){\vee}({\lnot}p{\wedge}q)\] \[{\Leftrightarrow}F{\vee}({\lnot}p{\wedge}q)\] \[{\Leftrightarrow}{\lnot}p{\wedge}q\] \[{\Rightarrow}q\] 因此, \({\lnot}p{\wedge}(p{\vee}q){\Rightarrow}q\).

求证: \(p{\wedge}q{\Rightarrow}p{\rightarrow}q\).

证明: \[p{\wedge}q\] \[{\Rightarrow}q\] \[{\Rightarrow}{\lnot}p{\vee}q\] \[{\Leftrightarrow}p{\rightarrow}q\] 因此, \(p{\wedge}q{\Rightarrow}p{\rightarrow}q\).

定理: 设\(A\)和\(B\)为命题公式, \(A{\Leftrightarrow}B\)的充分必要条件是\(A{\Rightarrow}B\)且\(B{\Rightarrow}A.\)

证明:

(必要性)设\(A{\Leftrightarrow}B\), 那么\(A{\leftrightarrow}B\)为永真式.

由于\(A{\leftrightarrow}B{\Leftrightarrow}(A{\rightarrow}B){\wedge}(B{\rightarrow}A)\), 故\(A{\rightarrow}B\)永真且\(B{\rightarrow}A\)永真, 即\(A{\Rightarrow}B\)且\(B{\Rightarrow}A\).

(充分性)设\(A{\Rightarrow}B\)且\(B{\Rightarrow}A\), 则\(A{\rightarrow}B\)永真且\(B{\rightarrow}A\)永真.

由于\(A{\leftrightarrow}B{\Leftrightarrow}(A{\rightarrow}B){\wedge}(B{\rightarrow}A)\), 故\(A{\leftrightarrow}B\)为永真式, 即\(A{\Leftrightarrow}B.\)

蕴含式有以下性质:

  1. 设\(A\), \(B\)为任意两个命题公式, 若\(A{\Rightarrow}B\)且\(A\)为永真式, 则\(B\)必为永真式.

  2. 自反性. 对任意命题公式\(A\), 有\(A{\Rightarrow}A\).

  3. 传递性. 对任意命题公式\(A\), \(B\)和\(C\), 若\(A{\Rightarrow}B\), \(B{\Rightarrow}C\), 则\(A{\Rightarrow}C\).

  4. 对任意命题公式\(A\), \(B\)和\(C\), 若\(A{\Rightarrow}B, A{\Rightarrow}C\), 则\(A{\Rightarrow}(B{\wedge}C)\).

  5. 对任意命题公式\(A\), \(B\)和\(C\), 若\(A{\Rightarrow}C, B{\Rightarrow}C\), 则\((A{\vee}B){\Rightarrow}C\).

联结词的完备集

虽然联结词\({\lnot}\), \({\wedge}\), \({\vee}\), \({\rightarrow}\)和\({\leftrightarrow}\)可以表示命题之间的任何关系, 可以等值表示任何命题公式, 但有时候不够简洁. 为此再定义4个联结词以作补充.

1.异或联结词

设\(p\)和\(q\)为命题, 复合命题“\(p\)或\(q\)有且仅有一个成立”称为\(p\)和\(q\)的异或式复合命题, 记作\(p{\oplus}q\) (或\({\nleftrightarrow}\)). 符号\({\oplus}\)称为异或联结词(不可兼析取联结词).

复合命题\(p{\oplus}q\)的真值由下表给出. \(p{\oplus}q\)真值为真当且仅当\(p\), \(q\)有且仅有一个为真.

  \[ \begin{array}{ccc} p & q & p{\oplus}q \\ 0 & 0 & 0 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \]

例:

  1. 他明天或者后天去百货商店.

设\(p\): 他明天去百货商店, \(q\): 他后天去百货商店, 于是(1)可符号化为\(p{\oplus}q\).

  1. 他如今不是在上海就是在杭州.

设\(p\): 他如今在上海, \(q\): 他如今在杭州, 于是(2)可符号化为\(p{\oplus}q\).

 

由异或联结词的定义可知:\[p{\oplus}q{\Leftrightarrow}{\lnot}(p{\leftrightarrow}q).\]

异或联结词有以下性质:

  1. \(p{\oplus}q{\Leftrightarrow}q{\oplus}p\)

  2. \((p{\oplus}q){\oplus}r{\Leftrightarrow}p{\oplus}(q{\oplus}r)\)

  3. \(p{\wedge}(q{\oplus}r){\Leftrightarrow}(p{\wedge}q){\oplus}(p{\wedge}r)\)

  4. \(p{\oplus}q{\Leftrightarrow}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}q)\)

  5. \((p{\oplus}q){\Leftrightarrow}{\lnot}(p{\leftrightarrow}q)\)

2.条件非联结词

设\(p\)和\(q\)为命题, 复合命题“如果\(p\)则\(q\)的否定”称为\(p\)和\(q\)的条件非式复合命题, 记作\(p{\nrightarrow}q\). 符号\({\nrightarrow}\)称为条件非联结词.

复合命题\(p{\nrightarrow}q\)的真值由下表给出.\(p{\nrightarrow}q\)真值为真当且仅当时\(p\)为真, \(q\)为假.

  \[ \begin{array}{ccc} p & q & p{\nrightarrow}q \\ 0 & 0 & 0 \\ 0 & 1 & 0 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \]  

由条件非联结词的定义可知:\[p{\nrightarrow}q{\Leftrightarrow}{\lnot}(p{\rightarrow}q).\]

3.与非联结词

设\(p\)和\(q\)为命题, 复合命题“\(p\)与\(q\)的否定”称为\(p\)和\(q\)的与非式复合命题, 记作\(p{\uparrow}q\). 符号\({\uparrow}\)称为与非联结词.

复合命题\(p{\uparrow}q\)的真值由下表给出. \(p{\uparrow}q\)的真值为真当且仅当\(p\), \(q\)不同时为真.

  \[ \begin{array}{ccc} p & q & p{\uparrow}q \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \\ \end{array} \]  

由与非联结词的定义可知:\[p{\uparrow}q{\Leftrightarrow}{\lnot}(p{\wedge}q).\]

与非联结词有如下性质:

  1. \(p{\uparrow}p{\Leftrightarrow}{\lnot}(p{\wedge}p){\Leftrightarrow}{\lnot}p\)

  2. \(p{\uparrow}q{\Leftrightarrow}q{\uparrow}p\)

  3. \((p{\uparrow}q){\uparrow}(p{\uparrow}q){\Leftrightarrow}{\lnot}(p{\uparrow}q){\Leftrightarrow}p{\wedge}q\)

  4. \((p{\uparrow}p){\uparrow}(q{\uparrow}q){\Leftrightarrow}{\lnot}p{\uparrow}{\lnot}q{\Leftrightarrow}p{\vee}q\)

4.或非联结词

设\(p\)和\(q\)为命题, 复合命题”\(p\)或\(q\)的否定”称为\(p\)和\(q\)的或非式复合命题, 记作\(p{\downarrow}q\). 符号\({\downarrow}\)称为或非联结词.

复合命题\(p{\downarrow}q\)的真值由下表给出. 复合命题\(p{\downarrow}q\)取值为真当且仅当\(p\), \(q\)同时为假.

  \[ \begin{array}{ccc} p & q & p{\downarrow}q \\ 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ 1 & 1 & 0 \\ \end{array} \]  

由或非联结词的定义可知: \[p{\downarrow}q{\Leftrightarrow}{\lnot}(p{\vee}q).\]

或非联结词有如下性质:

  1. \(p{\downarrow}p{\Leftrightarrow}{\lnot}(p{\vee}p){\Leftrightarrow}{\lnot}p\)

  2. \(p{\downarrow}q{\Leftrightarrow}q{\downarrow}p\)

  3. \((p{\downarrow}q){\downarrow}(p{\downarrow}q){\Leftrightarrow}{\lnot}(p{\downarrow}q){\Leftrightarrow}p{\vee}q\)

  4. \((p{\downarrow}p){\downarrow}(q{\downarrow}q){\Leftrightarrow}{\lnot}p{\downarrow}{\lnot}q{\Leftrightarrow}p{\wedge}q\)

至此, 已介绍了九个联结词.

联结词完备集(全功能联结词集)

设有一个联结词集合\(S\), 若由\(S\)中联结词构成的命题公式能表示任何命题公式, 则称\(S\)是联结词完备集.

例: {\(\lnot\), \(\wedge\), \(\vee\), \(\rightarrow\), \(\leftrightarrow\), \(\oplus\), \(\uparrow\), \(\downarrow\), \(\nrightarrow\)}是联结词完备集.

判断一个联结词集是否为联结词完备集, 只需看该联结词集中的联结词能否取代一个联结词完备集中的所有联结词.

求证: {\({\lnot}\), \({\wedge}\), \({\vee}\), \({\rightarrow}\), \({\leftrightarrow}\)}是联结词完备集.

证明: 由于{\({\lnot}\), \({\wedge}\), \({\vee}\), \({\rightarrow}\), \({\leftrightarrow}\), \({\oplus}\), \({\uparrow}\), \({\downarrow}\), \({\nrightarrow}\)}是联结词完备集, 而: \[p{\oplus}q{\Leftrightarrow}{\lnot}(p{\leftrightarrow}q)\] \[p{\uparrow}q{\Leftrightarrow}{\lnot}(p{\wedge}q)\] \[p{\downarrow}q{\Leftrightarrow}{\lnot}(p{\vee}q)\] \[p{\nrightarrow}q{\Leftrightarrow}{\lnot}(p{\rightarrow}q)\] 故\({\oplus}, {\uparrow}, {\downarrow}\)和\({\nrightarrow}\)这四个联结词完全可以由\({\lnot}, {\wedge}, {\vee}, {\rightarrow}\)和\({\leftrightarrow}\)这五个联结词来取代.

可见, {\({\lnot}, {\wedge}, {\vee}, {\rightarrow}, {\leftrightarrow}\)}是联结词完备集.

 

{\({\lnot}, {\wedge}, {\vee}\)}, {\({\lnot}, {\wedge}\)}, {\({\lnot}, {\vee}\)}也是联结词完备集.

求证: {\({\lnot}, {\wedge}, {\vee}\)}是联结词完备集.

证明: 由于{\({\lnot}, {\wedge}, {\vee}, {\rightarrow}, {\leftrightarrow}\)}是联结词完备集, 而: \[p{\rightarrow}q{\Leftrightarrow}{\lnot}p{\vee}q\] \[p{\leftrightarrow}q{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}{\lnot}q)\] 故\({\rightarrow}\), \({\leftrightarrow}\)这两个联结词可以由\({\lnot}\), \({\wedge}\)和\({\vee}\)这三个联结词来取代.

于是, {\({\lnot}\), \({\wedge}\), \({\vee}\)}也是联结词完备集.

在联结词集中, 如果一个联结词可以由该集合中其他联结词定义, 则此联结词称为冗余联结词. 否则称为独立联结词.

联结词集{\({\lnot}\), \({\wedge}\), \({\vee}\)}中, {\(\vee\)}是冗余联结词, 因为: \[p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q).\]

设有一个联结词完备集\(S\), 若\(S\)中不含冗余联结词, 则称\(S\)是极小联结词完备集.

求证: {\({\lnot}, {\vee}\)}是极小联结词完备集.

证明: 由于{\({\lnot}, {\wedge}, {\vee}\)}是联结词完备集, 而: \[p{\wedge}q{\Leftrightarrow}{\lnot}({\lnot}p{\vee}{\lnot}q)\] 所以, {\({\lnot}, {\vee}\)}是联结词完备集.

从命题定律可知包含二元联结词的命题公式不能用仅包含一元联结词的命题公式等值取代, \({\vee}\)是二元联结词, \({\lnot}\)是一元联结词, 相互之间不能取代, 所以{\({\lnot}, {\vee}\)}是极小全功能联结词集.

{\({\lnot}, {\wedge}\)}, {\({\lnot}, {\rightarrow}\)}, {\({\uparrow}\)}和{\({\downarrow}\)}也都是极小联结词完备集.

求证: {\({\uparrow}\)}是极小联结词完备集.

证明: 由于{\({\lnot}, {\vee}\)}是极小联结词完备集, 而: \[{\lnot}p{\Leftrightarrow}{\lnot}(p{\wedge}p){\Leftrightarrow}(p{\uparrow}p)\] \[p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q){\Leftrightarrow}{\lnot}p{\uparrow}{\lnot}q{\Leftrightarrow}(p{\uparrow}p){\uparrow}(q{\uparrow}q)\] 所以, {\({\uparrow}\)}也是极小联结词完备集.

\[{\lnot}p{\Leftrightarrow}{\lnot}(p{\wedge}p){\Leftrightarrow}p{\uparrow}p\] \[p{\wedge}q{\Leftrightarrow}{\lnot}(p{\uparrow}q){\Leftrightarrow}(p{\uparrow}q){\uparrow}(p{\uparrow}q)\] \[p{\vee}q{\Leftrightarrow}{\lnot}({\lnot}p{\wedge}{\lnot}q){\Leftrightarrow}({\lnot}p){\uparrow}({\lnot}q){\Leftrightarrow}(p{\uparrow}p){\uparrow}(q{\uparrow}q)\] \[p{\rightarrow}q{\Leftrightarrow}((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q)\] \[p{\leftrightarrow}q{\Leftrightarrow}((((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q))\] \[{\uparrow}(((q{\uparrow}q){\uparrow}(q{\uparrow}q)){\uparrow}(p{\uparrow}p))){\uparrow}\] \[((((p{\uparrow}p){\uparrow}(p{\uparrow}p)){\uparrow}(q{\uparrow}q))\] \[{\uparrow}(((q{\uparrow}q){\uparrow}(q{\uparrow}q)){\uparrow}(p{\uparrow}p)))\]

试将命题公式\({\lnot}p{\vee}(q{\rightarrow}r)\)用仅含有联结词\({\lnot}\)和\({\wedge}\)的等价式表示.

解: \[{\lnot}p{\vee}(q{\rightarrow}r){\Leftrightarrow}{\lnot}p{\vee}({\lnot}q{\vee}r)\] \[{\Leftrightarrow}{\lnot}p{\vee}{\lnot}(q{\wedge}{\lnot}r)\] \[{\Leftrightarrow}{\lnot}(p{\wedge}(q{\wedge}{\lnot}r))\]

对偶式

在给定仅含联结词\({\lnot}\), \({\wedge}\)和\({\vee}\)的命题公式\(A\)中, 将联结词\({\vee}\)换成\({\wedge}\), \({\wedge}\)换成\({\vee}\), 特殊变元\(T\)换成\(F\), \(F\)换成\(T\), 由此得到命题公式\(A^*\), 称\(A^*\)为\(A\)的对偶式.

从定义不难看出, \(A\)也是\(A^*\)的对偶式, 即对偶式是相互的, \((A^*)^*＝A\).

 

试给出下列命题公式的对偶式:

  1. \(p{\wedge}q\)

  2. \({\lnot}(p{\vee}q){\wedge}T\)

解:

  1. 对偶式为\(p{\vee}q\).

  2. 对偶式为\({\lnot}(p{\wedge}q){\vee}F\).

如果命题公式A除了包含\({\lnot}, {\wedge}, {\vee}\)联结词之外, 还包含\({\rightarrow}, {\leftrightarrow}, {\uparrow}, {\downarrow}\)等联结词, 则先将A转化成只包含\({\lnot}, {\wedge}, {\vee}\)的命题公式, 然后再求它的对偶式\(A^*\).

求命题公式\(A=r{\rightarrow}(p{\wedge}(p{\leftrightarrow}q))\)的对偶式.

解: \[A{\Leftrightarrow}r{\rightarrow}(p{\wedge}(p{\rightarrow}q){\wedge}(q{\rightarrow}p))\] \[{\Leftrightarrow}r{\rightarrow}(p{\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}q{\vee}p))\] \[{\Leftrightarrow}{\lnot}r{\vee}(p{\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}q{\vee}p)\] 所以\[A^*={\lnot}r{\wedge}(p{\vee}({\lnot}p{\wedge}q){\vee}({\lnot}q{\wedge}p).\]

试求\(p{\uparrow}q\)和\(p{\downarrow}q\)的对偶式.

解: \[p{\uparrow}q{\Leftrightarrow}{\lnot}(p{\wedge}q)\]

而\({\lnot}(p{\wedge}q)\)的对偶式为\({\lnot}(p{\vee}q)\), 所以\(p{\uparrow}q\)的对偶式为\({\lnot}(p{\vee}q)\).

又\[{\lnot}(p{\vee}q){\Leftrightarrow}p{\downarrow}q\]

故\(p{\uparrow}q\)的对偶式也就是\(p{\downarrow}q\),

也就是说, \(p{\downarrow}q\)与\(p{\uparrow}q\)互为对偶式.

定理: 设\(A\)和\(A^*\)是对偶式, \(p_{1}, p_{2}, {\cdots}, p_{n}\)是出现在\(A\)和\(A^*\)中的所有命题变元, 则有:

  1. \({\lnot}A(p_{1}, p_{2}, {\cdots}, p_{n}){\Leftrightarrow}A^*({\lnot}p_{1}, {\lnot}p_{2}, {\cdots}, {\lnot}p_{n})\)

  2. \(A({\lnot}p_{1}, {\lnot}p_{2}, {\cdots}, {\lnot}p_{n}){\Leftrightarrow}{\lnot}A^*(p_{1}, p_{2}, {\cdots}, p_{n})\)

设\(A(p, q, r)={\lnot}p{\vee}({\lnot}q{\wedge}r)\), 求证: \[{\lnot}A(p, q, r){\Leftrightarrow}A^*({\lnot}p, {\lnot}q, {\lnot}r), \, \, \, \, \, \, \, A({\lnot}p, {\lnot}q, {\lnot}r){\Leftrightarrow}{\lnot}A^*(p, q, r).\]

证明: \[A^*({\lnot}p, {\lnot}q, {\lnot}r)={\lnot}{\lnot}p{\wedge}({\lnot}{\lnot}q{\vee}{\lnot}r) \, {\Leftrightarrow}\, p{\wedge}(q{\vee}{\lnot}r)\] \[{\lnot}A(p, q, r)={\lnot}({\lnot}p{\vee}({\lnot}q{\wedge}r))\, {\Leftrightarrow}\, {\lnot}{\lnot}p{\wedge}{\lnot}({\lnot}q{\wedge}r)\, {\Leftrightarrow}\, p{\wedge}(q{\vee}{\lnot}r)\] 所以, \({\lnot}A(p, q, r){\Leftrightarrow}A^*({\lnot}p, {\lnot}q, {\lnot}r)\).

同理, \[A({\lnot}p, {\lnot}q, {\lnot}r)={\lnot}{\lnot}p{\vee}({\lnot}{\lnot}q{\wedge}{\lnot}r)\, {\Leftrightarrow}\, p{\vee}(q{\wedge}{\lnot}r)\] \[{\lnot}A^*(p, q, r)={\lnot}({\lnot}p{\wedge}({\lnot}q{\vee}r))\, {\Leftrightarrow}\, p{\vee}(q{\wedge}{\lnot}r)\] 所以, \(A({\lnot}p, {\lnot}q, {\lnot}r){\Leftrightarrow}{\lnot}A^*(p, q, r).\)

定理(对偶原理, Duality Principle): 设\(p_{1}, p_{2}, {\cdots}, p_{n}\)是出现在命题公式\(A\)和\(B\)中的所有命题变元, 若\(A{\Leftrightarrow}B\), 则\(A^*{\Leftrightarrow}B^*\).

由对偶原理可知:

  1. 若\(A\)为永真式, 则\(A^*\)必为永假式;

  2. 对命题公式\(A\)和\(B\), 若\(A{\Rightarrow}B\), 则\(B^*{\Rightarrow}A^*\);

  3. 已知\(A{\Leftrightarrow}B\), 且\(B\)是比\(A\)简单的命题公式, 则由对偶原理可直接求出较简单的\(B^*\), 且\(B^*\)与\(A^*\)等值.

设\(A=p{\vee}({\lnot}p{\vee}(q{\wedge}{\lnot}q))\), 则\(A^*=p{\wedge}({\lnot}p{\wedge}(q{\vee}{\lnot}q))\)

因为\[A{\Leftrightarrow}p{\vee}({\lnot}p{\vee}F){\Leftrightarrow}p{\vee}{\lnot}p{\Leftrightarrow}T\]

所以\[A^*{\Leftrightarrow}F\]

(实际上, \(A^*=p{\wedge}({\lnot}p{\wedge}T){\Leftrightarrow}p{\wedge}{\lnot}p{\Leftrightarrow}F\))

设\(A=p{\wedge}q\), \(B=p\), 则\(A^*=p{\vee}q, B^*=p\).

因为\[p{\wedge}q{\Rightarrow}p\, (A{\Rightarrow}B)\] \[p{\Rightarrow}p{\vee}q\, (B^*{\Rightarrow}A^*)\]

可见:\[A{\Rightarrow}B, \, \, \, \, B^*{\Rightarrow}A^*\]

求证:

  1. \((p{\wedge}q){\vee}({\lnot}p{\vee}q){\Leftrightarrow}{\lnot}p{\vee}q\)

  2. \((p{\vee}q){\wedge}({\lnot}p{\wedge}q){\Leftrightarrow}{\lnot}p{\wedge}q\)

证明: (1)

\[(p{\wedge}q){\vee}({\lnot}p{\vee}q){\Leftrightarrow}(p{\vee}({\lnot}p{\vee}q)){\wedge}(q{\vee}({\lnot}p{\vee}q))\] \[{\Leftrightarrow}(p{\vee}{\lnot}p{\vee}q){\wedge}(q{\vee}{\lnot}p{\vee}q){\Leftrightarrow}T{\wedge}({\lnot}p{\vee}q){\Leftrightarrow}{\lnot}p{\vee}q\]

\((p{\wedge}q){\vee}({\lnot}p{\vee}q)\)的对偶式为\((p{\vee}q){\wedge}({\lnot}p{\wedge}q)\), \({\lnot}p{\vee}q\)的对偶式为\({\lnot}p{\wedge}q.\)

由(1)式: \((p{\wedge}q){\vee}({\lnot}p{\vee}q){\Leftrightarrow}{\lnot}p{\vee}q\), 可证(2): \((p{\vee}q){\wedge}({\lnot}p{\wedge}q){\Leftrightarrow}{\lnot}p{\wedge}q\).

范式

定义: 由有限个命题变元或命题变元否定所组成的合取式称为简单合取式(基本积), 每个命题变元或命题变元否定称为合取项.

例: \(p\), \({\lnot}p\), \(q\), \({\lnot}q\), \(p{\wedge}q\), \(p{\wedge}{\lnot}q\), \({\lnot}p{\wedge}q\), \({\lnot}p{\wedge}{\lnot}q\), \(p{\wedge}q{\wedge}r\), \(p{\wedge}q{\wedge}{\lnot}r\)等都是基本积.

定义: 由有限个命题变元或命题变元否定所组成的析取式称为简单析取式(基本和), 每个命题变元或命题变元否定称为析取项.

例: \(p\), \({\lnot}p\), \(q\), \({\lnot}q\), \(p{\vee}q\), \(p{\vee}{\lnot}q\), \({\lnot}p{\vee}q\), \({\lnot}p{\vee}{\lnot}q\), \(p{\vee}q{\vee}r\), \(p{\vee}q{\vee}{\lnot}r\)等都是基本和.

注意: 一个命题变元或命题变元的否定即可看做是基本积也可以看做基本和.

例: \(p\), \({\lnot}p\), \(q\), \({\lnot}q\)是基本积, 也是基本和.

定理: 一个基本积为永假式的充分必要条件是它同时包含某个命题变元及其否定.

例: 基本积\(p{\wedge}q{\wedge}{\lnot}q\)是永假式, 因为它同时包含命题变元\(q\)及其否定\({\lnot}q\).

定理: 一个基本和为永真式的充分必要条件是它同时包含某个命题变元及其否定.

例: 基本和\(p{\vee}q{\vee}{\lnot}p\)为永真式, 因为它同时包含命题变元\(p\)及其否定\({\lnot}p\).

定义: 一个由基本积的析取组成的命题公式, 称为析取范式, 即该命题公式具有形式: \[A_{1}{\vee}A_{2}{\vee}{\cdots}{\vee}A_n\] 其中\(A_{1}, A_{2}, {\cdots}, A_n\)都是基本积.

例: 命题公式\({\lnot}p{\vee}(p{\wedge}q){\vee}(p{\wedge}{\lnot}q{\wedge}r)\)是析取范式.

定义:一个由基本和的合取组成的命题公式, 称为合取范式, 即该命题公式具有形式: \[B_{1}{\wedge}B_{2}{\wedge}{\cdots}{\wedge}B_n\] 其中\(B_{1}, B_{2}, {\cdots}, B_n\)都是基本和.

例: 命题公式\(q{\wedge}(p{\vee}q){\wedge}({\lnot}q{\vee}r)\)是合取范式.

任何析取范式的对偶式为合取范式; 任何合取范式的对偶式为析取范式.

定理(范式存在定理): 任一命题公式都存在与其等值的析取范式和合取范式.

对于一个命题公式, 求其析取范式和合取范式的步骤如下:

  1. 消去{\({\lnot}, {\wedge}, {\vee}\)}以外的逻辑联结词;

  2. 利用德\({\cdot}\)摩根律将否定联结词\({\lnot}\)内移到命题变元之前, 消去双重否定;

  3. 利用分配律化成析取范式或合取范式.

 

命题公式的析取范式和合取范式都不一定是唯一的.

求下面命题公式的合取范式和析取范式: \[((p{\vee}q){\rightarrow}r){\rightarrow}p\]

解: (1)求合取范式 \[((p{\vee}q){\rightarrow}r){\rightarrow}p\] \[{\Leftrightarrow}({\lnot}(p{\vee}q){\vee}r){\rightarrow}p\] \[{\Leftrightarrow}{\lnot}({\lnot}(p{\vee}q){\vee}r){\vee}p\] \[{\Leftrightarrow}((p{\vee}q){\wedge}{\lnot}r){\vee}p\] \[{\Leftrightarrow}(p{\vee}q{\vee}p){\wedge}({\lnot}r{\vee}p)\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}r{\vee}p)\]

 

 

(2)求析取范式

\[((p{\vee}q){\rightarrow}r){\rightarrow}p\] \[{\Leftrightarrow}{\lnot}({\lnot}(p{\vee}q){\rightarrow}r){\rightarrow}p\] \[{\Leftrightarrow}((p{\vee}q){\wedge}{\lnot}r){\vee}p\] \[{\Leftrightarrow}(p{\wedge}{\lnot}r){\vee}(q{\wedge}{\lnot}r){\vee}p\] \[{\Leftrightarrow}p{\vee}(q{\wedge}{\lnot}r)\]

也可以通过命题公式的合取范式来求析取范式, 或通过命题公式的析取范式来求和取范式.

\[((p{\vee}q){\rightarrow}r){\rightarrow}p\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}r{\vee}p)\] \[{\Leftrightarrow}(p{\wedge}{\lnot}r){\vee}(p{\wedge}p){\vee}(q{\wedge}{\lnot}r){\vee}(q{\wedge}p)\] \[{\Leftrightarrow}(p{\wedge}{\lnot}r){\vee}p{\vee}(q{\wedge}{\lnot}r){\vee}(q{\wedge}p)\] \[{\Leftrightarrow}p{\vee}(q{\wedge}{\lnot}r){\vee}(q{\wedge}p)\] \[{\Leftrightarrow}p{\vee}(q{\wedge}{\lnot}r)\]

利用析取范式和合取范式可对命题公式的类型进行判定.

  1. 一个析取范式是永假式, 当且仅当它的每个基本积都是永假式; \((A_{1}{\vee}A_{2}{\vee}{\cdots}{\vee}A_n\), \(A_i\)是永假式)

  2. 一个合取范式是永真式, 当且仅当它的每个基本和都是永真式; \((B_{1}{\wedge}B_{2}{\wedge}{\cdots}{\wedge}B_n\), \(B_i\)是永真式)

  3. 一个命题公式为永假式, 当且仅当它的析取范式中每一个基本积都至少含有一个命题变元及其否定;

  4. 一个命题公式为永真式, 当且仅当它的合取范式中每一个基本和都至少含有一个命题变元及其否定.

试通过求范式判断下列命题公式的类型:

\[p{\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q).\] 解: \[p{\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}((p{\wedge}{\lnot}p){\vee}(p{\wedge}q)){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}(F{\vee}(p{\wedge}q)){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}q){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}q{\wedge}{\lnot}p){\vee}(p{\wedge}q{\wedge}{\lnot}q)\] 由于第一个基本积中同时包含有\(p\)和\({\lnot}p\), 第二个基本积中同时包含有\(q\)和\({\lnot}q\).

因此该命题公式为永假式.

试通过求范式判断下列命题公式的类型: \[p{\rightarrow}(q{\rightarrow}(p{\wedge}q))\]

解: \[p{\rightarrow}(q{\rightarrow}(p{\wedge}q))\] \[{\Leftrightarrow}{\lnot}p{\vee}({\lnot}q{\vee}(p{\wedge}q))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}q{\vee}p){\wedge}({\lnot}q{\vee}q))\] \[{\Leftrightarrow}({\lnot}p{\vee}{\lnot}q{\vee}p){\wedge}({\lnot}p{\vee}{\lnot}q{\vee}q)\] 由于第一个基本和中同时包含有\(p\)和\({\lnot}p\), 第二个基本和中同时包含有\(q\)和\({\lnot}q\).

因此, 此命题公式为永真式.

试通过求范式判断下列命题公式的类型:

\[(p{\vee}q){\rightarrow}(p{\wedge}q)\] 解: \[(p{\vee}q){\rightarrow}(p{\wedge}q)\] \[{\Leftrightarrow}{\lnot}(p{\vee}q){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}(p{\vee}{\lnot}q){\wedge}({\lnot}p{\vee}q)\] 由该命题公式的析取范式和合取范式可知: 它既不是永真式, 也不是永假式, 而是可满足式.

试判断下式是否是永真式: \[q{\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}q).\] 解: 化成合取范式 \[q{\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}((q{\vee}p){\wedge}(q{\vee}{\lnot}q)){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}((q{\vee}p){\wedge}T){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(q{\vee}p){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(q{\vee}p{\vee}{\lnot}p){\wedge}(q{\vee}p{\vee}{\lnot}q)\] 因此, 该命题公式为永真式.

主析取范式与主合取范式

在含有\(n\)个命题变元的基本积中, 如果每个变元与它的否定不同时存在, 但二者之一必出现且仅出现一次, 则这样的基本积称为极小项.

二个命题变元构成的极小项有: \[p{\wedge}q, p{\wedge}{\lnot}q, {\lnot}p{\wedge}q, {\lnot}p{\wedge}{\lnot}q\] 三个命题变元构成的极小项有: \[p{\wedge}q{\wedge}r, p{\wedge}q{\wedge}{\lnot}r, p{\wedge}{\lnot}q{\wedge}r, p{\wedge}{\lnot}q{\wedge}{\lnot}r, {\lnot}p{\wedge}q{\wedge}r, {\lnot}p{\wedge}q{\wedge}{\lnot}r, \] \[{\lnot}p{\wedge}{\lnot}q{\wedge}r, {\lnot}p{\wedge}{\lnot}q{\wedge}{\lnot}r\] 一般情况下, \(n\)个命题变元共有\(2^{n}\)个不同的极小项, 分别记为\(m_{0}, m_{1}, \cdots, m_{2^n-1}\), \(m_{i}\)表示第\(i\)个极小项.

定义:在含有\(n\)个命题变元的基本和中, 如果每个变元与它的否定不同时存在, 但二者之一必出现且仅出现一次, 则这样的基本和称为极大项.

二个命题变元构成的极大项有: \[p{\vee}q, p{\vee}{\lnot}q, {\lnot}p{\vee}q, {\lnot}p{\vee}{\lnot}q\] 三个命题变元构成的极大项有: \[p{\vee}q{\vee}r, p{\vee}q{\vee}{\lnot}r, p{\vee}{\lnot}q{\vee}r, p{\vee}{\lnot}q{\vee}{\lnot}r, {\lnot}p{\vee}q{\vee}r, {\lnot}p{\vee}q{\vee}{\lnot}r, \] \[{\lnot}p{\vee}{\lnot}q{\vee}r, {\lnot}p{\vee}{\lnot}q{\vee}{\lnot}r\] 一般情况下, \(n\)个命题变元共有\(2^{n}\)个不同的极大项, 分别记为\(M_{0}, M_{1}, \cdots, M_{2^n-1}, M_{i}\)表示第\(i\)个极大项.

对于给定的含\(n\)个命题变元的命题公式, 若其析取范式的基本积均是这\(n\)个命题变元的极小项, 则称该析取范式为命题公式的主析取范式.

基本形式: \[A_{1}{\vee}A_{2}{\vee}{\cdots}{\vee}A_n\] 对于给定的含\(n\)个命题变元的命题公式, 若其合取范式的基本和均是这\(n\)个命题变元的极大项, 则称该合取范式为命题公式的主合取范式.

基本形式: \[B_{1}{\wedge}B_{2}{\wedge}{\cdots}{\wedge}B_n\]

定理(主析取范式存在唯一性): 任一个不为永假式的命题公式都存在与其等价的主析取范式, 且唯一.

定理(主合取范式存在唯一性): 任一个不为永真式的命题公式都存在与其等价的主合取范式, 且唯一.

求主范式可采用两种方法:

  1. 真值表法

  2. 公式推演法(等值演算法)

一个命题公式的主范式可通过构造其真值表的办法予以写出.

在真值表中, 命题公式真值为\(T\)的解释所对应真值为\(T\)的极小项的析取, 即为该命题公式的主析取范式.

在真值表法, 命题公式真值为\(F\)的解释所对应真值为\(F\)的极大项的合取, 即为该命题公式的主合取范式.

例: 求\(p{\rightarrow}q\)的主析取范式.

解: \(p{\rightarrow}q\)的主析取范式就是\(p{\wedge}q\), \(p{\wedge}{\lnot}q\), \({\lnot}p{\wedge}q\), \({\lnot}p{\wedge}{\lnot}q\)这四个极小项中若干个的析取.

命题公式及两个命题变元极小项的真值表如下:

 

\[ \begin{array}{ccccccc} p & q & p{\rightarrow}q & {\lnot}p{\wedge}{\lnot}q & {\lnot}p{\wedge}q & p{\wedge}{\lnot}q & p{\wedge}q\\ 0 & 0 & 1&1&0&0&0 \\ 0 & 1 & 1&0&1&0&0 \\ 1 & 0 & 0&0&0&1&0 \\ 1 & 1 & 1&0&0&0&1 \\ \end{array} \]

 

因此, \(p{\rightarrow}q\)的主析取范式是:

  \[p{\rightarrow}q{\leftrightarrow}({\lnot}p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}q){\vee}(p{\wedge}q).\]

求\({\lnot}p{\wedge}{\lnot}q\)的主合取范式.

解: \({\lnot}p{\wedge}{\lnot}q\)的主合取范式就是\(p{\vee}q, p{\vee}{\lnot}q, {\lnot}p{\vee}q, {\lnot}p{\vee}{\lnot}q\)这四个极大项中的若干个的合取.

\[ \begin{array}{ccccccc} p & q & {\lnot}p{\wedge}{\lnot}q & p{\vee}q & p{\vee}{\lnot}q & {\lnot}p{\vee}q & {\lnot}p{\vee}{\lnot}q\\ 0 & 0 & 1&0&1&1&1 \\ 0 & 1 & 0&1&0&1&1 \\ 1 & 0 & 0&1&1&0&1 \\ 1 & 1 & 0&1&1&1&0 \\ \end{array} \]  

因此, \({\lnot}p{\wedge}{\lnot}q\)的主合取范式: \[{\lnot}p{\wedge}{\lnot}q{\Leftrightarrow}(p{\vee}{\lnot}q){\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q).\]

求\(p{\rightarrow}{\lnot}q\)的主范式(主析取范式和主合取范式).

解:

\[ \begin{array}{ccccccc} p & q & p{\rightarrow}{\lnot}q & {\lnot}p{\wedge}{\lnot}q & {\lnot}p{\wedge}q & p{\wedge}{\lnot}q & p{\wedge}q\\ 0 & 0 & 1&1&0&0&0 \\ 0 & 1 & 1&0&1&0&0 \\ 1 & 0 & 1&0&0&1&0 \\ 1 & 1 & 0&0&0&0&1 \\ \end{array} \]  

因此, \(p{\rightarrow}{\lnot}q\)的主析取范式是 \(p{\rightarrow}{\lnot}q{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}q)\) \({\vee}({\lnot}p{\wedge}q){\vee}(p{\wedge}{\lnot}q).\)

接下来求\(p{\rightarrow}{\lnot}q\)的主合取范式.

  \[ \begin{array}{ccccccc} p & q & p{\rightarrow}{\lnot}q & p{\vee}q & p{\vee}{\lnot}q & {\lnot}p{\vee}q & {\lnot}p{\vee}{\lnot}q\\ 0 & 0 & 1&0&1&1&1 \\ 0 & 1 & 1&1&0&1&1 \\ 1 & 0 & 1&1&1&0&1 \\ 1 & 1 & 0&1&1&1&0 \\ \end{array} \]  

因此, \(p{\rightarrow}{\lnot}q\)的主合取范式是 \[p{\rightarrow}{\lnot}q{\Leftrightarrow}({\lnot}p{\vee}{\lnot}q).\]

可以利用公式推演法(等值演算法)构造主析取范式, 其步骤如下:

  1. 将命题公式化为析取范式.

  2. 除去析取范式中所有永假的基本积.

  3. 利用等幂律将重复出现的基本积和基本积中重复出现的变元合并.

  4. 利用同一律在基本积中补入未出现的命题变元(如\(p{\vee}{\lnot}p\)), 然后用分配律展开.

  5. 再次利用等幂律将重复出现的极小项合并.

求\({\lnot}p{\vee}{\lnot}q\)的主析取范式.

解: \[{\lnot}p{\vee}{\lnot}q\] \[{\Leftrightarrow}({\lnot}p{\wedge}(q{\vee}{\lnot}q)){\vee}((p{\vee}{\lnot}p){\wedge}{\lnot}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}{\lnot}q)\]

求\(p{\rightarrow}((p{\rightarrow}q){\wedge}{\lnot}({\lnot}q{\vee}{\lnot}p))\)的主析取范式.

解: \[p{\rightarrow}((p{\rightarrow}q){\wedge}{\lnot}({\lnot}q{\vee}{\lnot}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}p{\vee}q){\wedge}(q{\wedge}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}p{\wedge}q{\wedge}p){\vee}(q{\wedge}q{\wedge}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}F{\vee}(q{\wedge}p)\] \[{\Leftrightarrow}{\lnot}p{\vee}(q{\wedge}p)\] \[{\Leftrightarrow}({\lnot}p{\wedge}(q{\vee}{\lnot}q)){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q){\vee}(p{\wedge}q)\]

同样, 可以利用公式推演法构造主合取范式.

  1. 将命题公式化为合取范式.

  2. 除去合取范式中所有永真的基本和.

  3. 利用等幂律将重复出现的基本和与基本和中重复出现的变元合并.

  4. 利用同一律在基本和中补入未出现的命题变元(如\(p{\wedge}{\lnot}p\)), 然后用分配律展开.

  5. 再次利用等幂律将重复出现的极大项合并.

求\({\lnot}p{\wedge}{\lnot}q\)的主合取范式.

解: \[{\lnot}p{\wedge}{\lnot}q\] \[{\Leftrightarrow}({\lnot}p{\vee}(q{\wedge}{\lnot}q)){\wedge}((p{\wedge}{\lnot}p){\vee}{\lnot}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q){\wedge}(p{\vee}{\lnot}q){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}{\lnot}q){\wedge}(p{\vee}{\lnot}q)\]

求\(p{\rightarrow}((p{\rightarrow}q){\wedge}{\lnot}({\lnot}q{\vee}{\lnot}p))\)的主合取范式.

解: \[p{\rightarrow}((p{\rightarrow}q){\wedge}{\lnot}({\lnot}q{\vee}{\lnot}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}p{\vee}q){\wedge}(q{\wedge}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}(({\lnot}p{\wedge}q{\wedge}p){\vee}(q{\wedge}q{\wedge}p))\] \[{\Leftrightarrow}{\lnot}p{\vee}F{\vee}(q{\wedge}p)\] \[{\Leftrightarrow}{\lnot}p{\vee}(q{\wedge}p)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}({\lnot}p{\vee}p)\] \[{\Leftrightarrow}{\lnot}p{\vee}q\]

求\((p{\wedge}q){\vee}(p{\wedge}r)\)的主范式.

解: \[(p{\wedge}q){\vee}(p{\wedge}r){\Leftrightarrow}p{\wedge}(q{\vee}r)\] \[{\Leftrightarrow}(p{\vee}(q{\wedge}{\lnot}q){\vee}(r{\wedge}{\lnot}r)){\wedge}((p{\wedge}{\lnot}p){\vee}q{\vee}r)\] \[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}q{\vee}{\lnot}r){\wedge}(p{\vee}{\lnot}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}{\lnot}r){\wedge}(p{\vee}q{\vee}r){\wedge}({\lnot}p{\vee}q{\vee}r)\]

\[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}q{\vee}{\lnot}r){\wedge}(p{\vee}{\lnot}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}{\lnot}r){\wedge}({\lnot}p{\vee}q{\vee}r)\] 同时, \[(p{\wedge}q){\vee}(p{\wedge}r)\] \[{\Leftrightarrow}(p{\wedge}q{\wedge}(r{\vee}{\lnot}r)){\vee}(p{\wedge}(q{\vee}{\lnot}q){\wedge}r)\] \[{\Leftrightarrow}(p{\wedge}q{\wedge}r){\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}q{\wedge}r){\vee}(p{\wedge}{\lnot}q{\wedge}r)\] \[{\Leftrightarrow}(p{\wedge}q{\wedge}r){\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}{\lnot}q{\wedge}r)\]

 

主析取范式与主合取范式项数相加是: \(8=2^3\).

真值表法求主范式的简化

一般情况下, \(n\)个命题变元共有\(2^{n}\)个不同的极小项, 分别记为\(m_{0}, m_{1}, \cdots, m_{2^n-1}, m_{i}\)表示第\(i\)个极小项.

极小项下标的表示: n个命题变元构成的\(2^{n}\)个极小项, 其第\(i\)个极小项\(m_{i}\)的下标\(i\)使用\(n\)位二进制编码表示.

当某一位为命题变元时, 该位对应的二进制编码为1; 当某一位为命题变元的否时, 该位对应的二进制编码为0.

两个命题变元的4个不同的极小项真值表

  \[ \begin{array}{ccccccc} p & q & {\lnot}p{\wedge}{\lnot}q & {\lnot}p{\wedge}q & p{\wedge}{\lnot}q & p{\wedge}q&\\ && m_0(m_{00})& m_1(m_{01})& m_2(m_{10})& m_3(m_{11})&\\ 0 & 0 & 1&0&0&0 & m_0\\ 0 & 1 & 0&1&0&0 & m_1 \\ 1 & 0 & 0&0&1&0 & m_2 \\ 1 & 1 & 0&0&0&1 & m_3 \\ \end{array} \]  

极小项的十进制下标编码和二进制下标编码.

极小项的性质:

  1. 每个极小项当其解释与编码相同时, 其真值为\(T\); 而解释与编码不同时其真值为\(F\), 即在其余\(2^{n}-1\)个解释下其真值均为\(F\).

  2. 任意两个不同极小项的合取式为永假式, 即 \(m_{i}{\wedge}m_{j}{\Leftrightarrow}F(i{\neq}j).\)

  3. 所有极小项的析取式为永真式, 即 \(m_{0}{\vee}m_{1}{\vee}{\cdots}{\vee}m_{2^{n}-1}{\Leftrightarrow}T.\)

一般情况下, \(n\)个命题变元共有\(2^{n}\)个不同的极大项, 分别记为\(M_{0}, M_{1}, \cdots, M_{2^{n}-1}, M_{i}\)表示第\(i\)个极大项.

极大项下标的表示: \(n\)个命题变元构成的\(2^{n}\)个不同的极大项, 其第\(i\)个极大项\(M_{i}\)的下标i可以使用\(n\)位二进制编码表示.

当极大项的某一位为命题变元时, 该位对应的二进制为0; 当极大项的某一位为命题变元的否时, 该位对应的二进制为1.

两个命题变元的4个不同的极大项真值表

  \[ \begin{array}{ccccccc} p & q & {\lnot}p{\vee}{\lnot}q & {\lnot}p{\vee}q & p{\vee}{\lnot}q & p{\vee}q&\\ && M_3(M_{11})& M_2(M_{10})& M_1(M_{01})& M_0(M_{00})&\\ 1 & 1 & 0&1&1&1 & M_3\\ 1 & 0 & 1&0&1&1 & M_2\\ 0 & 1 & 1&1&0&1 & M_1\\ 0 & 0 & 1&1&1&0 & M_0\\ \end{array} \]

极大项的性质:

  1. 每个极大项当其解释与编码相同时, 其真值为\(F\); 而解释与编码不同时其真值为\(T\), 即在其余\(2^{n}-1\)个解释下其真值均为\(T\).

  2. 任意两个不同极大项的的析取式为永真式, 即\(M_{i}{\vee}M_j{\Leftrightarrow}T(i{\neq}j).\)

  3. 所有极大项的合取式为永假式, 即 \(M_{0}{\wedge}M_{1}{\wedge}{\cdots}{\wedge}M_{2^{n}-1}{\Leftrightarrow}F.\)

求如下命题公式的主析取和主合取范式: \[q{\wedge}(p{\vee}{\lnot}q)\] 解: 构造主析取范式   \[ \begin{array}{cccc} p & q & q{\wedge}(p{\vee}{\lnot}q) &\\ 0 & 0 & 0 & m_0\\ 0 & 1 & 0 & m_1\\ 1 & 0 & 0 & m_2\\ 1 & 1 & 1 & m_3\\ \end{array} \] 故\(q{\wedge}(p{\vee}{\lnot}q)\)的主析取式为: \[q{\wedge}(p{\vee}{\lnot}q){\Leftrightarrow}m_{3}{\Leftrightarrow}m_{11}{\Leftrightarrow}p{\wedge}q.\]

构造主合取范式

\[ \begin{array}{cccc} p & q & q{\wedge}(p{\vee}{\lnot}q) &\\ 1 & 1 & 1 & M_3\\ 1 & 0 & 0 & M_2\\ 0 & 1 & 0 & M_1\\ 0 & 0 & 0 & M_0\\ \end{array} \] 故\(q{\wedge}(p{\vee}{\lnot}q)\)的主合取式为: \[q{\wedge}(p{\vee}{\lnot}q)\] \[{\Leftrightarrow}M_{0}{\wedge}M_{1}{\wedge}M_{2}\] \[{\Leftrightarrow}M_{00}{\wedge}M_{01}{\wedge}M_{10}\] \[{\Leftrightarrow}(p{\vee}q){\wedge}(p{\vee}{\lnot}q){\wedge}({\lnot}p{\vee}q)\]

三个命题变元的8个不同的极小项真值表

 

\[ \begin{array}{ccccccccc} &&&m_0&m_1&m_2&m_3&m_4&m_5&m_6&m_7\\ p & q & r & \bar{p}\bar{q}\bar{r} & \bar{p}\bar{q}{r} & \bar{p}{q}\bar{r} &\bar{p}{q}{r} & {p}\bar{q}\bar{r} & {p}\bar{q}{r} & {p}{q}\bar{r} & {p}{q}{r}\\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & m_0\\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & m_1\\ 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & m_2\\ 0 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & m_3\\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & m_4\\ 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & m_5\\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & m_6\\ 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & m_7\\ \end{array} \]

三个命题变元的8个不同的极大项真值表

 

\[ \begin{array}{ccccccccc} p & q & r & M_7&M_6&M_5&M_4&M_3&M_2&M_1&M_0\\ 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & M_7\\ 1 & 1 & 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & M_6\\ 1 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & M_5\\ 1 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & 1 & M_4\\ 0 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & 1 & M_3\\ 0 & 1 & 0 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & 1 & M_2\\ 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & 1 & M_1\\ 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 0 & M_0\\ \end{array} \]

 

注意: 这里\(M_7\)对应于\(\lnot{p}{\lor}\lnot{q}{\lor}\lnot{r}\).

求\((p{\wedge}q){\vee}r\)的主范式.

\[ \begin{array}{cccccc} p & q & r & (p{\wedge}q){\vee}r&&\\ 0 & 0 & 0 & 0 & m_0 & \boxed{M_0}\\ 0 & 0 & 1 & 1 & \boxed{m_1} & M_1\\ 0 & 1 & 0 & 0 & m_2 & \boxed{M_2}\\ 0 & 1 & 1 & 1 & \boxed{m_3} & M_3\\ 1 & 0 & 0 & 0 & m_4 & \boxed{M_4}\\ 1 & 0 & 1 & 1 & \boxed{m_5} & M_5\\ 1 & 1 & 0 & 1 & \boxed{m_6} & M_6\\ 1 & 1 & 1 & 1 & \boxed{m_7} & M_7\\ \end{array} \]

主析取范式: \[(p{\wedge}q){\vee}r{\Leftrightarrow}m_{1}{\vee}m_{3}{\vee}m_{5}{\vee}m_{6}{\vee}m_{7}\] \[{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}q{\wedge}r){\vee}({\lnot}p{\wedge}q{\wedge}r){\vee}(p{\wedge}{\lnot}q{\wedge}r)\] \[{\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}q{\wedge}r)\] \[{\Leftrightarrow}m_{001}{\vee}m_{011}{\vee}m_{101}{\vee}m_{110}{\vee}m_{111}\]

主合取范式: \[(p{\wedge}q){\vee}r{\Leftrightarrow}M_{0}{\wedge}M_{2}{\wedge}M_{4}\] \[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}r){\wedge}({\lnot}p{\vee}q{\vee}r)\] \[{\Leftrightarrow}M_{000}{\wedge}M_{010}{\wedge}M_{100}\]

求\(({\lnot}p{\rightarrow}r){\wedge}(q{\leftrightarrow}p)\)的主范式.

\[ \begin{array}{cccccc} p & q & r & ({\lnot}p{\rightarrow}r){\wedge}(q{\leftrightarrow}p)&&\\ 0 & 0 & 0 & 0 & m_0 & \boxed{M_0}\\ 0 & 0 & 1 & 1 & \boxed{m_1} & M_1\\ 0 & 1 & 0 & 0 & m_2 & \boxed{M_2}\\ 0 & 1 & 1 & 1 & m_3 & \boxed{M_3}\\ 1 & 0 & 0 & 0 & m_4 & \boxed{M_4}\\ 1 & 0 & 1 & 1 & m_5 & \boxed{M_5}\\ 1 & 1 & 0 & 1 & \boxed{m_6} & M_6\\ 1 & 1 & 1 & 1 & \boxed{m_7} & M_7\\ \end{array} \]

主析取范式: \[({\lnot}p{\rightarrow}r){\wedge}(q{\leftrightarrow}p)\] \[{\Leftrightarrow}m_{1}{\vee}m_{6}{\vee}m_{7}\] \[{\Leftrightarrow}m_{001}{\vee}m_{110}{\vee}m_{111}\] \[{\Leftrightarrow}({\lnot}p{\wedge}{\lnot}q{\wedge}r){\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}q{\wedge}r)\] 主合取范式: \[({\lnot}p{\rightarrow}r){\wedge}(q{\leftrightarrow}p)\] \[{\Leftrightarrow}M_{0}{\wedge}M_{2}{\wedge}M_{3}{\wedge}M_{4}{\wedge}M_{5}\] \[{\Leftrightarrow}M_{000}{\wedge}M_{010}{\wedge}M_{011}{\wedge}M_{100}{\wedge}M_{101}\] \[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}r){\wedge}(p{\vee}{\lnot}q{\vee}{\lnot}r){\wedge}({\lnot}p{\vee}q{\vee}r){\wedge}({\lnot}p{\vee}q{\vee}{\lnot}r)\]

极小项与极大项之间的关系: \[{\lnot}m_{i}{\Leftrightarrow}M_{i}, \, \, {\lnot}M_{i}{\Leftrightarrow}m_{i}\] 设命题公式\(A\)中含\(n\)个命题变元, \(A{\vee}{\lnot}A\)(永真式)的主析取范式应包含有\(n\)个命题变元的所有\(2^{n}\)个极小项.

反之, \(A{\wedge}{\lnot}A\)(永假式)的主合取范式应包含有\(n\)个命题变元的所有\(2^{n}\)个极大项.

已知\(A\)的主析取范式求\(A\)的主合取范式的步骤:

  1. 求出\({\lnot}A\)的主析取范式, 即\(A\)的主析取范式中没有出现的极小项的析取;

  2. \({\lnot}{\lnot}A\)即为\(A\)的主合取范式.

已知\(A\)的主合取范式求\(A\)的主析取范式的步骤:

  1. 求出\({\lnot}A\)的主合取范式, 即\(A\)的主合取范式中没有出现的极大项的合取;

  2. \({\lnot}{\lnot}A\)即为\(A\)的主析取范式.

求命题公式的主范式: \[A=(p{\rightarrow}q){\wedge}q\] 解: \[A=(p{\rightarrow}q){\wedge}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}q)\] \[{\Leftrightarrow}M_{10}{\wedge}M_{00}\]

  \[{\lnot}A{\Leftrightarrow}M_{01}{\wedge}M_{11}\] \[{\lnot}{\lnot}A{\Leftrightarrow}{\lnot}(M_{01}{\wedge}M_{11}){\Leftrightarrow}m_{01}{\vee}m_{11}\] \[{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}(p{\wedge}q)\]

求命题公式的主范式: \[A=p{\vee}(q{\wedge}{\lnot}r)\] 解: \[A=p{\vee}(q{\wedge}{\lnot}r)\] \[{\Leftrightarrow}(p{\wedge}({\lnot}q{\vee}q){\wedge}({\lnot}r{\vee}r)){\vee}(({\lnot}p{\vee}p){\wedge}(q{\wedge}{\lnot}r))\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q{\wedge}{\lnot}r){\vee}(p{\wedge}{\lnot}q{\wedge}r){\vee}(p{\wedge}q{\wedge}{\lnot}r){\vee}(p{\wedge}q{\wedge}r){\vee}({\lnot}p{\wedge}q{\wedge}{\lnot}r)\]

\[{\Leftrightarrow}m_{100}{\vee}m_{101}{\vee}m_{110}{\vee}m_{111}{\vee}m_{010}\]

 

\[{\lnot}A{\Leftrightarrow}m_{000}{\vee}m_{001}{\vee}m_{011}\] \[{\lnot}{\lnot}A{\Leftrightarrow}{\lnot}(m_{000}{\vee}m_{001}{\vee}m_{011}){\Leftrightarrow}M_{000}{\wedge}M_{001}{\wedge}M_{011}\] \[{\Leftrightarrow}(p{\vee}q{\vee}r){\wedge}(p{\vee}q{\vee}{\lnot}r){\wedge}(p{\vee}{\lnot}q{\vee}{\lnot}r)\]

主析(合)取范式的应用:

  • 判断两命题公式是否等价;

  • 判断命题公式的类型.

 

欲证明等价式, 可分别求出两个命题公式的主析取范式或主合取范式. 若它们相同, 则两命题公式等价; 否则两命题公式不等价.

求证: \((p{\rightarrow}q){\wedge}q{\Leftrightarrow}(p{\vee}{\lnot}q){\rightarrow}q.\)

证明: \[(p{\rightarrow}q){\wedge}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\]   \[(p{\vee}{\lnot}q){\rightarrow}q\] \[{\Leftrightarrow}{\lnot}(p{\vee}{\lnot}q){\vee}q{\Leftrightarrow}({\lnot}p{\wedge}q){\vee}q\] \[{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}q{\Leftrightarrow}({\lnot}p{\vee}q){\wedge}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}p{\vee}q)\]

利用主析(合)取范式判定公式类型:

  1. 若\(A\)等价于\(T\)或\(A\)的主析取范式含有\(2^{n}\)个极小项, 则\(A\)为永真式;

  2. 若\(A\)等价于\(F\)或\(A\)的主合取范式含有\(2^{n}\)个极大项, 则\(A\)为永假式;

  3. 若\(A\)不等价于\(T\)也不等价于\(F\), 且其主析取范式中的极小项小于\(2^{n}\)个, 主合取范式中的极大项小于\(2^{n}\)个, 则\(A\)为可满足式.

判定下列命题公式的类型.

  1. \(p{\vee}((p{\vee}q){\rightarrow}q)\)

解: \[p{\vee}((p{\vee}q){\rightarrow}q)\] \[{\Leftrightarrow}p{\vee}({\lnot}(p{\vee}q){\vee}q)\] \[{\Leftrightarrow}p{\vee}q{\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}(q{\vee}{\lnot}q)){\vee}((p{\vee}{\lnot}p){\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}q){\vee}(p{\wedge}{\lnot}q){\vee}(p{\wedge}q){\vee}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] \[{\Leftrightarrow}(p{\wedge}q){\vee}(p{\wedge}{\lnot}q){\vee}({\lnot}p{\wedge}q){\vee}({\lnot}p{\wedge}{\lnot}q)\] 主析取范式含4个极小项, 因此为永真式.

  1. \(q{\wedge}(q{\rightarrow}p){\wedge}(p{\rightarrow}{\lnot}q)\)

解: \[q{\wedge}(q{\rightarrow}p){\wedge}(p{\rightarrow}{\lnot}q)\] \[{\Leftrightarrow}q{\wedge}({\lnot}q{\vee}p){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}((p{\wedge}{\lnot}p){\vee}q){\wedge}({\lnot}q{\vee}p){\wedge}({\lnot}p{\vee}{\lnot}q)\] \[{\Leftrightarrow}(p{\vee}q){\wedge}({\lnot}p{\vee}q){\wedge}({\lnot}q{\vee}p){\wedge}({\lnot}p{\vee}{\lnot}q)\] 主合取范式含4个极大项, 因此为永假式.

  1. \(p{\vee}(q{\wedge}{\lnot}({\lnot}p{\wedge}q)).\)

解: \[p{\vee}(q{\wedge}{\lnot}({\lnot}p{\wedge}q))\] \[{\Leftrightarrow}p{\vee}(q{\wedge}(p{\vee}{\lnot}q))\] \[{\Leftrightarrow}p{\vee}(q{\wedge}p){\vee}(q{\wedge}{\lnot}q)\] \[{\Leftrightarrow}p{\vee}(p{\wedge}q)\] \[{\Leftrightarrow}(p{\wedge}(q{\vee}{\lnot}q)){\vee}(p{\wedge}q)\] \[{\Leftrightarrow}(p{\wedge}{\lnot}q){\vee}(p{\wedge}q)\] 主析取范式含2个极小项, 为可满足式.

命题逻辑推理理论

推理是指由已知命题出发推出新命题的思维过程.

在这里已知命题称为推理的前提或假设, 新命题称为推理的结论, 而与推理相关的理论称为推理理论.

推理的前提可以是一个命题公式也可以是多个命题公式, 推理的结论是一个命题公式.

设\(A\), \(B\)为命题公式, 若\(A{\rightarrow}B\)为永真式, 即\(A{\Rightarrow}B\), 称\(A\)到\(B\)是一个有效推理. 也称\(B\)为\(A\)的有效结论, 或称\(B\)可由前提\(A\)推出.

设\(A_{1}, A_{2}, {\cdots}, A_n\)和\(B\)是命题公式, 若: \[(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n){\rightarrow}B\] 为永真式, 即: \[A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n{\Rightarrow}B\] 则称\(A_{1}, A_{2}, {\cdots}, A_n\)到\(B\)是一个有效推理, 也称\(B\)是一组前提\(A_{1}, A_{2}, {\cdots}, A_n\)的有效结论, 或称\(B\)可由一组前提\(A_{1}, A_{2}, {\cdots}, A_n\)推出.

这种由前提到结论的推理形式可表示为: \[{A_{1}, A_{2}, {\cdots}, A_n}{\vdash}B\] 其中\({\vdash}\)表示推出, 称\({A_{1}, A_{2}, {\cdots}, A_n}{\vdash}B\)为推理的形式结构.

若推理是有效的, 则记为: \[{A_{1}, A_{2}, {\cdots}, A_n}{\vDash}B\] 也就是\(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n{\Rightarrow}B\).

推理的方法

判别有效结论的过程就是推理或称论证过程.

常用的论证方法有:

  • 简单证明法

  • 形式证明法 (构造性证明法)

简单证明法

设\(A_{1}, A_{2}, {\cdots}, A_n\)和\(B\)是命题公式, 欲证: \[{A_{1}, A_{2}, {\cdots}, A_n}{\vDash}B\] 可通过证明 \[(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n){\rightarrow}B\] 是永真式, 即 \[(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n){\rightarrow}B\] 的真值表中, 在任一种解释下, \[(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n){\rightarrow}B\] 的真值皆为真.

试确定\({\lnot}p\)是否是前提\(p{\rightarrow}q\), \({\lnot}q\)的有效结论？

解: 先求\(((p{\rightarrow}q){\wedge}{\lnot}q){\rightarrow}{\lnot}p\)的真值表

  \[ \begin{array}{ccccccc} p & q & {\lnot}p & {\lnot}q & p{\rightarrow}q & (p{\rightarrow}q){\wedge}{\lnot}q & ((p{\rightarrow}q){\wedge}{\lnot}q){\rightarrow}{\lnot}p \\ 0 & 0 & 1&1&1&1&1 \\ 0 & 1 & 1&0&1&0&1 \\ 1 & 0 & 0&1&0&0&1 \\ 1 & 1 & 0&0&1&0&1 \\ \end{array} \]

 

由真值表可知, 命题公式\(((p{\rightarrow}q){\wedge}{\lnot}q){\rightarrow}{\lnot}p\)为永真式, \(((p{\rightarrow}q){\wedge}{\lnot}q){\vdash}{\lnot}p\)是有效的.

即: \({\lnot}p\)是前提\(p{\rightarrow}q, {\lnot}q\)的有效结论.

形式证明法

形式证明(构造证明)是一个描述推理过程的命题公式序列, 该序列中每个命题或者是已知的前提, 或者是由某些前提推导的结论.

推理规则包括:

  1. P规则(前提引入规则)

  2. T规则(结论引入规则)

  3. 置换规则

  4. CP规则

以及基本等价式和基本永真蕴含式.

\(P\)规则(前提引入规则): 在推导的任何步骤上都可以引入前提.

\(T\)规则(结论引入规则) 在推导过程中, 如果前面有一个或多个命题公式推证出结论\(B\), 则可将\(B\)作为后续推导的前提使用.

\(CP\)规则: 如果有效结论为形如\(R{\rightarrow}C\)的条件式, 则可将\(R\)加入到前提中作为附加前提, 然后推导结论\(C\)即可.

 

在形式证明中, 为得到给定前提的有效结论, 一般可采用两种基本方法: 直接证明法和间接证明法.

这两种证明法均需要构造三个序列:

第一序列为步骤编号; 第二序列为推导的命题公式序列; 第三序列为注释行序列, 包括引用的推理规则和使用的推理定律, 即推导的依据.

(1)直接证明法

直接证明法就是由一组已知的前提, 利用推理规则, 根据基本等价式和基本永真蕴含式推导有效结论.

下面证明\({\lnot}p\)是前提\(p{\rightarrow}{\lnot}q, q{\vee}{\lnot}r, r\)的有效结论.

  1. \(r, \qquad\) \(P\)规则

  2. \(q{\vee}{\lnot}r, \qquad\) \(P\)规则

  3. \(q, \qquad\) \(T\)规则(析取三段论), (1)(2)

  4. \(p{\rightarrow}{\lnot}q, \quad\) \(P\)规则

  5. \(q{\rightarrow}{\lnot}p, \quad\) \(T\)规则(逆反式), (4)

  6. \({\lnot}p, \quad\) \(T\)规则(假言推理), (3)(5)

故\({\lnot}p\)是前提\(p{\rightarrow}{\lnot}q, q{\vee}{\lnot}r\), \(r\)的有效结论.

求证: \(\{(p{\vee}q){\rightarrow}r, r{\rightarrow}s, {\lnot}s\}{\vDash}({\lnot}p{\vee}{\lnot}q)\)

证明:

  1. \((p{\vee}q){\rightarrow}r\qquad\) \(P\)规则

  2. \(r{\rightarrow}s\qquad\) \(P\)规则

  3. \((p{\vee}q){\rightarrow}s\qquad\) \(T\)规则, (1)(2)

  4. \({\lnot}s\qquad\) \(P\)规则

  5. \({\lnot}(p{\vee}q)\qquad\) \(T\)规则, (3)(4)

  6. \({\lnot}p{\wedge}{\lnot}q\qquad\) \(T\)规则, (5)

故\({(p{\vee}q){\rightarrow}r, r{\rightarrow}s, {\lnot}s}{\vDash}({\lnot}p{\wedge}{\lnot}q)\)有效.

求证: \({(w{\vee}r){\rightarrow}v, v{\rightarrow}c{\vee}s, s{\rightarrow}u, {\lnot}c{\wedge}{\lnot}u}{\vDash}{\lnot}w\)

证明:

  1. \({\lnot}c{\wedge}{\lnot}u\qquad\) \(P\)规则

  2. \({\lnot}u\qquad\) \(T\)规则, (1)

  3. \(s{\rightarrow}u\qquad\) \(P\)规则

  4. \({\lnot}s\qquad\) \(T\)规则, (2)(3)

  5. \({\lnot}c\qquad\) \(T\)规则, (1)

  6. \({\lnot}c{\wedge}{\lnot}s\qquad\) \(T\)规则, (4)(5)

 

 

  1. \({\lnot}(c{\vee}s)\qquad\) \(T\)规则, (4)

  2. \((w{\vee}r){\rightarrow}v\qquad\) \(P\)规则

  3. \(v{\rightarrow}c{\vee}s\qquad\) \(P\)规则

  4. \((w{\vee}r){\rightarrow}(c{\vee}s)\qquad\) \(T\)规则, (8)(9)

  5. \({\lnot}(w{\vee}r)\qquad\) \(P\)规则(7)(10)

  6. \({\lnot}w{\wedge}{\lnot}r\qquad\) \(T\)规则, (11)

  7. \({\lnot}w\qquad\) \(T\)规则, (12)

例: 一个数是复数当且仅当它是一个实数或虚数. 一个数既不是实数也不是虚数, 所以这个数不是复数.

证明: 将前提和结论符号化.

\(p\): 一个数是复数

\(q\): 一个数是实数

\(r\): 一个数是虚数

前提:\(p{\leftrightarrow}(q{\vee}r), {\lnot}q{\wedge}{\lnot}r\)

结论:\({\lnot}p\)

 

  1. \(p{\leftrightarrow}(q{\vee}r)\qquad\) \(P\)规则

  2. \((p{\rightarrow}(q{\vee}r)){\wedge}((q{\vee}r){\rightarrow}p)\quad\) \(T\)规则, (1)

  3. \(p{\rightarrow}(q{\vee}r)\qquad\) \(P\)规则

  4. \({\lnot}q{\wedge}{\lnot}r\qquad\) \(P\)规则

  5. \({\lnot}(q{\vee}r)\qquad\) \(T\)规则, (4)

  6. \({\lnot}p\qquad\) \(T\)规则, (3)(5)

所以, \({\lnot}p\)是前提\(p{\leftrightarrow}(q{\vee}r), {\lnot}q{\wedge}{\lnot}r\)的有效结论.

间接证明法

反证法

设\(A_{1}, A_{2}, {\cdots}, A_n\)为命题公式, \(P_{1}, P_{2}, {\cdots}, P_m\)为其中出现的全部命题变元.

若至少存在一种解释, 使\(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n\)的真值为真, 则称命题公式\(A_{1}, A_{2}, {\cdots}, A_n\)是相容的(一致的).

否则, 若对任何一种解释, 都至少有一个\(A_i(1{\leq}i{\leq}n)\)的真值为假, 致使\(A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n\)的真值为假. 则称命题公式\(A_{1}, A_{2}, {\cdots}, A_n\)是不相容的(非一致的).

定理: \(A_{1}, A_{2}, {\cdots}, A_n\)是不相容的当且仅当对于任何命题公式\(R\), 都有\[A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n{\Rightarrow}R{\wedge}{\lnot}R.\]

定理:设\(A_{1}, A_{2}, {\cdots}, A_n\), \(C\)为命题公式, 且\(A_{1}, A_{2}, {\cdots}, A_n\)是相容的, 而\[A_{1}, A_{2}, {\cdots}, A_n, {\lnot}C\]是不相容的, 则命题公式\(C\)是命题公式\(A_{1}, A_{2}, {\cdots}, A_n\)的有效结论.

 

要证明 \[{A_{1}, A_{2}, {\cdots}, A_n}{\vdash}C\] 有效, 只要证明: \[A_{1}{\wedge}A_{2}{\wedge}{\cdots}{\wedge}A_n{\wedge}{\lnot}C{\Rightarrow}R{\wedge}{\lnot}R.\]

求证: \({\lnot}D\)是前提\(A{\rightarrow}B, {\lnot}B{\vee}C, {\lnot}C, D{\rightarrow}A\)的有效结论.

证明: 采用反证法. 将\({\lnot}({\lnot}D){\Leftrightarrow}D\)作为附加前提加入到前提之中.

  1. \(D\qquad\) \(P\)(附加前提)

  2. \(D{\rightarrow}A\qquad\) \(P\)

  3. \(A\qquad\) \(T\), (1)(2)

  4. \(A{\rightarrow}B\qquad\) \(P\)

  5. \(B\qquad\) \(T\), (3)(4)

  6. \({\lnot}B{\vee}C\qquad\) \(P\)

  7. \(C\qquad\) \(T\), (5)(6)

  8. \({\lnot}C\qquad\) \(P\)

  9. \(C{\wedge}{\lnot}C\qquad\) \(T\), (7)(8)

求证: \({\lnot}p{\wedge}{\lnot}q{\vDash}{\lnot}(p{\wedge}q).\)

证明: 将\({\lnot}{\lnot}(p{\wedge}q){\Leftrightarrow}p{\wedge}q\)作为附加前提.

  1. \(p{\wedge}q\qquad\) \(P\)(附加前提)

  2. \(p\qquad\) \(T\), (1)

  3. \({\lnot}p{\wedge}{\lnot}q\qquad\) \(P\)

  4. \({\lnot}p\qquad\) \(T\), (3)

  5. \(p{\wedge}{\lnot}p\qquad\) \(T\), (2)(4)

结论\(p{\wedge}{\lnot}p\)是一个矛盾式, 所以 \[{\lnot}p{\wedge}{\lnot}q{\vDash}{\lnot}(p{\wedge}q)\]

求证: \({\lnot}p{\wedge}{\lnot}q{\vDash}{\lnot}(p{\wedge}q).\)

证明:

  1. \({\lnot}p{\wedge}{\lnot}q\qquad\) \(P\)

  2. \({\lnot}p\qquad\) \(T\), (1)

  3. \({\lnot}p{\vee}{\lnot}q\qquad\) \(T\), (2)

  4. \({\lnot}(p{\wedge}q)\qquad\) \(T\), (3)

因此, \[{\lnot}p{\wedge}{\lnot}q{\vDash}{\lnot}(p{\wedge}q).\]

CP规则

如果有效结论为形如\(R{\rightarrow}C\)的条件式, 则可将\(R\)加入到前提中作为附加前提, 然后推导结论\(C\)即可.

\[{A_{1}, A_{2}, {\cdots}, A_n}{\vDash}R{\rightarrow}C\] 等同于: \[{A_{1}, A_{2}, {\cdots}, A_n, R}{\vDash}C\]

求证: \(\{{\lnot}p{\vee}q, q{\rightarrow}s, {\lnot}p{\rightarrow}{\lnot}r\}{\vDash}r{\rightarrow}s\).

证明: 由于结论\(r{\rightarrow}s\)是一个条件式, 因此可采用\(CP\)规则, 将结论中的前件r作为附加前提加入到前提之中, 即: \[\{{\lnot}p{\vee}q, q{\rightarrow}s, {\lnot}p{\rightarrow}{\lnot}r, r\}{\vDash}s\]

  1. \(r\qquad\) \(P\)(附加前提)

  2. \({\lnot}p{\rightarrow}{\lnot}r\qquad\) \(P\)

  3. \(r{\rightarrow}p\qquad\) \(T\), (2)

 

 

  1. \(p\qquad\) \(T\), (1)(3)

  2. \({\lnot}p{\vee}q\qquad\) \(P\)

  3. \(q\qquad\) \(T\), (4)(5)

  4. \(q{\rightarrow}s\qquad\) \(P\)

  5. \(s\qquad\) \(T\), (6)(7)

  6. \(r{\rightarrow}s\qquad\) \(CP\), (1)(8)

设有下列情况, 判断论证是否有效？

前提:

  1. 如果我不去玩游戏, 我会有充足的时间.

  2. 假如我有充足的时间, 我就会认真复习英语.

  3. 如果我认真复习英语, 我的英语考试就不会不及格.

结论: 我的英语考试没及格, 所以我肯定去玩游戏了.

证明: 首先将前提和结论符号化.

\(p\): 我去玩游戏.

\(q\): 我有充足的时间.

\(r\): 我认真复习英语.

\(s\): 我的英语考试及格了.

前提:\({\lnot}p{\rightarrow}q, q{\rightarrow}r, r{\rightarrow}s\)

结论:\({\lnot}s{\rightarrow}p\).

重述一遍前提与结论

前提:\({\lnot}p{\rightarrow}q, q{\rightarrow}r, r{\rightarrow}s\)

结论:\({\lnot}s{\rightarrow}p\)

由于结论\({\lnot}s{\rightarrow}p\)是一个条件式, 故可采用\(CP\)规则来证明.

  1. \({\lnot}p{\rightarrow}q\qquad\) \(P\)

  2. \(q{\rightarrow}r\qquad\) \(P\)

  3. \({\lnot}p{\rightarrow}r\qquad\) \(T\), (1)(2)

 

 

 

  1. \(r{\rightarrow}s\qquad\) \(P\)

  2. \({\lnot}p{\rightarrow}s\qquad\) \(T\), (3)(4)

  3. \({\lnot}s\qquad\) \(P\)(附加前提)

  4. \(p\qquad\) \(T\), (5)(6)

  5. \({\lnot}s{\rightarrow}p\qquad\) \(CP\), (6)(7)