Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,1
1.1.2 命题演算
Propositional Equivalences
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,2
1、命题 (Proposition)
2、从简单命题 (atomic proposition)到复合命题 (compositional proposition)
3、从命题常量 (propositional constant)到命题变量 (propositional variable)
4、从复合命题 (compositional proposition)到命题公式 (propositional formulas)
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,3
永真命题公式（ Tautology）
公式中的命题变量无论怎样代入，公式对应的真值恒为 T。
永假命题公式（ Contradiction)
公式中的命题变量无论怎样代入，公式对应的真值恒为 F。
可满足命题公式（ Satisfaction）
公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为 T。
一般命题公式（ Contingency）
既不是永真公式也不是永假公式。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,4
EXAMPLE 1
We can construct examples of tautologies and
contradictions using just one proposition,Consider the
truth tables of p∨ p and p∧ p,shown in Table 1,
Since p∨ p is always true,it is a tautology,Since p∧ p
is always false,it is a contradiction.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,5
Table 1
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,6
DEFINITION 2
The propositions p and q are called logically
equivalent if p q is a tautotogy,The notation p q
denotes that p and q are logically equivalent.
逻辑等值，或逻辑等价
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,7
EXAMPLE 2
Show that (p∨ q) and p∧ q are logically
equivalent,This equivalence is one of De Morgan's laws for
propositions,named after the English mathematician
Augustus De Morgan,of the mid-nineteenth century.
Solution,
The truth tables for these propositions are displayed in Table 2,
Since the truth values of the propositions (p∨ q) and p∧ q
agree for all possible combinations of the truth values of p and q,
it follows that these propositions are logically equivalent.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,8
Table 2
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,9
EXAMPLE 3
Show that the propositions p→q and p ∨ q are
logically equivalent.
Solution,We construct the truth table for these
propositions in Table 3,Since the truth values of p∨ q
and p→q agree,these propositions are logically equivalent.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,10
Table 3
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,11
EXAMPLE 4
Show that the propositions p∨ (q∧ r) and
(p∨ q)∧ (p∨ r) are logically equivalent.This is the
distributive law of disjunction over conjunction.
Solution,
We construct the truth table for these propositions in Table
4,Since the truth values of p∨ (q∧ r) and (p∨ q)∧ (p∨ r)
agree,these propositions are logically equivalent.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,12
Table 4
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,13
基本逻辑等价定理：
对于任意的命题公式 p,q,r，下面的命题公式是等价的。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,14
Table 5
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,15
Table 6
p ∨ q T
p ∧ q F
p ∨ (p ∧ q) p Absorption Laws/吸收律
p ∧ (p ∨ q) p
p → q p ∨ q
p q (p → q) ∧ ( q → p)
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,16
EXAMPLE 5
Show that (p∨ ( p∧ q)) and p∧ q are
logically equivalent.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,17
EXAMPLE 6
Show that (p∧ q) → (p ∨ q) is a tautology.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,18
判断命题公式逻辑等价的方法：
1、真值表
2、命题公式的演算基本等值定理；
公式的代入不变性；
等值关系的传递性。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,19
命题公式逻辑等价关系的应用：
1、判定是否逻辑等价；
2、判断是否为永真公式或永假公式；
3、命题公式的化简
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,20
Example 7
什麽，如果她不来那么我也不去，没有那回事。
P：她来。
Q：我去。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,21
进一步的思考：
一、命题公式的对偶性及其对偶处理。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,22
限定性命题公式,最多仅含有否定、析取、合取逻辑联结词的命题公式。
命题公式 P的 对偶公式（ Dual）,将 P中的析取联结词换成合取联结词，
合取联结词换成析取联结词，
T换成 F,F换成 T（如果存在的话）。
记为 P*
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,23
对偶原理（ Duality Principle)
设 P,Q是限定性命题公式。如果
P Q
则
P* Q*?
例,A,（ P ∧ Q） ∨ Q
B,P ∨ Q
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,24
进一步的思考：
二、命题公式中的逻辑联接词的极小完备性。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,25
逻辑联接词组是 功能完备的
（ Functionally Complete）：
任一个命题公式都能够等价于仅包含这些逻辑联接词联结起来的公式。
逻辑联接词组是 极小功能完备的,
是功能完备的并且不能少一个。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,26
例 2：否定和合取组成的逻辑联结词组是 极小功能完备的。
例 3,否定和析取组成的逻辑联结词组是 极小功能完备的。
例 1：否定、析取、合取组成的逻辑联结词组是功能完备的，但不是 极小功能完备的。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,27
进一步的思考：
三、命题公式的进一步分类。
命题公式的标准化 -----范式
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,28
文字（ literal） /符号（ symbol）：
原子命题或其否定小项（ small item） /合取式（ conjunctive form ）,
若干个文字的合取。
大项（ large item） /析取式（ disjunctive form ）,
若干个文字的析取。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,29
合取范式（ conjunctive normal form):
若干个大项的合取。
析取范式（ disjunctive normal form):
若干个小项的析取。
标准句 (standard sentence)：合取范式或析取范式子句（ clause）,合取范式中的大项或析取范式中的小项。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,30
定理 1：任意一个命题公式都存在与之等价的合取范式和析取范式。
定理的证明思路：
1、化成限定性公式；
2、将否定联结词移到命题变量的前面；
3、消除多余的否定联结词；
4、化成合取范式和析取范式。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,31
定理 1的作用与局限：
1、标准化但仅仅是初步的
# 标准化的形式
# 不唯一性
2、能够判定是否为永真或永假公式但不方便
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,32
定理 2：一个命题公式是永真公式当且仅当与它等价的合取范式的每一个大项中包含了一个命题变量和它的否定；
一个命题公式是永假公式当且仅当与它等价的析取范式的每一个小项中包含了一个命题变量和它的否定；
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,33
令 A（ a1,a2,……,an）包含有 n个变量的公式，
极小项 (extremal ~):小项中恰包含 n个变量或其否定。
极大项 ( extremal ~):大项中恰包含 n个变量或其否定。
主合取范式（ Unique conjunctive normal form):
若干个极大项的合取。
主析取范式（ Unique disjunctive normal form):
若干个极小项的析取。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,34
定理 3：令 A（ a1,a2,……,an）包含有 n个变量的公式，则有：
1、如果 A存在与之等价的主析取范式，则必唯一；
2、如果 A存在与之等价的主合取范式，则必唯一；
3,A是永真公式当且仅当与 A等价的主析取范式恰有 2n个极小项或没有主合取范式；
4,A是永假公式当且仅当与 A等价的主合取范式恰有 2n个极大项或没有主析取范式；
5、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,35
例 6 张先生手中有代号为 A,B,C,D,E的五种股票,根据当前股市情况及张先生本人的经济需求,需要有若干个股票抛出,但又必须满足如下复杂的要求：
（ 1） 若 A抛出,则 B也抛出；
（ 2） B和 C要留一种股票且只能留一种；
（ 3） C和 D要么全抛,要么都不抛；
（ 4） D和 E两种股票中必然有一种或两种要抛出；
（ 5） 若 E抛出,则 A,B也抛出 。
上述五种条件全部满足,问有几种合理的方案供张先生选择 。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,36
小 结
1、命题公式的等价演算
2,命题公式的标准化描述表达、分类、判定、应用
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,37
练 习
Pp19 8(d),29
附加题
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,1
1.1.2 命题演算
Propositional Equivalences
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,2
1、命题 (Proposition)
2、从简单命题 (atomic proposition)到复合命题 (compositional proposition)
3、从命题常量 (propositional constant)到命题变量 (propositional variable)
4、从复合命题 (compositional proposition)到命题公式 (propositional formulas)
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,3
永真命题公式（ Tautology）
公式中的命题变量无论怎样代入，公式对应的真值恒为 T。
永假命题公式（ Contradiction)
公式中的命题变量无论怎样代入，公式对应的真值恒为 F。
可满足命题公式（ Satisfaction）
公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为 T。
一般命题公式（ Contingency）
既不是永真公式也不是永假公式。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,4
EXAMPLE 1
We can construct examples of tautologies and
contradictions using just one proposition,Consider the
truth tables of p∨ p and p∧ p,shown in Table 1,
Since p∨ p is always true,it is a tautology,Since p∧ p
is always false,it is a contradiction.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,5
Table 1
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,6
DEFINITION 2
The propositions p and q are called logically
equivalent if p q is a tautotogy,The notation p q
denotes that p and q are logically equivalent.
逻辑等值，或逻辑等价
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,7
EXAMPLE 2
Show that (p∨ q) and p∧ q are logically
equivalent,This equivalence is one of De Morgan's laws for
propositions,named after the English mathematician
Augustus De Morgan,of the mid-nineteenth century.
Solution,
The truth tables for these propositions are displayed in Table 2,
Since the truth values of the propositions (p∨ q) and p∧ q
agree for all possible combinations of the truth values of p and q,
it follows that these propositions are logically equivalent.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,8
Table 2
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,9
EXAMPLE 3
Show that the propositions p→q and p ∨ q are
logically equivalent.
Solution,We construct the truth table for these
propositions in Table 3,Since the truth values of p∨ q
and p→q agree,these propositions are logically equivalent.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,10
Table 3
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,11
EXAMPLE 4
Show that the propositions p∨ (q∧ r) and
(p∨ q)∧ (p∨ r) are logically equivalent.This is the
distributive law of disjunction over conjunction.
Solution,
We construct the truth table for these propositions in Table
4,Since the truth values of p∨ (q∧ r) and (p∨ q)∧ (p∨ r)
agree,these propositions are logically equivalent.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,12
Table 4
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,13
基本逻辑等价定理：
对于任意的命题公式 p,q,r，下面的命题公式是等价的。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,14
Table 5
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,15
Table 6
p ∨ q T
p ∧ q F
p ∨ (p ∧ q) p Absorption Laws/吸收律
p ∧ (p ∨ q) p
p → q p ∨ q
p q (p → q) ∧ ( q → p)
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,16
EXAMPLE 5
Show that (p∨ ( p∧ q)) and p∧ q are
logically equivalent.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,17
EXAMPLE 6
Show that (p∧ q) → (p ∨ q) is a tautology.
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,18
判断命题公式逻辑等价的方法：
1、真值表
2、命题公式的演算基本等值定理；
公式的代入不变性；
等值关系的传递性。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,19
命题公式逻辑等价关系的应用：
1、判定是否逻辑等价；
2、判断是否为永真公式或永假公式；
3、命题公式的化简
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,20
Example 7
什麽，如果她不来那么我也不去，没有那回事。
P：她来。
Q：我去。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,21
进一步的思考：
一、命题公式的对偶性及其对偶处理。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,22
限定性命题公式,最多仅含有否定、析取、合取逻辑联结词的命题公式。
命题公式 P的 对偶公式（ Dual）,将 P中的析取联结词换成合取联结词，
合取联结词换成析取联结词，
T换成 F,F换成 T（如果存在的话）。
记为 P*
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,23
对偶原理（ Duality Principle)
设 P,Q是限定性命题公式。如果
P Q
则
P* Q*?
例,A,（ P ∧ Q） ∨ Q
B,P ∨ Q
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,24
进一步的思考：
二、命题公式中的逻辑联接词的极小完备性。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,25
逻辑联接词组是 功能完备的
（ Functionally Complete）：
任一个命题公式都能够等价于仅包含这些逻辑联接词联结起来的公式。
逻辑联接词组是 极小功能完备的,
是功能完备的并且不能少一个。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,26
例 2：否定和合取组成的逻辑联结词组是 极小功能完备的。
例 3,否定和析取组成的逻辑联结词组是 极小功能完备的。
例 1：否定、析取、合取组成的逻辑联结词组是功能完备的，但不是 极小功能完备的。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,27
进一步的思考：
三、命题公式的进一步分类。
命题公式的标准化 -----范式
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,28
文字（ literal） /符号（ symbol）：
原子命题或其否定小项（ small item） /合取式（ conjunctive form ）,
若干个文字的合取。
大项（ large item） /析取式（ disjunctive form ）,
若干个文字的析取。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,29
合取范式（ conjunctive normal form):
若干个大项的合取。
析取范式（ disjunctive normal form):
若干个小项的析取。
标准句 (standard sentence)：合取范式或析取范式子句（ clause）,合取范式中的大项或析取范式中的小项。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,30
定理 1：任意一个命题公式都存在与之等价的合取范式和析取范式。
定理的证明思路：
1、化成限定性公式；
2、将否定联结词移到命题变量的前面；
3、消除多余的否定联结词；
4、化成合取范式和析取范式。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,31
定理 1的作用与局限：
1、标准化但仅仅是初步的
# 标准化的形式
# 不唯一性
2、能够判定是否为永真或永假公式但不方便
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,32
定理 2：一个命题公式是永真公式当且仅当与它等价的合取范式的每一个大项中包含了一个命题变量和它的否定；
一个命题公式是永假公式当且仅当与它等价的析取范式的每一个小项中包含了一个命题变量和它的否定；
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,33
令 A（ a1,a2,……,an）包含有 n个变量的公式，
极小项 (extremal ~):小项中恰包含 n个变量或其否定。
极大项 ( extremal ~):大项中恰包含 n个变量或其否定。
主合取范式（ Unique conjunctive normal form):
若干个极大项的合取。
主析取范式（ Unique disjunctive normal form):
若干个极小项的析取。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,34
定理 3：令 A（ a1,a2,……,an）包含有 n个变量的公式，则有：
1、如果 A存在与之等价的主析取范式，则必唯一；
2、如果 A存在与之等价的主合取范式，则必唯一；
3,A是永真公式当且仅当与 A等价的主析取范式恰有 2n个极小项或没有主合取范式；
4,A是永假公式当且仅当与 A等价的主合取范式恰有 2n个极大项或没有主析取范式；
5、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,35
例 6 张先生手中有代号为 A,B,C,D,E的五种股票,根据当前股市情况及张先生本人的经济需求,需要有若干个股票抛出,但又必须满足如下复杂的要求：
（ 1） 若 A抛出,则 B也抛出；
（ 2） B和 C要留一种股票且只能留一种；
（ 3） C和 D要么全抛,要么都不抛；
（ 4） D和 E两种股票中必然有一种或两种要抛出；
（ 5） 若 E抛出,则 A,B也抛出 。
上述五种条件全部满足,问有几种合理的方案供张先生选择 。
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,36
小 结
1、命题公式的等价演算
2,命题公式的标准化描述表达、分类、判定、应用
Propositional Equivalences
命题演算
7/31/2009 11:26 AM Deren Chen,Zhejiang Univ,37
练 习
Pp19 8(d),29
附加题
