50275 (Алгебра логіки як розділ математики)
Описание файла
Документ из архива "Алгебра логіки як розділ математики", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "контрольные работы и аттестации", в предмете "информатика, программирование" в общих файлах.
Онлайн просмотр документа "50275"
Текст из документа "50275"
Лабораторна робота №1
Теоретичні відомості.
1. Алгебра логіки
Алгебра логіки - це розділ математики, що вивчає висловлення, розглянуті з точки зору їхніх логічних значень (істинності або хибності) і логічних операцій над ними.
Логічне висловлення - це будь-яка оповідальне речення, у відношенні якого можна однозначно сказати, істинне воно або хибне. Щоб звертатися до логічних висловлень, їм призначають імена.
Операції над логічними висловленнями:
НЕ Операція, що виражається словом "не", називається запереченням і позначається рискою над висловленням (або знаком). Висловлення істинне, коли A хибне, і хибне, коли A істинне.
І Операція, що виражається зв'язуванням "і", називається кон’юнкцією (лат. conjunctio - з'єднання) або логічним множенням і позначається точкою " " (може також позначатися знаками або &). Висловлення А·В істинно тоді і тільки тоді, коли обидва висловлення А и В істинні.
АБО Операція, що виражається зв'язуванням "або" (у невиключаючому сенсі) називається диз'юнкцією (лат. disjunctio - поділ) або логічним додаванням і позначається знаком v (або плюсом). Висловлення А v В помилкове тоді і тільки тоді, коли обидва висловлення А и В помилкові.
ЯКЩО-ТО Операція, що виражається зв'язуваннями "якщо., то", "з. випливає",". витікає.", називається імплікацією (лат. implico - тісно зв'язані) і позначається знаком. Висловлення помилкове тоді і тільки тоді, коли А істинно, а В хибне.
РІВНОСИЛЬНА Операція, що виражається зв'язуваннями "тоді і тільки тоді", "необхідно і досить",". рівносильно.", називається еквіваленцією або подвійною імплікацією і позначається знаком або ~. Висловлення істинне тоді і тільки тоді, коли значення А и В збігаються. За допомогою логічних змінних і символів логічних операцій будь-яке висловлення можна формалізувати, тобто замінити логічною формулою. В алгебрі логіки виконуються наступні основні закони, що дозволяють робити тотожні перетворення логічних виражень:
Рівносильні перетворення логічних формул мають те ж призначення, що і перетворення формул у звичайній алгебрі. Вони служать для спрощення формул або приведення їх до визначеного виду шляхом використання основних законів алгебри логіки. Під спрощенням формули, що не містить операцій імплікації і еквіваленції, розуміють рівносильне перетворення, що приводить до формули, що або містить у порівнянні з вихідною менше число операцій кон’юнкції і диз'юнкції і не містить заперечень неелементарних формул, або містить менше число входжень змінних.
Закон | Для АБО | Для І |
Комутативний |
|
|
Асоціативний |
|
|
Дистрибутивний |
|
|
Правила де Моргана |
|
|
Тавтології |
|
|
Поглинання |
|
|
Склеювання |
| |
Операція над змінною з її інверсією |
|
|
Правила операцій з константами |
|
|
Закон подвійного заперечення |
|
Приклади
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 |
0 | 0 | 0 |
0 | 1 | 1 |
1 | 0 | 1 |
1 | 1 | 1 |
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. Завдання до лабораторної роботи
-
Спростити наступні вирази:
-
Проаналізувати наступні перемикальні схеми