Признак равносильности формул

Министерство образования и науки Российской Федерации

Нижнекамский химико-технологический институт (филиал)

Федерального государственного бюджетного образовательного

Учреждения высшего образования

«Казанский национальный исследовательский технологический

Университет»

 

 

А.В. Садыков

 

 

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

 

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

Нижнекамск

2016

УДК 510.6

С 14

Печатается по решению редакционно-издательского совета НХТИ ФГБОУ ВО «КНИТУ».

 

Рецензенты:

Апайчева Л.А., кандидат физ.-мат. наук, доцент;

Саримов Н.Н., кандидат физ.-мат. наук, доцент.

 

Садыков, А.В.

С 14 Математическая логика: учебное пособие / А.В. Садыков. – Нижнекамск: НХТИ ФГБОУ ВО «КНИТУ», 2016. – 93 с.

 

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

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

Подготовлено на кафедре математики Нижнекамского химико-технологического института.

 

УДК 510.6

 

© Садыков А.В., 2016

© НХТИ ФГБОУ ВО «КНИТУ», 2016

Содержание

1. ЛОГИКА ВЫСКАЗЫВАНИЙ …….………….…….… 4

1.1. Высказывания и операции над ними …………………4

1.2. Формулы алгебры высказываний …………………… 6

1.3. Классификация формул. Равносильные формулы….. 7

1.4. Нормальные формы ………………………………..... 12

1.5. Логическое следование ……………………………… 18

1.6. Правила вывода ……………………………………… 21

2. ФУНКЦИИ АЛГЕБРЫЛОГИКИ И ИХ ПРИЛОЖЕНИЯ ………………………………………………………………….25

2.1. Функции алгебры логики …………………………… 25

2.2. Специальные замкнутые классы функций
алгебры логики ……………………………….…...… 29

2.3. Приложение булевых функций к анализу
и синтезу релейно-контактных схем.................……. 31

3. ИСЧИСЛЕНИЕ ВЫСКАЗЫВАНИЙ ……..….……… 33

4. ПРАВИЛО РЕЗОЛЮЦИЙ…….……………………… 38

5. ЛОГИКА ПРЕДИКАТОВ ………………..…….……. 41

4.

5.

5.1. Определение предиката ……………………….……. 41

5.2. Логические операции над предикатами …….……... 43

5.3. Теоретико-множественный смысл предикатов…..… 46

5.4. Классификация предикатов …………………….….. 47

5.5. Формулы логики предикатов. Равносильность формул …………………….……………………………..…… 47

5.6. Классификация формул логики предикатов……… 49

6. ИСЧИСЛЕНИЕ ПРЕДИКАТОВ ……………….……. 52

7. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ…... 54

ЛИТЕРАТУРА …………..………….. ………………….. 92

 

1. ЛОГИКА ВЫСКАЗЫВАНИЙ

1.1. Высказывания и операции над ними

Определение 1. Высказывани­е – связное повествовательное предложение, о котором можно сказать истинно оно или ложно.

Примеры.

А ₁ – " 8 < 5 "

А ₂ – " Город Саратов находится на берегу Волги "

А ₃ – " Слава российским космонавтам! "

В приведенных примерах высказываниями являются А ₁, А ₂, причем А ₁ – ложное высказывание, А ₂ – истинное высказывание. А ₃ не является высказыванием, так как не является повествовательным предложением.

Высказывание можно рассматривать как величину, принимающую два значения: " истина " и " ложь ". Высказывания будем обозначать латин­скими буквами, а их значения, то есть " истину " и " ложь ", соответственно 1 и 0. Введем функцию l, заданную на совокупности всех высказываний и принимающую значения в множестве {0, 1}, по следующему правилу:

Функцию l называют функцией истинности, а значение для высказывания P – значением истинности или логическим значением высказывания P. Для приведенных высказываний имеем .

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

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

Определение 3. Дизъюнкцией двух высказываний А, В на­зывается высказывание A Ú B, которое ложно тогда и только тогда, когда ложны одновременно оба высказывания.

В обычной речи опе­рации дизъюнкции соответствует соединение высказываний связкой " или " с той лишь разницей, что A Ú B согласно определению истинно и в случае, когда и А, и В оба истинны. Дизъюнкцию еще обозначают символом +.

Определение 4. Импликацией двух высказываний А, В на­зывается высказывание А ® В, которое ложно тогда и только тогда, когда высказывание А истинно, а В ложно.

В обычной речи импли­кации соответствует связка " если... то ".

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

Также по определению при истинном В высказывание А ® В истинно независимо от того, какое значение принимает А. В обычной речи оба высказывания А и В могут быть истинными, но истинность В не выводится из истинности А как, например в пред­ложении " если калина красная, то снег белый".

Определение 5. Эквивалентностью двух высказываний А, В называется высказывание А «В, которое истинно тогда и только тогда, когда оба данных высказывания имеют одинаковые значения, то есть либо оба истинны, либо оба ложны. В обычной речи эквива­лентности соответствует связка " тогда и только тогда ".

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

Операция отрицания является унарной операцией, остальные – бинарными. Таблицы истинности этих операций имеют вид:

 

А В	А В	A Ú B	А ® В	А «В
0 0
0 1
1 0
1 1

1.2. Формулы логики высказываний

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

Понятие формулы в алгебре высказываний вводится индук­тивно.

Определение 7.

1. Переменные высказывания (пропозицио­нальные переменные) X, Y, Z, X_i, Y_i, Z_i (i Î N) и логические константы 0,1 – формулы.

2. Если F ₁ и F ₂ – формулы, то выражения (i = 1, 2), (F ₁ F ₂), (F ₁ÚF₂), (F ₁®F₂), (F ₁«F₂) также являются формулами.

3. Никаких других формул, кроме тех, которые образуются с помощью пунктов 1–2, нет.

Замечание 1. Для всякого выражения в алфавите { X, Y, Z, X_i, Y_i, Z_i (i Î N), , , Ú, ®, «, (,)}, используя пункты 1, 2 оп­ределения 7, очевидно, можно выяснить, является оно формулой или нет.

Замечание 2. Соглашение о скобках. Для упрощения записи формул разрешается не писать:

а) внешние скобки;

б) скобки с учетом силы (приоритета) операции: самая сильная операция – отрицание (выполняется в первую очередь), затем в порядке следования –, , Ú, ®, «.

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

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

 

1.3. Классификация формул.

Равносильные формулы

Определение 9. Формула называется выпол­нимой (опровержимой), если существует ее истинная (ложная) ин­терпретация.

Определение 10. Формула называется тавтологией (противоречием), если любая ее интерпретация истинна (ложна). Если формула является тавтологией, то пи­шут ╞ .

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

 

…	…
…	…

 

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

Пример. Построить таблицу истинности для формулы .

Решение.

0 0
0 1
1 0
1 1

 

 

Можно сформулировать следующую задачу: дать способ, позволяющий для каждой формулы конечным числом действий определить ее тип по приведенной (см. определения 9, 10) классификации. Поставленная задача носит название " проблемы разрешимости ". Эта проблема, очевидно, легко решается построени­ем соответствующей таблицы истинности для формулы , хотя число действий может оказаться очень большим, но оно конечно, в силу конечности (конечное число переменных и конечное число операций) формулы.

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

Очевидно, равносильные формулы имеют одинаковые таб­лицы истинности. Бинарное отношение равносильности на множест­ве формул обозначают @.

Основные равносильности

1. Законы нуля и единицы

2. Закон двойного отрицания

.

3. Коммутативные (переместительные) законы

.

4. Ассоциативные (сочетательные) законы

5. Дистрибутивные (распределительные) законы

6. Законы де Моргана

.

7. Законы идемпотентности (одинаковости)

.

8. Законы поглощения

9. Закон исключенного третьего

.

10. Закон противоречия

.

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

Упражнение 1. Доказать равносильности:

а) ;

б) ;

в) ;

г) ;

Лемма (о замене). Пусть - произвольная формула и .

Тогда Доказательство проводится непосредственным использованием определения равносильности формул. Эта лемма на практике позволяет осуществлять равносильные преобразования формул.

Признак равносильности формул

Теорема 1. Две формулы F и G алгебры высказываний равносильны тогда и только тогда, когда формула является тавтологией:

╞ .

Доказательство следует непосредственно из определений 5, 11.

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

Определение 12. Пусть – формула логики высказываний. Двойственной к ней называют формулу, определенную следующим образом

Замечание 3. Из закона двойного отрицания следует, что :

Теорема 2. Формулы и равносильны тогда, и только тогда, когда двойственные им формулы и тоже равносильны.

, (1)

Доказательство. Пусть – равносильны, а – пропозицио­нальные переменные, входящие в эти формулы.

Из равносильности и следует:

, (2)

Из (2) следует

, (3)

Отсюда

, ч.т.д.

Замечание 4. Пусть формула получается из формулы f на основании первого дистрибутивного закона. Тогда переход от к осуществляется на основании второго дистрибутивного закона.

Определение 13. Переход от к называется преобразованием, двойственным преобразованию, переводящему f в .

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

1.4. Нормальные формы

Введем обозначения

Пусть имеется набор пропозициональных переменных .

Определение 14. Формула , где , называется конъюнктивным одночленом (КО) или элементарной конъюнкцией.

Определение 15. Дизъюнкция КО называется дизъюнктивной нормальной формой (ДНФ).

Определение 16. Формула , где , называется дизъюнктивным одночленом (ДО) или элементарной дизъюнкцией.

Определение 17. Конъюнкция КО называется конъюнктивной нормальной формой (КНФ).

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

Примеры ДНФ, КНФ.

– ДНФ

– КНФ

Конъюнктивный одночлен, дизъюнктивный одночлен называют еще элементарным произведением и элементарной суммой.

Всякую формулу можно выразить через конъюнкцию, дизъюнкцию и отрицание. Используя законы де Моргана и свойство дистрибутивности конъюнкции относительно дизъюнкции можно преобразовать равносильным образом получаемое выражение ДНФ. Если же к исходному выражению применить свойство дистрибутивности дизъюнкции относительно конъюнкции, то его можно свести к КНФ. Таким образом, справедлива теорема.

Теорема 4. Любая формула равносильными преобразованиями может быть приведена к ДНФ и КНФ.

Теорема 5. Формула является тавтологией (противоречием) тогда и только тогда, когда в ее КНФ (ДНФ) в каждом ДО (КО) некоторая переменная встречается вместе со своим отрицанием.

Совершенные нормальные формы

Среди нормальных форм важную роль играют совершенные нормальные формы.

Совершенная дизъюнктивная нормальная форма

Определение 18. Совершенной дизъюнктивной нормальной формой (СДНФ) формулы , содержащей n различных переменных, называется ее ДНФ, удовлетворяющая следующим условиям:

1) в ней нет двух одинаковых слагаемых;

2) ни одно слагаемое не содержит двух одинаковых множителей;

3) никакое слагаемое не содержит переменной вместе с ее отрицанием;

4) в каждом слагаемом в качестве множителя содержится либо переменная , либо ее отрицание .

Условия определения 18 позволяют получить правила, с помощью которых можно приводить формулу к СДНФ. Опишем эти правила.

Пусть дана произвольная формула . Процедура приведения к СДНФ:

1) Сначала приведём её к ДНФ. Пусть ДНФ для f – это формула (то есть ).

2) Затем, если какое-нибудь слагаемое не содержит переменной , то добавим недостающую переменную:

,

Тогда условие 4) будет выполнено.

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

4) Если в некоторых слагаемых окажется несколько одинаковых множителей, то лишние множители можно удалить (используем закон ):

5) Удалим все слагаемые, которые содержат какую-либо переменную вместе с ее отрицанием ( такие слагаемые тождественно ложны). Если бы все слагаемые оказались таковыми, то вся сумма тождественно ложна. Тогда и формула f – тождественно ложна. В таком случае f не имеет СДНФ.

После выполнения указанных действий 1), 2), 3), 4), 5) получим СДНФ.

Замечание 5. При приведении к СДНФ нет необходимости знать заранее, является ли формула тождественно ложной или нет. Если выполняя операции пункта 5), будут удалены все слагаемые, то не получим СДНФ.

Таким образом, справедливо:

Свойство 1. У противоречий не существует СДНФ.

Пример. Привести формулу к СДНФ:

– ДНФ;

;

– CДНФ.

 

Совершенная конъюнктивная нормальная форма

Аналогичным образом определяется СКНФ. Определение дается в терминах, двойственных тем, которые были использованы в определении 18.

Определение 19. Совершенной конъюнктивной нормальной формой (СКНФ) формулы , содержащей n различных переменных, называется ее КНФ, удовлетворяющая следующим условиям:

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

2) ни один множитель не содержит двух одинаковых слагаемых;

3) никакой множитель не содержит какой-нибудь переменной вместе с ее отрицанием;

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

Правила приведения к СКНФ аналогичны тем, которые описаны выше для нахождения СДНФ, и выражаются в двойственных терминах (то есть конъюнкцию меняем на дизъюнкцию, дизъюнкцию на конъюнкцию, 0 на 1, 1 на 0).

Замечание 6. Если множители содержат какую-нибудь переменную вместе с ее отрицанием ( истина), то их удаляем. Если все множители такие, то всё произведение тождественно истинно; следовательно формула не имеет СКНФ.

Таким образом, справедливо:

Свойство 2. У тавтологий не существует СКНФ.

Пример. Привести формулу к СКНФ:

;

– КНФ;

;

;

– CКНФ.

Свойство 3. Каждая формула алгебры высказываний, не являющаяся тавтологией или противоречием, имеет СКНФ и СДНФ, причем единственные.

Доказательство. Существование СКНФ, СДНФ для формулы, не являющейся тавтологией или противоречием, следует из свойств 1,2. Доказательство единственности проводится методом от противного.

Можно дать следующее определение СКНФ, СДНФ:

Определение 20. Конъюнктивная (дизъюнктивная) НФ называется совершенной, если выполняются условия:

1) каждая переменная из полного набора содержится во всех элементарных дизъюнкциях (конъюнкциях) ровно один раз с отрицанием или без;

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

Совершенные нормальные формы позволяют дать критерий равносильности двух произвольных формул f и . Каковы бы ни были формулы f и , можно предположить, что они содержат одни и те же переменные. Если, например, формула f не содержит переменной , то можно ее заменить равносильной формулой:

.

Любые две формулы можно заменить равносильными им формулами, содержащими одинаковые переменные. Эти формулы надо привести к СКНФ или СДНФ.

Если формулы f и равносильны, то в силу единственности СНФ должны совпадать. Таким образом, сравнение СНФ формул f и решает вопрос об их равносильности.

Построение СДНФ, СКНФ на основе таблиц истинности

СДНФ: На основе 5-го пункта процедуры приведения к СДНФ слагаемые, равные 0, отбрасываются, то есть в СДНФ входят слагаемые, соответствующие наборам переменных, при которых формула имеет значение 1. Следовательно, можно предложить следующую процедуру получения СДНФ:

1) по каждому набору переменных, при которых формула принимает значение 1, составить элементарные конъюнкции;

2) в эти элементарные конъюнкции записать без инверсии переменные, заданные 1 в наборе, и с инверсией – переменные, заданные 0;

3) соединить элементарные конъюнкции знаком дизъюнкции.

Процедура получения СКНФ:

1) по каждому набору переменных, при которых формула принимает значение 0, составить элементарные дизъюнкции;

2) в элементарные дизъюнкции записать без инверсии переменные, заданные 0 в наборе, и с инверсией – переменные, заданные 1;

3) элементарные дизъюнкции соединить знаком конъюнкции.

Пример. Привести к СДНФ, СКНФ с помощью таблицы истинности

;

 

x	y	z		СДНФ	СКНФ

 

СДНФ: ;

СКНФ:

 

Другое определение совершенных

нормальных форм

Определения 18, 20 можно объединить.

ДО или КО называется совершенным, если в нем каждая переменная встречается один раз с отрицанием или без отрицания. Они имеют следующий вид:

СДО:

СКО:

Определение 21. КНФ (ДНФ) называется совершенной, если в ней все ДО (КО) являются совершенными.

1.5. Логическое следование

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

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

Теорема 6. ├ ╞ .

Доказательство следует непосредственно из определений.

Определение 23. Формула G называется логическим след­ствием формул , если для любых конкретных высказыва­ний из одновременной истинности формул следует истинность формулы .

Если G является логическим следствием , то это обстоятельство обозначается через ├ . Формулы называются посылками, a G – следствием этих посылок.

Теорема 7. Следующие утверждения

1) ├ ,

2) ├ ,

3) ╞

являются равносильными.

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

1. Даны посылки . Требуется найти все возможные следствия из этих посылок.

2. Дано следствие, то есть формула G, найти все возможные посылки, из которых G является следствием.

Сформулированные задачи можно решить, используя таблицы истинности заданных формул. При решении прямой задачи строим таблицы истинности для формул и отмечаем в таблице все строки, в которых одновременно истинны. Очевидно, поскольку искомые G должны быть следствиями посылок , то G в отмеченных строках обязаны принимать значение 1, а в остальных какие угодно значения. Перебирая все возможные варианты значений в неотмеченных строках, мы получим все иско­мые следствия.

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

Х 1 Х 2	F 1	F 2	G 1	G 2	G 3	G 4
0 0
0 1
1 0
1 1

Пусть наоборот дано следствие G. Требуется найти все воз­можные посылки, из которых следует G. При решении обратной за­дачи строим таблицу истинности G и отмечаем строки, в которых G ложно, то есть принимает значение 0. Очевидно, если G является след­ствием некоторой посылки F, то F в отмеченных строках обязана принимать значение 0. В остальных строках F может принимать лю­бые значения. Посредством перебора всех вариантов значений F в неотмеченных строках построим все возможные посылки для G.

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

Х 1 Х 2	G	F 1	F 2	F 3	F 4
0 0
0 1
1 0
1 1

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

Теорема 8. Для того чтобы формула G, не являющаяся тавтологией, была логическим следствием формул , из которых, по крайней мере, одна не является тавтологией, необходимо и достаточно, чтобы в СКНФ формулы G все дизъюнк­тивные одночлены были из СКНФ формулы