Теоретичні відомості. Алгебра логіки — це розділ математики, що вивчає висловлення, розглянуті з точки зору їхніх логічних значень (істинності або хибності) і логічних операцій над
1.Алгебра логіки
Алгебра логіки — це розділ математики, що вивчає висловлення, розглянуті з точки зору їхніх логічних значень (істинності або хибності) і логічних операцій над ними.
Логічне висловлення — це будь-яка оповідальне речення, у відношенні якого можна однозначно сказати, істинне воно або хибне. Щоб звертатися до логічних висловлень, їм призначають імена.
Операції над логічними висловленнями:
НЕ Операція, що виражається словом "не", називається запереченням і позначається рискою над висловленням (або знаком ). Висловлення істинне, коли A хибне, і хибне, коли A істинне.
І Операція, що виражається зв'язуванням "і", називається кон’юнкцією (лат. conjunctio — з'єднання) або логічним множенням і позначається точкою " " (може також позначатися знаками або &). Висловлення А·В істинно тоді і тільки тоді, коли обидва висловлення А и В істинні.
АБО Операція, що виражається зв'язуванням "або" (у невиключаючому сенсі ) називається диз'юнкцією (лат. disjunctio — поділ) або логічним додаванням і позначається знаком v (або плюсом). Висловлення А v В помилкове тоді і тільки тоді, коли обидва висловлення А и В помилкові.
ЯКЩО-ТО Операція, що виражається зв'язуваннями "якщо ..., то", "з ... випливає", "... витікає ...", називається імплікацією (лат. implico — тісно зв'язані) і позначається знаком . Висловлення помилкове тоді і тільки тоді, коли А істинно, а В хибне.
РІВНОСИЛЬНO Операція, що виражається зв'язуваннями "тоді і тільки тоді", "необхідно і досить", "... рівносильно ...", називається еквіваленцією або подвійною імплікацією і позначається знаком або ~. Висловлення істинне тоді і тільки тоді, коли значення А и В збігаються.
За допомогою логічних змінних і символів логічних операцій будь-яке висловлення можна формалізувати, тобто замінити логічною формулою.
В алгебрі логіки виконуються наступні основні закони, що дозволяють робити тотожні перетворення логічних виражень:
Рівносильні перетворення логічних формул мають те ж призначення, що і перетворення формул у звичайній алгебрі. Вони служать для спрощення формул або приведення їх до визначеного виду шляхом використання основних законів алгебри логіки.
Під спрощенням формули, що не містить операцій імплікації і еквіваленції, розуміють рівносильне перетворення, що приводить до формули, що або містить у порівнянні з вихідною менше число операцій кон’юнкції і диз'юнкції і не містить заперечень неелементарних формул, або містить менше число входжень змінних.
Закон | Для АБО | Для І |
Комутативний | ||
Асоціативний | ||
Дистрибутивний | ||
Правила де Моргана | ||
Тавтології | ||
Поглинання | ||
Склеювання | ||
Операція над змінною з її інверсією | ||
Правила операцій з константами | ||
Закон подвійного заперечення |
Приклади
1.
2.
3.
4.
5.
6.
7.
8.
9.
2.Перемикальні схеми
У комп'ютерах і інших автоматичних пристроях широко застосовуються електричні схеми, що містять сотні і тисячі перемикальних елементів: реле, вимикачів і т.п. Розробка таких схем досить трудомістка справа. Виявилося, що тут з успіхом може бути використаний апарат алгебри логіки.
Перемикальна схема — це схематичне зображення деякого пристрою, що складає з перемикачів і з'єднуючих провідників, а також із входів і виходів, на які подається і з яких знімається електричний сигнал.
Кожен перемикач має тільки два стани: замкнутий і розімкнутий. Перемикачеві Х поставимо у відповідність логічну перемінну х, що приймає значення 1 у тому і тільки в тому випадку, коли перемикач Х замкнути і схема проводить струм; якщо ж перемикач розімкнути, то х дорівнює нулеві.
Усій перемикальній схемі також можна поставити у відповідність логічну змінну, рівну одиниці, якщо схема проводить струм, і рівну нулеві — якщо не проводить. Ця змінна є функцією від змінних, відповідних усім перемикачам схеми, і називається функцією провідності.
Дві схеми називаються рівносильними, якщо через одну з них проходить струм тоді і тільки тоді, коли він проходить через іншу (при тому самому вхідному сигналі).
З двох рівносильних схем більш простою вважається та схема, функція провідності якої містить менше число логічних операцій або перемикачів.
При розгляді перемикальних схем виникають дві основні задачі: синтез і аналіз схеми.
СИНТЕЗ СХЕМИ по заданих умовах її роботи зводиться до наступних трьох етапів:
· складанню функції провідності по таблиці істинності, що відбиває ці умови;
· спрощенню цієї функції;
· побудові відповідної схеми.
АНАЛІЗ СХЕМИ зводиться до
· визначенню значень її функції провідності при всіх можливих наборах вхідних у цю функцію перемінних.
· одержанню спрощеної формули.
Приклади.
1. Побудуємо схему, що містить 4 перемикачі x, y, z і t, таку, щоб вона проводила струм тоді і тільки тоді, коли замкнути контакт перемикача t і який-небудь з інших трьох контактів.
Рішення. У цьому випадку можна обійтися без побудови таблиці істинності. Очевидно, що функція провідності має вигляд F(x, y, z, t) = t · (x v y v z), а схема виглядає так:
Приклад 2
Проаналізувати задану схему
Розв’язок
В даному випадку будувати таблицю істинності не потрібно.
Приклад 3
Розв’язок
Спрощена перемикальна схема
Таблиця істинності
z | t | F |
3.Логічний елемент комп'ютера — це частина електронної логічної схеми, що реалізує елементарну логічну функцію.
Логічними елементами комп'ютерів є електронні схеми І, АБО, НЕ, І-НЕ, АБО-НЕ й інші (звані також вентилями), а також тригер.
За допомогою цих схем можна реалізувати будь-яку логічну функцію, що описує роботу пристроїв комп'ютера. Звичайно у вентилів буває від двох до восьми входів і один або два виходи.
Високий рівень звичайно відповідає значенню “істина” (“1”), а низький — значенню “неправда” (“0”).
Кожен логічний елемент має свою умовну позначку, що виражає його логічну функцію, але не вказує на те, яка саме електронна схема в ньому реалізована. Це спрощує запис і розуміння складних логічних схем.
Роботу логічних елементів описують за допомогою таблиць істинності.
Таблиця істинності -це табличне представлення логічної схеми (операції), у якому перераховані всі можливі сполучення значень істинності вхідних сигналів (операндів) разом зі значенням істинності вихідного сигналу (результату операції) для кожного з цих сполучень.
Схема І
Схема І реалізує кон’юнкцію двох або більше логічних значень.
Одиниця на виході схеми І буде тоді і тільки тоді, коли на усіх входах будуть одиниці. Коли хоча б на одному вході буде нуль, на виході також буде нуль.
Зв'язок між виходом z цієї схеми і входами x і y описується співвідношенням: z = x · y
(читається як "x і y"). Операція кон’юнкції на структурних схемах позначається знаком "&" (читається як "амперсенд"), що є скороченим записом англійського слова and.
Схема АБО
Схема АБО реалізує диз'юнкцію двох або більш логічних значень. Коли хоча б на одному вході схеми АБО буде одиниця, на її виході також буде одиниця.
Умовна позначка на структурних схемах схеми АБО з двома входами представлене на мал. 5.2. Знак "1" на схемі — від застарілого позначення диз'юнкції як ">=1" (тобто значення диз'юнкції дорівнює одиниці, якщо сума значень операндів більше або дорівнює 1). Зв'язок між виходом z цієї схеми і входами x і y описується співвідношенням: z = x v y (читається як "x або y").
С х е м а НЕ
Схема НЕ (інвертор) реалізує операцію заперечення. Зв'язок між входом x цієї схеми і виходом z можна записати співвідношенням z = , x де читається як "не x" або "інверсія х".
Якщо на вході схеми 0, то на виході 1. Коли на вході 1, на виході 0.
Схема І-НЕ
Схема І-НЕ складається з елемента І и інвертора і здійснює заперечення результату схеми І. Зв'язок між виходом z і входами x і y схеми читається як "інверсія x і y".
Схема АБО-НЕ
Схема АБО-НЕ складається з елемента АБО й інвертора і здійснює заперечення результату схеми АБО. Зв'язок між виходом z і входами x і y схеми читається як "інверсія x або y ".
2.Завдання до лабораторної роботи
1. Спростити наступні вирази:
2. Проаналізувати наступні перемикальні схеми
3. Скласти перемикальні схеми функцій
4. Реалізувати функції з завдання 3 з допомогою логічних елементів .
Дата добавления: 2015-07-24; просмотров: 851;