Булева алгебра. Алгебра логіки. Елементи математичної логіки

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

Логіка

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

Часом кількість умов (ввідних) настільки велике, а взаємозв`язки між ними настільки заплутані і складні, що людський мозок не в змозі «переварити» все відразу. Може знадобитися не один місяць (тиждень, рік) для розуміння того, що відбувається. Але сучасне життя не дає нам таких часових інтервалів на прийняття рішень. І ми вдаємося до допомоги комп`ютерів. І ось тут-то і з`являється алгебра логіки, зі своїми законами і властивостями. Завантаживши всі вихідні дані, ми дозволяємо комп`ютера розпізнати всі взаємозв`язки, виключити протиріччя і знайти задовільне рішення.

Математика і логіка

Найвідоміший Готфрід Вільгельм Лейбніц сформулював поняття «математична логіка», завдання якої були доступні для розуміння тільки вузькому колу науковців. Особливого інтересу цей напрямок не викликало, і до середини XIX століття про математичній логіці знали небагато.

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

Забігаючи наперед, скажемо, що булева алгебра - сама використовувана в сучасному світі частина математики. Так що суперечка свій Буль програв.

Джордж Буль

Сама особистість автора заслуговує окремої уваги. Навіть враховуючи те, що в минулому люди дорослішали раніше нас, все одно не можна не відзначити, що в 16 років Дж. Буль викладав у сільській школі, а до 20 років відкрив власну школу в Лінкольні. Математик відмінно володів п`ятьма іноземними мовами, а у вільний час зачитувався роботами Ньютона і Лагранжа. І все це - про сина простого робітника!

У 1839 році Буль вперше послав свої наукові роботи в Кембриджський математичний журнал. Вченому виповнилося 24 роки. Роботи Буля настільки зацікавили членів Королівського наукового товариства, що в 1844 році він отримав медаль за внесок у розвиток математичного аналізу. Ще кілька опублікованих робіт, у яких були описані елементи математичної логіки, дозволили молодому математику зайняти пост професора в коледжі графства Корк. Нагадаємо, що у самого Буля освіти не було.

Ідея

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

Таким чином, алгебра логіки може бути використана буквально скрізь: у складанні розкладів і написанні інструкцій, аналізі суперечливої інформації про події та визначенні послідовності дій. Найголовніше - зрозуміти, що зовсім неважливо, як ми визначили істинність або хибність висловлювання. Від цих «як» і «чому» потрібно абстрагуватися. Значення має лише констатація факту: істина-брехня.

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

Основні поняття та визначення

Не вдаючись у глибини, розберемося з термінологією. Отже, булева алгебра передбачає наявність:

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

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

Всі висловлювання повинні носити однозначний характер, але вони можуть бути елементарними і складовими. Останні використовують логічні зв`язки. Т. е. В алгебрі суджень складові висловлювання утворюються складанням елементарних допомогою логічних операцій.

Операції булевої алгебри

Ми вже пам`ятаємо, що операції в алгебрі суджень - логічні. Подібно до того, як алгебра чисел використовує арифметичні операції для додавання, віднімання або порівняння чисел, елементи математичної логіки дозволяють скласти складні висловлювання, дати заперечення або обчислити кінцевий результат.

Логічні операції для формалізації і простоти записуються формулами, звичними для нас в арифметиці. Властивості булевої алгебри дають можливість записувати рівняння й обчислювати невідомі. Логічні операції зазвичай записують за допомогою таблиці істинності. Її стовпці визначають елементи обчислень і операцію, яка над ними виробляється, а рядки показують результат обчислень.

Основні логічні дії

Найпоширенішими в булевої алгебри операціями є заперечення (НЕ) і логічні І та АБО. Так можна описати практично всі дії в алгебрі суджень. Вивчимо докладніше кожну з трьох операцій.

Заперечення (не) застосовується тільки до одного елементу (операнду). Тому операцію заперечення називають унарною. Для запису поняття «Не А» використовують такі символи: ¬A, Amacr-macr-macr- або! A. У табличній формі це виглядає так:

Для функції заперечення характерно таке твердження: якщо А істинно, то A - помилково. Наприклад, Місяць обертається навколо Землі - істина- Земля обертається навколо Місяця - брехня.

Логічні множення додавання

Логічне І називають операцією кон`юнкції. Що це означає? По-перше, що застосувати її можна до двох операндам, т. Е. І - бінарна операція. По-друге, що тільки у разі істинності обох операндів (і А, і Б) істинно і сам вираз. Прислів`я «Терпіння і труд все перетруть» передбачає, що тільки обидва чинники допоможуть людині впоратися зі складнощами.

Для запису використовуються символи: Aand-Б, Asdot-Б або AБ.

Кон`юнкція аналогічна множенню в арифметиці. Іноді так і кажуть - логічне множення. Якщо перемножити елементи таблиці по рядках, ми отримаємо результат, аналогічний логічного роздуму.

Диз`юнкцією називають операцію логічного АБО. Вона приймає значення істинності тоді, коли хоча б одне з висловлювань істинно (або А, або Б). Записується це так: Aor-Б, A + Б або A || Б. Таблиці істинності для цих операцій такі:

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

Функції та закони

Отже, ми вже знаємо, які логічні операції використовує булева алгебра. Функції описують всі властивості елементів математичної логіки і дозволяють спрощувати складні складові умови задач. Самим зрозумілим і простим здається властивість відмови від похідних операцій. Під похідними розуміються виключає АБО, імплікація та еквівалентність. Оскільки ми ознайомилися з основними операціями, то і властивості розглянемо теж тільки їх.

Асоціативність означає, що у висловлюваннях типу «і А, і Б, і В» послідовність перерахування операндів не грає ролі. Формулою це запишеться так:

(Aand-Б) and-В = Aand- (Бand-В) = Aand-Бand-В,

(Aor-Б) or-В = Aor- (Бor-В) = Aor-Бor-В.

Як бачимо, це властиво не тільки кон`юнкції, а й диз`юнкції.

Комутативність стверджує, що результат кон`юнкції або диз`юнкції не залежить від того, який елемент розглядався спочатку:

Aand-Б = Бand-A- Aor-Б = Бor-A.

Дистрибутивність дозволяє розкривати дужки в складних логічних виразах. Правила схожі з розкриттям дужок при множенні і складення в алгебрі:

Aand- (Бor-В) = Aand-Бor-Aand-В- Aor-Бand-В = (Aor-Б) and- (Aor-В).

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

Aand-0 = 0, Aand-1 = A- Aor-0 = A, Aor-1 = 1.

Ідемпотентність говорить нам про те, що якщо стосовно двох рівних операндів результат операції виявляється аналогічним, то можна «викинути» зайві ускладнюють хід міркувань операнди. І кон`юнкція, і диз`юнкція є Ідемпотентний операціями.

Бand-Б = Б Бor-Б = Б.

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

Aand-Бor-Б = Б (Aor-Б) and-Б = Б.

Послідовність операцій

Послідовність операцій має важливе значення. Власне, як і для алгебри, існує пріоритетність функцій, які використовує булева алгебра. Формули можуть спрощуватися тільки за умови дотримання значущості операцій. Ранжуючи від самих значущих до незначних, отримаємо таку послідовність:

1. Заперечення.

2. Кон`юнкція.

3. Диз`юнкція, виключає АБО.

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

Як бачимо, тільки заперечення і кон`юнкція не мають рівних пріоритетів. А пріоритет диз`юнкції і виключає АБО рівні, також як і пріоритети імплікації і еквівалентності.

Функції імплікації і еквівалентності

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

Імплікація, або логічне проходження - це висловлювання, в якому одна дія є умовою, а інше - наслідком його виконання. Іншими словами, ця пропозиція із прийменниками «якщо ... то». «Любиш кататися, люби і саночки возити». Т. е. Для катання необхідно затягнути санки на гірку. Якщо ж немає бажання з`їхати з гори, то і санки тягати не доводиться. Записується це так: A-Б або A-Б.

Еквівалентність припускає, що результуюче дія настає тільки в тому випадку, коли істиною є обидва операнда. Наприклад, ніч змінюється днем тоді (і тільки тоді), коли сонце встає з-за обрію. Мовою математичної логіки це твердження записується так: Aequiv-Б, AhArr-Б, A == Б.

Інші закони булевої алгебри

Алгебра суджень розвивається, і багато що зацікавилися вчені сформулювали нові закони. Найбільш відомими вважаються постулати шотландського математика О. де Моргана. Він помітив і дав визначення таким властивостям, як тісне заперечення, доповнення та подвійне заперечення.

Тісна заперечення припускає, що перед дужкою немає жодного заперечення: ні (А чи Б) = Не А чи НЕ Б.

Коли операнд заперечується, незалежно від свого значення, говорять про доповненні:

Бand-¬Б = 0- Бor-¬Б = 1.

І, нарешті, подвійне заперечення саме себе компенсує. Тобто перед операндом або зникає заперечення, або залишається тільки одне.

Як вирішувати тести

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

Що ж зробити для спрощення? Перетворити всі похідні операції в прості. Потім розкрити всі дужки (або навпаки, винести за дужки, щоб скоротити цей елемент). Наступним дією має стати застосування властивостей булевої алгебри на практиці (поглинання, властивості нуля і одиниці і т. Д).

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