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

Табличные способы задания логических функций становятся весьма громоздкими с увеличением числа аргументов. Так, уже при восьми аргументах количество строк в таблице истинности или количество клеток карты Карно равно 256. Аналитические формы представления логических функций более компактны и наглядны, и позволяют очень просто синтезировать комбинационные автоматы из ограниченного количества логических элементов, реализующих логические операции умножения (конъюнкцию), сложения (дизъюнкцию) и отрицания (инверсию). В то же время, аналитические формы логических функций позволяют выполнять различные их математические преобразования с целью получения более простых соотношений или для каких - либо других целей.

Аналитический способ предусматривает запись логической функции в форме логического выражения, показывающего, какие логические операции над аргументами должны выполняться и в какой последовательности. Сложные функции от многих аргументов могут быть представлены в форме "функций от функций", т.е. выражаться через более простые функции - от меньшего числа аргументов. Так, если z = z(x,y); x = x (a,b); y = y (c,d), то z = z (a,b,c,d). Операция замены аргументов одной функции другими, более простыми функциями носит название суперпозиции функции. Многократное использование принципа суперпозиции дает возможность получить функции желаемого числа аргументов.

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

В алгебре логики существует две самые распространенные аналитические формы представления функции: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ). Каждая логическая функция имеет одну СДНФ и одну СКНФ.

СДНФ логической функции может быть получена путем многократного применения теоремы разложения (6.25) к некоторой функции n аргументов для каждой ее переменной x_i (i=1…n). Применяя теорему разложения, получим

F (x_1, x_2,… x_n) = f(0,0,…0 )x₁ x₂…x_n +

+

(6.31)

(6.32)

f(1,0,…0 )x₁ x₂…x_n +

+

2ⁿ -1

= ∑ f_i m_i,

i=0

f(0,1,…0 )x₁ x₂…x_n +

………………………

+ f(1,1,…1 )x₁ x₂…x_n

где f_i - значение логической функции на i -ом входном наборе аргументов;

m_i - i -ый минтерм или i -ая элементарная конъюнкция максимального ранга.

Из (6.31) следует, что СДНФ логической функции — это дизъюнкция конституент единицы (минтермов), соответствующих наборам входных переменных, для которых функция равна едини­це. Совершенная дизъюнктивная нормальная форма записывается для истинного значения логической функции. В то же время относительно логической функции можно сказать, что она истинна тогда, когда не ложна. Такое утверждение можно формализовать следующим образом.

Образуем логическую функцию по ее нулевым значениям на всех входных наборах. Тогда

2ⁿ -1

= ∑ f_i m_i.

i=0

F(x_1, x_2,… x_n)

Применяя к (6.32) правило де Моргана, получим

2ⁿ -1

= ∏ (f_i + M_i),

i=0

(6.33)

F(x_1, x_2,… x_n)

88

87

где f_i - значение логической функции на i -ом входном наборе аргументов;

M_i - i -ый макстерм или i -ая элементарная дизъюнкция максимального ранга.

Представление логической функции в виде (6.33) называется совершенной конъюнктивной нормальной формой (СКНФ).

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

Рассмотрим алгоритмы перехода от табличного описания логической функции к ее аналитическому описанию (СДНФ, СКНФ).

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

1) выбрать в таблице истинности такие входные наборы, на ко­торых функции обращается в единицу;

2) по каждому такому набору составить элементарные конъюнкции максимального ранга (минтермы);

3) в минтермы записать не инвертированными переменные, заданные единицей в таблице истинности, а инвертированными - те переменные, которые в таблице истинности заданы нулем;

4) полученные минтермы соединить между собой знаками дизъюнкции.

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

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

2) по каждому такому набору составить элементарные дизъюнкции максимального ранга (макстермы);

3) в макстермы записать не инвертированными переменные, заданные нулем в таблице истинности, а инвертированными - те переменные, которые в таблице истинности заданы единицей;

4) полученные макстермы соединить между собой знаками конъюнкции.

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

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

В общем виде СДНФ и СКНФ записываются выражениями (6.32) и (6.33), которые могут быть слишком громоздкими. Для их упрощения используется более компактная числовая форма записи, предусматривающая только перечисление десятичных эквивалентов двоичных наборов, на которых функция принимает значение единицы (для СДНФ) или нуля (для СКНФ), соединив их знаками дизъюнкции (для СДНФ) и конъюнкции (для СКНФ).

Пример 6.4. Пусть логическая функция P(x,y,z) задана следующей таблицей истинности (табл. 6.3). Требуется представить ее в виде СДНФ и СКНФ.

Р ешение. По таблице истинности находим, что функция P(x,y,z) принимает единичные значения на четырех входных наборах аргументов. Данным наборам аргументов соответствуют следующие четыре минтерма: x y z, x y z, x y z, x y z.

Т

90

89

огда, в виде СДНФ данная логическая функция будет представлена в следующем виде:

P ^сднф(x,y,z) =

Таблица 6.3

По аналогии, представим данную логическую функцию в виде СКНФ. В итоге получим:

P^скнф(x,y,z) =