简介

真值表可化归性(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