Вероятностные автоматы

Разложение функций на конституенты и переход от табличного задания функции к аналитическому

Правила преобразования

правило коммутативности

правило ассоциативности (сочетательный закон)

правило дистрибутивности (распределительный закон)

- правило де Моргана.

Þ

Þ

Рассмотрим, как можно перейти от табличного задания алгебры логики к аналитическому заданию. Для этого сначала определим понятия нормальных форм.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция конечного числа различных членов, каждый из которых представляет собой конъюнкцию отдельных переменных или их отрицаний, входящих в данный набор не более одного раза, например, .

Конъюнктивной нормальной формой (КНФ) называется конъюнкция конечного числа различных членов, каждый из которых представляет собой дизъюнкцию отдельных переменных или их отрицаний, входящих в данный набор не более одного раза, например, .

Приведение булевых соотношений к нормальной форме проводится следующим образом:

- с помощью законов де Моргана формулы преобразуются к такому виду, чтобы знаки отрицания относились только к отдельным переменным:

- на основе законов дистрибутивности формула сводится к дизъюнкции конъюнкций или конъюнкции дизъюнкций;

- полученное выражение далее упрощается.

Пример 1. Преобразовать выражение к ДНФ.

Решение. С помощью законов де Моргана преобразуем конъюнкцию последних двух членов:

.

После раскрытия вторых скобок получим:

.

После раскрытия всех скобок выражение приводится к окончательному виду:

.

Полученное выражение является ДНФ.

Если в каждом члене нормальной формы представлены все переменные либо в прямом, либо в инверсном виде, то такая нормальная форма называется совершенной нормальной формой:

- СДНФ,

- СКНФ.

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

Пример 2. Привести к СДНФ: .

Решение. Введем недостающий член и получим ответ:

.

Пример 3. Привести к СКНФ: .

Решение. Также как и в предыдущем примере введем н6едостающий член:

.

С учетом после преобразований получим искомый вид СКНФ:

.

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

Например, конституенте единицы соответствует набор 0100. При этом наборе в входят только единицы, что обеспечивает равенство =1, при других значениях переменных = 0.

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

Например, конституенте нуля соответствует набор 1011. При этом наборе в входят только нули, что обеспечивает равенство = 0, при других значениях переменных = 1.

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

Аналогично, так как булева функция, представленная в виде СКНФ является конъюнкцией конституент нуля, то она обращается в нуль только при наборах значений переменных, соответствующих конституентам нуля, а на остальных наборах значений эта функция принимает значение единицы.

Обратное утверждение также справедливо, что дает возможность сформулировать правила перехода от табличного представления функции к аналитическому:

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

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

Пример 4. Имеем табличное представление функции (табл. 1.6.2).

Таблица 1.6.2

Для СДНФ запишем конституенты единицы:

, , , , .

Тогда функция в виде СДНФ будет равна:

.

Для СКНФ запишем конституенты нуля:

, , .

Функция в виде СКНФ будет иметь вид:

.

Для практической реализации надо брать ту совершенную форму, которая содержит меньше конституент, так как это позволяет реализовать логическое устройство с меньшим количеством элементов.

Недостатки способа перехода от табличного задания к аналитическому через конституенты:

- громоздкость (требуются дальнейшие преобразования);

- эти преобразования не указывают, как доопределять функцию, если функция неопределенна на всех наборах.