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

Противоречием {тождественно ложной пропозициональной формой) называется пропозициональная форма, принимающая значение Л при любой совокупности истинностных значений пропо­ зициональных букв, входящих в нее. . Примеры противоречий: J&14,1 As]А. Истинностная таблица для противоречия, очевидно, имеет в результирующем столбце только значения Л. Очевидно, что пропозициональная форма А является тавтологи­ ей тогда и только тогда, когда есть противоречие. Тавтологию будем обозначать через Г, а противоречие - через П. Сформулируем и докажем две несложные теоремы. Теорема 1.1. ЕслиЛ иЛ=>В-тавтологии, то J5-тавтология. Доказательство. Пусть А и А=^В - тавтологии. Допустим, что при некотором распределении истинностных значений для пропози­ циональных букв, входящих ъ А п В, В принимает значение Л. По­ скольку А есть тавтология, то при этом распределении истинностных значений А принимает значение И. Тогда А=^В получит значение Л. Это противоречит предположению о том, что есть тавтология. Теорема доказана. Теорема 1.2. Если^4 есть тавтология, содержащая пропозицио­ нальные буквы А], Аг,..., An, и В получается из А подстановкой в А пропозициональных форм А], А^... А„ вместо букв Аь Аг,..., А„ соот­ ветственно, то В есть тавтология, т.е. подстановка в тавтологию при­ водит к тавтологии. Доказательство. Пусть задано произвольное распределение истинностных значений для пропозициональных букв, входящих в В. Формы А ], А 2,..., А п примут тогда некоторые значения X], хг,..., х„ (каждое Xi есть И или Л), Если придадим значения 2 2