- •1. Элементы теории множеств
- •1.1 Множества. Основные понятия
- •1.2. Способы задания множеств
- •1.3. Операции над множествами. Диаграммы Венна
- •1.4. Свойства операций над множествами
- •1.5. Прямое (декартово) произведение множеств
- •1.6 Разбиения и покрытия
- •1.7. Замечание о мощности некоторых множеств
- •1.8 Представление множеств в эвм
- •1.9. Отношения
- •1.9.1.Определения
- •1.9.2 Бинарные отношения
- •1.9.3. Способы задания бинарных отношений
- •1.9.4 Свойства бинарных отношений
- •1.9.5. Отношение эквивалентности
- •1.9.5. Отношение порядка
- •1.9.6.1. Минимальные и максимальные элементы множества
- •1.9.6.2. Диаграммы Хассе
- •1.9.6.3. Принцип двойственности
- •1.9.7. Представление отношений в эвм
- •1.10. Соответствия. Функции. Операции. Отображения
- •1.10.1. Соответствия и их свойства
- •1.10.2 Функции и отображения
- •1.10.3. Инъекция, сюръекция и биекция
- •1.10.4. Композиция и суперпозиция функций. Способы задания функций
- •1.10.5. Представление функций в эвм
- •1.10.6. Операции
- •1.10.6.1. Способы задания операций
- •1.11. Алгебраические структуры
- •1.11.2. Замыкание и подалгебры
- •1.11.3. Гомоморфизм и изоморфизм
- •1.11.4. Алгебры с одной бинарной операцией
- •1.11.5. Алгебры с двумя бинарными операциями
- •1.11.6.Решетки
- •1.11.7. Булевы алгебры
- •2. Элементы математической логики и булевы функции
- •2.1. Операции над высказываниями
- •2.2. Логические операции (логические связки)
- •2.3. Элементарные булевы функции
- •2.3.1. Функции алгебры логики
- •2.3.2. Равносильность функций. Существенные и несущественные переменные
- •2.3.3. Реализация функций формулами. Суперпозиция функций
- •2.3.4. Подстановки и замены
- •2.3.5. Принцип двойственности
- •2.3.6. Нормальные формы в логике высказываний
- •2.3.6.1. Разложение булевых функций по переменным. Дизъюнктивно-нормалльная форма (днф)
- •2.3.6.2. Совершенная дизъюнктивная нормальная форма
- •2.3.7. Арифметические операции в алгебре логики. Полиномы Жегалкина
- •2.3.8. Монотонные функции алгебры логики
- •2.3.9. Функционально замкнутые классы
- •2.4. Полнота системы булевых функций. Теорема
- •2.5. Элементы логике предикатов
- •2.5.1. Определение предиката
- •2.5.2. Кванторы. Формулы логики предикатов
- •2.5.3. Равносильность формул
- •2.5.4. Предикаты на конечных областях. Логика одноместных предикатов
- •2.6. Операции над предикатами и кванторами
- •2.7. Построение доказательств в логике предикатов
- •1.6.2. Разбор решений задач по логике предикатов
- •1. Элементы теории множеств 3
- •1.1 Множества. Основные понятия 3
- •2.6. Операции над предикатами и кванторами 137
- •394026 Воронеж, Московский просп., 14
2.3. Элементарные булевы функции
Подобно тому, как в математическом анализе знакомство с основами начинают с изучения основных элементарных функций (sin, log, и т.д.), так и изучение теории булевых функций естественно начинать с изучения основных элементарных булевых функций.
Основные булевы операции – конъюнкция, дизъюнкция, инверсия.
2.3.1. Функции алгебры логики
Мы установили, что с точки зрения алгебры высказываний логические операции полностью характеризуются таблицами истинности. При этом можно забыть о том, что мы рассматриваем какие-то операции над высказываниями, и иметь дело лишь с самими таблицами.
Определение
Функцией алгебры логики от n переменных
(х1, х2, х3, … ,хn) называется функция f: , где Е2:={0,1}. (или булева функция).
Таким образом, как аргументы функции, так и сама функция принимают только два значения: 1и 0.
Множество булевых функций от n переменных обозначим Pn, где Pn := {f(f: )}.
Функцию от n переменных f(х1, х2, х3, … ,хn) можно задать ее таблицей истинности (см. выше).
Легко заметить, число различных двоичных наборов длины n – упорядоченных наборов (α1, α2, ...,αn) из 0 и 1 – конечно.
х1 |
х2 |
х3 |
… |
хn-1 |
xn |
f(х1, х2, х3, … ,хn) |
0 1 … 1 1 |
0 0 … 1 1 |
0 0 ... 1 1 |
... ... ... ... .... |
0 0 ... 1 1 |
0 0 ... 1 1 |
f(0,0, ...,0,0) f(1,0, ...,0,0) ..................... f(1,1, ...,1,0) f(1,1, ..., 1,1) |
У нас имеется некоторое количество «основных» логических операций (отрицание, дизъюнкция, конъюнкция, импликация, эквивалентность). Они позволяют получить из простых высказываний сложные. При этом вместо простых высказываний можно брать уже построенные сложные. В результате появляется возможность применять при построении сложных высказываний многоступенчатые конструкции, многократно использующие введенные логические операции.
Назовем формулами логические операции, которые получаются комбинированием конечного числа указанных выше основных логических операций.
Пример : P : «Влажность большая»; Q: «Температура высокая»; С: «Мы чувствуем себя хорошо».
Тогда предложение: «Если влажность большая и температура высокая, то мы не чувствуем себя хорошо» можно записать в виде
(P^Q) .
Таким образом, составное высказывание может выражать довольно сложную мысль (является формулой).
Определение: Формулы в логике высказываний определяются следующим образом:
1. Атом есть формула.
2. Если G – формула, то - формула.
3. Если G и Н – формулы, то (G^H), (GvH), (G H) и (G H) – формулы.
4. Никаких формул, кроме порожденных применением указанных выше правил, нет.
Легко видеть, что такие выражения, как (P→) и (Pv), не являются формулами.
Для всякой формулы можно построить истинностную таблицу, последовательно пользуясь истинностными таблицами для основных операций.
Естественно считать равносильными формулы, которым соответствуют одинаковые истинностные таблицы.
Определение
Пусть U и В – две формулы высказываний, а
А1, А2, …, Аn – набор простых высказываний, входящих по крайней мере, в одну из формул U и В. Формулы U и В называются равносильными, если при всех значениях истинности А1, А2, …, Аn значения истинности U и В совпадают.
Равносильность U и В обозначается посредством обычного значка равенства:
U = В.
Примеры:
1) AvA = A; 2) (Av ) ^ B = B; 3) Av = Bv
4) Av(A^B) = A (доказать!).
Из определения видно, что наборы простых высказываний, входящих в равносильные формулы U и В, могут быть различными.
В этом случае, простые высказывания, входящие лишь в одну из формул, входят в нее фиктивным образом, т.е. истинность этой формулы не зависит от истинности этих простых высказываний.
Оказывается, что любую логическую операцию (с точностью до равносильности) можно выразить через основные операции; более того, для этого даже достаточно дизъюнкции, конъюнкции и отрицания.