Алгебра логіки

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

Практичне заняття

Алгебра логіки

Мета заняття: вивчити основи алгебри логіки.

Питання, що розглядаються:

- Основні поняття: проста і складне висловлювання, логічні операції, логічні вирази, логічна функція.

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

- Алгоритм побудови таблиць істинності.

- Схеми базових логічних елементів.

- Закони логіки

Основні поняття алгебри логіки

Логічною основою комп'ютера є алгебра логіки, яка розглядає логічні операції над висловлюваннями.

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

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

Приклад 1. «3 - просте число» є висловлюванням, оскільки воно є істинним.

Не будь-яке речення є логічним висловлюванням.

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

Приклад 2. «x+2>5» - висловлювальна форма, яка при x>3 є істинною, а в протилежному випадку хибною.

Алгебра логіки розглядає будь-яке висловлювання з однієї точки зору - є воно істинним або хибним.

Слова і словосполучення «не», «і», «або», «якщо ..., то», «тоді і тільки тоді» та інші дозволяють з вже заданих висловів будувати нові висловлювання. Такі слова і словосполучення називаються логічними зв'язками.

Висловлювання, утворені з інших висловлювань за допомогою логічних зв'язок, називаються складними (складними). Висловлювання, які не є складовими, називаються елементарними (простими).

Приклад. Вислів «Число 6 ділиться на 2» - просте висловлювання. Вислів «Число 6 ділиться на 2, і число 6 ділиться на 3» - складене висловлювання, утворене з двох простих за допомогою логічної зв'язки «і».

Істинність або хибність складових висловлювань залежить від істинності чи хибності елементарних висловлювань, з яких вони складаються.

Щоб звертатися до логічних висловлювань, їм призначають імена.

Приклад 3. Позначимо через А просте висловлювання «число 6 ділиться на 2», а через В просте висловлювання «число 6 ділиться на 3». Тоді складене висловлювання «Число 6 ділиться на 2, і число 6 ділиться на 3» можна записати як «А і В». Тут «і» - логічна зв'язка, А, В - логічні змінні, які можуть приймати тільки два значення - «істина» або «брехню», що позначаються, відповідно, «1» і «0».

Кожна логічна зв'язка розглядається як операція над логічними висловленнями і має свою назву та позначення (табл. 1).

Таблиця 1

Позначення операції	Читається	Назва операції	Альтернативні позначення
¬	НЕ	Заперечення (інверсія)	Риска зверху
	І	Кон'юнкція (логічне множення)	&
	АБО	Диз'юнкція (логічне додавання)	+
XOR	АБО … АБО	Виключаюче АБО (додавання по модулю 2)

НЕ Операція, що виражається словом «не», називається запереченням і позначається рискою над висловлюванням (або знаком ¬). Висловлювання ¬А істинне, коли A помилкове, і помилкове, коли A істинне.

Приклад 4. Нехай А = «Сьогодні похмуро», тоді ¬А = «Сьогодні не похмуро».

І Операція, що виражається зв'язкою «і», називається кон'юнкцією (лат. conjunctio - з'єднання) або логічним множенням і позначається крапкою « * » (може також позначатися знаками або &). Висловлювання А * В істинне тоді і тільки тоді, коли обидва висловлювання А і В істинні.

Приклад 5. Вислів «Число 6 ділиться на 2, і число 6 ділиться на 3» - істинний, а вислів «Число 6 ділиться на 2, і число 6 більше 10» - хибний.

АБО Операція, що виражається зв'язкою «або» (в прямому сенсі цього слова), називається диз'юнкцією (лат. disjunctio - поділ) або логічним додаванням і позначається знаком (або плюсом). Висловлювання АВ хибне тоді і тільки тоді, коли обидва висловлювання А і В хибні.

Приклад 6. Вислів «Число 6 ділиться на 2 або число 6 більше 10» - істинний, а вислів «Число 6 ділиться на 5 або число 6 більше 10» - хибний.

АБО ... АБО Операція, що виражається зв'язками «Або ... або», називається виключаюче АБО чи додавання по модулю 2 і позначається XOR або . Висловлювання АВ істинне тоді і тільки тоді, коли значення А і В не збігаються.

Приклад 7. Вислів «Число 6 або непарне або ділиться без залишку на 2» є істинним, а вислів «Або число 6 парне або число 6 ділиться на 3» - помилковий, так як істинні обидва висловлювання, що входять в нього.

Зауваження.

Імплікацію можна виразити через диз'юнкцію і заперечення:

.

Виключаюче АБО можна виразити через заперечення, диз'юнкцію і кон'юнкцію:

.

алгебра логіка диз'юнкція

Висновок. Операцій заперечення, диз'юнкції і кон'юнкції достатньо, щоб описувати й обробляти логічні висловлювання.

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

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

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

Логічна функція - це функція логічних змінних, яка може приймати тільки два значення: 0 або 1. У свою чергу, сама логічна змінна (аргумент логічної функції) теж може приймати тільки два значення: 0 або 1.

Приклад 8. - логічна функція двох змінних A і B.

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

Таблиця 2. Таблиця істинності основних логічних операцій

А	В
1	1	0	1	1	0
1	0	0	0	1	1
0	1	1	0	1	1
0	0	1	0	0	0

Спираючись на дані таблиці істинності основних логічних операцій можна складати таблиці істинності для більш складних формул.

Алгоритм побудови таблиць істинності для складних виразів:

1. Визначити кількість рядків:

кількість рядків = 2ⁿ + рядок для заголовка;

n - кількість простих висловлювань.

2. Визначити кількість стовпців:

кількість стовпців = кількість змінних + кількість логічних операцій;

визначити кількість змінних (простих виразів);

визначити кількість логічних операцій і послідовність їх виконання.

Приклад 9. Скласти таблицю істинності для формули І-НЕ, яку можна записати так: .

Рішення:

Визначити кількість рядків:

На вході два простих висловлювання: А і В, тому n = 2 і кількість рядків = 2² +1 = 5.

2. Визначити кількість стовпців:

Вираз складається з двох простих виразів (A і B) і двох логічних операцій (1 інверсія, 1 кон'юнкція), тобто кількість стовпців таблиці істинності = 4.

3. Заповнити стовпці з урахуванням таблиць істинності логічних операцій (табл. 3).

Таблиця 3. Таблиця істинності для логічної операції

А	В
1	1	1	0
1	0	0	1
0	1	0	1
0	0	0	1

Подібним чином можна скласти таблицю істинності (табл. 2.4) для формули АБО-НЕ, яку можна записати так: .

Таблиця 4. Таблиця істинності для логічної операції

А	В
1	1	1	0
1	0	1	0
0	1	1	0
0	0	0	1

Примітка. І-НЕ називають також «штрих Шеффера» (позначають |) або «антикон'юнкція»; АБО-НЕ називають також «стрілка Пірса» (позначають v) або «антидиз'юнкція».

Приклад 10. Скласти таблицю істинності логічного виразу .

Рішення:

1. Визначити кількість рядків:

На вході два простих висловлювання: А і В, тому n = 2 і кількість рядків = 2² +1 = 5.

2. Визначити кількість стовпців:

Вираз складається з двох простих виразів (A і B) і п'яти логічних операцій (2 інверсії, 2 кон'юнкції, 1 диз'юнкція), тобто кількість стовпців таблиці істинності = 7.

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

3. Заповнити стовпці з урахуванням таблиць істинності логічних операцій (табл. 5).

Таблиця 5. Таблиця істинності для логічної операції

А	В					C
1	1	0	0	0	0	0
1	0	0	1	0	1	1
0	1	1	0	1	0	1
0	0	1	1	0	0	0

Логічні формули можна також представляти за допомогою мови логічних схем.

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

- логічний елемент «І» - логічне множення - кон'юнктор;

- логічний елемент «АБО» - логічне додавання - диз'юнктор;

- логічний елемент «НЕ» - інверсію - інвертор.

Рисунок 1 - Базові логічні елементи

Оскільки будь-яка логічна операція може бути представлена у вигляді комбінації трьох основних, будь-які пристрої комп'ютера, що виконують обробку або зберігання інформації, можуть бути зібрані з базових логічних елементів, як з "цеглинок".

Логічні елементи комп'ютера оперують з сигналами, що представляють собою електричні імпульси. Є імпульс - логічний зміст сигналу - 1, немає імпульсу - 0. На входи логічного елемента надходять сигнали-значення аргументів, на виході з'являється сигнал-значення функції.

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

Алгоритм побудови логічних схем:

1. Визначити число логічних змінних.

2. Визначити кількість логічних операцій і їх порядок.

3. Зобразити для кожної логічної операції відповідний їй логічний елемент.

4. З'єднати логічні елементи в порядку виконання логічних операцій.

Приклад 11. За заданою логічною функцією побудувати логічну схему.

Рішення:

1. Число логічних змінних = 2 (A і B).

2. Кількість операцій = 5 (2 інверсії, 2 кон'юнкції, 1 диз'юнкція). Спочатку виконуються операції інверсії, потім кон'юнкції, в останню чергу операція диз'юнкції.

3. Схема буде містити 2 інвертора, 2 кон'юнктора і 1 диз'юнктор.

4. Побудову треба починати з логічної операції, яка повинна виконуватися останньою. В даному випадку такою операцією є логічне додавання, отже, на виході повинен бути диз'юнктор. На нього сигнали подаються з двох кон'юнкторов, на які, в свою чергу, подаються один вхідний сигнал нормальний та один інвертований (з інверторів).

Рисунок 2. - Приклад побудови логічних схем

Логічні закони і правила перетворення логічних виразів

Якщо дві формули А і В одночасно, тобто при однакових наборах значень вхідних до них змінних, приймають однакові значення, то вони називаються рівносильними.

В алгебрі логіки є ряд законів, що дозволяють отримувати рівносильні перетворення логічних виразів.

1. Закон подвійного заперечення: ;

2. Переміщувальний (комутативний) закон:

для логічного додавання: ;

для логічного множення: ;

3. Сполучний (асоціативний) закон:

для логічного додавання: ;

для логічного множення: ;

4. Розподільчий (дистрибутивний) закон:

для логічного додавання: ;

для логічного множення: ;

5. Закони де Моргана:

для логічного додавання: ;

для логічного множення: ;

6. Закон ідемпотентності:

для логічного додавання: ;

для логічного множення: ;

7. Закони виключення констант:

для логічного додавання: ;

для логічного множення: ;

8. Закон суперечності: ;

9. Закон виключення третього: ;

10. Закон поглинання:

для логічного додавання: ;

для логічного множення: ;

11. Правило виключення імплікації: ;

12. Правило виключення еквіваленції: .

Справедливість цих законів можна довести склавши таблицю істинності виразів в правій і лівій частині і порівнявши відповідні значення.

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

Приклад 12. Спростити логічний вираз .

Рішення:

Відповідно до закону де Моргана:

.

Згідно сполучному закону:

.

Згідно закону суперечності і закону ідемпотентності:

.

Відповідно до закону виключення 0:

Остаточно отримуємо .

Размещено на Allbest.ru

...