老师第一章命题逻辑-3rd

1、对偶原理定义：设有公式A，其中对偶原理定义：设有公式A，其中仅含有逻辑联结词, , 和逻辑常T和F。在中将, ,T , F分别换以, , F,T，得公式则称A*为的对偶式注意:式是相互举例P(QPP的对偶对偶原理定理1.5-1 设A和A*互为对偶式，P, P 对偶原理定理1.5-1 设A和A*互为对偶式，P, P ,L, P A和A*中所有命题变元，于是nA(P,P,L,P ) A*(P,P,L,Pn12nA(P,P,L,P)A*(P,P,L,P12nn证明 由德PQ (PPQ (P律 可知，对公式A求否定，直到深入到命题变元之前位置，在这个过程中，所有的变， 变 ，T变F， 对偶原理定理1.

2、5-若A B，且、B为命题变元1P2,LPn对偶原理定理1.5-若A B，且、B为命题变元1P2,LPn词的公式，则A* 证明：AB 意味AP1P2,PnB1P2,Pn)A(P1,P2,Pn)B(P1,P2,Pn于是永由定理1.5-1知，下式也永真Pi(i1,2,利用带入规则，以永A(P,P,P) B(P,P,P nn 对偶原理若(P Q对偶原理若(P QPPQ) PQ，试证(PQ)(P(PQ) P证明：A (P Q)(P(PBP (PQ)(P(PP则A因此，A* 对偶原理试证明)(PQ对偶原理试证明)(PQPQ(2)(P Q)(PQ) (P(P Q)(P (PQ)(PQ)(P (PQ)(P

3、Q)(PE11, (PQ)(PQ)(PQ)(P (PQPQ)(P QP (PT)(QTE17,T E17,对偶原理试证明对偶原理试证明)(PQPQ(2)(P Q)(PQ) (P(PQ)(PQ)(P由(PQP(PQ)(PQ)(PE11,知(P QPQ)和(P QPQ)互为对偶式(PQ)(PQ) 对偶原理定理1.5-对偶原理定理1.5-的公式，则B*ABB(P1,P2,Pn)A(P1,P2,Pn根据定理1.5-BP1P2,Pn) AP1P2,Pn永i 利用带入规则，以Pi (i 1,2 1.6范式和判定1.6范式和判定问题公式的标准形式范式用来在有限步内判定公式永真、永假、可满析取范式和合取范式定

4、义若一个析取范式和合取范式定义若一个命题公式是一些命题变元及其否定的积，则称之为基本积；若这个命题公式是一些变元及其否定之和，称为基本和。一个由基本积的和组成的公式，如果与给定的公式A等价，则称它是A的析取范式。析取范式：PQPQPQ,(PQP题公式A一个由基本和的积组成的公式，如果与给定价，则称它是A的合取范式。合取范式：PPQQPQ,(PQP析取范式和合取范式定理1.6-一个基本积是永假式，当且仅当它含PP形式的两个因子证明：析取范式和合取范式定理1.6-一个基本积是永假式，当且仅当它含PP形式的两个因子证明：QF （充分性）由于永假式P形式的两个因子时基本积是，所以含永假式P （必要性）

5、用反证法。设基本积为假但不含 形式的因子，于是给这个基本积中题变元指派真值T，给带有否定本积的真值是T题变元指派真值F，得基析取范式和合取范式定理1.6-2析取范式和合取范式定理1.6-2:一个基本和是永真式，当且仅P, P 形式的两个因子析取范式和合取范式例：求命题公式PR）的析取范式P析取范式和合取范式例：求命题公式PR）的析取范式PP Q解/*这是一个合取范式P Q） （P/*使用与对或的分配律，化成析取范式析取范式与合取范式析取范式与合取范式Q)(P(PQ)/*使用或对与的分配律及补余律，现在是合析取范式和析取范式和合取范式例：求(P Q) (P Q)的析取范式解：(PQ) (P (P

6、Q)(PQ)(PQ)(P (PQPQ)(PQ)(P F (PQ)(P (PQ)(P (PQ)P)(PQ) PPPQPQQ F PQPQ (PQ)(P析取范式和析取范式和合取范式例：求(PQ) (P Q)的合取范式解：令A (PQ (PQ)A (PQ) (P (PQ)(PQ)(PQ)(P (PQPQ)(PQ)(PPQP由于A A(PQP所以A (PQP主析取范式定义1.6-4：在含n个主析取范式定义1.6-4：在含n个变元的基本积中若每个变元与其否定不同时存在，而者之一必出现且仅出现一次，则称这种基本积为极小项。例两个命题变元P、Q的极小项PPQ,PQ,Pn个变元，极小项个数主析取范式假定有P、

7、Q、主析取范式假定有P、Q、R三个变元PQP Q R P Q R P Q RPQ01234567主析取范式主析取范式每个极小项只有一个真值指派任何两个极小项的合取必为假（因为在种真值指派中，只有一个极小项取值为真所有极小项的析取必为真主析取范式定义主析取范式定义1.6-5：一个由极小项的和组成的公式，如果与命题公式A等价，则称它是公式A的主析取范式对任何命题公式(永假式除外)都可求得与其等价的主析取范式，而且主析取范式的形主析取范式求主析取范式的方法：先化成与其等价的析取范式；主析取范式求主析取范式的方法：先化成与其等价的析取范式；若析取范式的基本积中同一命题变元出现多次，则将其化成只出现一次

8、；去掉析取范式中所有为永假式的基本积，即去掉基本积中含有形如PP的子公式的那些基本积；若析取范式中缺少某一命题变元如P，则可 并利用分配律展开，然后合并相同的基本积主析取范式A主析取范式A PQ(PQ)(RR)(PP)(PQR)(PQR)(PR)(P(PQR)(PQR)PR(Q(PR)(Q(PQR)(PQR)(PQ(PQR)(PQR)(PQ(PQR)(PQR)(PQ(PQR)(PQm7 m6 m5 m3 (1,3,5,6,主析取范式右图APQ对应的真值表：PQRPQ000P主析取范式右图APQ对应的真值表：PQRPQ000PQ0001PQ1010PQ0011PQ1100PQ0101PQ1110

9、PQ1111PQ1主合取范式定义1.6-6：在含n个主合取范式定义1.6-6：在含n个变元的基本和中若每个变元与其否定不同时存在，而者之一必出现且仅出现一次，则称这种基本和为极大项。例两个命题变元P、Q的极大项PPQ,PQ,Pn个变元，极大项个数主合取范式假定有P、Q、主合取范式假定有P、Q、R三个变元P Q R PQR PQPQPQ01234567MM每个极大项只有一组真值指派使其为每个极大项只有一组真值指派使其为任何两个极大项的析取必为真（因为在种真值指派中，只有一个极大项取值为假所有极大项的合取必为假。主合取范定义1.6-7：一个由极大项的积组成的公式，主合取范定义1.6-7：一个由极大

10、项的积组成的公式，的主合取范式。对任何命题公式(永真式除外)都可求得与其等价的主合取范式，而且主合取范式的形主合取范式A主合取范式A PQ(PR)(Q(PR)(QQ)(QR)(P(PQR)(PQR)(PQ(PQ(PQR)(PQR)(PQ M0 M2 M(0,2,主合取范式右图APQ对应的真值表：PQRPQ000PQ主合取范式右图APQ对应的真值表：PQRPQ000PQ0001PQ1010PQ 0011PQ1100PQ0101PQ1110PQ 1111PQ1极小项和极大项的关系极小项和极大项的关系极小项mi和极大项M i下列的关系：Mimi 由合取（析取）范式求主析取由合取（析取）范式求主析取（合取）范式二者可以互相转化已知公式A的主合取范式为：(PQR)(PQ求主析取范式。解A的主合取范式为M1M3，可知A的主析取式于是可直接写出A的主析取(PQR)(P Q R)(P Q(PQR)(PQR)(PQ主析取范式和主合取范式一个命题公式是主析取范式和主合取范式一个命题公式是永真式，它题变元的所有极出现在其主析取范式中，不存在与其等价的主合取范一个命题公式是永假式，它题变元所有极出现在其主合取范式中，不存在与其等价的主析取范式；一个命题公式是可满足的，它既有与其等价的主析取范式，也有与其等价的主合取范主析取范式和主合取范式主析取范式和主合取范式)主析取范式和主合取范式例