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

公式介紹

這種方法首先列出公式中所有變元的各種可能的真值組合，即指派，然后遵循由簡到繁的原則逐步列出各指派所對應的該公式的子公式的真值，最后列出該公式的真值.例如，求公式非p→q、非q→p的真值的真值表如下:

從上表可以發現a是永真公式.真值表方法是命題邏輯語義部分的重要方法，它有許多重要作用，如求成真指派，求成假指派，證明一個公式是永真公式，可滿足公式等.其缺點是對于復雜的公式，用此法工作量太大.

真值表方法是計算真值的重要方法。但是,如果一公式里的命題變項多過兩個,或公式較長時,那么相應的真值表就較為復雜,因此有必要把真值表方法簡化。常用的一種簡化方法適用于蘊涵式。其主要思想是:為了說明一蘊涵式常真,要求證明:不論其中變項取什么值,公式不會假。因為,一個蘊涵式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 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