[工学]132 范式.ppt

范 式 复习 蕴涵式 定义 →和?的区别和联系 性质 蕴涵式与等价式的关系 蕴涵式的证明方法 真值表 等值演算 假定前件为真 假定后件为假 复习(Cont.) 联结词的扩充 合取非（与非） 析取非（或非） 条件非 双条件非（异或）? 只有你走我才留下 这一命题是说：“若你不走，则我不留”；也是说：“如若我留则你得走”。因此，它的正确翻译是：令P为“你走”,Q为“我留”，则原命题的真值形式是：?P→?Q,亦即：Q→P。 与原命题类似的命题还有： 仅当你走我才留下； 仅当你走我将留下； 我留下仅当你走。 Tips 在一般的命题表述中，“仅当”是必要条件，译成条件命题时其后的命题是后件；而“当”是充分条件，译成条件命题时其后的命题是前件。 我今天进城，除非下雨 这一命题是说：“若不下雨，则我今天进城”,或者是说：“我今天不进城，仅当要下雨”。因此，它的正确翻译是：令P为“我今天进城”,Q为“今天下雨”，则原命题可以符号化为?Q→P,亦可: ?P→Q。 “除非”，表示唯一的条件，原命题相当于“只有天下雨我才不进城”。 Tips 单用“除非”的命题，“非...”是充分条件，译成条件命题时，“非…”是前件。要是“除非…，否则…”的命题，其真值形式就是双条件了 e.g. 除非敌人投降,否则他们没有出路 欲寄君衣君不还，不寄君衣君又寒。 寄与不寄间，妾身千万难。 人不犯我，我不犯人；人若犯我，我必犯人。 本节内容 范式 主范式 简单合取式与简单析取式 定义 在一公式中，仅由命题变元及其否定构成的合取式， 称该公式为简单合取式，其中每个命题变元或其否定，称为合取项。 例如： P，?Q，P?Q和?P?Q?P 定义 在一公式中，仅由命题变元及其否定构成的析取式， 称该公式为简单析取式，其中每个命题变元或其否定，称为析取项。 例如： P，?Q，P?Q，?P?Q?P 注意：一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如例中P，?Q等 定理 简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。 定理 简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。 合取范式和析取范式 定义 一个命题公式A称为析取范式，当且仅当A表示为简单合取式的析取，即A1?A2?…?An (n=1)；其中Ai为简单合取式，i=1，2，…，n。 例如： ?P?(P?Q)?(P??Q?R) 定义 一个命题公式A称为合取范式，当且仅当A表示为简单析取式的合取，即A1?A2?…?An (n=1)；其中Ai为简单析取式，1≤i≤n。 例如： (P??Q?R) ?(P?Q)??Q 范式求法 任何一个命题公式都可以变换为与它等值的析取范式或合取范式。按下列步骤进行： ①使用命题定律，消去公式中除?、?和?以外公式中出现的所有联结词； ②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前； ③利用结合律、分配律等将公式化成析取范式或合取范式。 范式的应用 利用析取范式和合取范式可对公式进行判定。 定理 公式A为永假式的充要条件是A 的析取范式中每个简单合取式至少包含一个命题变元及其否定。 定理 公式A为永真式的充要条件是A 的合取范式中每个简单析取式至少包含一个命题变元及其否定。 范式的应用(Cont.) 例：判别公式A=P? (P∧(Q?P))是否为重言式或矛盾式。 解： A? ?P∨(P∧(?Q∨P)) 　 ? ?P∨(P∧?Q)∨(P∧P) (析取范式) 根据定理，A不是矛盾式。 又A??P∨(P∧(?Q∨P)) ?（?P∨P）∧（?P∨?Q∨P)（合取范式） 由定理知，A是重言式。 公式的主范式 范式基本解决了公式的判定问题。但由于范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个问题(化成唯一的等价命题的标准形式)。 主析取范式 小项 定义 在含有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个小项。 主析取范式(Cont.) 小项的性质 如果将命题变元按字典序排列，并且把命题变元与1对应，命题变元的否定与0对应，则可对2n个小项依二进制数编码，记为mi，其下标i是由二进制数转化的十进制数。用这种编码所求得2n个