LSSX-1-3.ppt

例6 解：原式 由上例我们看到，一个命题公式的主析取范式，可由两种方法构成。一是由公式的真值表得出，另一是由基本等价公式推出。其推演步骤可归纳为： （1）化归为析取范式。 （2）除去析取范式中所有永假的析取项。 （3）将析取式中重复出现的合取项和相同的变元合并。 （4）对合取项补入没有出现的命题变元，即添加(P∨┒P) 式，然后，应用分配律展开公式。 定义1-7、6 n个命题变元的析取式，称作布尔析取或大项，其中每个变元与它的否定不能同时存在，但两者必须出现且仅出现一次。 例如：两个命题变元P、Q，其大项为 P?Q， P??Q， ?P?Q， ? P??Q 三个命题变元P、Q、R，其大项为P ? Q ? R ，P ? Q ? ?R ， P ? ?Q ? R ， P ? ?Q ? ?R ， ?P ? Q ? R ， ?P ? Q ? ?R ， ?P ? ?Q ? R ， ?P ? ?Q ? ?R 一般说来，n个命题变元共有2n个大项。 也可以得出结论： （1）没有两个大项是等价的 （2）每个大项只对应P和Q的一组真值指派，使得该大项的真值为F。 记作： M00=P?Q， M01=P?? Q， M10= ?P?Q， M11=?P??Q 总结出规律：在大项 中， 注：大项有如下性质： （1）每一个大项当其真值指派与编码相同时，其真值为F，在其余2n-1种指派情况下均为T。 （2）任意两个不同大项的析取式为永真。 （3）全体大项的合取式永为假，记为： 定义1-7、7 对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。 定理1-7、4 在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。 注：一个公式的主合取范式，亦可用基本等价式推出，其推演步骤为： （1）化归为合取范式。 （2）除去合取范式中所有为永真的合取项。 （3）合并相同的析取项和相同的变元。 （4）对析取项补入没有出现的命题变元，即添加(P∧┒P) 式，然后，应用分配律展开公式。 例：求(? P?Q) ? (P??Q)的主合取范式 解：用真值表法： P Q ? P?Q P??Q (? P?Q) ? (P??Q) T T F F F T F F T T F T T F T F F F F F 原式? (?P??Q)?(P?Q)?M11 ?M00 =?0，3 例：求(P ?Q) ? R的主合取范式。 解：用等价公式推导法： 原式? ?(?P?Q)?R ?(P??Q)?R ?(P?R)?(?Q?R) ?(P?R ?(Q ??Q))?(?Q?R?(P??P)) ?(P?Q?R)?(P??Q?R)?(P??Q?R)?(?P??Q?R) ?(P?Q?R)?(P??Q?R)?(?P??Q?R)=?0,2,6 例：求(P ?Q) ? R的主析取范式。 解：用等价公式推导法： 原式? ?(?P?Q)?R ?(P??Q)?R ?(P??Q?(R??R) )?( (P??P)?(Q??Q)?R) ?(P??Q?R) ? (P??Q??R)?(P?Q?R)? (?P?Q?R)? (P??Q?R) ? (?P??Q?R) ?(P??Q?R) ? (P??Q??R)?(P?Q?R)? (?P?Q?R)? (?P??Q?R) =?1,3,4,5,7 大家可以看到，当用等价公式推导的方法求得一公式的主析取范式或主合取范式时，可以方便地用编码求得另一种主范式，比真值表法快一些。 求 ? (P?Q)的主析取范式，再用编码大项写出主合取范式。 解：原式?P??Q ? m10 = ?2 原式? M00 ?M01 ? M11 ? (P?Q) ? (P??Q) ? (? P??Q) =?0,1,3 例题7 化 为主合取范式。 例7 解： * 一般来说，命题公式用{? ，?，?}表示。 联结词是否够用？ 每种联结词对应一种四个T或F的组合，总共可以有24=16种组合，似乎需要16种联结词才够用。 事实上，我们定义的这九种就够用了。 请看P27 表1-6.5 最小联结词组 最小联结词组 指可表示出其它所有联结词的最小联结词集合。如： {┒，∨}，{┒，∧} ，{↑} ，{↓} 都可构成最小联结词组。 最小联结词组 例：写出P ∨Q分别用{┒，∧} ，{↑} ， {↓}表示的等价式。 解：(1) 用{┒，∧}表示的等价式 P ∨Q ? ┒(┒P ∧ ┒Q) 德.