Алексеев В. Б. - Дискретная математика - Сокращённая дизъюнктивная функция. Полные системы

Лемма 1 11:26

Пусть и заданы своими сокращенными ДНФ:

Рассмотрим следующий алгоритм, если :
Прежде всего рассмотрим равенство:

Прежде всего упростим выражение в 2 этапа, пока это возможно:

  1. Упростим по правилам: , , , и получим формулу
  2. Продолжаем упрощать , используя , и получим формулу
    Так, мы получаем сокращенную ДНФ функции

Лемма 2 19:56

Пусть — простая импликанта ФАЛ . Тогда она также и простая импликанта

Лемма 3 27:05

Пусть — простая импликанта ФАЛ . Тогда она также и простая импликанта

Лемма 4 30:58

В содержатся только простые импликанты

Лемма 5 38:56

Пусть . Тогда правая часть — сокращенная ДНФ ФАЛ

Сам метод Нельсона 50:32

Метод Нельсона

Для строим какую-нибудь КНФ (например, СКНФ). Она будет иметь вид . Затем постепенно раскрываем скобки, при каждом раскрытии делая упрощение по Лемме 1 до упора. Так мы получаем рекурсивный алгоритм для поиска сокращенных ДНФ 53:07

Полные системы 55:06

Полная система 55:21

Множество ФАЛ называется полной системой, если любую ФАЛ можно выразить формулой над множеством

Лемма о полноте системы

Лемма 1 57:37

Система является полной
Очевидно следует из ДНФ

Эта лемма полезна тем, что доказывать факт того, что какая-либо система является полной теперь можно сведением задачи к доказательству того, что через систему можно выразить конъюнкцию, дизъюнкцию и отрицание

Чтобы доказать, что полная, нужно доказать, что уже полную систему можно выразить через 1:01:20

Другие полные системы

  1. 1:07:15
  2. 1:09:13
  3. 1:11:00
  5. 1:13:08

Попробуем развить дальше систему (5)

Полиномы Жегалкина

Монотонная конъюнкция 1:17:22

Монотонной конъюнкцией над переменными называют либо , либо произведение из различных переменных без отрицания
Для ФАЛ из переменных существует ровно монотонных конъюнкций

Полином Жегалкина 1:18:47

Полиномом Жегалкина над переменными называется либо , либо сумма по модулю 2 () из различных монотонных конъюнкций над переменными

Существование и единственность полинома Жегалкина 1:22:20

может быть представлена полиномом Жегалкина, причем единственным образом

Interactive Graph
Table Of Contents
Алексеев В. Б. - Дискретная математика - Сокращённая дизъюнктивная функция. Полные системы
Лемма 1 11:26
Лемма 2 19:56
Лемма 3 27:05
Лемма 4 30:58
Лемма 5 38:56
Сам метод Нельсона 50:32
Полные системы 55:06
Лемма о полноте системы
Другие полные системы
Полиномы Жегалкина