Алгебра суджень

Булева алгебра.

Алгебра суджень.

3. Закони алгебри логіки.

Логічні величини, операції, вирази.

• Логічні величини.

Логічні величини: поняття, що виражаються словами: ІСТИНА, НЕПРАВДА (true, false). Отже, істинність висловлень виражається через логічні величини.

Логічна константа: ІСТИНА чи НЕПРАВДА.

Логічна змінна: символічно позначена логічна величина. Отже, якщо відомо, що A, B, X, Y і ін. - перемінні логічні величини, те це значить, що вони можуть приймати значення тільки ІСТИНА чи НЕПРАВДА.

Логічний вираз - складне висловлення. Складне висловлення будується з простих за допомогою логічних операцій (зв'язувань).

• Логічні операції.

Інверсія (заперечення) Маючи судження А, можна утворити нове судження, що читається як „не А” чи „невірно, що А”. Для позначення заперечення судження вживають символ „│” і пишуть │А. У програмуванні операцію запереченню позначають „NOT” (від англійського „не”). Іноді позначають заперечення ще так: A.

Таблицю істинності заперечення А:

А	А

Тому що можливі тільки два значення перемінної, то завжди:

_ _

1 = 0 и 0 = 1

Нехай судження А = „Ми любимо інформатику”, тоді заперечення буде: A = „Ми не любимо інформатику”. Заперечення A має значення „щире”, якщо вихідне судження А помилкове. І навпаки, A має значення „помилкове”, якщо вихідне судження А щире.

Цю операцію називають також інверсією (чи логічним "не")

Кон'юнкція двох висловлень А и В відповідає союзу "і". Вона позначається символами „^” чи „&” (читається „ЭТ”). У програмуванні цю операцію позначають „AND” (від англійського „і”). Чи символом „*”.

Запис А*В читається так: „Кон'юнкція суджень А,В”, чи „А кон'юнкція В”, чи "судження А і судження В", чи, зовсім коротко, "А і В".

Таблиця Істинності кон’юнкції двох суджень А і В така:

А	В	А*В	А	В	А*В

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

А = "Сьогодні сонячний день",

В = "Остап пішов купатися".

Тоді кон’юнкція А*В є судження:

Х = "Сьогодні сонячний день, і Остап пішов купатися".

Це нове судження Х буде щирим, якщо одночасно і судження А щире.

У повсякденній мові іноді в ролі союзу "і" виступають союзи "а", "але" Наприклад, "Богдан був переможцем, а Степан зайняв друге місце".

Зв'язування "і" у складених судженнях завжди припускає одночасну істинність складових суджень.

Диз'юнкція двох суджень А и В відповідає союзу "чи" і позначається символом "V" чи символом "+". У програмуванні ця операція позначається союзом "ОR" (від англійського "чи") чи символом "+".

Запис А+В може бути прочитана так: "Диз'юнкція суджень А, В", чи "А диз'юнкція В", чи "судження А чи судження В", чи, зовсім коротко, "А чи В".

Таблиця істинності диз'юнкції двох суджень А и В така:

А	В	А+В	А	В	А+В

З таблиці істинності випливає, що операція диз'юнкція (операція "чи") - логічне додавання - відрізняється від звичайного алгебраїчного додавання. А саме: відрізняється лише першим рядком: 1+1=1. Результат цей також не збігається з додаванням двоїчних чисел (там було: 1+1=10). Це наслідок того, що 1 є не числом "один", а тільки символом, зміст якого був пояснений вище. Якщо маються дві щирі величини, то результатом їхнього додавання буде щира величина, але не може бути ні двічі істинно, ні напівістинно! Саме тому 1+1=1.

1. Наприклад, нехай дані судження:

А = "сніг піде вночі",

В = "сніг піде ранком".

Тоді судження Х = А + В= "Сніг піде чи вночі ранком".

Зв'язування "чи" відіграє об'єднуючу роль.

2. Наприклад, дані судження:

А = "Він прийде сьогодні",

В = "Він прийде завтра".

Судження Х = А + В = "Він прийде чи сьогодні завтра". В останньому випадку зв'язування "чи" грає тільки роз'єднує роль (її можна замінити поділяючим "або"). Можливі тільки два варіанти:

1. "Він прийде сьогодні", або

2. "Він прийде завтра".

Така диз'юнкція називається строгою чи розділеною диз'юнкцією, вона щира в тім і тільки в тому випадку, коли одне із суджень істинно, а інше НЕПРАВДА. У цьому випадку А+В читається "строго А чи В" чи "або А або В". У програмуванні таке що виключає "чи" позначають - "XOR".

Строга диз'юнкція може бути виражена через уже розглянуті нами об'єднуючу диз'юнкцію і кон’юнкцію:

Х=(А*В)+(A*В)

Дужки, як завжди, регулюють порядок виконання логічних операцій. Така диз'юнкція буде мати таку ж таблицю істинності, як і об'єднуюча, якщо в ній перший рядок 1+1=1 замінити на рядок 1+1=0.

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

1) або "ті учні, що бажають цього";

2) або "ті учні, яких запросив викладач".

Отже, загальне правило:

Складене судження зі зв'язуванням "чи" вважається щирим, якщо істинно хоча б одне зі складених суджень, і вважається помилковим, якщо помилкові всі його складові.

Імплікація двох суджень відповідає союзу "якщо..., те..." і позначається символами "=>" чи " ". У програмуванні саму логічну операцію позначають "ІМР", а союз "якщо..., те..." заміняють зв'язуванням "ІF..., ТНЕN..." (мовою ВАSІС).

Запис А=>В може бути прочитана так: "Якщо А, те В", чи "Якщо вірне судження А, те вірно і судження В", а також більш коротко "З А випливає В", "А волоче В", "В випливає з А" і ін. Іноді неї називають логічним висновком.

Таблиця істинності імплікацій двох висловлень така:

А	В	А=>В	А	В	А=>В

Ця таблиця показує, що з щирого висловлення А випливає тільки щире висловлення В. Помилкове ж висловлення А імплікує як помилкове, так і щире висловлення В (говорять: "З неправди - усе, що завгодно").

По суті справи, імплікація лежить в основі процесу висновку умовиводів. Тому в імплікації А=>В судження А називають умовою чи посилкою імплікації, а В - висновком чи наслідком імплікації.

Наприклад, що нехай істинно випливає судження:

А = "трикутник рівносторонній".

Тоді, як відомо, щире судження:

В = "трикутник рівнокутний",

тому імплікація:

Х = А=>В "якщо трикутник рівносторонній, то він рівнокутний" щира.

Еквівалентність. Може виявитися, що два судження А и В одночасно щирі чи одночасно помилкові; тоді назвемо їх рівносильними (еквівалентними) і умовимося писати:

А≡В.

Цей запис читають так: "Судження А еквівалентне судженню В", чи "А необхідно і досить для В".

Наприклад, судження:

А = "цей трикутник рівносторонній";

В = "цей трикутник рівнокутний" -

будуть рівносильними, так що А≡В.

У програмуванні логічну еквівалентність позначають символами "EQV". Таблиця істинності для еквівалентності така:

А	В	А≡В	А	В	А≡В

• Порядок виконання логічних операцій.

- інверсія

- кон’юнкція

- диз'юнкція

- імплікація

- еквівалентність

Пріоритет виконання операцій позначається дужками.

• Таблиці істини.

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

Таблиця істинності для формули (А*В+С) + (A*С)

А	В	С	А*В	А*В+С	А	С	А*С	(А*В+С) + (A*С)

Дата добавления: 2014-01-07