Математическая логика и теория алгоритмов

Теорема 1.10. Для того, чтобы форма Л была противоречием, необходимо и достаточно, чтобы равносильная ей д.н.ф. содержала в каждом слагаемом хотя бы одну пару множителей, из которых один - некоторая пропозициональная буква, а второй - отрицание этой бук­ вы. Доказательство. Пусть для Л равносильной ей д.н.ф. является форма В ]V ^2 V...V J B A (А: > 1), (1-10) где В, ( l<i< к) есть элементарное произведение. Дизъюнкция (1.10) будет противоречием тогда и только тогда, когда будет противоречием каждая Bi (1< i< к). Д-- элементарное про­ изведение и по теореме 1.8 будет противоречием тогда и только тогда, когда содержит хотя бы одну пару множителей, из которых один - некоторая буква, а второй - отрицание этой буквы. Теорема доказана. Следствие 1.1. Форма Л будет выполнимой, если равносиль­ ная ей д.н.ф. содержит'хотя бы одно слагаемое, в котором нет таких множителей, что один из них - некоторая пропозициональная буква, а другой множитель - отрицание этой буквы. Пропозициональная форма называется конъюнктивной нор­ мальной формой (к.н.ф.), если она представляет собой конъюнкцию элементарных сумм. Легко доказать следующую теорему. Теорема 1.11. Для каждой пропозициональной формы существует равносильная ей к.н.ф. (не единственная). Можно сформулировать правила для нахождения д.н.ф. и к.н.ф., равносильных заданной форме. Пусть задана форма Л: 1) исключить т А все связки, кроме ] , &, v ; 2) добиться, чтобы 1 относилась только к пропозициональным буквам; 33