简化真值表方法

真值表方法是计算真值的重要方法。但是,如果一公式里的命题变项多过两个,或公式较长时,那么相应的真值表就较为复杂,因此有必要把真值表方法简化。常用的一种简化方法适用于蕴涵式。其主要思想是:为了说明一蕴涵式常真,要求证明:不论其中变项取什么值,公式不会假。因为,一个蕴涵式A→B,只有当前件A真而后件B假时,它才是假的。简化方法就是要证明:不论其中变项取什么值,前件A真而后件B假是不可能的要使前件真而后件假,对变项赋值时必然会导致矛盾。例如要说明“((p→q)∧p)→q”是重言式,则只需证明(pq)Ap真,q假是不可能的。如果设前件真,后件假,那么有q假,此时p如真,p→q假;p如假p→q真,但两种情况前件(p→q)∧p都假因而前件真后件假是不可能的。所以原公式为一重言式。

真值表方法(truth table method)一种求真值的重要方法.指利用真值表来求命题演算公式真值的方法。

公式介绍

这种方法首先列出公式中所有变元的各种可能的真值组合，即指派，然后遵循由简到繁的原则逐步列出各指派所对应的该公式的子公式的真值，最后列出该公式的真值.例如，求公式非p→q、非q→p的真值的真值表如下:

从上表可以发现a是永真公式.真值表方法是命题逻辑语义部分的重要方法，它有许多重要作用，如求成真指派，求成假指派，证明一个公式是永真公式，可满足公式等.其缺点是对于复杂的公式，用此法工作量太大.

简介

真值表可化归性(truth-table reducibility) m化归的一种推广.直观地，对任意自然数集A和B,A可真值表化归到B记为A镇B，是指对任意x，可能行地求解一系列问题“y, E By, y2 E B}，一"y。 E B}y}，若这些回答在一个(可由二能行计算出的)真值表中对应真值，则xEA，否则x贫A.而m化归只能提一个问题，且真值表中，真只对应真，假只对应假.形式地，对自然数集A,B，若存在递归函数f，使得对所有二，xEA，当且仅当B满足tt条件f(二)，则称A可真值表化归到B，记为A}t,B(参见“真值表条件”).真值表可化归性也可等价定义为:对自然数集A,B，若存在递归函数.f}g，使得二EA，当且仅当对某个yEDK(二，,B卜f (x) =D,，则称A可真值表化归到B.其中D二表示典则下标为二的有穷集.若A<B &. B} A，则称A与B tt等价，记为

A=B.

真值表化归弱于m化归与btt化归，但强于wtt化归与T化归.对tt化归而言，所有递归集之间都可互相化归，且对一切自然数集.9 , A镇A. tt化归是波兰一美国数理逻辑学家波斯特((Post,E. L.)于1944年引人的.2100433B

简化函数是在一个子集上不小于一个给定函数的一族函数的下确界。

设Φ是一族从Ω到[0, ∞]的下半连续的函数u所组成的凸锥（必要时设 ∞∈Φ），f为E(E⊂Ω)到[0, ∞]的函数，令