Дискретная математика и алгоритмы — различия между версиями
(Удалено содержимое страницы) |
|||
| Строка 1: | Строка 1: | ||
| − | + | == Отношения == | |
| + | *Определение отношения | ||
| + | *Степень отношений | ||
| + | *[[Рефлексивное отношение|Рефлексивное отношение. Антирефлексивное отношение.]] | ||
| + | *[[Симметричное отношение]] | ||
| + | *[[Антисимметричное отношение]] | ||
| + | *[[Композиция отношений|Композиция отношений. Обратное отношение]] | ||
| + | *[[Транзитивное отношение]] | ||
| + | *[[Транзитивное замыкание|Транзитивное замыкание отношения]] | ||
| + | *Теорема об эквивалентности двух определений транзитивного замыкания | ||
| + | *[[Алгоритм Флойда — Уоршелла|Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения]] | ||
| + | == Булевы функции == | ||
| + | *[[Определение булевой функции]] | ||
| + | *[[Примеры булевых функций|Примеры булевых функций: все функции от нуля, одной и двух переменных]] | ||
| + | *Подстановка одной функции в другую, отождествление переменных | ||
| + | *Представление функции формулой, полные системы функций | ||
| + | *[[СДНФ]] | ||
| + | *[[СКНФ]] | ||
| + | *[[Полином Жегалкина]] | ||
| + | *[[Теорема Поста о полной системе функций]] | ||
| + | *[[Сокращенная и минимальная ДНФ]] | ||
| + | *[[Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно]] | ||
| + | *[[Специальные формы КНФ|Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома]] | ||
| + | *[[Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина]] | ||
Версия 00:42, 14 октября 2010
Отношения
- Определение отношения
- Степень отношений
- Рефлексивное отношение. Антирефлексивное отношение.
- Симметричное отношение
- Антисимметричное отношение
- Композиция отношений. Обратное отношение
- Транзитивное отношение
- Транзитивное замыкание отношения
- Теорема об эквивалентности двух определений транзитивного замыкания
- Алгоритм Флойда-Уоршалла построения транзитивного замыкания отношения
Булевы функции
- Определение булевой функции
- Примеры булевых функций: все функции от нуля, одной и двух переменных
- Подстановка одной функции в другую, отождествление переменных
- Представление функции формулой, полные системы функций
- СДНФ
- СКНФ
- Полином Жегалкина
- Теорема Поста о полной системе функций
- Сокращенная и минимальная ДНФ
- Минимизация ДНФ с помощью покрытий гиперкуба и карт Карно
- Специальные формы КНФ: КНФ в форме Хорна и КНФ в форме Крома
- Преобразование Мёбиуса для получения коэффициентов полинома Жегалкина
