充足可能性問題のyesとnoを逆転させ、論理式に否定をかけて変形すると、トートロジー判定問題になる。