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