Алгебра логіки - це математичний апарат, за допомогою якого записують, обчислюють, спрощують і перетворюють логічні висловлювання.
Творцем алгебри логіки є жив в ХIХ столітті англійський математик Джордж Буль, в честь якого ця алгебра названа булевої алгеброю висловлювань.
Що ж таке логічне висловлювання?
Логічне висловлювання - це любoй оповідної пpедлoженіе, в oтнoшеніі кoтopoгo мoжно oднoзначнo сказати, істіннo oнo або лoжнo.
Так, наприклад, пропозиція "6 - парне число" слід вважати висловом, так як воно істинне. Пропозиція "Рим - столиця Франції" теж висловлювання, так як воно помилкове.
Зрозуміло, не всяке пропозицію є логічним висловлюванням. Висловлюваннями не є, наприклад, пропозиції "учень десятого класу" і "інформатика - цікавий предмет". Перше речення нічого не стверджує про учня, а друге використовує занадто невизначений поняття "цікавий предмет". Запитання й оклику пропозиції також не є висловлюваннями, оскільки говорити про їх істинність або хибність не має сенсу.
Пропозиції типу "в місті A більше мільйона жителів", "у нього блакитні очі" не є висловлюваннями, так як для з'ясування їх істинність або хибність потрібні додаткові відомості: про яке конкретно місті або людині йдеться. Такі пропозиції називаються висказивательной формами.
Висказивательной форма - це оповідної пропозицію, яке прямо або побічно містить хоча б одну змінну і стає висловлюванням, коли всі змінні заміщуються своїми значеннями.
Алгебра логіки розглядає будь-яке висловлювання тільки з однієї точки зору - чи є воно істинним або хибним. Зауважимо, що часто важко встановити істинність висловлювання. Так, наприклад, висловлювання "площа поверхні Індійського океану дорівнює 75 млн кв. км "в одній ситуації можна порахувати хибним, а в іншій - істинним. Помилковим - так як вказане значення неточне і взагалі не є постійним. Справжнім - якщо розглядати його як деяке наближення, прийнятне на практиці.
Терміни, що вживаються в звичайній мові слова і словосполучення "не", "і", "або", "якщо. То", "тоді і тільки тоді" та інші дозволяють з вже заданих висловлювань будувати нові висловлювання. Такі слова і словосполучення називаються логічними зв'язками.
Bисказиванія, утворені з інших висловлювань за допомогою логічних зв'язок, називаються складовими. Висловлювання, які не є складовими, називаються елементарними.
Так, наприклад, з елементарних висловлювань "Петров - лікар", "Петров - шахіст" за допомогою зв'язки "і" можна отримати складене висловлювання "Петров - лікар і шахіст", що розуміється як "Петров - лікар, добре грає в шахи".
За допомогою зв'язки "або" з цих же висловлювань можна отримати складене висловлювання "Петров - лікар або шахіст", що розуміється в алгебрі логіки як "Петров або лікар, або шахіст, або і лікар і шахіст одночасно".
Істинність або хибність одержуваних таким чином складових висловлювань залежить від істинності чи хибності елементарних висловлювань.
Щоб звертатися до логічних висловлювань, їм призначають імена. Нехай через А позначено висловлювання "Тимур поїде влітку на море", а через В - висловлювання "Тимур влітку відправиться в гори". Тоді складене висловлювання "Тимур влітку побуває і на морі, і в горах" можна коротко записати як А і В. Тут "і" - логічна зв'язка, А, В - логічні змінні, які могут приймати тільки два значення - "істина" або " брехня ", що позначаються, відповідно," 1 "і" 0 "
Кожна логічна зв'язка розглядається як операція над логічними висловлюваннями і має свою назву і позначення:
(1) Операція, що виражається словом "не", називається запереченням і позначається рисою над висловлюванням (або знаком щ). Висловлення істинно, коли A помилково, і помилково, коли A істинно. Приклад. "Місяць - супутник Землі" (А); "Місяць - НЕ супутник Землі" ().
(2) Операція, що виражається зв'язкою "і", називається кон'юнкція (лат. Conjunctio - з'єднання) або логічним множенням і позначається крапкою "•" (може також позначатися знаками Щ або ). Висловлення А • В істинно тоді і тільки тоді, коли обидва висловлювання А і В істинні. Наприклад, висловлювання
"10 ділиться на 2 і 5 більше 3"
істинно, а висловлювання
"10 ділиться на 2 і 5 не більш 3",
"10 не ділиться на 2 і 5 більше 3",
"10 не ділиться на 2 і 5 не більш 3"
(3) Операція, що виражається зв'язкою "або" (в неразделітельном, невиключає сенсі цього слова), називається диз'юнкція (лат. Disjunctio - поділ) або логічним складанням і позначається знаком v (або плюсом). Висловлення А v В помилково тоді і тільки тоді, коли обидва висловлювання А і В помилкові. Наприклад, висловлювання
"10 не ділиться на 2 або 5 Не більше 3"
помилково, а висловлювання
"10 ділиться на 2 або 5 більше 3",
"10 ділиться на 2 або 5 Не більше 3",
"10 не ділиться на 2 або 5 більше 3"
(4) Операція, що виражається зв'язками "якщо. то "," з. слід ",". тягне. ", Називається импликацией (лат. Implico - тісно пов'язані) і позначається знаком ®. Висловлення А ® В помилково тоді і тільки тоді, коли А істинно, а В - хибне.
Яким же чином імплікація пов'язує два елементарних висловлювання? Покажемо це на прикладі висловлювань: "даний чотирикутник - квадрат" (А) і "близько даного чотирикутника можна описати коло" (В). Розглянемо складене висловлювання А ® В, що розуміється як "якщо даний чотирикутник квадрат, то біля нього можна описати коло". Є три варіанти, коли висловлювання А ®В істинно:
1. А істинно і В істинно, тобто даний чотирикутник квадрат, і біля нього можна описати коло;
2. А помилково і В істинно, тобто даний чотирикутник не є квадратом, але біля нього можна описати коло (зрозуміло, це справедливо не для всякого чотирикутника);
3. A помилково і B помилково, тобто даний чотирикутник не є квадратом, і біля нього не можна описати коло.
Хибна тільки один варіант: А істинно і В хибно, тобто даний чотирикутник є квадратом, але біля нього можна описати коло.
У звичайній мові зв'язка "якщо. то "описує причинно-наслідковий зв'язок між висловлюваннями. Але в логічних операціях сенс висловлювань не враховується. Розглядається тільки їх істинність або хибність. Тому не треба бентежитися "безглуздістю" імплікацій, утворених висловлюваннями, зовсім не пов'язаними за змістом. Наприклад, такими:
"Якщо президент США - демократ, то в Африці водяться жирафи",
"Якщо кавун - ягода, то в бензоколонці є бензин".
(5) Операція, що виражається зв'язками "тоді і тільки тоді", "необхідно і достатньо", ". Рівносильно.", Називається еквіваленціі або подвійний импликацией і позначається знаком «або
Висловлення А «В істинно тоді і тільки тоді, коли значення А і В збігаються.
"24 ділиться на 6 тоді і тільки тоді, коли 24 ділиться на 3",
"23 ділиться на 6 тоді і тільки тоді, коли 23 ділиться на 3"
істинні, а висловлювання
"24 ділиться на 6 тоді і тільки тоді, коли 24 ділиться на 5",
"21 ділиться на 6 тоді і тільки тоді, коли 21 ділиться на 3"
Висловлювання А і В, що утворюють складене висловлювання А «В, можуть бути абсолютно не пов'язані за змістом, наприклад:" три більше двох "(А)," пінгвіни живуть в Антарктиді "(В). Запереченнями цих висловлювань є висловлювання "зо три не більше двох" (), "пінгвіни не живуть в Антарктиді" (). Освічені з висловлювань А, В складові висловлювання A «B і« істинні, а висловлювання A «і« B - помилкові.
Отже, нами розглянуто п'ять логічних операцій: заперечення, кон'юнкція, диз'юнкція, імплікація і еквіваленція.
Імплікації можна виразити через диз'юнкцію і заперечення. А ® В = v В. еквіваленціі можна виразити через заперечення. диз'юнкцію і кон'юнкцію. А «В = (v В) • (v А).
Таким чином, операцій заперечення, диз'юнкції і кон'юнкції досить, щоб описувати і обробляти логічні висловлювання.
Порядок виконання логічних операцій задається круглими дужками. Але для зменшення числа дужок домовилися вважати, що спочатку виконується операція заперечення ( "не"), потім кон'юнкція ( "і"), після кон'юнкції - диз'юнкція ( "або") і в останню чергу - імплікація.