Алгебра логіки як розділ математики (стр. 1 из 6)

Лабораторна робота №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”).

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

Роботу логічних елементів описують за допомогою таблиць істинності.

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

Схема І

Схема І реалізує кон’юнкцію двох або більше логічних значень.

Одиниця на виході схеми І буде тоді і тільки тоді, коли на усіх входах будуть одиниці. Коли хоча б на одному вході буде нуль, на виході також буде нуль.