Как да изграждаме логически схеми в компютърните науки. Алгоритъм за конструиране на логически схеми. I. Организационен момент

Защо е необходимо да можем да изграждаме логически схеми?

Факт е, че портите се използват за създаване на по-сложни вериги, които позволяват аритметични операциии съхранява информация. Освен това верига, която изпълнява определени функции, може да бъде конструирана от различни комбинации и брой порти. Следователно значението на формалното представяне на логическа диаграма е изключително голямо. Необходимо е, така че разработчикът да има възможност да избере най-подходящия вариант за изграждане на верига от порти. По този начин процесът на разработване на общата логическа схема на устройството (включително компютъра като цяло) става йерархичен и на всяко следващо ниво логическите схеми, създадени на предишния етап, се използват като „градивни елементи“.

Алгебрата на логиката е дадена в ръцете на дизайнерите мощен инструментразработване, анализ и подобряване на логически схеми. Всъщност е много по-лесно, по-бързо и по-евтино да се изследват свойствата и да се докаже правилната работа на веригата, като се използва формула, която я изразява, отколкото да се създаде истинска техническо средство. Именно това е смисълът на всяко математическо моделиране.

Логическите схеми трябва да бъдат изградени от минимално възможен брой елементи, което от своя страна осигурява по-голяма скорост на работа и повишава надеждността на устройството.

Алгоритъм за конструиране на логически схеми :

1) Определете броя на логическите променливи.

2) Определете броя на основните логически операции и техния ред.

3) За всяка логическа операция нарисувайте съответния гейт.

4) Свържете портите по реда на извършване на логически операции.

Нека ги опознаем един по един.

Задача:

Направете логическа диаграма за него.

Решение:

1. отрицание
2. умножение
3. допълнение

Изграждаме веригата в посочения ред.

Задача:

Конструирайте логическа функция, като го използвате.

Решение:

Можете първо да обозначите на диаграмата междинните функции, получени на изхода на всеки блок, и след това да ги свържете с логически операции.

Задача:

Определете стойността на функцията F на изхода на веригата.

Решение:

Отговор:

Задача:

Конструирайте таблица на истината за него.

Решение:

Отговор:

Удобен начин за представяне на логически изрази е използването на логически диаграми. Ето как трите основни логически операции са изобразени в такива диаграми:

Фигура 6.1 - Схематично представяне на логическите операции

Пример.За да оцените булев израз: 1 или 0 И 1 начертайте диаграма, отразяваща последователността от логически операции. С помощта на диаграмата изчислете стойността на логически израз.

Това ясно показва, че първо се извършва операцията И, тогава или. Сега, в ред отляво надясно, ще присвоим резултатите от операциите на изходящите стрелки:

Резултатът беше 1 , т.е. "ВЯРНО".

Пример.Даден израз: Не (1 И (0 или 1) И 1).

Изчислете стойността на израз с помощта на логическа схема.

Решение. Логическата диаграма с резултатите от изчислението изглежда така:

Импликация и еквивалентност

Внушение(условно твърдение). На руски тази логическа операция съответства на съюзите ако..., тогава; когато..., тогава; щом... тогаваи така нататък.

Израз, започващ след съюзи ако, когато, веднага щом,се нарича основа на условно твърдение.

Израз след думите така че след това,наречено следствие. В логическите формули операцията на импликация се обозначава със знака “→”. Импликацията е операция на две места; е написано така: A→B.

Еквивалентност.Езиков еквивалент - съюзи ако и само ако; тогава и само тогава когато...Посочена е еквивалентност знак"≡" или "↔".

Редът на всичките пет логически операции в низходящ ред на приоритет е както следва: отрицание, конюнкция, дизюнкция, импликация, еквивалентност.

Преобразуване на булеви изрази

Една формула има нормална форма, ако не съдържа еквивалентност, импликация или двойни знаци за отрицание, докато знаците за отрицание се намират само за променливи.

Основни формули за преобразуване на логически изрази:

2. (A & B) ≡ A IN.

3. (А B) ≡ A & B.

4. (A → B) ≡A & B.

5. A→B ≡ A б.

6. А ↔ B ≡ (A & B) (A & B) ≡ (A B) & (A Б).

7. A & (A Б) ≡ А.

8. А A & B ≡ A.

9. A & (A B) ≡ A & B.

10.А A & B ≡ A IN.

11. Закони на комутативността:

A & B ≡ B & A;

А B ≡ B А.

12. Закони на асоциативността:

(А Б) C ≡ A (IN СЪС);

(A & B) & C ≡ A & (B & C).

13. Закони на идемпотентността:

А A ≡ A;

14. Закони на дистрибутивността:

A&(B C) ≡ (A & B) (A&C);

А (B & C) ≡ (A B) & (A СЪС).

15. А 1 ≡ 1;

16. A & 1 ≡ A;

17. А A ≡ 1;

18. A & 0 ≡ 0;

19. A & A ≡ 0.

6.3. Лабораторно задание

Задачите се разпределят в зависимост от даденото от преподавателя мн-код. Ако m е нечетно число, тогава вашият вариант е 1, ако е четно, тогава вариант 2.

Упражнение 1.Използвайки логически операции, запишете твърдения, които са верни, ако са изпълнени следните условия:

Опция 1.

1) поне едно от числата X, Y, Z е положително;

2) само едно от числата X, Y, Z не е положително.

3) само едно от числата X, Y, Z е по-голямо от 10

4) нито едно от числата X, Y, Z не е равно на 104

Вариант 2.

1) поне едно от числата X, Y, Z е отрицателно;

2) само едно от числата X, Y, Z е отрицателно.

3) само едно от числата X, Y, Z не е повече от 10

4) всяко от числата X, Y, Z е 0

Задача 2.Определете стойността на булев израз Не (X>Z) в противен случай (X=Y), ако:

Опция 1.

1) X=3, Y=5, Z=2;

2) X=5, Y=0, Z=–8.

Вариант 2.

1) X=9, Y=–9, Z=9;

2) X=0, Y=1, Z=19.

Задача 3.Нека a, b, c са логически величини, които имат следните значения: a = вярно, b= лъжа, c = вярно. Начертайте логически диаграми за следните булеви изрази и оценете техните стойности:

Опция 1.

1) а И b;

2) НеА или b;

3) а или b ИС;

4) (а илиб) И(° С илиб).

Вариант 2.

1) а или b;

2) а И b илиС;

3) НеА или b ИС;

4) Не(А И b ИС).

Задача 4.Конструирайте логически схеми, като използвате логически израз:

Вариант 1. х 1 И (Нех 2 или x 3).

Вариант 2. х 1 Их 2 Или нех 1 И x 3 .

Задача 5.Извършвайте логически изчисления. Запишете съответните логически изрази:

Вариант 1. Вариант 2.

Задача 6.Дадена е логическа схема. Конструирайте логически израз, съответстващ на тази верига.

Изчислете стойността на израза за:

Опция 1.

1) x 1 =0, x 2 =1;

2) x 1 =1, x 2 =1.

Вариант 2.

1) x 1 =1, x 2 =0;

2) x 1 =0, x 2 =0.

Задача 7.Дадена е логическа схема. Конструирайте таблица на истината за тази верига.

Задача 8.Определете истинността на формулата:

Вариант 1. ((a) .

Вариант 2. .

Задача 9.Опростете израза:

Опция 1. .

Вариант 2. .

6.4. Изисквания към съдържанието на отчета

1. Цел на лабораторната работа.

2. Лабораторна работа. Mn – код.

3. Резултати от решаване на проблеми на вашата версия.

4. Изводи въз основа на получените резултати.

6.5. Контролни въпроси

1. Какво е логическо твърдение, константа, променлива, формула?

2. Какви видове логически операции се разглеждат в лабораторната работа?

3. Таблици на истинност за импликация и еквивалентност?

4. Избройте законите на алгебрата на логиката?

Лабораторна работа №7
"ЧИСЛОВИ СИСТЕМИ"

7.1. Цел на работата

Изучаване на бройни системи. Придобиване на умения за прехвърляне от една бройна система в друга

7.2. Насоки

Разширена формазаписването на число се нарича записване във формата:

A q =±(a n-1 q n-1 + a n-2 q n-2 +…+ a 0 q 0 + a –1 q -1 + a -2 q -2 + …+ a -m q - м).

Тук A q е самото число, q е основата на бройната система, а i са цифрите на тази бройна система, n е броят на цифрите на цялата част на числото, m е броят на цифрите на дробната част част от числото.

Пример. Вземете разширена форма на десетични числа 32478; 26,387.

32478 10 = 3*10000 + 2*1000 + 4*100 + 7*10 + 8 = 3*10 4 + 2*10 3 + 4*10 2 + 7*10 1 + 8*10 0 .

26,387 10 = 2*10 1 + 6*10 0 + 3*10 -1 + 8*10 -2 + 7*10 -3 .

Пример. Вземете разширената форма на числата 112 3, 101101 2, 15FC 16, 101.11 2

112 3 =1*10 2 + 1*10 1 + 2*10 0 .

1011012 = 1*10 101 + 0*10 100 + 1*10 11 + 1*10 10 + 0*10 1 + 1*10 0 .

15FC 16 = 1*10 3 + 5 *10 2 + F*10 1 + C.

101,11 2 = 1*10 10 + 0*10 1 + 1*10 0 + 1*10 -1 + 1*10 -10 .

Ако всички членове в разгънатия вид на недесетично число са представени в десетичната система и полученият израз се изчисли по правилата на десетичната аритметика, тогава ще се получи число в десетичната система, равно на даденото. Този принцип се използва за преобразуване от недесетична система към десетична система.

Пример. Преобразувайте всички числа от предишния пример в десетичната система.

112 3 =1*3 2 + 1*3 1 + 2*3 0 = 9+3+2 = 14 10 .

101101 2 = 1*2 5 + 0*2 4 + 1*2 3 + 1*2 2 + 0*2 1 + 1*2 0 =32+8+4+1 = 45 10 ,

15FC 16 = 1*16 3 + 5*16 2 + 15*16 1 + 12 = 4096 + 1280 + 240 + 12 = 5628 10.

101,11 2 = 1*2 2 + 0*2 1 + 1*2 0 + 1*2 –1 + 12 -2 = 4 + 1 + 1/2 + 1/4 = 5 + 0,5 + 0,25 = 5,75 10 .

В цифровата схема цифровият сигнал е сигнал, който може да приема две стойности, считани за логическа "1" и логическа "0".

Логическите схеми могат да съдържат до 100 милиона входа и съществуват такива гигантски схеми. Представете си, че булевата функция (уравнение) на такава верига е загубена. Как да го възстановите с най-малко загуба на време и без грешки? Най-продуктивният начин е да разделите диаграмата на нива. С този метод се пише изходна функциявсеки елемент в предишното ниво и се замества със съответния вход в следващото ниво. Днес ще разгледаме този метод за анализ на логически схеми с всичките му нюанси.

Логическите схеми се реализират с помощта на логически елементи: „НЕ“, „И“, „ИЛИ“, „И-НЕ“, „ИЛИ-НЕ“, „XOR“ и „Еквивалентност“. Първите три логически елемента ви позволяват да реализирате всяка, без значение колко сложна, логическа функция в булева основа. Ще решаваме задачи върху логически схеми, реализирани точно в булев базис.

Използват се няколко стандарта за обозначаване на логически елементи. Най-често срещаните са американски (ANSI), европейски (DIN), международни (IEC) и руски (GOST). Фигурата по-долу показва обозначенията на логическите елементи в тези стандарти (за да увеличите, можете да щракнете върху фигурата с левия бутон на мишката).

В този урок ще решаваме задачи върху логически схеми, в които логическите елементи са обозначени в стандарта GOST.

Проблемите с логическите схеми са два вида: задача за синтезиране на логически схеми и задача за анализ на логически схеми. Ще започнем с втория тип задача, тъй като в този ред можем бързо да се научим да четем логически схеми.

Най-често във връзка с изграждането на логически схеми се разглеждат функциите на логическата алгебра:

• три променливи (ще се разглеждат в задачи за анализ и в една задача за синтез);
• четири променливи (в задачите за синтез, тоест в последните два параграфа).

Нека разгледаме изграждането (синтеза) на логически схеми

• в булевата база "И", "ИЛИ", "НЕ" (в предпоследния параграф);
• в също често срещаните основи “И-НЕ” и “ИЛИ-НЕ” (в последния параграф).

Проблем с анализ на логическа верига

Задачата на анализа е да се определи функцията f, реализиран от дадена логическа схема. При решаването на такъв проблем е удобно да се придържате към следната последователност от действия.

1. Логическата диаграма е разделена на нива. На нивата се присвояват последователни номера.
2. Изходите на всеки логически елемент са обозначени с името на желаната функция, снабдени с цифров индекс, където първата цифра е номерът на подреждането, а останалите цифри са серийният номер на елемента в подреждането.
3. За всеки елемент се записва аналитичен израз, който свързва неговата изходна функция с входните променливи. Изразът се определя от логическата функция, изпълнявана от дадения логически елемент.
4. Заместването на едни изходни функции с други се извършва, докато се получи булева функция, изразена чрез входни променливи.

Пример 1.

Решение. Разделяме логическата верига на нива, което вече е показано на фигурата. Нека запишем всички функции, като започнем от 1-во ниво:

х, г, z :

Пример 2.Намерете булевата функция на логическа схема и изградете таблица на истината за логическата схема.

Пример 3.Намерете булевата функция на логическа схема и изградете таблица на истината за логическата схема.

Продължаваме заедно да търсим булевата функция на логическата схема

Пример 4.Намерете булевата функция на логическа схема и изградете таблица на истината за логическата схема.

Решение. Разделяме логическата диаграма на нива. Нека запишем всички функции, като започнем от 1-во ниво:

Сега нека запишем всички функции, замествайки входните променливи х, г, z :

В резултат на това получаваме функцията, която логическата схема изпълнява на изхода:

.

Таблица на истината за тази логическа схема:

Пример 5.Намерете булевата функция на логическа схема и изградете таблица на истината за логическата схема.

Решение. Разделяме логическата диаграма на нива. Структурата на тази логическа верига, за разлика от предишните примери, има 5 нива, а не 4. Но една входна променлива - най-ниската - преминава през всички нива и директно влиза в логическия елемент в първия слой. Нека запишем всички функции, като започнем от 1-во ниво:

Сега нека запишем всички функции, замествайки входните променливи х, г, z :

В резултат на това получаваме функцията, която логическата схема изпълнява на изхода:

.

Таблица на истината за тази логическа схема:

Проблемът за синтезиране на логически схеми в булев базис

Разработването на логическа схема според нейното аналитично описание се нарича проблем за синтеза на логическа верига.

Всяка дизюнкция (логическа сума) съответства на елемент „ИЛИ“, чийто брой входове се определя от броя на променливите в дизюнкцията. Всяка връзка (логически продукт) съответства на елемент „И“, чийто брой входове се определя от броя на променливите в връзката. Всяко отрицание (инверсия) съответства на елемент „НЕ“.

Логическият дизайн често започва с дефиниране на логическата функция, която логическата верига трябва да реализира. В този случай е дадена само таблицата на истинността на логическата схема. Ще анализираме точно такъв пример, тоест ще решим проблем, който е напълно противоположен на проблема за анализиране на логически схеми, разгледан по-горе.

Пример 6.Конструирайте логическа схема, която изпълнява функция с дадена таблица на истината.

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

Схемно изпълнение на логически елементи. Изграждане на логически вериги.

Теоретична част.

Компютърната обработка на информация се основава на алгебрата на логиката, разработена от J. Boole. Доказано е, че всички електронни компютърни схеми могат да бъдат реализирани с помощта на логически елементи И, ИЛИ, НЕ.

Елемент НЕ

Когато на входа на веригата се подаде сигнал с ниско ниво (0), транзисторът ще бъде заключен, т.е. през него няма да преминава ток и изходът ще бъде сигнал високо ниво(1). Ако към входа на веригата се приложи сигнал с високо ниво (1), транзисторът ще се „отвори“ и ще започне да пропуска електрически ток. На изхода, поради спада на напрежението, напрежението ще се установи ниско ниво. Така веригата преобразува сигнали от едно ниво на друго, изпълнявайки логическа функция.

ИЛИ елемент

Функцията “ИЛИ” е логическо събиране (дизюнкция), резултатът й е 1, ако поне 1 от аргументите е 1. Тук транзисторите са свързани паралелно един на друг. Ако и двата са затворени, тогава общото им съпротивление е високо и изходът ще бъде сигнал с ниско ниво (логическа „0“). Достатъчно е да приложите сигнал с високо ниво ("1") към един от транзисторите, веригата ще започне да преминава ток и сигнал с високо ниво (логическо "1") също ще бъде установен при съпротивлението на натоварване.

Елемент I

Ако към входовете In1 и In2 се прилагат сигнали с ниско ниво (логически "0"), тогава и двата транзистора са затворени, през тях не преминава ток и изходното напрежение при Rn е близо до нула. Нека високо напрежение (“1”) бъде приложено към един от входовете. Тогава съответният транзистор ще се отвори, но другият ще остане затворен и през транзисторите и съпротивлението няма да минава ток. Следователно, когато напрежението на високо ниво се приложи само към един от транзисторите, веригата не се превключва и на изхода остава напрежение на ниско ниво. И само когато сигнали с високо ниво (“1”) се подават едновременно към входовете, ние също ще получим сигнал с високо ниво на изхода.

По този начин всяка основна логическа функция - "И", "ИЛИ", "НЕ" - съответства на специално проектирана схема, наречена логически елемент. Чрез комбиниране на сигнали, обозначаващи логически променливи и изходи, съответстващи на логически функции, използвайки логически елементи, използвайки таблица на истината или CNF и DNF представяне на логическа функция, може да се състави структурна или функционална диаграма(вижте примерите по-долу), което е основата за хардуерното изпълнение на веригата.

Анализирайки функционалната диаграма, можете да разберете как работи логическото устройство, т.е. отговорете на въпроса: каква функция изпълнява? Също толкова важна форма за описание на логически устройства е структурната формула. Нека покажем с пример как се записва формула по дадена функционална диаграма (1 диаграма). Ясно е, че елементът "И" извършва логическо умножение на стойностите и B. Извършва се операция за отрицание на резултата в елемента "НЕ", т.е. изчислява се стойността на израза: Формулата е структурната формула на логическото устройство.

И така, основните логически функции са обозначени

Пример:е дадена логическата диаграма:

Изграден е на базата на булев израз - Y = Ē /\ I \/ Ē /\ A \/ Ā /\ E

Практическа част.

Упражнение 1.За всяка от функционалните диаграми запишете съответната структурна формула.

2) За CNF и DNF от лабораторна работа 5 построете функционални диаграми.