N-арная операция

Def. Функцией алгебры логики (двузначной, булевой) от N переменных называется

Логические(булевы) ф-ии как n-арные операции.

Аd =‹B, Ù, Ú, ù, ®, ~› (® - "если, то", ~ - "тогда и только тогда")

В= {0,1}-,булево множество.

Замечание: |Bⁿ| = 2ⁿ f:Bⁿ -› B f (x, x₂, x_n)

Пример: устройство, фиксирующее принятие некоторой резолюции "комитета трех" реализует булеву функцию трех переменных, когда каждый член комитета при голосовании нажимает свою кнопку и в том случае, если большинство членов

согласно, то резолюция принята и отображается регистрирующим устройством

x	y	z	f(x,y,z)

0 0 1 1

0 1 0 1

f(x,y,z)= x y z Ú x y z Ú x y z Ú xyz;

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

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

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 j₀ (x) j₁ j₂ j₃

j₀ - тождественный ноль для констант

j - тождественная единица

j₁ - функция повторения

j₂ - функция отрицания (инверсия)

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

X₂ à

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

f0

Ù

à

¬

Ú

¯

~

ù

¬

ù

®

½

f1

Назв.     Пе- рем.

Конст. ноль

Конъюнкция

Запрет Х1 т

Повторение Х1

Запрет Х2

Повторение Х2

Сложение по мод. 2

Дизъюнкция   к

Стрелка Пирса

Эквивалентность

Отрицание Х2

Импликация Х2иХ1

Отрицание Х1

Импликация

Штрих Шеффера

Константа 1

X1

X2

j0

j1

j2

j3

j4

j5

j6

j7

j8

j9

j10

j11

j12

j13

j14

j15

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

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

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

j₁(X₁,X_{2) =} X₁

j₃(X₁,X₂) = X1 j₀ = 0

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

j₁₀(X₁,X₂) =X₂

j₁₂(X₁,X₂) =X₁

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

j₁(X₁,X₂)= j₁₄(X₁,X₂)

1) j₀ = j₁₅ j₀ = j₁₅ , т.к. 0=1 0 =1

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

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

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

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

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

4) j₆(X₁,X₂)= j₉(X₁,X₂)– функция равнозначности, эквивалентность

ИЛИ – НЕ

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

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

5) j₁₃(X₁,X₂)= j₂(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Ú х₂)- КНФ (т.к. присутствует элементарная дизъюнкция).

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

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

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

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

xy Ú xy Ú xy - СДНФ

В этой формуле присутствуют элементарные конъюнкции второго ряда (в ВТ называемые минтермами).

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

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

x	y	z	f(x,y,z)
			1 Ú
			1 Ú
			1 Ú
			1 Ú

Дата добавления: 2014-01-06