Практичні програми алгебри висловлювань

Міністерство загальної та професійної освіти РФ

Сочинський державний університет

туризму і курортної справи

Соціально-педагогічний інститут

Математичний факультет

Кафедра загальної математики

Дипломна робота

«Практичні програми алгебри висловлювань»

Виконав: студент V курсу

^{(Підпис)} денної форми навчання

спеціальність 010100

«Математика»

Галайджян А. С.

студентський квиток № 98-МА011

Завідувач кафедри: доцент, кандидат ф.-м. наук

^{(Підпис)} Симонян А. Р.

^(Сочі - 2002

Зміст

Введення

1. Елементи алгебри висловлювань

1.1 Логічні операції над висловлюваннями

1.2 Рівносильні формули алгебри висловлень

1.3 Нормальні форми

1.4. Логічні наслідки

2. Рішення задач за допомогою алгебри висловлювань

2.1 Дослідження міркувань

2.2 Отримання логічних наслідків з даних формул і посилок для даних логічних наслідків

2.3 Необхідні і достатні умови

2.4 Аналіз і синтез релейно-контактних схем

Висновок

Література

Введення

Як самостійна наука логіка оформилася в працях грецького філософа Аристотеля (384-322 р. до н.е.). Він систематизував відомі до нього відомості, і ця система стала надалі називатися формальної або Арістотелевої логікою.

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

Вперше в історії ідеї про побудову логіки на математичній основі були висловлені німецьким математиком Г. Лейбніцем в кінці XVII століття. Він вважав, що основні поняття логіки повинні бути позначені символами, які з'єднуються за особливими правилами. Це дозволить всяке міркування замінити обчисленням.

«Ми вживаємо знаки не тільки для того, щоб передати наші думки іншим особам, а й для того, щоб полегшити сам процес нашого мислення» (Лейбніц).

Перша реалізація ідеї Лейбніца належить англійському вченому Д. Булю. Він створив алгебру, в якій буквами позначені висловлювання, і це призвело до алгебри висловлювань. Введення символічних позначень в логіку мало для цієї науки таке ж вирішальне значення, як і введення літерних позначень для математики. Саме завдяки введенню символів в логіку була отримана основа для створення нової науки - математичній логіці.

Застосування математики до логіки дозволило представити логічні теорії в новій зручній формі і застосувати обчислювальний апарат до вирішення завдань, малодоступних людського мислення, і це, звичайно, розширило область логічних досліджень. До кінця XIX століття актуальне значення для математики набули питання обгрунтування її основних понять та ідей. Ці завдання мали логічну природу і, природно, призвели до подальшого розвитку математичної логіки.

Особливості математичного мислення пояснюються особливостями математичних абстракцій і різноманіттям їх взаємозв'язків. Вони відображаються в логічній систематизації математики, а доказі математичних теорем. У зв'язку з цим сучасну математичну логіку визначають як розділ математики, присвячений вивченню математичних доказів і питань основ математики.

Методи обгрунтування математики були розвинені Д. Гільбортом і його школою. Вони грунтуються на побудові математичних теорій як синтаксичних теорій, в яких всі аксіоми записуються формулами в деякому алфавіті і точно вказуються правила виведення одних формул з інших, тобто в теорію як складова частина входить математична логіка.

Таким чином математична теорія несуперечність якої вимагалося довести, стала предметом іншої математичної теорії, яку Гільберт назвав математикою, або теорією доказів.

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

Мета дипломної роботи: ознайомитися з практичними додатками алгебри висловлювань, а також навчитися реалізовувати їх на практиці при вирішенні задач різного типу.

Для досягнення мети роботи в першій частині розглядаються основні поняття і теоретичні відомості, що стосуються даної проблеми:

- Логічні операції над висловлюваннями;

- Рівносильні формули алгебри висловлень;

- Нормальні форми;

- Логічні наслідки.

У другій частині наводиться докладний опис і завдання практичних програм, як:

- Дослідження міркувань;

- Отримання логічних наслідків з даних формул і посилок для даних логічних наслідків;

- Необхідні і достатні умови;

- Аналіз і синтез релейно-контактних схем.

1. Елементи алгебри висловлювань

1.1 Логічні операції над висловлюваннями

Запереченням висловлення х називається нове висловлювання, яке є істинним, якщо висловлювання X ложно, і хибним, якщо висловлювання X істинно.

Заперечення висловлювання X позначається і читається «не X» або «невірно, що X».

Логічні значення висловлювання можна описати за допомогою таблиці

Таблиці такого виду прийнято називати таблицями істинності.

Кон'юнкція двох висловлювань X, Y називається висловлення, яке вважається дійсним, якщо обидва висловлювання X, Y істинні, і хибним, якщо хоча б одне з них помилково.

Кон'юнкція висловлювань X, Y позначається символом X & Y або (X Ù Y), читається «X і Y». Висловлювання X і Y називаються членами кон'юнкції або кон'юнктивні елементами.

Логічні значення кон'юнкції описуються наступною таблицею істинності:

Наприклад, для висловлювань «6 ділиться на 2», «6 ділиться на З» їх кон'юнкція буде висловлювання «6 ділиться на 2 і 6 ділиться на З», яке, очевидно, істинно.

З визначення операції кон'юнкції видно, що союз «і» в алгебрі логіки вживається в тому ж сенсі, що і в повсякденній мові. Але в звичайній мові не прийнято з'єднувати союзом «і» два висловлювання далеких один від одного за змістом, а в алгебрі логіки розглядається кон'юнкція двох будь-яких висловлювань.

Диз'юнкцією двох висловлювань X, Y називається висловлення, яке вважається дійсним, якщо хоча б одне з висловлювань X, Y істинно, і хибним, якщо вони обидва хибні.

Диз'юнкція висловлювань X, Y позначається символом X Y, читається «X або Y», де «або» використовується в неразделітельной формі. Висловлювання X і Y називаються членами диз'юнкції.

Логічні значення диз'юнкції описуються наступною таблицею істинності:

Наприклад, вислів «У трикутнику DFE кут D або кут Е гострий» істинно, тому що обов'язково істинно хоча б одне з висловлювань: «У трикутнику DFE кут D гострий», «В трикутнику DFE кут Е гострий».

Імплікацією двох висловлювань X, Y називається висловлення, яке вважається помилковим, якщо X істинно, а Y - помилково, і істинним у всіх інших випадках.

Імплікація висловлювань X, Y позначається символом X Y, читається «якщо X, то Y» або «з X слід Y». Висловлення X називають посилкою, висловлювання Y - ув'язненням.

Логічні значення операції імплікації описуються наступною таблицею істинності:

Наприклад, вислів «Якщо число 12 ділиться на 6, то воно ділиться на З», очевидно, істинно, так як тут істинна посилка «Число 12 ділиться на 6» і істинно висновок «Число 12 ділиться на 3».

Вживання слів «якщо ..., то ...» в алгебрі логіки відрізняється від вживання їх в повсякденній мові, де ми, як правило, вважаємо, що, якщо висловлювання X ложно, то вислів «Якщо X, то Y» взагалі не має сенсу. Крім того, будуючи пропозицію виду «якщо X, то Y »в повсякденній мові, ми завжди маємо на увазі, що пропозиція Y випливає з пропозиції X. Вживання слів «якщо ..., то ...» в математичній логіці не вимагає цього, оскільки в ній сенс висловлювання не розглядається.

Еквіваленції (або еквівалентністю) двох висловлювань X, Y називається висловлення, яке вважається дійсним, коли обидва висловлювання X, Y або одночасно істинні, або одночасно хибні, і помилковим у всіх інших випадках.

Еквіваленції висловлювань X, Y позначається символом X Y, читається «для того, щоб X, необхідно і достатньо, щоб Y »або« X тоді і тільки тоді, коли Y ». Висловлювання X, Y називаються членами еквіваленції.

Логічні значення операції еквіваленції описуються наступною таблицею істинності:

Наприклад, еквіваленції «Трикутник SPQ з вершиною S і підставою PQ рівнобедрений тоді і тільки тоді, коли P = Q »є істинною, так як висловлювання «Трикутник SPQ з вершиною S і підставою PQ рівнобедрений» і «В трикутнику SPQ з вершиною S і підставою PQ P = = Q »або одночасно істинні, або одночасно хибні.

Еквівалентність грає важливу роль в математичних доказах. Відомо, що значна кількість теорем формулюється у формі необхідних і достатніх умов, тобто у формі еквівалентності. У цьому випадку, знаючи про істинність або хибність одного з двох членів еквівалентності і довівши істинність самої еквівалентності, ми укладаємо про істинність або хибність другого члена еквівалентності.

Однак існують операції, за допомогою яких може бути виражена будь-яка з п'яти логічних операцій, якими ми користуємося. Такий операцією є, наприклад, операція «Штрих Шеффера». Ця операція позначається символом і визначається наступною таблицею істинності:

Штрих Шеффера - Функція, що приймає значення брехня, якщо X - істинно і Y - істинно.

Очевидно, мають місце равносильности:

1)

2)

З цих двох рівносильних випливає, що всяка формула алгебри логіки може бути замінена равносильной формулою, що містить тільки операцію «Штрих Шеффера».

Зазначимо, що .

Стрілка Пірса (функція Вебба) X Y - функція, що приймає значення істина, коли X - помилково і Y - помилково.

Зазначимо, що X Y =

Функція додавання по модулю 2 (функція різнойменними, або сума Жегалкина) - Функція, що приймає значення істинне, коли X і Y приймають протилежні значення.

Зазначимо, що = .

За допомогою логічних операцій над висловлюваннями із заданої сукупності висловлювань можна будувати різні складні висловлювання. При цьому порядок виконання операцій вказується дужками. Наприклад, з трьох висловлювань X, Y, Z можна побудувати висловлювання

(X & Y) Z і X .

Перше з них є диз'юнкція кон'юнкції X, Y і заперечення вияв Z, а друге висловлювання є імплікація, посилкою якої є висловлення X, а укладанням - заперечення диз'юнкції висловлювання Y і кон'юнкції висловлювань X, Z.

Будь-яке складне висловлювання, яке може бути отримано з елементарних висловлювань за допомогою застосування логічних операцій заперечення, кон'юнкції, диз'юнкції, імплікації і еквіваленції, називається формулою алгебри логіки.

Висловлювання позначаються великими літерами латинського алфавіту А, В, С, ...

Для спрощення запису формул прийнято низку угод. Дужки можна опускати, дотримуючись наступного порядку дій: кон'юнкція виконується раніше, ніж всі інші операції, диз'юнкція виконується раніше, ніж імплікація та еквівалентність. Якщо над формулою стоїть знак заперечення, то дужки теж опускаються.

У зв'язку з цим формули

(X & Y) Z і X

можуть бути записані так:

X & Y Z і X .

Логічне значення формули алгебри логіки повністю визначається логічними значеннями входять до неї елементарних висловлювань. Наприклад, логічним значенням формули у випадку, якщо X = 1, Y = 1, Z = 0 буде істина, тобто = 1.

Всі можливі логічні значення формули, залежно від значень вхідних у неї елементарних висловлювань, можуть бути описані повністю за допомогою таблиці істинності. Ця таблиця буде містити 2 ⁿ рядків, де n - кількість змінних.

Наприклад, для формули таблиця істинності має вигляд:

Легко бачити, що, якщо формула містить n елементарних висловлювань, то вона приймає 2 ⁿ значень, що складаються з нулів і одиниць, або, що теж, таблиця містить 2 ⁿ рядків.

1.2 Рівносильні формули алгебри висловлень

Дві формули алгебри висловлень А і В називаються рівносильними або еквівалентними, якщо вони приймають однакові логічні значення на будь-якому наборі значень вхідних у формули елементарних висловлювань.

Рівносильність формул будемо позначати знаком , А запис А В означає, що формули А і В рівносильні.

Наприклад, рівносильні формули:

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

Наприклад, урочисте істинні формули

Формула А називається тотожно хибною (або протиріччям), якщо вона приймає значення 0 при всіх значеннях вхідних в неї висловлювань.

Наприклад, тотожне помилкова формула .

Формула А називається здійсненною, якщо вона приймає значення 1 при всіх значеннях вхідних в неї висловлювань.

Наприклад, здійсненна формула .

Ясно, що ставлення равносильности рефлексивно, симетрично і транзитивній.

Між поняттями равносильности і операцією існує наступна зв'язок: якщо формули А і В рівносильні, то формула А В - тавтологія, і назад, якщо формула А В - тавтологія, то формули А і В рівносильні.

Найважливіші равносильности алгебри висловлювань можна розбити на наступні групи.

1.Равносільності алгебри Буля:

1.Закон подвійного заперечення:

2. Комутативність:

3. Асоціативність:

4. Дистрибутивність & щодо :

5. Дистрибутивність щодо &:

6. Закони де Моргана:

7. Закони поглашенія:

8. Закони ідемпотентності:

9. Властивості констант:

10. Закон суперечності:

11. Закон виключення третього:

2. Равносильности, які виражають одні логічні операції через інші:

12.

13.

14.

15.

16.

17.

1.3 Нормальні форми

Основний із завдань алгебри висловлень є проблема дозволу, тобто чи є дана формула тавтологією або суперечністю або здійсненним формулою. Ця проблема легко вирішується за допомогою нормальних форм.

Визначення 1. Елементарною кон'юнкцією п висловлювань називається кон'юнкція висловлювань або їх заперечень.

Визначення 2. Елементарною диз'юнкцією п висловлювань називається диз'юнкція висловлювань або їх заперечень.

Теорема 1. Щоб елементарна диз'юнкція була тотожно істинною, необхідно і достатньо, щоб у ній містилося два висловлювання, з яких одна є запереченням іншого.

Теорема 2. Щоб елементарна кон'юнкція була тотожно хибною, необхідно і достатньо, щоб в ній була присутня пара висловлювань, з яких одна є запереченням іншого.

Визначення 3. Формула рівносильна даної і представляє собою диз'юнкцію елементарних кон'юнкція називається діз'юнктівной нормальною формою цієї формули. (ДНФ).

Визначення 4. Формула рівносильна даної і представляє собою кон'юнкцію елементарних диз'юнкцій називається кон'юнктівной нормальною формою цієї формули. (КНФ).

Узагальнимо існування ДНФ або КНФ для кожної формули:

1. Всі логічні операції можна замінити трьома: кон'юнкція, диз'юнкція і запереченням.

2. Знак заперечення за допомогою законів де Моргана можна віднести до пропозіціональним змінним.

3. За допомогою дистрибутивних законів формула перетворюється в кон'юнкцію елементарних диз'юнкцій або диз'юнкцію елементарних кон'юнкція.

Для кожної формули може бути складено кілька ДНФ і КНФ. Але все ДНФ (або КНФ) даної формули рівносильні між собою.

Визначення 5. Досконалою діз'юнктівной нормальною формою формули А (x _1, x _2, ..., x _n) називається ДНФ, що володіє наступними властивостями:

а) в ній немає однакових диз'юнктивних елементів;

б) жодна елементарна кон'юнкція не містить двох однакових висловлювань;

в) ні яка елементарна кон'юнкція не містить висловлювання разом з її запереченням;

г) у кожної елементарної кон'юнкції міститься або X _i, або , Де i = .

Умова а) - г) є необхідними і достатніми для того, щоб ДНФ стала СДНФ. У свою чергу ці умови дають можливість скласти алгоритм отримання СДНФ з ДНФ:

1) якщо яка-небудь елементарна кон'юнкція не містить висловлювання X _i, то замінимо виразом ;

2) якщо в отриманому виразі виявляться однакові елементарні кон'юнкції, то зайві опускаються;

3) якщо в деяких елементарних кон'юнкція виявляться однакові висловлювання, то зайві опускаються;

4) видаляємо елементарні кон'юнкції, в яких містяться висловлювання разом з їх запереченням.

Якщо всі елементарні кон'юнкції виявляться такими, тобто вся формула буде помилковою, то вона не буде мати СДНФ.

Визначення 6. Досконала кон'юнктивні нормальна форма - це її КНФ володіє властивостями:

а) в ній немає двох однакових кон'юнктивні елементів;

б) жодна елементарна диз'юнкція не містить двох однакових висловлювань;

в) жодна елементарна диз'юнкція не містить який-небудь змінної з її запереченням;

г) кожна елементарна диз'юнкція містить або X _i, або , Де i = .

У свою чергу ці умови дають можливість скласти алгоритм отримання СКНФ з КНФ:

1) якщо яка-небудь елементарна диз'юнкція не містить висловлювання X _i, то замінимо виразом ;

2) якщо в отриманому виразі виявляться однакові елементарні диз'юнкції, то зайві опускаються;

3) якщо в деяких елементарних диз'юнкція виявляться однакові висловлювання, то зайві опускаються;

4) видаляємо елементарні диз'юнкції, в яких містяться висловлювання разом з їх запереченням.

Для тотожно істинних формул СКНФ не існує.

Для будь-якої формули алгебри висловлень існує тільки одна СДНФ і тільки одна СКНФ, крім протиріч і тавтологій, тобто для протиріч буде існувати СКНФ, а для тавтологію - тільки СДНФ.

1.4 Логічні слідства

Визначення 1. Формула B називається логічним наслідком формул A _1, A _2, ..., A _n, якщо при будь-яких значеннях, що входять до них, елементарних висловлювань формула B приймає значення істинно всякий раз, коли формули A _1, A _2, ..., A _n приймають значення істинне. Позначається A _1, A _2, ..., A _n ╞ B

З визначення логічного слідування випливає:

1. Тавтологія логічно випливає з будь-якої формули.

2. З протиріччя логічно випливає будь-яка формула.

Теорема 1. З A логічно випливає B тоді й тільки тоді, коли тавтологією є A B.

Теорема 2. A _1, A _2, ..., A _n ╞ B тоді і тільки тоді, коли є тавтологією

A ₁ & A ₂ & ... & A _n B.

Теорема 3. З формул A _1, A _2, ..., A _n, B логічно випливає C тоді і тільки тоді, коли з формул A _1, A _2, ..., A _n логічно випливає B C.

Слідство 1. З A і B логічно випливає C тоді і тільки тоді, коли тавтологією є

A (B C).

Наслідок 2. З формул A _1, A _2, ..., A _n логічно випливає B тоді й тільки тоді, коли тавтологією є

A ₁ (A ₂ ... (A _n B) ...).

Відношення логічного слідування відіграє в математиці велику роль.

Якщо з A ╞ B, то A називається достатньою умовою для B, а B - необхідною умовою для A.

Якщо разом з A ╞ B з B ╞ A, то A називається необхідною і достатньою умовою для B, а B - необхідним і достатнім умовою для A.

2. Рішення задач за допомогою алгебри висловлювань

2.1 Дослідження міркувань

Відношення логічного слідування використовується при дослідженні міркувань.

Завдання 1. Якщо 6 - складене число (S), то 12 - складене число (W). Якщо 12 - складене число, то існує просте число, більше ніж 12 (P). Якщо існує просте число більше 12, то існує складене число більше 12 (C). Якщо 6 ділиться на 2 (D), то 6 - складене число. Число 12 складене. Отже, 6 - складене число.

Посилки: , , , , W

Висновок: S

Рішення:

Дане висловлювання тавтологією не є, значить із зазначених посилок не слід вислів «6 - складене число».

Завдання 2. Я піду в кіно на нову комедію (A) або на заняття з математичної логіки (B). Якщо я піду в кіно, то я від усієї душі посміюся (C). Якщо я піду на заняття з математичної логіки, то випробую задоволення від логічних міркувань (D). Отже, чи я від усієї душі посміюся або випробую задоволення від логічних міркувань.

Посилки: , ,

Висновок:

Рішення:

Значить з даних посилок слід .

Завдання 3. Я піду додому (H) або залишуся тут і вип'ю стаканчик (S). Я не піду додому. Отже, я залишуся і вип'ю.

Посилки: ,

Висновок: S

Рішення:

Значить, вислів «я залишуся і вип'ю» є логічним наслідком з даних посилок.

Задача 4. Якщо Джон ляже сьогодні пізно (S), він буде вранці в отупінні (D). Якщо він ляже не пізно, то йому буде здаватися, що не варто жити (L). Отже, або Джон буде завтра в заціпенінні, або йому буде здаватися, що не варто жити.

Посилки: ,

Висновок:

Рішення:

Значить з даних посилок слід .

Задача 5. Або Селлі і Боб одного віку (S), або Селлі старше Боба (O). Якщо Селлі і Боб одного віку, то Ненсі і Боб не одного віку (N). Якщо Селлі старше Боба, то Боб старше Уолтера (W). Отже, чи Ненсі і Боб не одного віку, або Боб старше Уолтера.

Рішення:

Посилки: , ,

Висновок:

Значить з даних посилок слід .

2.2 Отримання логічних наслідків з даних формул і посилок для даних логічних наслідків

Логічні слідства знаходять таким чином:

1) всі посилки з'єднуються кон'юнкція і знаходяться СКНФ отриманої формули.

2) при виборі будь-яких елементарних диз'юнкцій і кон'юнкція будь-яких декількох елементарних диз'юнкцій, взятих по два, три і т.д.

виходять всі можливі висновки з даних посилок.

Завдання 1. Дано посилки: A і A B

Рішення:

Логічні наслідки:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. .

Завдання 2. Дано посилки:

Рішення:

Логічні наслідки:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7. .

Завдання 3. Дано посилки:

Рішення:

Логічні наслідки:

1. ;

2. ;

3. ;

4. ;

5. ;

6. ;

7.

;

Задача 4. Знайти формулу F (X, Y), що залежить тільки від змінних X і Y і яка є логічним наслідком зазначених формул (посилок):

Рішення:

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

1

1

0

0

1

1

0

0