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

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

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

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

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

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. Призначення та правила складання таблиць істини

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

І. Основної:

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

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

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

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

ІІ. Додаткової:

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

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