真值表方法

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

公式介紹

這種方法首先列出公式中所有變?cè)母鞣N可能的真值組合，即指派，然后遵循由簡(jiǎn)到繁的原則逐步列出各指派所對(duì)應(yīng)的該公式的子公式的真值，最后列出該公式的真值.例如，求公式非p→q、非q→p的真值的真值表如下:

從上表可以發(fā)現(xiàn)a是永真公式.真值表方法是命題邏輯語(yǔ)義部分的重要方法，它有許多重要作用，如求成真指派，求成假指派，證明一個(gè)公式是永真公式，可滿足公式等.其缺點(diǎn)是對(duì)于復(fù)雜的公式，用此法工作量太大.

真值表方法是計(jì)算真值的重要方法。但是,如果一公式里的命題變項(xiàng)多過(guò)兩個(gè),或公式較長(zhǎng)時(shí),那么相應(yīng)的真值表就較為復(fù)雜,因此有必要把真值表方法簡(jiǎn)化。常用的一種簡(jiǎn)化方法適用于蘊(yùn)涵式。其主要思想是:為了說(shuō)明一蘊(yùn)涵式常真,要求證明:不論其中變項(xiàng)取什么值,公式不會(huì)假。因?yàn)?一個(gè)蘊(yùn)涵式A→B,只有當(dāng)前件A真而后件B假時(shí),它才是假的。簡(jiǎn)化方法就是要證明:不論其中變項(xiàng)取什么值,前件A真而后件B假是不可能的要使前件真而后件假,對(duì)變項(xiàng)賦值時(shí)必然會(huì)導(dǎo)致矛盾。例如要說(shuō)明“((p→q)∧p)→q”是重言式,則只需證明(pq)Ap真,q假是不可能的。如果設(shè)前件真,后件假,那么有q假,此時(shí)p如真,p→q假;p如假p→q真,但兩種情況前件(p→q)∧p都假因而前件真后件假是不可能的。所以原公式為一重言式。

簡(jiǎn)介

真值表可化歸性(truth-table reducibility) m化歸的一種推廣.直觀地，對(duì)任意自然數(shù)集A和B,A可真值表化歸到B記為A鎮(zhèn)B，是指對(duì)任意x，可能行地求解一系列問(wèn)題“y, E By, y2 E B}，一"y。 E B}y}，若這些回答在一個(gè)(可由二能行計(jì)算出的)真值表中對(duì)應(yīng)真值，則xEA，否則x貧A.而m化歸只能提一個(gè)問(wèn)題，且真值表中，真只對(duì)應(yīng)真，假只對(duì)應(yīng)假.形式地，對(duì)自然數(shù)集A,B，若存在遞歸函數(shù)f，使得對(duì)所有二，xEA，當(dāng)且僅當(dāng)B滿足tt條件f(二)，則稱A可真值表化歸到B，記為A}t,B(參見“真值表?xiàng)l件”).真值表可化歸性也可等價(jià)定義為:對(duì)自然數(shù)集A,B，若存在遞歸函數(shù).f}g，使得二EA，當(dāng)且僅當(dāng)對(duì)某個(gè)yEDK(二，,B卜f (x) =D,，則稱A可真值表化歸到B.其中D二表示典則下標(biāo)為二的有窮集.若A<B &. B} A，則稱A與B tt等價(jià)，記為

A=B.

真值表化歸弱于m化歸與btt化歸，但強(qiáng)于wtt化歸與T化歸.對(duì)tt化歸而言，所有遞歸集之間都可互相化歸，且對(duì)一切自然數(shù)集.9 , A鎮(zhèn)A. tt化歸是波蘭一美國(guó)數(shù)理邏輯學(xué)家波斯特((Post,E. L.)于1944年引人的.2100433B