- •Введение
- •Предисловие
- •1. Теория множеств
- •1.1. Понятие множества
- •1.2. Операции над множествами
- •1.3. Основные тождества алгебры множеств
- •1.4. Кортежи и декартово произведение множеств
- •1.5. Бинарные отношения. Свойства отношений
- •1.6. Соответствия. Отображения. Функции
- •Вопросы для самопроверки
- •2. Элементы комбинаторики
- •Вопросы для самопроверки
- •3. Логические операции
- •3.1. Основные понятия
- •3.2. Простейшие связки (операции)
- •3.3. Другие связки (операции)
- •3.4. Основные законы, определяющие свойства введенных логических операций.
- •4. Булевы функции
- •4.1. Основные понятия
- •4.2. Свойства элементарных булевых функций
- •4.3. Дизъюнктивные и конъюнктивные нормальные формы алгебры высказываний
- •4.4. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
- •Задачи по теме «Булевы функции.»
- •Вопросы для самопроверки
- •5. Теория графов
- •5.1. Ориентированные графы
- •5.2. Неориентированные графы
- •5.3. Матричное задание ориентированных графов
- •5.4. Матричное задание неориентированных графов
- •5.5. Изоморфизм графов
- •5.6. Операции над графами
- •5.7. Пути, контуры, маршруты, цепи, циклы
- •5.8. Расстояние в графах
- •5.9. Связность в неориентированных графах
- •5.10. Связность в ориентированных графах
- •5.11. Эйлеровы графы
- •5.12. Гамильтоновы графы
- •5.13. Деревья
- •5.14. Остовные деревья
- •5.15 Взвешенные графы. Экстремальные остовы графов
- •5.16 Поиск кратчайшего пути между вершинами. Алгоритм Дейкстры
- •5.17 Раскраска графов. Раскраска вершин графа
- •Вопросы для самопроверки
- •Библиографический список
- •Оглавление
- •Подписано к изданию «8» октября 2014.
- •394026 Воронеж, Московский просп., 14
4. Булевы функции
4.1. Основные понятия
Функцию , принимающую одно из двух значений 0 или 1, от п переменных, каждая из которых принимает одно из двух значений 0 или 1, будем называть булевой функцией от п переменных, называемых пропозиционными.
Булева функция от п переменных сопоставляет каждому упорядоченному набору (кортежу), составленному из п элементов, 0 и 1, либо 1, либо 0.
Две булевы функции называются равными, если для любых одинаковых наборов значений переменных обе функции принимают одинаковые значения. Булевых функций одной переменной четыре, а двух переменных — шестнадцать и т. д. Число булевых функций от п переменных равно .
Рассмотрим функции одной и двух переменных, которые называются «элементарными» функциями и с помощью которых можно определить функции большего количества переменных.
Рассмотрим таблицы истинности таких функций. В таблице, задающей булевы функции, наборы значений переменных пишут в лексикографическом порядке, который совпадает с порядком возрастания наборов, рассматриваемых как числа в двоичной системе счисления.
Таблица истинности булевой функции одной переменной:
Таблица 22.
-
x
0
0
0
1
1
1
0
1
0
1
Функции и называются константами — соответственно 0 и 1.
Функция совпадает с переменной х и называется тождественной .
Функция принимает значения, противоположные значениям аргумента х, и называется отрицанием х, обозначается :
Таблица истинности булевой функции двух переменных:
Таблица 23.
x1 |
x2 |
f1 |
f2 |
f3 |
f4 |
f5 |
f6 |
f7 |
f8 |
f9 |
f10 |
f11 |
f12 |
f13 |
f14 |
f15 |
f16 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
l |
l |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
l |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
Следует отметить, что здесь к функциям двух переменных относятся и такие, которые в действительности зависят от одной переменной.
1. Функции и представляют собой константы 0 и 1.
2. Функции , существенно зависят только от одной переменной: .
3. Остальные функции существенно зависят от двух переменных, и для них есть названия и обозначения:
а) функция и называется конъюнкцией,
б) функция и называется дизъюнкцией,
в) функция и называется эквивалентностью,
г) функция и называется суммой по модулю два, или суммой Жегалкина,
д) функция и называется конверсией,
е) функция и называется импликацией,
ж) функция и называется штрих Шеффера,
з) функция и называется стрелкой Пирса,
и) функции и логически несовместимы с импликацией и конверсией и называются функциями запрета.