Булева алгебра. Алгебра логікі. Элементы матэматычнай логікі

У сучасным свеце мы ўсё часцей выкарыстоўваем разнастайныя машыны і гаджэты. І не толькі тады, калі неабходна прымяніць літаральна нечалавечую сілу: перамясціць груз, падняць яго на вышыню, вырыць доўгую і глыбокую траншэю і т. Д. Аўтамабілі сёння збіраюць робаты, еду рыхтуюць мультиварки, а элементарныя арыфметычныя разлікі вырабляюць калькулятары. Усё часцей мы чуем выраз «булева алгебра». Мабыць, прыйшоў час разабрацца ў ролі чалавека ў стварэнні робатаў і ўменні машын вырашаць не толькі матэматычныя, але і лагічныя задачы.

логіка

У перакладзе з грэцкага логіка - гэта спарадкаваная сістэма мыслення, якая стварае ўзаемасувязі паміж зададзенымі ўмовамі і дазваляе рабіць высновы, грунтуючыся на перадумовах і здагадках. Даволі часта мы пытаемся адно ў аднаго: «Лагічна?» Атрыманы адказ пацвярджае нашы здагадкі альбо крытыкуе ход думкі. Але працэс не спыняецца: мы працягваем разважаць.

Часам колькасць умоў (ўводных) настолькі вялікае, а ўзаемасувязі паміж імі гэтак заблытанасці і складаныя, што чалавечы мозг не ў стане «пераварыць» усё адразу. Можа спатрэбіцца не адзін месяц (тыдзень, год) для разумення таго, што адбываецца. Але сучасная жыццё не дае нам такіх часовых інтэрвалаў на прыняцце рашэнняў. І мы звяртаемся да дапамогі кампутараў. І вось тут-то і з'яўляецца алгебра логікі, са сваімі законамі і ўласцівасцямі. Загрузіўшы ўсе зыходныя дадзеныя, мы дазваляем кампутара распазнаць ўсе ўзаемасувязі, выключыць супярэчнасці і знайсці здавальняючы рашэнне.

Матэматыка і логіка

Найвядомы Готфрыд Вільгельм Лейбніц сфармуляваў паняцце «матэматычная логіка», задачы якой былі даступныя для разумення толькі вузкаму колу вучоных. Асаблівай цікавасці гэты кірунак не выклікала, і да сярэдзіны XIX стагоддзя пра матэматычнай логіцы ведалі нямногія.

Вялікую цікавасць у навуковых супольнасцях выклікаў спрэчка, у якім ангелец Джордж Буль заявіў пра свой намер стварыць падзел матэматыкі, які не мае абсалютна ніякага практычнага прымянення. Як мы памятаем з гісторыі, у гэты час актыўна развівалася прамысловая вытворчасць, распрацоўваліся разнастайныя дапаможныя машыны і станкі, т. Е. Ўсе навуковыя адкрыцці мелі практычную накіраванасць.

Забягаючы наперад, скажам, што булева алгебра - самая выкарыстоўваная ў сучасным свеце частка матэматыкі. Так што спрэчка свой Буль прайграў.

Джордж Буль

Сама асоба аўтара заслугоўвае асобнай увагі. Нават улічваючы тое, што ў мінулым людзі сталелі раней за нас, усё роўна нельга не адзначыць, што ў 16 гадоў Дж. Буль выкладаў у вясковай школе, а да 20 гадоў адкрыў уласную школу ў Лінкольне. Матэматык выдатна валодаў пяццю замежнымі мовамі, а ў вольны час зачытваўся працамі Ньютана і Лагранжа. І ўсё гэта - пра сына простага рабочага!

У 1839 году Буль ўпершыню паслаў свае навуковыя працы ў Кембрыджскі матэматычны часопіс. Навукоўцу споўнілася 24 гады. Работы Буля настолькі зацікавілі членаў Каралеўскага навуковага таварыства, што ў 1844 годзе ён атрымаў медаль за ўклад у развіццё матэматычнага аналізу. Яшчэ некалькі апублікаваных прац, у якіх былі апісаны элементы матэматычнай логікі, дазволілі маладому матэматыку заняць пасаду прафесара ў каледжы графства Корк. Нагадаем, што ў самога Буля адукацыі не было.

ідэя

У прынцыпе, булева алгебра вельмі простая. Існуюць выказванні (лагічныя выразы), якія, з пункту гледжання матэматыкі, можна вызначыць толькі двума словамі: «ісціна» або «хлусня». Напрыклад, вясной дрэвы расцвітаюць - ісціна, летам ідзе снег - хлусня. Уся хараство гэтай матэматыкі заключаецца ў тым, што няма строгай неабходнасці выкарыстоўваць толькі чысла. Для алгебры меркаванняў цалкам падыходзяць любыя выказванні з адназначным сэнсам.

Такім чынам, алгебра логікі можа быць выкарыстана літаральна ўсюды: у складанні раскладаў і напісанні інструкцый, аналізе супярэчлівай інфармацыі аб падзеях і вызначэнні паслядоўнасці дзеянняў. Самае галоўнае - зразумець, што зусім няважна, як мы вызначылі праўдзівасць або памылковасць выказванні. Ад гэтых «як» і «чаму» трэба абстрагавацца. Значэнне мае толькі канстатацыя факту: ісціна-хлусня.

Безумоўна, для праграмавання важныя функцыі алгебры логікі, якія запісваюцца адпаведнымі знакамі і сімваламі. І вывучыць іх - гэта значыць асвоіць новы замежную мову. Няма нічога немагчымага.

Асноўныя паняцці і азначэнні

Не ўдаючыся ў глыбіні, разбярэмся з тэрміналогіяй. Такім чынам, булева алгебра мяркуе наяўнасць:

• выказванняў;
• лагічных аперацый;
• функцый і законаў.

Выказванні - любыя сцвярджальныя выразы, якія не могуць быць вытлумачаны двухзначны. Яны запісваюцца ў выглядзе лікаў (5> 3) ці фармулююцца звыклымі словамі (слон - самае вялікае млекакормячых). Пры гэтым фраза «у жырафа няма шыі» таксама мае права на існаванне, толькі булева алгебра вызначыць яе як "хлусьня".

Усе выказванні павінны насіць адназначны характар, але яны могуць быць элементарнымі і складовымі. Апошнія выкарыстоўваюць лагічныя звязкі. Т. е. У алгебры меркаванняў складовыя выказванні утвараюцца складаннем элементарных з дапамогай лагічных аперацый.

Аперацыі булевай алгебры

Мы ўжо памятаем, што аперацыі ў алгебры меркаванняў - лагічныя. Падобна таму, як алгебра лікаў выкарыстоўвае арыфметычныя аперацыі для складання, аднімання або параўнання лікаў, элементы матэматычнай логікі дазваляюць скласці складаныя выказванні, даць адмаўленне ці вылічыць канчатковы вынік.

Лагічныя аперацыі для фармалізацыі і прастаты запісваюцца формуламі, звыклымі для нас у арыфметыцы. Ўласцівасці булевай алгебры даюць магчымасць запісваць ўраўненні і вылічаць невядомыя. Лагічныя аперацыі звычайна запісваюць з дапамогай табліцы праўдзівасці. Яе слупкі вызначаюць элементы вылічэнняў і аперацыю, якая над імі вырабляецца, а радкі паказваюць вынік вылічэнняў.

Асноўныя лагічныя дзеянні

Самымі распаўсюджанымі ў булевай алгебры аперацыямі з'яўляюцца адмаўленне (НЕ) і лагічныя Ды i АБО. Так можна апісаць практычна ўсе дзеянні ў алгебры меркаванняў. Вывучым падрабязней кожную з трох аперацый.

Адмаўленне (не) ужываецца толькі да аднаго элементу (аперанда). Таму аперацыю адмаўлення называюць Унарный. Для запісу паняцця "не А» выкарыстоўваюць такія сімвалы: ¬A, A¯¯¯ або! A. У таблічнай форме гэта выглядае так:

Для функцыі адмаўлення характэрна такое сцвярджэнне: калі А праўдзіва, то A - фальшыва. Напрыклад, Месяц круціцца вакол Зямлі - ісціна; Зямля круціцца вакол Месяца - хлусня.

Лагічныя множанне і складанне

Лагічнае І называюць аперацыяй конъюнкции. Што гэта значыць? Па-першае, што ўжыць яе можна да двух аперанд, т. Е. І - бінарная аперацыя. Па-другое, што толькі ў выпадку праўдзівасці абодвух аперанд (і А, і Б) праўдзівае і сам выраз. Прыказка «Цярпенне і праца ўсё перетрут» мяркуе, што толькі абодва фактару дапамогуць чалавеку справіцца са складанасцямі.

Для запісу выкарыстоўваюцца сімвалы: A∧Б, A⋅Б або A && Б.

Конъюнкция аналагічная множаньню ў арыфметыцы. Часам так і кажуць - лагічны множанне. Калі перамнажаць элементы табліцы па радках, мы атрымаем вынік, аналагічны лагічнага разважання.

Дизъюнкцией называюць аперацыю лагічнага АБО. Яна прымае значэнне праўдзівасці тады, калі хаця б адно з выказванняў праўдзіва (або А, ці Б). Запісваецца гэта так: A∨Б, A + Б або A || Б. Табліцы праўдзівасці для гэтых аперацый такія:

Дизъюнкция падобная арыфметычным складанні. Аперацыя лагічнага складання мае толькі адно абмежаванне: 1 + 1 = 1. Але мы ж памятаем, што ў лічбавым фармаце матэматычная логіка абмежаваная 0 і 1 (дзе 1 - ісціна, 0 - хлусня). Напрыклад, зацвярджэнне «ў музеі можна ўбачыць шэдэўр ці сустрэць цікавага суразмоўцы» азначае, што можна паглядзець творы мастацтва, а можна пазнаёміцца з цікавым чалавекам. У той жа час, не выключаны варыянт адначасовага здзяйсненні абодвух падзей.

Функцыі і законы

Такім чынам, мы ўжо ведаем, якія лагічныя аперацыі выкарыстоўвае булева алгебра. Функцыі апісваюць усе ўласцівасці элементаў матэматычнай логікі і дазваляюць спрашчаць складаныя складовыя ўмовы задач. Самым зразумелым і простым здаецца ўласцівасць адмовы ад вытворных аперацый. Пад вытворнымі разумеюцца якое выключае АБО, імплікацыі і эквівалентнасць. Паколькі мы азнаёміліся толькі з асноўнымі аперацыямі, то і ўласцівасці разгледзім таксама толькі іх.

Асацыятыўнасць азначае, што ў выказваннях накшталт "і А, і Б, і В» паслядоўнасць пералічэння аперанд не гуляе ролі. Формулай гэта запішацца так:

(A∧Б) ∧В = A∧ (Б∧В) = A∧Б∧В,

(A∨Б) ∨В = A∨ (Б∨В) = A∨Б∨В.

Як бачым, што гаворка тут не толькі конъюнкции, але і дизъюнкции.

Коммутативность сцвярджае, што вынік конъюнкции або дизъюнкции не залежыць ад таго, які элемент разглядаўся спачатку:

A∧Б = Б∧A; A∨Б = Б∨A.

Дыстрыбутыўнага дазваляе раскрываць дужкі ў складаных лагічных выразах. Правілы падобныя з раскрыццём дужак пры памнажэньні і складанні ў алгебры:

A∧ (Б∨В) = A∧Б∨A∧В; A∨Б∧В = (A∨Б) ∧ (A∨В).

Ўласцівасці адзінкі і нуля, якія могуць быць адным з аперанд, таксама аналагічныя алгебраічным множаньню на нуль або адзінку і складанні з адзінкай:

A∧0 = 0, A∧1 = A; A∨0 = A, A∨1 = 1.

Идемпотентность кажа нам пра тое, што калі ў адносінах да двух роўных аперанд вынік аперацыі аказваецца аналагічным, то можна «выкінуць» лішнія ўскладняюць ход разважанняў аперанды. І конъюнкция, і дизъюнкция з'яўляюцца идемпотентными аперацыямі.

Б∧Б = Б; Б∨Б = Б.

Паглынанне таксама дазваляе нам спрашчаць ўраўненні. Паглынанне сцвярджае, што калі да выказвання з адным аперандам ўжываецца іншая аперацыя з гэтым жа элементам, вынікам аказваецца аперанд з паглынальнай аперацыі.

A∧Б∨Б = Б; (A∨Б) ∧Б = Б.

паслядоўнасць аперацый

Паслядоўнасць аперацый мае немалаважнае значэнне. Уласна, як і для алгебры, існуе прыярытэтнасць функцый, якія выкарыстоўвае булева алгебра. Формулы могуць спрашчацца толькі пры ўмове захавання значнасці аперацый. Па ранжыру ад самых значных да нязначных, атрымаем такую паслядоўнасць:

1. Адмаўленне.

2. Конъюнкция.

3. Дизъюнкция, якое выключае АБО.

4. імплікацыі, эквівалентнасць.

Як бачым, толькі адмаўленне і конъюнкция не маюць роўных прыярытэтаў. А прыярытэт дизъюнкции і які выключае АБО роўныя, таксама як і прыярытэты імплікацыі і эквівалентнасці.

Функцыі імплікацыі і эквівалентнасці

Як мы ўжо казалі, акрамя асноўных лагічных аперацый матэматычная логіка і тэорыя алгарытмаў выкарыстоўвае вытворныя. Часцей за ўсё ўжываюцца імплікацыі і эквівалентнасць.

Імплікацыі, або лагічнае прытрымліванне - гэта выказванне, у якім адно дзеянне з'яўляецца умовай, а іншае - следствам яго выканання. Іншымі словамі, гэтую прапанову з падставамі «калі ... то». «Любіш катацца, любі і саначкі вазіць». Т. е. Для катання неабходна зацягнуць санкі на горку. Калі ж няма жадання з'ехаць з гары, то і санкі цягаць не прыходзіцца. Запісваецца гэта так: A → Б або A⇒Б.

Эквівалентнасць мяркуе, што выніковае дзеянне наступае толькі ў тым выпадку, калі ісцінай з'яўляюцца абодва аперанда. Напрыклад, ноч змяняецца днём тады (і толькі тады), калі сонца ўстае з-за гарызонту. На мове матэматычнай логікі гэта зацвярджэнне запісваецца так: A≡Б, A⇔Б, A == Б.

Іншыя законы булевай алгебры

Алгебра меркаванняў развіваецца, і многія якія зацікавіліся навукоўцы сфармулявалі новыя законы. Найбольш вядомымі лічацца пастулаты шатландскага матэматыка А. дэ Моргана. Ён заўважыў і даў вызначэнне такім уласцівасцям, як цеснае адмаўленне, дадатак і падвойнае адмаўленне.

Цеснае адмаўленне мяркуе, што перад дужкай няма ніводнага адмаўлення: ня (А ці Б) = ня А ці НЕ Б.

Калі аперанд адмаўляецца, незалежна ад свайго значэння, кажуць аб дапаўненні:

Б∧¬Б = 0; Б∨¬Б = 1.

І, нарэшце, падвойнае адмаўленне само сябе кампенсуе. Г.зн. перад аперандам альбо знікае адмаўленне, альбо застаецца толькі адно.

Як вырашаць тэсты

Матэматычная логіка мае на ўвазе спрашчэнне зададзеных раўнанняў. Гэтак жа, як і ў алгебры, неабходна спачатку максімальна палегчыць ўмова (пазбавіцца ад складаных ўводных і аперацый з імі), а затым прыступіць да пошуку дакладнага адказу.

Што ж зрабіць для спрашчэння? Пераўтварыць ўсе вытворныя аперацыі ў простыя. Затым раскрыць усе дужкі (ці наадварот, вынесці за дужкі, каб скараціць гэты элемент). Наступным дзеяннем павінна стаць прымяненне уласцівасцяў булевай алгебры на практыцы (паглынанне, ўласцівасці нуля і адзінкі і т. Д).

У канчатковым выніку раўнанне павінна складацца з мінімальнай колькасці невядомых, аб'яднаных простымі аперацыямі. Лягчэй за ўсё шукаць рашэнне, калі дамагчыся вялікай колькасці цесных адмаўленьняў. Тады адказ ўсплыве як бы сам сабой.