《命题演算》PPT课件.ppt
7/11/2023,Deren Chen,Zhejiang Univ.,1,1.2 命题演算 Propositional Equivalences,7/11/2023,Deren Chen,Zhejiang Univ.,2,1、命题(Proposition)2、从简单命题(atomic proposition)到 复合命题(compositional proposition)3、从命题常量(propositional constant)到 命题变量(propositional variable)4、从复合命题(compositional proposition)到 命题公式(propositional formulas),7/11/2023,Deren Chen,Zhejiang Univ.,3,永真命题公式（Tautology）公式中的命题变量无论怎样代入，公式对应的真值恒为T。永假命题公式（Contradiction)公式中的命题变量无论怎样代入，公式对应的真值恒为F。可满足命题公式（Satisfaction）公式中的命题变量无论怎样代入，公式对应的真值总有一种情况为T。一般命题公式（Contingency）既不是永真公式也不是永假公式。,7/11/2023,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.,7/11/2023,Deren Chen,Zhejiang Univ.,5,Table 1,7/11/2023,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.,逻辑等值，或逻辑等价,7/11/2023,Deren Chen,Zhejiang Univ.,7,EXAMPLE 2,Show that(pq)and p q are logically equivalent.This equivalence is one of De Morgans 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(pq)and p q agree for all possible combinations of the truth values of p and q,it follows that these propositions are logically equivalent.,7/11/2023,Deren Chen,Zhejiang Univ.,8,Table 2,7/11/2023,Deren Chen,Zhejiang Univ.,9,EXAMPLE 3,Show that the propositions pq and pq are logically equivalent.,Solution:We construct the truth table for these propositions in Table 3.Since the truth values of pq and pq agree,these propositions are logically equivalent.,7/11/2023,Deren Chen,Zhejiang Univ.,10,Table 3,7/11/2023,Deren Chen,Zhejiang Univ.,11,EXAMPLE 4,Show that the propositions p(qr)and(pq)(pr)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(qr)and(pq)(pr)agree,these propositions are logically equivalent.,7/11/2023,Deren Chen,Zhejiang Univ.,12,Table 4,7/11/2023,Deren Chen,Zhejiang Univ.,13,基本逻辑等价定理：对于任意的命题公式p、q、r，下面的命题公式是等价的。,7/11/2023,Deren Chen,Zhejiang Univ.,14,Table 5,7/11/2023,Deren Chen,Zhejiang Univ.,15,Table 6,p(p q)p Absorption Laws/吸收律p(p q)pp q p qp q(p q)(q p),7/11/2023,Deren Chen,Zhejiang Univ.,16,EXAMPLE 5,Show that(p(pq)and p q are logically equivalent.,7/11/2023,Deren Chen,Zhejiang Univ.,17,EXAMPLE 6,Show that(pq)(pq)is a tautology.,7/11/2023,Deren Chen,Zhejiang Univ.,18,判断命题公式逻辑等价的方法：1、真值表 2、命题公式的演算 基本等值定理；公式的代入不变性；等值关系的传递性。,7/11/2023,Deren Chen,Zhejiang Univ.,19,命题公式逻辑等价关系的应用：1、判定是否逻辑等价；2、判断是否为永真公式或永假公式；3、命题公式的化简,7/11/2023,Deren Chen,Zhejiang Univ.,20,Example 7,什麽，如果她不来那么我也不去，没有那回事。,P：她来。Q：我去。,7/11/2023,Deren Chen,Zhejiang Univ.,21,进一步的思考：一、命题公式的对偶性及其对偶处理。,7/11/2023,Deren Chen,Zhejiang Univ.,22,限定性命题公式：最多仅含有否定、析取、合取逻辑联结词的命题公式。命题公式P的对偶公式（Dual）：将P中的 析取联结词换成合取联结词，合取联结词换成析取联结词，T换成F，F换成T（如果存在的话）。记为P*,7/11/2023,Deren Chen,Zhejiang Univ.,23,对偶原理（Duality Principle)设P、Q是限定性命题公式。如果 P Q 则 P*Q*,例：A：（P Q）Q B：P Q,7/11/2023,Deren Chen,Zhejiang Univ.,24,进一步的思考：二、命题公式中的逻辑联接词的极小完备性。,7/11/2023,Deren Chen,Zhejiang Univ.,25,逻辑联接词组是功能完备的（Functionally Complete）：任一个命题公式都能够等价于仅包含这些逻辑联接词联结起来的公式。逻辑联接词组是极小功能完备的：是功能完备的并且不能少一个。,7/11/2023,Deren Chen,Zhejiang Univ.,26,例2：否定和合取组成的逻辑联结词组是极小功能完备的。例3：否定和析取组成的逻辑联结词组是极小功能完备的。,例1：否定、析取、合取组成的逻辑联结词组是功能完备的，但不是极小功能完备的。,7/11/2023,Deren Chen,Zhejiang Univ.,27,进一步的思考：三、命题公式的进一步分类。,命题公式的标准化-范式,7/11/2023,Deren Chen,Zhejiang Univ.,28,文字（literal）/符号（symbol）：原子命题或其否定小项（small item）/合取式（conjunctive form）:若干个文字的合取。大项（large item）/析取式（disjunctive form）:若干个文字的析取。,7/11/2023,Deren Chen,Zhejiang Univ.,29,合取范式（conjunctive normal form):若干个大项的合取。析取范式（disjunctive normal form):若干个小项的析取。标准句(standard sentence)：合取范式或析取范式子句（clause）:合取范式中的大项或 析取范式中的小项。,7/11/2023,Deren Chen,Zhejiang Univ.,30,定理1：任意一个命题公式都存在与之等价的合取 范式和析取范式。,定理的证明思路：1、化成限定性公式；2、将否定联结词移到命题变量的前面；3、消除多余的否定联结词；4、化成合取范式和析取范式。,7/11/2023,Deren Chen,Zhejiang Univ.,31,定理1的作用与局限：1、标准化但仅仅是初步的#标准化的形式#不唯一性 2、能够判定是否为永真或永假公式但不方便,7/11/2023,Deren Chen,Zhejiang Univ.,32,定理2：一个命题公式是永真公式当且仅当与它等价的合取范式的每一个大项中包含了一个命题变量和它的否定；一个命题公式是永假公式当且仅当与它等价的析取范式的每一个小项中包含了一个命题变量和它的否定；,7/11/2023,Deren Chen,Zhejiang Univ.,33,令A（a1、a2、an）包含有n个变量的公式，极小项(extremal):小项中恰包含n个变量或其否定。极大项(extremal):大项中恰包含n个变量或其否定。主合取范式（Unique conjunctive normal form):若干个极大项的合取。主析取范式（Unique disjunctive normal form):若干个极小项的析取。,7/11/2023,Deren Chen,Zhejiang Univ.,34,定理3：令A（a1、a2、an）包含有n个变量的公式，则有：1、如果A存在与之等价的主析取范式，则必唯一；2、如果A存在与之等价的主合取范式，则必唯一；3、A是永真公式当且仅当与A等价的主析取范式恰有2n个极小项或没有主合取范式；4、A是永假公式当且仅当与A等价的主合取范式恰有2n个极大项或没有主析取范式；5、两个命题公式等价当且仅当它们有相同的主合取范式或相同的主析取范式。,7/11/2023,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也抛出。上述五种条件全部满足，问有几种合理的方案供张先生选择。,7/11/2023,Deren Chen,Zhejiang Univ.,36,小 结1、命题公式的等价演算2、命题公式的标准化描述 表达、分类、判定、应用,7/11/2023,Deren Chen,Zhejiang Univ.,37,练 习Pp19 8(d),15,29 附加题,
