Лабораторна робота № 2.

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

Час виконання

4 години

Мета роботи

Вивчити основи алгебри логіки.

Завдання лабораторної роботи

В результаті проходження зайняття студент повинен:

1. знати:

• визначення основних понять(просте і складне висловлювання, логічні операції, логічні вирази, логічна функція);

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

• алгоритм побудови таблиць істинності;

• схеми базових логічних елементів;

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

        2. уміти:

• застосовувати закони логіки для спрощення логічних виразів;

• будувати таблиці істинності;

• будувати логічні схеми складних виразів.

Загальні теоретичні відомості Основні поняття алгебри логіки

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

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

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

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

Не всяка пропозиція є логічним висловлюванням.

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

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

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

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

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

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

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

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

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

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

Таблиця 1. Основні логічні операції

Позначення операції	Читається	Назва операції	Альтернативні позначення
¬	НЕ	Заперечення(інверсія)	Риска згори
	І	Кон'юнкція(логічне множення)	∙ &
	Або	Диз'юнкція(логічне складання)	+
→	Якщо, то	Імплікація
↔	Тоді і тільки тоді	Еквіваленція	~
XOR	Або,або	Що виключає АБО(складання по модулю 2)

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

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

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

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

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

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

ЯКЩО, ТО Операція, що виражається зв'язками «якщо, то» називається імплікацією(лат. implico - тісно пов'язані) і позначається знаком →. Висловлювання А→В неправдиво тоді і тільки тоді, коли А істинно, а В неправдиво.

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

РІВНОСИЛЬНО Операція, що виражається зв'язками «тоді і тільки тоді», «необхідно і достатньо» «... рівносильно »., називається еквіваленцією або подвійною імплікацією і позначається знаком ↔ або ~. Висловлювання А↔В істинно тоді і тільки тоді, коли значення А і В співпадають.

Приклад: Висловлювання «Число є парним тоді і тільки тоді, коли воно ділиться без залишку на 2» є істинним, а висловлювання «Число є непарним тоді і тільки тоді, коли воно ділиться без залишку на 2» - неправдиво.

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

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

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

.

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

.

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

.

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

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

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

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

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

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

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

Приведемо таблицю істинності основних логічних операцій(таблиця. 2)

Таблиця 2

A	B
1	1	0	1	1	1	1	0
1	0	0	0	1	0	0	1
0	1	1	0	1	1	0	1
0	0	1	0	0	1	1	0

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

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

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

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

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

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

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

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

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

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

Алгоритм виконання:

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

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

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

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

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

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

A	B
1	1	1	0
1	0	0	1
0	1	0	1
0	0	0	1

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

.

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

A	B
1	1	1	0
1	0	1	0
0	1	1	0
0	0	0	1

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

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

Рішення:

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

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

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

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

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

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

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

A	B					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, немає імпульсу - 0. На входи логічного елементу поступають сигнали-значення аргументів, на виході з'являється сигнал-значення функції.

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