工科离散数学课件 第一章 1_6_范式(1) - 简单范式.pptx

1.6 范式在科学哲学概念上，范式指一种公认的模型或模式。这里指命题公式都应具有的一种内在表示形式。因此，一种重要的衡量命题公式是否等价的方法是将其都转换成标准形式。这种标准形式称为“范式”。 1.6.1 简单范式1.6 范式-简单范式[文字]原子命题变元或它的否定。示例： p 和 ┐p。 [合取范式]一个具有合取形式的命题公式： ——由析取式组成的合取式 A1?A2?? ?An，n≥1 ——积范式?ni =1Ai或?ni =1Ai其中，每个Ai 都是由文字组成的析取式。[析取范式]一个具有析取形式的命题公式： ——由合取式组成的析取式 A1?A2???An，n≥1 ——和范式?ni =1Ai或 ?ni =1Ai其中，每个Ai 都是由文字组成的合取式。 示例：(p?┐q?r)?(┐p?q)?┐q是合取范式。(p?┐q?r)?(┐p?q)?┐q是析取范式。1.6 范式-简单范式2. ┐(p?q)是合取范式吗？——否1. 单个文字（如 p 和 ┐p）是什么范式？ 单个合取式p?q、析取式p?┐q分别是什么范式？——既是合取范式，也是析取范式否定只能作用在原子变元前，绝不能置于括号前! 求范式的等价演算方法：1.6 范式-简单范式Step1：联结词转换为?、?及┐：┐( p→q) ? ┐(┐p?q)。Step2：用德?摩根律（对偶原理）将否定联结词 ┐直接移到各命题变元之前： ┐(┐p?q) ? p?┐qStep3：用分配律、结合律转换为合取范式或析取范式。 例1-23：求(p?(q→r))→s的合取范式。解： (p ? (q→r) )→s ?(规范联结词) ┐(p?(┐q?r))?s ?(否定深入) ┐p?(q?┐r)?s?(交换律、结合律) (┐p?s) ? (q?┐r)?(分配律) (┐p?s?q)?(┐p?s?┐r) Try it：命题公式的合取范式与析取范式是唯一的吗？1.6 范式-简单范式问：不唯一的原因是？答：组成范式的合取式（或析取式）中的原子变元不全。 ——“不太标准”答：不唯一。 0A = p ? p?(q?┐q) ? (p?q)?(p?┐q)2个公式都是A的合取范式。 1.6 范式-简单范式1. 你能解释任何命题可以转换成范式的原因吗？——{┐, ?, ?}是功能完备的2. 推导s?(s→t) 的析取范式和合取范式。——s?(s→t)? s?(┐s ?t)[合取范式]? (s?┐s)?(s?t)?0 ?(s?t) ?s?t[析取范式]