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 в базисе ИЛИ-НЕ: *