Бинарные функции

При n = 2 число булевых функций равно 2^2² = 2⁴ = 16.

Таблица значений булевых функций от двух переменных:

x

y

x ↓ y

x ← y

x̅

x → y

y̅

x ⊕ y

x | y

x & y

x ≡ y

y

x → y

x

x ← y

x ∨ y

2.1.5 Основные булевы тождества.

1) (ассоциативность)

2) (коммутативность)

3) (свойство нуля)

4) (закон поглощения для 1)

5) (ассоциативность)

6) (коммутативность)

7) (свойство нуля по умножению)

8) (свойство нейтральности 1 по умножению)

9) (дистрибутивность)

10) (дистрибутивность 2)

11) (закон поглощения)

12) (Законы

13) де Моргана)

14) (закон снятия двойного отрицания)

15) (tertium non datur – третьего не дано)

16) (ассоциативность)

17)

18)

19)

20)

21) (Свойства

22) идемпотентности)

Совершенные нормальные формы (СДНФ и СКНФ) записи булевых выражений

Совершенной дизъюнктивной нормальной формой (СДНФ) называют наиболее полную форму записи логического выражения. Эта форма записи представляет собой сумму, каждое слагаемое которой является произведением всех входных аргументов или их инверсий, например: F = `A`В`С + `А В`С + А В`С + А В С. СДНФ является избыточной, но логические функции, записанные в СДНФ, легко сравнивать между собой, их удобно преобразовывать в таблицы истинности и составлять по ним карты Карно. Булево выражение, полученное из таблицы истинности логической функции, имеет совершенную дизъюнктивную нормальную форму. В некоторых случаях более удобной формой записи логического выражения является совершенная конъюнктивная нормальная форма (СКНФ). Это произведение сомножителей, каждый из которых является суммой всех входных аргументов или их инверсий, например: F = (`А + В +`С) (`А + В + С) (А +`В + С) (А + В + С). Так же, как и СДНФ, СКНФ является явно избыточной.

Билет 15