Технічний університет Молдови
РЕФЕРАТ З ПРОГРАМУВАННЯ
ТЕМА: Булева алгебра.
Факультет CIM
Група С - 092
Підготував Пліс Володимир.
Кишинів 1999
План:
Введення.
1) Предмет математичної логіки.
2) Калькуляція висловлювань.
3) Висновок.
Бібліографія.
ВСТУП
У даному рефераті я спробую розкрити, деякі аспекти булевої алгебри. Математична логіка є сучасною формою, так званої формальної логіки, яка застосовує математичні методи для дослідження свого предмета. (Інші її назви: символічна логіка, теоретична логіка, логістика.) У формальній логіці і, відповідно, в математичній логіці, зібрані результати закони структури правильних висновків. Висновок є таким розумовим процесом, в результаті якого з'являються нові відкриття на підставі вже наявних (які передбачаються правильними), без практичних досліджень. У дійсності, нове відкриття, отриманий в результаті виведення, (так званий остаточний висновок) у прихованій формі знаходиться в попередньо наявних знаннях, в так званих передумовах.
МАТЕМАТИЧНА ЛОГІКА
ПРЕДМЕТ МАТЕМАТИЧНОЇ ЛОГІКИНайпростіші закономірності висновків відкривалися людством емпіричним шляхом в ході суспільного виробництва (наприклад, найпростіші співвідношення арифметики і геометрії). Відкриття більш складних законів пов'язано з результатами науки формальної логіки. Перше велике узагальнення формальної логіки належить Арістотелеві. У формальної логіки, з самого початку застосовувалися (у поодиноких випадках) математичні методи, але розвиток логіки не встигало за застосуванням таких методів в порівнянні з іншими областями математики. Тому формальна логіка відстала від потреб науки (в першу чергу від вимог математики); відставання виявилося особливо очевидним в нову еру. Головними недоліками формальної логіки були наступні.
1. Вона не зуміла привести закони висновків до невеликої кількості надійних логічних законів, тому підтвердила правильність деяких висновків на основі експериментів, які пізніше були спростовані прикладами, які доводять протилежне.
2. Вона була нездатна аналізувати значну частину висновків, застосовуваних у повсякденному і науковому житті; довести правильність чи неправильність таких висновків. (Наприклад, не могла довести, що з правильності пропозиції «Кожна трапеція є чотирикутником» випливає правильність пропозиції «Хто малює трапецію, той малює чотирикутник).
Завдання математизації формальної логіки була поставлена і здійснена Лейбніцем. Його роботу продовжили математики XIX століття. На рубежі століть з відкриттям суперечностей у теорії множин (див. гл. «Теорія множин») розвиток математичної логіки отримало широкий розмах. В даний час результати математичної логіки використовуються в усіх традиційних областях формальної логіки; відкриті абсолютно нові області. В даний час «традиційна» формальна логіка в порівнянні з математичною логікою має значення тільки для історії науки.
Математична логіка не претендує на відкриття законів мислення взагалі, або ще в меншому ступені на аналіз філософських проблем, пов'язаних з людським мисленням. Ці питання більше відносяться до «логікою» (у більш загальному сенсі слова) і до філософії. (Надалі під словом «логіка» будемо мати на увазі математичну логіку.)
ЩО ТАКЕ ВИСНОВОК?
Для більш точного визначення предмета математичної логіки слід було б уточнити, що мається на увазі під терміном логічно правильного висновку. Щоб сформулювати хоча б одне тимчасове визначення, розглянемо приклад виведення. (Відповідно до традиційною формою запису, передумови відокремлюються від остаточного виведення горизонтальній рисою):
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 р.