Спеціальні класи та функціональна повнота системи функцій алгебри логіки. Теорема Поста

Міністерство освіти і науки України

Національний університет «Львівська політехніка»

Кафедра Прикладної математики

Курсова робота

з курсу «Дискретна математика»

на тему

«Функціональна повнота системи функцій алгебри логіки. Спеціальні класи функцій алгебри логіки. Теорема Поста»

Виконала: ст. гр.ІФ-31

Мартинюк Н.О

Прийняла: Тесак І.Є

Львів – 2011р.

В роботі розглянуто поняття функціональної повноти системи функцій алгебри логіки, спеціальних класів функцій алгебри логіки, а також досліджено умови виконання теорема Поста.

В середовищі програмування С# реалізується алгоритм, який визначає чи є система функцій алгебри логіки функціонально повна, вид повноти.

Вступ

Засади алгебри логіки були сформульовані британцем Джорджем Булем у 1847 році. Пізніше її розвивали Чарлз Пірс, Генрі Шеффер, П. С. Порецький, Бертран Рассел, Давид Гільберт та ін.

Відтоді ця система застосовується для вирішення широкого спектру проблем математичної логіки та теорії множин, та особливо конструювання цифрової електроніки (початок використання алгебри логіки для синтезу перемикальних (релейних) схем був покладений в 1938 році роботами відомого американського вченого Клода Шеннона).

Алгебра логіки (Булева логіка, двійкова логіка, двійкова алгебра) — розділ математичної логіки, що вивчає систему логічних операцій над висловлюваннями. Тобто, представлення логіки у вигляді алгебраїчної структури.

Спочатку проблематика алгебри логіки перетиналась з проблематикою алгебри множин (теоретико-множинні операції).

Проте із закінченням формування теорії множин, що відбулось в 70-тих роках 19 століття, яка включила в себе алгебру множин, і подальшим розвитком математичної логіки, предмет алгебри логіки значно змінився.

Сучасна алгебра логіки розглядає операції над висловлюваннями, як булеву функцію і вивчає відносно них такі питання, як:

-таблиці істинності;

-функціональна повнота;

-замкнені класи;

-представлення у вигляді: ДНФ, КНФ, полінома Жегалкіна.

Базовими елементами алгебри логіки є висловлювання. Висловлювання будуються над множиною {B, , , , 0, 1}, де B — булева множина, над елементами якої визначені три операції:

- заперечення (унарна операція),

- кон'юнкція (бінарна),

- диз'юнкція (логічна, бінарна),

- константи — логічний нуль 0 та логічна одиниця 1.

Функціональна повнота системи функцій алгебри логіки відіграє важливу роль в математичній логіці.

Розділ 1. Функціональна повнота системи функцій алгебри логіки

1.1. Функції алгебри логіки

Визначення. Нехай Е₂={0,1} основна множина, тоді Е={}. Тоді всюди визначеною булевою функцією називаємо відображення . Таку функцію можна задати таблично а також як суперпозицію інших, простіших функцій. Наприклад, для n=1:

Булева функція табличне зображення.

Таблиця №1