Пример. Следствие 4. Конъюнктивное разложение булевой функции по всем переменным

Следствие 4. Конъюнктивное разложение булевой функции по всем переменным.

Следствие 3. Конъюнктивное разложение булевой функции по одной переменной.

Любую булеву функцию можно представить в следующей форме .

Запись означает, что конъюнкция берется по всем значениям , то есть по 0 и по 1. Запись обозначает значение функции на наборе , где вместо значения переменной подставлено .

Любую булеву функцию можно представить в следующей форме:.

Запись означает, что конъюнкция берется по всем наборам значений , на которых .

Запишем конъюнктивное разложение функции по всем переменным.

Определим значение функции на каждой интерпретации:

,

,

,

,

,

,

,

.

Запишем формулу, используя следствие 4 теоремы о разложении функций

.

СКНФ функции является результатом конъюнктивного разложения функции по всем переменным.

Переход от табличного представления функции к алгебраическому представлению функции. Любая таблично заданная функция алгебры логики может быть представлена в виде

или в виде

,

где - элементарная конъюнкция ранга (конституента единицы);

- номера наборов, на которых функция равна 1, а функция равна 0;

- символ обобщенной дизъюнкции;

- элементарная дизъюнкция ранга (конституента нуля);

- символ обобщенной конъюнкции.

Для перехода от таблицы истинности булевой функции к СДНФ можно воспользоваться следующим алгоритмом:

а) выделить в таблице истинности все интерпретации, на которых значение функции равно единице;

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

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

Дата добавления: 2014-10-22