数理逻辑命题逻辑精品文稿.ppt

《数理逻辑命题逻辑精品文稿.ppt》由会员分享，可在线阅读，更多相关《数理逻辑命题逻辑精品文稿.ppt（55页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、数理逻辑命题逻辑第1页，本讲稿共55页 引言q 给定一个命题公式，如何判断它的类型是重言式、矛盾式、还是可满足式？q 目前已经给出了两种方法，即真值表法和逻辑等价演算法。q 还有第三种方法，这就是把命题公式化成一种统一的、标准的公式范式。2第2页，本讲稿共55页给定命题变元p,q，则p，q，p，q，p q，p q，p q，p q等都是简单析取式，而p，q，p，q，p q，p q，p q，p q 都等都是简单合取式。1.简单析取式和简单合取式定义 仅由有限个命题变元或其否定构成的析取式称为简单析取式。仅由有限个命题变元或其否定构成的合取式称为简单合取式。3第3页，本讲稿共55页2.析取范式和合取

2、范式定义(1)仅由有限个简单合取式构成的析取式称为析取范式；(2)仅由有限个简单析取式构成的合取式称为合取范式。u显然任何析取范式的对偶式为合取范式；任何合取范式的对偶式为析取范式。4第4页，本讲稿共55页例如：A=(p q r)(p q)(p q)则A为析取范式。A的对偶式为：A*=(p q r)(p q)(p q)显然，A*为合取范式。u对任何给定的命题公式，都能求出与之等价的析取范式与合取范式。5第5页，本讲稿共55页定理(范式存在定理)任一命题公式都存在着与之等价的析取范式和合取范式。下述分析给出了任何命题公式范式存在性的证明，这证明同时也是求其范式的具体步骤，即(1).消去对、来说冗

3、余的联结词。即用基本的逻辑恒等式及置换规则将、联结词消去，所用的逻辑恒等式是pq p qpq(p q)(p q)6第6页，本讲稿共55页(2).否定号消去或内移若遇有p或(p q)，(p q)等形式，利用双重否定律和德.摩根律可将否定号消去或内移，即p p；(p q)p q；(p q)p q。7第7页，本讲稿共55页(3).利用分配律若是求析取范式，应该利用“”对“”的分配律；若是求合取范式，应该利用“”对“”的分配律。任给一个命题公式A，经过以上三步演算，可得到一个与A逻辑等价的析取范式或合取范式。u值得注意的是，任何命题公式的析取范式和合取范式都不是唯一的，我们把其中运算符最少的称为最简析

4、取(合取)范式。8第8页，本讲稿共55页例1求下面命题公式的合取范式和析取范式。解(1)求合取范式 至此，求出了原公式的合取范式。但上式可再化简，得：(p q)(r p)，该式也是原公式的合取范式（最简），这说明与某个命题公式等价的合取范式是不唯一的。9第9页，本讲稿共55页(2)求析取范式 最后结果为原公式的析取范式，利用交换律和吸收律得，也是原公式的析取范式，由此可见，与命题公式等值的析取范式也是不唯一的。10第10页，本讲稿共55页例2求P(PQ)的最简析取范式。解：P(PQ)P(P Q)P P P Q0P QP Q11第1 1页，本讲稿共55页3.极小项与主析取范式定义在含n个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，而二者之一必出现且仅出现一次，且第i个命题变元或其否定出现在从左起的第i位上(若命题变元无下标，则按字典顺序)，这样的简单合取式称为极小项。显然，n个变元可构成2n个不同的极小项。12第12页，本讲稿共55页