完全集

完全集，设 F 是 n 元联结词，p1，，pn 是不同的命题变元。如果公式 A 中不出现除 p1，，pn 之外的命题变元，并 A⇔Fp1pn，则称 A 定义 F。如果存在由联结词集合 S 生成的公式定义 F ，则称 F 可由 S 定义。设 r 是某种归约。一个集合 A 是 r 完全的是指它是递归可枚举的且对所有递归可枚举集 W 有。