- •1. Предикаты и кванторы
- •Определение
- •Примеры
- •Операции над предикатами
- •Логические операции
- •Кванторные операции
- •Примеры
- •Введение в понятие
- •Кванторы в математической логике
- •Свободные и связанные переменные
- •Операции над кванторами
- •2. Комбинаторные правила. Правило птичьих гнёзд. Правило сложения
- •Тема 2. Элементы теории множеств и комбинаторика
- •3. Общие правила комбинаторики
- •Пример 1
- •Пример 2
- •3. Правило умножения
- •4. Размещение с повторениями и без повторений
- •Количество размещений
- •Размещение с повторениями
- •Размещения без повторений
- •Где все это применяется, уже очевидно. Осталось только привести несколько хитрых примеров:
- •5. Сочетания без повторений
- •6. Сочетания с повторениями. Разбитие множеств на части
- •Определение
- •Разбиения конечных множеств
- •Примеры
- •7. Отношения. Представления и свойства отношений
- •8. Отношения эквивалентности. Связь отношений эквивалентности и разбиений множеств
- •Связанные определения
- •Примеры отношений эквивалентности
- •Факторизация отображений
- •9. Отношение эквивалентности. Связь отношений эквивалентности и разбиений множеств Отношение частичного порядка
- •10. Отношения линейного порядка Отношение линейного порядка
- •Упорядоченные множества
- •11. Логические функции. Задание и элементарные функции
- •Основные сведения
- •Нульарные функции
- •Унарные функции
- •Бинарные функции
- •Тернарные функции
- •[Править]Полные системы булевых функций Суперпозиция и замкнутые классы функций
- •Тождественность и двойственность
- •Полнота системы, критерий Поста
- •Представление булевых функций
- •Дизъюнктивная нормальная форма (днф)
- •Конъюнктивная нормальная форма (кнф)
- •Элементарные функции по Лиувиллю
- •Дифференцирование элементарных функций
- •Интегрирование элементарных функций
- •12. Дизъюнктивные нормальные формы
- •Примеры и контрпримеры
- •Построение днф Алгоритм построения днф
- •Пример построения днф
- •Переход от днф к сднф
- •13. Минимизация днф
- •14. Монотонные функции
- •Определения
- •Другая терминология
- •Свойства монотонных функций
- •Условия монотонности функции
- •15. Графы. Представления графов. Пути в графах
- •Путь и цикл в графе. Эйлеровые линии
10. Отношения линейного порядка Отношение линейного порядка
Определение 3. Бинарное отношение на множестве называется отношением линейного порядка5), если
является отношением частичного порядка;
для любых либо , либо .
Пример 5. Бинарное отношение на множестве комплексных чисел из примера 1 не является отношением линейного порядка, так как ни пара , ни не принадлежат бинарному отношению .
Пример 6. На множестве действительных чисел упорядочение 6) является отношением линейного порядка.
Упорядоченные множества
Про множество, на котором задано отношение частичного порядка, говорят, что оно частично упорядочено. Если же задано отношение линейного порядка, то множество называют линейно упорядоченным, или просто упорядоченным.
11. Логические функции. Задание и элементарные функции
Бу́лева фу́нкция (или логи́ческая функция, или функция а́лгебры ло́гики) от n переменных — в дискретной математике отображение Bn → B, где B = {0,1} — булево множество. Элементы булева множества 1 и 0 обычно интерпретируют как логические значения «истинно» и «ложно», хотя в общем случае они рассматриваются как формальные символы, не несущие определенного смысла. Неотрицательное целое число n называют арностью или местностью функции, в случае n = 0 булева функция превращается в булеву константу. Элементы декартова произведения Bn называют булевыми векторами. Множество всех булевых функций от любого числа переменных часто обозначается P2, а от n переменных — P2(n). Булевы функции названы так по фамилии математика Джорджа Буля.
Основные сведения
Каждая булева функция арности n полностью определяется заданием своих значений на своей области определения, то есть на всех булевых векторах длины n. Число таких векторов равно 2n. Поскольку на каждом векторе булева функция может принимать значение либо 0, либо 1, то количество всех n-арных булевых функций равно 22n. Поэтому в этом разделе рассматриваются только простейшие и важнейшие булевы функции. То, что каждая булева функция задаётся конечным массивом данных, позволяет представлять их в виде таблиц. Такие таблицы носят название таблиц истинности и в общем случае имеют вид:
x1 |
x2 |
… |
xn |
f(x1,x2,…,xn) |
0 |
0 |
… |
0 |
f(0,0,…,0) |
0 |
0 |
… |
1 |
f(0,0,…,1) |
0 |
1 |
… |
0 |
f(0,1,…,0) |
0 |
1 |
… |
1 |
f(0,1,…,1) |
|
|
|
|
|
1 |
0 |
… |
0 |
f(1,0,…,0) |
1 |
0 |
… |
1 |
f(1,0,…,1) |
1 |
1 |
… |
0 |
f(1,1,…,0) |
1 |
1 |
… |
1 |
f(1,1,…,1) |
Практически все булевы функции малых арностей (0, 1, 2 и 3) сложились исторически и имеют конкретные имена. Если значение функции не зависит от одной из переменных (то есть строго говоря для любых двух булевых векторов, отличающихся лишь в значении этой переменной, значение функции на них совпадает), то эта переменная называется фиктивной.