命题逻辑中范式教学的思考与总结.doc

命题逻辑中范式教学的思考与总结摘 要：范式是命题逻辑中的重要概念，范式是把命题公式化归为一种标准的形式。范式最大的作用是可以进行两个命题的等价判定。本文通过剖析范式的定义和判定方法，帮助离散数学的初学者深入理解范式并能够熟练书写命题的范式。关键词：范式;命题逻辑;等价判定;离散数学一、范式的引入在引入范式的定义之前，我们先来讲解一下判定的含义：以有限次步骤来决定命题公式是否为永真式、永假式还是可满足式，或者判定两个命题公式是否定价等这一类问题统称为判定问题。在命题逻辑中，讲解了两个命题A和B等价（A=B）的充要条件是A-B为永真式。具体判断的方法可以归纳为三种：第一种是真值表法，即对于等价号两边的命题变元给予相同的真值指派，看结果是否相同，相同的话A-B即为永真式，此时A=B。第二种是命题演算的方法，即化简命题A-B至最简式，看是否为T，然后判断。第三种就是我们要介绍的范式判定的方法，将命题公式A和B分别化成主析取范式（或主合取范式）。如果化成后的主范式相同，则可以判定两个公式等价。把命题公式化归为一种规范标准的形式，称此标准形式为范式。二、析（合）取范式许多教材对析取和合取范式有着不同类型的定义。这里我们先引入两个词的定义：基本积和基本和。命题的析取式称为“和”，命题的合取式称为“积”。基本积是指命题公式的变元和变元的否定之积。同理，基本和是指命题公式的变元和变元的否定之和。若“基本积”和“基本和”中有子公式，则称为基本积（和）的因子。基本积和永假式有着密切的关系，一个基本积是永假式的充分必要条件是它至少包含一对因子，其中一个是另一个的否定。该判定很容易理解，因为一旦包含这样的因子，那幺其中必然含有F，由于基本积是合取，那幺整个命题的值为F，即为永假命题。同理，一个“基本和”必定为永真式的充分必要条件是该公式至少包含一对因子，其中一个是另一个的否定。析取范式的定义可以简称为“积之和”，即与命题公式等价的一个公式，如果是由基本积之和组成，则称它为命题的析取范式。并记为：PP1P2Pn（nI+）。其中P1，P2Pn均为基本积。合取范式和析取范式相反，可以简称为“和之积”，具体定义在此就不再赘述。从上面的定义可以看出，一个命题公式的析（合）取范式并不是唯一的，但是同一命题公式的析（合）取范式之间一定是等价的。可以说，一个命题公式的析（合）取范式有无数多个，因此单纯讨论析（合）取范式意义不大。我们更希望能够找到一种标准的形式，使得一个命题公式仅仅对应一个等价的析（合）取范式，这样就引入了主析（合）取范式。三、主析（合）取范式限于篇幅，这里我们以主析取范式为例。讲解之前，先要给出极小项的定义，而极小项又和前面讲的基本积息息相关。在n个变元的基本积中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此基本积为极小项。对于两个命题变元来说，极小项有2的2次方4个，即PQ、?PQ、P?Q、?P?Q。对于只有一个变元的命题，极小项有2个，即P、?P。依次类推，对于三个命题变元来说，极小项有8个，即PQR、PQ?R、P?QR、?PQR、?PQ?R、?P?QR、P?Q?R、?P?Q?R。推广到一般，n个命题变元构成的不同极小项有2的n次方个。而使得每个极小项为真的赋值仅有一个。有了极小项的定义，就可以定义主析取范式了，对于给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的主析取范式。在真值表中，一个公式真值为T的指派所对应的极小项的析取，即为此公式的主析取范式。对于该定义，要注意一下几点：第一，只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“T”的行，对应写出极小项的析取式，且该公式一定是唯一的。第二，若命题公式是含有n个变元的永真式，则它的主析取范式一定含有2的n次方个极小项。第三，若两个命题公式对应的主析取范式相同，则此两个命题公式一定是定价的。第四，命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“T”的个数。四、求主析取范式的方法求主析取范式的方法主要有两种，第一种是真值表法，其含义就是将真值表中对应结果为“T”的项列出来，然后将这些项用连接起来。这种方法较为简单，列出真值表，结果就一目了然了。但是当命题变元为3个以上时，真值表的数目将指数级增长，较为麻烦。下面介绍不用真值表，直接求命题公式主析取范式的方法，分为4步：第1步将命题公式化为与其等价的析取范式。第2步除去永假项，合并基本积中相同项，变为最简单析取范式。第3步是利用添变元的方法，将所有基本积变为极小项。第4步合并相同的极小项变为一项。五、总结主范式是将无数不同的命题公式转化成标准形式，以此来判断不同的命题公式之间是否等价。我们知道，含有1个命题变元的公式对应的真值表有两行，每一行的结果有两种，分别是T和F，那幺可以产生2的2次方种（即4种）不同的真值表。同理，含有2个命题变元的公式可以产生出2的4次方种（即16种）不(本文来自：www.bdFqY.cOM 千 叶帆文 摘:命题逻辑中范式教学的思考与总结)同的真值表。含有变元个数越多，