大家好，欢迎来到IT知识分享网。

1.语句

 

1.1命题

一个或真或假，而不能两者都是的陈述句。
说明：

1）命题是陈述句，而不能是疑问句、命令句、感叹句等；
　　例如（1）把门关上！
           　　（2）你到哪里去？
2）如果命题为真，我们就说它的真值为真（T或1）；
     如果命题为假，我们就说它的真值为假（F或0）。
3）命题通常用大写英文字母表示，如 P、Q、R、……。
4）命题语句或真或假，二者必取一；
　　　　例如   x = 3.

1.1.1命题的分类

原子命题：一个命题，但不能分解成更简单的命题。
　　例如  我是一位学生。
复合命题 ：若干个原子命题由联结词和圆括号联结起来构成的新命题。
　　例如  我是一位学生和他是一位工人。
命题常元 ：已知真假值的命题。
　　可直接用{T、F} 表示。
命题变元 ：以真假为其变域之变元，或没有指定真值的命题，但它不是命题。

　　常用大写英文字母 A , B , … , Z 表示。

1.2悖论

语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。
　　例如   我正在说谎。（在命题逻辑中不讨论这类问题）

 

例:判断下列语句是否为命题。  1）十是整数。  2）上海是一个村庄。  3）外星人曾到过地球。  4）小明很高。  5）π 的小数点后面第十亿位上是5。  6）我在说谎。  7）严禁随地吐痰！  8）她身体好吗？  9）x + y > 4. TTTTTFFFF

 

 

---

---

2.命题联结词

在命题逻辑中有以下几种基本的联结词：

¬  ∧  ∨  →  ↔

 

 2.1否定词(  ¬  )

定义：给定命题 P，则在Ｐ的前面加否定词 ¬，变为命题 ¬P，称其为 P 的否定或非 P，记为： ¬P。
其定义可用如下真值表表示:

P	¬P
0	1
1	0

 

 例如： 

P：今天下雨，
¬P：今天不下雨。
Q：每一种生物均是动物。——F
¬Ｑ：有一些生物不是动物。——T
注：这里¬Ｑ不能讲成“每一种生物都不是动物” ——F.
即对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。

 

2.2 合取词( ∧ )

定义：给定两个命题P、Q，则 P∧Q 称为 P 与 Q 的合取，记为： P∧Q 。

 其定义可用如下真值表表示:

注：Ｐ和Ｑ是互为独立的；地位是平等的，Ｐ和Ｑ的位置可以交换而不会影响ＰΛＱ的结果。
例如：

设  P：张三是三好学生；
    Q：李四是三好学生。
则 P∧Q：张三和李四都是三好学生。
注：并非所有的“和”都表示“合取”，例如，王五和赵六是兄弟。当谓词描述的是对象之间的关系时不能用合取。

 

2.3析取词( ∨ )

定义：给定两个命题P、Q，则 P∨Q 称为 P 与 Q 的析取，记为： P ∨ Q 。
其定义可用如下真值表表示:

例如

设 P：灯泡坏了；
   Q：开关坏了；
则 P ∨ Q： 灯泡坏了或是开关坏了。
P：今晚写字；
Q：今晚看书；
则 P ∨ Q：今晚写字或看书。
P：今天下雨；
Q：今天打雷；
则 P ∨ Q：今天下雨或打雷。

2.3.1 不可兼或

注：区分“可兼或”与“不可兼或”
       并非所有的“或”都表示“析取”。
       析取词“∨”为“可兼或”；
       异或词“▽”为“不可兼或”；

例如   我向西走或向东走。

这种“或”就是“不可兼或”（“排斥或”、“异或”）
其特点：当两个命题的真值不同时，原命题的真值为“1”；否则为“0”。

可构造真值表如下：

设P：我向西走； Q：我向东走；
则 P ▽ Q：我向西走或向东走。
例如 1）他通过电视看杂技或到剧场看杂技。2）他乘火车去北京或乘飞机去北京。
以上两句均为“不可兼或”。

 

2.4蕴含词(→),   如果…，则….

定义：给定两个命题P、Q，
命题“如果P，则Q”称为“P蕴含Q”，记为：P→Q。
其中 P 称为蕴含前件、条件、前提；
     Q 称为后件、结果、结论。

注：当且仅当 P 为真，Q 为假时，P→Q 为假；
       否则， P→Q 均为真。

其定义可用如下真值表表示:

例1  P：我拿起一本书
      Q：我一口气读完了这本书
——形式条件命题
则 P→Q：如果我拿起一本书，则我一口气读完了 这本书。

例2  P：月亮出来了
     Q： 3×3=9
——实质条件命题
则 P→Q：如果月亮出来了，则 3×3=9。

例3  a）如果地球是方的，则海水是咸的。
     b）只有地球是方的海水才是咸的。
解：首先用字母表示简单命题。
设 P：地球是方的；
     Q：海水是咸的；
该命题符号化为：a) P→Q  b)¬P→¬Q

注：在日常生活中，用蕴含关系时前提和结论之间都有因果关系，称为“形势蕴含”，

但是在数理逻辑中，蕴含前件和后件可以没有任何因果关系，称为“实质蕴含”。

2.5 等值词（双条件词） ( ↔ )

定义： 给定两个命题P、Q，命题“P 当且仅当 Q”称为“P 等价 Q”记为：P↔Q。
当且仅当P、Q同为真或同为假时 P↔Q 为真；否则， P↔Q 为假。
其定义可用如下真值表表示:

例如  设 Ｐ：△ABC是等腰三角形
         Ｑ：△ABC有两只角相等
   则Ｐ↔Ｑ：△ABC是等腰三角形当且仅当△ABC中有   
              两只角相等。

例如   设 P：2+2=4；Q：雪是白的，
       则 P↔Q：2+2=4当且仅当雪是白的。

例如   设 P：春天来了；Q：燕子飞回来了，
       则 P↔Q：春天来了当且仅当燕子飞回来了。

 

2.6 命题联结词的结合律

1）联结词在运算中的优先级由高到低为：

2）使用括号（  ）可以改变运算顺序——先括号内，后括号外。
3）连续的多个同种联结词结合力顺序为从左到右次序。

例如

2.7命题联结词小结

(1)五个联结词的含义与日常生活中的联结词的含义大致相同。
(2)“或”可分为可兼或（∨）和异或（▽）即不可兼或
(3) 除“¬”为一元运算外，其余四个均为二元运算。
(4) “→”分为形式条件和实质条件命题，当前件为“Ｆ”时，不论后件怎样，则单条件命题的真值均为“Ｔ”。
(5)命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。

经联结词运算后，复合命题真值的规定：

数理逻辑推理步骤如下：
①找出各简单命题，分别符号化。
②找出各联结词，把简单命题逐个联结起来。

 例如： 将下列命题符号化：
（1）李明是计算机系的学生，他住在312室或313室。
（2）张三和李四是朋友。
（3）虽然交通堵塞，但是老王还是准时到达了车站。
（4）老王或小李中有一个去上海出差。
（5）只有一个角是直角的三角形才是直角三角形。

解：
（1）首先用字母表示简单命题。
P：李明是计算机系的学生。
Q：李明住在312室。
R：李明住在313室。
该命题符号化为：P∧（Q▽R）
（2）张三和李四是朋友。是一个简单句，该命题符号化为：P
（3）首先用字母表示简单命题。
P：交通堵塞。
Q：老王准时到达了车站。
该命题符号化为：P ∧ Q
（4）首先用字母表示简单命题。
P：老王去上海出差。
Q：小李去上海出差。
该命题符号化为：P ▽ Q
也可符号化为：
或者

（5）首先用字母表示简单命题。
P：三角形的一个角是直角。
Q：三角形是直角三角形。
该命题符号化为：
注：该命题不可以化为

 

3.命题公式

 3.1定义

命题公式：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。

定义：命题公式可按下述法则来生成：
(1)孤立的命题变元和命题常元是一个命题公式；
(2)若Ａ是命题公式， ¬Ａ也为命题公式；
(3)如果A和B是命题公式，则(A∧B），(A∨B) ，(A→B)和(A↔B)都是命题公式；
(4)当且仅当有限次使用规则(l)(2)和（3）所生成的公式才是命题公式。

 

3.2 命题公式的真值表

对命题变元用特定的命题来取代，这一过程称为对该命题变元进行指派。
命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。写成ｙ＝ｆ(x)

例如：公式P →(Q → R) 可定义三元函数
Y(P，Q，R)＝ P →(Q →R)

定义：命题公式 A 在其所有可能的赋值下取得的值所列成的表称为 A的真值表。

构造命题公式真值表的步骤如下：
1)找出给定命题公式中所有的命题变元，列出所有可能的赋值。
2)按照从低到高的顺序写出命题公式的各层次。
3)对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。

例1：构造命题公式 ¬ (( P ∨ Q )∧P) 的真值表

例2：构造命题公式¬(P∨¬R)∧(Q∨¬P)的真值表

例3  构造命题公式(P∧(P→Q))→Q 的真值表   永真式（重言式）

例4：证明 P ↔ Q 与 P∧Q ∨ ¬P ∧ ¬Q 是逻辑等假命题。
证明：可列真值表证明  真值表相同的两个公式称为等价公式。

由上二例可见，在一个命题公式中，包含：
２个命题变元就有４组真值指派；
３个命题变元就有 2³＝ ８组真值指派，
ｎ个命题变元则有 2ⁿ 个真值指派。

几点说明
熟练之后，真值表的中间有些层次可不写
真值表的用途
    （1）有了公式A的真值表就知道了A的一切信息
    （2）其它用途待续

3.3 重言式（永真式）

举例说明

3.3.1定义

1）设命题公式A(P1,P2,…,Pn)中含有n个不同的原子变元 P1,P2,…,Pn(n为正整数)。

该变元组的任意一组确定的值（U1,…,Un）称为Ａ关于 P1,…,Pn 的一个完全指派，其中 Ui 或为Ｔ或为Ｆ。

如果对于Ａ中部分变元赋以确定值，其余变元没有赋以确定的值，

则这样的一组值称为公式Ａ的关于该变元组的部分指派。

2）使得公式 A 的真值为真的指派称为成真指派；使得公式 A 的真值为假的指派称为成假指派；

3）如果一个命题公式 A 的所有完全指派均为成真指派，则称公式 A 为重言式(永真式)。
如果一个命题公式 A 的所有完全指派均为成假指派，则称公式 A 为矛盾式(永假式)。
既不是永真式，又不是永假式，则称此命题公式是可满足式。

3.3.2 永真式的特点

（１）永真式的否定为永假式（￢Ｔ＝Ｆ）；
           永假式的否定为永真式（￢Ｆ＝Ｔ）。
（２）二个永真式的析取、合取、蕴含、等值等均为永真式。

例如  求（P∧Q）∧﹁P 与（P∨Q）∨﹁P 的真值表。

 

3.4等价式

3.4.1定义

如果对两个公式Ａ，Ｂ不论作何种指派，它们的真值均相同，则称Ａ，Ｂ是逻辑等价的，亦说Ａ等价于Ｂ，记作A ⇔B

例如  P ∨ ¬ P   ⇔  Q ∨ ¬  Q

例如  判断公式A：(P ∨ ¬ Q) ∨ (P ∨ Q) 与 B：(P ∨¬ R) ∨ (P ∨ R) 是否等价

解：列该公式的真值表

 

3.4.2 定理

命题公式A⇔B的充要条件是A↔B为永真式

说明：
①“⇔”为等价关系符。
     Ａ⇔Ｂ表示Ａ和Ｂ有等价关系。
     Ａ⇔Ｂ不为命题公式。
②“↔”为等值联结词（运算符）。
     若Ａ、Ｂ为命题公式，则（Ａ↔Ｂ）也为一命题公式。

例如    证明：  ¬ ¬P ⇔ P
                          P → Q ⇔ ¬ P ∨ Q.
解：列公式的真值表

 

3.4.3 等价式的性质

1）自反性: A ⇔ A.
2）对称性: A ⇔ B，则 B ⇔ A.
3）传递性: A ⇔ B， B ⇔ C，则 A ⇔ C.

3.4.4 常用等价公式

 说明：
（1）上述１7组等价公式的证明方法可用真值表法，即把 ⇔改为 ↔ 所得的命题公式为永真式，则 ⇔ 成立。
（2） Λ、∨、 ↔ 均满足结合律，则在单一用 Λ、∨、 ↔ 联结词组成的命题公式中，括号可以省去。

 

3.4.5置换原则

《定义》给定一命题公式Ｂ，其中P1,P2 ,…,Pn 是Ｂ中的原子命题变元，若
（1）用某些命题公式Ａi代换Ｂ中的一些原子命题变元 Pi；
（2）用命题公式Ａi 代换 Pi，则必须用Ａi代换Ｂ中的所有Pi；
   由此而得到的新的命题公式Ａ称为命题公式Ｂ的代换实例。

讨论定义：
（１）用命题公式只能代换原子命题变元，而不能去代换分子命题公式。
（２）要用命题公式同时代换同一个原子命题变元。
（３）永真式的代换实例仍为永真式；
     反之，若代换实例为永真式时，则不能断定原公式也一定是永真式。

 例１  设Ｂ：Ｐ→（ ¬ QΛＰ）.
  现用（Ｒ↔Ｓ）代换Ｂ中的Ｐ，得
        Ａ：(Ｒ↔Ｓ)→( ¬ QΛ(Ｒ↔Ｓ))
则Ａ是Ｂ的代换实例；
而Ａ’：(Ｒ↔Ｓ)→(¬ QΛＰ)不是B的代换实例。

例２  Ｐ→ ¬Ｑ的代换实例有：
     (ＲΛ ¬Ｓ)→ ¬Ｍ，
     (ＲΛ ¬Ｓ)→Ｐ，
     Ｑ→ ¬ (Ｐ→ ¬Ｑ)等.
所以，一个命题公式的代换实例有无限个。

下面讨论取代过程（置换规则）：
《定义》给定一命题公式 A，设 A’是 A 的任何部分。如果 A’也是一个命题公式，则称 A’是 A 的 子命题公式。
《替换规则定理》给定一命题公式 A，设 A’是 A 的子公式。设 B’是一命题公式，如果 A’⇔ B’，并且用B’取代 A 中 的 A’，从而生成一新的命题公式 B,则有 A ⇔ B。
注：从定理可见，一个命题公式A，经多次取代，所得到的新公式与原公式等价。

例1   证明输出律：
Ｐ→(Ｑ→Ｒ)  ⇔ (ＰΛＱ)→Ｒ
证明：Ｐ→(Ｑ→Ｒ) ⇔ Ｐ→(¬Ｑ∨Ｒ)
                  ⇔ ¬Ｐ∨ (¬Ｑ∨ Ｒ)
                  ⇔ ¬(ＰΛＱ) ∨Ｒ
                  ⇔ (ＰΛＱ)→Ｒ
真值表证明法

 

例2：证明：
(  (Ｐ∨Ｑ) Λ ¬ ( ¬ＰΛ ( ¬Ｑ∨ ¬Ｒ) )  ) ∨ ( ¬ＰΛ ¬Ｑ)  ∨  (¬ＰΛ ¬Ｒ)为一永真式。
证明：原式
⇔ (  (Ｐ∨Ｑ) Λ ¬ ( ¬ＰΛ ¬( ＱΛＲ) )  ) ∨ ¬( Ｐ∨ Ｑ) ∨ ¬(Ｐ∨Ｒ)
⇔ (  (Ｐ∨Ｑ) Λ  ( Ｐ∨ ( ＱΛＲ) )  )∨ ¬( Ｐ∨ Ｑ) ∨ ¬(Ｐ∨Ｒ)
⇔ (  (Ｐ∨Ｑ) Λ  ( Ｐ∨ ( ＱΛＲ) )  ) ∨ ¬( Ｐ∨ Ｑ) ∨ ¬(Ｐ∨Ｒ)
⇔(  (Ｐ∨Ｑ) Λ  ( (Ｐ∨Ｑ) Λ (Ｐ∨Ｒ) )  ) ∨ ¬ (  ( Ｐ∨ Ｑ) Λ (Ｐ∨Ｒ)   )
⇔ (  (Ｐ∨Ｑ) Λ (Ｐ∨Ｒ)  ) ∨ ¬ (  ( Ｐ∨ Ｑ) Λ (Ｐ∨Ｒ)   )
⇔ T
∵它是Ｐ Λ ¬Ｐ（永真式）的代换实例，永真式的代换实例仍为永真式

 

3.4.6对偶原理

《定义》给定两个限定性命题公式(仅含¬，∧，∨) A和A*，若用∨代换∧，用∧代换∨，用T代换F，用F代换T。代换之后，一个命题公式可由另一个命题公式得来，则称 A和A* 互为对偶式，而联结词 ∧和∨ 也是互为对偶的。

讨论定义：
(1)若命题公式中有联结词 →，↔，则必须把其化成由联结词Λ，∨，¬ 组成的等价的命题公式，然后求它的对偶式；
(2)在写对偶式时，原命题公式中括号不能省去，且必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。

例1：求(P→Q)Λ(P→R)的对偶式。
解：(¬P∨Q)Λ(¬P∨R)
对偶式：(¬PΛQ) ∨ (¬PΛR)
例2：求(ＰΛＱ)∨Ｒ的对偶式。
解: 对偶式： （Ｐ∨Ｑ）ΛＲ
注： (ＰΛＱ)∨Ｒ的对偶式必须写成（Ｐ∨Ｑ）ΛＲ，而不能写成Ｐ∨ＱΛＲ。

定理1:设A和A*是对偶式，P1,P2,…,Pn是出现在A和A*中的所有原子命题变元,则有
        ¬A(P1,P2,…,Pn) ⇔ A*(¬P1,¬P2,…,¬Pn)
        A(¬P1,¬P2,…,¬Pn) ⇔ ¬A*(P1,P2,…,Pn)

注  不难看出，一个命题公式的否定等价于它的对偶式，且用变元的否定代替每一个变元。

定理2:(对偶定理)若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若 A⇔B，则 A * ⇔B *。

结论：（１）和（２）是互为对偶的。

 

3.5 永真蕴含式

3.5.1 定义

命题公式Ａ称为永真蕴含命题公式Ｂ，当且仅当Ａ→Ｂ是一个永真式，记作：Ａ⇒Ｂ

 说明：“Ａ⇒Ｂ”读作“Ａ永真蕴含Ｂ”，  “Ａ蕴含Ｂ”，  “Ａ能推得Ｂ”     “⇒ ”是关系符，Ａ⇒ Ｂ不是命题公式。

例如     证明：Ｐ⇒ Ｐ∨Ｑ； ＰΛＱ⇒ P
方法1：列出真值表
证明：Ｐ→(Ｐ∨Ｑ)和(ＰΛＱ)→Ｐ为永真式.

方法2：可用等价公式证

3.5.2 定理

设Ａ、B是两个命题公式，则Ａ⇔Ｂ的充要条件是Ａ⇒Ｂ且Ｂ⇒ Ａ。

3.5.3 常用的永真蕴含式

 

3.5.4 证明方法

证明上述永真蕴含式的方法有三种：
(1)把“⇒”关系符改为“→”联结词，证明它为永真式。
   (a)真值表法
   (b)命题演算法

(2)＊找出使单条件命题的前件为“Ｔ”的所有真值指派，试看能否导致后件均为“Ｔ”，若为“Ｔ”，则永真蕴含关系式“⇒”成立。

例如   证明假言推理 :ＰΛ(Ｐ→Ｑ)  ⇒ Ｑ.
证：前件为“Ｔ”的所有指派为:
Ｐ、 (Ｐ→Ｑ)均为“Ｔ”，
Ｐ→Ｑ为“Ｔ”，
∵Ｐ为“Ｔ”，
∴Ｑ也应为“Ｔ” ，
∴ＰΛ(Ｐ→Ｑ)  ⇒ Ｑ成立。

(3)＊找出使单条件命题的后件均为“Ｆ”的所有真值指派，试看前件的所有真值是否也为Ｆ”，若是，则永真蕴含关系式“⇒”成立。

例如   证明拒绝式 : ¬ ＱΛ (Ｐ→Ｑ)  ⇒  ¬ Ｐ.
证：后件为“Ｆ”的所有真值指派是：
Ｐ为“Ｔ”，
代入前件得
(i)若Ｑ为Ｔ，则¬ＱΛ (Ｐ→Ｑ)为“Ｆ”；
(ⅱ)若Ｑ为Ｆ，则¬ＱΛ (Ｐ→Ｑ)为“Ｆ”；
∴ ¬ＱΛ (Ｐ→Ｑ)  ⇒  ¬Ｐ成立.

注：若后件简单则可选用(3)；若前件简单则可选用(2)。二种方法是互为独立的，只需使用其中一种证明就行。

讨论一下永真式，可得出三个结论：
(1)若一个命题公式等价于一个永真式，则该公式一定为永真式。
(2)若一个永真的命题公式永真蕴含一个命题公式，则此命题公式一定也为永真式。
(3)若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。

3.5.5 定理

定理：给定命题公式Ａ、Ｂ、Ｃ，若Ａ⇒Ｂ，且Ｂ⇒Ｃ，则Ａ⇒Ｃ

推论：若Ａ⇒ B1 ，B1 ⇒ B2，…，Bm ⇒Ｂ， 则Ａ⇒Ｂ

定理：给定命题公式Ａ、Ｂ、Ｃ，若A⇒B、A⇒C，则  A ⇒ B∧C

定义：设H1,H2, …,Hm,Ｑ均为命题公式，若（H1 Λ H2  Λ … Λ H ） ⇒Ｑ，则称H1,H2, …,Hm共同蕴含Ｑ，并记作：H1,H2, …,Hm ⇒Ｑ.
定理：若 (H1 Λ H2  Λ … Λ Hm)，P  ⇒ Ｑ，则 (H1 Λ H2  Λ … Λ Hm)  ⇒ (P →Ｑ).

3.6 范式

3.6.1 定义

3.6.1.1 问题引出

如何判定命题公式为永真式、永假式和可满足的呢？
如何判定两个命题公式等价？

归纳起来有三种方法：
(1)真值表法：对于变元的所有真值指派，看对应命题公式的真值。
(2)命题演算方法：化简命题公式至最简式，看是否存在与（Ｐ∨ ¬Ｐ）或（Ｐ∧ ¬Ｐ）等价，若不则为可满足的。
(3)范式方法：本节就介绍此法。

#

什么叫范式

把命题公式化归为一种标准的形式，称此标准形式为范式。

#

什么叫判定

以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类问题，统称为判定问题。

#

讨论范式和主范式的目的就是为了进行判定。

 

3.6.1.2 基本积和基本和

##定义：设命题变元为：Ｐ、Ｑ、Ｒ，则：析取式（Ｐ∨Ｑ∨Ｒ）称为“和”； 合取式（Ｐ∧Ｑ∧Ｒ）称为“积”。

##定义：命题公式的变元和变元的否定之积称为基本积；而变元和变元的否定之和称为基本和。

　　　　“基本和”或“基本积”中的子公式，称为此基本积（和）的因子。
例如：设Ｐ、Ｑ为二个命题变元，则：
基本和：Ｐ∨Ｐ，Ｑ∨Ｑ， ¬Ｐ∨Ｑ， ¬Ｑ∨ ¬Ｐ，Ｐ∨Ｑ，Ｐ∨ ¬Ｑ；
基本积：Ｐ∧Ｐ，Ｑ∧Ｑ， ¬Ｐ∧Ｑ， ¬Ｑ∧ ¬Ｐ，Ｐ∧Ｑ，Ｐ∧ ¬Ｑ。
例如： 基本积  ¬Ｑ∧Ｐ∧  ¬Ｐ的因子有：¬Ｑ、Ｐ、  ¬Ｐ、  ¬Ｑ∧Ｐ、Ｐ∧  ¬Ｐ……

##定理：一个“基本积” 必定是永假式，其充要条件是，它至少包含一对因子，且其中一个是另一个的否定。
##定理：一个“基本和” 必定是永真式 ，其充要条件是，它至少包含一对因子，且其中一个是另一个的否定。
例如： 基本和 ¬Ｑ∨Ｐ∨ ¬Ｐ的因子有：¬Ｑ、Ｐ、 ¬Ｐ、 ¬Ｑ∨Ｐ、Ｐ∨ ¬Ｐ……

 

3.6.1.3 析取范式和合取范式

##定义：设与给定命题公式  A 等价的一个公式，如果其是由基本积之和组成，

则称它为命题公式  A的析取范式。并记为：A ⇔ P1∨ P2 ∨，…， ∨ Pn

其中P1，P2 ，…，Pn均为基本积。

##定义：设与给定命题公式  A 等价的一个公式，如果其是由基本和之积组成，

则称它为命题公式  A的合取范式。并记为：A ⇔ Q1∧ Q2∧，…，∧Qn

其中Q1，Q2 ，…，Qn均为基本和。

 

3.6.1.4主析取范式和主合取范式

##定义：在ｎ个变元的基本积中，若每个变元及其否定并不同时存在，

　　　　且二者之一必出现一次且仅出现一次，则称此基本积为极小项。

对一个命题变元讲，极小项有2¹=2个，即：Ｐ、 ¬Ｐ

对于二个命题变元，极小项有2²=4个，即：Ｐ∧Ｑ、 ¬Ｐ∧Ｑ、Ｐ∧ ¬Ｑ、 ¬Ｐ∧ ¬Ｑ

对三个命题变元讲，极小项有23=8个，即：Ｐ∧Ｑ∧Ｒ、Ｐ∧Ｑ∧ ¬Ｒ、Ｐ∧ ¬Ｑ∧Ｒ、Ｐ∧ ¬Ｑ∧ ¬Ｒ、¬Ｐ∧Ｑ∧Ｒ、 ¬Ｐ∧Ｑ∧ ¬Ｒ、 ¬Ｐ∧ ¬Ｑ∧Ｒ、     ¬Ｐ∧ ¬Ｑ∧ ¬Ｒ

推广到一般：ｎ个命题变元构成的不同极小项有2ⁿ个（n∈I₊）。使得每个极小项为真的赋值仅有一个。

##定义：给定一命题公式，其仅含有极小项析取的等价式称为给定命题公式的主析取范式。

例如：Ｐ→Ｑ⇔ ( ¬Ｐ∧ ¬Ｑ)∨ ( ¬Ｐ∧Ｑ) ∨ (Ｐ∧Ｑ)

#

##定义：在ｎ个变元的基本和中，若每个变元与其否定并不同时存在，

　　　　且二者之一必出现一次且仅出现一次，则称这种基本和为极大项。

对于两个变元Ｐ,Ｑ，其极大项有 2²=4 个，即（Ｐ∨Ｑ）、（Ｐ∨ ¬Ｑ）、（ ¬Ｐ∨Ｑ）、（ ¬Ｐ∨ ¬Ｑ）
推广到一般：ｎ个命题变元构成的不同极大项有2ⁿ个（n∈I₊）。

 ##定义：给定一命题公式，其仅含有极大项合取的等价式称为给定命题公式的主合取范式。

^为合取，两边都满足叫合取，中间部分主要，中间部分是合取，用^连接叫主合取范式

例如：Ｐ∧（Ｐ→Ｑ）∨Ｑ ⇔ （Ｐ∨Ｑ）∧（ ¬Ｐ∨Ｑ）

 

3.6.2 求范式

 3.6.2.1 求公式的析取范式和合取范式的步骤

(1)利用等价公式，化去联结词“→”、“↔” ，把命题公式变为与其等价的且用{¬ ，∧，∨}表达的公式；

例1: Ｐ→Ｑ ⇔ ¬Ｐ∨Ｑ，
　　Ｐ↔Ｑ ⇔ （Ｐ∧Ｑ）∨（ ¬Ｐ∧ ¬Ｑ）⇔ （ ¬Ｐ∨Ｑ）∧（Ｐ∨ ¬Ｑ）

(2)将“¬”深入到原子命题变元之前，并使变元之前最多只有一个“¬”词；

例2: ¬ （ ¬Ｐ∨ ¬Ｑ） ⇔ ¬ ¬Ｐ∧ ¬ ¬Ｑ
　　⇔Ｐ∧Ｑ

(3)利用“∧”与“∨”的分配律，将公式化为析取范式（合取范式）。

(4)去掉永假项（永真项）得最简析取范式（最简合取范式）。

例3 求公式 ¬ (P∨Q) ↔(P∧Q) 的析取范式。

解 原式
⇔ (¬ （Ｐ∨Ｑ） ∧ （Ｐ∧Ｑ）) ∨ (（Ｐ∨Ｑ）∧ ¬ （Ｐ∧Ｑ）)
—–（1）化去↔词

⇔  (¬Ｐ∧ ¬Ｑ∧ Ｐ∧Ｑ) ∨ (（Ｐ∨Ｑ）∧ （¬Ｐ∨ ¬Ｑ）)
——（2）“¬”深入到变元前，并最多保留一个

⇔ (（Ｐ∨Ｑ）∧ （¬Ｐ∨¬Ｑ）)

⇔ (Ｐ∧¬Ｐ）∨（ Ｐ∧ ¬Q）∨ (Q∧ ¬P) ∨ （Ｑ∧ ¬Ｑ）
——（3）“∧”对“∨”的分配，化为析取范式

⇔（Ｐ∧ ¬Ｑ） ∨ （¬Ｐ∧Ｑ）
——（4）最简析取范式

注：(1)从上例看出，一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等价的。

(2)若一个命题公式的析取范式中各基本积均为永假式，则该公式也一定为永假式。(可用来判定命题公式 A是否为永假式)

即，A ⇔ P1∨ P2 ∨…∨ Pn    (其中P1，P2 ，…，Pn均为基本积)
则，当P1 ⇔ P2⇔ … ⇔ Pn⇔ F时，A一定为永假式。

例4（析取范式）：Ｐ↔ ¬Ｐ
⇔（Ｐ∧ ¬Ｐ）∨（ ¬Ｐ∧Ｐ）
⇔ Ｆ 永假式

例5：求Ｑ∨ ¬(Ｐ→Ｑ)∨¬ (Ｐ∨Ｑ)的合取范式.

解：原式

⇔ Ｑ∨ ¬ (¬Ｐ∨Ｑ)∨ ¬ (Ｐ∨Ｑ)
——化去“→”词
⇔ Ｑ∨ (Ｐ∧ ¬Ｑ) ∨ ( ¬Ｐ∧ ¬Ｑ)
——“”深入到变元前，并最多保留一个
⇔  ( (Ｑ∨Ｐ) ∧ (Ｑ∨ ¬Ｑ) ) ∨ (¬Ｐ∧ ¬Ｑ)
——“∨”对“∧”的分配
⇔  (Ｑ∨Ｐ) ∨ (¬Ｐ∧ ¬Ｑ)
⇔  (Ｑ∨Ｐ∨ ¬Ｐ) ∧ (Ｑ∨Ｐ∨ ¬Ｑ)
⇔ Ｔ（最简合取范式）

注：(1)给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。

(2)若一个命题公式的合取范式中的各基本和的真值为“Ｔ”，则该命题公式一定是永真式。(可用来判定命题公式 是否为永真式)

即，A ⇔ P1 ∧ P2 ∧ … ∧ Pn   (其中P1，P2 ，…，Pn均为基本和)
则，当P1 ⇔ P2 ⇔ … ⇔ Pn ⇔ T时，A一定为永真式。

例6（合取范式）：（Ｐ ↔Ｐ）
⇔  （ ¬Ｐ∨Ｐ）∧（Ｐ∨ ¬Ｐ）
⇔    Ｔ

3.6.2.2求主析取范式

【法一】

定理：在真值表中，一个公式的真值为Ｔ的指派所对应的极小项的析取，即为此公式的主析取范式。

例1：求Ｐ→Ｑ、Ｐ∨ ¬Ｑ、 ¬（Ｐ∧Ｑ）、Ｐ∧ ¬Ｑ的主析取范式.

则可直接写出各命题公式的主析取范式：
Ｐ→Ｑ⇔ ( ¬Ｐ∧ ¬Ｑ)∨ ( ¬Ｐ∧Ｑ) ∨ (Ｐ∧Ｑ)
Ｐ∨¬Ｑ⇔ (¬Ｐ∧¬Ｑ) ∨ (Ｐ∧¬Ｑ) ∨ (Ｐ∧Ｑ)
¬(Ｐ∧Ｑ) ⇔¬(¬Ｐ∧¬Ｑ) ∨ (¬Ｐ∧Ｑ) ∨ (Ｐ∧¬Ｑ)
Ｐ∧ ¬Ｑ⇔ (Ｐ∧¬Ｑ)

讨论此定理：
(1)只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，

　　其方法是找出该公式为“Ｔ”的行，对应写出极小项的析取式，且一定是唯一的。

(2)若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2ⁿ个极小项。

(3)若两个命题公式对应的主析取范式相同，则此两个命题公式一定是等价的。

(4)命题公式的主析取范式中极小项的个数一定等于其对应真值表中真值为“Ｔ”的个数。

【法二】

不用真值表，直接求命题公式主析取范式的方法，分四步：

(1)将命题公式化为与其等价的析取范式；
(2)除去永假项，合并基本积中的相同项（例：Ｐ∧Ｐ∧Ｑ⇔Ｐ∧Ｑ），变为最简析取范式。
(3)利用添变元的方法，将所有基本积变为极小项。

例如 设有二个变元Ｐ、Ｑ，利用“∧”对“∨”的分配律添项：
Ｐ ⇔ Ｐ∧（Ｑ∨ ¬Ｑ） ⇔ （Ｐ∧Ｑ）∨（Ｐ∧ ¬Ｑ）
Ｑ ⇔ Ｑ∧（Ｐ∨ ¬Ｐ）⇔（Ｐ∧Ｑ）∨（ ¬Ｐ∧Ｑ）

(4) 合并相同的极小项，只保留一项。

例1: 求（Ｐ∧（Ｐ→Ｑ））∨Ｑ的主析取范式。

解：原式 ⇔（Ｐ∧ ¬Ｐ）∨（Ｐ∧Ｑ）∨Ｑ
—-（1）化为析取范式
⇔ （Ｐ∧Ｑ）∨Ｑ
—-（2）消去永假项，变为最简析取范式

⇔ （Ｐ∧Ｑ）∨（Ｑ∧（Ｐ∨¬Ｐ））
⇔ （Ｐ∧Ｑ）∨（Ｐ∧Ｑ）∨（ ¬Ｐ∧Ｑ）
—-（3）添项

⇔ （Ｐ∧Ｑ）∨（ ¬Ｐ∧Ｑ）     主析取范式

—-（4）合并相同极小项

 

3.6.2.3求主合取范式

【法一】

定理：在真值表中，一个公式的真值为F的指派所对应的极大项的合取，即为此公式的主合取范式。

注：在真值表中真值为“Ｆ”的个数等于主合取范式中极大项的个数。

例如 求（Ｐ→Ｑ）、（Ｐ∨Ｑ）、 ¬（Ｐ∧Ｑ）、（Ｐ∧Ｑ）的主合取范式。

直接写出其主合取范式：
（Ｐ→Ｑ） ⇔ （ ¬Ｐ∨Ｑ）（极大项）主合取范式

　　           ⇔ （ ¬Ｐ∧ ¬Ｑ）∨（ ¬Ｐ∧Ｑ）∨（Ｐ∧Ｑ）主析取范式

 

注：

（１）与命题公式等价的主合取范式中极大项的个数等于其真值表中真值为“Ｆ”的个数。

　　　由真值表找极大项的方法为：将表中真值为“Ｆ”的对应变元指派中，把变元写成否定，把变元的否定写成变元。
（２）只要命题公式不是永真式，则一定可以写出与其等价的唯一的主合取范式。
（３）若命题公式为含有ｎ个变元的永假式，则主合取范式包含了2n个极大项的合取式。

（４）可用主合取范式判定两个命题公式是否等价。
（５）已知一个命题公式的主析取范式，则一定可以直接写出与其等价的主合取范式来。反之也行。

（６）对于有ｎ个变元的命题公式，则一定有：主析范式极小项数＋主合范式极大项数＝ 2ⁿ.

 

【法二】

不用真值表求一命题公式主合取范式的方法：

(1)将命题公式化为与其等价的合取范式；
(2)除去永真项，合并基本和中的相同项（例：Ｐ∨Ｐ∨Ｑ⇔Ｐ∨Ｑ），变为最简合取范式。
(3)利用添变元的方法，将所有析取项均变为极大项。

例如：Ｐ、Ｑ为两个变元，即：
Ｐ⇔Ｐ∨（Ｑ∧ ¬Ｑ）⇔ （Ｐ∨Ｑ）∧（Ｐ∨ ¬Ｑ）

(4) 合并相同的极大项，只保留一项。

例1：求Ｐ∧（Ｐ→Ｑ）∨Ｑ的主合取范式。

解：原式 ⇔Ｐ∧（ ¬Ｐ∨Ｑ）∨Ｑ
⇔ （Ｐ∧ ¬Ｐ）∨ （Ｐ∧Ｑ）∨Ｑ
⇔ （Ｐ∧Ｑ）∨Ｑ
⇔ （Ｐ∨Ｑ）∧Ｑ
⇔ （Ｐ∨Ｑ）∧（Ｑ∨ （ ¬Ｐ∧ Ｐ））
⇔ （Ｐ∨Ｑ）∧（ ¬Ｐ∨Ｑ） ∧（ Ｐ∨Ｑ）
⇔ （Ｐ∨Ｑ）∧（ ¬Ｐ∨Ｑ）.

 

3.6.3 主范式排序（列）的唯一性

3.6.3.1 极小项及其编码

为了确保主范式的唯一性，两个安排：

（a）固定各命题变元的位置次序；

（b）对极小项、极大项安排一个次序。

对于有ｎ个变元的命题公式，则最多可有2ⁿ个极小项，用m0， m1 ，… ， m_2ⁿ-1来表示。

例如  给定三个变元，且Ｐ、Ｑ、Ｒ的位置已排定，则其极小项的次序为：

从而，可归纳出一求极小项m_(i)十的方法：
(a)把(i)_十变换成等价的(J0J1…Jn-1)_二；
(b)由二进制写出其对应的极小项。

例1：设一命题公式有五个变元，P0,P1,P2,P3,P4（次序已定），

则必可写出2⁵=32个极小项，下面列出m₍₁₁₎₊和m₍₁₈₎₊的极小项表示：

 

例2：求（Ｐ∧Ｑ）∨（ ¬Ｐ∧Ｒ）的极小项编码表达式：（设Ｐ、Ｑ、Ｒ次序已定）

 

3.6.3.2 极大项及其编码

对于有ｎ个变元的命题公式，则最多可有2ⁿ个极大项，用M0，M1，…，M_2ⁿ-1表示。

例如 给定三个变元，且Ｐ、Ｑ、Ｒ的位置已排定，则其极大项的次序为：

 

 

求极大项的方法：
(a)把(i)_十变换成等价的(J0J1…J_n-1)_二；
(b)由二进制写出其对应的极大项。

例1：求（Ｐ∧Ｑ）∨（ ¬Ｐ∧Ｒ）的极大项编码表示（设Ｐ、Ｑ、Ｒ次序已定）

 

例2：写出（Ｐ∨ ¬Ｑ）的主析取和主合取编码表示。

 

由真值表可知：
Ｐ∨¬Q ⇔ ∑ 0,2,3
　　　 ⇔ ∏ 1

主析范式为：
（ ¬Ｐ∧ ¬Ｑ）∨（Ｐ∧ ¬Ｑ）∨（Ｐ∧Ｑ）
主合范式为：P ∨ ¬ Q
且P ∨ ¬ Q ⇔ （ ¬Ｐ∧ ¬Ｑ）∨（Ｐ∧ ¬Ｑ）∨（Ｐ∧Ｑ）

 4.证明方法

4.1定义

在命题逻辑中，除了利用等价关系来判定问题之外，还可以用推理来判定问题。

推理 ：判定由给定前提A是否能推导出某个结论B，
　　　即判定命题 A 是否永真蕴含命题 B。

推论规则：确定论证有效性的判据。
　　　　其依据是常用的永真蕴含式和等价公式。

　　推理规则是正确推理的依据，而正确推理对任何一门学科都非常重要。

　　按公认的推理规则，从前提集合中推导出一个结论来，这样的推导过程称为演绎，或者叫形式证明。

　　根据推理规则推导出来的任何结论称为有效结论。

　　在任何论证中，若认定前提是真的，并且从前提集合推导出结论的论证是遵守了推理规则的，则我们称此结论是合法的。

 

4.2证明方法

证明方法，归纳分成三类：

（一）真值表技术；
（二）推理规则；
（三）间接证明法

4.2.1 真值表技术

1）依据

真值表技术的主要依据是“→”的真值表定义。
若Ｐ⇒Ｑ当且仅当（Ｐ→Ｑ）为永真式。

 2）定义

定义：给定两个命题公式 A 和 B，当且仅当Ａ→Ｂ是一个永真式，
　　才可以说Ｂ是从Ａ推导出来的（A ⇒ B），或称Ｂ是前提Ａ的有效结论。

定义：设H1，H2，… ，Hm，C 都是命题公式，

　　当且仅当 H1 ∧ H2 ∧ … ∧ Hm  ⇒ C ，则称 C是前提集合{H1，H2，… ，Hm}的有效结论 。

 3）方法

从给定真值表判断 H1 ∧ H2 ∧ … ∧ Hm ⇒ C ，常用的判断方法有两种：
（１）检查真值表中 H1，H2，… ，Hm 全部为“Ｔ”的所有行，

　　看结论Ｃ是否也均为“Ｔ”，若Ｃ均为“Ｔ”，则结论有效，否则结论无效。

（２）看结论Ｃ为“Ｆ”的所有行，检查每行前提H1，H2，… ，Hm中是否至少有一个为Ｆ，

　　若有“Ｆ”，则结论有效；否则结论无效。

例如 试证明下列结论是否有效（画出真值表）.

 

由真值表可见：

（１）Ｐ，Ｐ→Ｑ⇒Ｑ 有效
（２）Ｐ→Ｑ， ¬Ｐ⇒Ｑ 无效
（３）Ｐ→Ｑ， ¬ （Ｐ∧Ｑ） ⇒ ¬Ｐ 有效
（４） ¬Ｐ，Ｐ↔Ｑ⇒ ¬ （Ｐ∧Ｑ） 有效

（５）Ｐ→Ｑ，Ｑ⇒Ｐ 无效

真值表技术在前提数目较多时，是比较繁琐的。下面介绍基于推理规则的方法。

 

 4.2.2推理规则

1）依据

从这节开始，我们只讨论命题论证的有效性，而不去讨论命题的真假值；
∴在推理规则中不需要有真值表，也不需要对命题进行真值指派。

推理规则的依据是常用的永真蕴含式和等价公式。

 

 2）最常用的推理规则

 

3）推理公式构造的两个规则:

•P 规则：在推导的任何步骤上，都可以引入前提。
•T 规则：在推导过程中，如果前面有一个或多个命题公式永真蕴含命题公式 S，

　　　　那么就可以把公式 S 引入推导过程之中。

例1 证明： P→ Q，Q→R，P ⇒ R.

证明 推理过程如下：

 

也可以这样来推理：

 

例2 证明构造性二难推理：

(P→ Q)∧(R→ S) ∧ (P∨R) ⇒ Q∨S

证明 推理过程如下：

4）条件证明的 CP 规则：
如果能从Q和给定的前提集合P中推导出R来，
则就能从前提集合P中推导出（Q → R）来。
即：若 P∧Q ⇒ R，则 P ⇒ (Q → R).

注：当待证的有效结论是一个如 Q→R 类型的条件命题时，

我们可以将有效结论中的前提 Q 单独提出来加到前提中去，

然后证明剩下的后件 R 是附加了前提之后的新的一组前提P∧Q的有效结论。

这种附加前提的证明方法——条件证明的CP规则。

证明 因为：P →(Q →R) ⇔ (P ∧ Q) →R
∴要证明 P ⇒ (Q→ R)
即 P → (Q → R)为永真式
即 (P ∧ Q) → R 为永真式.
即 (P ∧ Q) ⇒ R .

 

例1： P →(Q → S)， ¬ R∨P，Q ⇒ R → S

证明 推理过程如下：

 

例2： P → Q ⇒ P → P ∧ Q

证明 推理过程如下：

 

4.2.3间接证明法（反证法、归谬法）

定义：给出命题公式 H1，H2，…，Hm，
　　若H1∧H2∧ … ∧Hm具有真值为“T”，则称命题公式集合{H1，H2，…，Hm} 是一致的。
　　否则称{H1，H2，…，Hm}是非一致的。

定理：设命题公式集合{H1，H2，…，Hm}是一致的，同时设C是一个命题公式，

　　如果前提集合{H1，H2，…，Hm， ¬ C}是非一致的，则一定有H1，H2，…，Hm ⇒ C 成立。

证 ∵条件{H1，H2，…，Hm， ¬ C}是非一致的，
∴ H1∧H2∧ … ∧Hm ∧ ¬ C必定为永假式。
而H1∧H2∧ … ∧Hm是一致的，即为永真式，从而只有¬ C为永假式，则C 一定为永真式，
故H1，H2，…，Hm ¬ C成立。

例1 证明： ¬ P ∧ ¬ Q ⇒ ¬ (P ∧ Q)

 

 例2    证明： R → ¬ Q, R∨S , S → ¬ Q, P → Q ⇒ ¬ P

 

讨论：由上例可见，间接证明法在结论较为简单的条件下，使用是比较方便的，

　　实际上间接证明法也可以用CP规则代替它。

习题：前提： ¬P→Q;     ¬R ∨ ¬S Q→S;   R
　　　结论：P

 

小结 学习命题逻辑要注意以下几点：
（1）弄清命题与陈述句的关系。
（2）弄清由5种基本联结词联结的复合命题的逻辑关系及其真值。特别是要弄清蕴含式“P → Q” 的逻辑关系及其真值。
（3）记住常用的蕴含式和等价式，这是学好命题逻辑的关键问题。
（4）会准确地求出给定公式的主析取范式和主合取范式。掌握主析取范式与真值表、成真赋值、主合取范式的关系。

（5）会用多种方法判断公式的类型及判断两个公式是否等价。
（6）掌握推理和判断推理是否正确的方法。

 

命题逻辑的应用实例 例如 一位计算机工作者协助公安人员审查一起谋杀案，经调查，他认为下列情况均是真的。 (1)会计张某或邻居王某谋害了厂长。 (2)如果会计张某谋害了厂长，则谋害不可能发生在半夜。 (3)如果邻居王某的证词不正确，则在半夜时房里灯光未灭。 (4)如果邻居王某的证词是正确的，则谋害发生在半夜。 (5)在半夜房子里的灯光灭了，且会计张某曾贪污过。 解：设 P：会计张某谋害了厂长 Q：邻居王某谋害了厂长 N：谋害发生在半夜 O：邻居王某的证词是正确的 R：半夜时房子的灯光灭了 A：会计张某曾贪污过 列出条件公式： (1) P∨Q  (2) P → ¬ N  (3)¬ O → ¬ R (4) O →  N (5) R ∧ A 推导过程为： 结论：邻居王某谋害了厂长.   习题 已知：若A有罪，则B、C有罪； 或者A有罪，或者B有罪； 或者B无罪，或者C无罪； 问：谁有罪？ 解 列出条件公式： (1) A → B ∧C (2) A∨B (3) ¬ B ∨ ¬ C 推导过程为： 结论：B有罪.