double arrow

Логические операции, основные элементные базисы

x y   [&] 3(x,y) x 3(y,x) y v w = S [1]
                                   
                                   
                                   
                                   
    F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15

F0 – функция логического нуля;

F1 – конъюнкция;

F2 – запрет на х;

F3 – совпадает с переменной х;

F4 – запрет на у;

F5 – совпадает с переменной у;

F6 – исключающее или неравнозначное сложение по модулю 2;

F7 – дизъюнкция;

Все функции, начиная с F8 представляют собой инверсии предыдущих операций.

F8 = – ИЛИ-НЕ (функция Вебба);

F9 = ; F10 = ; F11 = ; F12 = ; F13 = ; F14 = ;

F15 = .

F14 – И-НЕ (функция Шеффера);

F15 – логическая единица.

Существуют различные элементные базисы для реализации логических операций, они могут быть минимальные и не минимальные. Рассмотрим четыре основных базиса:

1) Логические функции реализуются в базисе И-НЕ: .

Примеры:

а) = S(x,1) = S(x,x)



б) x&y = S(S(x,y),1) = S(S(x,y),S(x,y))



в) x y = S(S(x,1),S(y,1)) = S(S(x,x),S(y,y))



2) Базис ИЛИ-НЕ, функция Вебба: .

a) =W(x,0)=W(x,x)



б)x y=W(W(x,y),0)=W(W(x,y),W(x,y))



в) x&y = W(W(x,0),W(y,0)) = W(W(x,x),W(y,y))



3) Базис запрет+дизъюнкция: З(x,y), x y.

a) = З(1,х)

4) Алгебра Жигалкина, сложение по модулю 2 и конъюнкция: , &.

На практике в основном используют первые два базиса – «И-НЕ», «ИЛИ-НЕ». Для того чтобы представить заданное логическое выражение в базисе И-НЕ необходимо дважды проинвертировать это выражение. Нижнюю инверсию раскрывать по правилу де Моргана, если в полученном выражении уже нет дизъюнкции, то это выражение можно реализовать в базисе И-НЕ, если остались дизъюнкции, то продолжать применение двойной инверсии и правило де Моргана пока дизъюнкции не останется.

Пример: ab cd h в базисе И-НЕ: .

Для того, чтобы представить заданное логическое выражение в базисе ИЛИ-НЕ, необходимо дважды проинвертировать, про правилу де Моргана раскрыть каждую инверсию, затем раскрыть инверсии над сомножителями в последнем выражении, затем раскрыть оставшуюся большую инверсию, чтобы записать результат в базисе ИЛИ-НЕ, еще раз дважды проинвертировать последнее выражение.

Пример: ab cd h в базисе ИЛИ-НЕ: *


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: