Математика в Internet

ОСНОВИ ДИСКРЕТНОГО АНАЛІЗУ.
Автори: Н.Д.Федоренко,В.В.Демченко

     3.13. ДЕЯКІ КЛАСИ БУЛЕВИХ ФУНКЦІЙ

      Представлення функцій ДНФ, КНФ утворено трьома операціями, а саме: диз'юнкцією, кон'юнкцією та запереченням. В логіці Буля діє принцип суперпозиції, який стверджує: довільна складна функція може бути представлена як сукупність елементарних функцій двох аргументів. Поставимо запитання: через які ще системи логічних операцій можна виразити довільну булеву функцію.

Розглянемо п'ять класів булевих функцій двозмінних.

0 - клас - це функція, що зберігає нульове значення на нульовому наборі термів, тобто .

1 - клас, це функція, що зберігає константу 1 на одиничному наборі термів, тобто , до 1 класу відносяться непарні функції.

2 - клас - клас лінійних функцій, визначаються лінійністю поліноміальної форми. Наприклад - еквівалентність - лінійна функція.

3 - клас - клас самодвоїстих функцій; описується формулою , таких функцій - чотири.

4 - клас - клас монотонних функцій, визначається нерівністю , де;

      Наприклад:

Для диз'юнкції, тобто диз'юнкція монотонна функція. Належність елементарних функцій до того чи іншого класу К відмітимо на таблиці 16 .

Дана таблиця визначає систему базисних функцій.

Систему функцій називають базисною, якщо вона перекриває нулями всі рядки К-класів . З таблиці видно, що це дві функції двох змінних (штрих Шефера та стрілка Пірса), кожна з яких може бути застосована для побудови алгебри логіки. Всі інші функції можна отримати із них.


Таблиця 16.
П'ять класів булевих функцій Клас
Поряд-
ковий
номер
Табли-
ця зна-
чень
функ-
цій
Назва функції Симво-
лічне
позна-
чення
функції
Представлення функції
в основній алгебрі
або у виді полінома
01234
12345678910
10000Константа
0
10011
21111Константа
1
01011
30011Основна
змінна
11111
40101Основна
змінна
11111
51100Заперечення 00101
61010Заперечення 00101
71001Логічна
рівно-
значність
01001
80110Логічна
нерівно-
значність
10001
90111Диз'юнкція 00001
101110Штрих
Шеффера
00000
111101Імплікація 01000
121011Імплікація 01000
130001Кон'юнкція 11010
140010Кон'юнкція 10000
150100Кон'юнкція 10000
151000Стрілка
Пірса
00000




ЗМІСТ