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

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

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

Федерального муниципального экономного образовательного

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

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

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

А.В. Садыков

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

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

Нижнекамск

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. Высказывани­е – связное повествовательное предложение, о котором можно сказать поистине оно либо неверно.

Примеры.

А1 – " 8 < 5 "

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Замечание 1.Для всякого выражения в алфавите {X, Y, Z, Xi, Yi, Zi (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.Закон противоречия

.

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

Упражнение 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-ух схожих слагаемых;

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

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

4) в каждом слагаемом в качестве множителя Признак равносильности формул содержится или переменная , или ее отрицание .

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

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

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

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

,

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

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

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

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

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

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

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

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

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

– ДНФ;

;

– CДНФ.

Совершенная конъюнктивная обычная форма

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

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

1) в ней нет 2-ух схожих множителей;

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

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

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

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

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

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

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

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

;

– КНФ;

;

;

– CКНФ.

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

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

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

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

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

2) посреди простых дизъюнкций (конъюнкций) нет схожих.

Совершенные обычные формы позволяют дать аспект равносильности 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 F1 F2 G1 G2 G3 G4
0 0
0 1
1 0
1 1

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

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

Х1Х2 G F1 F2 F3 F4
0 0
0 1
1 0
1 1

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

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

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

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


priznaki-yuridicheskaya-kvalifikaciya-vreda-zdorovyu.html
priznaki-zarazheniya-pk-virusom.html
priznakov-zhenshin-znakomitsya-s-kotorimi-ne-stoit-ili-povest-o-tom-kak-ya-do-zhizni-takoj-dokatilsya.html