МІНІСТЕРСТВО освіти и науки України
Національний університет В«Львівська політехнікаВ»
Кафедра Прікладної математики
Курсова робота
з курсу В«Дискретна математикаВ»
на тему
В«Функціональна повнотіла системи функцій алгебри логікі. Спеціальні класи функцій алгебри логікі. Теорема Поста В»
Виконала: ст. гр.ІФ-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 = 0
Y = 0
0
1
1
0
1
1
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.
заперечення імплікації
повторення Першого аргументу
заперечення оберненої імплікації
У
повторення іншого аргументу
ху
|
