- •Сервер Методического Обеспечения вгуэс http://abc.Vvsu.Ru
- •Введение
- •Вводная глава Метод математической индукции (мми) §1. Формулировки мми. Доказательство равенств
- •Теорема 1 (стандартный мми)
- •Пример 1
- •Доказательство
- •Глава I Алгебра высказываний §1. Основные понятия. Логические операции
- •Примеры
- •Определение 1
- •Определение 2
- •Определение 3
- •Определение 4
- •Определение 5
- •Теорема 3
- •Доказательство
- •Определение 4
- •Доказательство
- •Доказательство
- •Доказательство
- •Доказательство
- •Решение
- •Определение 3
- •Теорема 4
- •Доказательство
- •§6. Приложение алгебры высказываний к исследованию электрических двухполюсников
- •Определение 3
- •Теорема 6
- •Доказательство
- •§7. Отношение порядка Определение 1
- •Примеры
- •Определение 2
- •Теорема 3
- •Доказательство
- •Теорема 4
- •Доказательство
- •§9. Экстремальные элементы в частично упорядоченных множествах и подмножествах Определение 1
- •Пример 1
- •Пример 2
- •Пример 3
- •Определение 13
- •Определение 14
- •Теорема 15
- •Доказательство
- •Примеры обратных отображений
- •Теорема 16
- •Доказательство
- •Определение 17
- •Определение 18
- •Литература
Теорема 3
Наборов длины n из 0 и 1 существует .
Доказательство
Обозначим это количество буквой и докажем ММИ, что .
Пусть n=1. Наборов длины 1 из 0 и 1 существует 2: (0) и (1), поэтому . Базис индукции заложен.
Индуктивное предположение. Допустим, что .
Индуктивный переход. Докажем, что . В самом деле, рассмотрим какой-нибудь набор из 0 и 1 длины k, скажем . Тогда из него можно получить ровно два набора длины k+1, а именно и . Значит, наборов длины k+1 в два раза больше, чем наборов длины k, то есть . Теорема доказана.
Существует общепринятый порядок выписывания наборов длины n из 0 и 1. Начинается этот список с нулевого набора – (0,0,..,0,0). Каждый следующий набор получается из предыдущего прибавлением 1 в двоичной арифметике. Заканчивается список единичным набором – (1,1,..,1,1). Тем, кто забыл или не знает двоичной арифметики, сообщаем необходимые и самые простые равенства: 0+0=0, 0+1=1+0=1, 1+1=10.
Составим списки наборов из 0 и 1 длины 3 и длины 4:
1) 0 0 0 2) 0 0 0 0
0 0 1 0 0 0 1
0 1 0 0 0 1 0
0 1 1 0 0 1 1
1 0 0 0 1 0 0
1 0 1 0 1 0 1
1 1 0 0 1 1 0
1 1 1 0 1 1 1
1 0 0 0
1 0 0 1
1 0 1 0
1 0 1 1
1 1 0 0
1 1 0 1
1 1 1 0
1 1 1 1
Задача
Составьте список наборов длины пять.
Определение 4
Таблица истинности для высказывания имеет вид:
|
|
... |
|
|
|
0 |
0 |
... |
0 |
0 |
|
0 |
0 |
... |
0 |
1 |
|
... |
... |
... |
... |
... |
... |
|
|
... |
|
|
|
... |
... |
... |
... |
... |
... |
1 |
1 |
... |
1 |
0 |
|
1 |
1 |
... |
1 |
1 |
|
По сути дела, пример таблицы истинности был приведен в §1. Здесь же мы лишь дали необходимые обозначения и теоретические обоснования. В дальнейшем нам неоднократно придется строить таблицы истинности.
§3. Равносильные высказывания. Основные логические тождества
Определение 1
Высказывания и называются равносильными (или просто равными), если для любых наборов имеет место равенство:
Обозначим .
Другими словами, два высказывания равны, если у них совпадают таблицы истинности.
Примеры
1) .
Доказательство
|
|
|
0 |
1 |
1 |
1 |
0 |
0 |
2) .
Доказательство
|
|
|
|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
3) .
Доказательство
|
|
|
|
|
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
Приведем список основных логических равенств, которые называются логическими тождествами. Для некоторых из них приведем доказательства. Остальные рекомендуется проверить самостоятельно.
Основные логические тождества:
1) – идемпотентность дизъюнкции;
2) – идемпотентность конъюнкции;
3) – коммутативность дизъюнкции;
4) – коммутативность конъюнкции;
5) – ассоциативность дизъюнкции;
6) – ассоциативность конъюнкции;
7) – дистрибутивность конъюнкции относительно дизъюнкции;
8) – дистрибутивность дизъюнкции относительно конъюнкции.