計算可能な集合の性質

例えば、A,Bが計算可能であった場合、ＡまたはＢの集合も計算可能であることを示す場合は、条件がＯＲのプログラムを作ってやれば証明が可能である。同様にＮＯＴとＡＮＤも証明することができる。