《命题逻辑推理系统》由会员分享，可在线阅读，更多相关《命题逻辑推理系统（56页珍藏版）》请在金锄头文库上搜索。
1、第三节 命题演算 一、重言式及其判定 （一）真值联结词、真值形式 复合命题形式在数理逻辑中叫真值形式。表示关系的联结词叫真值联结词。 真值联结词是日常语言联结词在真假关系上的一种抽象。,真值联结词有五个：否定 、合取 、析取 、蕴涵 、等值 。真值形式就是真值联结词与命题变项所构成的形式结构。命题变项是组成复合命题的原子命题,用字母p、q、r、s表示。,五种基本的真值形式： 合取式：pq 析取式：pq 蕴涵式：pq 等值式：pq 否定式： p 五种基本形式可生成更复杂的形式，1、（pq）（pq）p； 2、（pq）（rs） （pr）（qs）,真值形式最外层的括号根据五个联结词的结合力可以省略，结
2、合力按照下列顺序递减： 、 (pq)r) (ps) 可以省略为： pqr ps,复合命题真假与其支命题真假之间的关系与数学中的函数类似。在数学中，函数是用下面的公式表示的： y=f（x） 其中，x是自变元，y是函数的值，f是函数关系。例如：y=x2,数理逻辑引入函数原理来说明复合命题与其支命题之间的真假关系，它把这种关系当作一种函项关系，把这种函数叫做真值函项。 真值函项的值不是数，而是真值。,数学中同一个函数可以有不同的表现形式，例如： y=2x2+x，y=x（2x+1） 同样，数理逻辑中，同一个真值函项也可以有不同的真值形式，例如：pq，（pq）,真值形式的数目是无穷的，但是在命题变项的数
3、目给定之后，真值函项的数目也就确定了。 n个命题变项的真假组合会有多少个真值函项？,当n=1时，只有一个命题变项p，而p本身有真或假两种取值，当p取真时，对应的真值函项有真或假两种可能，当p取假时，对应的真值函项也有真或假两种可能。因此，一个命题变项对应的真值函项有四种。,当n=2时，命题变项p和q取值： p真时，对应q有真假两种可能； p假时，q也有真假两种可能；、两个命题变项有四种真假取值。 对于p和q的四种取值，其真值函项真假取值情况共有16种。,两个命题变项有四种真假取值为： p q T T T F F T F F,对应的16种真值函项有 p q f1f2f3f4f5f6f7f8f9f
4、10f11f12f13f14f15f16 T T TT T T T T T T F F F F F F F F T F TT T T F F F F T T T T F F F F F T TT F F T T F F T T F F T T F F F F TF T F T F T F T F T F T F T F,计算方法： 1个命题变项，其真假取值有21个，对应的真值函项有2的21次方个。 2个命题变项，其真假取值有22个，对应的真值函项有2的22次方个。 n个命题变项，其真假取值有2n个，对应的真值函项又有2的2n次方个。,设想一下： 两张红黑扑克牌，它们的红黑组合有多少种？ 这就相
5、当于两个命题变项的4种真假组合。 你猜对或猜不对各种组合的情况有多少种可能？ 这就相当于两个命题变项的4种真假组合对应的16种真值函项,再设想一下： 你参加两次考试，它们及格和不及格的组合有多少种？ 这也相当于两个命题变项的4种真假组合。 而4种情形对应的你考试时的精神状态的好坏有多少种？ 这也相当于两个命题变项的4种真假组合对应的16种真值函项,（二）真值函项的种类及其判定方法 （1）真值函项的种类 按真值函项的取值，真值函项分为： 常真的。 常假的。 可满足的。 真值形式也分为三类： 重言式。如：pp、pp等。 矛盾式。如：pp、pp。 可满足式。如：pq、pq。,命题逻辑中有效的推理在形
6、式上都是重言式。要判定一个复合命题推理是否有效，其实质也就是判定反映该推理的公式是否为重言式。 介绍两种判定重言式的方法：真值表法 归谬赋值法。,（2）真值表判定方法： 第一步：找出公式中所有不同的命题变项，竖行列出它们之间所有可能的真假组合。例：判定（pq）p）q p q T T T F F T F F,第二步：由简单到复杂横行列出该公式的所有子公式与该公式本身 p q pq (pq)p （pq）pq T T T F F T F F,第三步：计算出各子公式的真值与该公式的真值。若该公式值都真，为重言式，都假，为矛盾式，有真有假，为可满足式。,p q pq (pq)p （pq）pq T T T
7、 T TT F F F TF T T F TF F T F T,（3）归谬赋值法 第一步：假定被判定的公式为假。 第二步：从这一假定出发，按照不同联结词的要求对公式各部分赋以真值。 第三步：检查变项真值，如出现逻辑矛盾，证明原假定为假，原公式是重言式；如未导致矛盾，证明原假定成立，原公式不是重言式。,（pq）（qr）（pr） 1） F 2） T F 3） T T T F 4） T T F F 5） q真与 q假 矛盾 6)证明原假定为假，原公式是重言式,（ ( p q ) q ） p 假 （1） 真 假 （2） 真 真 （3）假 假 （4） q假与 q真矛盾 （5） 证明原假定为假，原公式是重
8、言式,（( p q )p ） q 假 真 真真 假 假 真 证明原假定成立，原公式不是重言式,二、命题逻辑的公理系统 命题演算是命题逻辑的形式系统。 形式系统是指用人工语言表示的系统。 形式系统只考虑符号与符号之间的关系。 一个形式系统通常包括形式语言与演绎系统。 形式语言：包括初始符号与形成规则 演绎系统：包括公理、推理规则与定理。,一个形式公理系统一般由初始符号、形成规则、初始公式与变形规则四个部分组成 。 希尔伯特（DHilbert）与阿克曼(Wackermann)提出的系统，简称系统P。,P系统包括如下出发点： （一）初始符号： （1）命题变项：p，q，r，p1， （2）联结词：否定，
9、析取 （3）辅助符号：（，）。,二）形成规则： （1）一个命题变项是合式公式。（2）如果符号序列A是合式公式，那么A也是合式公式。 （3）如果符号序列A和B是合式公式，那么AB是合式公式。 （4）只有符合上面三条的符号序列是合式公式。,（三）定义：定义1：（AB）=df（AB）定义2：（AB）=dfAB定义3：（AB）=df（AB）（BA）,四）公理：公理1：（pp）p公理2：p（pq）公理3：（pq）（qp）公理4：（qr）（pq）（pr）,（五）推演规则： （1）代入：将合式公式A中出现的某初始符号全部代以某一合式公式B，从而得到合式公式A（/B）。 （2）分离：从A和AB可推出B。 （3
10、）定义置换：定义两边的公式可互相替换。,定理1： (qr)(pq)(pr) 证明： （1）、 （qr）（pqpr） （公理4） （2）、 （qr）（pqpr） （1）式代入：p/p） （3）、 （qr）（pq）(pr)） （2）式定义置换：pq/pq，pr/ pr）,定理2：pp 证明： 1、p（pq） (公理2) 2、p（pp） ( 1代入q/ p) 3、（pp）p （公理1） 4（qr）（pq）（pr） ( 定理1) 5、(ppp)（(ppp)(pp)） ( q/ pp，r/ p) 6、（p（pp）（pp） （ 5、3分离） 7、pp (6、2分离),定理3： pp 证明：（1）、 pp（
11、2）、 pp （1）式定义置换：pp/pp）,根据公理3：（pq）（qp），可以从AB得BA。此推演规则叫“析取交换”规则。 定理4： pp 证明：（1）、 pp （定理（3）（2）、 pp （1）式析取交换）,定理5： p p 证明：（1）、 pp （定理（4）（2）、pp(1)代入p/p)（3）、 p p（2）式定义置换：p p/p p ）,定理5： q（pq） 证明： 1、p（pq） (公理2) 2、q（ q p ）（p / q 、 q/ p ） 3、（qp）（pq）（析取交换） 4、（qr）（pq）（pr） (公理4),5、（qp）（pq） （ q （qp） （q （pq）（4代入：q
12、/ qp、r/ pq 、 p/ q） 6、（q（qp）（q（pq）(3、5分离) 7、 （q（pq）(2、6分离) 8、 q（pq）（7式定义置换：pp / pp ）,有些定理的证明不需要依赖于其它定理，而大部分定理的证明则需要依赖于其它定理，这种依赖于其它定理的证明实际上是对证明过程的简化。假如把所依赖的其它定理证明过程也写出来，那么整个证明过程就会非常复杂、冗长。,三、命题逻辑的自然推理系统 自然推理系统没有公理，只有一组推理规则，它从假设前提出发进行推演，在推理过程中随时引入假设，并根据规则消去假设，最后获得被求证公式。 命题逻辑的自然推理系统也有很多。,（一）形式语言 （1）、初始符号： A、命题变项：p，q，r，p1， B、联结词：否定，析取，合取，蕴涵，等值。 C、辅助符号：（，）。,（2）形成规则： A、任一命题变项是合式公式。 B、如果A是合式公式，则A是合式公式。 C、如果A和B是合式公式，则AB、AB、AB、AB是合式公式； D、只有符合以上三条的是合式公式。,（二）推理规则： （1）假设引入规则（P）：可按推演需要随时引入一个假设前提。 （2）重复规则：先前已出现的前提可在以后的证明过程中重复引用。 （3）合取引入规则（）：A ，B AB,（4）合取消除规则（-）：AB AB A B （5）析取引入规则（）：A B AB AB,
