Білоруський державний університет інформатики і радіоелектроніки
Кафедра інформатики
РЕФЕРАТ
На тему:
«Переключательние функції одного та двох аргументів»
МІНСЬК, 2008
1.Переключательние функції одного аргументу.
Існує чотири переключательние функції одного аргументу, які наведені в табл. 1.
Таблиця 1
Переключательние функції одного аргументу
Функція f 0 (x) тотожно дорівнює нулю. Вона називається константою нуль і позначається f 0 (x) = 0.
Функція f 1 (x) повторює значення аргументу і тому тотожний дорівнює змінної x.
Функція f 2 (x) приймає значення, протилежні значенням аргументу: якщо x = 0, то f 2 (x) = 1; якщо x = 1, то f 2 (x) = 0. Цю функцію називають інверсією x або запереченням x і вводять для неї спеціальне позначення f 2 (x) =
Функція f 3 (x) тотожно дорівнює одиниці. Вона називається константою одиниця і позначається f 3 (x) = 1.
2. Переключательние функції двох аргументів.
Існує шістнадцять різних перемикальних функцій двох аргументів, кожна з яких визначена на чотирьох наборах. Ці функції представлені у табл. 2.
У числа шістнадцяти перемикальних функцій входять функції, розглянуті в п.1:
f 0 (x, y) = 0 - константа нуль;
f 15 (x, y) = 1 - константа одиниця;
f 3 (x, y) = x - змінна x;
f 5 (x, y) = y - мінлива y;
f 12 (x, y) =
f 10 (x, y) =
Таблиця 2
Переключательние функції двох аргументів
Розглянемо деякі переключательние функції двох аргументів.
Функція f 1 (x, y) називається кон'юнкція, чи логічним множенням. Таблиця істинності цієї функції збігається з таблицею множення двох однорозрядних двійкових чисел. Можна ввести функцію n аргументів, відповідну твору n однорозрядних двійкових чисел. Така Переключательная функція дорівнює одиниці тоді і тільки тоді, коли всі її аргументи дорівнюють одиниці. Для кон'юнкції справедливі наступні співвідношення:
x × 0 = 0;
x × 1 = x;
x × x = x;
x × y = y × x;
x ×
Функція f 7 (x, y) називається диз'юнкцією чи логічним складанням. Ця функція дорівнює нулю тільки в тому випадку, коли всі її аргументи дорівнюють нулю. Можна ввести функцію n аргументів, відповідну логічного додаванню n однорозрядних двійкових чисел. Така Переключательная функція дорівнює нулю тоді і тільки тоді, коли всі її аргументи дорівнюють нулю. Для кон'юнкції справедливі наступні співвідношення:
x Ú 0 = x;
x Ú 1 = 1;
x Ú x = x;
x Ú y = y Ú x;
x Ú
Таблиця істинності функції f 6 (x, y) збігається з таблицею складання двох однорозрядних двійкових чисел за модулем два. Можна ввести функцію n аргументів, відповідну сумі по модулю два n однорозрядних двійкових чисел. Така Переключательная функція визначається наступною умовою: вона дорівнює одиниці, якщо число аргументів, рівних одиниці, непарне, і дорівнює нулю, якщо число таких аргументів парне. Наведемо деякі співвідношення для суми по модулю два:
x Å 0 = x;
x Å 1 =
x Å x = 0;
x Å x Å x = x;
x Å y = y Å x.
Розглянуті шістнадцять функцій двох аргументів (будемо називати їх елементарними) дозволяють будувати нові переключательние функції наступним чином:
· Шляхом перенумерації аргументів;
· Шляхом підстановки у функцію нових функцій замість аргументів.
Функцію, отриману з функцій f 1, f 2, ..., f k шляхом застосування (можливо багаторазового) цих двох правил, будемо називати суперпозицією функцій f 1, f 2, ..., f k. Наприклад, маючи елементарні функції інверсії, кон'юнкції, диз'юнкції, імплікації, заборони, додавання за модулем два, можна скласти нову переключательную функцію:
f (x, y, z) = ((
Використовуючи таблиці, що визначають елементарні функції, можна задавати у вигляді таблиці будь-яку переключательную функцію, яка є суперпозицією цих функцій.
Приклад 1. Представити у вигляді таблиці функцію
f (x, y, z) = ((
Рішення. Функцію f (x, y, z) будемо представляти послідовно, записуючи в стовпці табл. 1.5 проміжні результати, які одержуються після виконання кожної операції:
Таблиця 3
Таблиця істинності функції f (x, y, z) = ((
Розглянемо переключательние функції, звані конституентами.
Визначення 1. Конституентов одиниці називають переключательную функцію n аргументів, яка приймає значення, рівне одиниці на одному єдиному наборі аргументів.
З визначення випливає, що кількість різних констітуєнт одиниці серед функцій n аргументів дорівнює 2 n. Конституенти одиниці позначаються так: K i (x 1, ..., x n), де i - номер набору, на якому конституента дорівнює одиниці. Наприклад, запис K 7 (x 1, x 2, x 3, x 4) означає функцію чотирьох аргументів, рівну одиниці на наборі (0111).
Конституента одиниці може бути виражена через кон'юнкцію всіх аргументів, кожний з яких входить у твір зі знаком заперечення або без нього. Наведену вище конституенту одиниці можна представити через кон'юнкцію аргументів наступним чином:
K 7 (x 1, x 2, x 3, x 4) =
Щоб записати у вигляді добутку конституенту K i (x 1, ..., x n), можна скористатися наступним правилом: записати n-розрядне двійкове число (n - число аргументів), рівне i, і кон'юнкцію n змінних; над змінними, місця яких збігаються з позиціями нулів у двійковому числі i, поставити знак заперечення.
Приклад 2. Записати конституенту, рівну одиниці на дванадцятому наборі для функції п'яти змінних.
Рішення. Пятіразрядное двійкове число, рівне дванадцяти, записується у вигляді: 01100. Запишемо твір п'яти аргументів, розташовуючи їх у порядку зростання індексів: x 1 × x 2 × x 3 × x 4 × x 5. Зіставляючи це твір з двійковим числом 01100, визначаємо, що знаки заперечення необхідно поставити над першим, четвертим і п'ятим аргументами:
K 12 (x 1, x 2, x 3, x 4, x 5) =
Визначення 3. Конституентов нуля називають переключательную функцію n аргументів, яка приймає значення, рівне нулю, на одному єдиному наборі аргументів.
З визначення випливає, що кількість різних констітуєнт нуля серед функцій n аргументів дорівнює 2 n. Конституенти нуля позначаються так: M i (x 1, ..., x n), де i - номер набору, на якому конституента дорівнює нулю. Конституента нуля може бути виражена через диз'юнкцію усіх аргументів, кожний з яких входить у твір зі знаком заперечення або без нього.
Щоб записати у вигляді добутку конституенту M i (x 1, ..., x n), можна скористатися наступним правилом: записати n-розрядне двійкове число (n - число аргументів), рівне i, і диз'юнкцію n змінних; над змінними, місця яких збігаються з позиціями одиниць у двійковому числі i, поставити знак заперечення.
Приклад 3. Записати конституенту нуля, рівну нулю на двадцять п'ятому наборі для функції п'яти змінних.
Рішення. Пятіразрядное двійкове число, рівне двадцяти п'яти, записується у вигляді: 11001. Запишемо диз'юнкцію п'яти аргументів, розташовуючи їх у порядку зростання індексів: x 1 Ú x 2 Ú x 3 Ú x 4 Ú x 5. Зіставляючи це твір з двійковим числом 11001, визначаємо, що знаки заперечення необхідно поставити над першим, другим і п'ятим аргументами:
M 25 (x 1, x 2, x 3, x 4, x 5) =
2. Представлення перемикача функції у вигляді полінома Жегалкина.
Теорема Жегалкина. Будь-яка Переключательная функція може бути представлена у вигляді полінома (многочлена), тобто записана у формі
f (x 1,..., x n) = а про Å a 1 x 1 Å a 2 x 2 Å ... Å a n x n Å a n +1 x 1 x 2 Å ... Å a N x 1 ... x n,
(1)
де a 0, a 1 x 1, ... a N - Константи, рівні нулю або одиниці;
Å - операція складання по модулю два.
При запису конкретної перемикача функції у вигляді многочлена коефіцієнти a 0, a 1 x 1, ... a N випадають, так як члени, при яких коефіцієнти дорівнюють нулю, можна опустити, а коефіцієнти, що дорівнюють одиниці, не писати.
Для доказу теореми Жегалкина припустимо, що задана довільна Переключательная функція п аргументів f (x 1,..., X n), що дорівнює одиниці на деякому числі наборів з номерами m 1, ... m p.
Покажемо, що Переключательная функція f (x 1,..., X n) дорівнює сумі констітуєнт одиниці, які дорівнюють одиниці на тих же наборах, що і дана функція:
f (x 1,..., x n) = K m1 Å K m2 Å. . . Å K mp. (2)
Дійсно, на кожному з наборів з номерами m 1, ... m p дорівнює одиниці тільки одна конституента, що стоїть в правій частині виразу (2), а інші рівні нулю. Отже, на цих наборах і тільки на них права частина виразу (2) приймає значення, рівне одиниці.
Для того щоб перейти від виразу (2) до виду (1), досить представити конституенти одиниці у вигляді творів і, використовуючи співвідношення
Тоді отримаємо
K i = (1 Å x 1) x 2 (1 Å x 3) x 4 x 5.
Розкриваючи дужки і приводячи подібні члени згідно з властивостями операції додавання за модулем два, отримуємо запис заданої функції у формі (1), що і доводить теорему.
Наведене доказ теореми дозволяє сформулювати правило уявлення будь-який перемикача функції у вигляді многочлена.
Щоб переключательную функцію, задану таблицею істинності, представити у вигляді полінома Жегалкина, достатньо записати функцію у вигляді суми констітуєнт одиниці, рівних одиниці на тих же наборах, на яких дорівнює одиниці задана функція. Потім всі аргументи, що входять в отримане вираз з запереченням, замінити за допомогою співвідношення
x, якщо п непарній,
x Å x Å. . . Å x = 0, якщо п парне.
Приклад 3. Представити у вигляді полінома Жегалкина функцію f 58 (x 1, x 2, x 3).
Функція f 58 (x 1, x 2, x 3) дорівнює одиниці на другому, третьому, четвертому та шостому наборах, і може бути записана у вигляді суми відповідних констітуєнт одиниці:
f 58 (x 1, x 2, x 3) = K 2 Å K 3 Å K 4 Å K 6 = 
Використовуючи співвідношення
f 58 (x 1, x 2, x 3) = (1 Å x 1) x 2 (1 Å x 3) Å (1 Å x 1) x 2 x 3 Å x 1 (1 Å x 2) (1 Å x 3) Å x 1 x 2 (1 Å x 3).
Наводячи подібні члени, остаточно знаходимо
f 58 (x 1, x 2, x 3) = x 1 Å x 2 Å x 1 x 2 Å x 1 x 3.
3. Досконала діз'юнктівная нормальна форма перемикача функції.
У загальному вигляді Переключательная функція п аргументів може бути задана таблицею істинності. Позначимо через f (i) (i = 0, ..., 2 n -1) значення функції на i-му наборі аргументів. Нагадаємо, що кожна з величин f (i) приймає значення нуль або одиниця. У відповідність i-му набору аргументів можна поставити конституенту одиниці Ki, яка приймає значення, рівне одиниці тільки на даному f (i) наборі. Помножимо кожну конституенту одиниці Ki на значення функції f (i) і розглянемо диз'юнкцію творів f i K i:
Якщо підставити у вираз (3) значення f (i), то отримаємо диз'юнкцію констітуєнт, які дорівнюють одиниці на тих же наборах, що і задана функція. Дійсно, з огляду на те, що 0 × x = 0 і 0Ú х = х, члени вираження (2), в яких коефіцієнти f (i) = 0, можна опустити, а так як x × 1 = x, то коефіцієнти f (i ) = 1 можна не писати. Тоді
де j 1, ..., j m - номери наборів, на яких функція дорівнює одиниці;
m - Число таких наборів.
Визначення 3. Диз'юнкція констітуєнт одиниці, рівних одиниці на тих же наборах, що і задана функція, називається досконалою диз'юнктивної нормальною формою перемикача функції.
Будь-яку переключательную функцію f (x 1,..., X n) (крім константи нуль) можна представити в досконалої диз'юнктивної нормальній формі. Зауважимо, що будь-яка Переключательная функція має єдину досконалу діз'юнктівную нормальну форм у: це безпосередньо випливає з виразу (3).
Досконалу діз'юнктівную нормальну форму перемикача функції зручно знаходити в такій послідовності:
· Виписати ряд творів усіх аргументів і з'єднати їх знаками диз'юнкції; кількість творів має дорівнювати числу наборів, на яких задана функція звертається в одиницю;
· Записати під кожним твором набір аргументів, на якому функція дорівнює одиниці, і над аргументами, рівними нулю, поставити знаки заперечення.
Це правило називають іноді правилом запису перемикача функції по одиницях.
Приклад 4. Представити в досконалої диз'юнктивної нормальній формі переключательную функцію чотирьох аргументів f 23805 (x 1, x 2, x 3, x 4) (див. табл. 2).
Рішення. З таблиці. 2 видно, що Переключательная функція приймає значення, що дорівнюють одиниці, на наступних наборах аргументів:
0001, 0011, 0100, 0101, 1000, 1001, 1010, 1011, 1100, 1101, 1111.
Таким чином, досконала діз'юнктівная нормальна форма функції f 23805 (x 1, x 2, x 3, x 4) буде складатися з одинадцяти диз'юнкцій, кожна з яких представляє собою кон'юнкцію чотирьох елементів:
4. Досконала Кон'юнктивна нормальна форма перемикача функції.
Якщо задана Переключательная функція дорівнює одиниці на більшості наборів аргументів, то представлення функції в досконалої диз'юнктивної нормальній формі може виявитися досить громіздким. У цих випадках зручніше використовувати іншу форму представлення функції - досконалу кон'юнктивні нормальну форму. Для представлення функцій у цій формі використовується функція конституенти нуля.
Розглянемо вираз
де f (i) - значення перемикача функції на i-му наборі.
Зважаючи справедливості співвідношень 1Ú x = 1 і 0 Ú х = х, при підстановці у вираз (4) значень функції f (i), співмножники, у яких f (i), == 1, можна опустити, а значення функції f (i) = 0 не писати . Тоді
де j 1, j 2, ..., j m -Номери наборів, на яких функція дорівнює нулю;
т - число таких наборів.
Визначення 4. Твір констітуєнт нуля, які дорівнюють нулю на тих же наборах, що і задана функція, називається досконалою кон'юнктивній нормальною формою.
Будь-яка Переключательная функція f (x 1,..., X n) (крім константи одиниці) може бути представлена в досконалої кон'юнктивній нормальній формі. Будь-яка Переключательная функція має єдину досконалу кон'юнктивні нормальну форму.
Сформулюємо правило подання перемикача функції в досконалої кон'юнктивній нормальній формі. Щоб уявити переключательную функцію п аргументів на досконалої кон'юнктивній нормальній формі, достатньо:
· Виписати твір диз'юнкцій всіх аргументів з кількістю співмножників, що дорівнює кількості наборів, на яких задана функція звертається в нуль;
· Виписати під кожним співмножником набір аргументів, на якому функція дорівнює нулю, і над аргументами, рівними одиниці, поставити знаки заперечення;
Це правило іноді називають правилом запису перемикача функції по нулях.
Приклад 5. Представити в досконалої кон'юнктивній нормальній формі функцію f 23805 (x 1, x 2, x 3, x 4) (див. табл. 2).
Рішення. З таблиці. 2 видно, що Переключательная функція приймає значення, рівні нулю, на наступних наборах аргументів:
0000, 0010, 0110, 0111, 1110.
Таким чином, досконала Кон'юнктивна нормальна форма функції f 23805 (x 1, x 2, x 3, x 4) буде складатися з п'яти кон'юнкція, кожна з яких представляє собою диз'юнкцію чотирьох елементів:
ЛІТЕРАТУРА
1. Бєлоусов А.І., Ткачов С.Б. Дискретна математика: Підручник для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: изд-во МГТУ ім. Н.Е. Баумана, 2001 .- 744 с. (Сер. Математика в технічному університеті; Вип XIX).
2. Горбатов В.А. Фундаментальні основи дискретної математики. Інформаційна математика .- М.: Наука, Фізматліт, 2000 .- 544 с .- ISBN 5-02-015238-2.
3. Зарубін В.С. Математичне моделювання в техніці: Учеб. для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: Із МГТУ ім. Н.Е. Баумана, 2001 .- 496 с. (Сер. Математика в технічному університеті; вип. XXI, заключний).
Кафедра інформатики
РЕФЕРАТ
На тему:
«Переключательние функції одного та двох аргументів»
МІНСЬК, 2008
1.Переключательние функції одного аргументу.
Існує чотири переключательние функції одного аргументу, які наведені в табл. 1.
Таблиця 1
Переключательние функції одного аргументу
f (x) | 0 | 1 | Умовне позначення | Назва функції |
| f 0 (x) | 0 | 0 | 0 | Константа нуль |
| f 1 (x) | 0 | 1 | x | Змінна x |
| f 2 (x) | 1 | 0 | Інверсія x | |
| f 3 (x) | 1 | 1 | 1 | Константа одиниця |
Функція f 1 (x) повторює значення аргументу і тому тотожний дорівнює змінної x.
Функція f 2 (x) приймає значення, протилежні значенням аргументу: якщо x = 0, то f 2 (x) = 1; якщо x = 1, то f 2 (x) = 0. Цю функцію називають інверсією x або запереченням x і вводять для неї спеціальне позначення f 2 (x) =
Функція f 3 (x) тотожно дорівнює одиниці. Вона називається константою одиниця і позначається f 3 (x) = 1.
2. Переключательние функції двох аргументів.
Існує шістнадцять різних перемикальних функцій двох аргументів, кожна з яких визначена на чотирьох наборах. Ці функції представлені у табл. 2.
У числа шістнадцяти перемикальних функцій входять функції, розглянуті в п.1:
f 0 (x, y) = 0 - константа нуль;
f 15 (x, y) = 1 - константа одиниця;
f 3 (x, y) = x - змінна x;
f 5 (x, y) = y - мінлива y;
f 12 (x, y) =
f 10 (x, y) =
Таблиця 2
Переключательние функції двох аргументів
| x | 0 | 0 | 1 | 1 | Назва функції | Позначення |
| y | 0 | 1 | 0 | 1 | ||
| f 0 (x, y) | 0 | 0 | 0 | 0 | Константа нуль | 0 |
| f 1 (x, y) | 0 | 0 | 0 | 1 | Твір (кон'юнкція) | x ∙ y; x Ùy; x & y |
| f 2 (x, y) | 0 | 0 | 1 | 0 | Функція заборони по y | x D y |
| f 3 (x, y) | 0 | 0 | 1 | 1 | Змінна x | x |
| f 4 (x, y) | 0 | 1 | 0 | 0 | Функція заборони по x | y D x |
| f 5 (x, y) | 0 | 1 | 0 | 1 | Змінна y | y |
| f 6 (x, y) | 0 | 1 | 1 | 0 | Сума по модулю 2 (логічна нерівнозначність) | x Å y |
| f 7 (x, y) | 0 | 1 | 1 | 1 | Логічне додавання (диз'юнкція) | x + y; x Ú y |
| f 8 (x, y) | 1 | 0 | 0 | 0 | Операція Пірса (стрілка Пірса) | x ¯ y |
| f 9 (x, y) | 1 | 0 | 0 | 1 | Еквівалентність (логічна рівнозначність) | x ~ y |
| f 10 (x, y) | 1 | 0 | 1 | 0 | Інверсія y | |
| f 11 (x, y) | 1 | 0 | 1 | 1 | Імплікація від y до x | y ® x |
| f 12 (x, y) | 1 | 1 | 0 | 0 | Інверсія x | |
| f 13 (x, y) | 1 | 1 | 0 | 1 | Імплікація від x до y | x ® y |
| f 14 (x, y) | 1 | 1 | 1 | 0 | Операція Шеффера (штрих Шеффера) | x ½ y |
| f 15 (x, y) | 1 | 1 | 1 | 1 | Константа одиниця | 1 |
Функція f 1 (x, y) називається кон'юнкція, чи логічним множенням. Таблиця істинності цієї функції збігається з таблицею множення двох однорозрядних двійкових чисел. Можна ввести функцію n аргументів, відповідну твору n однорозрядних двійкових чисел. Така Переключательная функція дорівнює одиниці тоді і тільки тоді, коли всі її аргументи дорівнюють одиниці. Для кон'юнкції справедливі наступні співвідношення:
x × 0 = 0;
x × 1 = x;
x × x = x;
x × y = y × x;
x ×
Функція f 7 (x, y) називається диз'юнкцією чи логічним складанням. Ця функція дорівнює нулю тільки в тому випадку, коли всі її аргументи дорівнюють нулю. Можна ввести функцію n аргументів, відповідну логічного додаванню n однорозрядних двійкових чисел. Така Переключательная функція дорівнює нулю тоді і тільки тоді, коли всі її аргументи дорівнюють нулю. Для кон'юнкції справедливі наступні співвідношення:
x Ú 0 = x;
x Ú 1 = 1;
x Ú x = x;
x Ú y = y Ú x;
x Ú
Таблиця істинності функції f 6 (x, y) збігається з таблицею складання двох однорозрядних двійкових чисел за модулем два. Можна ввести функцію n аргументів, відповідну сумі по модулю два n однорозрядних двійкових чисел. Така Переключательная функція визначається наступною умовою: вона дорівнює одиниці, якщо число аргументів, рівних одиниці, непарне, і дорівнює нулю, якщо число таких аргументів парне. Наведемо деякі співвідношення для суми по модулю два:
x Å 0 = x;
x Å 1 =
x Å x = 0;
x Å x Å x = x;
x Å y = y Å x.
Розглянуті шістнадцять функцій двох аргументів (будемо називати їх елементарними) дозволяють будувати нові переключательние функції наступним чином:
· Шляхом перенумерації аргументів;
· Шляхом підстановки у функцію нових функцій замість аргументів.
Функцію, отриману з функцій f 1, f 2, ..., f k шляхом застосування (можливо багаторазового) цих двох правил, будемо називати суперпозицією функцій f 1, f 2, ..., f k. Наприклад, маючи елементарні функції інверсії, кон'юнкції, диз'юнкції, імплікації, заборони, додавання за модулем два, можна скласти нову переключательную функцію:
f (x, y, z) = ((
Використовуючи таблиці, що визначають елементарні функції, можна задавати у вигляді таблиці будь-яку переключательную функцію, яка є суперпозицією цих функцій.
Приклад 1. Представити у вигляді таблиці функцію
f (x, y, z) = ((
Рішення. Функцію f (x, y, z) будемо представляти послідовно, записуючи в стовпці табл. 1.5 проміжні результати, які одержуються після виконання кожної операції:
Таблиця 3
Таблиця істинності функції f (x, y, z) = ((
| x | y | z | | ( | ( | (Y ® z) | (Y ® z) × x | (( |
| 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 |
3. Представлення перемикача функції у вигляді многочленів.
1. Конституенти. У п. 2 був розглянутий один з можливих способів представлення перемикача функції - завдання її у вигляді таблиці істинності. У цьому розділі будемо вирішувати зворотну задачу, а саме уявлення перемикача функції, заданої таблицею істинності, через елементарні функції, утворюють базис.Розглянемо переключательние функції, звані конституентами.
Визначення 1. Конституентов одиниці називають переключательную функцію n аргументів, яка приймає значення, рівне одиниці на одному єдиному наборі аргументів.
З визначення випливає, що кількість різних констітуєнт одиниці серед функцій n аргументів дорівнює 2 n. Конституенти одиниці позначаються так: K i (x 1, ..., x n), де i - номер набору, на якому конституента дорівнює одиниці. Наприклад, запис K 7 (x 1, x 2, x 3, x 4) означає функцію чотирьох аргументів, рівну одиниці на наборі (0111).
Конституента одиниці може бути виражена через кон'юнкцію всіх аргументів, кожний з яких входить у твір зі знаком заперечення або без нього. Наведену вище конституенту одиниці можна представити через кон'юнкцію аргументів наступним чином:
K 7 (x 1, x 2, x 3, x 4) =
Щоб записати у вигляді добутку конституенту K i (x 1, ..., x n), можна скористатися наступним правилом: записати n-розрядне двійкове число (n - число аргументів), рівне i, і кон'юнкцію n змінних; над змінними, місця яких збігаються з позиціями нулів у двійковому числі i, поставити знак заперечення.
Приклад 2. Записати конституенту, рівну одиниці на дванадцятому наборі для функції п'яти змінних.
Рішення. Пятіразрядное двійкове число, рівне дванадцяти, записується у вигляді: 01100. Запишемо твір п'яти аргументів, розташовуючи їх у порядку зростання індексів: x 1 × x 2 × x 3 × x 4 × x 5. Зіставляючи це твір з двійковим числом 01100, визначаємо, що знаки заперечення необхідно поставити над першим, четвертим і п'ятим аргументами:
K 12 (x 1, x 2, x 3, x 4, x 5) =
Визначення 3. Конституентов нуля називають переключательную функцію n аргументів, яка приймає значення, рівне нулю, на одному єдиному наборі аргументів.
З визначення випливає, що кількість різних констітуєнт нуля серед функцій n аргументів дорівнює 2 n. Конституенти нуля позначаються так: M i (x 1, ..., x n), де i - номер набору, на якому конституента дорівнює нулю. Конституента нуля може бути виражена через диз'юнкцію усіх аргументів, кожний з яких входить у твір зі знаком заперечення або без нього.
Щоб записати у вигляді добутку конституенту M i (x 1, ..., x n), можна скористатися наступним правилом: записати n-розрядне двійкове число (n - число аргументів), рівне i, і диз'юнкцію n змінних; над змінними, місця яких збігаються з позиціями одиниць у двійковому числі i, поставити знак заперечення.
Приклад 3. Записати конституенту нуля, рівну нулю на двадцять п'ятому наборі для функції п'яти змінних.
Рішення. Пятіразрядное двійкове число, рівне двадцяти п'яти, записується у вигляді: 11001. Запишемо диз'юнкцію п'яти аргументів, розташовуючи їх у порядку зростання індексів: x 1 Ú x 2 Ú x 3 Ú x 4 Ú x 5. Зіставляючи це твір з двійковим числом 11001, визначаємо, що знаки заперечення необхідно поставити над першим, другим і п'ятим аргументами:
M 25 (x 1, x 2, x 3, x 4, x 5) =
2. Представлення перемикача функції у вигляді полінома Жегалкина.
Теорема Жегалкина. Будь-яка Переключательная функція може бути представлена у вигляді полінома (многочлена), тобто записана у формі
f (x 1,..., x n) = а про Å a 1 x 1 Å a 2 x 2 Å ... Å a n x n Å a n +1 x 1 x 2 Å ... Å a N x 1 ... x n,
(1)
де a 0, a 1 x 1, ... a N - Константи, рівні нулю або одиниці;
Å - операція складання по модулю два.
При запису конкретної перемикача функції у вигляді многочлена коефіцієнти a 0, a 1 x 1, ... a N випадають, так як члени, при яких коефіцієнти дорівнюють нулю, можна опустити, а коефіцієнти, що дорівнюють одиниці, не писати.
Для доказу теореми Жегалкина припустимо, що задана довільна Переключательная функція п аргументів f (x 1,..., X n), що дорівнює одиниці на деякому числі наборів з номерами m 1, ... m p.
Покажемо, що Переключательная функція f (x 1,..., X n) дорівнює сумі констітуєнт одиниці, які дорівнюють одиниці на тих же наборах, що і дана функція:
f (x 1,..., x n) = K m1 Å K m2 Å. . . Å K mp. (2)
Дійсно, на кожному з наборів з номерами m 1, ... m p дорівнює одиниці тільки одна конституента, що стоїть в правій частині виразу (2), а інші рівні нулю. Отже, на цих наборах і тільки на них права частина виразу (2) приймає значення, рівне одиниці.
Для того щоб перейти від виразу (2) до виду (1), досить представити конституенти одиниці у вигляді творів і, використовуючи співвідношення
Тоді отримаємо
K i = (1 Å x 1) x 2 (1 Å x 3) x 4 x 5.
Розкриваючи дужки і приводячи подібні члени згідно з властивостями операції додавання за модулем два, отримуємо запис заданої функції у формі (1), що і доводить теорему.
Наведене доказ теореми дозволяє сформулювати правило уявлення будь-який перемикача функції у вигляді многочлена.
Щоб переключательную функцію, задану таблицею істинності, представити у вигляді полінома Жегалкина, достатньо записати функцію у вигляді суми констітуєнт одиниці, рівних одиниці на тих же наборах, на яких дорівнює одиниці задана функція. Потім всі аргументи, що входять в отримане вираз з запереченням, замінити за допомогою співвідношення
x Å x Å. . . Å x = 0, якщо п парне.
Приклад 3. Представити у вигляді полінома Жегалкина функцію f 58 (x 1, x 2, x 3).
Функція f 58 (x 1, x 2, x 3) дорівнює одиниці на другому, третьому, четвертому та шостому наборах, і може бути записана у вигляді суми відповідних констітуєнт одиниці:
f 58 (x 1, x 2, x 3) =
Використовуючи співвідношення
f 58 (x 1, x 2, x 3) = (1 Å x 1) x 2 (1 Å x 3) Å (1 Å x 1) x 2 x 3 Å x 1 (1 Å x 2) (1 Å x 3) Å x 1 x 2 (1 Å x 3).
Наводячи подібні члени, остаточно знаходимо
f 58 (x 1, x 2, x 3) = x 1 Å x 2 Å x 1 x 2 Å x 1 x 3.
3. Досконала діз'юнктівная нормальна форма перемикача функції.
У загальному вигляді Переключательная функція п аргументів може бути задана таблицею істинності. Позначимо через f (i) (i = 0, ..., 2 n -1) значення функції на i-му наборі аргументів. Нагадаємо, що кожна з величин f (i) приймає значення нуль або одиниця. У відповідність i-му набору аргументів можна поставити конституенту одиниці Ki, яка приймає значення, рівне одиниці тільки на даному f (i) наборі. Помножимо кожну конституенту одиниці Ki на значення функції f (i) і розглянемо диз'юнкцію творів f i K i:
Якщо підставити у вираз (3) значення f (i), то отримаємо диз'юнкцію констітуєнт, які дорівнюють одиниці на тих же наборах, що і задана функція. Дійсно, з огляду на те, що 0 × x = 0 і 0Ú х = х, члени вираження (2), в яких коефіцієнти f (i) = 0, можна опустити, а так як x × 1 = x, то коефіцієнти f (i ) = 1 можна не писати. Тоді
де j 1, ..., j m - номери наборів, на яких функція дорівнює одиниці;
m - Число таких наборів.
Визначення 3. Диз'юнкція констітуєнт одиниці, рівних одиниці на тих же наборах, що і задана функція, називається досконалою диз'юнктивної нормальною формою перемикача функції.
Будь-яку переключательную функцію f (x 1,..., X n) (крім константи нуль) можна представити в досконалої диз'юнктивної нормальній формі. Зауважимо, що будь-яка Переключательная функція має єдину досконалу діз'юнктівную нормальну форм у: це безпосередньо випливає з виразу (3).
Досконалу діз'юнктівную нормальну форму перемикача функції зручно знаходити в такій послідовності:
· Виписати ряд творів усіх аргументів і з'єднати їх знаками диз'юнкції; кількість творів має дорівнювати числу наборів, на яких задана функція звертається в одиницю;
· Записати під кожним твором набір аргументів, на якому функція дорівнює одиниці, і над аргументами, рівними нулю, поставити знаки заперечення.
Це правило називають іноді правилом запису перемикача функції по одиницях.
Приклад 4. Представити в досконалої диз'юнктивної нормальній формі переключательную функцію чотирьох аргументів f 23805 (x 1, x 2, x 3, x 4) (див. табл. 2).
Рішення. З таблиці. 2 видно, що Переключательная функція приймає значення, що дорівнюють одиниці, на наступних наборах аргументів:
0001, 0011, 0100, 0101, 1000, 1001, 1010, 1011, 1100, 1101, 1111.
Таким чином, досконала діз'юнктівная нормальна форма функції f 23805 (x 1, x 2, x 3, x 4) буде складатися з одинадцяти диз'юнкцій, кожна з яких представляє собою кон'юнкцію чотирьох елементів:
4. Досконала Кон'юнктивна нормальна форма перемикача функції.
Якщо задана Переключательная функція дорівнює одиниці на більшості наборів аргументів, то представлення функції в досконалої диз'юнктивної нормальній формі може виявитися досить громіздким. У цих випадках зручніше використовувати іншу форму представлення функції - досконалу кон'юнктивні нормальну форму. Для представлення функцій у цій формі використовується функція конституенти нуля.
Розглянемо вираз
де f (i) - значення перемикача функції на i-му наборі.
Зважаючи справедливості співвідношень 1Ú x = 1 і 0 Ú х = х, при підстановці у вираз (4) значень функції f (i), співмножники, у яких f (i), == 1, можна опустити, а значення функції f (i) = 0 не писати . Тоді
де j 1, j 2, ..., j m -Номери наборів, на яких функція дорівнює нулю;
т - число таких наборів.
Визначення 4. Твір констітуєнт нуля, які дорівнюють нулю на тих же наборах, що і задана функція, називається досконалою кон'юнктивній нормальною формою.
Будь-яка Переключательная функція f (x 1,..., X n) (крім константи одиниці) може бути представлена в досконалої кон'юнктивній нормальній формі. Будь-яка Переключательная функція має єдину досконалу кон'юнктивні нормальну форму.
Сформулюємо правило подання перемикача функції в досконалої кон'юнктивній нормальній формі. Щоб уявити переключательную функцію п аргументів на досконалої кон'юнктивній нормальній формі, достатньо:
· Виписати твір диз'юнкцій всіх аргументів з кількістю співмножників, що дорівнює кількості наборів, на яких задана функція звертається в нуль;
· Виписати під кожним співмножником набір аргументів, на якому функція дорівнює нулю, і над аргументами, рівними одиниці, поставити знаки заперечення;
Це правило іноді називають правилом запису перемикача функції по нулях.
Приклад 5. Представити в досконалої кон'юнктивній нормальній формі функцію f 23805 (x 1, x 2, x 3, x 4) (див. табл. 2).
Рішення. З таблиці. 2 видно, що Переключательная функція приймає значення, рівні нулю, на наступних наборах аргументів:
0000, 0010, 0110, 0111, 1110.
Таким чином, досконала Кон'юнктивна нормальна форма функції f 23805 (x 1, x 2, x 3, x 4) буде складатися з п'яти кон'юнкція, кожна з яких представляє собою диз'юнкцію чотирьох елементів:
ЛІТЕРАТУРА
1. Бєлоусов А.І., Ткачов С.Б. Дискретна математика: Підручник для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: изд-во МГТУ ім. Н.Е. Баумана, 2001 .- 744 с. (Сер. Математика в технічному університеті; Вип XIX).
2. Горбатов В.А. Фундаментальні основи дискретної математики. Інформаційна математика .- М.: Наука, Фізматліт, 2000 .- 544 с .- ISBN 5-02-015238-2.
3. Зарубін В.С. Математичне моделювання в техніці: Учеб. для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: Із МГТУ ім. Н.Е. Баумана, 2001 .- 496 с. (Сер. Математика в технічному університеті; вип. XXI, заключний).