Бульова алгебра

Технічний університет Молдовы.

РЕФЕРАТ ПО ПРОГРАММИРОВАНИЮ.

ТЕМА: Булева алгебра.

Факультет.

CIM.

Группа.

З — 092.

Підготував Плис Владимир.

Проверил.

Кишинів 1999 г.

План: Запровадження. 1) Предмет математичної логіки. 2) Калькуляція висловлювань. 3) Укладання. Библиография.

У цьому рефераті я спробую розкрити, деякі аспекти булевой алгебри. Математична логіка є сучасної формою, так званої формальної логіки, яка застосовує математичні методи на дослідження свого предмета. (Інші її назви: символічна логіка, теоретична логіка, логістика.) У формальної логіки і, в математичної логіці, зібрані результати законів структури правильних висновків. Висновок є розумовим процесом, у результаті якого з’являються нові відкриття виходячи з вже наявних (які передбачаються правильними), без практичних досліджень. Насправді, нове відкриття, отриманий у результаті виведення, (так званий остаточний висновок) у прихованій формі перебуває у попередньо наявних знаннях, в так званих предпосылках.

МАТЕМАТИЧНА ЛОГИКА.

ПРЕДМЕТ МАТЕМАТИЧНОЇ ЛОГИКИ.

Найпростіші закономірності висновків відкривалися людством емпіричним шляхом під час громадського виробництва (наприклад, найпростіші співвідношення арифметики і геометрії). Відкриття складніших законів пов’язані з результатами науки формальної логіки. Перше велике узагальнення формальної логіки належить Арістотелеві. У формальної логіки від початку застосовувалися (в поодинокі випадки) математичні методи, але розвиток логіки не встигало за застосуванням таких методів проти іншими областями математики. Тому формальна логіка відставала потреб науки (в першу чергу від вимог математики); відставання виявилося особливо очевидним до нової ери. Головними вадами формальної логіки були такі. 1. Вона не зуміла привести закони висновків до невеликого кількості надійних логічних законів; тому підтвердило слушність деяких висновків на основі експериментів, які потім спростували прикладами, які зворотне. 2. Вона стала нездатна аналізувати значну частину висновків, що застосовуються у повсякденної і з наукового життя; довести правильність чи неправильність таких висновків. (Наприклад, не могла довести, що з правильності пропозиції «Кожна трапеція є чотирикутником» випливає правильність пропозиції «Хто малює трапецію, той малює чотирикутник). Завдання математизації формальної логіки було поставлено і здійснена Лейбніцем. Його роботу продовжили математики ХІХ століття. На межі століття з відкриттям суперечностей у теорії множин (див. гол. «Теорія множин») розвиток математичної логіки одержало широкого розмаху. Нині результати математичної логіки використовують у всіх традиційних областях формальної логіки; відкриті цілком нові області. У час «традиційна» формальна логіка проти математичної логікою має значення для історії науки. Математична логіка не претендує для відкриття законів мислення взагалі, або ще меншою мірою на аналіз філософських проблем, що з людським мисленням. Це питання більше ставляться до «логіці» (на більш загальному буквальному розумінні) і до філософії. (Надалі слово «логіка» будемо розуміти математичну логику.).

ЩО ТАКЕ ВЫВОД?

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

1. (Передумови) Якщо буде роздача премії, ми виконали план.

Буде роздача премії. (Остаточний висновок) Ми виконали план.

Якщо прийняти це правильність передумов, слід прийняти Європу і правильність остаточного виведення. Інший, аналогічний приклад :

Якщо мені випаде туз, то я йду ва-банк.

Мені випав туз. Я йду ва-банк.

Зазвичай замість пропозицій (мені випав туз) і (я йду ва-банк) може бути записані будь-які такі изъявительные пропозиції, значення яких то, можливо правильно чи брехливо; слід залишити незмінними лише розташування слів «якщо» і «то» і місцезнаходження припущень, тобто структуру виведення. Нехай Проте й У позначає будь-які які замінять пропозиції. Структуру виведення можна висловити такою схемой;

Якщо Бо В.

А.

В.

Під визначенням, що це схема є (логічно правильну) схему висновків, мається на увазі таке. Якщо замість Проте й У підставити такі пропозиції, що передумови, отримані внаслідок заміни, будуть правильними, те й остаточне виведення правильно. Будь-який людина, розуміє значення спілок «якщо. .. то», зрозуміє, що це правильна схема виведення. У схемою виведення фігурують кілька слів з постійним значенням, далі кілька символів (літер) з мінливим значенням. Символи з мінливим значенням може бути перемінними різних типів. Відповідно до їх типом замість символів може бути поставлено різні граматичні формації (наприклад: изъявительные пропозиції, слова, які виражають властивості, назви предметів тощо. буд.). У минулому прикладі перемінні Проте й У замінюються лише изъявительными пропозиціями. На основі «регулярної» заміни змінних деякою (правильної) схеми виведення повинен виникати правильний висновок. Але визначення «регулярної заміни» означає як дотримання граматичних правил. У попередній схемою Проте й У можуть означати лише изъявительные пропозиції, правильність чи неправдивість яких то, можливо вирішена однозначно. Такі изъявительные пропозиції називатимемо висловлюваннями. За підсумками будь-який схеми виведення можна отримати правильний висновок лише за дотримання умов подібного характеру. Шляхом зміни умов можуть бути побудовано різні теорії логіки. Найважливішими главами математичної логіки є калькуляція висловлювань і калькуляція предикатів. У межах даних глав то, можливо досліджували схема виведення у найзагальнішому разі за найменшому числі умов. За інших розділах логіки розглядаються спеціальні схеми виведення, є менш общими.

КАЛЬКУЛЯЦІЯ ВЫСКАЗЫВАНИЙ.

ВЫСКАЗЫВАНИЕ.

Предметом калькуляції висловлювань є аналіз таких схем виведення, при яких заміняючи змінних висловлювання, виходять правильні висновки. Під терміном висловлювання мається на увазі таке дійсне пропозицію, що є однозначно чи правильним, чи хибним; тож: яке неспроможна одночасно б бути набагато правильним, і неправдивим (принцип несуперечливості); б) виключено, щоб було і неправильним, і неложным (принцип винятку третьої можливості). Властивості «правильне» і «хибне» маються на увазі у тому звичному значенні; вони не потребують подальшому аналізі. При в даних обставинах наведені вище изъявительные пропозиції задовольняють (з «хорошим наближенням») цим двом умовам; їх вважатимуться висловлюваннями. Тому логіка, побудована цих двох умовах, може мати простий дуже широка застосування. Природно, існують такі «тонкі обставини», у яких деяких изъявительных пропозицій не вважається висловлюваннями (наприклад, якщо дано пропозицію: «Іван прокидається», навряд можна сумніватися у правильності чи помилковості пропозиції «Іван спить»). Математичні терміни визначаються таким чином, що пропозиції, які виражають співвідношень між ними, завжди вважаються висловлюваннями; таке становище існує в усіх точних науках. Поняття «висловлювання» іноді позначається словами «твердження», «судження». У висновках можуть фігурувати висловлювання (або у формі передумов, або остаточною висновок), які з однієї чи кількох висловлювань, шляхом застосування деякого грамматического методу; вони називаються складними висловлюваннями. В багатьох випадках правильність виведення залежить від виду формування складного висловлювання. Тому необхідно займатися виглядом формування складних висловлювань деяких типів. Під терміном калькуляції висловлювань мається на увазі такий метод, з допомогою якого вже з чи навіть кількох висловлювань (членів операції калькуляції висловлювань) виходить вислів (результат операції), правильність чи неправдивість якого однозначно визначається правильністю чи ложностью членов.

ЗАПЕРЕЧЕННЯ І КОНЪЮНКЦИЯ.

Двома найпростішими прикладами вищенаведеної операції є заперечення і і. (Операція і результати операції тут позначається у тому ж назвою.) Під запереченням висловлювання, А мається на увазі висловлювання «Неправильно, що А» (чи деяка граматично перетворена форма даного висловлювання). За значенням висловлювання «неправильно» заперечення, А чи правильно тоді й тільки тоді, якщо саме, А неправильно; отже, заперечення справді є операція калькуляції висловлювань (відповідно до вищенаведеним определением).

Приклад: Запереченням пропозиції «мотор працює» є пропозицію «неправда, що мотор працює» чи, інакше: «мотор спрацьовує». Заперечення є одночленной операцією. Заперечення «А» позначається символом «~А» (читається: «не А»). Застосовуються ще й позначення «~ А», «— А», «А». Під конъюнкцией двох висловлювань Проте й У мається на увазі висловлювання «Проте й У» (чи деяка граматично змінена форма даного висловлювання). По значенням союзу «і» й є правильною тоді й тільки тоді, якщо обидва її члена правильні. Отже, зв’язок є також операцією калькуляції висловлювань. Операція конъюнкции «Проте й У» є двучленную операцію; її позначають, «А & У», «АВ». У разі конъюнкции союз «і» іноді замінюється іншим союзом (наприклад, «Анатолій тут, але Бориса немає» чи «Анатолій тут, хоча Борис пішов» тощо. буд.). Не впливає правильність чи неправдивість результату, має сенс тільки емоційне значення. Іноді союз взагалі пропускається. Якщо присудки двох пропозицій, пов’язаних між собою шляхом конъюнкции, збігаються, те спільне присудок представлено тільки одного з пропозицій. Наприклад, та «я живлюся хлібом і живлюся водою» після перетворення має такий вигляд: «я живлюся хлібом і води». Вивчення інших операцій калькуляції висловлювань уточнюється і полегшується з допомогою наступного міркування. Нехай властивості висловлювань «правильне» і «хибне» називаються логічними значеннями і позначаються знаками пив. Правильність (чи неправдивість) деякого висловлювання, А виражається й у такому формі, що логічним значенням висловлювання, А є п (чи л). Якщо задаються логічні значення окремих членів у певній операції калькуляції висловлювань, то даної операцією логічне значення результату визначається однозначно. Це дозволяє визначення таких операцій для логічних значень (крім вищенаведеного визначення для висловлювань) так: На місце і членів і результату підставляються логічні значення; причому, замість результату підставляється логічне значення висловлювання, образующееся даної операцією з висловлювань з відповідними членам логічними значениями.

Наприклад, заперечення логічних значень визначаються так:

(оскільки заперечення правильного висловлювання є ложным),.

(оскільки заперечення помилкового висловлювання є правильным);

а конъюнкции логічних значень так: (оскільки з'єднання двох правильних висловлювань є правильной),.

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

АЛГЕБРА ЛОГІЧНИХ ЗНАЧЕНИЙ.

Операції, проведені на логічних значеннях, називаються логічними операціями. Для викладу будь-яких логічних значенні вводяться логічні перемінні; вони позначаються символами p, q, r, …, р, р, … Отже, логічні перемінні можуть приймати відвідувачів два «значення»: п чи л. З використанням кількох операцій послідовно порядок виконання окремих операції позначається дужками; наприклад, ~(р) А q) (іноді дужки опускаються). Наприклад, замість висловлювання (7p)/q пишеться 7р / q при попередньому поясненні, у разі появи висловлювання без скобок знак стосується лише наступному знаку. Загалом буквальному розумінні n-членной логічного операцією називається кожна така функція, областю існування якої є упорядкований безліч всіх висловів, утворених з логічних значень пилці довжиною висловлювання n, а значенням став з двох логічних значень п і л. Будь-яка логічна операція має через операції заперечення і конъюнкции.

ДЕЯКІ ІНШІ ЛОГІЧНІ ОПЕРАЦИИ.

У сфері операцій на логічних змінних крім заперечення і конъюнкции корисні деяких інших операции.

У сфері одномірних логічних операцій фактичний інтерес представляє лише отрицание.

дизъюнкция.

Операція називається диз’юнкцією і позначається символом «p/q» (інакше її називають альтернацией, адъюнкцией, логічним складанням), чи «р + q». Диз’юнкція виражається з допомогою операцій конъюнкции і заперечення. Зв’язок, створена між двома висловлюваннями з допомогою допустового союзу «чи», є така операцією, якої у області логічних значень відповідає операція диз’юнкції: висловлювання бреше тоді й тільки тоді, якщо обидва висловлювання хибні. (Союз «чи» у разі застосовується у значенні припущення, якщо допускається правильність обох висловлювань). Наприклад: «випав дощ чи полили парк». Тому таке поєднання двох висловлювань також називається диз’юнкцією. (Символ «V» читається як і «чи»). Операція сполучення виражається з допомогою операцій дизъюнкции.

Отже, керуючись теоремою, кожна логічна операція має з допомогою лише операцій диз’юнкції і отрицания.

«ни-ни».

ИМПЛИКАЦИЯ.

Операція «р влечёт q» і називається імплікацією (з попереднім членом р і з наступним членом q).

Припустимо, що й р = п, ті значення висловлювання р влечёт q буде чи п, чи л залежно від цього, чи є значення q п, чи л. Це аналогічна тій, що типу «якщо Бо У», у якому перший член, А є правильною, вважається чи правильним, чи хибним в залежність від того, правильний чи помилковий другий його член У. Тому з'єднанню типу «якщо Бо У» відповідає імплікація у сфері логічних значень. Але водночас при фальшивому висловлюванні А пропозицію типу «якщо Бо У» може взагалі вважатися виступом Наприклад: якщо горить лампочка, то ліфт працює. Якщо висловлювання «горить лампочка» правильно, то правильністю висловлювання «ліфт працює» однозначно вирішується правильність вищенаведеного пропозиції. Але якщо висловлювання «горить лампочка» брехливо, то нічого не можна сказати правильність вищенаведеного пропозиції. Можна сказати: треба почекати, поки лампочка займеться Наведемо приклад, в якому нічого очікувати навіть можливості «почекати»: Якщо 2 * 2 = 5, то Дунай є європейської рікою. Якщо прийняти це те, що з'єднання типу «якщо.. .то» відповідає операції імплікації, при дотриманні останнього тотожності висловлювання «якщо Бо У» виражалося б із допомогою операцій конъюнкции і заперечення наступного вигляді: «неправильно, що: Проте й не У» (тут є вираз «не У» замість висловлювання «неправильно, що У»; в такий спосіб, ясно, що вираз «неправильно, що», розташоване початку висловлювання, належить як до Л, до вираженню «Проте й не У»). Відповідно до цим наведені вище два пропозиції в прикладі може бути переформулированы так: а) Неправильно, що горить лампочка і ліфт спрацьовує. б) Неправильно, що 2 * 2 = 5 і Дунай перестав бути європейської рікою. Якщо вираз «горить лампочка» брехливо, то брехливо і вираз «лампочка горіт і ліфт спрацьовує», а заперечення його — по а) — є правильною. Вислів. «2 * 2 = 5» брехливо, брехливо ще й вираз «Дунай перестав бути європейської рікою»; їх і — також помилкова, а заперечення цієї конъюнкции — по б) — є правильною. Тут немає протиріччя по порівнянню зі звичайним розумінням речей, оскільки звичайно не звертають уваги на правильність складного пропозиції типу «якщо. .. то» у разі, коли перша член сполуки бреше. Висловлювання виду «якщо Бо У» вважатимуться синонімами висловів виду «неправильно, що: «Проте й не У»; вони називаються импликациями (з попереднім членом, А наступним членом У); їхнього позначення застосовується символ, А влечёт У. Представлене у сфері логічних значень поняття імплікації типу р влечёт q відповідає поняттю вищенаведеної операції висловлювання. Операції на висловлюваннях, висловлені з допомогою спілок і частинок, сформульовані недостатньо точно; здебільшого, вони до деякою ступеня двозначні. Цілком імовірно розпізнавання операцій конъюнкции і заперечення найменш проблематично у тому граматичної формі уявлення. Тому велике значення має тут можливість висловлювання будь-який логічного операції через операції конъюнкции і заперечення. Як засвідчили вище, це дало змогу витлумачити освіту складного пропозиції виду «якщо. .. то» як операцію. Згадуються деякі інші граматичні синоніми операції «А влечёт У»: «У, за умови що Л», «Тільки тоді Якщо ж У», «Достатнім умовою У є А», «Необхідною умовою, А є У», «У, а то й А». І і і диз’юнкція виражаються з допомогою операцій імплікації і заперечення. Тому будь-яка логічна операція має з допомогою операцій заперечення і импликации.

ЭКВИВАЛЕНТНОСТЬ.

Останній вид висловлювання операції еквівалентності. Оскільки висловлювання p еквівалентно q = n тоді й тільки тоді, коли p = q, то дана логічна операція відповідає освіті складного пропозиції виду «А тоді й тільки тоді, коли У». Порозуміння спікера і логічне значення пропозиції такої вдачі, освіченого з цих двох будь-яких висловлювань, іноді важко до людини, як і розуміння пропозиції виду «якщо. .. то». Наприклад, «2 < 3 тоді й тільки тоді, якщо світить сонце». Тому це припущення розуміється операцією калькуляції висловлювань тільки у тому випадку, якщо слід його синонімом висловлювань виду «неправильно, що Проте й не У, і, неправильно, що ні Проте й У». І тут дана операція «А влечёт У» і називається еквівалентністю. Часто трапляються такі синоніми цієї операції: «Для, А необхідне й досить б», «Як-от тоді, коли В».

Укладання Булеву алгебру утворюють все підмножини деякого безлічі. Те, що вони утворюють ґратчасту структуру, очевидно. Неважко довести виконання дистрибутивности. Нульовим елементом є порожній безліч, а одиничним — все основне безліч. До кожного підмножини існує додатковий елемент — доповнення до безлічі в теоретико-множественном сенсі. Булевы алгебри знаходять застосування головним чином теорії множин, в математичної логіці, теоретично ймовірностей й у функціональному анализе.

Библиография.

1. Мала математична енциклопедія. Еге. Фрід., І. Пастор., І. Рейман., П. Ревес., І. Ружа. Издательсво Академії Наук Угорщини. Будапешт 1976 р. 2. Математичний аналіз. ЧастьIII. В. А. Зоричь. Москва «наука». 1984 р. 3. Допомога за математика для що у ВУЗИ. Під редакцією Р. М. Яковлєва Москва «наука» 1988 г.