Міністерство освіти Республіки Білорусь
Установа освіти«Білоруський державний університет
інформатики і радіоелектроніки »
кафедра ЕТТ
РЕФЕРАТ
На тему:
«Функціонально повні системи логічних функцій. Алгебраїчний підхід »
МІНСЬК, 2008
З безлічі функціонально повних наборів розглянемо тільки ті, які мають найбільше практичне значення.
1. Основна функціонально повна система логічних функцій. Найбільшого поширення одержав набір, до складу якого входять три логічні функції:
· F 10 - інверсія (логічний зв'язок НЕ, логічне заперечення);
· F 1 - кон'юнкція (логічний зв'язок І, логічне множення),
· F 7 - диз'юнкція (логічний зв'язок АБО, логічне додавання).
Цей набір отримав назву функціонально повної системи логічних функцій (ОФПС). З теореми про функціональної повноті випливає, що основна функціонально повна система логічних функцій є надмірною, так як умовам теореми відповідають набори функцій f 10 і f 1 або f 10 і f 7. Властивості цих функцій були розглянуті раніше.
З визначення уявлення перемикача функції у вигляді диз'юнктивної або кон'юнктивній нормальної форми випливає, що ці уявлення реалізуються в основний функціонально повної системи логічних функцій.
2. Закони алгебри логіки в ОФПС та їх наслідки. В алгебрі логіки є чотири основних закони, що регламентують порядок проведення операцій НЕ, І, АБО в будь-якому логічному вираженні:
· Переместительное (комутативність);
· Сочетательних (асоціативний);
· Розподільний (дистрибутивний);
· Інверсії (правило Де Моргана).
Переместительное закон. Цей закон справедливий як для диз'юнкції, так і для кон'юнкції:
x 1 Ú x 2 = x 2 Ú x 1; x 1 Ù x 2 = x 2 Ù x 1. (1)
Справедливість вираження (5.1) неважко довести простий підстановкою в нього різних значень x 1 і x 2. Оскільки будь-яку перестановку більшої кількості доданків можна звести до послідовності перестановок доданків в окремих парах, то переместительное закон буде справедливий при будь-якій кількості доданків.
Сочетательних закон. Цей закон, так само як і переместительное, є симетричним, тобто справедливим і для диз'юнкції, і для кон'юнкції:
x 1 Úx 2 Úx 3 = x 1 Ú (x 2 Úx 3) = (x 1 Úx 2) Úx 3 = x 2 Ú (x 1 Úx 3); (2)
x 1 Ùx 2 Ùx 3 = x 1 Ùx 2 Ùx 3) = (x 1 Ùx 2) Ùx 3 = x 2 Ù (x 1 Ùx 3).
Доказ цього закону також не становить жодних труднощів і може бути виконано простою підстановкою.
Розподільний закон. На відміну від звичайної алгебри алгебра логіки симетрична. У ній справедливі два розподільних закону:
для логічного множення щодо логічного складання (розподільний закон 1-го роду) і для логічного додавання щодо логічного множення (розподільний закон 2-го роду).
1. Розподільний закон 1-го роду записується таким чином:
(X 1 Úx 2) Ùx 3 = (x 1 Ùx 3) Ú (x 2 Ùx 3). (3)
Справедливість формули (5.3), а також і її більш загального випадку, коли в дужках укладена сума будь-якої кількості доданків, можна довести шляхом встановлення ідентичності умов обігу в 0 або 1 її лівої і правої частин. Умовою звернення до нуль лівій частині виразу (5.3) полягає в тому, щоб нулю дорівнював або один аргумент х 3, або одночасно аргументи x 1 і x 2. Умови звернення до нуль правій частині виразу (5.1) такі ж. Отже, розподільний закон 1-го роду справедливий для алгебри логіки.
2. Розподільний закон 2-го роду має вигляд
(X 1 Ùx 2) Úx 3 = (x 1 Úx 3) Ù (x 2 Úx 3). (4)
Cправедлівость формули (4) (при будь-якій кількості аргументів) неважко довести за допомогою встановлення ідентичності умов обігу обох її частин в одиницю.
Закон інверсії (правило Де Моргана). Цей закон, так само як і всі попередні, симетричний щодо логічних додавання і множення.
1. Заперечення логічної суми кількох аргументів одно логічного добутку заперечень цих же аргументів:
Доказ закону не становить труднощів, оскільки умова звернення в нуль як лівої, так і правої частин рівняння (5) полягає в тому, щоб був істинним хоча б один аргумент.
2. Заперечення логічного твори кількох аргументів одно логічної сумі заперечень цих же аргументів:
Справедливість цього закону випливає з того, що умова звернення в одиницю обох частин формули (6) полягає в тому, щоб був хибним хоча б один аргумент.
Наслідки з законів алгебри логіки. З доведених вище законів можна вивести ряд наслідків, які сформулюємо у вигляді правил.
Правило виконання спільних логічних дій (правило старшинства логічних функцій). При вирішенні логічних завдань доводиться зустрічатися з виразами, що містять дії заперечення, кон'юнкції і диз'юнкції в будь-якому поєднанні. За аналогією з арифметичними діями будемо вважати заперечення логічним дією першого ступеня (старшої логічною операцією), кон'юнкцію - дією другого ступеня, а диз'юнкцію - дією третього ступеня (молодшої логічною операцією).
Старшинство операції інверсії випливає із закону інверсії, відповідно до якого логічна сума заперечень деяких аргументів не дорівнює заперечення їхньої суми (це справедливо і для логічного твору). Це означає, що ні операцію диз'юнкції, ні операцію кон'юнкції не можна проводити, ігноруючи знак заперечення над яким-небудь з логічних аргументів, тобто операцію заперечення треба проводити в першу чергу.
Щодо операцій логічного додавання і множення на підставі симетричності законів алгебри логіки можна сказати, що вони «рівноправні». З цього випливає, що можна домовитися вважати більш старшої операцією будь-яку з них, але, прийнявши яка-небудь умова, треба дотримуватися його весь час. На практиці виявилося зручніше вважати більш старшої операцію логічного множення, тому що це відповідає правилам звичайної алгебри і для нас більш звично.
На основі викладеного можна сформулювати наступне правило виконання спільних логічних дій: якщо в логічному вираженні зустрічаються тільки дії однієї і тієї ж щаблі, то їх прийнято виконувати у тому порядку, в якому вони написані; якщо в логічному вираженні зустрічаються дії різних ступенів, то спочатку прийнято виконувати дії першої сходинки, потім - другий, і тільки після цього - третьою. Будь-яке відхилення від цього порядку повинне бути позначено дужками.
Правило склеювання. Перш ніж сформулювати саме правило, введемо деякі нові поняття. Якщо є деякий кінцевий набір логічних аргументів x 1, x 2, ... x n, то логічне твір будь-якого їх числа називається елементарним в тому випадку, коли співмножники в ньому є або одиночні аргументи, або заперечення одиночних аргументів. Так, наприклад, f 1 (х 1, х 2, x 3, х 4) = х 1 × х 2 × x 3 × х 4 - елементарне твір (елементарна кон'юнкція);
Символи будь-якого аргументу в елементарній кон'юнкції може зустрічатися тільки один раз, оскільки твір аргументу самого на себе одно цього ж аргументу, а твір аргументу на своє заперечення дорівнює нулю. Кількість співмножників в елементарній кон'юнкції називається її рангом.
Два елементарних твори однакового рангу r називаються сусідніми, якщо вони є функціями одних і тих же аргументів і відрізняються тільки знаком заперечення (інверсії) одного із співмножників. Наприклад, елементарні кон'юнкції
f 1 (х 1, х 2, x 3, х 4) = х 1 × х 2 × x 3 × х 4 і f 3 (х 1, х 2, x 3, х 4) =
є сусідніми, тому що відрізняються тільки однією інверсією у змінній x 2, а елементарні кон'юнкції
f 3 (х 1, х 2, x 3, х 4) =
сусідніми не є.
Правило склеювання для елементарних кон'юнкція може бути сформульовано таким чином: логічну суму двох сусідніх творів деякого рангу r можна замінити одним елементарним твором рангу r -1, що є спільною частиною вихідних доданків.
Це правило є наслідком розподільного закону 1-го роду і доводиться шляхом винесення за дужку загальної частини доданків, що є сусідніми кон'юнкції. Тоді в дужках залишається логічна сума деякого аргументу і його інверсії, що дорівнює одиниці, що й доводить справедливість правила.
Наприклад,
Оскільки алгебра логіки є симетричною, то всі визначення, дані для кон'юнкції, будуть справедливі і для диз'юнкції.
Якщо є деякий кінцевий набір логічних аргументів, то логічна сума (диз'юнкція), що залежить від будь-якого їх числа, називається елементарною в тому випадку, коли доданками в ній є або одиночні аргументи, або заперечення одиночних аргументів.
Кількість доданків в елементарній диз'юнкції називається її рангом. Дві елементарні суми однакового рангу називаються сусідніми, якщо вони є функціями одних і тих же аргументів і відрізняються тільки знаком заперечення (інверсії) одного з доданків.
Правило склеювання двох елементарних диз'юнкцій формулюється так: логічне твір двох сусідніх сум деякого рангу r можна замінити однією елементарної сумою рангу r - 1, що є спільною частиною вихідних співмножників.
Це правило є наслідком розподільного закону 2-го роду і застосовується для спрощення логічних виразів.
Наприклад:
Правило поглинання. Так само як і склеювання, поглинання може бути двох видів. Правило поглинання для двох елементарних кон'юнкція формулюється так: логічну суму двох елементарних творів різних рангів, з яких одна є власною частиною іншого, можна замінити доданком, мають менший ранг.
Це правило є наслідком розподільного закону 1-го роду. Доводиться воно, прийнявши за дужку загальної частини доданків. У дужках залишиться логічна сума деякого виразу і одиниці, що дорівнює в свою чергу також одиниці, що й доводить справедливість правила. Наприклад,
Правило поглинання для двох елементарних диз'юнкцій: логічне твір двох елементарних сум різних рангів, з яких одна є загальною частиною іншої, можна замінити співмножником, мають менший ранг.
Це правило є наслідком розподільного закону 2-го роду і теж знаходить широке застосування для спрощення логічних функцій.
Правило розгортання. Це правило регламентує чинність, зворотне склеюванню. Іноді потрібно представити деякий логічне вираження у вигляді сукупності констітуєнт одиниці або констітуєнт нуля. Якщо членами преутвореного вирази є елементарні кон'юнкції, то перехід від них до конституента одиниці виробляється в три етапи за наступним правилом:
· У розгорнутих елементарну кон'юнкцію рангу r в якості додаткових співмножників вводиться п-r одиниць, де п - ранг конституенти;
· Кожна одиниця представляється у вигляді логічної суми деякої, не наявною у вихідній кон'юнкції змінної і її заперечення:
· Проводиться розкриття всіх дужок на основі розподільного закону першого роду, що приводить до розгортання вихідної елементарної кон'юнкції рангу r в логічну суму кон-стітуент одиниці.
Приклад Розгорнути елементарну кон'юнкцію f (x 1, x 2, x 3, x 4) = = x 1 × x 3 в логічну суму констітуєнт одиниці.
Рішення. Ранг конституенти одиниці для даної функції дорівнює 4. Виробляємо розгортання вихідної кон'юнкції поетапно відповідно до правила розгортання:
1-й етап-f (x 1, x 2, x 3, x 4) = x 1 × 1 × x 3 × 1.
2-й етап - f (x 1, x 2, x 3, x 4) =
3-й етап - f (x 1, x 2, x 3, x 4) =
=
Якщо членами преутвореного вирази є елементарні диз'юнкції, то перехід від них до конституента нуля проводиться також у три етапи за наступним правилом:
· У розгорнутих елементарну диз'юнкцію рангу r в якості додаткових доданків вводиться п-r нулів;
· Кожен нуль представляється у вигляді логічного твори деякої, не наявною у вихідній диз'юнкції змінної, і її заперечення:
· Вийшло вираз перетворюється на основі розподільного закону другого роду таким чином, щоб зробити розгортання вихідної елементарної диз'юнкції рангу r в логічне твір констітуєнт нуля.
Приклад. Розгорнути елементарну диз'юнкцію f (x 1, x 2, x 3, x 4) = = x 3 Ú x 4 в логічне твір констітуєнт нуля.
Рішення. Ранг конституенти нуля п = 4. Далі виробляємо розгортання вихідної диз'юнкції поетапно відповідно до правила розгортання:
1-й етап - f (x 1, x 2, x 3, x 4) = 0 Ú 0 Ú x 3 Ú x 4;
2-й етап - f (x 1, x 2, x 3, x 4) =
3-йетап-f (x 1, x 2, x 3, x 4) =
що й потрібно було отримати.
Перевірити правильність проведених перетворень можна за допомогою правила склеювання.
3. Функціонально повні системи логічних функцій. Аналіз приналежності перемикальних функцій замкнутим класам показує, що існують дві переключательние функції f 8 і f 14, не належать ні одного класу. Згідно з теоремою про функціональної повноті, кожна з цих функцій утворює функціонально повну систему логічних зв'язків і використовуючи тільки одну з них можна представити будь-яку, як завгодно складну переключательную функцію.
Операція Пірса (стрілка Пірса) реалізує функцію, яка приймає значення, рівне одиниці тільки в тому випадку, коли всі її аргументи дорівнюють 0 (АБО-НЕ), що може бути записано в ОФПС для функції двох змінних наступним чином:
Використовуючи операції суперпозиції і підстановки можна показати, що операція Пірса може бути реалізована для n аргументів:
Для представлення перемикача функції в базисі Пірса необхідно виконати наступні дії:
· Представити переключательную функцію f у кон'юнктивній нормальній формі;
· Отриманий вираз представити у вигляді
· Застосувати правило Де Моргана.
Наприклад, для того щоб представити функцію
в базисі Пірса, необхідно виконати наступні перетворення:
Для представлення отриманого виразу в базисі Пірса скористаємося співвідношенням (7):
Операція Шеффера (штрих Шеффера) реалізує функцію, яка приймає значення, рівне нулю, тільки в тому випадку, коли всі її аргументи дорівнюють 1 (І-НЕ), що може бути записано в ОФПС для функції двох змінних наступним чином:
Використовуючи операції суперпозиції і підстановки, можна показати, що операція Пірса може бути реалізована для n аргументів:
f (x 1, x 2, ..., x n) = x 1 ½ x 2 ½ ... ½ x n =
Для представлення перемикача функції в базисі Шеффера необхідно виконати наступні дії:
· Представити переключательную функцію f у диз'юнктивній нормальній формі;
· Отриманий вираз представити у вигляді
· Застосувати правило Де Моргана.
Наприклад, для того щоб представити функцію
в базисі Шеффера, необхідно виконати наступні перетворення:
Для представлення отриманого виразу в базисі Шеффера скористаємося співвідношенням (5.9):
f (x 1, x 2, x 3, x 4) = (x 4 ½ x 2) ½ (x 3 ½ x 1).
ЛІТЕРАТУРА
1. Бєлоусов А.І., Ткачов С.Б. Дискретна математика: Підручник для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: изд-во МГТУ ім. Н.Е. Баумана, 2001 .- 744 с. (Сер. Математика в технічному університеті; Вип XIX).
2. Горбатов В.А. Фундаментальні основи дискретної математики. Інформаційна математика .- М.: Наука, Фізматліт, 2000 .- 544 с .- ISBN 5-02-015238-2.
3. Петрова В.Т. Лекції з алгебри і геометрії. Підручник для ВУЗів: в 2 ч. - К.: Гуманит. вид. центр ВЛАДОС .- ч. 1 - 312 с., ч. 2 - 344 с. ISBN 5-691-00077-2. ISBN 5-691-00238-4 (I), ISBN 5-691-00239-2 (II).
4. Зарубін В.С. Математичне моделювання в техніці: Учеб. для вузів / Під ред. В.С. Зарубіна, А.П. Крищенко .- М.: Із МГТУ ім. Н.Е. Баумана, 2001 .- 496 с. (Сер. Математика в технічному університеті; вип. XXI, заключний).