Головна |
Система булевих функцій {f1, f2, ..., Fm} Називається повною, якщо будь-яка булева функція може бути виражена через функції f1, f2, ..., Fm за допомогою суперпозиції.
нехай К0= {F1(x1, ...,xk1), F2(x1, ...,xk2), ..., Fm(x1, ...,xkm)} - Кінцева система булевих функцій. функція f називається елементарної суперпозицией (суперпозицією рангу 1) функцій f1, f2, ..., Fm, якщо f може бути отримана одним із таких способів:
а) перейменуванням деякої змінної xj який-небудь функції fi;
б) підстановкою деякої функції замість якої-небудь змінної xj будь-який з функцій .
Суперпозиції рангу 1 утворюють клас функцій К1. Клас функцій, що виходить з функцій класу Ks-1 суперпозицией рангу s-1 за допомогою елементарних суперпозиций, називається класом функцій Ks суперпозиций рангу s. Суперпозиціями функцій з К0 називаються функції, що входять в якийсь із класів Ks.
Згідно з введеними визначень, можна говорити, що система булевих функцій сповнена. Тоді будь-яку булеву функцію можна представити у вигляді многочлена від своїх змінних.
У сучасному комп'ютері цифрами є нуль і одиниця. Отже, команди, які виконує процесор, суть булеві функції. Ми вже бачили, що будь-яка булева функція реалізується через кон'юнкцію, диз'юнкцію і заперечення. Отже, можна побудувати потрібний процесор, маючи в розпорядженні елементи, що реалізують . Далі розглянемо питання: чи існують (і якщо існують, то які) інші системи булевих функцій, що володіють тим властивістю, що з їх допомогою можна виразити всі інші функції. Розглянемо деякі замкнуті класи (класи Посту), їх п'ять.
1. Клас функцій, що зберігають константу нуль (позначається T0 або P0):
T0: = {F | f (0,0, ..., 0) = 0}.
До цього класу належать, наприклад, функції ; ; ; .
2. Клас функцій, що зберігають константу одиниця (позначається T1 або P1):
T1: = {F | f (1,1, ..., 1) = 1}.
До нього відносяться всі непарні функції.
3. Клас самодвоїстих функцій (позначається T* або S):
T*: = {F | f*};
приклад и .
функція називається двоїстої по відношенню до функції , якщо . Подвійна функція виходить з вихідної при заміні значень всіх змінних, а також значень функції на протилежні, т. Е. В таблиці істинності потрібно замінити 0 на 1, 1 на 0.
Приклад. Двоїстої до функції є функція, що відповідає формулі , Т. Е. або : . аналогічно , .
принцип подвійності:
якщо ,
то .
Таким чином, функція, двоїста суперпозиції функцій, є відповідна суперпозиція двоїстих функцій.
Цей принцип зручний при знаходженні двоїстих функцій, представлених формулами, що містять лише кон'юнкції, диз'юнкції і заперечення. В цьому випадку у вихідній формулі кон'юнкції замінюються на диз'юнкції, а диз'юнкції - на кон'юнкції. Таким чином, ДНФ відповідає КНФ, КНФ - ДНФ, СДНФ - СКНФ, СКНФ - СДНФ.
Приклад. ,
якщо , То і .
функція називається самодвоїстих, якщо .
Приклад. Покажемо, що формула задає самодвоїстих функцію.
Переконаємося, що на всіх протилежних наборах значень змінних и формула приймає протилежні значення. Дійсно, складемо таблицю істинності:
x | y | z | |
отримуємо , , , .
4. Клас монотонних функцій (позначається TM або M):
, де , , , .
5. Клас лінійних функцій (позначається TL або L):
.
Еквівалентність є лінійною функцією . Стрілка Пірса - немає, .
, , , ..., ,
т. е.
, , ..., . (7)
Таким чином, перевірка лінійності зводиться до знаходження коефіцієнтів за формулами (7) і порівняно таблиць істинності цієї формули і отриманої формули .
Приклад. Перевіримо, чи є лінійної функція . маємо , , . Таким чином, . Зіставляючи таблиці істинності формул и , Переконуємося, що вони не збігаються. Висновок: функція нелінійна.
Лінійність функції можна також визначити за допомогою наступної теореми.
Теорема Жегалкина. Будь-яка булева функція представима полиномом Жегалкина, т. е. у вигляді , Де в кожному наборі (i1, ..., Ik) Усе ij різні, а підсумовування ведеться по деякому безлічі таких незбіжних наборів. Подання булевої функції у вигляді полінома Жегалкина єдино з точністю до порядку доданків.
Поліном Жегалкина називається нелінійним (лінійним), якщо він (не) містить твори змінних.
Таким чином, лінійність булевої функції рівносильна лінійності відповідного полінома Жегалкина.
Для отримання полінома Жегалкина булевої функції, що знаходиться в СДНФ, використовуються аксіоми булевої алгебри, аксіоми булева кільця і рівності, які виражають операції через операції цього булева кільця: і т.д.
Приклад. Визначимо лінійність функції .
маємо
Отриманий поліном Жегалкина є нелінійним, і, отже, функція f також нелінійна.
Зауважимо, що якщо в еквівалентності формули є різними констітуентамі одиниці, то їх твір дорівнює 0, і тоді . Отже, для отримання полінома Жегалкина з СДНФ можна відразу замінити .
Відзначимо, що кожен клас Посту замкнутий щодо операцій заміни змінних і суперпозиції, т. Е. З допомогою цих операцій з функцій, що належать даному класу, можна отримати тільки функції з цього ж класу.
Приклад. Визначимо, до яких класів Посту відноситься булева функція .
Так як f (0,0) = 1, а f (1,1) = 0, то и . оскільки , то . Так як f (0,0)> f (1,1), то . Поліном Жегалкина для функції має вигляд в силу рівності . Тому дана функція нелінійна. Таким чином, можна скласти таку таблицю
Таблиця функцій
функція | класи | ||||
Р0 | Р1 | S | М | L | |
х | у | немає | немає | немає | немає | немає |
Теорема Поста. система F булевих функцій тоді і тільки тоді є повною, коли для кожного з класів P0, P1, S, M, L в системі F знайдеться функція, яка не належить цьому класу.
В силу теореми Поста функція х | у утворює повну систему, т. е. з допомогою штриха Шеффера можна отримати будь-яку булеву функцію. Зокрема, .
Система булевих функцій називається базисом, Якщо вона сповнена, а видалення будь-якої функції з цієї системи робить її неповною.
Теорема. Кожен базис містить, не більше чотирьох булевих функцій.
Доведення. Припустимо, що існує базис F, Що складається більш ніж з чотирьох функцій. По теоремі Посту тоді отримуємо, що F складається рівно з п'яти функцій, кожна з яких не належить рівно одного класу Посту. нехай f - Функція з F, Яка не належить класу Р0. Тоді, з одного боку, f (0,0, ..., 0)= 1, а, з іншого - з випливає, що f (1,1, ..., 1)= 1. Це означає, що f не є самодвоїстих функцією, що суперечить припущенню.
Приклад. Наступні системи булевих функцій є базисами: .
Таблиця 7
обгрунтування | базис |
; Отже, | {І, НЕ} - кон'юнктивний базис |
; Отже, | {АБО, НЕ} - диз'юнктивний базис |
; | {І, , 1} - базис Жегалкина |
; Отже, ; | {|} - Базис Шеффера |
; Отже, ; | { } - Базис Пірса |
Приклад.
Кон'юнкції, тобто всі функції виду , Теж становлять замкнутий клас. Очевидно, однак, що, наприклад, функцію, яка на наборі (0,0, ..., 0) має значення 1, не можна уявити суперпозицией таких функцій. Таким чином, {І} не є базисом, отже, кон'юнктивний базис {І, НЕ} є мінімальним.
Розглянемо більш докладно базис Жегалкина.
Дискретна математика | Введення в алгебру логіки | Основні функції алгебри логіки | Формули алгебри логіки | Закони алгебри логіки і наслідки з них | Логічні функції багатьох змінних | Методи мінімізації логічних функцій | Неповністю певні логічні функції | Бінарні діаграми рішень (БДР) | Побудова логічних схем |