命题演算

来自计算思维百科
跳转至: 导航搜索

在数学中或者在其他领域内,经常会出现一些推断式的陈述,其中一类形如”如果三角形为直角三角形,那么其中某两边的平方和等于第三边的平方”,这类陈述反过来也是对的,“如果三角形某两边的平方和等于第三边的平方,那么它是直角三角形”;还有一类形如“如果a=1,b=0,那么a>b”,这类陈述反过来就不对了,“如果a>b,那么a=1,b=0”。那么,是什么造成的这种差异?命题演算就可以回答这个问题,命题演算是研究关于命题如何通过一些逻辑连词构成更复杂的命题以及逻辑推理的方法。

命题演算.png

基本概念

最常用的一个命题演算系统是由公式集L(X)(简单的可以理解为由一些字母以及—>和逻辑运算符所组成的串构成)以及如下公理集L和演绎规则(MP)所构成。如果我们把命题看作运算的对象,如同代数中的数字、字母或代数式,而把逻辑连接词看作运算符号,也就是命题的演算。

这样的逻辑运算也同代数运算一样具有一定的性质,满足一定的运算规律,如满足交换律、结合律、分配律等。利用这些定律,我们可以进行逻辑推理,可以简化复合命题,可以推证两个复合命题是不是等价等。

命题演算的一个具体模型就是逻辑代数,也就是布尔代数。逻辑代数的基本运算是逻辑加、逻辑乘和逻辑非,即命题演算中的或、与、非,运算对象只有两个数“0”和“1”,相当于命题演算中的“真”和“假”。

应用范围

命题演算在逻辑推理中、电路分析中以及自动控制方面有着广泛应用。

使用方法及步骤

先把命题符号化,根据公理集和演算规则进行运算。

应用案例

应用1-审查推理

案例

公安人员审查一件盗窃案,已知的事实如下:

  1. 甲或乙盗窃了录音机;
  2. 若甲盗窃了录音机,则作案时间不能发生在午夜前;
  3. 若乙的证词正确,则午夜时屋里灯光未灭;
  4. 若乙的证词正确,则作案时间发生在午夜前;
  5. 午夜时灯光灭了。

解决步骤

首先将已经查明的事实符号化。

设: p:甲盗窃录音机;

   q:乙盗窃录音机;

   r:作案时间发生在午夜前;

   s:乙的证词正确;

   t:午夜时灯光未灭;

根据查明的事实,p或q,p→~r(意思是p可以推出不是r),s→t,~s→r,~t的值均为真,据此确定p和q的值,求解如下:

把上述五个已知为真的条件并起来然后进行合并转化,因为非t的值为真,可推出~s,由~s又可推出r,由r即可推出~p,同时q的结果也就得到了。最后得出~p,q,~s,r,~t为真。

因此,他们的成真赋值分别为p=0,q=1,s=0,r=1,t=0。因此,结论是乙盗窃录音机。此外还有下述结论:甲没有盗窃录音机,作案时间不是在午夜之前,乙的证词错误,午夜时灯光已灭。

应用2-你答我猜

案例

生活中我们常常玩到一个你答我猜的游戏,先让我们心中想着某一事物,然后机器给我们出问题,我们根据所想事物的特征进行回答,然后机器根据我们的回答的是或否来进行运作,最后机器会一步步缩小范围找到你心中所想的东西。

解决步骤

上述机器给出的问题就是命题,而问题之间通常需要命题的与,或,非来进行联系,而我们的回答也就是成真赋值。这里就是用到了命题演算的方法。

可以体现的计算思维

命题演算体现了计算思维的抽象思想,常常需要把命题抽象符号化,然后再进行逻辑运算。