Способы задания логической функции

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

1. Формула, указывающая последовательность логических операций, которые нужно произвести над высказываниями - аргументами, чтобы получить значение функции. Например, F(X_1, X₂, X₃) = X₁× ®X_3.

2. Таблица истинности. В таблице указываются значения функции в зависимости от значений истинности аргументов. Если функция зависит от n аргументов, то число всех наборов аргументов равно 2ⁿ.

В таблице истинности указываются все наборы и значение функции на каждом наборе.

3. Числовой способ задания функции. Каждой независимой переменной-аргументу функции ставится в соответствие число 2^k (k = 0, 1, 2,...). Аргументы функции записываются в виде упорядоченного множества, например, F(X₁, X₂, X₃). При этом переменная, записанная крайней справа, получает коэффициент 2⁰ = 1, переменная, стоящая рядом слева, получает коэффициент 2¹=2 и т. д. Так, для функции F(X_1, X₂, X₃) независимые переменные получают следующие коэффициенты: X₃ -1, X₂ -2. X₁ -4. Для каждого набора независимых переменных определяется число номер N по формуле

N = 4 × X₁ + 2 × X₂ + 1 × X₃

При задании функции указывают номера тех наборов, на которых функция равна единице, и перед списком номеров единичных наборов ставят знак дизъюнкции. Можно также указать те номера наборов, на которых функция равна нулю, но при этом перед списком нулевых наборов ставят знак конъюнкции. Например, функция, заданная таблицей истинности (табл.4) может быть записана следующим образом: F(X,Y,Z) = Ú(0,1,4,7) = Ù(2,3,5,6)

Рис.18. Геометрический способ задания логической функции

Таблица 4

N	X	Y	Z	F

 

4. Геометрический способ задания логической функции. Для функции n - независимых логических переменных рассматривается единичный n - мерный куб. Вершины куба соответствуют наборам независимых переменных. Каждой вершине приписывают значение функции на соответствующем наборе. На рисунке единичные наборы помечают, например, кружками. (рис.18).

5. Логическая схема, представляющая собой условное графическое обозначение логических функций. На рис.19 показаны графические обозначения некоторых элементарных логических функций. На рис.20 показан пример логической схемы.

 

 

Рис.19. Графические обозначения элементарных логических функций.

 

 

Рис.20. Логическая схема.

 

 

3.4. Конституенты единицы и нуля. Составление логической формулы по

таблице истинности

Конъюнкция любого количества различных независимых переменных, входящих в нее в утвердительной или инверсной форме не более одного раза, называется элементарной конъюнкцией. Например, ABC , X, Y. Выражения (A+B)C, ABC , не являются элементарными конъюнкциями.

Дизъюнкция любого количества различных независимых переменных, входящих в нее в утвердительной или инверсной форме не более одного раза, называется элементарной дизъюнкцией. Например, A+B+C+D, A+B. Выражения AB+C+D, +C, A+ +B не являются элементарными дизъюнкциями.

Пусть задана некоторая логическая функция n независимых переменных F(X₁,X_2,...,X_n). Элементарная конъюнкция, в которую входят все n независимые переменные, называется конституентой единицы.

Элементарная дизъюнкция, в которую входят все n независимые переменные, называется конституентой нуля.

Очевидно, для функции n независимых переменных общее число всех конституент единицы также как и общее число всех конституент нуля равно 2ⁿ.

Пример. Для функции трех переменных F(X₁,X₂,X₃) выпишем все конституенты единицы и все конституенты нуля.

Конституенты единицы: X₁X₂X₃, ₁X₂X₃, X_{1 2}X₃, X₁X_{2 3}, _{1 2}X₃, ₁X_{2 3}, X_{1 2 3}, _{1 2 3.}

Конституенты нуля: X₁+X₂+X₃, ₁+X₂+X₃, X₁+ ₂+X₃, X₁+X₂+ ₃, ₁+ ₂+X₃, ₁+X₂+ ₃, X₁+ ₂+ ₃, ₁+ ₂+ _3.

 

Каждая конституента единицы равна единице лишь на одном, вполне определенном наборе значений переменных. Для каждого набора имеется своя конституента, принимающая значение 1 на этом наборе и значение 0 на всех остальных наборах. Например, конституента единицы _{1 2}X₃ равна единице на наборе X₁ = 0, X₂ = 0, X₃ = 1.

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

Рассмотрим функцию F(X₁,X₂,...,X_n). Пусть K_m1, K_m2,...,K_mi конституенты единицы, которые равны единице на наборах m₁, m₂,... m_i, совпадающих с единичными наборами функции. Рассмотрим выражение

F(X₁,X₂,...,X_n) = K_m1+K_m2+...,+K_mi. (1)

Покажем, что (1) есть тождество. Действительно, на каждом из наборов с номерами m₁, m₂,... m_i равна единице только одна конституента, стоящая в правой части (1), а остальные равны нулю. Следовательно, на этих наборах и только на них правая часть (1) принимает значение, равное единице. Но на этих же наборах и левая часть (1) равна единице, а на остальных она равна нулю. Следовательно, выражение (1) есть тождество. Отсюда следует правило записи формулы булевой функции по заданной таблице истинности.

Чтобы булеву функцию, заданную таблицей истинности, представить в виде дизъюнкции ее конституент единицы, нужно составить дизъюнкцию тех конституент единицы, которые равны единице на тех же наборах, что и данная функция. При этом, если в наборе, для которого F=1, какая-либо переменная равна единице, то ее нужно записать в конституенте единицы в утвердительной форме, если какая-либо переменная равна нулю, то ее нужно записать в конституенте единицы с отрицанием. Такая форма записи логической функции называется - совершенная дизъюнктивная нормальная форма (СДНФ).

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

Чтобы булеву функцию, заданную таблицей истинности, представить в виде конъюнкции ее конституент нуля нужно составить конъюнкцию тех конституент нуля, которые равны нулю на тех же наборах, что и данная функция. При этом, если в наборе, для которого F=0, какая-либо переменная равна единице, то ее нужно записать в конституенте нуля с отрицанием, если какая-либо переменная равна нулю, то ее нужно записать в утвердительной форме. Такая форма записи логической функции называется - совершенная конъюнктивная нормальная форма (СКНФ).

Пример. Рассмотрим функцию, таблица истинности которой приведена в табл.4. Для этой функции СДНФ и СКНФ имеют вид:

F = СДНФ

CКНФ.

 

Полином Жегалкина

.

Советский ученый Жегалкин И.И. (1869-1947) разработал систему логического счисления, основанную на использовании элементарных логических функций конъюнкции, суммы по модулю два и константы 1.

Покажем, что любую логическую функцию можно представить в виде суммы по модулю два всех ее конституент единицы. Действительно, пусть функция имеет конституенты единицы K_m1, K_m2,...,K_mi. Рассмотрим выражение

F = K_m1 Å K_m2 Å... Å K_mi. (2)

Это выражение аналогично СДНФ (1) и отличается лишь тем, что операции дизъюнкции заменены операциями суммы по модулю 2. Такая замена не нарушает тождества, т.к. на каждом из наборов с номерами m₁, m₂,..., m_i равна единице только одна конституента, стоящая в правой части (2), а остальные равны нулю. Но для суммы по модулю 2 справедливы соотношения:

0 Å 0 Å... Å 0 =0; 0 Å 1 = 1.

Следовательно (2) также как и (1) является тождеством.

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

 

F(X₁,X₂,...,X_n) = A₀ Å A₁X₁ Å A₂X₂ Å... Å A_nX_n Å A_n1X₁X₂ Å A_n2X₁X₃ Å... Å ÅA_NX₁X₂...X_n

 

где A₁, A₂,... A_N константы, равные 0 или 1. При записи конкретной логической функции коэффициенты не пишут, т.к. если A_i=0, то A_iF=0, если A_i=1, то A_iF=F.

Чтобы произвольную логическую функцию представить в виде полинома Жегалкина нужно записать ее в виде суммы по модулю 2 всех ее конституент единицы, затем все аргументы, входящие в полученное выражение с отрицанием, заменить на основании соотношения = X Å 1, раскрыть скобки и привести подобные члены с учетом тождества

X Å X Å... Å X =

если n нечетно, если n четно,

где n - количество слагаемых.

 

Пример. Рассмотрим функцию, заданную таблицей 3.

F = Å Y Å XY = (1 Å X)(1 Å Y) Å (1 Å X)Y Å XY=

=1 Å X Å Y Å XY Å Y Å XY Å XY = 1 Å X Å XY.