додати матеріал


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

[ виправити ] текст може містити помилки, будь ласка перевіряйте перш ніж використовувати.

скачати

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

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

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

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

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

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

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

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

Виконав: студент 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

1

0

0

1

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

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

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

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

X

Y

X & Y

1

1

1

1

0

0

0

1

0

0

0

0

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

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

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

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

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

X

Y

X Y

1

1

1

1

0

1

0

1

1

0

0

0

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

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

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

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

X

Y

X Y

1

1

1

1

0

0

0

1

1

0

0

1

Наприклад, вислів «Якщо число 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 називаються членами еквіваленції.

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

X

Y

X Y

1

1

1

1

0

0

0

1

0

0

0

1

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

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

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

X

Y

1

1

0

1

0

1

0

1

1

0

0

1

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

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

1)

2)

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

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

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

X

Y

X Y

1

1

0

1

0

0

0

1

0

0

0

1

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

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

X

Y

1

1

0

1

0

1

0

1

1

0

0

0

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

За допомогою логічних операцій над висловлюваннями із заданої сукупності висловлювань можна будувати різні складні висловлювання. При цьому порядок виконання операцій вказується дужками. Наприклад, з трьох висловлювань 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 - кількість змінних.

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

X

Y

1

1

0

0

1

0

0

1

0

0

1

0

1

1

0

1

1

0

1

0

0

0

0

1

1

1

0

0

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

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 1 & A 2 & ... & 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 1 (A 2 ... (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 і яка є логічним наслідком зазначених формул (посилок):

Рішення:

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

X

Y

Z

V


1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

0

0

1

1

0

0

1

1

1

1

1

1

1

1

1

1

0

0

1

1

1

1

1

1

0

0

1

1

1

1

1

0

1

0

1

1

1

1

1

0

1

0

1

1

1

1

0

0

1

0

0

0

1

0

0

0

1

0

0

0

1

0















*

У правому стовпчику зірочками відзначимо ті рядки, в яких всі чотири посилки приймають значення 1. Цій вимозі задовольняє лише 15-й рядок, в якій λ (X) = 0 і λ (Y) = 0. Отже, треба знайти таку формулу F (X, Y), для якої F (0, 0) = 1, то така формула буде логічним наслідком чотирьох даних посилок. Шукаємо таку формулу, використовуючи СДНФ і вважаємо, що на всіх інших наборах значень змінних шукана формула звертається до 0:

F (0, 1) = F (1, 0) = F (1, 1) = 0.

Отримуємо F (X, Y) .

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

Рішення:

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

X

Y

Z


1

1

1

0

1

0

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

1

1

1

1

1

0

1

0

1

1

0

1

1

1

0

1

*

*


*

*

Знайдемо таку формулу F (X, Y), для якої F (1, 1) = F (0, 1) = F (1, 0) = 1, яка буде логічним наслідком двох даних посилок.

F (0, 0) = 0.

Отримуємо F (X, Y) .

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

Рішення:

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

X

Y

Z


1

1

1

0

1

0

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

1

0

1

1

0

1

1

1

0

1

0

0

1

1

1

1

1

1

1

0

1

0

1

1







*

*

Знайдемо таку формулу F (X, Y), для якої F (0, 0) = 1, яка буде логічним наслідком трьох даних посилок.

F (1, 0) = F (0, 1) = F (1, 1) = 0.

Отримуємо F (X, Y) .

Щоб визначити логічним наслідком яких посилок є формула А (X 1, X 2, ..., X n), необхідно:

1) привести її до СКНФ.

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

Знайти всі не тотожне помилкові формули алгебри висловлень, для яких така формула є логічним наслідком:

Завдання 1.

Рішення:

Відсутні диз'юнкції:

Здійснення:

Дана формула може логічно випливати або з самої себе, або з тотожно хибною формули.

Завдання 2.

Рішення:

Відсутні диз'юнкції:

Здійснення:

Дана формула може логічно випливати або з самої себе, або з тотожно хибною формули.

Завдання 3.

Рішення:

Відсутні диз'юнкції:

Посилки:

;

;

;

;

;

;

.

Дана формула може логічно випливати або з самої себе, або з тотожно хибною формули.

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

Рішення:

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

X

Y

Z

V


1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

1

1

1

1

1

1

1

1

1

1

1

1

1

0

0

0

0

0

0

1

0

1

0

0

0

0

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

0

0

0













*



У правому стовпчику зірочками відзначимо ті рядки, в яких обидві дані посилки приймають значення 1, а наслідок приймає значення 0. Цій вимозі задовольняє лише 12-й рядок, в якій λ (Z) = 1 і λ (V) = 1. Ясно, що при цих значеннях Z і V шукана посилка F (Z, V) повинна приймати значення 0, тому що в противному випадку формула не буде логічним наслідком формул . Будемо вважати, що на інших наборах значень висловлювань Z і V формула F (Z, V) приймає значення 1. Отже, для шуканої посилки F (Z, V) отримуємо таку таблицю істинності:

Z

V

F (Z, V)

1

1

0

1

0

1

0

1

1

0

0

1

Знаходимо СКНФ для шуканої формули. Отримуємо F (Z, V) .

Задача 5. Знайти відсутню посилку (формулу) F, залежить лише від зазначених висловлювань, щоб була вірна наступна виводимість:

Рішення:

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

X

Y

Z


1

1

1

0

1

0

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

1

1

1

0

1

1

0

1

1

0

1

0

1

0

1

1

0

1

1

0

1

1

1

1

*

У правому стовпчику зірочками відзначимо ті рядки, в яких обидві дані посилки приймають значення 1, а наслідок приймає значення 0. Цій вимозі задовольняє лише 1-й рядок, в якій λ (X) = 1 і λ (Y) = 1. Будемо вважати, що на інших наборах значень висловлювань X і Y формула F (X, Y) приймає значення 1. Отже, для шуканої посилки F (X, Y) одержуємо наступну таблицю істинності:

X

Y

F (X, Y)

1

1

0

1

0

1

0

1

1

0

0

1

Знаходимо СКНФ для шуканої формули. Отримуємо F (X, Y) .

Задача 5. Знайти відсутню посилку (формулу) F, залежить лише від зазначених висловлювань, щоб була вірна наступна виводимість:

Рішення:

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

X

Y

Z


1

1

1

0

1

0

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

1

1

1

0

1

1

0

1

1

0

1

0

1

0

1

1

0

1

1

0

1

1

1

1

*

У правому стовпчику зірочками відзначимо ті рядки, в яких обидві дані посилки приймають значення 1, а наслідок приймає значення 0. Цій вимозі задовольняє лише 1-й рядок, в якій λ (X) = 1 і λ (Y) = 1. Будемо вважати, що на інших наборах значень висловлювань X і Y формула F (X, Y) приймає значення 1. Отже, для шуканої посилки F (X, Y) одержуємо наступну таблицю істинності:

X

Y

F (X, Y)

1

1

0

1

0

1

0

1

1

0

0

1

Знаходимо СКНФ для шуканої формули. Отримуємо F (X, Y) .

Задача 5. Знайти відсутню посилку (формулу) F, залежить лише від зазначених висловлювань, щоб була вірна наступна виводимість:

Рішення:

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

X

Y

Z

Z


1

1

1

0

1

0

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

0

0

0

1

0

1

0

0

1

0

1

1

0

0

1

0






*

У правому стовпчику відзначимо рядок, в якому дана посилка приймає значення 1, а наслідок приймає значення 0. Цій вимозі задовольняє лише 6-й рядок, в якій λ (X) = 0, λ (Y) = 1 і λ (Z) = 0. Будемо вважати, що на інших наборах значень висловлювань X, Y, Z формула F (X, Y, Z) приймає значення 1. Отже, для шуканої посилки F (X, Y, Z) отримуємо таку таблицю істинності:

X

Y

Z

F (X, Y, Z)

1

1

1

0

1

0

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

1

1

1

1

1

0

1

1

Знаходимо СКНФ для шуканої формули. Отримуємо

F (X, Y, Z) .

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

У наступних пропозиціях замість трьох крапок поставте слова «необхідно, але недостатньо» або «достатньо, але не необхідно", а де можливо «необхідно і достатньо» так, щоб вийшло справжнє твердження:

Завдання 1. Нехай на відрізку [a, b] визначена неперервна функція f (x) має на проміжку [a, b] кінцеві похідні, тоді:

Для того, щоб функція f (x) була постійною на відрізку [a, b] необхідно і достатньо, щоб = 0 для .

Рішення:

F (x) = const на [a, b] - Істина

F (x) = const на [a, b] - істина

Завдання 2. Для того, щоб два вектора в просторі були перпендикулярними, необхідно і достатньо, щоб їх скалярний твір дорівнювало нулю

- Істина

- Істина

Завдання 3. Для того, щоб рівняння мало дійсні корені, необхідно і достатньо, щоб .

мало дійсні корені

мало дійсні корені

Задача 4. Для того, щоб в точці x 0 функція f (x) мала екстремум, необхідно, щоб

Рішення:

функція f (x) в точці x 0 має екстремум - Істина

функція f (x) в точці x 0 має екстремум - брехня

контрпример: .

Задача 5. Для того, щоб чотирикутник був квадратом, необхідно, але не достатньо, щоб його діагоналі були перпендикулярні.

Рішення:

ABCD - квадрат - Істина

ABCD - квадрат - брехня

B

контрпример: A C

D

Задача 6. Для того, щоб рівняння cos x = a мало рішення, необхідно, але не достатньо, щоб .

Рішення:

Cos x = a - має рішення

Cos x = a - має рішення - брехня

контрпример: a = 3.

Завдання 7. Для того, щоб в точці x 0 функція f (x) мала розрив другого роду, достатньо, щоб = ∞.

Рішення:

функція f (x) в точці x 0 має розрив другого роду - істина.

Завдання 8. Для того, щоб вираз x 2 - 2x - 3 дорівнювало нулю, достатньо, але не необхідно, щоб x = -1.

Рішення:

x 2 - 2x - 3 = 0 - Брехня

контрпример: x = 3.

x 2 - 2x - 3 = 0 - істина

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

Одне з застосувань алгебри висловлювань - аналіз і синтез релейно-контактних схем.

Ще в 1910 році фізик П.С. Еренфест вказав на можливість застосування апарату алгебри логіки при дослідженні релейно-контактних схем. Кожній схемі можна поставити у відповідність певну формулу алгебри висловлювань, і кожна формула алгебри висловлень реалізується за допомогою деякої схеми.

Розглянемо 2-х-полюсні перемикачі, тобто такі, які мають два стани: «замкнуто» - 1, «розімкнуте» - 0. На схемі будемо зображувати:

Визначення 7. Перемикач, який зблокований з X так, що він замкнутий, якщо X розімкнений, і розімкнений, якщо X замкнутий, називається інверсним і позначається .

Кон'юнкція двох висловлювань X і Y буде представлена ​​двополюсної схемою з послідовним з'єднанням двох перемикачів X і Y.

Ця схема пропускає струм тоді і тільки тоді, коли істини і X, і Y одночасно, тобто істина кон'юнкція X & Y.

X & Y

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

X Y

Ця схема пропускає струм у випадку, якщо істинно висловлювання X або істинно висловлювання Y, тобто істина диз'юнкція X Y.

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

Визначення 8. Дві схеми називаються рівносильними, якщо мають однакові функції провідності.

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

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

Завдання 1. Скласти РКС, що володіє такою функцією провідності:

Рішення:

Завдання 2. Скласти РКС володіє такою функцією провідності:

Рішення:

Завдання 3. Скласти РКС володіє такою функцією провідності:

Рішення:

Задача 4. Спростити РКС:

Рішення:

Їй відповідає функція провідності:

F (X, Y, Z)

F (X, Y, Z)

Цією ж функції провідності відповідає більш проста схема.

Задача 5. Спростити РКС:

Рішення:

Їй відповідає функція провідності:

Цією ж функції провідності відповідає більш проста схема.

Задача 6. Спростити РКС:

Рішення:

Їй відповідає функція провідності:

Завдання 7. Який контакт необхідно вкласти в вакантне місце, щоб функція провідності отриманої схеми стала б дорівнює даної булевої функції:

Даній схемі відповідає функція провідності:

Рішення:

Завдання 8. Який контакт необхідно вкласти в вакантне місце, щоб функція провідності отриманої схеми стала б дорівнює даної булевої функції:

Даній схемі відповідає функція провідності:

Рішення:

Задача 9. Який контакт необхідно вкласти в вакантне місце, щоб функція провідності отриманої схеми стала б дорівнює даної булевої функції:

Даній схемі відповідає функція провідності:

Рішення:

Задача 10. Побудувати РКС з чотирма перемикачами, яка проводить струм тоді і тільки тоді, коли замикаються не всі перемикачі, а тільки деякі з них.

Рішення:

Складемо таблицю значень функції провідності F (X, Y, Z, T) цієї схеми:

X

Y

Z

T

F (X, Y, Z, T)


1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

0

0

0

0

0

0

0

0

0

0

1

*















*

У правому стовпчику зірочками відзначимо ті рядки, на яких функція F (X, Y, Z, T) звертається до 0, запишемо для неї вираз, використовуючи СКНФ, бо наборів значень аргументів, на яких функція звертається до 0, значно менше, ніж наборів значень аргументів, на яких функція звертається в 1, і значить, СКНФ буде простіший, ніж СДНФ:

Задача 11. Побудувати схему з трьома перемикачами, яка замикається тоді і тільки тоді, коли замкнутий або один, або два перемикача. При побудові використовувати не більше шести контактів.

Рішення:

Складемо таблицю значень функції провідності F (X, Y, Z) цієї схеми:

X

Y

Z

F (X, Y, Z)


1

1

1

0

1

0

0

0

1

1

0

1

0

1

0

0

1

0

1

1

0

0

1

0

0

1

1

1

1

1

1

0


*

*

*

*

*

*

У правому стовпчику зірочками відзначимо ті рядки, на яких функція

F (X, Y, Z, T) звертається до 1, запишемо для неї вираз, використовуючи СКНФ, бо наборів значень аргументів, на яких функція звертається до 0, значно менше, ніж наборів значень аргументів, на яких функція звертається в 1, і виходить, СКНФ буде простіший, ніж СДНФ:

Завдання 12. Потрібно скласти схему з чотирма перемикачами X, Y, Z, T. Схема повинна проводити ток тоді і тільки тоді, коли будуть замкнуті перемикачі X і Y або Z і T.

Рішення:

Складемо таблицю значень функції провідності F (X, Y, Z, T) цієї схеми:

X

Y

Z

T

F (X, Y, Z, T)


1

1

1

1

1

1

1

1

0

0

0

0

0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

0

0

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

0

0

0

1

0

0

0

0

0

0

0

0

1

0

0

0




*









*




У правому стовпчику зірочками відзначимо ті рядки, на яких функція

F (X, Y, Z, T) звертається до 1, запишемо для неї вираз, використовуючи СДНФ:

Задача 13. Побудувати контактну схему для оцінки результатів деякого спортивного змагання трьома суддями при наступних умовах: суддя, зараховуються результати, натискає наявну в його розпорядженні кнопку, а суддя, не зараховуються результати, кнопки не натискає. У випадку, якщо кнопки натиснули не менше двох суддів повинна загорітися лампочка (позитивне рішення суддів прийняте простою більшістю голосів).

Робота РКС описується функцією Буля трьох змінних F (X, Y, Z), де змінні висловлення X, Y, Z означають:

X - суддя X голосує «за»

Y - суддя Y голосує «за»

Z - суддя Z голосує «за»

Таблиця істинності функції F (X, Y, Z) має вигляд:

XYZ

F (X, Y, Z)

1 1 1

1

1 1 0

1

1 0 1

1

0 1 1

1

1 0 0

0

0 1 0

0

0 0 1

0

0 0 0

0

Цією ж функції провідності відповідає більш проста схема.

Висновок

У Дипломною роботі розглянуті практичні програми алгебри висловлювань. Детально викладена теоретична частина, що стосується практичних застосувань викладених у цій роботі, як:

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

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

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

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

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

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

Література

  1. Ігошин В.І. Задачник - практикум з математичної логіки. М.: Просвещение, 1986.

  2. Л.М. Ліхтарніков, Т.Г. Сукачова Математична логіка. Видавництво «Лань», 1998

  3. М.А Айзерман, Л.А. Гусєв, Л.І. Розоноер, І.М. Смирнов, А.А. Таль. Логіка. Автомати. Алгоритми. М., Фізматгіз, 1963 р.

  4. Математична логіка (Під загальною редакцією А. А. Столяра) - Мінськ, 1991

  5. Новиков П.С., Елементи математичної логіки. Фізматгіз, М., 1959

  6. Яблонський С.В., Гаврилов Г.П., Кудрявцев В.Б. Опції алгебрилогікі і класи Посту. - М.: Наука, 1966

Рецензія

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

математичного факультету СГУТ і КД

Галайджян Аркадій Сетраковіч.

Представлена ​​для рецензування робота присвячена практичним додаткам алгебри висловлювань, які зберігають свою актуальність.

Дипломна робота містить вступ, іеоретіческую частина, пратіческую частина, висновок і список літератури.

У першій частині дипломної роботи розглянуті основні теоретичні питання, в тому числі рівносильні формули алгебри висловлень, нормальні форми, логічні наслідки і т.д.

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

Дипломна робота Галайджян А. С. грамотно викладена, зазначені джерела використані досить повно, поставлена ​​мета достігнута.Работа логічно послідовна, задовольняє всім вимогам, пред'являти до дипломних робіт і заслуговує відмінної оцінки.

Рецензент доцент, кандидат ф.-м. наук

Симонян А. Р.

Додати в блог або на сайт

Цей текст може містити помилки.

Математика | Диплом
282.4кб. | скачати


Схожі роботи:
Розвиток функціональної лінії в курсі алгебри 7-9 класів на прикладі підручників з алгебри під ред
Розвиток функціональної лінії в курсі алгебри 9 липня класів на прикладі підручників з алгебри під ред
Логіка висловлювань
Алгебра висловлювань на уроках інформатики
Структурні та прагматичні особливості директивних висловлювань
Прагматичні аспекти компліментарних висловлювань в сучасній англій
Розробка технологій повторення теми Логіка висловлювань
Прагматичні аспекти компліментарних висловлювань в сучасній англійській мові
Принцип резолюції в обчисленні висловлювань та логіки предикатів і його модифікації
© Усі права захищені
написати до нас
Рейтинг@Mail.ru