Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Введем некоторые соглашения о более экономном употреблении скобок в записях форм. Эти соглашения облегчат чтение сложных выражений. Во-первых, будем опускать в форме внешнюю пару скобок (в случае про­ позициональной буквы этой внешней пары скобок нет по определению). Во-вторых, если форма содержит вхождения только одной бинарной связ­ ки (т.е. &, V, ^ или =), то для каждого вхождения этой связки опускаются внешние скобки у той из двух, соединяемых этим вхождением формул, которая стоит слева. Пример. AvBvCvA пишется вместо (((AvB)vC)vA), а В^В^А^(С^А) - вместо (((В^В)^А)^(С^А)). В-третьих, договоримся считать связки упорядоченными следуюш,им обра­ зом: —1, с&, v; ^ , = и будем опускать во всякой форме все те пары скобок, без которых возможно восстановление этой формы на основе следуюш,его правила. Каждое вхождение знака —i относится к наименьшей пропозициональной форме, следуюш,ей за ним. После расстановки всех скобок, относяш,ихся ко всем вхождениям знака —i, каждое вхождение знака & связывает наименьшие формы, окружаюш,ие это вхождение; затем каждое вхождение знака v связыва­ ет наименьшие формы, окружаюш,ие это вхождение, и аналогично для ^ и =. При применении этого правила к одной и той же связке продвигаемся слева на­ право. Пример. В формуле А= -А&В^С v —iD скобки восстанавливаются сле- дуютттими шагами: A^^)&B^v(^), А^(-^)&В) v(^D), А^(-^)&В) ^(С v(^)), А^(Ы)&В)^(Су(^0))), (А^(Ы)&В)^(Су(^)))). Однако не всякая форма может быть записана без скобок. Так, нельзя опустить оставшиеся скобки в формах: А&(В^>С), А^(В^>С), —i(A vB). § 3. Тавтологии (общезначимые формулы). Противоречия Тавтологией {тождественно истинной пропозициональной формой или общезначимой формулой) называется пропозициональная форма, которая при­ нимает значение И при любой совокупности истинностных значений пропози­ циональных букв, входятттих в нее. Примером тавтологии является А v —А, в чем легко убедиться, составив таблицу истинности. Другие примеры тавтологий: А^А, (А=В)=(В=А). Запись 1= Л в логике высказываний означает, что А является тавтологией (о бш,езначимой). 10