35. Некоторые эквивалентные преобразования.

1) При последовательном вхождении нескольких конъюнкций или дизъюнкций можно опускать скобки.

2) Скобки можно опускать, если они являются внешними у конъюнкции.

3) Элиминация операций.

Любая булевая функция реализуется формулой {диз., кон., отр.} mi+nj, поэтому любая присутствующая в формуле подформула с другой операцией отличной от диз., кон., отр. должна біть заменена на подформулу, содержащую базисніе операции.

4) Правило протаскивания отрицаний: используя свойство инволютивности отрицания и закон де Моргана, операция отрицания протаскивается к переменнім, поєтому в формуле – могут находиться только над переменніми.

5) Приведение подобных содержит операцию поглощения, в результате которой происходит удаление повторных вхождений одинаковых переменных входящих в каждую конъюнкцию и склеивание, при котором удаляются повторные вхождения конъюнкций в дизъюнкцию.

6) Расщепление переменных. В соответствии с этим правилом каждую конъюнкцию можно добавлять недостающие переменные, при этом не забывать добавлять дизъюнкцию, которая содержит отрицания этих переменных так, чтобы первоначальная формула не менялась. При этом формула получает вид совершенной дизъюнктивной нормальной формы.

7) Сортировка переменных. Переменные в каждой конъюнкции должны быть упорядоченными.

Для любой формулы выполняется следующая последовательность:

- успользуя законы двойного отрицания и де Моргана отрицания опускаются к переменным;

- раскрываются скобки;

- устраняются лишние конъюнкции и повторные вхождения переменных в конъюнкции;

- удаляются константы.

36. Приведение дизъюнктивной нормальной формы к совершенной дизъюнктивной нормальной форме.

Правила построения СДНФ:

1) проанализировать ф-цию:

а) определить кол-во переменных;

б) определить вид ф-ции (если ф-ция задана таблицей начений то перейти к построению, а если формулой, то получить таблицу значений ф-ции, выполняя операции по действиям);

2) построить СДНФ:

а) в таблице значений выбрать только те наборы переменных, на которых ф-ция принимает значение равное 1 и записать конъюнкции инвертируя переменны со значениями 0 и оставлять без изменения переменные со значениями 1. Каждому набору соответствует конъюнкция все переменных, таким образом между таблицей значений и СДНФ устанавливается взаимооднозначноо соответствие.

37. Замкнутые классы. Свойства замыкания.

Определение:

Множество М логических функций называется замкнутым классом, если:

1) для любой ф-ции fM любая замена переменных не выводит функцию из множества М.

2) любая суперпозиция ф-ций f1, f2 … fn  М снова принадлежит М

Всякая система F логических ф-ций пораждает некоторый замкнутый класс, а именно класс, состоящий из вех ф-ций, которые можно получить при помощи суперпозиций из F.

Замыкание F обозначают [F] называется множество всех ф-ций, реализуемых формулами над F.

1. F[F]

2. [[F]]=[F]

3. F1F2=[F1][F2]

4. [F1]  [F2]=[F1F2]

Класс ф-ций F называется замкнутым если его замыкание равно ему самому [F]=F.

Существует 5 наиболее важных замкнутых классов:

1. Класс ф-ций, сохраняющих значение 0;

2. Класс ф-ций, сохраняющих значение 1;

3. Класс самодвойственных функций;

4. Класс монотонных ф-ций;

5. Класс линейных ф-ций.