Формы представления логических функций

Целью проектирования цифрового устройства является получение его логической функции (ЛФ) и соответствующей ей схемной реализации. ЛФ могут иметь различные формы представления: 1) словесное, 2) графическое, 3) табличное, 4) алгебраическое, 5) на алгоритмическом языке (например VHDL) и 6) схемное.

Источник: Новиков Ф.А. Дискретная математика для программистов, 2003

Функции f: à E ₂, где E ₂:= {0, 1}, называются функциями алгебры логики, или булевыми функциями, по имени Дж. Буля. Множество булевых функций от n переменных обозначим P_n, P_n:= {f | f: à E ₂}

Булевы функции двух переменных

Полнота

Класс функций F называется полным, если его замыкание совпадает с P_n:

[ F ] = P_n.

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

Теорема. Пусть заданы две системы функций:

F = { f₁, …,f_m } и G = { g₁, …, g_k }

Тогда, если система F полна и все функции из F реализуемы формулами над G, то система G также полна:

([ F ] = P_n & "i f _i = func J_i[G]) Þ [G] = P_n.

Доказательство

Пусть h – произвольная функция, h Î P_n.

Тогда [ F ] = P_n Þ h = func Á [ F ] Þ Á{ J_i//f_i} – формула на G. Следовательно, h = func J_i[G].

Система {Ú,Ù,Ø} – полная, следовательно:

1. система {Ù,Ø} полная, так как x₁ Ú x₂ = Ø (Øx₁ Ù Øx₂)
2. система {Ú,Ø} полная, так как x₁ Ù x₂ = Ø (Øx₁ Ú Øx₂)
3. система {|} полная, так как Øx = x | x, x₁ Ù x₂ = Ø (x₁ | x₂) = (x₁ | x₂) | (x₁ | x₂)
4. система {0,1, Ù, +} полная, так как Øx = x + 1 (здесь + означает сложение по модулю 2). Представление булевой функции над базисом {0,1, Ù, +} называется полиномом Жегалкина.

Источник: Карпов Ю.Г. Теория автоматов