«Ш. И. ГАЛИЕВ МАТЕМАТИЧЕСКАЯ ЛОГИКА И ТЕОРИЯ АЛГОРИТМОВ УЧЕБНОЕ ПОСОБИЕ Казань 2002 2 УДК 6 Галиев Ш. И. Математическая логика и теория алгоритмов. – Казань: Издательство КГТУ им. А. Н. Туполева. 2002. - 270 с. ISBN ...»

КАЗАНСКИЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

им. А. Н. Туполева

Ш. И. ГАЛИЕВ

МАТЕМАТИЧЕСКАЯ ЛОГИКА

И ТЕОРИЯ АЛГОРИТМОВ

УЧЕБНОЕ ПОСОБИЕ

Казань 2002

2

УДК 6

Галиев Ш. И. Математическая логика и теория алгоритмов. – Казань: Издательство КГТУ

им. А. Н. Туполева. 2002. - 270 с.

ISBN 5-93629-031-X Пособие содержит следующие разделы. Логику высказываний и предикатов с приложениями, в том числе метод резолюций и элементы его реализации в языке ПРОЛОГ. Классические исчисления (высказываний и предикатов) и элементы неклассических логик: трёхзначные и многозначные логики, модальную, временную и нечеткую логики. Теорию алгоритмов: нормальные алгоритмы, машины Тьюринга, рекурсивные функции и их взаимосвязи. Понятие о сложности вычислений, различные (по сложности) классы задач и примеры таких задач.

Все главы снабжены контрольными вопросами и упражнениями, приведены варианты типовых заданий и тесты для самоконтроля усвоения материала.

Пособие предназначено студентам технических вузов по специальности направления «Информатика и вычислительная техника» и может быть использовано для специальности 2202 и других специальностей данного направления.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ Глава 1. ЛОГИКА ВЫСКАЗЫВАНИЙ § 1. Высказывание. Логические операции § 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности § 3. Упрощения в записях пропозициональных форм § 4. Тавтологии (общезначимые формулы). Противоречия § 5. Равносильность пропозициональных форм § 6. Важнейшие пары равносильных пропозициональных форм § 7. Зависимости между пропозициональными связками § 8. Нормальные формы § 9. Совершенные нормальные формы § 10. Булева (переключательная) функция § 11. Приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем § 12. Приложение алгебры высказываний к анализу и синтезу схем из функциональных элементов § 13. Вопросы и темы для самопроверки § 14. Упражнения Глава 2. ЛОГИКА ПРЕДИКАТОВ § 1. Понятие предиката § 2. Кванторы § 3. Формулы логики предикатов § 4. Интерпретация. Модель § 5. Свойства формул в данной интерпретации § 6. Логически общезначимые формулы. Выполнимые и равносильные формулы § 7. Правила перенесения отрицания через кванторы § 8. Правила перестановки кванторов § 9. Правила переименования связанных переменных § 10. Правила вынесения кванторов за скобки. Предваренная нормальная форма § 11. Вопросы и темы для самопроверки § 12. Упражнения Глава 3. ЛОГИЧЕСКОЕ СЛЕДСТВИЕ И МЕТОД РЕЗОЛЮЦИЙ § 1. Логическое следствие и проблема дедукции в логике высказываний § 2. Резольвента дизъюнктов логики высказываний § 3. Метод резолюции в логике высказываний § 4. Метод насыщения уровня § 5. Стратегия вычёркивания § 6. Лок-резолюция § 7. Метод резолюции для хорновских дизъюнктов § 8. Преобразование формул логики предикатов. Сколемовская § 11. Приложение метода резолюций для анализа силлогизмов § 12. Использование метода резолюций в языке ПРОЛОГ § 1. Понятие об эффективных и полуэффективных процессах § 4. Пример полуформальной аксиоматической теории - геометрия § 9. Эквивалентность двух определений непротиворечивости § 10. Производные (доказуемые) правила вывода в исчислении § 12. Другие аксиоматизации исчисления высказываний § 4. Нечёткие высказывания и максиминные операции над ними § 2. Алфавит, слова, алгоритм в алфавите. Вполне эквивалентные § 4. Функции частично вычислимые и вычислимые по Маркову § 5. Замыкание, распространение нормального алгоритма § 10. Связь между машинами Тьюринга и нормальными алгоритмами § 11. Основная гипотеза теории алгоритмов (принцип нормализации § 13. Примеры алгоритмически неразрешимых массовых проблем § 14. Сведения любого преобразования слов в алфавите к вычислению значений целочисленных функций § 15. Примитивно рекурсивные и общерекурсивные функции § 16. Примитивно рекурсивность некоторых функций. Частично Глава 7. СЛОЖНОСТЬ ВЫЧИСЛЕНИЙ С ПОМОЩЬЮ Тест по логическому следствию и методу резолюций (тест № 3) Тест по неклассическим логикам и сложности вычислений (тест

ВВЕДЕНИЕ

Логика обычно понимается как наука о способах доказательств и опровержений. Математическая логика – это логика, развиваемая с помощью математических методов.

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

1. Все люди смертны. Сократ – человек. Следовательно, Сократ – 2. Все котята любят играть. Мура – котенок. Следовательно, Мура любит играть.

Оба эти вывода имеют одну и ту же форму: Все А суть В; С есть А;

следовательно, С есть В. Эти выводы верны в силу своей формы, независимо от содержания, независимо от того истинны или ложны взятые по себе посылки и заключения. Систематическая формализация и каталогизация правильных способов рассуждений – одна из основных задач логики. Если при этом применяется математический аппарат и исследования посвящены в первую очередь изучению математических рассуждений, то эта логика является математической логикой (формальной логикой). Данное определение не является строгим (точным) определением. Чтобы понять предмет и метод математической логики лучше всего приняться за ее изучение.

Математическая логика начала формироваться давно. Зарождение ее идей и методов происходило в Древней Греции, Древней Индии и Древнем Китае примерно с VI в. до н. э. Уже в этот период ученые пытались расположить цепь математических доказательств в такую цепочку, чтобы переход от одного звена к другому не оставлял сомнений и завоевал всеобщее признание. Уже в самых ранних дошедших до нас рукописях «канон» математического стиля изложения прочно установлен.

Впоследствии он получает окончательное завершение у великих классиков:

Аристотеля, Евклида, Архимеда. Понятие доказательства у этих авторов уже ничем не отличается от нашего.

Логика как самостоятельная наука берет свое начало в исследованиях Аристотеля (384 – 322 г. до н. э.). Великий философ древности Аристотель осуществляет энциклопедическую систематизацию античных знаний во всех областях существовавшей тогда науки. Логические исследования Аристотеля изложены, в основном, в двух его трудах «Первая аналитика» и «Вторая аналитика», объединенных под общим названием «Органон» (Орудие познания).

Следует особо отметить большое значение для становления и развития математической логики одного из самых блестящих достижений в истории человечества, а именно, превращение геометрии в точную дедуктивную систему в работе Евклида (330 – 275 г. до н. э.) «Начала». Именно этот дедуктивный подход с ясным осознанием целей и методов был положен в основу развития философской и математической мысли последующих столетий.

Также большое значение для становления и развития логики сыграли достижения в алгебре (алгебра Буля) и в других математических дисциплинах, в том числе и вновь в геометрии (создание неевклидовой геометрии - геометрии Лобачевского – Гаусса – Бойяи). Краткий обзор становления математической логики можно найти в [6].

В формировании и становлении математической логики участвовали многие и многие ученые, как древних времен, так средневековья и последующих времен.

Принципиальное и прикладное значение математической логики Принципиальное значение математической логики – обоснование математики (анализ основ математики).

Прикладное значение математической логики в настоящее время очень велико. Математическая логика применяется для следующих целей:

• анализа и синтеза (построения) цифровых вычислительных машин и других дискретных автоматов, в том числе и интеллектуальных систем;

• анализа и синтеза формальных и машинных языков, для анализа • анализа и формализации интуитивного понятия вычислимости;

• выяснения существования механических процедур для решения задач определённого типа;

• анализа проблем сложности вычислений.

Также математическая логика оказалась тесно связанной и с рядом вопросов лингвистики, экономики, психологии и философии.

В данном пособии излагаются основные понятия математической логики и теории алгоритмов. Материал, изложенный в пособии, соответствует государственному образовательному стандарту для направления «Информатика и вычислительная техника» и может быть использован для студентов обучающихся по разным специальностям этого направления.

При написании пособия использовались литература [1-31], и, конечно, использованы и другие источники. В перечень литературы включены книги, которые желательно просмотреть любознательному и требовательному студенту.

В пособии в каждой главе приведены вопросы для самопроверки теоретического материала и упражнения, предназначенные для выработки навыков решения задач и углубления знаний по излагаемой теме. Кроме того, в пособии приведены варианты типовых заданий и тесты для самоконтроля усвоения материала.

Автор выражает искреннюю благодарность рецензентам д.ф.м.-н., профессорам И. З. Батыршину и Ф. Г. Мухлисову за полезные предложения и замечания, которые позволили улучшить работу.

Автор признателен своим студентам за помощь по набору текста.

Высказыванием называется любое повествовательное предложение, которое истинно либо ложно.

Примерами высказываний в математической логике являются следующие предложения:

Сократ - человек.

Не являются высказываниями в математической логике предложения:

х > 5 (здесь х(-, ) и считается переменной).

Закройте книгу!

Данное предложение ложно.

Какое же у меня есть дело на земле?

Высказывания будем обозначать заглавными печатными латинскими буквами (А, B, С,...) и этими же буквами с числовыми индексами.

В логике высказываний отвлекаются от содержания высказывания и интересуются истинностью либо ложностью (истинностными значениями) высказывания.

Таким образом, высказывание рассматривается как величина, которая может принимать два значения: «истина» либо «ложь». В дальнейшем для краткости будем обозначать значение «истина» через И, а «ложь» - Л. Если По Синодальному изданию; по Восстановительному переводу эта фраза имеет вид: «Ибо мы не можем делать что либо против истины, а можем ради истины». Выделение слов здесь и в эпиграфе сделано согласно указанным источникам.

высказывание А истинное, то будем говорить, что А принимает значение И (истина), и писать: А = И. Если высказывание А ложное, то будем говорить, что А принимает значение Л (ложь), и писать: А = Л. Заметим, что мы не будем определять, что такое истина и что такое ложь, но считаем себя способными охарактеризовать некоторые высказывания как истинные, другие - как ложные.

Из высказываний можно образовывать другие высказывания, соединяя их различными способами, т.е. производя операции над высказываниями.

Эти логические операции над высказываниями таковы, что истинностные значения составных высказываний определяются только истинностными значениями составляющих высказываний, а не их содержательным смыслом.

1. Первой из операций над высказываниями введем отрицание. Прежде отметим, что в разговорном языке высказывание может быть отрицаемо многими способами, например: отрицанием для высказывания «2 - четное число» может служить: «2 не является четным числом», «неверно, что 2 четное число», «не имеет места, что 2 - четное число» и т.п. Мы будем строить отрицание для данного высказывания одним способом, помещая знак отрицания перед всем высказыванием.

Отрицание - логическая операция, с помощью которой из данного высказывания А образуется новое высказывание, обозначаемое А, которое истинно тогда и только тогда, когда А ложно. Следовательно, имеем следующую таблицу, которая называется таблицей истинности.

операция отрицания соответствует образованию нового высказывания из высказывания А с помощью частицы «не».

В литературе встречаются и другие обозначения для А: A или А. Отрицание является одноместной логической операцией. Другие логические операции, которые введем ниже, - двуместные операции, сложное высказывание строится из двух данных высказываний А и В.

2. Конъюнкция - логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое А&В, которое истинно тогда и только тогда, когда А и В оба истинны.

Высказывание А&В читается «А и В» и называется конъюнкцией А и В, а А и В называются конъюнктивными членами. По определению конъюнкции имеем следующую таблицу истинности.

литературе встречаются и другие обозначения, конъюнкция соответствует образованию нового высказывания из двух данных соединением их союзом "и". Выражение А&В может служить обозначением не только для высказывания А и В, но и для высказываний: «как А, так и В»; «А вместе с В»;

«А, в то время как В»; «не только А, но и В», «А, хотя и В». Очевидно, что этот список можно продолжить.

Однако, А&В не является моделью для каждого случая употребления союза «и». Поясним это. Согласно определения конъюнкции истинностные значения А&В и В&А одинаковы, т.е. А&В и В&А понимаются как равносильные (равнозначные) высказывания. В то же время высказывания «Таня проснулась и солнце взошло над горизонтом», «Солнце взошло над горизонтом и Таня проснулась» понимаются как различные. Также различны высказывания «Иванову стало жарко и он пошёл искупаться», «Иванов пошёл искупаться и ему стало жарко».

3. Дизъюнкция - логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое АВ, которое ложно тогда и только тогда, когда ложны оба высказывания А и Высказывание «АВ» читается «А или В», а А и В называются дизъюнктивными членами. Из определения видно, что операция дизъюнкции соответствует образованию нового высказывания из данных А и В соединением их связкой «или», где «или» понимается в соединительном (хотя бы одно), а не в разделительном (либо - либо) смысле.

Согласно определению дизъюнкции получим таблицу истинности:

литературном языке мы привыкли к тому, что в высказываниях «если А, то В» между посылкой А и заключением В имеется определенная (обычно причинная) связь. Если же такого рода связи между А и В нет, то не всегда ясно, истинно либо ложно высказывание «если А, то В». Неясно, например, истинными или ложными будут высказывания:

1) если 2х2=4, то Л. Н. Толстой - автор романа «Война и мир», 2) если 2х24, то Л. Н. Толстой - автор романа «Война и мир», 3) если 2х24, то А. П. Чехов - автор романа «Война и мир».

Введем правила, по которым можно будет определять истинность высказывания «если А, то В», зная только истинностные значения А и В вне зависимости от того, существует ли между А и В какая-нибудь содержательная связь или нет.

Импликация (следование)- логическая операция, с помощью которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое АВ, которое ложно тогда и только тогда, когда посылка А истинна, а заключение В ложно.

Высказывание АВ читается «если А, то В» или «из А следует В» и называется импликацией А и В.

Согласно определению импликации получим таблицу истинности:

то вне зависимости, истинно или ложно В, высказывание А, то В» не противоречит обычной практике. Иногда встречается некоторое не истинностно-функциональное употребление связки «если..., то...», связанное с законами причинности и в так называемых условных контрафактических предложениях. Но мы будем использовать, введенную импликацию, только там где не используются законы причинности и условные контрафактические предложения.

Другие обозначения импликации (следования): А В, А В.

5. Эквивалентность - логическая операция, при помощи которой из двух данных высказываний А и В образуется новое высказывание, обозначаемое АВ, которое истинно тогда и только тогда, когда А и В принимают одинаковые истинностные значения.

Высказывание АВ читается «А тогда и только тогда, когда В» и называется эквивалентностью А и В. Другие обозначения для АВ: АВ, АВ, АВ.

Из определения эквивалентности получаем следующую таблицу истинности.

высказываний, введены пять операций. С помощью этих операций из данных высказываний можно образовать новые, более сложные высказывания, истинность или доказывается, что этих операций достаточно, более того, сложное высказывание выражается с использованием только некоторых из введенных выше операций.

Отметим еще раз, что мы ввели операции над произвольными высказываниями без учета их смыслового содержания. При этом можно выяснить истинностное значение полученных высказываний, не обращая внимания на смысловое содержание высказывания. Так, например, можно образовать высказывание: «Если Иванов - студент, то 1 сентября 2002 года в Воронеже шел дождь», и это высказывание будет ложно, когда высказывание «Иванов – студент» истинно, а 1 сентября 2002 года в Воронеже дождя не было, в остальных случаях будем считать, что рассматриваемое условное предложение истинно.

Также отметим, что приведенные контрпримеры (для конъюнкции и импликации) показывают, что логика высказываний позволяет моделировать не все возможные предложения языка, а только часть. Но эта часть достаточно объемна и важна. В других главах данной работы рассмотрены логики, которые расширяют возможности логики высказываний, учитывая, например, многозначность высказываний или их возможный нечеткий характер, зависимость от времени и т. п.

§ 2. Пропозициональные буквы, связки и формы (формулы логики высказываний). Построение таблиц истинности Символы, &,,, называются пропозициональными связками.

Заглавные буквы алфавита (А,В,С,...) и те же буквы с числовыми индексами (А1,А2,...,В1,В2,...,С1,С2,...) называются пропозициональными буквами. Считается, что каждая пропозициональная буква может принимать значение И либо Л.

Выражением называется конечная последовательность определенных символов. Например, А&В - выражение, построенное из символов, &, А и В, а ?§!! - выражение, построенное из символов ?, § и !.

Пропозициональная форма представляет собой выражение, полученное по некоторым правилам из пропозициональных букв с помощью пропозициональных связок.

Индуктивное определение пропозициональной формы:

1) все пропозициональные буквы суть пропозициональные формы, 2) если А и В пропозициональные формы, то ( А), (А&В), (АВ), (АB), (АB) тоже пропозициональные формы, 3) только те выражения являются пропозициональными формами, для которых это следует из пп.1,2.

((( А)В)С).

Пропозициональные формы часто называют формулами логики высказываний.

Жирные заглавные буквы латинского алфавита (А,В,C,...) или те же буквы с числовыми индексами (А1,А2,...,В1,В2,...,С1,С2,...) употребляются для обозначения произвольных пропозициональных форм, тогда как обычное написание этих букв применяется лишь для пропозициональных букв.

Истинностной функцией от n аргументов называется n-аргументная функция, принимающая одно из двух значений: И либо Л, когда ее аргументы пробегают те же значения.

Составное (сложное) высказывание, образованное с помощью введенных операций, &,,, будет истинным либо ложным в зависимости от значений исходных высказываний. Следовательно, полученное составное высказывание порождает некоторую истинностную функцию.

Как определено выше, каждая пропозициональная буква может принимать значения И либо Л. Будем считать, что пропозициональные формы (А), (А&В), (АВ), (АВ) и (А ) имеют те же таблицы истинности, что и обозначаемые таким образом высказывания (см.§1). Тогда пропозициональных букв, входящих в пропозициональную форму, соответствуют согласно таблицам истинности для пропозициональных связок некоторые истинностные значения этой пропозициональной формы.

Таким образом, каждая пропозициональная форма порождает некоторую функцию, принимающую значение Л или И в зависимости от истинностных значений пропозициональных букв в нее входящих, следовательно, каждая пропозициональная форма порождает некоторую истинностную функцию.

Заметим, что пропозициональная форма не является высказыванием. По определению пропозициональная форма - это выражение, построенное из пропозициональных букв, т.е. букв А, В, С,..., А1,А2,..., В1,В2,..., С1,С2,... с помощью пропозициональных связок согласно правилам 1), 2), 3) и ничего более. В частном случае пропозициональные буквы могут обозначать высказывания, пропозициональные связки - логические операции, тогда пропозициональная форма будет обозначать некоторое высказывание.

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

Так как добавление каждой новой пропозициональной буквы увеличивает количество строк в таблице истинности вдвое, то пропозициональная форма, содержащая n различных пропозициональных букв, имеет таблицу истинности с 2n строками. Например, для формы (((А&В)С)А) имеем следующую таблицу истинности.

Л Л Л Л Л И

Л Л И Л И Л

Л И Л Л Л И

Л И И Л И Л

И Л Л Л Л И

И Л И Л И И

И И Л И И И

И И И И И И

Составление таблицы истинности можно сократить, выписывая шаг за шагом под каждой пропозициональной связкой истинностные значения той составляющей пропозициональной формы, для которой применяется эта связка. Например, для той же формы (((А&В)С)А) получаем таблицу:

Л Л Л Л ЛИ

Л Л И Л ИЛ

Л И Л Л ЛИ

Л И И Л ИЛ

И Л Л Л ЛИ

И Л И Л ИИ

И И Л И ИИ

И И И И ИИ

Следующий метод построения таблиц истинности, называют алгоритмом Квайна. В форме выбирается некоторая буква, например, та буква, которая чаще всего встречается в рассматриваемой форме. Выбранной букве (для формы D=(((А&В)С)А) это будет буква А) приписывается значение И либо Л. Далее проводят вычисления, где возможно, при выбранном значении этой буквы. Если А=И, то для формы D=(((А&В)С)А), вне зависимости от значении букв В и С, легко получить, что D=И. При А=Л и С=Л получим снова, что D=И. Наконец, если А=Л и С=И, то D=Л. В результате получим сокращенную запись таблицы истинности содержащую всего три строки (в данном случае результат не зависит от значений буквы В, а при А=И не зависит и от значений С):

§ 3. Упрощения в записях пропозициональных форм Введем некоторые соглашения о более экономном употреблении скобок в записях форм. Эти соглашения облегчат нам чтение сложных выражений.

Во-первых, будем опускать в пропозициональной форме внешнюю пару скобок. (В случае пропозициональной буквы этой внешней пары скобок нет по определению).

Во-вторых, если форма содержит вхождения только одной бинарной связки (т.е. &,, или ), то для каждого вхождения этой связки опускаются внешние скобки у той из двух форм, соединяемых этим вхождением, которая стоит слева.

Пример. АВСА пишется вместо (((АВ)С)А), а ВВА(СА) пишется вместо (((ВВ)А)(СА)).

В-третьих, договоримся считать связки упорядоченными следующим образом:, &,,, и будем опускать во всякой пропозициональной форме все те пары скобок, без которых возможно восстановление этой формы на основе следующего правила.

Каждое вхождение знака относится к наименьшей пропозициональной форме, следующей за ним; после расстановки всех скобок, относящихся ко всем вхождениям знака, каждое вхождение знака & связывает наименьшие формы, окружающие это вхождение; затем (т.е. после расстановки всех скобок, относящихся ко всем вхождениям знаков и &) каждое вхождение знака связывает наименьшие формы, окружающие это вхождение, и аналогично для и. При применении этого правила к одной и той же связке мы продвигаемся слева направо.

Пример. В форме А А&ВС D скобки восстанавливаются следующими шагами:

А((А)&В)С( D), А(( А)&В)(C( D)), А((( А)&В)(С( D))), (А((( А)&В)(С( D)))).

Однако не всякая форма может быть записана без скобок. Например, нельзя опустить оставшиеся скобки в формах: А&(ВС), А(ВC), (АВ).

§ 4. Тавтологии (общезначимые формулы). Противоречия Тавтологией (тождественно истинной пропозициональной формой или общезначимой формулой) называется пропозициональная форма, которая принимает значение И при любой совокупности истинностных значений пропозициональных букв, входящих в нее.

Таблица истинности тавтологии имеет результирующий столбец, состоящий только из И.

Примером тавтологии является пропозициональная форма (А А), в чем легко убедиться, составив таблицу истинности. Другие примеры тавтологий:

АА, (АВ) (ВА).

Противоречием (тождественно ложной пропозициональной формой) называется пропозициональная форма, принимающая значение Л при любой Казахстанский поэт.

совокупности истинностных значений пропозициональных букв, входящих в нее.

Примеры противоречий: А&А, (АА), (А А).

Истинностная таблица для противоречия, очевидно, имеет в результирующем столбце только значения Л.

Очевидно, что пропозициональная форма А является тавтологией тогда и только тогда, когда А есть противоречие.

Тавтологию будем обозначать через Т, а противоречие - через П.

Сформулируем и докажем две несложные теоремы.

Теорема 1.1. Если А и (АВ) - тавтологии, то В - тавтология.

Доказательство. Пусть А и (АВ) - тавтологии. Допустим, что при некотором распределении истинностных значений для пропозициональных букв, входящих в А и В, В принимает значение Л. Поскольку А есть тавтология, то при этом распределении истинностных значений А принимает значение И. Тогда (АВ) получит значение Л. Это противоречит предположению о том, что (АВ) есть тавтология. Теорема доказана.

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

истинностных значений для пропозициональных букв, входящих в В. Формы А1, А2,..., Аn примут тогда некоторые значения х1, х2,..., хn (каждое хi есть И или Л). Если мы придадим значения х1, х2,..., хn соответственно буквам А1, А2,..., Аn, то так как А есть тавтология, то А будет истинно, и это же значение пропозициональных букв форма В принимает значение И, что и требовалось доказать.

Ясно, что при подстановке в пропозициональную форму вместо пропозициональных букв высказываний, мы получим некоторое высказывание.

Высказывание, которое получается из какой-либо тавтологии посредством подстановки высказываний вместо пропозициональных букв, при условии, что вхождение одной и той же буквы замещается одним и тем же высказыванием, называется логически истинным высказыванием. Это высказывание истинно в силу своей формы, а не в силу своего содержания.

Например, высказывание: "Если Иванов - студент, то Иванов - студент" всегда истинно (логически истинно), в то время как высказывание: "Иванов студент", если и истинно, то в силу уже других причин.

Высказывание, которое можно получить с помощью подстановки в противоречие, называется логически ложным высказыванием. Примером логически ложного высказывания может служить высказывание: "2х2=4 и 2х24", где имеет место одновременно какое-то высказывание и отрицание этого же высказывания.

Пропозициональная форма называется выполнимой если она принимает значения И хотя бы для одной совокупности значений пропозициональных букв, в нее входящих.

Например, А&В является выполнимой пропозициональной формой, так как принимает значения И, когда А=И и В=И, а форма А&А не будет выполнимой, так как всегда ложна.

Очевидно, что пропозициональная форма А выполнима тогда и только тогда, когда А не является противоречием.

Проблема разрешимости (алгебры высказываний) состоит в следующем. Существует ли правило, позволяющее для каждой пропозициональной формы А конечным числом действий выяснить, является А выполнимой или нет.

Ясно, что выяснение выполнимости А равносильно выяснению, является ли А противоречием или нет, что, в свою очередь, равносильно выяснению, является ли А тавтологией или нет. Таким образом, если есть метод, позволяющий для произвольной формы конечным числом действий выяснить, тавтология это или нет, то можно решить вопрос выполнима или нет произвольная форма А. Для этого достаточно выяснить А - тавтология или нет. Если А - тавтология, то А - противоречие, следовательно, А невыполнимо, если же А - не тавтология, то А выполнимо.

Проблема разрешимости (алгебры высказываний) полностью решается, например, с помощью таблиц истинности. Если пропозициональная форма содержит n различных букв, то, как известно, ее таблица истинности имеет 2n строк. При больших значениях n составление таблиц истинности и выяснение выполнимости по ним является громоздкой операцией. Для решения проблемы разрешимости существуют и другие способы, основанные на приведении к так называемым нормальным формам. Эти формы и способы решения с их помощью проблемы разрешимости будут рассмотрены ниже.

§ 5. Равносильность пропозициональных форм Пропозициональные формы А и В называются равносильными, если при каждой совокупности значений всех пропозициональных букв, входящих в А и В, эти формы принимают одинаковые истинностные значения.

Например, форма АВ равносильна форме АВ, в чем легко убедиться с помощью таблиц истинности:

В этих таблицах результирующие столбцы совпадают, т.е. при одинаковых значениях букв А и В значения форм АВ и АВ равны, следовательно, эти формы равносильны. Далее, форма АА&В равносильна А. Действительно, имеем следующую таблицу:

Также, очевидно, А А равносильно В В.

При определении равносильности двух форм не обязательно предполагать, что они содержат одни и те же пропозициональные буквы. Так, в последних примерах имеем случаи, когда в равносильные формы входят разные буквы. При этом, если какая-нибудь пропозициональная буква входит только в одну из двух равносильных форм, то эта форма при всех значениях этой буквы принимает одно и то же значение, если значения других фиксированы. Следовательно, хотя эта буква и входит в форму, но истинностная функция, определенная формой, от этой буквы не зависит.

Высказывание "А равносильно В" будем обозначать следующим образом: А ~ B.

Здесь и далее, цитаты из произведений Л. Кэрролла приводятся по переводу с английского, выполненного Н. Димуровой, в котором приведены стихи в переводах С. Маршака, Д. Орловской и О. Седаковой.

Пусть А, В, C - произвольные пропозициональные формы. Отношение равносильности пропозициональных форм, как легко видеть, обладает следующими свойствами:

1) А ~ А - рефлексивность;

2) если А ~ В, то В ~ А - симметричность;

3) если А ~ В и В ~ C, то А ~ C - транзитивность.

Следовательно, отношение равносильности является отношением эквивалентности и порождает разбиение множества пропозициональных форм на непересекающиеся классы. В каждый класс попадают равносильные между собой пропозициональные формы. Докажем теорему.

Теорема 1.3. Пропозициональные формы А и В равносильны тогда и только тогда, когда АВ является тавтологией.

Доказательство. Необходимость. Пусть А и В равносильны, следовательно, они при каждой совокупности значений всех пропозициональных букв, входящих в них, принимают одинаковые истинностные значения, тогда по определению связки форма АВ всегда принимает значение И, т.е. является тавтологией.

Достаточность. Пусть АВ тавтология, т.е. принимает всегда значение И. Это означает, что А и В имеют всегда одинаковые истинностные значения, т.е. они равносильны. Теорема доказана.

§ 6. Важнейшие пары равносильных пропозициональных форм Пусть А, В, С - пропозициональные буквы, Т- тавтология и П противоречие. Используя таблицу истинности, легко показать, что 1) ( А) равносильно А.

Если под А понимать обозначение некоторого высказывания, то получаем, что двойное отрицание высказывания А означает то же, что и высказывание А. Полученное соотношение между ( А) и А называют законом двойного отрицания.

Аналогичным образом можно показать, что имеют место следующие законы.

6) А&(ВС) ~ А&ВА&С - первый закон дистрибутивности;

7) АВ&С ~ (АВ)&(АС) - второй закон дистрибутивности;

10) А&А ~ А, законы идемпотентности;

12) А А ~ Т - закон исключенного третьего;

13) А& А ~ П - закон противоречия;

20) АВ ~ В А - закон контропозиции.

Как уже замечено выше, соотношения 1) - 20) доказываются с помощью таблиц истинности.

Можно показать, что соотношения 1) - 20) будут иметь место и тогда, когда вместо пропозициональных букв А, В и С будут подставлены произвольные пропозициональные формы. Соотношения 1) - 20) позволяют находить для заданных пропозициональных форм равносильные упрощенные формы или равносильные формы, имеющие более удобный с некоторых позиций вид. Из этих же соотношений видно, что над пропозициональными формами можно производить преобразования: раскрытие скобок, заключение в скобки, вынесение за скобки общего множителя.

Из соотношений 2) - 6) видно, что операция & напоминает умножение (обладает некоторыми свойствами умножения), а - сложение, поэтому часто конъюнкцию двух высказываний называют (логическим) произведением их, а дизъюнкцию - (логической) суммой.

§ 7. Зависимости между пропозициональными связками Связки, &,, =>, не являются независимыми друг от друга в том смысле, что одни из них можно выражать через другие так, что при этом получаются равносильные пропозициональные формы.

Например, связка может быть выражена через связки и & на основании соотношения Для доказательства (1.1) достаточно составить таблицы истинности и убедиться, что результирующие столбцы этих таблиц совпадают.

Для импликации имеем:

Таким образом, связку можно выразить через, & и :

Так как А равносильно ( А), то А&В равносильно ( А)& ( В), а последнее согласно закону де Моргана равносильно ( А В), следовательно, Из (1.4) видно, что & можно выразить через и. Покажем, что можно выразить через и &. Действительно, так как А равносильно ( А), то АВ равносильно ( А)( В), последнее по закону де Моргана равносильно ( А& В). Итак, Из соотношения (1.2) заменой А на А получаем, что Т.е. можно выразить через и.

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

Теорема 1.4. Для каждой пропозициональной формы А существует равносильная ей форма, содержащая только связки, &,, причем связка относится только к пропозициональным буквам.

Доказательство. Связки и можно исключить согласно соотношениям (1.2) и (1.3). При этом останутся только связки, &,. Если пропозициональная связка стоит перед некоторой скобкой, например, (А&ВС В), то на основании законов де Моргана можно внести под скобки, при этом связка & меняется на, а на &, а связки и нигде не появляются. Внеся под скобки, перед которыми они стоят, добьемся, чтобы относилась только к пропозициональным буквам. Теорема доказана.

Теорема 1.5. Для каждой пропозициональной формы А существует равносильная ей форма, содержащая либо только связки, &, либо только,, либо только,.

Доказательство. Покажем, что можно оставить только связки и &.

Связки и можно исключить (если они есть) на основании соотношений (1.2) и (1.3), а затем по (1.5) исключим. В результате останутся только и &. Остальные случаи доказываются аналогичным образом на основании соотношений (1.1) - (1.6).

Будем рассматривать пропозициональные формы, содержащие только связки, &,. Как уже установлено выше, всякая пропозициональная форма может быть приведена преобразованиями равносильности к такому виду.

Будем говорить, что связка & двойственна связке, и наоборот.

Пропозициональные формы А и А* называются двойственными, если одна получается из другой заменой каждой связки & и на двойственную.

Например, если А =(А В)&С, то А* =(А & В)С.

Отношение двойственности взаимно: если А двойственно А*, то А* двойственно А. Следующую теорему считают законом двойственности.

Теорема 1.6. Если пропозициональные формы А и В равносильны, то и двойственные им формы А* и В* также равносильны.

Доказательство. Пусть А и В равносильны, а А1,А2,...,Аn - буквы, входящие в А или В. Будем считать, что А1,А2,...,Аn входят и в А, и в В. Если бы это было не так, например, В не содержала бы Аk(1kn), входящего в А, то В можно заменить равносильной формой ВАk& Аk, содержащей эту букву. Таким образом, всегда можем добиться, чтобы А и B содержали все буквы А1,А2,...,Аn.

А(А1,А2,...,Аn) ~ В(А1,А2,...,Аn).

Если формы А и В равносильны, то, очевидно, равносильны и их отрицания, поэтому из (1.7) получим, что А(А1,А2,...,Аn ) ~ В(А1,А2,...,Аn).

В пропозициональных формах соотношения (1.8) добьемся, чтобы относилась только к буквам. При этом согласно законам де Моргана связки & и поменяются на двойственные. Следовательно, получим А* ( А1, А2,..., An) ~ B* ( А1, А2,..., An ) А*( А1, А2,..., An) и B*( А1, А2,..., An) означает, что они принимают одинаковые значения при любых совокупностях значений букв А1,А2,...,An.

Поэтому, если вместо букв А1,А2,...,An подставить А1, А2,..., An, то формы останутся равносильными. Учитывая, что А равносильно А, из (1.9) получим А*( А1,А2,...,Аn ) ~ B*(А1,А2,...,Аn), что и требовалось доказать.

Известно, что в математическом анализе среди всевозможных функций выделяют элементарные (основные) функции: степенные, показательные, тригонометрические и т.п. Среди пропозициональных форм, выделим некоторые как элементарные, а далее из них можно получать более сложные.

Элементарной суммой (элементарным произведением) называют дизъюнкцию (конъюнкцию) пропозициональных букв либо их отрицаний.

Одну букву тоже будем рассматривать как элементарную сумму или как элементарное произведение. Элементарную сумму часто называют дизъюнктом, а слагаемые этой суммы называются литералами (литерами).

Примеры элементарных сумм: А, АВ, АВАС.

Примеры элементарных произведений: А, А&В, А&С&А&В.

Теорема 1.7. Чтобы элементарная сумма была тавтологией (общезначимой формулой), необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из которых одно есть некоторая буква, а другое - отрицание этой буквы.

Доказательство. Достаточность. Пусть такая пара букв существует, т.е.

сумма имеет вид АА.... Для нас важно, что имеются слагаемые А и А, остальные слагаемые могут быть, но могут и отсутствовать. Форма А и А всегда принимает значение И, поэтому и вся элементарная сумма будет И при любых значениях букв, в нее входящих. Следовательно, наша элементарная сумма - тавтология.

Необходимость. Пусть данная элементарная сумма - тавтология.

Допустим, что такой пары слагаемых нет. В таком случае каждой букве, стоящей без знака отрицания, можно дать значение Л, а буквам, стоящим со знаком отрицания, - значение И. Это возможно осуществить, ибо одна и та же буква не входит одновременно без отрицания и с отрицанием. После указанной подстановки каждое слагаемое примет значение Л, следовательно, и вся элементарная сумма примет значение Л и, значит, элементарная сумма не является тавтологией, что противоречит условию. Полученное противоречие и доказывает необходимость.

Также легко доказать следующую теорему.

Теорема 1.8. Для того, чтобы элементарное произведение А было противоречием, необходимо и достаточно, чтобы в нем содержалась хотя бы одна пара множителей, из которых один множитель является отрицанием другого.

Дизъюнктивной нормальной формой (д.н.ф.) называется дизъюнкция элементарных произведений. Одно элементарное произведение тоже будем считать д.н.ф. Примеры д.н.ф.: АВ,АВ&С, АА&СА&В&С.

Теорема 1.9. Для каждой пропозициональной формы существует равносильная ей д.н.ф. (не единственная).

Доказательство. Ранее было показано, что для любой формы существует равносильная ей форма, содержащая только связки, &,, причем связка относится только к отдельным буквам. Еще раньше было замечено, что с формой, содержащей связки &,, можно проводить операции раскрытия скобок (см. законы дистрибутивности). В результате получаем дизъюнкцию элементарных произведений, т.е. д.н.ф.

Пример. Пусть задана формула (АВ)&С. Исключим связку, затем :

((АВ)&(ВА))&С, ((АВ)&( ВА))&С.

Теперь добьемся, чтобы относилась только к пропозициональным буквам:

(А& ВВ&А)&С.

Раскрыв скобки, получим А& В&СВ&А&С. Последнее и есть д.н.ф.

Полученная д.н.ф., очевидно, равносильна следующей д.н.ф.: А& В&С А&В&СА&А. Из примера видно, что д.н.ф., равносильная заданной форме, определяется не единственным образом.

Теорема 1.10. Для того, чтобы форма А была противоречием, необходимо и достаточно, чтобы равносильная ей д.н.ф. содержала в каждом слагаемом хотя бы одну пару множителей, из которых один - некоторая пропозициональная буква, а второй - отрицание этой буквы.

Доказательство. Пусть для А равносильной ей д.н.ф. является форма где Вi ( 1ik ) есть элементарное произведение. Дизъюнкция (1.10) будет противоречием тогда и только тогда, когда будет противоречием каждая Вi (1ik). Вi - элементарное произведение и по теореме 1.8 будет противоречием тогда и только тогда, когда содержит хотя бы одну пару множителей, из которых один - некоторая буква, а второй - отрицание этой буквы. Теорема доказана.

Следствие 1.1. Форма А будет выполнимой, если равносильная ей д.н.ф.

содержит хотя бы одно слагаемое, в котором нет таких множителей, что один из них - некоторая пропозициональная буква, а другой множитель отрицание этой буквы.

Пропозициональная форма называется конъюнктивной нормальной формой (к.н.ф.), если она представляет собой конъюнкцию элементарных сумм. Легко доказать следующую теорему.

Теорема 1.11. Для каждой пропозициональной формы существует равносильная ей к.н.ф. (не единственная).

Можно сформулировать правила для нахождения д.н.ф. и к.н.ф., равносильных заданной форме. Пусть задана форма А:

1) исключить из А все связки, кроме, &,, 2) добиться, чтобы относилась только к пропозициональным буквам, 3) если раскрыть скобки по первому дистрибутивному закону, то получится д.н.ф., 4) если сгруппировать в скобки, пользуясь вторым дистрибутивным законом, то получится к.н.ф.

Легко доказать следующую теорему.

Теорема 1.12. Для того, чтобы пропозициональная форма А была тавтологией, необходимо и достаточно, чтобы равносильная ей к.н.ф.

содержала в каждом множителе хотя бы одну букву вместе с отрицанием этой же буквы.

Приведенная теорема позволяет очень просто выяснить является ли форма тавтологией или нет. Для этого достаточно построить к.н.ф.

Также просто по теореме 1.12 выяснить выполнима форма А или нет.

Для этого находим к.н.ф. для А и если найденная к.н.ф. тавтология, то А не выполнима, если же найденная к.н.ф. не тавтология, то форма А выполнима.

Совершенной дизъюнктивной нормальной формой (с.д.н.ф.) пропозициональной формы А(A1,A2,…,An) называется д.н.ф. этой формы удовлетворяющая следующим условиям:

-нет одинаковых слагаемых;

-в каждое слагаемое входят все буквы A1,A2,…,An один и только один раз (и только они) с отрицанием либо без отрицания.

С.д.н.ф. для А можно построить по таблице истинности этой формы.

Для этого выбираем строки, где А равна И; пусть это будут строки k1,k2,…,km.

Для каждой выбранной строки ki, 1 i m, строим элементарное произведение (конституенту единицы) Ki следующим образом. Если в выбранной строке ki буква Aj принимает значение И, то в Ki она входит без отрицания, если же Aj=Л, то в Ki она входит с отрицанием. Дизъюнкция построенных произведений и будет с.д.н.ф. и можно доказать, что эта с.д.н.ф. равносильна А В С А(А,В,С) Пусть форма А(A,B,C) ложна тогда и только тогда, А& В&СА& В&СА&В&СА& В&СА&В&С.

Второй метод нахождения с.д.н.ф. – метод равносильных преобразований, который состоит в следующем. Для заданной формы А находим д.н.ф. (которая всегда существует) и пусть д.н.ф. равна:

D1D2…Dm (m1), где Di(1 im) – элементарное произведение. Построенная д.н.ф. может удовлетворять требуемым условиям, тогда это с.д.н.ф.

Если в некоторое Di входит некоторая буква вместе с ее отрицанием, то Di – противоречие и из д.н.ф. Di можно исключить. Если при такой процедуре нужно отбросить все слагаемые из д.н.ф., то А – противоречие и с.д.н.ф. не существует.

Если в некоторое Di не входит одна из букв Аj формы А, то заменяем Di на равносильную:

(Di& Аj)( Di&Аj).

Таким образом, добиваемся, чтобы каждое слагаемое содержало все аргументы формы А.

Если в полученной форме окажутся одинаковые слагаемые, то оставляем только одно из них. В результате получим с.д.н.ф Совершенной конъюнктивной нормальной формой (с.к.н.ф.) пропозициональной формы А(A1,A2,…,An) называется к.н.ф. этой формы удовлетворяющая следующим условиям:

-нет одинаковых множителей;

-в каждый множитель входят все буквы из пропозициональной формы А один и только один раз (и только они) с отрицанием, либо без отрицания.

С.к.н.ф. для пропозициональной формы А можно построить по таблице истинности этой формы. Для этого выбираем строки, где А=Л. Для каждой строки, где А=Л строим элементарную сумму (конституенту нуля) K следующим образом. Если в выбранной строке буква Аj принимает значение И, то в K0 она входит с отрицанием, если Аj=Л, то Аj входит в K0 без отрицания. Конъюнкция построенных конституент нуля и будет с.к.н.ф.

Рассмотрим пример на построение с.к.н.ф. для пропозициональной формы, рассмотренной выше. Решение. Таблица истинности уже построена.

Выберем строки, где А принимает значение Л, т. е. строки с номерами: 4, 6 и 7. Для четвертой строки элементарная сумма (конституента нуля) представляется в виде А ВС; для шестой в виде: АВ С, а для седьмой - А ВС. В результате получим с.к.н.ф.:

Второй метод построения с.к.н.ф. – метод равносильных преобразований – заключается в следующем.

Для заданной формы А находим к.н.ф., которая имеет вид К1&K2&…&Km, затем добиваемся выполнения указанных выше условий.

Если в некоторое Ki входит некоторая буква вместе с ее отрицанием, то Ki – тавтология и из к.н.ф. множитель Ki можно исключить. Если при такой процедуре нужно отбросить все множители из к.н.ф., то А – тавтология и с.к.н.ф. не существует.

Если некоторый множитель к.н.ф., например Ki, не содержит букву А, то вводим ее согласно равносильности Таким образом, добиваемся, чтобы каждый множитель к.н.ф. содержал все аргументы исходной формулы А.

Если в некотором множителе окажутся одинаковые слагаемые, то оставляем только одно из них. Если в полученной форме окажутся одинаковые множители, то оставляем только один из них. В результате получим с.к.н.ф.

§ 10. Булева (переключательная) функция Булевой переменной назовем переменную, которая принимает одно из двух возможных значений. Ясно, что высказывание можно рассматривать как частный случай булевой переменной, ибо высказывание принимает только одно из двух значений: Л или И.

Функция (А1,А2,...,An) называется булевой (переключательной) функцией, если она может принимать одно из двух возможных значений, когда ее аргументы принимают тоже одно из этих двух значений.

Очевидно, что истинностная функция является частным случаем булевой функции.

Значения булевой функции и булевых переменных можно обозначать любыми символами, например, + и -, либо 1 и 0. В дальнейшем значения булевых переменных и функций будем обозначать через 1 и 0.

При исследовании высказываний, истинностных функций и пропозициональных форм нигде не использовалась природа значений "истина" (И) и "ложь" (Л). Тогда всюду И и Л можно рассматривать как символы, служащие для различения двух значений. Поэтому И можно переобозначить через 1, а Л - через 0, и все результаты, полученные для истинностных функций, будут справедливы для булевых функций. Более того, булевы функции можно отождествить с истинностными функциями.

Выражения (А), (А&В), (АВ), (АВ), (АВ) можно рассматривать как булевы функции, значения которых определяются по таблицам построенным для пропозициональных форм (А), (А&В), (АВ), (АВ), (АВ) соответственно, если в них всюду заменить И на 1, а Л на 0. Эти таблицы будем тоже называть таблицами истинности.

Очевидно, что пропозициональную форму можно рассматривать как булеву функцию, значения которой определяются по таблицам истинности.

Можно показать, что число различных булевых функций от n переменных равно N= 2 2. Например: для n=1 N=4, для n=2 N=16, для n= N=256, для n=5 N - более четырех миллиардов.

Булеву функцию можно задать с помощью таблиц, аналитически, графически и т.п.

§ 11. Приложение алгебры высказываний к анализу и синтезу Алгебра высказываний находит весьма широкое практическое применение. Рассмотрим приложение алгебры высказываний к анализу и синтезу контактных (переключательных) схем.

Контакты (переключатели) можно рассматривать как переменные и обозначать буквами А, В, С,... или теми же буквами с числовыми индексами:

А1,А2,...,В1,В2,...,С1,С2,.... Каждая из переменных может принимать одно и только одно из двух возможных значений: если контакт А разомкнут, то по определению А=0, если контакт А замкнут, то по определению А=1.

Под контактной (переключательной) схемой понимается схема, состоящая из замкнутых и разомкнутых контактов, соединенных параллельно, или последовательно, или смешанным образом.

Отрицанием контакта А называется контакт, равный 1, если А=0, и равный 0, если А=1. Отрицание контакта А обозначается через А.

Очевидно, что последовательное соединение двух контактов А и В моделируется конъюнкцией переменных А и В, а параллельное соединение их дизъюнкцией, см. Рис. 1.1.

Известно, что любую булеву функцию можно представить, используя только, &,, причем относится только к буквам. Следовательно, любую булеву функцию можно представить в виде контактной схемы.

Используя булевы функции, можно строить контактные схемы, удовлетворяющие заданным требованиям (производить синтез контактных схем), а также преобразовывать, упрощать схемы (производить анализ контактных схем). Покажем это на примере.

Требуется построить контактную схему для голосования комитета из трех человек. При голосовании "за" - нажатием кнопки свет должен загораться тогда и только тогда, когда "за" проголосовало большинство.

Решение. В нашем случае имеем три переменные. Обозначим их через А, В, и С. По условию свет должен загораться тогда и только тогда, когда большинство этих переменных принимает значение 1, т.е. имеем таблицу:

Эта схема выполняет естественно попытаться проанализировать данную например, уменьшить количество контактов в переключательной схеме.

форма (1.11) равносильна форме А&ВА&СВ&С, которую преобразуем к виду: А&ВС&(АВ). Тогда схема будет содержащей всего пять контактов, см. Рис. 1.3.

Очевидно, что анализ позволил сильно упростить контактную схему.

§ 12. Приложение алгебры высказываний к анализу и синтезу схем из Огромные скорости работы современных ЭВМ достигнуты за счет применения бесконтактных схем, работающих значительно быстрее, чем контактные схемы. В ЭВМ применяются электронные приборы, реализующие основные логические операции (отрицание, конъюнкцию, дизъюнкцию и др.).

Не касаясь структуры и физических основ этих устройств, называемых функциональными элементами, обозначим их условно следующим образом:

устройство, реализующее отрицание;

устройство, реализующее конъюнкцию;

1 устройство, реализующее дизъюнкцию.

Ограничимся только этими устройствами, хотя на практике существуют функциональные элементы, реализующие и другие операции, например, отрицание конъюнкции и т. п. Но можно обойтись только перечисленными тремя устройствами, так как любую булеву функцию можно выразить, используя только, &,.

Об этих устройствах (функциональных элементах) мы знаем лишь следующее:

устройство, реализующее отрицание имеет один Этих свойств элементов достаточно для решения задач синтеза и анализа схем из этих элементов.

Рассмотрим пример построения одноразрядного сумматора двоичных чисел. Заданы двоичные числа а1а2…аk…аn и b1b2…bk…bn. Требуется построить сумматор для k –го разряда. Задача состоит в конструировании схемы (Рис. 1.4) с тремя входами А, В, С и двумя выходами S и Р, чтобы при двоичной системе, получим таблицу:

Считая, что 0 и 1 есть значения булевой функции, и выбирая строки, оканчивающиеся на 1, получим:

S=А&В&СА& В&СА&В&СА& В&С, Р=А&В&СА&В&СA& В&СА&В&С Имея выражение (1.12), уже можно построить схему из функциональных элементов, выполняющих поставленную задачу. Но поскольку схема построена из функциональных элементов, выполняющих некоторые операции, то возникает задача такого упрощения, чтобы она содержала как можно меньше знаков операций. Можно показать, что Тогда получим схему (Рис. 1.5), которая выполняет поставленную задачу, причем схема содержит значительно меньше функциональных элементов по сравнению со схемой, которая получилась при ее построении по (1.12) без проведения преобразований.

1. Высказывание, логические операции,&,,,; их определения и таблицы истинности.

2. Пропозициональные формы или формулы логики высказываний, определение, примеры. Упрощение записей пропозициональных форм.

3. Методы составления таблиц истинности.

4. Тавтологии (общезначимые формулы), противоречия. Две теоремы о тавтологиях.

5. Равносильность пропозициональных форм (формул логики высказываний), свойства отношения равносильности.

6. Важнейшие пары равносильных пропозициональных форм (запишите).

7. Зависимости между пропозициональными связками. Две теоремы о выражении пропозициональных форм с помощью форм, содержащих связки 3-х видов, 2-х видов.

8. Закон двойственности.

9. Выполнимые пропозициональные формы. Как можно выяснить выполнимость пропозициональной формы?

10. Элементарные суммы и произведения, их свойства.

11. Нормальные формы (д.н.ф. и к.н.ф.). Алгоритмы нахождения к.н.ф.;

единственна ли к.н.ф. для заданной формы?

12. Выяснение общезначимости пропозициональной формы по к.н.ф.

13. Совершенная конъюнктивная нормальная форма (с.к.н.ф.). Алгоритмы нахождения с.к.н.ф.

14. Для каждой ли пропозициональной формы существует равносильная ей с.к.н.ф.? Единственна ли с.к.н.ф. для заданной формы?

15. Булева (переключательная) функция, определение, сколько существует различных булевых функций от n переменных?

16. Можно ли любую булеву функцию представить в виде переключательной схемы?

17. Можно ли любую переключательную схему представить в виде булевой функции, содержащей только связки,&,?

18. Можно ли любую булеву функцию представить в виде схемы из функциональных элементов?

Логические операции. Символизация языка. Таблицы истинности 1. Какие из следующих предложений являются высказываниями?

в) город Париж находится в Азии;

ж) числа вида 2p–1, где p – простое число, назовем числами Мерсенна;

з) остаток от деления на 7 числа 3, возведенного в степень 123 и) является ли число 12345678998765432111111111111 простым?

2. Следующие предложения являются составными высказываниями.

Найдите их простые компоненты, т. е. такие высказывания, которые уже не построены из каких-либо других высказываний:

а) 7 – простое число и не делится на 5;

б) число 211213 – 1 простое и его запись содержит более 3376 цифр;

в) города Самара и Казань расположены на берегу Волги;

г) слово «алгоритм», которое иногда пишут «алгорифм», происходит от имени арабского математика аль-Хорезми (полное имя которого: АльХорезми Абу Абдала Мохаммед бен Муса аль-Маджуси), который в IX столетии внес значительный вклад в распространение существовавших тогда методов вычислений;

д) число вида аbа bаb делится на 7, так как такое число является произведением чисел аb и 10101, а сомножитель 10101 кратен 7.

3. Пусть А и В обозначают соответственно «Андрей студент» и «Борис студент». Запишите приведенные ниже высказывания в символической форме, т. е. используя только обозначения для высказываний (А,В), символы,&,,, и скобки:

а) Андрей студент и Борис не студент;

б) Борис студент, а Андрей не студент;

в) Андрей и Борис оба не студенты;

г) Андрей или Борис студент;

д) либо Андрей студент, либо Борис студент;

е) ни Андрей, ни Борис не студенты;

ж) Андрей не студент и Борис не студент;

з) неверно, что Андрей и Борис оба студенты;

к) Андрей студент тогда и только тогда, когда Борис студент.

4. Пуcть С обозначает «Снег белый», а D обозначает «Дважды два четыре». Сформулируйте словесно каждое из следующих высказываний:

5. Составьте таблицы истинности для высказываний:

6. Запишите следующие высказывания в символической форме употребляя заглавные латинские буквы для обозначения атомарных высказываний, т. е. таких высказываний, которые уже не построены из каких-либо других высказываний:

а) для того, чтобы число а было нечетным, достаточно, чтобы а было простым;

б) если а простое число, то а2 – нечетное;

в) необходимым условием делимости числа на 4 является делимость г) если а положительно, то а2положительно;

д) Игорь или школьник, или студент, но он не студент, значит, он школьник;

е) (п-1)!+1 не делится на п, если п – не простое число;

ж) необходимым и достаточным условием делимости числа а на является делимость его на 2 и 3;

з) для того, чтобы число а делилось на 6, достаточно чтобы а делилось и) Фиорелло ходит в кино только в том случае, когда там показывают комедию.

7. Пусть А, В обозначают некоторые высказывания. Запишите следующие высказывания в символической форме:

а) А достаточно для В;

б) В необходимо для А;

г) В только тогда, когда А;

е) А лишь тогда, когда В;

ж) А тогда и только тогда, когда В;

и) А необходимо и достаточно для В;

л) А необходимое следствие из В;

м) А при условии, что В;

о) в случае А имеет место В;

т) если А, то В, и обратно.

8. Составьте списки выражений, которые могут быть заменены символами: а)А; б) А&В; в) АВ; г) АВ; д) АВ.

Пропозициональные связки и формы (формулы логики высказываний) 9. Являются ли следующие выражения пропозициональными формами?

10. а). Пусть значение пропозициональной формы (АВ) есть И. Что можно сказать о значениях пропозициональных форм (А( В)) и ((А)В)?

б). Пусть значение пропозициональной формы (АВ) есть Л. Что можно сказать о значениях (А( В)) и ((А)В)?

11. Найти значения А, В, С, если:

в) (((А(АВ)))С)=Л; г) (А(А&В))=Л;

пропозициональных форм:

б) ((А(ВС))((АВ)(АС)));

в) ((( В)(А))((( В)А)В));

е) ((АВ)(( В)(А)));

ж) ((АВ)((С)&В));

з) ((АВ)((А)( В))).

Укажите, какие из этих пропозициональных форм являются тавтологиями и какие противоречиями.

14. Доказать, что если А – тавтология, то тавтологиями являются (АВ) и (ВА), где В – произвольная пропозициональная форма.

15. Для данных пропозициональных форм составить таблицы истинности. Определить, для которых из них истинностные значения всей формы можно записать без промежуточных выкладок (используйте результаты задачи 14):

ж) (((С&D)(А&В))(В(В))); з) ((А(В(А)))&(С(А(С))));

и) ((ВВ)&(СС)&(А(А))); к) (((А&В)&(А&А))((А&В))).

16. Составить таблицу истинности для истинностной функции, зависящей от трех переменных, если известно, что функция истинна тогда и только тогда, когда а) все переменные принимают одинаковые значения;

б) истинны значения большинства переменных этой функции;

в) истинно значение одного и только одного из ее переменных;

г) каждая переменная принимает значение, отличное от значения соседней переменной.

Упрощение в записях пропозициональных форм.

17. 1). Записать в сокращенном виде, т. е. по возможности опустив скобки:

а) (((А)(В(С)))((В&А)( В)));

б) (((А( В))С)((А)&В));

г) ((((А)В)&(В(С)))А);

д) ((((А(А))( В))С)&(АВ));

пропозициональных форм восстановить опущенные скобки:

Равносильные пропозициональные формы 18. Найти простейшие (содержащие минимально возможное число вхождений пропозициональных букв) равносильные пропозициональные формы для заданных пропозициональных форм:

ж) А&А&ВВА&ВВА&А&С; з) (А(В&С))(А&( ВС));

19. Законы Де Моргана для п переменных можно записать в виде Для п=2 эти равносильности доказаны (например, с помощью таблицы истинности). Доказать их для любого п индукцией по числу переменных.

20. Доказать, что АВ&С&D равносильно (АВ)&(АС)&(АD).

Связь между логическими операциями 23. Запишите А(ВС) без связки. Запишите ответ так, чтобы связка не стояла перед скобками.

24. Запишите (ВС)А без связки. Запишите результат в форме, не содержащей перед скобками.

25. Запишите каждую из следующих пропозициональных форм без пропозициональной связки, а окончательный результат без пропозициональной связки, стоящей перед скобками:

26. Выразите А(ВС) без,, внутренних скобок и отрицаний, стоящих перед скобками.

27. Для пропозициональной формы АВС найдите равносильную ей форму, содержащую только связку.

28. Для пропозициональной формы АВС найдите шесть равносильных ей форм, содержащих только связки,.

29. Для пропозициональной формы (АВ)С найти равносильную, содержащую: а) только связки, ; б) только связки,&; в) только связки 30. Для пропозициональной формы АВС найти равносильную, содержащую: а) только связки, ; б) только связки,&.

31. Найти простейшие равносильные пропозициональные формы для заданных пропозициональных форм:

32. Для пропозициональной формы АВ&С найти равносильную, содержащую а) только связки, &; б) только связки, ; в) только связки, 33. Упростить, насколько это возможно:

34. Доказать, что связки недостаточно для выражения любой истинностной функции.

35. Доказать, что каждая из пар связок (, ), (&, ) не является достаточной для выражения любой истинностной функции.

36. Показать, что для выражения любой истинностной функции недостаточно 37. Следующие пропозициональные формы привести к д.н.ф. и к.н.ф.

б) ((АВ)&(СD))&((А&С)(В&D));

38. Для заданных пропозициональных форм:

1) найдите д.н.ф., к.н.ф.; 2) выясните, является ли выполнимой или тавтологией; 3)найдите с.д.н.ф и с.к.н.ф.:

39. Сколько существует различных способов возможного заполнения последнего столбца таблицы истинности для истинностной функции от п аргументов? Сколько существует различных истинностных (булевых) функций от п аргументов?

Приложение алгебры высказываний. Контактные схемы 40. Записать пропозициональную форму, соответствующую схеме Рис. 1.6.

41. Построить контактные схемы для пропозициональных форм:

42. Комитет состоит из пяти членов. Решения выносятся большинством голосов; однако, если председатель против, решение не может быть принято. Построить схему, чтобы при голосовании «за» - нажатием кнопки – свет загорался только в том случае, если решение принято.

43. Требуется, чтобы в большом зале можно было включать и выключать свет при помощи любого из четырех переключателей, расположенных на четырех стенках. Построить схему. (Это осуществимо путем конструирования схемы, в которой свет включается, когда замкнуто четное число выключателей, и выключается, когда замкнуто нечетное число переключателей. Почему?) 44. В большом, совершенно темном зале стоит круглый стол, вокруг которого стоит 8 стульев. Около каждого стула имеется переключатель. В комнату сходят 4 мальчика и 4 девочки и садятся за стол. Каждая девочка замыкает свой переключатель, а каждый мальчик размыкает свой. Начертите схему, которая замыкается тогда и только тогда, когда мальчики и девочки сядут через одного.

Схемы из функциональных элементов 45. С помощью функциональных элементов составить схему с тремя входами и одним выходом так, чтобы на выходе появился сигнал тогда и только тогда, когда по крайней мере на двух входах поступают сигналы.

46. С помощью функциональных элементов построить схему с тремя входами А, В, С и двумя выходами S,P, такую, что на выходе S сигнал появляется тогда и только тогда, когда по крайней мере на одном из входов есть сигнал, а на выходе P сигнал появляется тогда и только тогда, когда на всех входах имеется сигнал.

47. С помощью функциональных элементов составить схему с двумя входами и двумя выходами так, чтобы на одном выходе появлялся сигнал тогда и только тогда, когда хотя бы на одном из входов поступает сигнал, а на другом выходе – когда только на одном из входов поступает сигнал.

Логика предикатов представляет собой развитие логики высказываний.

Она содержит в себе всю логику высказываний, т.е. элементарные высказывания, рассматриваемые как величины, которые принимают значения И либо Л. Но помимо этого, язык логики предикатов вводит в рассмотрение утверждения, отнесенные к предметам, т.е. производится более детальный анализ предложений. Рассмотрение логики предикатов вызвано тем, что логика высказываний не позволяет моделировать рассуждения всех видов, в частности рассуждении с использованием понятии «каждый», «некоторый». Отметим, что логика предикатов тоже не охватывает всевозможных случаев рассуждений, например, когда нужно исследовать рассуждения, истинность которых зависит от времени или вводятся понятия «должно быть» и «может быть» и т.п.; подробнее см. главу 5.

Пусть M- некоторое множество предметов, а1,а2,...- какие-то определенные предметы (элементы) из этого множества. Тогда через А(а1) будем обозначать некоторое высказывание о предмете а1, а через А(а2 ) - то же высказывание о предмете а2. Например, если M есть множество всех натуральных чисел и а1=3, а2=8, то А(а1) может обозначать высказывание "3простое число", тогда А(а2) будет обозначать "8-простое число".

Как и в логике высказываний, будем рассматривать эти высказывания только с той точки зрения, что они представляют либо истину, либо ложь, обозначаемые соответственно И и Л. При этом значения высказывания А(а1) и А(а2) могут быть разными или нет в зависимости от выбранных предметов а1 и а2. Следовательно, в отличие от алгебры высказываний будем считать, что значения И и Л ставятся в соответствие определенным предметам или группам предметов.

Если же не будем фиксировать предмет, например, рассмотрим А(х), где х - любой предмет из M, то получим некоторое предложение, которое становится высказыванием, когда х замещено определенным предметом из M. Например, если M является множеством всех натуральных чисел, то А(х) может обозначать "х - простое число". Это предложение становится высказыванием, если х заменить числом, например, "3 -простое число", "4простое число". При этом получаем высказывания, которые истинны, либо ложны. Следовательно, А(х) порождает функцию, область определения которой есть множество M, а область значений – множество {И,Л}. Отметим (еще раз), что А(х) становится высказыванием при замене х фиксированным (определенным) предметом из M.

Предложения, в которых имеются две и более переменных, будем обозначать, например, А(х,у), В(х,у,z) и т. п. При этом х, у, z пробегают все множество M, а А(х,у), В(х,у,z) при фиксированных х, у, z становятся высказываниями, следовательно, принимают значение И либо Л. Например, пусть M есть множество всех действительных чисел Рассмотрим предложение: "х делится нацело на у". Если вместо х и у подставить конкретные числа из M, получится высказывание истинное либо ложное, так, при х=6, у=3 высказывание "6 делится нацело на 3" - истинное, а при х=5, у=7 высказывание "5 делится нацело на 7" - ложно. Рассмотренное предложение "х делится нацело на у" можно обозначить, например, через С(х,у). Такого типа предложения, порождающие функции одного или нескольких переменных, будем считать предикатами.

Точнее: предикатом называется повествовательное предложение об элементах некоторого заданного множества M, которое (предложение) становится высказыванием, если все переменные в нем заменить фиксированными элементами из M; высказывание тоже будем считать предикатом - нульместным предикатом. Часто вместо "предикат от n переменных " говорят "n-местный предикат".

Упражнение. Пусть на множестве M, состоящем из m элементов, задан 3-х местный предикат А(х,у,z). Сколько высказываний об элементах M можно получить, фиксируя переменные предиката А(х,у,z)?

Введем операции над предикатами. Пусть А(х), В(х) - заданные на M предикаты. Будем считать, что А(х) тоже определяет предикат на M, причем при каждом фиксированном х=b значение высказывания А(b) противоположно значению высказывания А(b). Так же будем образовывать из предикатов А(х), В(х) новые предикаты с помощью операций &,,,.

Так, например, А(х)&В(х) обозначает предикат, который при фиксированном х=b превращается в сложное высказывание А(b)&В(b), образованное из высказываний А(b) и В(b) соединением их связкой &. Точно так же будем образовывать новые предикаты из произвольных многоместных предикатов.

Например, А(х,у)С(х,у,z) обозначает предикат, который при фиксированных переменных: х=а, у= b, z=с (а,b,с M) превращается в высказывание А(а,b)С(а,b,с), образованное из двух высказываний А(а,b) и С(а,b,с) соединением их связкой.

X множество, Р(х) - определенный на M одноместный предикат. Тогда выражение читается: "для всех х Р(х)" или "для всех х выполняется Р(х)", или "для любого х Р(х)", или "для каждого х Р(х)". Под выражением "хР(х)" будем подразумевать высказывание истинное, когда Р(х) истинно для каждого х из M и ложное - в противном случае. Символ х называется квантором всеобщности. Выражение читается "существует х такое, что Р(х)" или "хотя бы для одного х Р(х)", или "для некоторого (некоторых) х Р(х)". Под выражением "хР(х)" будем подразумевать высказывание, которое истинно, если Р(х) принимает значение И хотя бы для одного значения переменной х M, и ложно, если Р(х) для всех значений переменной х принимает значение Л. Символ х называется квантором существования. Квантор х будем называть двойственным к квантору х, и наоборот.

В литературе применяются и другие обозначения. Так, вместо хР(х) пишут хР(х) или хР(х), а вместо хР(х) пишут VхР(х) или VхР(х), или ЕхР(х) Введенные обозначения позволяют записывать предложения в символической форме, которая оказывается более удобной для анализа и логических действий над этими предложениями. При символизации языка требуется определенная аккуратность и правильное понимание контекста. В естественном языке часто слово "все" опускается. Так, например, предложение "рыбы дышат жабрами" означает, что все рыбы дышат жабрами или что каждая рыба дышит жабрами. Поэтому при символизации необходимо ввести квантор общности. Таким образом, если положить для множества живых существ, что R(х) означает "х - рыба", а G(х) - "х дышит жабрами", то имеем х(R(х)G(х)).

Но в то же время не в каждом случае встречающиеся в предложениях слова "все" понимаются как "каждый". Например, предложение "все песчинки образуют кучи пуска" не означает, что каждая песчинка образует кучи песка, следовательно, при символизации нельзя употреблять квантор х, как это сделано в предыдущем примере.

В языке слово "все" имеет два значения: "любой, каждый" и "все вместе". Квантор х применяется для первого значения.

Из изложенного следует, что "хР(х)" служит обозначением для следующих высказываний:

для всех х выполняется (имеет место) Р(х);

для каждого х выполняется (имеет место) Р(х);

для любого х выполняется (имеет место) Р(х);

для произвольного х выполняется (имеет место) Р(х);

каково бы ни было х выполняется (имеет место) Р(х).

В языке слово "некоторый", так же как и "все", часто опускается.

Например, предложение "люди побывали на Луне" означает, что некоторые люди побывали на Луне.

Символическая запись хР(х), как мы знаем, означает, что для некоторых х имеет место Р(х), но не исключено, что и для всех х имеет место Р(х). В естественном же языке слово "некоторый" иногда употребляют в смысле "не все". Когда говорят "некоторые студенты отличники", подразумевают, что некоторые, но не все студенты отличники.

Следовательно, имеется в виду: "неверно, что все студенты отличники, но некоторые - отличники". Тогда, если С(х) означает "х - студент", О(х) означает "х - отличник", то получим:

(х(С(х) О(х))) & х(С(х)&О(х)).

Итак, слово "некоторый" имеет два значения: первое - "некоторый, но может быть и все", второе - "некоторый, но не все". Символ х обозначает первое. Следовательно, запись хР(х) служит обозначением для следующих высказываний:

для некоторых х (имеет место) Р(х);

существует х, для которого Р(х);

найдется х, для которого Р(х);

хотя бы для одного х (верно) Р(х);

имеется х, для которого Р(х).

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

(А) все S суть Р Е) ни одно S не есть Р - х(S(х) Р(х));

(I) некоторые S суть Р - х(S(х)&Р(х));

(О) некоторые S не есть Р - х(S(х)& Р(х)).

Символизация приведенных предложений позволяет записывать в символическом виде довольно сложные выводы, использующие всевозможные комбинации предложений (А)-(О).

До сих пор мы рассматривали приписывание кванторов к одноместным предикатам.

Далее рассмотрим приписывание кванторов к многоместным предикатам. Пусть P(х1,х2,...,хn) -n-местный (n2) предикат, заданный на множестве M. Выражение является (n-1)-местным предикатом, зависящим от (свободных) переменных х1,х2,...,хi-1,хi+1,...,хn, причем высказывание хiР(а1,а2,...,а i-1,х i,а i+1,...,а n) истинно тогда и только тогда, когда для любого значения аiM истинно высказывание Р(а1,а2,...,а i-1,ai,а i+1,...,а n).

Выражение является (n-1)-местным предикатом, зависящим от (свободных) переменных х1,х2,...,х i-1,х i+1,...,х n, причем высказывание хiА(а1,а2,...,а i-1,х i,а i+1,...,а n) истинно тогда и только тогда, когда существует такое значение аi, (аiM) переменной хi, для которого высказывание (2.2) истинно.

Также положим, что если Р - нульместный предикат (высказывание), то записи хР и хР означают то же, что и Р.

Приписывание (навешивание) квантора по переменной х связывает переменную х. Приписывая к (n-1)-местным предикатам (2.1) и (2.3) любой квантор по любой из свободных переменных, получим (n-2)-местные предикаты (если n=2, то просто высказывание). Ясно, что к полученным предикатам можно снова приписать произвольные кванторы и т.д. Очевидно, что, приписав кванторы по всем переменным, получим высказывание.

Например, пусть на множестве действительных чисел задан трехместный предикат х2 + у2 z2, который можно превратить в двуместный предикат, записав квантор: z(х2 + у2 z 2) или превратить в одноместный предикат уz(х2 + у2 z2), или же превратить в высказывание:

можно получить и другие высказывания, например:

и т.д. Ясно, что высказывание (2.6) истинно, а (2.4) и (2.5) - ложные.

Упражнение. Пусть на множестве M задан трехместный предикат Р(х,у,z). Определить, какое число одноместных предикатов можно получить из Р(х,у,z), приписывая к нему различные кванторы.

Пусть множество M состоит из конечного числа элементов. Для определенности положим M = {а1,а2,...,аn} и пусть Р(х) заданный на M одноместный предикат. Тогда, очевидно, имеем:

Следовательно, квантор всеобщности является обобщением (аналогом) конъюнкции, а квантор существования - обобщением (аналогом) дизъюнкции на произвольное, не обязательно конечное, множество.

в виде символов. В этом параграфе рассмотрим правила образования из определенных символов различных выражений (термов, формул) без какихлибо ссылок на их содержательный смысл. Только в дальнейшем (§4) будем придавать содержательный смысл этим наборам символов, т.е.

рассматривать, какие предложения содержательного языка они могут обозначать.

Буквы начала латинского алфавита (а,b,с,...) и они же с числовыми индексами (а1,а2,...,b1,b2,...,с1,с2,...) называются предметными постоянными.

Буквы конца латинского алфавита (х,у,z,...) и они же с числовыми индексами (х1,х2,...,у1,у2,...,z1,z2,...) называются предметными переменными.

предикатными буквами, а f in, i 1, n 1, - функциональными буквами.

Верхний индекс предикатной или функциональной буквы указывает число аргументов, а нижний индекс служит для различения букв с одним и тем же числом аргументов.

Будем по возможности опускать числовые индексы у предикатных и функциональных букв, считая, что их легко можно восстановить. Например, вместо A1 (х,у) будем писать А1(х,у), и если нет других двухаргументных (двуместных) предикатных букв А, то вместо А1(х,у) будем писать просто А(х,у), кроме того иногда будем использовать буквы Р, Q, R, S для обозначения предикатных букв Ain.

Определение терма:

а) всякая предметная переменная или предметная постоянная есть терм;

б) если f in - функциональная буква и t1,t2,...,tn - термы, то f in (t1,t2,...,tn) есть терм;

Здесь приведена некоторая копия древнеегипетских записей – иероглифов. Она перерисована из книги С. Коваль, От развлечения к знаниям. Варшава, 1972.

в) выражение является термом только в том случае, если это следует из правил а) и б).

Примеры термов: а, х1, f 12 (х,а), f 32 (а, f 2 (у)).

Предикатные буквы, примененные к термам, порождают элементарные формулы, или точнее: если Ain - предикатная буква, а t1,t2,...,tn - термы, то Ain (t1,t2,...,tn) - элементарная формула.

Будем считать, что нульместная предикатная буква тоже является элементарной формулой.

A2 (х,у, f 12 (а,х)).

Формулы логики предикатов определяются следующим образом:

а) всякая элементарная формула есть формула;

б) если А и В - формулы и х - предметная переменная, то каждое из выражений (А), (АВ), (хА) и (хА) есть формула;

в) выражение является формулой только в том случае, если это следует из правил а) и б).

В выражениях (хА) и (хА) формула А называется областью действия кванторов х и х соответственно.

Примеры формул: ( A1 A1 (х,а)), (х A1 (х, f 1 ( f 1 (х)))), (х(х A1 (а))).

Если А и В - формулы, то договоримся, что А&В является сокращенной записью формулы ( (А ( В)), АВ является сокращенной записью формулы ((А)В), AВ является сокращенной записи формулы (((АВ) ((ВА)))).

Будем придерживаться тех же правил опускания скобок, которые приняты в §3 главы 1, введя дополнительно, что кванторы х, х располагаются по силе между связками,&, и связками,. Например, вместо ((хА)В) пишем хАВ.

Договоримся также опускать скобки, в которые заключается формула А в формулах вида (Q1(Q(А))), где Q1 и Q - любые кванторы. Например, вместо (х(у(z( A1 (х,у,z))))) пишем хуz A1 (х,у,z).

Вхождение переменной х в данную формулу называется связанным, если х является переменной входящих в эту формулу кванторов х, х или находится в области действия входящих в эту формулу кванторов х, х; в противном случае вхождение переменной х в данную формулу называется у A1 (х,у) A2 (у,у) является свободным, первое и второе вхождение переменной у - связанное, а третье и четвертое вхождение у в эту формулу свободное. Таким образом, одна и та же переменная в одной и той же формуле может иметь как связанные, так и свободные вхождения.

Переменная называется свободной (связанной) переменной в данной формуле, если существуют свободные (связанные) ее вхождения в эту формулу.

Формула называется замкнутой, если она не содержит никаких свободных переменных, т.е. либо все ее переменные связанные, либо переменных нет совсем. Например, формула х(у A1 (х,у) A2 (x,x)) замкнутая, а формула х A1 (х,у) - не замкнутая, ибо содержит свободную переменную у.

Замыканием формулы А называется формула, полученная из А приписыванием перед нею кванторов всеобщности по всем ее свободным переменным, при этом кванторы приписываются следующим образом:

сначала записываем кванторы общности по всем свободным переменным х (если они есть) в порядке возрастания их индексов, затем по свободным переменным у (если они есть) в порядке возрастания их индексов и т.д. Так, замыканием формулы A1 (х3,х1,у2) будет формула:

х1х3у2 A1 (х3,х1,у2), а замыканием для формулы у1х3 A1 (х1,у1,х3) A1 (х3,х2) будет формула:

х1х2х3(у1х3 A1 (х1,у1,х3) A1 (х3,х2)).

Интерпретацию будем считать заданной, если:

1. Задано непустое множество M, называемое областью интерпретации.

2. Заданы следующие соответствия:

a) предикатным буквам Ain поставлены в соответствие некоторые n местные предикаты (отношения) в M;

b) функциональным буквам f in поставлены в соответствие некоторые n аргументные функции, отображающие M n в M;

c) каждой предметной постоянной поставлен в соответствие некоторый (фиксированный) элемент из M;

d) символам,, x, x поставлен в соответствие их обычный смысл.

3. Считается, что предметные переменные пробегают всё множество M.

Например, чтобы задать интерпретацию для формулы x A1 (x,y,b1), нужно задать множество M - область интерпретации (область изменения переменных x,y). Из этой области M будем брать некоторый элемент, соответствующий предметной постоянной b1. Далее нужно задать 3-х местный предикат на M, соответствующей предикатной букве A1. Так, можно положить, что M=[0, ); предметной постоянной b1 поставить в соответствие 1, а A1 (x,y,z) поставить в соответствие предикат x + y z. Тогда формула x A1 (x,y,b1) в заданной интерпретации запишется:

и означает, что для любого x (x [0, )) сумма x + у больше или равна 1.

Очевидно, что это отношение истинно при некоторых у (у 1) и ложно при других значениях у (0уу, тогда высказывание означает, что для любого числа у существует число х большее, чем у. Это высказывание истинно. Высказывание, полученное из (2.20) перестановкой кванторов ху(х>у), означает, что существует число х больше любого другого числа и, очевидно, является ложным. Тогда ложна импликация:

ух(х>у)ху(х>у). Следовательно, формула (2.19) не истинна в приведенной интерпретации, т.е. не является логически общезначимой.

Теорема доказана.

Заметим, что в частном случае формула (2.19) может оказаться и логически общезначимой, например, когда А является замкнутой формулой.

В этом случае, как известно (см. § 6), формула А равносильна формуле Q1Q2...QnА, где Q1,Q2,...,Qn любая совокупность кванторов. Поэтому формула (2.19) будет логически общезначимой.

Однако подчеркнем еще раз, что для произвольной формулы перестановка разноименных кванторов не всегда приводит к равносильным формулам.

§ 9. Правила переименования связанных переменных Рассмотрим формулы хА(х) и уА(у). Очевидно, что в каждой интерпретации из истинности первой следует истинность второй, и наоборот, поэтому эти формулы равносильны: хА(х) ~ уА(у).

Таким образом, переименование переменной х на у в кванторе и в области действия этого квантора привело к формуле равносильной исходной.

В математическом анализе имеется аналогичное правило. Например, замена переменной в подинтегральном выражении определенного интеграла не меняет его величины:

Точно так же в сумме индекс суммирования можно переименовывать:

В последнем примере переименовывается n на k, но нельзя переименовывать m, ибо это свободная переменная.

В формуле хА(х) можно заменить переменную х на у. Ясно, что если х заменить любой другой переменной, то полученная формула будет равносильна исходной. Можно показать, что и в произвольной формуле переименование (замена) связанных переменных на любые другие приводит к формуле равносильной исходной. Имея в виду дальнейшие приложения, будем придерживаться следующего правила переименования связанных переменных.

Пусть А - произвольная формула логики предикатов. Формулу А получим из А заменой связанных переменных другими переменными, отличными от всех свободных переменных формулы А, причем заменяемая переменная в формуле А должна меняться одинаковым образом всюду в области действия квантора, связывающего данную переменную и в самом кванторе. Тогда А0 равносильна А.

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

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

Рассмотрим действие приведенного правила на примерах. Пусть имеем формулу Переименовав связанную переменную х на у, в первой посылке получим формулу, равносильную исходной:

уА(у)хВ(х)С(х).

Из формулы (3.21) переименованием можно получить формулу хА(х)zВ(z)С(х) или хА(х)уВ(у)С(х).

При этом каждая полученная формула будет равносильна исходной формуле (2.21).

Отметим еще раз, что переименовываются только связанные переменные, а свободные не трогаются. Так, в формуле (2.21) последнее вхождение х свободно, поэтому при любых переименованиях она остается неизменной.

Рассмотрим еще один пример. Пусть задана формула Переименовывая в этой формуле переменную х, мы должны заменить ее одинаковым образом всюду, где она входит, ибо х в формуле (2.22) является либо переменной квантора, либо находится в области действия квантора. Например, переименовав х на z, получим следующую формулу, равносильную исходной:

z(уР(z,у)уQ(z,у)R(z)) В формуле (2.22) переменную у можно переименовать в первой посылке, например, на переменную v, а во второй оставить без изменения, либо заменить, например, переменной u. В последнем случае получим формулу: х(vР(х,v)uQ(х,u)R(х)). Если учесть еще переименование переменной х, то имеем: z(vР(z,v)uQ(z,u)R(z)). Полученные формулы тоже равносильны исходной формуле (2.22).

§ 10. Правила вынесения кванторов за скобки. Предваренная Выясним, каким образом выносятся кванторы за скобки, при этом получим и правила внесения кванторов под скобки.

Теорема 2.6. Пусть А обозначает формулу, не имеющую свободных вхождений переменной х, В(х) и C(х) -произвольные формулы, возможно, и содержащие свободные вхождения х. Тогда:

Кроме того формулы (xB(x))xC(x)x(B(x)C(x)), логически общезначимы, а импликации, обратные к (2.29) и (2.30), уже не всегда логически общезначимы.

Доказательство. Докажем соотношение (2.23). Для этого возьмем произвольную, но фиксированную интерпретацию формулы А&хВ(х).

Если свободных переменных в формуле А&хВ(х) нет, то в интерпретации получим высказывание. Пусть это высказывание истинно, тогда истинны А и В(х) при любом значении х из области интерпретации M.

Поэтому будет истинно высказывание x(А&В(х)). Аналогичным образом из истинности x(А& &В(х)) следует истинность А&хВ(х).

Пусть формула А&хВ(х) имеет свободные переменные, для определенности пусть это у1, у2,...,уn. Придадим им произвольные значения из M, например, b1, b2,...,bn соответственно. Положим, что при указанных значениях у1, у2,...,уn формула А&хВ(х) принимает значение истина.

Последнее означает, что при у1=b1, у2=b2,...,уn= bn истинны А и В(х) при любом х из M, следовательно, при выбранных значениях свободных переменных истинно высказывание x(А&В(х)). Очевидно, верно и обратное.

Соотношение (2.23) доказано.

Доказательство равносильностей (2.24) - (2.28) и логической общезначимости формул (2.29) и (2.30) можно провести аналогично доказательству равносильности (2.23), т.е. фиксированием интерпретации.

Для завершения доказательства теоремы осталось доказать, что импликации, обратные к (2.29) и (2.30), точнее, формулы (хВ(х))&xC(x)x(B(x)&C(x)) не всегда являются логически общезначимыми. Чтобы доказать это, достаточно для каждой из импликаций (2.31) и (2.32) указать формулы В(х) и C(х) и для них привести хотя бы одну интерпретацию, где формулы (2.31) и (2.32) не истинны.

Пусть для формулы (2.31) область интерпретации есть множество целых чисел, формуле В(х) соответствует предикат "х - четное число", а формуле C(х) -предикат "х - нечетное число". Тогда, считая, что нуль четно, получим истинное высказывание х(х - четное число или х - нечетное число ), в то время, как высказывание [х(х-нечетное число ) или х(х - четное число)] ложно. Поэтому формула (2.31) в приведенной интерпретации ложна, следовательно, не логически общезначима.

Для формулы (2.32) можно взять ту же интерпретацию, что и для формулы (2.31). При этом легко видеть, что формула (2.32) ложна, следовательно, не логически общезначима. Теорема доказана.

Правила вынесения кванторов за скобки, когда задана импликация некоторых формул, следуют из теоремы.

Теорема 2.7. Пусть А - произвольная формула, не содержащая свободных вхождений переменой х, а В(х)- произвольная формула, возможно, и содержащая свободные вхождения х. Тогда Доказательство. Докажем соотношение (2.33). Рассмотрим формулу:

Вместо формулы (2.37) введем равносильную формулу х( В(х)А), которая по (2.24) равносильна формуле (х В(х))А, которая равносильна формуле хВ(х)А. Используя соотношение (2.15) между кванторами, получим формулу (хВ(х))А. Таким образом, формула х(В(х)А) равносильна формуле (хВ(х)) А, что и требовалось доказать.

Доказательство равносильностей (2.34)-(2.36) можно провести примерно так же, как доказывалось соотношение (2.33).

Из изложенного выше видно, что при вынесении кванторов за скобки для указанных формул кванторы могут выноситься без изменения, либо меняться на двойственные. В общем случае, оказывается, нужно проводить еще и переименование переменных, прежде чем вынести квантор за скобки.

Например, в формуле xB(x)xC(x) попытка вынести квантор х без изменения за скобки приводит к неравносильной формуле. Если при вынесении квантора за скобки его сменить на двойственный, то полученная формула тоже не всегда равносильна исходной. Именно поэтому необходимо переименование связанных переменных.

Теорема 2.8. Пусть В(х) и C(х) - произвольные формулы логики предикатов, которые, может быть, содержат свободные вхождения переменной х, тогда имеют место следующие равносильности:

где z и у - переменные, отличные от всех свободных переменных формул В(х) и C(х), а В(у) и C(z) -формулы полученные из В(х) и C(х) соответственно при переименовании связанной переменной х на у и z.

Доказательство. Рассмотрим формулу Пусть у и z - переменные отличные от всех свободных переменных формулы (2.42). Проведем переименование связанной переменной х в посылке этой формулы на переменную у, а в заключении - на z. Получим равносильную формулу:

По построению в формуле (2.43) выражение zC(z) не содержит свободных вхождений переменной у, тогда по равносильности (2.35) можно вынести за скобки квантор у, причем он сменится на двойственный, т.е.

получим у(В(у)zC(z)).

Так как формула В(у) не содержит свободных вхождений z, то, используя равносильность (2.34), получим требуемое соотношение (2.38).

Для доказательства соотношения (2.39) выразим импликацию в левой части соотношения (2.39) через и :

хВ(х)хC(х) (хВ(х))хC(x) (х В(х))хC(х).

Далее по доказанной равносильности (2.28) получаем: х( В(х)C(х)) откуда и следует равносильность (2.39).

Равносильности (2.40) и (2.41) доказываются аналогично как для соотношения (2.38).

Замечание 1. При доказательстве равносильности (2.38) мы вынесли за скобки квантор из посылки, а затем, из заключения, хотя, как легко видеть, можно сделать это и в обратной последовательности: сначала вынести квантор из заключения, а затем из посылки. В этом случае вместо (2.38) получим Так как левые части равносильностей (2.38) и (2.44) совпадают, то имеем:

Известно, что в общем случае разноименные кванторы не перестановочны, а в частном случае (2.45) разноименные кванторы оказались перестановочными. Таким образом, в равносильности (2.45) в правой части порядок кванторов несущественен. Можно показать, что и в правых частях равносильностей (2.40) и (2.41) порядок кванторов не существенен.