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

РЕФЕРАТ З ПРОГРАМУВАННЯ

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

Факультет 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 р.