数理逻辑—命题逻辑(3).ppt

1 Discrete Mathematics 西南科技大学计算机科学与技术学院第一章命题逻辑 范式及用途 2 Discrete Mathematics 西南科技大学计算机科学与技术学院引言?给定一个命题公式,如何判断它的类型—是重言式、矛盾式、还是可满足式? ?目前已经给出了两种方法,即真值表法和逻辑等价演算法。?还有第三种方法,这就是把命题公式化成一种统一的、标准的公式—范式。 3 Discrete Mathematics 西南科技大学计算机科学与技术学院给定命题变元 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都等都是简单合取式。 。仅由有限个命题变元或其否定构成的合取式称为简单合取式。 4 Discrete Mathematics 西南科技大学计算机科学与技术学院 (1) 仅由有限个简单合取式构成的析取式称为析取范式; (2) 仅由有限个简单析取式构成的合取式称为合取范式。?显然任何析取范式的对偶式为合取范式;任何合取范式的对偶式为析取范式。 5 Discrete Mathematics 西南科技大学计算机科学与技术学院例如: A=( p∧┒ q∧ r)∨(┒p∧ q)∨(p∧┒ q ) 则A为析取范式。 A的对偶式为: A * =(p∨┒ q∨ r)∧(┒p∨ q)∧(p∨┒ q ) 显然, A *为合取范式。?对任何给定的命题公式,都能求出与之等价的析取范式与合取范式。 6 Discrete Mathematics 西南科技大学计算机科学与技术学院定理(范式存在定理) 任一命题公式都存在着与之等价的析取范式和合取范式。下述分析给出了任何命题公式范式存在性的证明, 这证明同时也是求其范式的具体步骤,即(1). 消去对{┒、∧、∨} 来说冗余的联结词。即用基本的逻辑恒等式及置换规则将→、?联结词消去,所用的逻辑恒等式是 p→q?┒p∨ q p ? q ?(┒p∨ q)∧(p∨┒ q) 7 Discrete Mathematics 西南科技大学计算机科学与技术学院(2). 否定号消去或内移 若遇有┒┒ p或┒(p∧ q),┒(p∨ q)等形式,,即┒┒ p?p; ┒(p∧ q)?┒p∨┒ q; ┒(p∨ q)?┒p∧┒ q。 8 Discrete Mathematics 西南科技大学计算机科学与技术学院(3). 利用分配律 若是求析取范式,应该利用“∧”对“∨”的分配律;若是求合取范式,应该利用“∨”对“∧”的分配律。 任给一个命题公式 A,经过以上三步演算,可得到一个与 A逻辑等价的析取范式或合取范式。?值得注意的是, 任何命题公式的析取范式和合取范式都不是唯一的,我们把其中运算符最少的称为最简析取(合取)范式。 9 Discrete Mathematics 西南科技大学计算机科学与技术学院例1 求下面命题公式的合取范式和析取范式。解(1) 求合取范式至此,求出了原公式的合取范式。但上式可再化简,得: ?(p∨ q)∧(┒r∨ p),该式也是原公式的合取范式(最简), 这说明与某个命题公式等价的合取范式是不唯一的。 10 Discrete Mathematics 西南科技大学计算机科学与技术学院(2) 求析取范式最后结果为原公式的析取范式,利用交换律和吸收律得,也是原公式的析取范式, 由此可见,与命题公式等值的析取范式也是不唯一的。