12.0.3. Метод доказательства от противного

Как уже отмечалось, высказывание Т следует из множества предложений если Т есть логическое следствие высказываний (предложений) из Предположим для простоты, что Т состоит из единственного предложения Т. Рассмотрим множество предложений

Для того чтобы высказывание было истинным, все предложения и Т должны быть истинными. В свою очередь значения истинности этих предложений будут определяться значениями истинности содержащихся в них атомов, причем значения истинности должны присваиваться атомам так, чтобы по крайней мере один литерал в каждом предложении был истинным. Отдельное присваивание атомам значений истинности называется моделью. Еели влечет за собой Т, то не существует модели, в которой высказывание истинное, а Т нет. Вместе с тем, если высказывание Т истинное, его отрицание должно быть ложным. Поэтому если влечет за собой Т, высказывание

должно быть ложным для любой модели.

Предположим на некоторое время, что число атомов конечно. Тогда существует конечное число моделей, так как атомам можно присвоить логические значения только 2 различными способами. Ясно, что можно было бы сделать это каким-то систематическим образом и каждый раз определять значения истинности и для и Т. Если для всех моделей высказывание (5) окажется ложным, то, безусловно, влечет за собой Т. Такое рассуждение, называемое доказательством от противного, составляет основу всех излагаемых в этой главе методов доказательства теорем.