《2-数理逻辑之等值式》由会员分享，可在线阅读，更多相关《2-数理逻辑之等值式（50页珍藏版）》请在金锄头文库上搜索。
1、 离散数学 第二讲第二讲数理逻辑之等值式数理逻辑之等值式李昊李昊信息楼信息楼3121二二 命题逻辑等值演算命题逻辑等值演算2第一节第一节 等值式等值式注意： 不是联结词！3 判断方法：判断方法：1。利用真值表。（计算量太大）。利用真值表。（计算量太大）2。利用已知定律。利用已知定律。 利用真值表证明：利用真值表证明： (pq) 和和 p q 逻辑等值，是等值式逻辑等值，是等值式.4Table 2Table 2放在同一个表中，两个公式的真值相同，则称这两个公式等值。pq11100100111111111000000000005 利用真值表证明：利用真值表证明： pq 和和 pq 逻辑等值，是等值
2、式逻辑等值，是等值式.6Table 4Table 4789101112131415EXAMPLE 5 EXAMPLE 5 证明证明16EXAMPLE 6 EXAMPLE 6 证明证明 (pq) (pq) 为永真式为永真式(p q) (p q)17判断命题公式逻辑等价的方法：判断命题公式逻辑等价的方法： 1、真值表、真值表 2、命题公式的演算、命题公式的演算 基本等值定理；基本等值定理； 公式的代入不变性；公式的代入不变性； 等值关系的传递性。等值关系的传递性。18命题公式逻辑等价关系的应用：命题公式逻辑等价关系的应用： 1、判定是否逻辑等价；、判定是否逻辑等价； 2、判断是否为永真公式或永假公
3、式；、判断是否为永真公式或永假公式； 3、命题公式的化简、命题公式的化简19应用：应用：应用：应用：有一个逻辑学家误入某部落，被拘于牢囚。酋长意欲放行。于是他对逻辑学家说：“今有两门，一为自由，一为死亡。你可任意开启一门。为协助你逃脱，加派两名战士负责解答你所提问题。两名战士中，一人说的永远是真话，另一永假。”逻辑学家沉思片刻，然后向一名战士发问。后从容走出。试问：逻辑学家应如何发问？20应用：应用：应用：应用：解答：逻辑学家指着一扇门问一名战士：“当我问他（另一名战士）这扇门是否是死亡之门时，他将回答是，对吗？”分析：P：被问战士是诚实人。q：被问战士回答：是。r：另一战士回答：是。s：这扇
4、门死亡之门。21应用：应用：应用：应用：P q r s1 1 1 01 0 0 10 1 0 00 0 1 1结果说明根据被询战士的回答可选择从哪扇门出去。若回答“是”，说明被指的门非死亡之门。回答“否”，说明该门是死亡之门。22第二节第二节 析取范式与合取范式析取范式与合取范式2324定理定理2.1 （1） 一个简单析取式是重言式当且仅当它同时一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式含某个命题变项及它的否定式（2）一个简单合取式是矛盾式当且仅当它同时含某个命）一个简单合取式是矛盾式当且仅当它同时含某个命题变项及它的否定式。题变项及它的否定式。定理定理2.2 2.2 （1
5、 1） 一个析取式是矛盾式当且仅当它的每个一个析取式是矛盾式当且仅当它的每个简单合取式都是矛盾式简单合取式都是矛盾式（2 2）一个合取范式是重言式当且仅当它的每个简单析取）一个合取范式是重言式当且仅当它的每个简单析取式都是重言式式都是重言式25合取范式（合取范式（conjunctive normal form)(小项小项): 有限个简单析取式构成的合取式。有限个简单析取式构成的合取式。析取范式（析取范式（disjunctive normal form)（大项）（大项）: 有限个简单合取式构成的析取式。有限个简单合取式构成的析取式。标准句标准句(standard sentence)：合取范式或析
6、取范式：合取范式或析取范式26析取范式：析取范式：析取范式：析取范式： 对对对对 分配；分配；分配；分配； 定理定理2.3：任意一个命题公式都存在与之等价的合取：任意一个命题公式都存在与之等价的合取 范式和析取范式。范式和析取范式。定理的证明思路：定理的证明思路： 1、将所有联结词转换为合取，析取，否定；、将所有联结词转换为合取，析取，否定； 2、将否定联结词移到命题变量、将否定联结词移到命题变量 的前面；的前面； 3、消除多余的否定联结词；、消除多余的否定联结词； 4、化成合取范式和析取范式。、化成合取范式和析取范式。合取范式：合取范式：合取范式：合取范式： 对对 分配；分配； 27例例例例
7、 求下面式子的析取范式以及合取范式。求下面式子的析取范式以及合取范式。求下面式子的析取范式以及合取范式。求下面式子的析取范式以及合取范式。即析取范式即合取范式282930定理定理2.3的作用与局限：的作用与局限： 1、标准化但仅仅是初步的、标准化但仅仅是初步的 # 标准化的形式标准化的形式 # 不唯一性（规范化要求：主范式）不唯一性（规范化要求：主范式） 2、能够判定是否为永真或永假公式但不方便、能够判定是否为永真或永假公式但不方便313233343536定理定理2.4：令：令A（a1、a2、an）包含有）包含有n个变量个变量的公式，则有：的公式，则有：1、如果、如果A存在与之等价的主析取范式
8、，则必唯一；存在与之等价的主析取范式，则必唯一；2、如果、如果A存在与之等价的主合取范式，则必唯一；存在与之等价的主合取范式，则必唯一；37实际上，可以通过主析取范式求主合取范式；实际上，可以通过主析取范式求主合取范式；实际上，可以通过主析取范式求主合取范式；实际上，可以通过主析取范式求主合取范式；也可以通过主合取范式求主析取范式；也可以通过主合取范式求主析取范式；也可以通过主合取范式求主析取范式；也可以通过主合取范式求主析取范式；例：已知例：已知例：已知例：已知3839如何利用真值表来求主析取范式、主合取范式？40414243二、命题公式中的逻辑联接词的极小完备性。二、命题公式中的逻辑联接词
9、的极小完备性。逻辑联接词组是逻辑联接词组是功能完备的：功能完备的： 任一个命题公式都能够等价于仅包含这些逻任一个命题公式都能够等价于仅包含这些逻辑联接词联结起来的公式。辑联接词联结起来的公式。逻辑联接词组是逻辑联接词组是极小功能完备的极小功能完备的： 是功能完备的并且不能少一个。是功能完备的并且不能少一个。44例例2：否定和合取组成的逻辑联结词组是：否定和合取组成的逻辑联结词组是极小功能极小功能完备的。完备的。例例1：否定、析取、合取组成的逻辑联结词组：否定、析取、合取组成的逻辑联结词组是功能完备的（由是功能完备的（由范式的存在性范式的存在性），但不是），但不是极小极小功能完备的。功能完备的。
10、例例3：否定和析取组成的逻辑联结词组是否定和析取组成的逻辑联结词组是极小功能完备的。极小功能完备的。45pq为真当且仅当为真当且仅当p，q不同时为真不同时为真 （pq）与非（与非（p与与q的否定）的否定）pq，或非（或非（p或或q的否定）的否定）pqpq为真当且仅当为真当且仅当p，q不同时为假不同时为假 46Pq与非与非pq或非或非pq110010100110001147也是联结词完备集。也是联结词完备集。证明：已知：否定，析取，合取联接词是完备的，证明：已知：否定，析取，合取联接词是完备的，48例例例例49小小 结结1、命题公式的等价演算、命题公式的等价演算2、 命题公式的标准化描述命题公式的标准化描述 表达、分类、判定、应用表达、分类、判定、应用 50
