Совершенная конъюнктивная и дизъюнктивная нормальные формы

Любая булева функция может иметь много представлений в виде ДНФ и КНФ. Особое место среди этих представлений занимают совершенные ДНФ (СДНФ) и совершенные КНФ (СКНФ).

Совершенная дизъюнктивная нормальная форма (СДНФ) – это ДНФ, в которой в каждый конъюнктивный одночлен каждая переменная x_i из набора x₁,x₂,…,x_n входит ровно один раз, причем входит либо сама x_i , либо ее отрицание .

Совершенная конъюнктивная нормальная форма (СКНФ) – это КНФ, в которой в каждый дизъюнктивный одночлен каждая переменная x_i из набора x₁,x₂,…,x_n входит ровно один раз, причем входит либо сама x_i , либо ее отрицание .

Существуют следующие теоремы:

Произвольную булеву функцию f(x₁,x₂,…,x_n) можно задать формулой f(x₁,x₂,…,x_n)=˅(), где дизъюнкция берется по всем τ=(τ₁, τ₂, …, τ_n), где f(τ)=1 , а x_i=x_i , если τ_i=1 и x_i= , если τ_i=0.

Произвольную булеву функцию f(x₁,x₂,…,x_n) можно задать формулой f(x₁,x₂,…,x_n)=(), где конъюнкция берется по всем =(), где f(τ)=0 , а x_i=x_i , если =0 и x_i= , если =1.

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

Пример:

x1	x2	x3	f(x1,x2,x3)
0	0	0	0
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	0
1	1	1	0

Функция принимает значение 1 на наборах 001, 010, 101. Набору 001 по теореме соответствует элементарная конъюнкция ˄˄x₃ , набору 010 соответствует конъюнкция ˄x₂˄ и набору 101 – конъюнкция x₁˄˄x₃. Напомним, что для каждого набора из нулей и единиц τ₁, τ₂, τ₃ выписываем конъюнкцию , причем, еслиτ_i=1, то соответствующая переменная x_i входит в конъюнкцию без отрицания. Получаем СДНФ f(x₁,x₂,x₃) =(˄˄x₃)˅(˄x₂˄)˅(x₁˄˄x₃) .

Построим теперь СКНФ для данной функции.

Функция принимает значение 0 на наборах 000, 011, 100, 110 и 111. Согласно второй теореме, набору 000 соответствует дизъюнкция x₁˅x₂˅x₃, набору 011 – дизъюнкция x₁˅˅, набору 100 – дизъюнкция ˅x₂˅x₃, набору 110 – дизъюнкция ˅˅x₃, и, наконец, набору 111 соответствует дизъюнкция ˅˅. Таким образом, получаем СКНФ: f(x₁,x₂,x₃)=(x₁˅x₂˅x₃)˄(x₁˅˅)˄(˅x₂˅x₃)˄(˅˅x₃)˄(˅˅).

В данной формуле раскроем скобки, используя законы дистрибутивности и поглощения: f(x₁,x₂,x₃)= (˄x₂˄)˅(˅x₃). Таким образом, мы получили минимальную ДНФ.

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

1. Находим числа k, r, удовлетворяющие условиям 2^k-1< m ≤ 2^k , 2^r-1< n ≤ 2^r, где m – количество символов входного алфавита, n – размерность пространства состояний конечного автомата. Очевидно, что k и r соответственно, равны числу разрядов в двоичном представлении чисел m и n. В частности, если m=2 и n=3, то k=1 и r=2.

2. Каждому q_i из Q={q₁, q₂, …, q_n} взаимно-однозначно ставим в соответствие двоичную последовательность длины r – двоичный код β(q_i)=y₁y₂ … y_r . Аналогично каждому a_i∑ ставим взаимно-однозначно в соответствие двоичные последовательности γ(a_i)=x₁x₂ … x_k . Отметим, что кодирование состояний, входных символов можно провести многими способами. При этом некоторые последовательности (коды) могут оказаться неиспользованными.

3. Составляем следующую таблицу:

Код входного символа

Код текущего состояния

Код следующего состояния

x1

x2

…

xk

y1

y2

…

yr

=φ1

=φ2

…

=φr

0

0

…

0

0

0

…

0

γ1

γ2

…

γk

β1

β2

…

βr

…

1

1

…

1

1

1

…

1

Эта таблица содержит k+r+r столбцов и 2^k+r строк. В первых k+r столбцах выписаны все наборы длины k+r. Каждый такой набор соответствует паре (γ, β), где β – возможный код некоторого состояния, γ – код входного символа.

4. Заполнение последних столбцов таблицы. По таблице автомата или диаграмме Мура определяем φ(a, q_i)=. Затем находим соответствующий код β()=… .

5. Определяем систему булевых функций. После выполнения предыдущего пункта может оказаться, что не все строки в таблице заполнены. Это произойдет, если хотя бы одно из чисел m, n не является степенью два. Таким образом, функции переходов окажутся не полностью определенными – на некоторых наборах их значения не определены. Мы их можем доопределить произвольным образом. Как правило, доопределенные функции производят так, чтобы получившиеся полностью определенные функции удовлетворяли тем или иным условиям оптимальности, например, представлялись минимальными ДНФ.

Вернемся теперь к микроволновой печке. В разработанной нами модели алфавит включает два символа, т.е. m=2 и, следовательно, k=1. Автомат принимает три состояния n=3, а значит, r=2. Пусть значение 0 обозначает событие ”Get the door”; а значению 1 сопоставим событие ”Press the button”. Состояния автомата будут описываться словами {00, 01, 10, 11}. Состоянию FoodInOut сопоставим слово 00, состоянию Stop сопоставим слово 01 и, наконец, состоянию Cooking слово 10. Функции будут не полностью определенными, поскольку слову 11 не сопоставляем никакого состояния. Теперь, согласно построенной нами таблице и диаграмме Мура построим таблицу конечного автомата на основе булевых функций.

x	y1	y2	=φ1	=φ2
0	0	0	0	1
0	0	1	0	0
0	1	0	0	0
0	1	1	1*	1*
1	0	0	0	0
1	0	1	1	0
1	1	0	1	0
1	1	1	1*	1*

В таблице символами* отмечены наборы переменных, на которых функции φ не определены. Положим значения функции на этих наборах равными 1.

Построим СКНФ этой функции. Функция φ₁ принимает значения 0 на наборах 000, 001, 010, 100. Следовательно, элементарные дизъюнкции имеют вид: x˅y₁˅y₂, x˅y₁˅, x˅˅y₂ и ˅y₁˅y₂. Тогда φ₁=(x˅y₁˅y₂)˄(x˅y₁˅)˄(x˅˅y₂)˄(˅y₁˅y₂). Используя закон дистрибутивности и поглощения, получаем минимальную ДНФ φ₁=(x˄y₁)˅(x˄y₂)˅(y₁˄y₂). Аналогично строим СКНФ для функции φ₂=(x˅y₁˅)˄(x˅˅y₂)˄(˅y₁˅y₂)˄(˅y₁˅)˄(˅˅y₂). Минимальная ДНФ равна φ₂=(y₁˄y₂)˅(˄˄).

Канонические уравнения автомата

Если в момент времени t= 1,2, .. на вход автомата (∑, Q, φ, q₀ , F) последовательно подаются входные сигналы ∑(t) ={a₁, a₂, …, a_m}и при этом автомат находится в состоянии q(t)Q, то под воздействием символа a(t) автомат перейдет в новое состояние q(t+1)Q. Тогда функцию перехода можно записать следующим образом:

q(t+1)= φ(a(t), q(t)).

Эти уравнения называются каноническими уравнениями автомата второго рода. Состояние системы в каждый такт однозначно определяется состоянием системы и поданным в нее сигналом в предыдущий такт.

Возможна модель, когда состояние автомата в каждый такт определяется поданным на нее сигналом в данный такт и состоянием системы в предыдущий такт:

q(t+1)= φ(a(t+1), q(t)).

Эти уравнения называются каноническими уравнениями автомата первого рода.

Канонические уравнения микроволновой печки можно тогда записать следующим образом:

y₁(t+1)=(x(t)˄y₁(t))˅(x(t)˄y₂(t))˅(y₁(t)˄y₂(t));

y₂(t+1)=(y₁(t)˄y₂(t))˅((t)˄(t)˄(t)).

P.S. Понятие «конечный автомат» охватывает и те конечные системы, состояния которых определяются предысторией любой наперед заданной конечной длины. Однако, оно не охватывает системы с бесконечной предысторией. Можно рассматривать системы, которые помнят свои состояния и поступившие сигналы в предыдущее моменты времени. На самом деле, класс конечных автоматов, которые «помнят» конечное число предыдущих тактов, не шире класса систем, помнящих лишь предыдущий такт.

16