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

1 2 3 4 5 6 7

[&]

3(x,y)

3(y,x)

[1]

F₀

F₁

F₂

F₃

F₄

F₅

F₆

F₇

F₈

F₉

F₁₀

F₁₁

F₁₂

F₁₃

F₁₄

F₁₅

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

F₁ – конъюнкция;

F₂ – запрет на х;

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

F₄ – запрет на у;

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

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

F₇ – дизъюнкция;

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

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

F₉ = ; F₁₀ = ; F₁₁ = ; F₁₂ = ; F₁₃ = ; F₁₄ = ;

F₁₅ = .

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

F₁₅ – логическая единица.

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

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