离散数学的一个推理例子（离散数学推理的三要素）

张三说李四在说谎，李四说王五在说谎，王五说张三、李四都在说谎，问三人中谁说假话？

解：设P：张三说真话；Q：李四说真话；R：王五说真话。

则前提为：

PnotQ,notPQ,QnotR,notQR,R(notP∧notQ),notR(P∨Q)。

这里首先要弄懂“张三说李四在说谎”这个命题为什么可以用公式PnotQ表示。

我们知道，PQ是一个条件命题，其真值表如下：

这里我们必须认为“张三说李四在说谎”这句话是对的。

由图1，得到如下真值表：

按照 P：张三说真话；Q：李四说真话 的假设，图2真值表PnotQ第一行

就表示在张三说假话和李四也说假话的时候，PQ和PnotQ的结果都是真。

意思就是，在张三说假话的前提下，我们根本无法判断李四到底说的是真话还是假话，所以我们只能认为真值表的第一行是正确的：

同样，第二行我们也只能认为是正确的。

第三行

因为我们事先假设“张三说李四在说谎”这句话是对的，那么P=1和notQ=1则表示，在张三说真话的前提下，李四是在说假话，PnotQ=1，表示其结果是正确的。

注意这个时候P=1和Q=0，PQ=0。意思就是，如果承认PnotQ=1，则必然PQ=0。

意思就是，在张三说真话的前提下，如果假设“张三说李四在说谎”这句话是对的，

则必然有PnotQ=1。

同理，因为PnotQ表示承认“张三说李四在说谎”这句话是对的，那么PQ就表示承认“张三说李四在说真话”这句话是对的。这个时候就有P=1和Q=0，PQ=0。

第四行

则是第三行的必然结果。

由上分析，以PnotQ表示承认“张三说李四在说谎”这句话是对的这样的假设，在逻辑上不存在任何问题。

有了这个基础以后，后面的解答就很容易了：

第一句PnotQ，这个表达式放在这里作为条件，其结果一定要是真，也就是我们首先认为，张三说李四在说谎这句话是对的，并从这个前提出发进行推导。

注意，第一句PnotQ的整个结果一定要是真，并不等于P一定要等于1。

第二句是同样的前提。

第三句则由前面两句得到。

第四句也是前提。

第五句由第三句和第四句得到。

第六句由第五句得到。

关键第七句怎么得到。

由第一句PnotQ假设为真，我们得到P、Q不可能同时为真，也就是张三李四不可能同时说真话，当然也表示张三李四不可能同时说假话。即P、Q的取值必然不同。

也由此得到notP∧notQ不可能等于1，但整个第六句的结果必须是真，由此得到第七句notP为真。

同样，第八句是前提，第九句由第七和第八句得到。

第十句是前提，十一句由第九第十句得到。

最后得到第十二句。

也就是结论：张三和王五说谎，李四说真话。

前面推导中多次应用：

P,PQQ

即如果在P为真的前提下，要使得PQ也为真，此时Q必然为真。也就是图1中真值表的第四行。