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

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

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

Факультет

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 р.