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

Ясно, что выяснение выполнимости А равносильно выяснению, является ли А противоречием или нет, что, в свою очередь, равно­ сильно выяснению, является ли "U тавтологией или нет. Таким обра­ зом, если есть метод, позволяющий для произвольной формы конеч­ ным числом действий выяснить, тавтология это или нет, то можно решить вопрос - выполнима или нет произвольная форма Л. Для этого достаточно выяснить ']А ~ тавтология или нет. Если 14 - тавтология, то Л - противоречие, следовательно, А невыполнимо, если же 1 /1 - не тавтология, то А выполнимо. Проблема разрешимости (логики высказываний) полностью ре­ шается, например, с помощью таблиц истинности. Если пропозицио­ нальная форма содержит п различных букв, то, как известно, ее таблица истинности имеет 2" строк. При больших значениях п составление таблиц истинности и выяснение выполнимости по ним является громоздкой операцией. Для решения проблемы раз­ решимости существуют и другие способы, основанные на приведении к так называемым нормальным формам. Эти формы и способы реше­ ния с их помощью проблемы разрешимости будут рассмотрены. Шел я садом однажды и вдруг увидал, Как делили коврижку Сова и Шакал. И коврижку Шакал проглотил целиком, А Сове только блюдечко дал с ободком. А потом предложил ей: «Закончим дележ - Ты возьми себе ложку, я — вилки и нож». И наевшись, улегся Шакал па траву. Но сперва на десерт проглотил он... Л. Кэрролл * § 5. Равносильность пропозициональных форм Пропозициональные формы А ш В называются равносгтьньши, если при каждой совокупности значений всех пропозициональных " Здесь и далее, цитаты из произведений Л. Кэрролла приводятся по переводу с английского языка, выполненному Н. Димуровой, в котором приведены стихи в переводах С. Мари^ака, Д. Орловской и О. Седаковой. 24