《离散数学课件第一章(第4讲).ppt》由会员分享，可在线阅读，更多相关《离散数学课件第一章(第4讲).ppt（47页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、对偶原理对偶原理（对偶定律）（对偶定律）定义定义：给定命题公式，若用给定命题公式，若用代换代换，用，用代换代换，用代换，用代换，得到另一个命，用代换，用代换，得到另一个命题公式题公式A*，则称和，则称和A*是互为对偶的。是互为对偶的。例：写出下列命题公式的对偶式：例：写出下列命题公式的对偶式：（）（）对偶式对偶式 A*5 对偶与范式对偶与范式讨论定义：讨论定义：（）若命题公式中有联结词（）若命题公式中有联结词，则必须把化，则必须把化成由联结词成由联结词，组成的等价的命题公式，组成的等价的命题公式，然后求它的对偶式；然后求它的对偶式；例例：求：求(P(PQ)Q)(P(PR)R)的对偶式的对偶式(
2、P(PQ)Q)(P(PR)R)（）（R R）则其对偶式为：则其对偶式为：（）（R R）（）在写对偶式时，原命题公式中括号不能省（）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。对偶式时仍将保留括号。例：（例：（）对偶式写成对偶式写成（），而不能写成，而不能写成定理定理：（摩根推广定理）（摩根推广定理）设和设和A*为对偶式为对偶式,P1,P2Pn 是出现在和是出现在和A*中的所有原子命题变元，于是有：中的所有原子命题变元，于是有：（P1，P2Pn）A*（P1，P2Pn）（1）（P1，P2Pn）A*（P1，
3、P2Pn）（）（）证明证明：由摩根定理：由摩根定理（）（）（）（）（）（）例：设（，）例：设（，）（），），验证上述定理：验证上述定理：证明：证明：()（，）（，）（，）（，）A*（，）（，）A*（，）有有（，）（，）=A*（，）（）（）（，）A*（，）（，）（）有（有（，）A*（，）（，）定理定理：若二个命题公式互为等价，则它们的对：若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若偶式也互为等价，亦即若，则，则A*B*成立。成立。由由，即（即（P1，P2Pn）（P1，P2Pn）（P1，P2Pn）（P1，P2Pn）由由摩根推广定理摩根推广定理*（P1，P2Pn）*（P1，P2Pn）证明
4、：证明：设：设：P1、P2Pn 是出现在和中的原子命题变元，是出现在和中的原子命题变元，*（P1，P2Pn）*（P1,P2Pn）为永真式为永真式由于永真式的代换实例仍为永真式，所以用由于永真式的代换实例仍为永真式，所以用 Pi代换代换A*和和B*中中的的Pi（1in)in)则得：则得：*（P1，P2 Pn）*（P1，P2 Pn）即为：即为：*（P1，P2Pn）*（P1，P2Pn）范式范式把命题公式化归为一种标准的形式，称此标准形式为范式。把命题公式化归为一种标准的形式，称此标准形式为范式。1析取范式和合取范式析取范式和合取范式：定义定义一个命题公式称为析取范式，当且仅当它具有形式：一个命题公式
5、称为析取范式，当且仅当它具有形式：A1 A2 An(n1),其中其中A1，A2，An都是由命题变元或都是由命题变元或其否定所组成的合取式。其否定所组成的合取式。如：（如：（）（）（）是一个析取范）是一个析取范式式判定二个命题公式等价，还可以使用范式方法。判定二个命题公式等价，还可以使用范式方法。（）利用等价公式：化去（）利用等价公式：化去“”、“”联结词，把联结词，把命题公式变为与其等价的用命题公式变为与其等价的用，表达的公式。表达的公式。例例:，（）（）（）（）（）将（）将“”深入到原子命题变元之前，并使变元之深入到原子命题变元之前，并使变元之前最多只有一个前最多只有一个“”词。词。例：例：
6、（）求析取范式的方法可按下列三步（或四步）进行：求析取范式的方法可按下列三步（或四步）进行：（）利用（）利用“”对对“”的分配律，将公式化为的分配律，将公式化为析取范式。析取范式。（）除去永假项得最简析取范式。（）除去永假项得最简析取范式。例：求例：求(（）R)(P Q)Q)的析取范式的析取范式原式原式 (（）R)(（）Q)化去化去“”词词 (（）R)(（）Q)“”深入到变元前，并最多保留一个深入到变元前，并最多保留一个（R)（）（Q）“”对对“”的分配的分配 律律（R)（）去掉永假的合取项去掉永假的合取项注：给定一命题公式的析取范式不是唯一的，但同一命题公式的析注：给定一命题公式的析取范式不
7、是唯一的，但同一命题公式的析取范式一定是等价的。取范式一定是等价的。定义定义一个命题公式称为合取范式，当且仅当它具有一个命题公式称为合取范式，当且仅当它具有形式：形式：A1 A2 An(n1),其中其中A1，A2，An都是都是由命题变元或其否定所组成的析取式。由命题变元或其否定所组成的析取式。如：（如：（）（）（）是）是一个合取范式。一个合取范式。求一个命题公式的合取范式的方法和求析取范式求一个命题公式的合取范式的方法和求析取范式的方法类同：的方法类同：（）利用等价公式：化去（）利用等价公式：化去“”、“”联结词，联结词，把命题公式变为与其等价的用把命题公式变为与其等价的用，表达的表达的公式。
8、公式。（）将（）将“”深入到原子命题变元之前，并使变元深入到原子命题变元之前，并使变元之前最多只有一个之前最多只有一个“”词。词。（）利用（）利用“”对对“”的分配律，将公式化为的分配律，将公式化为合取范式；合取范式；（）去掉永真的析取项。（）去掉永真的析取项。例：求例：求(（）)（）的合取范式）的合取范式原式原式 (（）)（）化去化去“”词词 (（）)（）“”深入到变元前，并最多保留一个深入到变元前，并最多保留一个（）（）（）“”对对“”的分配的分配（）（）去掉永真的析取项去掉永真的析取项注：给定一命题公式的合取范式不是唯一的，但同一命题公式的合注：给定一命题公式的合取范式不是唯一的，但同一
9、命题公式的合取范式一定是等价的。取范式一定是等价的。2主析取范式主析取范式定义定义在个变元的合取项中，若每个变元及其否在个变元的合取项中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一定并不同时存在，且二者之一出现一次且仅出现一次，则称此合取项为次，则称此合取项为小项小项。例例:具有二个命题变元的命题公式具有二个命题变元的命题公式,小项最多有小项最多有22=4个个,即即、具有三个命题变元的命题公式，小项最多有具有三个命题变元的命题公式，小项最多有23=8个，个，即：即：、推广：具有个命题变元的命题公式的小项最多有推广：具有个命题变元的命题公式的小项最多有2n个（个（nII+）。）
10、。定义定义对于给定的命题公式，若干个对于给定的命题公式，若干个小项的析取小项的析取称称为该命题公式的主析取范式。为该命题公式的主析取范式。定理定理在真值表中，一个命题公式的所有在真值表中，一个命题公式的所有真值为真值为的指派所对应的的指派所对应的小项的析取小项的析取，即为此命题公式的，即为此命题公式的主析取范式。主析取范式。例：根据真值表，分别求出例：根据真值表，分别求出、的主析取范式。的主析取范式。TTTTTFFTFTTFFTFTTTFF PQ则根据真值表可直接写出各命题公式的主析取范式：则根据真值表可直接写出各命题公式的主析取范式：（）（）（）（）（）（）PQ（）（）讨论此定理：讨论此定理
11、：（1）只要命题公式不是永假式，则一定可以根据该）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方命题公式的真值表直接写出其主析取范式，其方法是找出该命题公式真值为法是找出该命题公式真值为“”的行，对应写的行，对应写出小项的析取式，命题公式的主析取范式一定是出小项的析取式，命题公式的主析取范式一定是唯一的。唯一的。（2）由真值表找小项的方法为：将表中值为由真值表找小项的方法为：将表中值为“T”所对应的真值指派中，所对应的真值指派中，T对应变元本身，对应变元本身，F对应变元的否定。对应变元的否定。（3）命题公式的主析取范式中小项的个数一）命题公式的主析取范式中小
12、项的个数一定等于对应真值表中真值为定等于对应真值表中真值为“”的个数。的个数。（4）若二个命题公式对应的主析取范式相同，）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。则此二个命题公式一定是等价的。下下面面介介绍绍不不用用真真值值表表，直直接接求求命命题题公公式式主主析析取取范范式式的的方方法，分四步：法，分四步：（）（）将命题公式化为与其等价的析取范式；将命题公式化为与其等价的析取范式；（）（）除去永假项，合并合取项中相同项除去永假项，合并合取项中相同项 例：例：为永假项为永假项，去掉。，去掉。，合并合取项中相同项合并合取项中相同项（）（）对合取项补入没有出现的命题变元对
13、合取项补入没有出现的命题变元，即添加（合取），即添加（合取）例如（例如（P）的形式，并应用）的形式，并应用对对的的分配律展开分配律展开公式。公式。例：若命题公式有二个变元、，当析取范式中例：若命题公式有二个变元、，当析取范式中的某一项缺少变元时，利用的某一项缺少变元时，利用“”对对“”的分的分配律添项：配律添项：（）（）（）（）（）（）（）（）合并相同的小项。合并相同的小项。（）-（2）消去永假项，变为最简析取范式）消去永假项，变为最简析取范式（）（）-（3）添项）添项（）（）（）（）（）-（4）合并相同小项）合并相同小项例：求（例：求（）的主析取范式的主析取范式解：原式解：原式（）（）-（1
14、）化为析取范式）化为析取范式例：证明例：证明（）证明方法是写出二命题公式的主析取范式，看其是否相同：证明方法是写出二命题公式的主析取范式，看其是否相同：（）（）（）（）（）（）（）（）（）（）（）（）（）（）（）两个命题公式两个命题公式 主析范式相同，主析范式相同，（）3主合取范式主合取范式定义定义在个变元的析取项中，若每个变元与其否定，在个变元的析取项中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，并不同时存在，且二者之一出现一次且仅出现一次，则称这种析取项为则称这种析取项为大项大项。例：具有二个变元例：具有二个变元,的命题公式，其大项最多有的命题公式，其大项最多有22
15、=4个：（个：（）、（）、（）、（）、（）、）、（）具有个变元的命题公式，其大项最多有具有个变元的命题公式，其大项最多有2n个个（nII+）。）。定义定义对于给定的命题公式，若干个对于给定的命题公式，若干个大项的合取大项的合取称为该称为该命题公式的主合取范式。命题公式的主合取范式。定理定理在真值表中，一个命题公式的所有在真值表中，一个命题公式的所有真值为真值为F的指的指派所对应的派所对应的大项的合取大项的合取，即为此命题公式的主合取范式。，即为此命题公式的主合取范式。在真值表中真值为在真值表中真值为“”的个数等于主合取范式中大项的个数等于主合取范式中大项的个数。的个数。TTTTTFFFFTTF
16、FTFTTFFF例：根据真值表，分别求出例：根据真值表，分别求出、的主合取的主合取范式。范式。（）（）（）根据真值表，可直接写出各命题公式的主合取范式：根据真值表，可直接写出各命题公式的主合取范式：（）（）讨论：讨论：（1）该该命命题题公公式式的的主主合合范范式式中中大大项项的的个个数数等等于于其其真真值值表中真值为表中真值为“”的个数。的个数。（2）由由真真值值表表找找大大项项的的方方法法为为：将将表表中中值值为为“”所所对对应应的的真真值值指指派派中中，T对对应应变变元元的的否否定定，F对对应应变变元元本本身。身。（3）只只要要命命题题公公式式不不是是永永真真式式，则则一一定定可可以以写写
17、出出与与其其等价的唯一的主合取范式。等价的唯一的主合取范式。（4）可用主合取范式判定二个命题公式是否等价。）可用主合取范式判定二个命题公式是否等价。（5）对应于有个变元的命题公式，则一定有：）对应于有个变元的命题公式，则一定有：主析范式小项数主合范式大项数主析范式小项数主合范式大项数2n下下面面介介绍绍不不用用真真值值表表求求一一命命题题公公式式主主合合取取范范式式的的方方法：法：（1）将命题公式化为与其等价的合取范式；将命题公式化为与其等价的合取范式；（2）除除去去永永真真项项，合合并并析析取取项项中中相相同同变变元元，变变为为最最简简合取式合取式；例：例：为永真项为永真项，去掉。，去掉。，
18、合并析取项中相同变元合并析取项中相同变元。（3）对析取项补入没有出现的命题变元对析取项补入没有出现的命题变元，即添加，即添加(析取析取)例如（例如（P）的形式，并应用）的形式，并应用对对的的分配律展开分配律展开公式。公式。例例：若若命命题题公公式式有有二二个个变变元元、，当当合合取取范范式式中中的的某某一项缺少变元时，利用一项缺少变元时，利用“”对对“”的分配律添项：的分配律添项：即：即：（）（）（）（4）合并相同的大项。合并相同的大项。例：求例：求（）的主合取范式的主合取范式 解：原式解：原式 （）（）（）（）（）（）（）-合并析取项中相同变元，化为最简合取范式合并析取项中相同变元，化为最简
19、合取范式 （）(（）)-添项添项 （）（）（）（）（）-合并相同大项合并相同大项4主析主析(合合)取范式的编码表示取范式的编码表示为了能够用编码的形式表达主析为了能够用编码的形式表达主析(合合)取范式，作如下规定：取范式，作如下规定：小项和大项中的各命题变元的出现位置必须安排一固定次序。小项和大项中的各命题变元的出现位置必须安排一固定次序。（）小项的编码（）小项的编码对于有个变元的命题公式，则最多可有对于有个变元的命题公式，则最多可有2n个小项，个小项，用用mi表示小项，用表示小项，用m0 m1 m2n-1来表示主析取范式。来表示主析取范式。P Q R1117m7P Q R1106m6P Q
20、R1015m5P Q R1004m4P Q R0113m3 P Q R0102m2 P Q R0011m1P Q R0000m0小项表示二进制数十进制数m(i)十下面表格列出三个变元，且、的位置已固定，下面表格列出三个变元，且、的位置已固定，小项表达如下：小项表达如下：对主析取范式编码的方法：对主析取范式编码的方法：(1)将小项中的变元按照固定次序排列；将小项中的变元按照固定次序排列；(2)用用二二进进制制表表示示出出其其对对应应的的小小项项，将将小小项项中中变变元元的的肯肯定定用用1表示，变元的否定用表示，变元的否定用0表示；表示；(3)将二进制转变为十进制，用将二进制转变为十进制，用mi表
21、示小项；表示小项；(4)将将mi表表示示的的各各小小项项，用用析析取取符符号号连连接接，得得到到编编码码表表示示的主析取范式；的主析取范式；(5)取取各各小小项项下下标标的的十十进进制制数数字字，按按照照顺顺序序置置于于 符符号号后后，可进一步简化编码表示可进一步简化编码表示主析取范式。主析取范式。解：原式解：原式（）（）（）（）m(111)m(110)m(001)m(011)m7 m6 m1 m3 m1,m3,m6,m7 1,3,6,7 例例：求求（）（）的的主主析析取取范范式式的的编编码表达式：（设小项按照、次序固定）码表达式：（设小项按照、次序固定）（2）大项的编码）大项的编码对对于于有
22、有个个变变元元的的命命题题公公式式，则则最最多多可可有有2n个个大大项项，用用Mi表表示示大大项项，用用M0 M1 M2n-1来来表表示示主合取范式。主合取范式。P Q R1117M7P Q R1106M6P Q R1015M5P Q R1004M4P Q R0113M3P Q R0102M2P Q R0011M1P Q R0000M0大项表示大项表示二进制数二进制数十进制数十进制数M(i)十十下下面面表表格格列列出出三三个个变变元元，且且、的的位位置置已已固固定定，大大项表达如下：项表达如下：对主合取范式编码的方法：对主合取范式编码的方法：(1)将大项中的变元按照固定次序排列；将大项中的变元
23、按照固定次序排列；(2)用用二二进进制制表表示示出出其其对对应应的的大大项项，将将大大项项中中变变元元的的肯肯定定用用0表示，变元的否定用表示，变元的否定用1表示；表示；(3)将二进制转变为十进制，用将二进制转变为十进制，用Mi表示大项；表示大项；(4)将将Mi表表示示的的各各大大项项，用用合合取取符符号号连连接接，得得到到编编码码表表示示的主合取范式；的主合取范式；(5)取取各各大大项项下下标标的的十十进进制制数数字字，按按照照顺顺序序置置于于符符号号后后，可进一步简化编码表示可进一步简化编码表示主合取范式。主合取范式。例：求（例：求（）（）的大项编码表示）的大项编码表示（设、次序已定）（设
24、、次序已定）解：原式解：原式（）（）（）（）M(000)M(010)M(100)M(110)M 0 M 2 M 4 M 5 M0,M2,M4,M5 0,2,4,5 通通过过编编码码，可可以以由由主主析析取取范范式式的的编编码码表表示示直直接接获获得得主合取范式的编码表示，反之也可以。主合取范式的编码表示，反之也可以。从从上上例例中中，可可以以获获知知两两种种主主范范式式的的编编码码方方式式可可以以互互相获得。相获得。（）（）1,3,6,7 -主析取范式的编码表示主析取范式的编码表示 0,2,4,5 -主合取范式的编码表示主合取范式的编码表示TTTFFTFTFTFFP QQP计算主析取范式的编码
25、步骤为计算主析取范式的编码步骤为:P Q(）（）m00 m11m0 m3 0,3则主合取范式编码为则主合取范式编码为:1,2例：写出（例：写出（Q）的主析取范式和主合取范式的编码表示。）的主析取范式和主合取范式的编码表示。方方法法一一：通通过过求求（Q）的的主主析析取取范范式式的的编编码码来来给给出出主主合合取取范范式式的的编编码码表表示示。TTTFFTFTFTFFP QQP计算主合取范式编码过程为计算主合取范式编码过程为:P Q(）（）M01 M10M1 M2 1,2则主析取范式编码为则主析取范式编码为:0,3例：写出（例：写出（Q）的主析取范式和主合取范式的编码表示。）的主析取范式和主合取范式的编码表示。方方法法二二：通通过过求求（Q）的的主主合合取取范范式式的的编编码码来来给给出出主主析析取取范范式式的的编编码码表表示示。