Міністерство освіти Республіки Білорусь
Установа освіти
В«Білоруський державний університет
інформатики та радіоелектроніки В»
кафедра ЕТТ
РЕФЕРАТ
На тему:
В«Функціонально повні системи логічних функцій. Алгебраїчний підхід В»
МІНСЬК, 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 2 Г™x 3 ) . (3)
Справедливість формули (5.3), а також і її більш загального випадку, коли в дужках укладена сума будь-якої кількості доданків, можна довести шляхом встановлення ідентичності умов обігу в 0 або 1 її лівої і правої частин. Умовою звернення в нуль лівій частині виразу (5.3) полягає в тому, щоб нулю дорівнював або один аргумент х 3 , або одночасно аргументи x 1 і x 2 . Умови звернення в нуль правої частини виразу (5.1) такі ж. Отже, розподільний закон 1-го роду справедливий для алгебри логіки.
2. Розподільний закон 2-го роду має вигляд
(X 2 Гљx 3 ). (4)
об'єктивно формули (4) (при будь-якому кількості аргументів) неважко довести за допомогою встановлення ідентичності умов обігу обох її частин в одиницю.
Закон інверсії (правило Де Моргана). Цей закон, так само як і всі попередні, симетричний щодо логічних додавання і множення.
1. Заперечення логічної суми декількох аргументів одно логічного добутку заперечень цих же аргументів:
(5)
Доказ закону не представляє труднощів, оскільки умова звернення в нуль як лівої, так і правої частин виразу (5) полягає в тому, щоб був істинним хоча б один аргумент.
2. Заперечення логічного твори кількох аргументів одно логічної сумі заперечень цих же аргументів:
(6)
Справедливість цього закону слід з того, що умова звернення в одиницю обох частин формули (6) полягає в тому, щоб був помилковим хоча б один аргумент.
Наслідки з законів алгебри логіки. З доведених вище законів можна вивести ряд наслідків, які сформулюємо у вигляді правил.
Правило виконання спільних логічних дій (правило старшинства логічних функцій). При вирішенні логічних завдань доводиться зустрічатися з виразами, що містять дії заперечення, кон'юнкції і диз'юнкції в будь-якому поєднанні. За аналогією з арифметичними діями будемо вважати заперечення логічним дією першого ступеня (старшої логічною операцією), кон'юнкцію - дією другого ступеня, а диз'юнкцію - дією третього ступеня (Молодшої логічною операцією).
Старшинство операції інверсії випливає із закону інверсії, у відповідності з яким логічна сума заперечень деяких аргументів не дорівнює запереченню їх суми (це справедливо і для логічного твори). Це означає, що ні операцію диз'юнкції, ні операцію кон'юнкції не можна проводити, ігноруючи знак заперечення над яким-небудь з логічних аргументів, тобто операцію заперечення треба проводити в першу чергу.
Щодо операцій логічного додавання і множення на підставі симетричності законів алгебри логіки можна сказати, що вони В«рівноправніВ». З цього випливає, що можна умовитися вважати більш старшої операцією будь-яку з них, але, прийнявши небудь умова, треба дотримуватися його весь час. На практиці виявилося зручніше вважати більш старшої операцію логічного множення, так як це відповідає правилам звичайної алгебри і для нас більш звично.
На основі викладеного можна сформулювати наступне правило виконання спільних логічних дій: якщо в логічному вираженні зустрічаються тільки дії однієї і тієї ж щаблі, то їх прийнято виконувати в тому порядку, в якому вони написані; якщо в логічному вираженні зустрічаються дії різних ступенів, то спочатку прийнято виконувати дії першого ступеня, потім - другий, і тільки після цього - третьою. Усяке відхилення від цього порядку повинне бути позначене дужками.
Правило склеювання. Перш ніж сформулювати саме правило, введемо деякі нові поняття. Якщо є деякий кінцевий набір логічних аргументів x 1 , x 2 , ... x n , то логічне твір будь-якого їх числа називається елементарним в тому випадку, коли співмножників в ньому є або одиночні аргументи, або зап...
