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

Пример решения инженерных задач, связанных с булевыми уравнениями

x y z = x

y

z

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

Куб со стороной 1 представляет функцию трех переменных.

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

Булева формула – это способ представления логической функции (булева функция)

Формула использует три действия - , , 

Функция – 5 действий: __, +,, , ~

В этом случае используются комбинационные таблицы для представления N – местной логической функции в этой таблице все наборы данных N, упорядоченные как двоичные числа. Мощность множества

2ⁿ

всех логических функций, задаваемых таблично равна 2,

так как каждая логическая функция может рассматриваться как 2ⁿ - мерный вектор нулей 0 и единиц 1.

Кортеж ‹ 1…… 1 › представляет наибольший номер логической функции в таблице.

Замечание: если для обработки логических функций на ЭВМ размерность таблицы может быть как угодно большой, то для ручного ввода используют число элементов не больше 3.

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

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

В связи с важностью применения в ВТ функций одной и 2-х переменных рассмотрим их подробно.

а) элемент логической функции

X f (X) f: B  B

2¹

Логическая функция 1 переменной 4 = 2

Число кортежей 2ⁿ n=1

X _(x)___

_тождественный ноль для констант

 тождественная единица

_ функция повторения

_ функция отрицания (инверсия)

X₁  f (X₁,X₂) f: B2 B, B ={ 0,1 }

X₂ 

Логических функций 2-х переменных шестнадцать, среди них можно найти логическую функцию (стрелка Пирса, штрих Шеффера) и несколько логических функций, которые образуют полную систему (в том смысле, что любую логическую функцию 2-х аргументов можно представить как суперпозицию этих функций)

Пояснение: среди представленных 16 логических функций фактически зависят от 2-х аргументов лишь 10, остальные или

константы (const) или являются функциями повторения переменных,

или их отрицания.

_(X₁,X_{2) =} X₁

_(X₁,X₂) = X1 ₀ = 0

₅(X₁,X₂) = X₂ ₁₅ = 1

_(X₁,X₂) =X₂

_(X₁,X₂) =X₁

Из таблицы следует зависимость между функциями:

_(X₁,X₂)=_(X₁,X₂)

1)₀ = ₁₅ ₀ = ₁₅ , т.к. 0=1 0 =1

2) X₁  X₂ = X_{1 /} X₂ ; где  - конъюнкция, или логическое умножение

Штрих Шеффера – антиконъюнкция (Не И)

3) ₇ = ₈ дизъюнкция или логическое сложение

X_1 X₂ = X_{1 } X₂ Стрелка Пирса – антидизъюнкция (не ИЛИ)

Вебба, Даггера

4)_(X₁,X₂)=_(X₁,X₂)– функция равнозначности, эквивалентность

ИЛИ – НЕ

X₁  X₂ = X_{1 ~} X₂

Неравнозначность (исключающее ИЛИ); или сумма по модулю 2

5) _(X₁,X₂)=_(X₁,X₂) Запрет Х₁

X₁  X₂ = X_{1 } X₂ Импликация эквивалентна выражению " если, то"

6) X₁ ~ X₂ = (X₁  X₂ )(X₁  X₂ ) = X_{1 } X₂

X₁ ~ X₂ = X₁ X_{2 } X₁ X₂ = (X_{1 } X₂ ) (X_{1 } X₂ )

X₁  X₂ = X_{1 } X₂

X₁  X₂ = X₁ X_{2 } X₁ X₂ = (X_{1 } X₂ ) (X_{1 } X₂ )

X₁ / X₂ = X₂ X₁ = X_{1 } X₂

X₁ / X₂ = X_{1 } X₂ = X₂ X₁

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

 P ~ o  t =  P(o  t) V P (o  t) =  P(o t  o t)  P ((o  t) (o  t))

Важность элементарных логических функций в алгебре логики

обусловлена тем, что с помощью их и операторов суперпозиции

можно построить следующие выражения.

Y= f ₁(X₁,X₂); X₂ = f₂(X₃, ₄); Y = f (X₁; f₂(X_3,4)

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

Нормальной формой представления логических функций являются следующие формы:

ДНФ КНФ СДНФ СКНФ

а ) ДНФ - дизъюнктивная нормальная форма (дизъюнкция элементарных конъюнкций)

n m

ДНФ   Ci, j, где Сi,j переменная или отрицание переменной (i =1,n; j = 1,m)-

i =1; j =1

ДНФ выполнима тогда и только тогда, когда при некотором U () среди всех элементарных конъюнкций не встречается одновременно формулы вида Р и  P

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

Примеры

1) х₁х_2 х₁ х₂ х₃

х₁х_3 х₂х_3 х₁х₃

Это примеры ДНФ, т.к. здесь присутствует элементарная конъюнкция.

2) х₁х₂х_3 х₁х₃ – не ДНФ, т.к. присутствует

неэлементарная конъюнкция (х₁х₂= х_1 х₂)

б) КНФ - конъюнктивная нормальная форма (конъюнкция элементарных дизъюнкций)

n m

КНФ   Ci, j, где Сi,j - переменная или отрицание переменной, -

i =1; j =1

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

для каждой переменной P_i, то КНФ выполнима. Для всякой логической формулы можно построить эквивалентную ей КНФ, содержащую те же переменные.

Пример:

(х_1 х_2 х₃) (х_1 х₂)- КНФ (т.к. присутствует элементарная дизъюнкция).

Каноническое представление логических функций:

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

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

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