Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста (стр. 1 из 5)
Міністерство освіти і науки України
Національний університет «Львівська політехніка»
Кафедра Прикладної математики
Курсова робота
з курсу «Дискретна математика»
на тему
«Функціональна повнота системи функцій алгебри логіки. Спеціальні класи функцій алгебри логіки. Теорема Поста»
Виконала: ст. гр.ІФ-31
Мартинюк Н.О
Прийняла: Тесак І.Є
Львів – 2011р.
В роботі розглянуто поняття функціональної повноти системи функцій алгебри логіки, спеціальних класів функцій алгебри логіки, а також досліджено умови виконання теорема Поста.
В середовищі програмування С#реалізується алгоритм, який визначає чи є система функцій алгебри логіки функціонально повна, вид повноти.
Засади алгебри логіки були сформульовані британцем Джорджем Булем у 1847 році. Пізніше її розвивали Чарлз Пірс, Генрі Шеффер, П. С. Порецький, Бертран Рассел, Давид Гільберт та ін.
Відтоді ця система застосовується для вирішення широкого спектру проблем математичної логіки та теорії множин, та особливо конструювання цифрової електроніки (початок використання алгебри логіки для синтезу перемикальних (релейних) схем був покладений в 1938 році роботами відомого американського вченого Клода Шеннона).
Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями. Тобто, представлення логіки у вигляді алгебраїчної структури.
Спочатку проблематика алгебри логіки перетиналась з проблематикою алгебри множин (теоретико-множинні операції).
Проте із закінченням формування теорії множин, що відбулось в 70-тих роках 19 століття, яка включила в себе алгебру множин, і подальшим розвитком математичної логіки, предмет алгебри логіки значно змінився.
Сучасна алгебра логіки розглядає операції над висловлюваннями, як булеву функцію і вивчає відносно них такі питання, як:
-таблиці істинності;
-функціональна повнота;
-замкнені класи;
-представлення у вигляді: ДНФ, КНФ, полінома Жегалкіна.
Базовими елементами алгебри логіки є висловлювання. Висловлювання будуються над множиною {B, , , , 0, 1}, де B — булева множина, над елементами якої визначені три операції:
- заперечення (унарна операція),
- кон'юнкція (бінарна),
- диз'юнкція (логічна, бінарна),
- константи — логічний нуль 0 та логічна одиниця 1.
Функціональна повнота системи функцій алгебри логіки відіграє важливу роль в математичній логіці.
Розділ 1. Функціональна повнота системи функцій алгебри логіки
1.1. Функції алгебри логіки
Визначення. Нехай Е2={0,1} основна множина, тоді Е
={ 
}. Тоді всюди визначеною булевою функцією називаємо відображення 
. Таку функцію можна задати таблично а також як суперпозицію інших, простіших функцій. Наприклад, для n=1:Булева функція табличне зображення.
Таблиця №1
 |  |  | |  |
| 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 0 |
Функція 0 називається константою нулем, функція 1 – константою одиницею, функція х – тотожною, а функція
- запереченням х ( 
).Булевою функцією називається функція
в якій всі аргументи 
є незалежними, і сама функція є логічними змінними, що приймають лише два значення 0 та 1. Ці функції можуть бути задані аналітично, геометрично або за допомогою таблиць істинності. Всі елементарні булеві функції двох змінних представлені таблицею істинності.Таблиця істинності булевих функцій двох змінних.
Таблиця №2
| № | X= 0Y= 0 | 01 | 10 | 11 | fк (X,Y) |
| 1 | 0 | 0 | 0 | 0 |  |
| 2 | 0 | 0 | 0 | 1 |  |
| 3 | 0 | 0 | 1 | 0 |  |
| 4 | 0 | 0 | 1 | 1 |  |
| 5 | 0 | 1 | 0 | 0 |  |
| 6 | 0 | 1 | 0 | 1 |  |
| 7 | 0 | 1 | 1 | 0 |  |
| 8 | 0 | 1 | 1 | 1 |  |
| 9 | 1 | 0 | 0 | 0 |  |
| 10 | 1 | 0 | 0 | 1 |  |
| 11 | 1 | 0 | 1 | 0 |  |
| 12 | 1 | 0 | 1 | 1 |  |
| 13 | 1 | 1 | 0 | 0 |  |
| 14 | 1 | 1 | 0 | 1 |  |
| 15 | 1 | 1 | 1 | 0 |  |
| 16 | 1 | 1 | 1 | 1 |  |
Більшість із шістнадцяти булевих функцій f(x, у) часто застосовуються на практиці. Оскільки дані функції використовуються як у математиці, так і в програмуванні, вони можуть мати різне позначення.
Позначення булевих функцій та їх назви.
Таблиця №3
| Функція | Позначення | Назва |
 | 0 | константа 0 |
 |  | Кон'юнкція (логічне «і») — двомісна логічна операція, що має значення «істина», якщо всі операнди мають значення «істина». Операція відображає вживання сполучника «і» в логічних висловлюваннях.  Позначається в програмуванні як & чи and. |
 |  | заперечення імплікації |
 |  | Повторення першого аргументу |
 |   | заперечення оберненої імплікації |
 | У | Повторення другого аргументу |
 | х  у | Виключна диз'юнкція (XOR, додавання за модулем два) — двомісна логічна операція, що приймає значення «істина» тоді і тільки тоді коли значення «істина» має рівно один з її операндів. Виключна диз'юнкція є запереченням логічної еквівалентності. |
 |  | Диз'юнкція (логічне «або») — двомісна логічна операція, що має значення «істина», якщо хоча б один з операндів має значення «істина». Операція відображає вживання сполучника «або» в логічних висловлюваннях. Позначається в програмуванні як or. |
 |  | Стрілка Пірса (операція NOR) — двомісна логічна операція, яка є запереченням диз'юнкції; тому значення «істина» одержується тільки тоді, коли обидва операнди мають значення «хиба». |
 |  | Еквівалентність — двомісна логічна операція, що має значення «істина», якщо обидва операнди мають однакове значення. Операція відображає вживання сполучника «тоді і тільки тоді» в логічних висловлюваннях. |
 |  | заперечення другого аргументу |
 |  | обернена імплікація |
 |  | заперечення першого аргументу |
 |  | Імплікація – двомісна логічна операція, що має значення «хиба», тоді і тільки тоді, коли перший операнд має значення «істина», а другий — «хиба». |
 |  | Штрих Шеффера (операція NAND) — двомісна логічна операція, яка є запереченням кон'юнкції; тому значення «хиба» одержується тільки тоді, коли обидва операнди мають значення «істина». |
 | 1 | константа 1 |
1.2 Функціональна повнота