Спецiальнi класи та функцiональна повнота системи функцiй алгебри логiки. Теорема Поста
Мiнiстерство освiти i науки Украiни
Нацiональний унiверситет ВлЛьвiвська полiтехнiкаВ»
Кафедра Прикладноi математики
Курсова робота
з курсу ВлДискретна математикаВ»
на тему
ВлФункцiональна повнота системи функцiй алгебри логiки. Спецiальнi класи функцiй алгебри логiки. Теорема ПостаВ»
Виконала: ст. гр.РЖФ-31
Мартинюк Н.О
Прийняла: Тесак РЖ.РД
Львiв тАУ 2011р.
В роботi розглянуто поняття функцiональноi повноти системи функцiй алгебри логiки, спецiальних класiв функцiй алгебри логiки, а також дослiджено умови виконання теорема Поста.
В середовищi програмування С# реалiзуiться алгоритм, який визначаi чи i система функцiй алгебри логiки функцiонально повна, вид повноти.
Вступ
Засади алгебри логiки були сформульованi британцем Джорджем Булем у 1847 роцi. Пiзнiше ii розвивали Чарлз Пiрс, Генрi Шеффер, П. С. Порецький, Бертран Рассел, Давид Гiльберт та iн.
Вiдтодi ця система застосовуiться для вирiшення широкого спектру проблем математичноi логiки та теорii множин, та особливо конструювання цифровоi електронiки (початок використання алгебри логiки для синтезу перемикальних (релейних) схем був покладений в 1938 роцi роботами вiдомого американського вченого Клода Шеннона).
Алгебра логiки (Булева логiка, двiйкова логiка, двiйкова алгебра) тАФ роздiл математичноi логiки, що вивчаi систему логiчних операцiй над висловлюваннями. Тобто, представлення логiки у виглядi алгебраiчноi структури.
Спочатку проблематика алгебри логiки перетиналась з проблематикою алгебри множин (теоретико-множиннi операцii).
Проте iз закiнченням формування теорii множин, що вiдбулось в 70-тих роках 19 столiття, яка включила в себе алгебру множин, i подальшим розвитком математичноi логiки, предмет алгебри логiки значно змiнився.
Сучасна алгебра логiки розглядаi операцii над висловлюваннями, як булеву функцiю i вивчаi вiдносно них такi питання, як:
-таблицi iстинностi;
-функцiональна повнота;
-замкненi класи;
-представлення у виглядi: ДНФ, КНФ, полiнома Жегалкiна.
Базовими елементами алгебри логiки i висловлювання. Висловлювання будуються над множиною {B, , , , 0, 1}, де B тАФ булева множина, над елементами якоi визначенi три операцii:
- заперечення (унарна операцiя),
- кон'юнкцiя (бiнарна),
- диз'юнкцiя (логiчна, бiнарна),
- константи тАФ логiчний нуль 0 та логiчна одиниця 1.
Функцiональна повнота системи функцiй алгебри логiки вiдiграi важливу роль в математичнiй логiцi.
Роздiл 1. Функцiональна повнота системи функцiй алгебри логiки
1.1. Функцii алгебри логiки
Визначення. Нехай Е2={0,1} основна множина, тодi Е
={
}. Тодi всюди визначеною булевою функцiiю називаiмо вiдображення 
. Таку функцiю можна задати таблично а також як суперпозицiю iнших, простiших функцiй. Наприклад, для n=1:
Булева функцiя табличне зображення.
Таблиця №1
Вместе с этим смотрят:
РЖнварiантнi пiдпростори. Власнi вектори i власнi значення лiнiйного оператора
Актуальные проблемы квантовой механики
Алгебра и алгебраические системы
Анализ эмпирического распределения
Аналитическая теория чисел. L-функция Дирихле