yandex rtb 1
ГоловнаЗворотній зв'язок
yande share
Главная->Математика і інформатика->Содержание->2.3. Метатеоремы о тавтологиях.

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

2.3. Метатеоремы о тавтологиях.

Теорема 2.1. Правило отделения. Если А - тавтология и АВ -тавтология, то В - тавтология, т. е. |=А, |=АВ  |=3

Правило отделения устанавливает логическое следование А, АВ|=В и называется modus ponens (MP).

Теорема 2.2. Правило подстановки. Если А – тавтология, содержащая пропозициональные переменные а12,…….аn, то формула В, полученная из А заменой каждого вхождения а1 на некоторую формулу А1, также будет тавтологией.

Доказательство.

Предположим |В|=F|. Тогда AB|=|AF|=T (по условию теоремы). Следовательно, |A|=F, что невозможно, так как |=А (А - ч антология),

Пусть задано истинностные распределение для пропозициональных букв входящих в В. Формулы А1 для этого распределения примут некоторые  значения где 1, есть Т или F. Если такое же распределение придать формулам А1,..,Аn, то значение формулы B совпадает со значением формулы А. Но так как А есть тавтология, то это значение будет Т при любом истинностном распределении букв, входящих в В. Следовательно В есть тавтология.

Пример. Формула АА) - тавтология. заменим А на AvB. Получим новую тавтологию: |=AvB(BAvB). Таким образом, каждую тавтологию можно рассматривать как схему из которой с помощью подстановки можно получить бесконечное множество тавтологий.

Теорема 2.3. Правило эквивалентной замены. Если В получает из А подстановкой В1 вместо одного или нескольких вхождений А1 в А, то ((А1В1)( АВ)) есть тавтологии, и, следовательно, если А1 и В1 логически эквивалентны, то А и В также логически эквивалентны.

Иными слонами, если есть тавтология А, и в ней есть подформула А1, и если заменить А, на эквивалентную ей формулу В1, то полученная формула В будет эквивалентна А.

Доказательство. Рассмотрим произвольное истинностное распределение переменных, входящих в А, В, А1, В1. Если при этом распределении А1, и В1, имеют различные значения, то А1В1=F и, следовательно, ((А1В1)( АВ)) примет значение Т. Если же А, и В, принимают одинаковые значения, то одинаковые истин постные значения примут А и В, так как В отличается от А только тем, что некоторые вхождении подформулы А, заменены в ней на В1, которая имеет то же самое истинностное значение. Следовательно, в этом случае, если A1B1 =T, то и АВ=Т, и  ((А1В1)( АВ)) есть тавтология.

Пример. |=АА)  -   тавтология,  ВA¬ BvA,  следовательно, |=А¬ BvA       - тоже тавтология.   Тавтологией также будет формула: |=А¬(В&¬А).

Рассмотренные     метатеоремы     дают     возможность     получать     новые тавтологии и новые правила вывода из уже имеющихся.

 

15