- •Алгебра логіки
- •2.1. Алгебра Буля і алгебра логіки
- •2.2. Логічні функції однієї і двох змінних
- •2.3. Властивості елементарних логічних функцій
- •2.4. Формули в алгебрі логіки
- •2.5. Диз’юнктивні й кон’юктивні нормальні форми алгебри Буля
- •2.6. Двоїсті функції
- •2.7. Досконалі диз’юнктивні й кон’юнктивні нормальні форми
- •3.1. Поняття алгебри Жегалкіна
- •Питання для самоконтролю
- •3.2. Властивості операцій алгебри Жегалкіна
- •3.3. Многочлени Жегалкіна
- •Питання для самоконтролю
- •4.1. Поняття повної системи функцій
- •4.2. Замикання множини логічних функцій
- •4.3. Основні замкнуті класи логічних функцій
- •4.4. Критерій Поста повноти системи функцій
- •Питання для самоконтролю
- •5.1. Поняття мінімізації
- •5.2. Побудова скорочених днф
- •5. 3. Побудова тупикових днф. Метод імплікантних таблиць Квайна. Метод Петрика
- •5.4. Мінімізація на основі карт Карно
- •Питання для самоконтролю
3.2. Властивості операцій алгебри Жегалкіна
Нехай . Тоді для операцій алгебри Жегалкіна справедливі такі властивості.
1. Кон’юнкція і сума за модулем два комутативні:
;
.
2. Кон’юнкція і сума за модулем два асоціативні.
;
.
3. Кон’юнкція дистрибутивна відносно суми за модулем два:
4. Виконується закон ідемпотентності для кон’юнкції:
;
5. Виконуються властивості одиниці й нуля для кон’юнкції:
,
.
6. Виконуються властивості щодо зведення подібних і щодо нуля для суми за модулем два:
,
.
Використовуючи
таблицю істинності, покажемо справедливість
властивості 3 (дистрибутивності кон’юнкції
відносно суми за модулем два)
:
3.3. Многочлени Жегалкіна
Визначення 3.2. Многочленом (поліномом) Жегалкіна називають многочлен, який є сумою за модулем два константи і кон’юнктивних одночленів, у які кожна змінна входить не більше одного разу (тобто один раз або відсутня). Многочлен Жегалкіна ще називають многочленом за модулем два, а також алгебричною нормальною формою (АНФ).
Степенем многочлена Жегалкіна є найбільша кількість змінних, які входять у кон’юнктивні одночлени.
Визначення 3.3. Многочлен Жегалкіна називають нелінійним, якщо він містить кон’юнкції змінних; якщо ж він не містить кон’юнкцій змінних, то його називають лінійним.
Приклад
3.1.
У многочлені Жегалкіна нульового степеня
будь-які змінні відсутні; такий многочлен
дорівнює сталій — 0 чи 1:
,
.
Оскільки многочлени нульового степеня
не містять кон’юнкцій, то вони є
лінійними. Многочлен
має перший степінь — він лінійний.
Многочлен
має степінь 3, оскільки найбільша
кількість змінних входить в одночлен
і цих змінних є 3; цей многочлен нелінійний.
У
загальному вигляді многочлен Жегалкіна
логічної функції-константи (тобто
функції нуля змінних) має вигляд
;
логічної функції однієї змінної —
;
двох змінних —
;
трьох змінних —
і т.д., де коефіцієнти
.
У
многочлені Жегалкіна логічної функції
n
змінних максимально можлива кількість
доданків дорівнює
,
а всіх многочленів Жегалкіна від n
змінних може бути
.
Теоретичним обґрунтуванням алгебри Жегалкіна є наведена нижче теорема.
Теорема 3.1 (І.І. Жегалкіна). Кожну логічну функцію можна однозначно подати многочленом Жегалкіна:
,
де
,
.
Справедливість
цієї теореми випливає з таких міркувань.
Раніше було доведено теорему (теорема
2.2) про те, що будь-яку логічну функцію
можна подати у вигляді формули через
заперечення, диз’юнкцію і кон’юнкцію.
У свою чергу заперечення подається
через суму за модулем два
,
а диз’юнкція через кон’юнкцію і суму
за модулем два
.
Отже, будь-яку логічну функцію можна
подати через кон’юнкцію і суму за
модулем два. Однозначність подання є
наслідком того, що потужності множини
многочленів Жегалкіна від n
логічних змінних і множини всіх можливих
логічних функцій n
змінних однакові (рівні
).
Визначення 3.4. Логічну функцію називають лінійною, якщо її многочлен Жегалкіна не містить кон’юнкцій змінних.
Для лінійної логічної функції многочлен Жегалкіна має вигляд:
,
де коефіцієнти .
Лінійні функції В.М. Фомичов називає афінними функціями.
Існує
простий спосіб знаходження коефіцієнтів
,
,
…,
і вільного члена
многочлена Жегалкіна для довільної
логічної функції
,
відповідно до якого:
;
;
; (3.1)
.
Використовуючи формули (3.1), можна встановити, чи є задана логічна функція лінійною чи нелінійною.
Алгоритм визначення лінійності логічної функції.
1. За таблицею істинності логічної функції і формулами (3.1) треба знайти коефіцієнти , , …, і вільний член і записати лінійний многочлен Жегалкіна:
.
2.
Побудувати таблицю істинності для
і порівняти її з таблицею істинності
логічної функції
.
Якщо таблиці істинності однакові, то
є многочленом Жегалкіна для заданої
функції
і ця функція лінійна; якщо не однакові,
то функція — нелінійна.
Приклад
3.2.
Щоб визначити, чи є функція Шеффера
лінійною, запишемо її таблицю істинності:
Лінійна
частина многочлена Жегалкіна для функції
двох змінних має такий загальний вигляд:
.
Відповідно до формул (3.1) і таблиці
істинності функції Шеффера знайдемо
значення вільного члена
і коефіцієнтів
і
:
;
;
.
Отже,
.
Побудуємо
таблицю істинності для
:
Оскільки
таблиці істинності для
і для
різні, то функція Шеффера нелінійна.
Для побудови многочлена Жегалкіна довільної функції можна скористатися методом невизначених коефіцієнтів (МНК).
Алгоритм побудови многочлена Жегалкіна методом невизначених коефіцієнтів.
1.
За таблицею істинності логічної функції
і загальним виглядом многочлена Жегалкіна
треба записати систему
рівнянь відносно
невідомого вільного члена і коефіцієнтів
.
2.
Послідовно розв’язуючи одержану
систему, знайти значення вільного члена
і коефіцієнтів
,
,
…,
,
,
,
…,
,
…,
многочлена Жегалкіна.
Приклад
3.3.
Скориставшись методом невизначених
коефіцієнтів,
побудуємо многочлен Жегалкіна для
логічної функції
і дослідимо цю функцію на лінійність.
Спочатку
побудуємо таблицю істинності для заданої
функції. На
кожній
інтерпретації
в
загальний вигляд многочлена Жегалкіна
для функції трьох змінних
підставимо
значення самої функції і значення
змінних
і одержимо
систему восьми рівнянь з вісьмома
невідомими
,
,
,
,
,
,
,
:
З
першого, другого, третього і п’ятого
рівнянь маємо, що
,
,
,
.
Решта рівнянь системи набувають такого
вигляду:
звідки:
,
,
.
Останнє рівняння запишемо так:
;
з нього одержуємо, що
.
Отже, , , , , , , , і многочлен Жегалкіна для заданої функції має вигляд:
.
Оскільки
одержаний многочлен містить кон’юнкції
змінних (доданки
,
),
то задана функція нелінійна.
Цю задачу можна розв’язати й іншим способом. Враховуючи, що і , виконаємо еквівалентні перетворення:
.
Одержали той самий результат.
Крім заперечення й диз’юнкції, через кон’юнкцію і суму за модулем два можна подати й інші елементарні функції:
;
;
;
;
.
Приклад
3.4.
Використовуючи еквівалентні перетворення,
подамо логічну функцію
у вигляді многочлена Жегалкіна і
визначимо, чи є задана функція лінійною.
При проведенні перетворень скористаємося
наведеними вище тотожностями:
.
Побудований многочлен має другий степінь, і тому він не є лінійним; отже, і задана функція — нелінійна.
Приклад 3.5. Функцію подано таблицею істинності:
Подамо її у вигляді многочлена Жегалкіна. У даному випадку зручно застосувати метод невизначених коефіцієнтів. У загальний вигляд многочлена підставимо значення булевих змінних і значення функції на кожній інтерпретації, знайдемо розв’язки:
Многочлен Жегалкіна має вигляд:
,
він нелінійний, отже, задана функція — нелінійна.
