Спирина, М.С. Дискретная математика

законов логики: А А = 0. Покажем это на примере высказываний. То, что это тоже формальная теория, будет показано далее. Не­ посредственным выводом будет импликация-тавтология из про­ изведения вы сказы ваний :/,,/2, ...,/„ (= /суть (Д ■... ■/„) - > / = 1. Действительно, пусть получены два противоположных_вывода, причем_обеимпликации истинны. Тогда (S -> А) ■(S -» А) = (S v v А) • ( 5 v А) = S, что подразумевает или противоречивость сис­ темы S, или невыводимость формулы А. Иллюстрацией примера того, что из двух противоположных посы­ лок, одна из которых в двоичной логике всегда ложна, следует любая бессмыслица, могут служить рассуждения философа и математика Г. X. Харди. На просьбу доказать, что из ложной посылки можно вывести все, что угодно, он предложил такие «рассуждения». Рассмотрим одно­ временно две противоположные посылки: 2 - 2 = 4 и 2 - 2 = 5 и докажем, что если они обе истинны, то Мак-Таггарт — папа римский. Итак, если 2 - 2 = 4 и 2 - 2 = 5, то 4 = 5. Вычтем из обеих частей равенства число 3, имеем 1 = 2, т.е. двое — папа римский и Мак-Таггарт суть один и тот же человек. Полнота. В п. 4.8.3 подробно рассматривались полные системы булевых функций. Аналогичные рассуждения применимы к фор­ мулам в формальных теориях. Из аксиом должны следовать ис­ тинные (в смысле некой модели) высказывания, и, наоборот, для полноты нужно, чтобы все истинные высказывания модели выводились из аксиом. Если L — модель формальной теории Т (х: F —> L), то Т называется полной, если всякому истинному высказыванию из L соответствует теорема из Т, т.е. V/ е L: v(/) = = 1 3/ = лг '(/) е { h\ | - И}. Полнота такой системы означает, что тот набор элементарных функций или аксиом, который принят за базисный, достаточен для того, чтобы с их помощью вывести любые другие функции и суждения этой системы. Независимость. В определении функционально полных систем функций (см. п. 4.8.3) базисом называлась такая функционально полная система, удаление любой функции из которой превраща­ ет ее в функционально неполную. Добавление же произвольной функции в базис не влияет на функциональную полноту, но ли ­ шает систему свойства базиса. Так, в R3 есть только три линейно независимых вектора, например декартов базис (0, 0, 1), (0, 1, 0) и (0, 0, 1). Любые четыре вектора уже будут зависимы, т.е. четвер­ тый можно разложить по первым трем. То же справедливо для системы аксиом формальной теории. Независимой системой аксиом непротиворечивой формальной теории Т = (A, F, Р, R) называется такая система, в которой любая аксиома не может быть выведена на основании всех осталь­ ных аксиом этой системы, т.е. Va е Р {И\Р \{о} (— h) Р - 0 . 214