Функционально полные системы булевых функций

Монотонные логические функции

Линейные логические функции

Самодвойственные булевые функции

Функции сохраняющие константу единицы

Функции сохраняющие константу нуля

СВОЙСТВА ЛОГИЧЕСКИХ ФУНКЦИЙ

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

F (0, …, 0) = 0.

Таких функций существует (2 ⁿ - 1)

В таблице 2.6 они отмечены знаком +.

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

F (1, …, 1) = 1.

Таких функций существует (2 ⁿ - 1)

В таблице 2.6 они отмечены знаком +.

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

F (х₁, …, х_n) = ù F (ù х₁, …,ù х_n).

Таких функций существует 2 ⁿ

Ö 2

В таблице 2.6 они отмечены знаком +.

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

F (х₁, …, х_n) = a ₀ Å a₁ х₁ Å a₂ х₂ Å... Å a_n х_n.

Где a_i Î {0, 1}.

Таких функций существует

2 ^{( n + 1 )} .

В таблице 2.6 они отмечены знаком +.

Определение: логическая функция F (х₁, …, х_n) называется монотонной, если для любых двух наборов a = (a₁, …, a_n) и b = (b₁, …, b_n) таких, что a ³ b, существует место неравенство F (a₁, …, a_n) ³ F (b₁, …, b_n).

Двоичный набор a не меньше b, если для каждой пары (a _i, b _i), где

i Î {1, n }, справедливо a _i ³ b _i. Так 11 > 00, 11 > 10.

Вместе с тем наборы 01 и 10 или 1011 и 0100 не сравниваются между собой при определении монотонности, т.к. для них не выполняется ни a _i ³ b _i, ни b _i ³ a _i.

В таблице 2.6 они отмечены знаком +.

Таблица 2.6 – Свойства логических функций

х1

х2

F 0

F 1

F 2

F3

F 4

F5

F 6

F 7

F 8

F 9

F 10

F 11

F 12

F 13

F 14

F 15

обозн

Ù

х1 ¬ х2

х1

х2 ¬ х1

х2

Å

Ú

¯

~

ù х2

х2 ® х1

ù х1

х1 ® х2

½

сохр0

+

+

+

+

+

+

+

+

¾

¾

¾

¾

¾

¾

¾

¾

сохр1

¾

+

¾

+

¾

+

¾

+

¾

+

¾

+

¾

+

¾

+

самд

¾

¾

¾

+

¾

+

¾

¾

¾

¾

+

¾

+

¾

¾

¾

лин

+

¾

¾

+

¾

+

+

¾

¾

+

+

¾

+

¾

¾

+

мон

+

+

¾

+

¾

+

¾

+

¾

¾

¾

¾

¾

¾

¾

+

Определение: система функций å называется функционально полной, если произвольную булевую функцию F может быть записана в виде формулы через функции этой системы å.

Теорема Поста-Яблонского: для того, чтобы система булевых функций была функционально полной, необходимо и достаточно, чтобы она содержала хотя бы по одной функции

· не сохраняющей 0;

· не сохраняющей 1;

· не самодвойственной;

· не линейной;

· не монотонной.

На основании этого строятся различные алгебры:

· алгебра Пирса: включает в себя операцию стрелка Пирса;

· алгебра Шеффера: включает в себя операцию штрих Шеффера;

· алгебра Жегалкина: включает константу единицы, конъюнкцию и сложение по модулю 2;

· алгебра Буля: включает дизъюнкцию, конъюнкцию и отрицание.

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