Математика в Internet |
Представлення функцій ДНФ, КНФ утворено трьома операціями, а саме: диз'юнкцією, кон'юнкцією та
запереченням.
В логіці Буля діє принцип суперпозиції, який стверджує: довільна складна функція може бути
представлена як сукупність елементарних функцій двох аргументів. Поставимо запитання: через які
ще системи логічних операцій можна виразити довільну булеву функцію.
Розглянемо п'ять класів булевих функцій двозмінних.
0 - клас - це функція, що зберігає нульове значення на нульовому наборі термів, тобто .
1 - клас, це функція, що зберігає константу 1 на одиничному наборі термів, тобто , до 1 класу
відносяться непарні функції.
2 - клас - клас лінійних функцій, визначаються лінійністю поліноміальної форми. Наприклад -
еквівалентність - лінійна функція.
3 - клас - клас самодвоїстих функцій; описується
формулою , таких функцій - чотири.
4 - клас - клас монотонних функцій, визначається
нерівністю , де;
Наприклад:
Для диз'юнкції, тобто диз'юнкція монотонна функція. Належність елементарних функцій до того
чи іншого класу К відмітимо на таблиці 16 .
Дана таблиця визначає систему базисних функцій.
Систему функцій називають базисною, якщо вона перекриває нулями всі рядки К-класів . З таблиці
видно, що це дві функції двох змінних (штрих Шефера та стрілка Пірса), кожна з яких може бути
застосована для побудови алгебри логіки. Всі інші функції можна отримати із них.
Таблиця 16.
П'ять класів булевих функцій | Клас | ||||||||
Поряд- ковий номер |
Табли- ця зна- чень функ- цій |
Назва функції | Симво- лічне позна- чення функції |
Представлення функції в основній алгебрі або у виді полінома |
0 | 1 | 2 | 3 | 4 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
1 | 0000 | Константа 0 | 1 | 0 | 0 | 1 | 1 | ||
2 | 1111 | Константа 1 | 0 | 1 | 0 | 1 | 1 | ||
3 | 0011 | Основна змінна | 1 | 1 | 1 | 1 | 1 | ||
4 | 0101 | Основна змінна | 1 | 1 | 1 | 1 | 1 | ||
5 | 1100 | Заперечення | 0 | 0 | 1 | 0 | 1 | ||
6 | 1010 | Заперечення | 0 | 0 | 1 | 0 | 1 | ||
7 | 1001 | Логічна рівно- значність | 0 | 1 | 0 | 0 | 1 | ||
8 | 0110 | Логічна нерівно- значність | 1 | 0 | 0 | 0 | 1 | ||
9 | 0111 | Диз'юнкція | 0 | 0 | 0 | 0 | 1 | ||
10 | 1110 | Штрих Шеффера | 0 | 0 | 0 | 0 | 0 | ||
11 | 1101 | Імплікація | 0 | 1 | 0 | 0 | 0 | ||
12 | 1011 | Імплікація | 0 | 1 | 0 | 0 | 0 | ||
13 | 0001 | Кон'юнкція | 1 | 1 | 0 | 1 | 0 | ||
14 | 0010 | Кон'юнкція | 1 | 0 | 0 | 0 | 0 | ||
15 | 0100 | Кон'юнкція | 1 | 0 | 0 | 0 | 0 | ||
15 | 1000 | Стрілка Пірса | 0 | 0 | 0 | 0 | 0 |
ЗМІСТ |