- •Элементы комбинаторного анализа
- •1.1. Начальные понятия теории множеств
- •Свойства операций над множествами
- •Булева алгебра
- •2.1. Логика высказываний
- •2.2. Понятие булевой функции
- •Примеры булевых функций
- •2.3. Реализация булевых функций формулами
- •2.5. Разложение булевых функций по переменным
- •2.4. Двойственные функции
- •2.6. Полнота системы булевых функций
- •2.7. Полином Жегалкина
- •2.8. Классы функций, сохраняющих 0 и 1
- •2.9. Класс самодвойственных функций
- •2.10. Класс монотонных функций
- •2.11. Класс линейных функций
- •2.12. Критерий полноты (теорема Поста)
- •3.1. Начальные понятия теории графов
- •3.2. Маршруты, цепи и циклы в графе
- •3.3. Связность, компоненты связности графа
- •3.4. Цикломатическое число графа
- •3.5. Матрицы, ассоциированные с графом
- •3.6. Деревья и леса
- •3.7. Кодирование деревьев
- •3.8. Эйлеровы графы
- •3.9. Раскраска графа
- •3.10. Планарные графы
- •3.11. Ориентированные графы
- •3.12. Задача о кратчайшем пути
- •3.13. Задача о максимальном потоке
Булева алгебра
2.1. Логика высказываний
Любая научная теория воспринимается нами как некоторая система понятий и утверждений. Истинность каждого утверждения нуждается в доказательстве, которое в математике проводится с использованием логических средств. Именно эти логические средства изучает раздел математики, называемый математической логикой. Исходным понятием математической логики является понятие высказывания.
Под высказыванием принято понимать повествовательное предложение, о котором имеет смысл говорить, что оно истинно или ложно.
Например,
предложение «
»
- истинное высказывание. Предложение
«
»
- ложное высказывание. Предложения «
»
и «Студенты, ходите на лекции!»
высказываниями не являются.
В математической логике интересуются не содержанием высказывания, а его истинностным значением, т.е. его истинностью или ложностью. Для истинностных значений будем использовать следующие обозначения: «1» для истинности и «0» для ложности. Введем в рассмотрение основные логические связки:
Название |
Прочтение |
Обозначение |
Отрицание |
не |
|
Конъюнкция |
и |
|
Дизъюнкция |
или |
|
Импликация |
если … то |
|
Эквиваленция |
тогда и только тогда, когда |
|
Используя логические связки, из одного или двух высказываний можно образовать новое высказывание, осуществив тем самым логическую операцию. При этом истинностные значения образованных высказываний определяются только истинностными значениями составляющих их высказываний, а не их смыслом.
Пусть
и
высказывания. Введем основные логические
операции
над высказываниями.
Название |
Обозначение |
Прочтение |
Когда высказывание, полученное в результате операции, истинно |
Когда высказывание, полученное в результате операции, ложно |
Отрицание
|
|
не |
если ложно |
если истинно |
Конъюнкция и |
|
и |
и оба истинны |
в остальных случаях |
Дизъюнкция и |
|
или |
в остальных случаях |
и оба ложны |
Импликация и |
|
если , то ( влечет , из следует ) |
в остальных случаях |
истинно, ложно |
Эквиваленция и |
|
тогда и только тогда когда ( эквивалентно ) |
и имеют одинаковые значения истинности |
в остальных случаях |
Операции удобно задавать с помощью таблиц истинности.
|
|
|
|
|
|
|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
Высказывательными
переменными
будем называть такие переменные,
значениями которых могут быть любые
высказывания. Обозначать высказывательные
переменные будем заглавными буквами
латинского алфавита
и так далее.
Выражения, содержащие логические операции, назовем формулами. Для каждой формулы можно составить таблицу истинности.
Пример
1. Составить
таблицу истинности формулы
.
|
|
|
|
|
|
|
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
Таким образом, значение истинности данной формулы равно 1 при любых значениях истинности высказывательных переменных. Формулы, обладающие таким свойством, называются тавтологиями.
Значение тавтологий
состоит, в частности, в том, что они дают
правильные способы умозаключений.
Например,
схема логического умозаключения,
выражаемого тавтологией
,
часто используется в математике и носит
название «доказательство от противного».
Упражнение. Показать, что следующие формулы являются тавтологиями:
1.
.
2. .
Определение.
Две формулы
и
алгебры высказываний называются
равносильными,
если при любых значениях истинности
переменных
истинностные значения высказываний
и
совпадают.
То, что формулы
и
равносильны, обозначают так:
.
Пример
2. Доказать
равносильность формул
и
.
Для каждой из данных формул составим таблицу истинности.
|
|
|
|
0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
|
|
|
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
Сравнивая таблицы, видим, что указанные формулы равносильны.
Существует связь
между понятием тавтологии и понятием
равносильности формул. Она заключается
в следующем: формулы
и
равносильны тогда и только тогда, когда
формула
является тавтологией.
Утверждение.
Пусть
- произвольные
высказывания.
Имеют место
равносильности:
1.
;
2.
;
3.
;
4.
;
5.
;
6.
;
7.
;
8.
;
9.
;
10.
;
11.
;
12.
;
13.
;
14.
;
15.
;
16.
;
17.
;
18.
;
19.
.
В качестве упражнения рекомендуем самостоятельно доказать перечисленные равносильности, взяв за образец решение примера 2.

(
)