Алгоритм получения СДНФ по таблице истинности

1. Отметить те строки таблицы истинности, в последнем столбце ко­торых стоят 1:

2. Выписать для каждой отмеченной строки конъюнкцию всех пере­менных следующим образом: если значение некоторой переменной в дан­ной строке равно 1, то в конъюнкцию включать саму эту переменную, если равно 0, то ее отрицание: — для 2-й строки; — для 3-й строки.

3. Все полученные конъюнкции связать в дизъюнкцию: (1*)

(Алгоритм приведения формулы булевой функции к СДНФ)

Шаг 1. Используя алгоритм построения ДНФ, находим формулу В, являющуюся ДНФ формулы А.

Шаг 2. Вычеркиваем в B все элементарные конъюнкции, в которые одновременно входят какая-нибудь переменная и ее отрицание. Это обосновывается равносильностями:

A&A  0, B&0  0, СV0  С.

Шаг 3. Если в элементарной конъюнкции формулы B некоторая переменная или ее отрицание встречается несколько раз, то оставляем только одно ее вхождение. Это обосновывается законом идемпотентности для конъюнкции: A&A  A.

Шаг 4. Если в элементарную конъюнкцию С формулы В не входит ни переменная x, ни ее отрицание x, то на основании 1- го закона расщепления заменяем С на (С&x) V (C&x).

Шаг 5. В каждой элементарной конъюнкции формулы B переставляем конъюнктивные члены так, чтобы для каждого i (i = 1,..., n) на i-м месте была либо переменная x_i, либо ее отрицание x_i.

Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: СVС  С.