asyan.org
добавить свой файл
1
Тема: Булева алгебра. Закони алгебри логіки.


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

  2. Логічні схеми.

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


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

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

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

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

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

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

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

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

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

А

А

1

0

0

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

_ _

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

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

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

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

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


А

В

А*В

А

В

А*В

1

1

1

0

1

1

0

0

1

0

1

0

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

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

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

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

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

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

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

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

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

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

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


А

В

А+В

А

В

А+В

1

1

1

0

1

1

0

0

1

0

1

0

З таблиці істинності випливає, що операція диз'юнкція (операція "чи") - логічне додавання - відрізняється від звичайного алгебраїчного додавання. А саме: відрізняється лише першим рядком: 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ІС).

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

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



А

В

А=>В

А

В

А=>В

1

1

1

0

1

1

0

0

1

0

1

1

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

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

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

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

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

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

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

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

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

А≡В.

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

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

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

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

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

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


А

В

А≡В

А

В

А≡В

1

1

1

0

1

0

0

0

1

0

0

1


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

- інверсія

- кон’юнкція

- диз'юнкція

- імплікація

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

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

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

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

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

А

В

С

А*В

А*В+С

А

С

А*С

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

0

0

0

0

0

1

1

1

1

0

0

1

0

1

1

0

0

1

0

1

0

0

0

1

1

1

1

0

1

1

0

1

1

0

0

1

1

0

0

0

0

0

1

0

0

1

0

1

0

1

0

0

0

1

1

1

0

1

1

0

1

0

1

1

1

1

1

0

0

0

0

1


^ 2. Логічні схеми.

Логічний елемент – це схема, реалізуюча логічні операції і, або, не.

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

Інвертор реалізує операції заперечення, чи інверсію. У схемах зображується в такі способи:

Х

 

 

F = не X







 

не







Елемент не. Реалізує логічну операцію не.

Х – вхідний сигнал, F – вихідний сигнал. Тому що вихідний сигнал завжди протилежний вхідному, елемент не й одержав назву «інвентор»

^ У інвертора один вхід і один вихід. Сигнал на виході з’являється тоді, коли на вході його не і, і навпаки.

Кон’юнктор - реалізує операції кон’юнкції. У схемах зображується в такий спосіб:

X

&

 







 

F=X і Y

Y

 

 







 

і




Елемент І. Реалізує логічну операцію І.

X,Y – вхідні сигнали, F – вихідний сигнал.

^ У кон’юнктора один вихід і не менш двох входів. Сигнал на виході з’являється тоді і тільки тоді, коли на усі входи подані сигнали.

Диз’юнктор – реалізує операцію диз’юнкції. У схемах зображується в такий спосіб:

X

1

 










 

F=X або Y

Y

 

 










 

або







Елемент або. Реалізує логічну операцію або.

F = X або Y

X, Y – вхідні сигнали, F – вихідний сигнал.

^ У диз’юнктора один вихід і не менш двох входів. Сигнал на виході з’являється тоді і тільки тоді, коли на усі входи не подані сигнали.

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

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

У 1847 р. англійський математик Джордж Буль, викладач Коркського університету, розробив алгебру логіки. Майже 100 років ця "алгебра висловлень" не була відома широкому колу користувачів. Лише в 1938 році видатний американський математик і інженер Клод Шеннон знайшов, що алгебра логіки застосовна до будь-яким перемінної, котрі можуть приймати тільки два значення. Наприклад, до стану контактів: включене - виключено чи напрузі (чи току): є - ні, якими представляється інформація в ЕОМ.

У результаті алгебра логіки з'явилася математичною основою теорії електричних і електронних перемикальних схем, використовуваних в ЕОМ, тому неї воліють називати не алгеброю логіки, а Булевий алгеброю - по імені її творця.

Приведемо Булеви алгебри. Якщо умовимося писати замість знаків диз'юнкції і кон’юнкції відповідно більш звичні знаки "+" і "*", а замість знака еквівалентності - знак "=", то ми одержимо, що для будь-яких суджень справедливі наступні залежності:

1. А + В = В + А

(Комутативність чи додавання перемістительний закон).

2. А * В = В * А

(Комутативність чи множення сполучний закон).

З. (А + В) + С = А+ (В + С)

(Асоціативність чи додавання розподільний закон додавання).

4. (А * В) * С = А * (В * С)

(Асоціативність чи множення розподільний закон множення).

5. А * (В + С) = А * В + А * С

(Дистрибутивність множення щодо додавання).

6. А + В * С = (А + В)*(А + С)

(Дистрибутивність додавання щодо множення)

7. А + А = А

(Ідемпотентність додавання).

8. А * А = А

(Ідемпотентність множення).

9. А * (В + В) = А (чи А * (А + В) = А; (А + В) * В = А * В)

1О. А + В * В = А (чи А + (А * В) = А; (А *В) + В = А + В)

(Правили поглинання).

11. А + В = А * В (чи А + В = А * В)

12. А * В = А + В (чи А * В = А + В)

(Правила де Моргана).

13. А = А

(Подвійне чи заперечення закон заперечення заперечення).

Судження, істинність яких постійно і не залежить від істинності вхідних у них простих суджень, а визначаються тільки їх структурою, називаються тотожними чи тавтологіями.

Крім того, якщо позначити через 0 судження, що напевно неправда, а через 1 - судження, що свідомо істинно, те мають місце ще такі залежності:

14. А + A = 1

(А чи не А завжди істинно; закон виключення третього).

15. А * A = 0

(А і не А завжди ложно; закон несуперечності).

16. 1 + А = 1

(Істина чи А рівносильна істині - тавтологія тавтології).

17. 1 * А = А

(Істина й А рівносильна істині - тавтологія тавтології).

18. 0 + А = А

(Протиріччя чи А рівносильне А).

19. 0 * А = 0

(Протиріччя й А є протиріччя).

Опанувавши цими основними властивостями суджень, можна спрощувати формули логіки суджень уже формально, подібно тому, як в алгебрі виконуються тотожні перетворення.

Приклад. Спростите судження А * ((В + С) + В * С) + А

А * ((В + С) + В * С) + А = А * (В * С + В * С) + А = А * 1 + А = А + А = 1

по 12 по 14 по 17 по 14

Має А * ((В + С) + В * С) + А = 1.

Для практичних застосувань алгебри суджень важливим є те, що будь-яку формулу можна перетворити так, що:

^ Не будуть використані

Будуть використані

Знаки логічного додавання

Знаки логічного множення

Знаки заперечення і логічного множення

Знаки заперечення і логічного додавання

Приклад. Судження А + В перетворити в еквівалентне йому судження, що не містить знака логічного додавання: А + В = А * В = А * В

по 11 по 13

Приклад. Судження А * В * С перетворити в еквівалентне йому судження, що не містить знака логічного множення:

А * В * С = А * (В + С) = А * В + А * С = А * В + А * С = А + В + А + С =

по 12 по 5 по 13 по 13 по 12 по 12 по 13 по 13

= А + В + А + С = А + В + А + С.

по 13 по 13
Контрольні питання.

  1. Дати визначення: логічні величини, операції, вирази.

  2. Переличити основні логічні операції

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

  4. Призначення та правила складання таблиць істини

  5. Що таке логічний елемент? Перелічити логічні елементи.


Список літератури.

І. Основної:

1. Коляда А.Я. Курс информатики 10-11 класс, Донецк, 2000.

2. Симонович С.В. Информатика. Базовый курс. Харьков, 2001, 638 стр.

3. Семакін С.В. Інформатика, Київ, 2000.

4. Єфімова П.Я. Інформатика. Інформаційні технології, Київ, 2000, 425 стр.
ІІ. Додаткової:

5. Пушкар О.І. Інформатика. Комп'ютерні технології – К.: Видавничий центр «Академія»,2001.