Постройте логическую схему соответствующую логическому выражению: Задание 1.Постройте логическую схему, соответствующую логическому выражению и найдите — RC74 — интернет-магазин радиоуправляемых моделей

Содержание

Практическая работа №5,6 по Информатике и ИКТ

Практическая работа №5,6

Тема: Логические величины, операции, выражения. Построение логических схем.

Цель работы: научиться составлять аналитические выражения по табличному значению функции, строить схемы из элементарных логических элементов по заданному аналитическому выражению функции.

Студент должен

знать:

основной базис логики;

особенности применения логических элементов;

уметь:

производить синтез и анализ аналитических выражений логических функций

строить схемы из элементарных логических элементов по заданному аналитическому выражению функции.

Теоретическое обоснование.

1. Логические элементы

Функция отрицание НЕ или инверсия

Таблица истинности функции отрицания имеет вид:

Логический элемент НЕ обозначается на схемах следующим образом:
(пишется X c чертой сверху)

Логическое ИЛИ (логическое сложение, дизъюнкция): Y= X1 + X2 = X1VX2

Таблица истинности логического ИЛИ имеет вид:

Логический элемент ИЛИ обозначается на схемах следующим образом:

Логическое И (логическое умножение, конъюнкция): Y = X1X2 = X1&X2

Таблица истинности логического И имеет вид:

Логический элемент И обозначается на схемах следующим образом:

Функция ИЛИ-НЕ: Y = (X1+X2)

Таблица истинности функции ИЛИ-НЕ имеет вид:

Логический элемент ИЛИ-НЕ обозначается на схемах следующим образом:

Функция И-НЕ: Y = (X1^X2)

Таблица истинности функции И-НЕ имеет вид:

Логический элемент И-НЕ обозначается на схемах следующим образом:

2. Алгоритм построение логических схем.

1. Определить число логических переменных.

2. Определить количество базовых логических операций и их порядок.

3. Изобразить для каждой логической операции соответствующий ей вентиль.

4. Соединить вентили в порядке выполнения логических операций.

Пример 1.
Составить логическую схему для логического выражения: F=A v B & A.
Две переменные – А и В.
Две логические операции: 1-&, 2-v.
Строим схему:

Пример 2.
Постройте логическую схему, соответствующую логическому выражению F=А&Вv (ВvА). Вычислить значения выражения для А=1,В=0.
Переменных две: А и В;
Логических операций три: & и две v; А&Вv (Вv А).
Схему строим слева направо в соответствии с порядком логических операций:

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

Синтез комбинационных устройств может быть произведен по табличному заданию функции по «0» и «1». Рассмотрим для примера синтез по «1». Для всех значений аргументов х1, х2, х3, где функция задана как «1» берется их конъюнкция, если аргумент равен «1», если же 0 – конъюнкция их инверсий. От полученных конъюнкций берется дизъюнкция.

Например, функция от трех аргументов задана следующей таблицей:

х1

х2

Х3

Это значит, что при любых наборах аргументов ч кроме второго и последнего, аргумент у будет равен 0. Составляем для второго набора выражение: .

Для последнего набора: х1 х2 х3

Составим аналитическое выражение функции:

Схема должна содержать инверсию сигналов х1, х2, две схемы «И» и одну двухвходовую схему «ИЛИ»

Ход работы:

1. Изучить теоретическое обоснование;

2. Выполнить практическое задание по вариантам;

3. Оформить отчет.

4. Ответить на контрольные вопросы по указанию преподавателя.

Практические задания:

Задание 1
Записать логическую функцию, описывающую состояние логической схемы. Составить таблицу истинности.

Вариант 1

а)

б)

Вариант 2

Вариант 3

а)

б)

Вариант 4

а)

б)

Задание 2

Построить логические схемы по формулам и составить таблицу истинности

Вариант 1

а) F= (AvB)&(Cv`B)

б) F= (A&B&C)

Вариант 2

а) F=(X&`Y)vZ.

б) F=X&Yv`Z.

В ариант 3

а)F= (XvY) & (Yv`X).

б)F= ((XvY) & (`ZvX)) & (ZvY).

Вариант 4

а) F= A&B&C&`D.

б) F= (AvB) &(`AvB).

Задание 3

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

Вариант 1

Вариант 2

Вариант 3

Вариант 4

х1

х2

Х3

у1

у2

у3

У4

у5

у6

у7

у8

Как построить логическую схему по логическому выражению. Определение сигнала на выходе логической схемы по заданным значениям сигналов на всех входах этой схемы

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

Схемотехническая реализация логических элементов. Построение логических схем.

Теоретическая часть.

В основе обработки компьютером информации лежит алгебра логики, разработанная Дж. Булем. Было доказано, что все электронные схемы ЭВМ могут быть реализованы с помощью логических элементов И, ИЛИ, НЕ.

Элемент НЕ

При подаче на вход схемы сигнала низкого уровня (0) транзистор будет заперт, т.е. ток через него проходить не будет, и на выходе будет сигнал высокого уровня (1). Если же на вход схемы подать сигнал высокого уровня (1), то транзистор “откроется”, начнет пропускать электрический ток. На выходе за счет падения напряжения установится напряжение низкого уровня. Таким образом, схема преобразует сигналы одного уровня в другой, выполняя логическую функцию.

Элемент ИЛИ

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

Элемент И

Если на входы Вх1 и Вх2 поданы сигналы низкого уровня (логические “0”), то оба транзистора закрыты, ток через них не проходит, выходное напряжение на R н близко к нулю. Пусть на один из входов подано высокое напряжение (“1”). Тогда соответствующий транзистор откроется, однако другой останется закрытым, и ток через транзисторы и сопротивление проходить не будет. Следовательно, при подаче напряжения высокого уровня лишь на один из транзисторов, схема не переключается и на выходе остается напряжение низкого уровня. И лишь при одновременной подаче на входы сигналов высокого уровня (“1”) на выходе мы также получим сигнал высокого уровня.

Таким образом, каждой базовой логической функции – «И», «ИЛИ», «НЕ» — соответствует особым образом сконструированная схема, называемая логическим элементом. Комбинируя сигналы, обозначающие логические переменные, и выходы, соответствующие логическим функциям, с помощью логических элементов, пользуясь таблицей истинности или представлением логической функции в виде КНФ и ДНФ, можно составить структурную или функциональную схему (см. примеры ниже), являющуюся основой для аппаратной реализации схемы.

Анализируя функциональную схему, можно понять, как работает логическое устройство, т.е. дать ответ на вопрос: какую функцию она выполняет. Не менее важной формой описания логических устройств является структурная формула. Покажем на примере как выписывают формулу по заданной функциональной схеме (1 схема). Ясно, что элемент “И” осуществляет логическое умножение значений и В. Над результатом в элементе “НЕ” осуществляется операция отрицания, т.е. вычисляется значение выражения: Формула и есть структурная формула логического устройства.

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

Инверсия
Конъюнкция
Дизъюнкция

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

Она построена на основании булева выражения — Y = Ē /\ I \/ Ē /\ A \/ Ā /\ E

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

Задание 1. Для каждой из функциональных схем выписать соответствующую структурную формулу.

2) Для КНФ и ДНФ из лабораторной работы 5 построить функциональные схемы.

Цели урока:

Образовательные:

закрепить у учащихся представление об устройствах элементной базы компьютера;
закрепить навыки построения логических схем.

Развивающие:

формировать развитие алгоритмического мышления;
развить конструкторские умения;
продолжать способствовать развитию ИКТ — компетентности;

Воспитательные:

продолжить формирование познавательного интереса к предмету информатика;
воспитывать личностные качества:
активность,
самостоятельность,
аккуратность в работе;

Требования к знаниям и умениям:

Учащиеся должны знать:

основные базовые элементы логических схем;
правила составления логических схем.

Учащиеся должны уметь:

составлять логические схемы.

Тип урока: урок закрепления изученного материала

Вид урока: комбинированный

Методы организации учебной деятельности:

фронтальная;
индивидуальная;

Программно-дидактическое обеспечение:

ПК, SMART Board, карточки с индивидуальным домашним заданием.

Урок разработан с помощью программы Macromedia Flash .

Ход урока

I. Постановка целей урока.

Добрый день!

Сегодня мы продолжаем изучение темы «Построение логических схем».

Приготовьте раздаточный материал «Логические основы ЭВМ. Построение логических схем» Приложение 1

Вопрос учителя. Назовите основные логические элементы. Какой логический элемент соответствует логической операции И, ИЛИ, НЕ?

Ответ учащихся. Логический элемент компьютера — это часть электронной логической схемы, которая реализует элементарную логическую функцию. Основные логические элементы конъюнктор (соответствует логическому умножению), дизъюнктор (соответствует логическому сложению), инвертор (соответствует логическому отрицанию).

Вопрос учителя. По каким правилам логические элементы преобразуют входные сигналы. Рассмотрим элемент И. В каком случае на выходе будет ток (сигнал равный 1).

Ответ учащихся. На первом входе есть ток (1, истина), на втором есть (1, истина), на выходе ток идет (1, истина).

Вопрос учителя. На первом входе есть ток, на втором нет, однако на выходе ток идет. На входах тока нет и на выходе нет. Какую логическую операцию реализует данный элемент?

Ответ учащихся. Элемент ИЛИ — дизъюнктор.

Вопрос учителя. Рассмотрим логический элемент НЕ. В каком случае на выходе не будет тока (сигнал равный 0)?

Ответ учащихся. На входе есть ток, сигнал равен 1.

Вопрос учителя. В чем отличие логической схемы от логического элемента?

Ответ учащихся. Логические схемы состоят из логических элементов, осуществляющих логические операции.

Проанализируем схему и определим сигнал на выходе.

II. Закрепление изученного материала.

Почему необходимо уметь строить логические схемы?

Дело в том, что из вентилей составляют более сложные схемы, которые позволяют выполнять арифметические операции и хранить информацию. Причем схему, выполняющую определенные функции, можно построить из различных по сочетанию и количеству вентилей. Поэтому значение формального представления логической схемы чрезвычайно велико. Оно необходимо для того, чтобы разработчик имел возможность выбрать наиболее подходящий ему вариант построения схемы из вентилей. Процесс разработки общей логической схемы устройства (в том числе и компьютера в целом), становится иерархическим, причем на каждом следующем уровне в качестве «кирпичиков» используются логические схемы, созданные на предыдущем этапе.

Дома вам необходимо было построить логические схемы, соответствующие логическим выражениям.

Вопрос учителя. Каков алгоритм построение логических схем?

Ответ учащихся. Алгоритм построение логических схем:

Определить число логических переменных.

Определить количество базовых логических операций и их порядок.

Изобразить для каждой логической операции соответствующий ей элемент (вентиль).

Соединить вентили в порядке выполнения логических операций.

Проверка домашнего задания Приложение 1 . Домашнее задание. Часть 1

Построить логическую схему для логического выражения:

Алгебра логики дала конструкторам мощное средство разработки, анализа и совершенствования логических схем. Проще, и быстрее изучать свойства и доказывать правильность работы схемы с помощью выражающей её формулы, чем создавать реальное техническое устройство.

Таким образом, цель нашего следующего урока — изучить законы алгебры логики.

IV. Домашнее задание. Часть 2

V. Практическая работа.

Программа — тренажер «Построение логических схем»

www.Kpolyakov.narod.ru Программа «Logic»,

4) Ответ: l v 0 & l = 1.

Пример 2

Постройте логическую схему, соответствующую логическому выражению

F = X & Y v (Y v X).

Вычислить значения выражения для X = 1, Y = 0.

1) Переменных две: X и Y;

2) Логических операций три: конъюнкция и две дизъюнкции: 14 3 2 X & Y v (Y v X).

3) Схему строим слева направо в соответствии с порядком логических операций:

3) Вычислим значение выражения: F = l & 0 v (0 v 1) = 0

Выполните упражнение

Постройте логическую схему, соответствующую логическому выражению, и найдите значение логического выражения:

A) F = A v B & C, если А = 1, В=1, С=1.

Б) F = (A v B & C), если А=0, В=1, С=1.

B) F = A v B & C, если А=1, В=0, С=1.

Г) F = (А v В) & (С v В),еслиА=0, В=1, С=0.

Д) F = (А & В & С), если А=0, В=0, С=1.

Е) F = (A & B & C) v (B & C vA), если А=1, В=1,С=0.

Ж) F = B &A v B & A, если А=0, В=0.

Законы логики

Если логическое выражение содержит большое число операций, то составлять для него таблицу истинности достаточно сложно, так как приходится перебирать большое количество вариантов. В таких случаях формулы удобно привести к нормальной форме.

Формула имеет нормальную форму, если в ней отсутствуют знаки эквивалентности, импликации, двойного отрицания, при этом знаки отрицания находятся только при логических переменных.

Для приведения формулы к нормальной форме используют законы логики и правила логических преобразований.


	А= А	Закон тождества
	А&А=0	Закон противоречия
	Av A = l	Закон исключающего третьего
	А = А	Закон двойного отрицания
	A&0 = 0 A v 0 = A	Законы исключения констант
	А&1=А A v 1 = 1	Законы исключения констант
	А&А=А A v A=A	Правило идемпотентности
	AvA = l
	(А→В)=А&В
	A→B = A v B
	А& (Av В)= А	Закон поглощения
	A v (А & В) = A	Закон поглощения
	А& (Av В) = А & В
	AvA&B = A v B
	(AvB) vC =Av(BvC) (A&B)&C = A&(B&C)	Правило ассоциативности
	(A&B) v(A&C) = A&(BvC) (AvB)&(AvC) = Av(B&C)	Правило дистрибутивности
	AvB = BvA A&B = B&A	Правило коммутативности
	AóB = A&Bv(A&B)
	(AvB)= A & B	Законы Моргана
	(A&B)=Av B	Законы Моргана

Пример

Упростите логическое выражение F = ((A v В) → (В v С)) . Это логическое выражение необходимо привести к нормальной форме, т.к. в нем присутствует импликация и отрицание логической операции.

1. Избавимся от импликации и отрицания. Воспользуемся (8). Получится: ((AvB)→(BvC))= (AvB)&(BvC).

2. Применим закон двойного отрицания (4). Получим: (AvB)&(BvC)= (AvB)&(BvC)

3. Применим правило дистрибутивности (15). Получим:

(AvB)&(BvC)= (AvB)&Bv(AvB)&C.

4. Применим закон коммутативности (17) и дистрибутивности (15). Получим: (AvB)&Bv(AvB)&C = A&BvB&BvA&CvB&C.

5. Применим (16) и получим: A&BvB&BvA&CvB&C=A&BvBvA&CvВ&С

6. Применим (15), т.е вынесем за скобки В. Получим:

A&BvBv A&Cv B&C=B&(Av1)v A&Cv В&С

7. Применим (6). Получим: В &(Avl)v A&Cv В &С= Bv A&Cv В &С.

8. Переставим местами слагаемые, сгруппируем и вынесем В за скобки. Получим:
BvA&CvB&C = B&(1vC)vA&C.

9. Применим (6) и получим ответ:

Ответ: F = ((A v В) → (В v С)) = В v A & С.

Упростите выражение:

1) F = (A & B) v(B v C).

2) F = (A→B) v (B→A).

3) F = A & C vA & C.

4) F = A vB vC v A v B v C.

5) F = (X & Y v(X & Y)).

6) F= X &(Y v X).

7) F = (X v Z) & (X vZ) & (Y v Z).

10) F= B&C& (AvA).

11) F= A&B&CvAvB

12) F= (AvB)&(BvA)& (CvB)

Упростите выражение:

1. F = A & C vA & C.

2. F= A ↔ B v A&C

3. F=A& (B↔C)

4. F = (X v Y) & (Y ↔ X).

5. F= A vB vC v A v B v C.

6. F=(AvB) → (AvC)

7. F= А ↔ (В v C)

8. F = A & B → C & D.

9. F= (X & Y v(X & Y)).

10. F = (X v Y) & (Y v X).

11. F= A ↔ B &C

12. F = (A v B) & (B v A→ B).

13. F= X &(Y v X).

14. F= A → B v A&C

15. F = X & Y v X.

16. F = ((X v Y) & (Z → X)) & (Z v Y).

17. F= (X v Z) & (X vZ) & (Y v Z).

18. F= А →(В v C)

19. F= A ↔ B v C

20. F = ((X v Y) & (Z v X)) & (Z → Y).

21. F= (B & (A→C))

22. F= A → B v A&C

23. F= А ↔ (В v C)

24. F = ((X v Y) & (Z v X)) & (Z v Y).

25. F= (A→B) v (B→A).

26. F = A & B & C & D.

27. F= А ↔(В v C)

28. F=A& (B→C).

29. F= A&(AvB)

30. F= А ↔ (В v C)

31. F= A → B v A &C

32. F = (A v B) & (B v A v B).

33. F= B&C& (AvA).

34. F= A & B v A&C

35. F = X & Y ↔ X.

36. F = ((X v Y) & (Z → X)) & (Z ↔ Y).

37. F= A&B&CvAvB

38. F = (X → Y) & (Y v X).

39. F= A → B &C

40. F = (A ↔ B) & (B v A &B).

41. F = (AvB)&(BvA)& (CvB).

42. F= A & B v A&C

43. F=A& (BvC)

44. F = (X → Y) & (Y ↔ X).

45. F= Av(A&B)

46. F = A & B ↔ C & D.

47. F= А ↔(В v C)

48. F=(X & Y) v (Y & X).

Назначение сервиса . Онлайн-калькулятор предназначен для построения таблицы истинности для логического выражения .
Таблица истинности – таблица содержащая все возможные комбинации входных переменных и соответствующее им значения на выходе.
Таблица истинности содержит 2 n строк, где n – число входных переменных, и n+m – столбцы, где m – выходные переменные.

Инструкция . При вводе с клавиатуры используйте следующие обозначения: Например, логическое выражение abc+ab~c+a~bc необходимо ввести так: a*b*c+a*b=c+a=b*c
Для ввода данных в виде логической схемы используйте этот сервис .y) .

Максимальное количество переменных равно 10 .

Проектирование и анализ логических схем ЭВМ ведётся с помощью специального раздела математики — алгебры логики. В алгебре логики можно выделить три основные логические функции: «НЕ» (отрицание), «И» (конъюнкция), «ИЛИ» (дизъюнкция).
Для создания любого логического устройства необходимо определить зависимость каждой из выходных переменных от действующих входных переменных такая зависимость называется переключательной функцией или функцией алгебры логики.
Функция алгебры логики называется полностью определённой если заданы все 2 n её значения, где n – число выходных переменных.
Если определены не все значения, функция называется частично определённой.
Устройство называется логическим, если его состояние описывается с помощью функции алгебры логики.
Для представления функции алгебры логики используется следующие способы:

словесное описание – это форма, которая используется на начальном этапе проектирования имеет условное представление.
описание функции алгебры логики в виде таблицы истинности.
описание функции алгебры логики в виде алгебраического выражения: используется две алгебраические формы ФАЛ:
а) ДНФ – дизъюнктивная нормальная форма – это логическая сумма элементарных логических произведений. ДНФ получается из таблицы истинности по следующему алгоритму или правилу:
1) в таблице выбираются те строки переменных для которых функция на выходе =1 .
2) для каждой строки переменных записывается логическое произведение; причём переменные =0 записываются с инверсией.
3) полученное произведение логически суммируется.
Fднф= X 1 *Х 2 *Х 3 ∨ Х 1 x 2 Х 3 ∨ Х 1 Х 2 x 3 ∨ Х 1 Х 2 Х 3
ДНФ называется совершенной, если все переменные имеют одинаковый ранг или порядок, т.е. в каждое произведение обязательно должны включаться все переменные в прямом или инверсном виде.
б) КНФ – конъюнктивная нормальна форма – это логическое произведение элементарных логических сумм.
КНФ может быть получена из таблицы истинности по следующему алгоритму:
1) выбираем наборы переменных для которых функция на выходе =0
2) для каждого набора переменных записываем элементарную логическую сумму, причём переменные =1 записываются с инверсией.
3) логически перемножаются полученные суммы.
Fскнф=(X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3) ∧ (X 1 V X 2 V X 3)
КНФ называется совершенной , если все переменные имеют одинаковый ранг.

По алгебраической форме можно построить схему логического устройства , используя логические элементы.

Рисунок1- Схема логического устройства

Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операции для всех возможны х логических значений исходных высказываний. Количество вариантов, отражающих результат применения операций, будет зависеть от количества высказываний в логическом выражении. Если число высказываний в логическом выражении N, то таблица истинности будет содержать 2 N строк, так как существует 2 N различных комбинаций возможных значений аргументов.

Операция НЕ — логическое отрицание (инверсия)

Логическая операция НЕ применяется к одному аргументу, в качестве которого может быть и простое, и сложное логическое выражение. Результатом операции НЕ является следующее:

если исходное выражение истинно, то результат его отрицания будет ложным;
если исходное выражение ложно, то результат его отрицания будет истинным.

Для операции отрицания НЕ приняты следующие условные обозначения:
не А, Ā, not A, ¬А, !A
Результат операции отрицания НЕ определяется следующей таблицей истинности:
Результат операции отрицания истинен, когда исходное высказывание ложно, и наоборот.

Операция ИЛИ — логическое сложение (дизъюнкция, объединение)

Логическая операция ИЛИ выполняет функцию объединения двух высказываний, в качестве которых может быть и простое, и сложное логическое выражение. Высказывания, являющиеся исходными для логической операции, называют аргументами. Результатом операции ИЛИ является выражение, которое будет истинным тогда и только тогда, когда истинно будет хотя бы одно из исходных выражений.
Применяемые обозначения: А или В, А V В, A or B, A||B.
Результат операции ИЛИ определяется следующей таблицей истинности:
Результат операции ИЛИ истинен, когда истинно А, либо истинно В, либо истинно и А и В одновременно, и ложен тогда, когда аргументы А и В — ложны.

Операция И — логическое умножение (конъюнкция)

Логическая операция И выполняет функцию пересечения двух высказываний (аргументов), в качестве которых может быть и простое, и сложное логическое выражение. Результатом операции И является выражение, которое будет истинным тогда и только тогда, когда истинны оба исходных выражения.
Применяемые обозначения: А и В, А Λ В, A & B, A and B.
Результат операции И определяется следующей таблицей истинности:

A	B	А и B
0	0	0
0	1	0
1	0	0
1	1	1

Результат операции И истинен тогда и только тогда, когда истинны одновременно высказывания А и В, и ложен во всех остальных случаях.

Операция «ЕСЛИ-ТО» — логическое следование (импликация)

Эта операция связывает два простых логических выражения, из которых первое является условием, а второе — следствием из этого условия.
Применяемые обозначения:
если А, то В; А влечет В; if A then В; А→ В.
Таблица истинности:

A	B	А → B
0	0	1
0	1	1
1	0	0
1	1	1

Результат операции следования (импликации) ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно.

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Применяемое обозначение: А ↔ В, А ~ В.
Таблица истинности:

A	B	А↔B
0	0	1
0	1	0
1	0	0
1	1	1

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Применяемое обозначение: А XOR В, А ⊕ В.
Таблица истинности:

A	B	А⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны.

Приоритет логических операций

Действия в скобках
Инверсия
Конъюнкция (&)
Дизъюнкция (V), Исключающее ИЛИ (XOR), сумма по модулю 2
Импликация (→)
Эквивалентность (↔)

Совершенная дизъюнктивная нормальная форма

Совершенная дизъюнктивная нормальная форма формулы (СДНФ) это равносильная ей формула, представляющая собой дизъюнкцию элементарных конъюнкций, обладающая свойствами:

Каждое логическое слагаемое формулы содержит все переменные, входящие в функцию F(x 1 ,x 2 ,…x n).
Все логические слагаемые формулы различны.
Ни одно логическое слагаемое не содержит переменную и её отрицание.
Ни одно логическое слагаемое формулы не содержит одну и ту же переменную дважды.

СДНФ можно получить или с помощью таблиц истинности или с помощью равносильных преобразований.
Для каждой функции СДНФ и СКНФ определены единственным образом с точностью до перестановки.

Совершенная конъюнктивная нормальная форма

Совершенная конъюнктивная нормальная форма формулы (СКНФ) это равносильная ей формула, представляющая собой конъюнкцию элементарных дизъюнкций, удовлетворяющая свойствам:

Все элементарные дизъюнкции содержат все переменные, входящие в функцию F(x 1 ,x 2 ,…x n).
Все элементарные дизъюнкции различны.
Каждая элементарная дизъюнкция содержит переменную один раз.
Ни одна элементарная дизъюнкция не содержит переменную и её отрицание.

Пример решение логических задач средствами алгебры логики

Логические схемы

Логическая схема – это схематическое изображение некоторого устройства, состоящего из переключателей и соединяющих их проводников, а также из входов и выходов, на которые подаётся и с которых снимается электрический сигнал.

Каждый переключатель имеет только два состояния: замкнутое и разомкнутое . Переключателю Х поставим в соответствие логическую переменную х, которая принимает значение 1 в том и только в том случае, когда переключатель Х замкнут и схема проводит ток; если же переключатель разомкнут, то х равен нулю.

Две схемы называются равносильными , если через одну из них проходит ток тогда и только тогда, когда он проходит через другую (при одном и том же входном сигнале).

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

При рассмотрении переключательных схем возникают две основные задачи: синтез и анализ схемы.

СИНТЕЗ СХЕМЫ по заданным условиям ее работы сводится к следующим трём этапам:

составлению функции проводимости по таблице истинности, отражающей эти условия;
упрощению этой функции;
построению соответствующей схемы.

АНАЛИЗ СХЕМЫ сводится к:

определению значений её функции проводимости при всех возможных наборах входящих в эту функцию переменных.
получению упрощённой формулы.

Задача : Составить таблицу истинности для данной формулы: (x ~ z) | ((x y) ~ (y z)).

Решение : В таблицу истинности данной формулы полезно включить таблицы истинности промежуточных функций:

xyz	x ~ z	x y	y z	(x y) ~ (y z)	(x~ z)\|((x y) ~ (yz)

Методические указания для выполнения практического задания №2. «Алгебра логики». Построение таблиц истинности.

Цель работы : Ознакомиться с основными арифметическими операциями, базовыми логическими элементами (И, И-НЕ, ИЛИ, ИЛИ-НЕ, исключающее ИЛИ) и изучить методы построения на их основе таблиц истинности.

Задание:

1. В приложении 2 выбрать вариант задания и составить таблицу истинности .

2. Выполнить задание, используя пример решение логических задач средствами алгебры логики.

Задача :

Построить логическую схему по заданному булевому выражению:

F =`BA + B`A + C`B.

Решение:

Как правило, построение и расчет любой схемы осуществляется начиная с ее выхода.

Первый этап : выполняется логическое сложение, логическую операцию ИЛИ, считая входными переменными функции`B A, B`A и C`B:

Второй этап : к входам элемента ИЛИ подключаются логические элементы И, входными переменными которых являются уже A, B, C и их инверсии:

Третий этап : для получения инверсий`A и`B на соответствующих входах ставят инверторы:

Данное построение основано на следующей особенности, – поскольку значениями логических функций могут быть только нули и единицы, то любые логические функции могут быть представлены как аргументы других более сложных функций. Таким образом, построение логической схемы осуществляется с выхода ко входу.

Методические указания для выполнения практического задания №3. «Алгебра логики». Построение логических схем

Задание:

1. В приложении 2 выбрать вариант задания и построить логическую схему .

2. Выполнить задание, используя пример построения логических схем.

3. Оформить работу в тетради для практических работ.

4. Результат работы предъявить преподавателю.

5. Защитить выполненную работу у преподавателя.

Приложение 2. Таблица вариантов заданий

Составить таблицу истинности и логическую схему для данных операций
Вариант	Операции

4. Индивидуальное задание. Модуль 1. «Построение логических схем по заданным булевым выражениям»

Задания к ИДЗ:

В приложении 3 выбрать вариант индивидуального задания.
Выполнить задание, пользуясь теоретическими сведениями
Проверить логическую схему у тьютора.
Оформить ИДЗ в формате А4, титульный лист по образцу Приложение 4.
Результат работы предъявить преподавателю.
Защитить выполненную работу у преподавателя.

Приложение 3. Таблица вариантов индивидуального задания

Варианты	Составить таблицу истинности и логическую схему по формулам

Приложение 4. Титульный лист ИДЗ

Создание выражений

Для каждой выходной переменной окно Комбинационный анализ поддерживает две структуры — соответствующую колонку таблицы истинности и логическое выражение — указывающее, как каждый выход связан со своими входами. Вы можете редактировать и таблицу истинности и выражение; одно будет автоматически менять другое по мере необходимости, чтобы они соответствовали друг другу.

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

Вы можете просматривать и редактировать выражения, используя две последние вкладки: Выражение и Минимизация.

Вкладка Выражение

Вкладка Выражение позволяет вам просматривать и редактировать текущее выражение, связанное с каждой выходной переменной. Вы можете выбрать выходное выражение, которое вы хотите просматривать и изменять, с помощью списка «Выход:» наверху вкладки.

Чуть ниже списка появится выражение, отформатированное в довольно общепринятых обозначениях, где ИЛИ представляется в виде сложения, И — как умножение, а НЕ обозначается чертой над той частью, для которой вычисляется НЕ.

Текстовое поле ниже отображает ту же информацию в виде ASCII последовательности. Здесь НЕ представляется как тильда (‘~’).

Вы можете изменить выражение в текстовом поле и нажать кнопку Ввести, чтобы изменения вступили в силу; это также обновит таблицу истинности для соответствия. Кнопка Очистить очищает текстовое поле, а кнопка Вернуть меняет поле обратно к представлению текущего выражения.

Обратите внимание, что отредактированные вами выражения будут потеряны, если вы измените таблицу истинности.

В дополнение к умножению и сложению, обозначающим И и ИЛИ, выражение, которое вы набираете, может содержать любой из логических операторов C/Java, а также просто английские слова сами по себе.

высший приоритет	~ ! ‘	НЕ
	(отсутствие символа) & && AND	И
	^ XOR	Исключающее ИЛИ
низший приоритет	+ \| \|\| OR	ИЛИ

Все нижеприведённые примеры — допустимые представления одного и того же выражения. Кроме того, можно смешивать операторы.

a’ (b + c)

!a && (b || c)

NOT a AND (b OR c)

Вообще-то, скобки в последовательностях AND’ов (или OR’ов или XOR’ов) не имеют значения. (В частности, когда Logisim создаёт соответствующую схему, он будет игнорировать такие скобки.)

Вкладка Минимизация

Последняя вкладка отображает минимизированное выражение, соответствующее столбцу таблицы истинности. Вы можете выбрать, для какого выхода вы хотите просматривать минимизированное выражение с помощью списка сверху, и можете указать, какое выражение вы хотите получить — сумму произведений или произведение сумм, с помощью списка снизу.

Если входов четыре или меньше, то ниже списка появится карта Карно, соответствующая выходной переменной. Вы можете щёлкать на карте Карно для изменения соответствующих значений таблицы истинности. Карта Карно будет также показывать выбранные в данный момент для минимизированного выражения термы в виде сплошных полупрозрачных скругленных прямоугольников.

Ниже — само минимизированное выражение, отформатированное так же, как во вкладке Выражение. Если выходов более четырёх, то карта Карно не появится, но минимизированное выражение всё равно будет вычислено. (Logisim использует метод Куайна — Мак-Класки для вычисления минимизированного выражения. Он эквивалентен карте Карно, но применим к любому числу входных переменных.)

Кнопка Установить как выражение позволяет вам выбрать минимизированное выражение как выражение, соответствующее переменной. Это, как правило, не нужно, поскольку изменения в таблице истинности приводят к использованию минимизированного выражения для изменённого столбца; но если вы введете выражение через вкладку Выражение, то это может быть удобно, чтобы перейти к соответствующему минимизированному выражению.

Далее: Создание схемы.

Виды задач на логические элементы.

Построение логической схемы по заданной логической функции;
Запись логической функции по заданной логической схеме;
Определение сигнала на выходе логической схемы по заданным значениям сигналов на всех входах этой схемы;
Построение таблицы истинности для заданной логической схемы;

Познакомимся с ними поочередно.

Построение логической схемы по заданной логической функции.

Задача:

Дана логическая функция:

Составить логическую схему для неё.

Решение:

Расставим порядок выполнения логических операций, руководствуясь правилами:

отрицание
умножение
сложение

Не забываем про приоритет скобок.
Получаем:

Строим схему по указанному порядку. Посмотреть.

Запись логической функции по заданной логической схеме.

Задача:

Дана логическая схема:

Составить логическую функцию по ней.

Решение:

Рассматриваем схему с конца и записываем соответствующие логические операции, учитывая, что в записываемой функции три операнда А, В, С Посмотреть.

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

Определение сигнала на выходе логической схемы по заданным значениям сигналов на всех входах этой схемы.

Задача:

Дана логическая схема и значения сигналов на всех входах:

Определить значение функции F на выходе схемы.

Решение:

Пользуясь таблицами истинности для соответствующих логических элементов схемы, расставляем значения сигналов на выходах и соответственно на входах каждого логического элемента пока не доберёмся до конца схемы. Получаем:

Ответ:

Значение функции F на выходе схемы = 1. Построение таблицы истинности для заданной логической схемы.

Задача:

Дана логическая схема:

Построить для неё таблицу истинности.

Решение:

Проверяем количество входов на схеме. Количество комбинаций сигналов на 2 входах равно 4, для 3 входов равно 8, для 4 входов равно 16 и т. д. Составляем таблицу истинности, в которой первые столбцы — это входы схемы, обозначенные буквами, следущие столбцы — функции, полученные на выходах каждого элемента схемы, а строки — отражают разные комбинации сигналов на входах. Количество строк совпадает с количеством комбинаций сигналов. Пользуясь таблицами истинности для соответствующих логических элементов схемы, расставляем значения сигналов на выходах каждого логического элемента, т. е. по каждому столбцу пока не доберёмся до конца схемы. Получаем:

Ответ:

Запишите логическую функцию соответствующую функциональной схеме

Примеры решения задач “Логические основы работы компьютера”

Дана логическая функция: F (А,В) = ¬ (А / В). Постройте соответствующую ей функциональную схему.

Функциональная схема будет содержать 2 входа А и В. Рассмотрим логическое выражение и определим порядок действий в нем:

1) первым выполняется логическое умножение А / В, следовательно, сигналы с входов А и В подаются на конъюнктор;

2) далее выполняется логическое отрицание ¬(А / В), следовательно, сигнал, полученный на выходе из конъюнктора должен быть инвертирован, т.е. подан на инвертор.

Выход инвертора является выходом функциональной схемы.

Изобразим схему, следуя данным действиям:

Определите логическую функцию, соответствующую заданной функциональной схеме:

Решение:

Функциональная схема содержит 2 входа А и В. Вход А инвертирован и его выход является входом дизъюнктора. Вход В подает сигнал на дизъюнктор. Выход дизъюнктора является выходом функциональной схемы.

Итак, последовательность действий:

1) ¬A – сигнал входа А инвертирован;

2) ¬A / B – на дизъюнктор подают инвертированный сигнал входа А и нормальный входа В.

Выход дизъюнктора является выходом функциональной схемы. Следовательно, логическая функция F –это функция двух переменных А и В и имеет вид:

Постройте логическую схему, соответствующую логическому выражению и найдите значение логического выражения: F=A/B/ ¬C, если А=1, В=1, С=1.

Значение логического выражения – 1

Постройте логическую схему, соответствующую логическому выражению и найдите значение логического выражения: F= ¬(A/B/C),если А=0, В=1, С=1.

Сигнал, выработанный одним логическим элементом можно подавать на вход другого логического элемента. Это дает возможность образовывать цепочки из отдельных логических элементов. На рисунке 15 показаны примеры таких цепочек.

а)

б)

На рисунке 15 а) элемент ИЛИ (дизъюнктор) соединен с элементом НЕ (инвертор), а на рисунке 15 б) — элемент И (конъюнктор) с элементом НЕ (инвертор). Каждую такую цепочку будем называть логическим устройством: поскольку она состоит из нескольких элементов.

Цепочку из логических элементов будем называть логическим устройством. Схемы, соответствующие таким устройствам, называют функциональными .

Составить логическую схему по функциональной формуле достаточно просто. Например, функциональная схема, изображенная на рисунке 16, имеет два входа A и B. До поступления на конъюнктор B отрицается, а затем отрицается результат логического умножения. Все это приводит нас к формуле

(21)

которая представляет собой структурную формулу логического устройства. Важно научиться решать и обратную задачу: по структурной формуле вычерчивать соответствующую ей функциональную схему. Усложним задачу. Пусть имеется произвольная логическая функция, требуется построить функциональную схему.

Алгоритм решения такой задачи начинается с построения таблицы истинности. Затем в таблице следует определить одну или несколько строк, с результатом равным 1. На следующем шаге необходимо выписать комбинацию входных переменных, соединенных логическим умножением. Если входная переменная в нужной нам строке имеет значение 0, то она должна войти в логическое выражение с отрицанием. Полученные таким образом конъюнкции требуется логически сложить. Далее полученную формулу нужно сократить с использованием логических законов. Рассмотрим этот алгоритм на следующем примере.

Задача 7. Начертить функциональную схему, соответствующую таблице истинности.

Рассмотрим строки, которые в столбце F(A,B) дают истину (эти строки в таблице выделены). Составим по первой строке выражение (A следует отрицать, потому что в таблице стоит 0), аналогичное выражение по третьей строке дает . Соединяем два последних выражения союзом ИЛИ , получим . Вычерчиваем по логическому выражению функциональную схему.

Логическую функцию F(A,B)=&#256 &#923 B V A &#923 называют операцией XOR (исключающее или) и обозначают .

Еще один пример построения функциональной схемы.


	Задача 8.

Начертить функциональную схему, соответствующую таблице истинности.

A	B	C	результат

		1
	1
	1	1	1
1			1
1		1	1
1	1		1
1	1	1	1

Решение.

Выделяем в таблице строки, когда результатом функции является истина.

A	B	C	результат
	1	1	1
1			1
1		1	1
1	1		1
1	1	1	1

Для первой строки последней таблицы имеем.

(22)

для второй строки —

(23)

для третьей строки —

(24)

(24) для четвертой строки —

(25)

(25) и для пятой строки —

(26)

Соединяем выражения (22)-(26) логическим сложением. Будем иметь

(27)

Теперь требуется упростить (27) на основе логических законов. .

Таким образом, получили: .

(28)

Построим функциональную схему. Для этого потребуется отрицание A с последующим умножением на B, затем на C и, наконец, сложение с A. Полученная функциональная схема представлена на рисунке 18.

По заданной таблице истинности составить СДНФ или СКНФ, упростить её, если возможно. Построить функциональную схему

Вариант № 16

Определите значение логического выражения:

Найдите значения выражений:

Определить истинность составного высказывания:

если значения простых высказываний следующие:

А = <Принтер – устройство хранения информации>

В = <Сканер – служит для ввода информации.>

С = <Система команд –совокупность операций, выполняемых некоторым компьютером.

Построить таблицу истинности для выражения (п. 3)

Упростите выражение, правильность упрощения проверьте с помощью таблиц истинности для исходного и полученного логического выражения: (c. 149)

Постройте функциональную схему для логической функции.

Построение логических схем выражений на примерах

Примеры решения задач «Логические основы работы компьютера»

Теория по этой теме по этой теме Пройти тестирование по этой теме Контрольная по этой теме

№1.

Дана логическая функция: F(А,В) = ¬ (А /\ В). Постройте соответствующую ей функциональную схему.

Решение:

1) первым выполняется логическое умножение А /\ В, следовательно, сигналы с входов А и В подаются на конъюнктор;

2) далее выполняется логическое отрицание ¬(А /\ В), следовательно, сигнал, полученный на выходе из конъюнктора должен быть инвертирован, т.е. подан на инвертор.

Выход инвертора является выходом функциональной схемы.

Изобразим схему, следуя данным действиям:

№2.

Определите логическую функцию, соответствующую заданной функциональной схеме:

Решение:

Итак, последовательность действий:

1) ¬A — сигнал входа А инвертирован;

2) ¬A \/ B — на дизъюнктор подают инвертированный сигнал входа А и нормальный входа В.

F(A, B) = ¬A \/ B

Ответ: F(A, B) = ¬A \/ B

№3.

Постройте логическую схему, соответствующую логическому выражению и найдите значение логического выражения: F=A\/B/\ ¬C, если А=1, В=1, С=1.

Решение:

Значение логического выражения — 1

№4.

Постройте логическую схему, соответствующую логическому выражению и найдите значение логического выражения: F= ¬(A\/B/\C),если А=0, В=1, С=1.

Решение:

Значение логического выражения — 1

Программа для построения логических схем

Почему необходимо уметь строить логические схемы?

Дело в том, что из вентилей составляют более сложные схемы, которые позволяют выполнить арифметические операции и хранить информацию. Причем схему, выполняющую определенные функции, можно построить из различных по сочетанию и количеству вентилей. Поэтому значение формального представления логической схемы чрезвычайно велико. Оно необходимо для того, чтобы разработчик имел возможность выбрать наиболее подходящий ему вариант построения схемы из вентилей. Процесс разработки общей логической схемы устройства (в том числе и компьютера в целом) таким образом становится иерархическим, причем на каждом следующем уровне в качестве «кирпичиков» используются логические схемы, созданные на предыдущем этапе.

Алгебра логики дала в руки конструкторам мощное средство разработки, анализа и совершенствования логических схем. В самом деле, гораздо проще, быстрее и дешевле изучать свойства и доказывать правильность работы схемы с помощью выражающей ее формулы, чем создавать реальное техническое устройство. Именно в этом состоит смысл любого математического моделирования.

Логические схемы необходимо строить из минимально возможного количества элементов, что в свою очередь, обеспечивает большую скорость работы и увеличивает надежность устройства.

Алгоритм построения логических схем :

1) Определить число логических переменных.

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

3) Изобразить для каждой логической операции соответствующий ей вентиль.

4) Соединить вентили в порядке выполнения логических операций.

Составить логическую схему для логического выражения: F = ¬ X v Y & X .

1) Две переменные – X и Y .

2) Две логические операции: 1 3 2

3) Строим схему, соединяя вентили в порядке выполнения логических операций:

Постройте логическую схему, соответствующую логическому выражению F = X & Y v ¬ ( Y v X ).

Вычислить значения выражения для X =1, Y =0.

1) Переменных две: X и Y .

2) Логических операций четыре: конъюнкция, две дизъюнкции и отрицание. Определяем порядок выполнения операций:

3) Схему строим слева направо в соответствии с порядком выполнения логических операций:

4) Вычислим значение выражения: F =1&0 v ¬ ( 0 v 1)=0.

1) F=A v B& ¬ C, если A=1, B=1, C=1 .

2) F = ¬ (A v B&C), если A=0, B=1, C=1 .

3) F = ¬ A v B&C, если A=1, B=0, C=1 .

4) F =(A v B)&(C v B), если A=0, B=1, C=0 .

5) F = ¬ (A&B&C), если A=0, B=0, C=1 .

6) F=B& ¬ A v ¬ B&A, если A=0, B=0 .

7) F= ¬ (A&B&C) v (B&C v ¬ A), если A=1, B=1, C=0 .

Инструкция . Для добавления логического элемента выберите его тип и количество входов, нажмите на поле. Для его удаления нажмите правой кнопкой мыши над его местоположением.

Ввод данных
Решение
Видеоинструкция

Стандарт изображений элементов

Выберите логический элемент:

Cоединить элемент с переменной по входу Соединить

Cоединить элемент с элементом по входу Соединить

Цвет линий Цвет элементов

Для последнего элемента входы

Для послелнего элемента разделяющие линии

Операция И НЕ (штрих Шеффера)

Операция ИЛИ НЕ

Сложение по модулю2

Исключающее ИЛИ НЕ

Операция И НЕ (штрих Шеффера)

Операция ИЛИ НЕ

Сложение по модулю2

Исключающее ИЛИ НЕ

Каждая страница разделена на секции, каждая секция описывается названием (навигация по заголовкам).
Наиболее важным разделам присвоена определенная роль (навигация по ориентирам)
В верхней части каждой страницы вы найдете меню быстрого перехода ( ссылки внутренней навигации). Каждая ссылка привязана к определенной клавише (кнопке быстрого вызова).

Внимание: вы используете устаревший браузер! Мы советуем вам обновить программное обеспечение до новой версии или скачать альтернативный браузер: здесь вы можете загрузить последнюю версию Firefox.
Если вы работаете в операционной системе Windows на компьютере с низкой производительностью Midori.

Внимание, ваш браузер устарел и больше не поддерживается. Мы рекомендуем просматривать наш вебсайт в режиме полный доступ.

Опции формата

Внешний вид:

Ширина просмотра:

Поиск

Оценка по информатике ниже пятёрки быть не может!

Дополнительные ресурсы (левая колонка)

Конструктор логических схем

Multimedia Logic (MMLogic) — это бесплатная программа-конструктор, с помощью которой можно моделировать логические схемы любой сложности и устройства компьютера. Её автор — George Mills — разместил на сайте фирмы Softronix не только исполняемый файл программы, но и её исходные тексты на Visual C++ 7.1.

В оригинальной версии MMLogic существует две проблемы:

интерфейс программы — англоязычный;
в программе используются зарубежные обозначения логических элементов, которые сильно отличаются от отечественных (ГОСТ 2.743—91).

НЕ	И	ИЛИ	XOR
зарубежные
ГОСТ 2.743—91

Русифицированный и адаптированный вариант соотвествует ГОСТ 2.743—91

Логика и схемы

Карл Берч, Hendrix College, сентябрь 2011 г.

Логика и схемы Карла Берча под лицензией Creative Commons Attribution-Share Alike 3.0 США Лицензия.
На основе работы на www.cburch.com/books/logic/ .

Содержание

Чтобы понять, как работают компьютеры, мы захотим понять основы цифровых схем. Как оказалось, цифровые схемы построены на основе базовой логики.

1. Логические схемы

На самом базовом уровне, конечно, компьютер — это электрическая схема построена из проводов . Мы будем думать о каждом проводе в цепи как о несущем одну информацию. элемент, называемый бит . Слово бит происходит от B inary dig IT , используя термин двоичный , потому что бит может иметь любое из два возможных значения, 0 и 1. С точки зрения электричества вы можете думать о нулевом вольт представляющий 0 и пять вольт, представляющий 1; но для нашего цели, конкретные напряжения не важны — и действительно существуют различные системы для интерпретации уровней напряжения как 0 или 1.(Люди экспериментировали с более чем двумя разными уровнями напряжения, но это в конечном итоге приводит к более сложным и сложным схемам. в конечном итоге оказывается менее эффективным, чем двоичная система.)

Вот пример, показывающий схему простой логической схемы.

Рисунок 1: Простая логическая схема.

Эта диаграмма состоит из некоторых необычных форм, связанных с несколько строк. Линии представляют собой провода; формы представляют так называемые логические элементы , которые мы изучим скоро.

Мы будем думать о каждом проводе как о несущем немного, пока он не попадет в ворота. Вы можете видеть, что некоторые провода пересекаются в маленьком сплошном круге: Этот кружок указывает на то, что провода подключены, и поэтому поступающие значения в круг продолжите вниз все провода, соединенные с кругом. Если два провода пересекаются без круга, это означает, что один провод проходит через другой, как эстакада между штатами, и значение на одном проводе не влияет на другой.

(В наших схемах мы будем рисовать системы проводов, используя разные цвета, поэтому вы можете сказать, что два провода не соприкасаются когда вы видите их в разных цветах.Однако традиционно схемы нарисованы только черным и белым, и эти точки имеют решающее значение для понимание того, когда провода пересекаются, а когда они перекрываются.)

Предположим, что мы взяли нашу примерную схему из Рисунок 1 и отправьте бит 0 на верхний вход ( x ) и 1 бит на нижнем входе ( y ). Затем эти входы будут перемещаться по проводам, пока не попадут в логический вентиль.

Так что же происходит, когда вход достигает логического элемента? Это зависит от какой это тип логического элемента.Есть три основных типа логические ворота, изображенные в трех разных формах.

	НЕ ворота:	Берет один бит слева и производит противоположный бит справа (рис. 2 (а)). Для верхнего элемента НЕ в нашем примере его вход от `x` равен 0, поэтому на выходе вентиль выдает 1.
	И ворота:	Принимает два входа слева и выход 1 справа только если оба входа и , второй вход равен 1 (Рисунок 2 (б)).Для верхнего логического элемента И в нашем примере его верхний вход равен 1. от `до` , а его нижний вход равен 1 от верхнего НЕ ворота; оба входа равны 1, поэтому логический элемент И производит 1 как его выход.
	ИЛИ ворота:	Принимает два входа слева и выход 1 на его право, если либо первый вход , либо второй вход равен 1 (или если оба равны 1). (Рисунок 2 (c))

Вот удобная мнемоника для различения форм для OR и AND: Символ ворот И выглядит как заглавная буква D , которую вы можете найти в слове И .

Рисунок 2: Логическое поведение ворот.
(а) НЕ вентиль (b) И ворота (c) ИЛИ ворота

После фильтрации значений через ворота на основе поведения На рис.2 значения в схеме будет следующим.

На основе этой диаграммы мы можем видеть, что когда x равно 0, а y равно 1, выход o равен 1.

Выполняя такое же распространение для других комбинаций входных данных значений, мы можем составить следующую таблицу, показывающую, как это Схема ведет себя для разных комбинаций входов.

Чтобы интерпретировать эту таблицу, рассмотрим вторую строку: у него 0 в столбце x , 1 в y столбец, и 1 в столбце o .Это означает, что если вход x равен 0, а вход y равен 1, тогда выход схемы o будет 1.
Такая таблица называется таблицей истинности . Таблица истинности содержит строку для всех возможных комбинация входных значений а также каждая строка сообщает, какое значение будет на выходе схемы. для этой комбинации входов. В этом примере таблицы у нас есть четыре строки, представляющие каждую Возможна комбинация x и y .В нашей таблице истинности было бы восемь строк, если бы в схеме было три входы; и было бы шестнадцать, если бы схема имела четыре входа.
2. Построение логических схем
В предыдущем разделе мы видели, как работают логические схемы. Это полезно когда вы хотите понять, как ведет себя схема. Но компьютерные дизайнеры часто сталкиваются с противоположной проблемой: желаемое поведение, как мы можем построить такую схему? Или задать тот же самый основной вопрос: как мы можем преобразовать истину таблицу в логическую схему?
В этом разделе мы рассмотрим систематическую технику проектирования схемы.Однако сначала мы сделаем необходимый обходной путь, изучив Логические выражения.
2.1. Логические выражения
В середине девятнадцатого века Джордж Буль разработал систему логики, которая составляет основу современный компьютер. Он заметил, что логические функции могут быть построены из операторов И, ИЛИ и НЕ операций и что это наблюдение приводит к рассуждению о логика в математической системе.
Поскольку Буль работал в девятнадцатом веке, конечно, он не думать о логических схемах.Он изучал сферу логика создан для размышлений о справедливости философских аргументов. Философы задумывались над этим предметом еще со времен Аристотель. Логики формализовали некоторые типичные ошибки, например, соблазн заключить, что если A подразумевает B , и если B удерживает, то A также должно удерживаться. («Гениальные люди носят очки, а я ношу очки, так что я, должно быть, гениален »)
Как математик Буль искал способ кодировать предложения. как это в алгебраические выражения, и он изобрел то, что мы теперь называем Логические выражения .Пример логического выражения: « y x + y x ». Линия над переменной (или большее выражение) представляет НЕ; для Например, выражение y соответствует кормлению y через ворота НЕ. Умножение (как в случае x y ) представляет собой AND. В конце концов, рассуждал Буль, таблица истинности AND (Рисунок 2 (б)) идентичен таблица умножения над 0 и 1.Сложение (как в случае x + y ) представляет собой OR. Таблица истинности OR (рис. 2 (c)) не совпадает с таблицей сложения более 0 и 1 в точности. — 1 OR 1 равно 1, но 1 плюс 1 равно 2 — но, Boole решил, что это достаточно близко.
В логических выражениях мы наблюдаем регулярный порядок операций: Умножение (И) предшествует сложению (ИЛИ). Таким образом, когда мы пишем y x + y x , мы имеем в виду ( y x + y x ).Мы можем использовать круглые скобки, когда этот порядок операций не тот, который мы хотеть. Для НЕ, полоса над выражением указывает степень выражение, к которому оно применяется; таким образом, x + y представляет НЕ x ИЛИ y ), а x + y представляет (НЕ x ) ИЛИ (НЕ y ).
Предупреждение: Студенты, плохо знакомые с логическими выражениями, часто пытаются сокращать x y as x y — то есть они рисуют одну линию над всем выражением, а не двумя отдельными строками над двумя отдельные части.Это сокращение неправильное . Первый, x y , переводится как (НЕ x ) И (НЕ y ) (то есть оба x и y равны 0), а x y преобразуется в НЕ ( x И y ) (то есть x и y не являются одновременно 1). Мы могли бы составить таблицу истинности, сравнивая результаты для этих двух выражения.
x y x y x y x y x y
0 0 1 1 1 0 1
0 1 1 0 0 0 1 0 0 1 0 0 1
1 1 0 0 0 1 0
Поскольку пятый столбец ( x y ) и седьмой столбец ( x y ) не идентичны, два выражения не идентичны эквивалент.
Каждое выражение напрямую соответствует схеме и наоборот. Чтобы определить выражение, соответствующее логической схеме, мы пропускаем выражения через схему так же, как распространяются значения через это. Предположим, мы делаем это для нашей схемы Рисунок 1.
Входы верхнего логического элемента И: y и x , и поэтому он выводит y x . Нижний вентиль И выводит y x , а логический элемент ИЛИ объединяет эти два в y x + y x .
2.2. Законы булевой алгебры
Булева система записи логических выражений называется Булева алгебра . Это называется алгебра , потому что мы можем манипулировать символами, используя законы, подобные те из традиционной алгебры. Например, коммутативный закон применяется как к OR, так и к AND. Чтобы доказать, что OR коммутативен (т. Е. Что A + B = B + A , мы можем заполнить таблицу истинности, демонстрирующую, что для каждого возможного комбинация A и B , значения A + B и B + A идентичны.
A B А + В B + A
0 0 0 0
0 1 1 1
1 0 1 1
1 1 1
Поскольку третий и четвертый столбцы совпадают, мы можем заключить, что A + B = B + A — универсальный закон.
Поскольку ИЛИ (и И) коммутативны, мы можем свободно изменить порядок терминов, не меняя значения выражения. Коммутативный закон OR позволит нам преобразовать y x + y x в y x + y x , а закон коммутативности И (примененный дважды) позволяет преобразовать это на x y + x y .
Точно так же ИЛИ (и И) имеет ассоциативный закон (т. Е. A + ( B + C ) = ( A + B ) + C . Из-за этой ассоциативности мы можем писать A + B + C (и A B C ) без скобок — ведь ставя круглые скобки вокруг первой пары ( A + B ) приводит к тому же результату, что и скобки вокруг второй пары ( B + C ).При рисовании схем мы будем рисовать логические элементы И и ИЛИ. которые имеют несколько входов. 3-входной логический элемент И фактически соответствовал бы двум логическим элементам И с 2 входами, когда схема на самом деле проводной. Есть два возможных способа подключить это.
Из-за ассоциативного закона для AND не имеет значения, что мы выбрать, и поэтому мы можем двусмысленно нарисовать И или ИЛИ ворота с тремя (и более) входами.
Существует множество таких законов, кратко представленных на Рисунке 3. Сюда входят аналоги всех важных алгебраических законов. имея дело с умножением и сложением.Есть также много законов, которых не придерживается . со сложением и умножением; в таблице они отмечены красным значком звездочка.
Рисунок 3: Сэмплер важных логических идентификаторов.
* Красные со звездочкой не соответствуют стандартным алгебраическим тождествам.
И OR
коммутативный A B = B A A + B = B + A
ассоциативный A ( B C ) = ( A B ) C A + ( B + C ) = ( A + B ) + C
идентификационный номер A ⋅ 1 = A А + 0 = А
распределительный A ( B + C ) = A B + A C * A + B C = ( A + B ) ( A + C ))
один / ноль А ⋅ 0 = 0 * А + 1 = 1
идемпотентность * A A = A * A + A = A
обратное * A A = 0 * A + A = 1
Закон ДеМоргана * A B = A + B * A + B = A B
двойное отрицание * А = А
2.3. Сумма произведений
Теперь мы можем вернуться к нашей проблеме: Если у нас есть конкретная логическая функция, которую мы хотим вычислить, как мы можем построить схему для ее вычисления? Начнем с описания логической функции как таблицы истинности. Предположим, мы начинаем со следующей функции, для которой хотим схема.
0 0
x y z o
0 0 0 0
1 1
0 1 0 1
0 1 1 0
1 0 0 55 1 0 1 0
1 1 0 1
1 1 1 1
Учитывая такую таблицу истинности, определяющую функцию, мы создадим логическое выражение, представляющее функцию.Для каждого ряда таблица , где желаемый результат — 1 , мы описываем это как И нескольких факторов.
x y z o описание
0 0 1 1 y z
0 1 0 1 x y z
1 1 1 x y z
1 1 1 1 x y z
Чтобы получить описание строки, мы выбираем для каждой переменной либо эта переменная или ее отрицание, в зависимости от того, в этой строке 1 или нет; а затем мы берем И этих вариантов.Например, глядя на первую строку выше, мы включаем x , поскольку x — 0 в этой строке, y , поскольку y также 0, и z , поскольку z равно 1; наше описание является И этих: x y z . Это выражение дает 1 для комбинации значений в этой строке; но для других строк его значение равно 0, поскольку каждая вторая строка отличается по какой-то переменной, и вклад этой переменной в И даст 0.
Как только у нас есть описания для всех строк, в которых желаемый результат равно 1, мы наблюдаем следующее: Значение желаемой схемы должно быть 1, если входы соответствуют к первому 1 ряду, второму 1 ряду, третьему 1 ряду, или четвертый 1-рядный. Таким образом, мы объединим выражения, описывающие строки, с ИЛИ:
x y z + x y z + x y z + x y z
Обратите внимание, что наше выражение не включает описания строк где таблица истинности сигнализирует, что желаемый результат равен 0: если бы мы это сделали, то это описание было бы 1, и поэтому ИЛИ все члены будут равны 1, а не 0, как мы хотим.
Это выражение сразу приводит к схеме Рисунок 4.
Рисунок 4: Схема, полученная из заданной таблицы истинности.
Окончательное выражение, которое мы получаем, называется суммой продукция выражение. Это называется так, потому что это ИЛИ (a сумма, если мы понимаем ИЛИ как сложение) нескольких И (продуктов, поскольку И соответствует умножению). Мы называем эту технику построение выражения из таблицы истинности суммы произведений Техника .
Этот метод суммирования произведений позволяет нам принимать любую функцию над битами. и построить схему для вычисления этой функции. Существование такой техники доказывает, что схемы могут вычислять любую логическую функцию.
Подведем итог: мы видели три способа описания логического функция: логических схем , таблиц истинности и Логические выражения . Более того, мы видели систематические способы преобразования между тремя техниками, схематически изображенными ниже.
Единственная отсутствующая стрелка — это преобразование из таблиц истинности в схемы; мы можем справиться с этим, преобразовав истину таблицу в логическое выражение (с использованием суммы произведений техника) и преобразовав это в схему.
3. Упрощающие схемы
Логические вентили — это физические устройства, построенные на транзисторах. На практике эффективность схемы имеет значение. Теперь мы перейдем к пониманию того, как измерить эффективности, и мы увидим метод, который часто приводит к более эффективная схема, чем та, к которой мы пришли, используя сумма произведений техники.
3.1. КПД схемы измерения
Мы можем измерить эффективность схемы по двум направлениям: пространство и скорость. Фактор пространства связан с тем, что каждый транзистор занимает место, а микросхема, содержащая транзисторы, ограничены по размеру, поэтому количество транзисторов, которые умещаются на микросхеме ограничено современными технологиями. Поскольку разработчики ЦП хотят соответствовать многие функции на чипе, они пытаются построить свои схемы с как можно меньше транзисторов для выполнения необходимых задач.К уменьшают количество транзисторов, пытаются создавать схемы с несколько логических ворот. Таким образом, мы можем приблизительно оценить использование пространства схема, просто подсчитав, сколько логических вентилей в схеме включает в себя.
Второй фактор, скорость, связан с тем, что транзисторы требуют времени. работать. Поскольку проектировщики хотят, чтобы схемы работали так быстро, как возможно, они работают, чтобы минимизировать глубину цепи , что является максимальным расстоянием от любого входа через схему до выход. Рассмотрим, например, две пунктирные линии на следующей схеме: которые указывают два разных пути от входа к выходу в схема.
Пунктирный путь, начинающийся с x , проходит через три ворот (ворота ИЛИ, затем ворота НЕ, затем еще одни ворота ИЛИ), а пунктирный путь, начинающийся с y , идет только через два ворот (ворота И и ворота ИЛИ). Есть еще два пути тоже, но ни один из путей не проходит более чем через три ворот. Таким образом, мы бы сказали, что глубина этой схемы равна 3. Это грубая мера скорости схемы: Вычисление выхода с помощью этой схемы занимает примерно три раза количество времени, которое требуется отдельным воротам для выполнения своей работы.
«Техника суммы произведений», которую мы видели для преобразования логической функции в схему не так уж и плохо используя эти критерии. Схема, полученная в результате этой техники имеет глубину всего 3 — или чуть больше, если вы настаиваете (как это будут делать разработчики схем), что каждый логический элемент И и ИЛИ имеет только два входы. Но он работает хуже, чем мы могли бы надеяться с точки зрения Космос.
3.2. Карно карты
Теперь перейдем к исследованию техники построения схемы из таблицы истинности, что приводит к меньшим схемам без каких-либо глубоких компромиссов.
Для логических функций с четырьмя или меньшим количеством входов Карта Карно — особенно удобный способ найти наименьшее возможное выражение суммы произведений. Это простой процесс: преобразовываем таблицу истинности в матрицу. как мы увидим позже, тогда мы определяем, как лучше «прикрыть» 1 в матрице с набором прямоугольников; каждый прямоугольник будет соответствуют члену в нашем выражении суммы произведений.
Начнем с таблицы истинности, используемой в Раздел 2.3.
0 0
x y z o
0 0 0 0
1 1
0 1 0 1
0 1 1 0
1 0 0 55 1 0 1 0
1 1 0 1
1 1 1 1
Поскольку в этой таблице восемь строк, мы преобразуем ее в матрицу 2 × 4.(Если бы было 4 строки, это был бы Матрица 2 × 2. А если бы строк было 16, это был бы Матрица 4 × 4.) Одна из переменных будет представлена по вертикальной оси, а две другие переменные — по Горизонтальная ось. Обратите внимание, как комбинации переменных вдоль горизонтальная ось делать , а не идти в традиционном порядке 00-01-10-11, а вместо этого 00-01-11-10. Это важно для Техника карты Карно для работы.
Создав эту матрицу, мы заполняем ее, копируя соответствующие выходные значения в соответствующую ячейку.Правда последняя строка таблицы, например, сопоставляется ячейке во второй строке матрицы (поскольку x — 1 в этой строке таблицы истинности) и третий столбец (поскольку y и z оба равны 1 в этой строке таблица истинности). В вывод в последней строке таблицы истинности — 1, поэтому мы помещаем 1 в эту ячейку матрицы. Ниже представлена заполненная матрица, с цифрой 1, соответствующей последней строке таблицы истинности в кружке.
Теперь мы ищем наименьший набор прямоугольных областей, покрывающих в нашей таблице все единицы, но нет нулей.Высота и ширина каждого прямоугольника. должно быть степенью двойки, поэтому возможны следующие варианты: 1 × 1, 1 × 2, 1 × 4, 2 × 1, 2 × 2, 2 × 4, 4 × 1, 4 × 2, и 4 × 4. В нашем примере мы можем охватить все единицы, используя всего три прямоугольника.
Каждому из регионов будет соответствовать член в сумме выражения продуктов, которые мы строим на основе выбранных регионы. Крайняя правая розовая область для Например, в столбце 10 соответствует члену, где y равно 1 и z равно 0, но x может быть либо 0, либо 1.Тогда соответствующий член будет y z . Положив вместе термины из трех регионов вместе получаем:
x y z + y z + x y
Это можно перевести в схему Рисунок 5. Обратите внимание, что эта схема имеет только 7 ворот по сравнению с 10 ворот на Рисунке 4.
Рисунок 5: Упрощенная схема, эквивалентная Рисунок 4.
3.3. Более сложная карта Карно
Другой пример проиллюстрирует некоторые дополнительные функции Карта Карно. На этот раз мы будем работать с таблицей истинности над четыре входа.
0 0 90
w x y z o
0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 0
0 1 0 0 1
0 1 0 1 0
0 1 0 1
0 1 1 1 0
901 901
w x y z o
1 0 0 0 1 0 0 1 0
1 0 1 0 1
1 0 1 1
1 1 0 0 0
1 1 0 1 0
1 1 1 1
1 1 1 1 1
Поскольку в этой таблице 16 строк, мы начнем с 4 × 4 матрица.Каждая строка будет представлять собой комбинацию значения для значений первых двух переменных, и каждый столбец будет представляют собой комбинацию значений двух последних переменных.
При определении прямоугольных областей мы вводим новое правило: регионов можно обернуть края матрицы. (Это правило применяется для трехвходового функций тоже, хотя в наших предыдущий пример.) Используя этот факт, мы можем охватить единицы, используя всего три прямоугольника.
Самая простая область (выделена желтым цветом) находится в правом нижнем углу; это соответствует сроку w y . Верхняя область 2 × 2 (нарисованная розовым цветом) оборачивается с последней столбец вокруг первого столбца; это соответствует сроку w z . Есть еще один регион (нарисуйте синим цветом), переносится между столбцами, а также между строками, поэтому охватывает все четыре угла матрицы; это соответствует сроку x z .Объединив эти три термина, мы приходим к нашему упрощенному Логическое выражение:
w y + w z + x z
Когда вы рисуете прямоугольные области, вы хотите использовать их как как можно меньше: каждому региону соответствует дополнительный И ворота. В нашем примере выше мы опустили возможный прямоугольник который покрывает последний столбец, потому что он не покрывает никакие единицы которые еще не были покрыты.
Более того, вы хотите, чтобы каждый прямоугольник покрыл столько единиц, сколько возможно, даже если в этом нет необходимости, потому что прямоугольники большего размера приводят к терминам, содержащим меньше переменных. В нашем ранее Например, мы могли бы нарисовать верхний розовый прямоугольник как Прямоугольник 1 × 2 только во втором ряду. Но потом второй условия были бы w x z , в котором на одну переменную больше, чем мы использовали ранее.
4. Другие логические элементы и универсальность
До сих пор мы имели дело только с логическими элементами И, ИЛИ и НЕ.Дизайнеры схем часто работают с четырьмя другими воротами: NAND ( n от и ), NOR ( n ot или ), XOR (e x , включая или ), и XNOR ( n или x , включая или ). Логический элемент XOR выдает 1, когда один или другой из его входов равен 1, но не тогда, когда они оба; то есть случай двух входов 1 исключил из ситуации, когда гейт выдает 1. Ворота NAND, NOR и XNOR работают просто как ворота AND / OR / XOR с вентиль NOT после него — и они рисуются как AND / OR / XOR ворота с маленьким кружком на выходе.На рисунке 6 изображен внешний вид этих ворот и сводки таблицы истинности.
Рисунок 6: Больше логических ворот.
(a) Логический элемент NAND (b) ворота NOR (c) вентиль XOR (d) вентиль XNOR
Раньше мы не смотрели на эти ворота, потому что они могут все они должны быть построены с использованием логических элементов И, ИЛИ, и НЕ.Фактически, мы видели что каждая таблица истинности имеет схему логических элементов И, ИЛИ, и НЕ. что ему соответствует — мы просто получаем выражение суммы продуктов (которое имеет только И, ИЛИ, и НЕ), а затем построить соответствующие схема. Из-за этого свойства мы называем комбинацию И, ИЛИ, и НЕ универсальный .
Несколько более удивительно то, что только вентиль NAND универсальный — то есть может быть реализована любая таблица истинности схемой, которая включает только вентили NAND.Чтобы убедиться в этом, начнем с того, что любой таблица истинности может быть реализована с помощью логических элементов И, ИЛИ и НЕ; а также тогда мы увидим, как можно заменить каждый вентиль И / ИЛИ / НЕ на система вентилей NAND, чтобы попасть в цепь, включающую только NAND ворота. Рисунок 7 демонстрирует NAND-вентиль. система, соответствующая каждому из И, ИЛИ и НЕ.
Рисунок 7: Построение NOT, AND и OR с использованием логических элементов NAND.
Мы можем сделать то же самое, чтобы найти, что ворота NOR сами универсальны.
Тот факт, что NAND универсален, часто используется схемно дизайнеров. Хотя разработчики сначала проектируют схему, используя AND, ИЛИ, а не вентили, на практике схемы легче производство, когда они используют только вентили NAND (или только вентили NOR). (Почему это так, мы не будем здесь разбираться.) Таким образом, их начальные Конструкции И / ИЛИ / НЕ преобразуются для использования только NAND (или NOR).
В любом случае, к этому моменту мы увидели, как можно наращивать достаточно небольшая схема для любой возможной логической функции.Эти знания формируют основу для построения полной вычислительной устройств.
Как разрабатывать логические схемы и логические вентили — видео и стенограмма урока
Пример 1
Хорошо, давайте рассмотрим несколько примеров, связанных с проектированием логических схем.
Пример 1: Начнем с простого примера разработки простой системы голосования. Предположим, вы хотите разработать систему голосования для компании. В этой компании есть совет директоров, состоящий из трех директоров с разным весом голоса, а именно:
Директор A: 20%
Директор Б: 30%
Директор C: 50%
Решение считается принятым, если за него набралось более 50% голосов.Мы хотим разработать схему, реализующую эту систему голосования.
Предположим, что выход схемы обозначен Z, чтобы разработать эту систему, мы начнем с использования таблицы истинности, которую вы можете увидеть здесь:
C B A Z
0 0 0 0
0 0 1 0
0 1 0 0
0 1 1 0
1 0 0 0
1 0 1 1
1 1 0 1
1 1 1 1
Обратите внимание на важность каждого слова в спецификации.Решение принимается только в том случае, если оно набирает более 50%. Поэтому, если, например, голосует только C, решение не принимается.
Следующим шагом является перенос таблицы истинности в карту Карно с целью упрощения функции. Мы делаем следующую цифру, появившуюся здесь:
Используя карту Карно нашего первого рисунка, мы получаем:
Z = AC + BC ‘
Используя Logisim (или любое другое программное обеспечение, используемое для построения схем логических схем), мы получаем диаграмму на следующем рисунке, которая появляется здесь, заменяя каждую функцию И вентилем И, а функцию ИЛИ вентилем ИЛИ:
Мы можем дополнительно упростить эту функцию в письменной форме следующим образом:
Z = C (A + B)
Это приводит к более простой функции, чем первая, потому что последняя функция может быть реализована только с использованием два ворот вместо трех, необходимых для первой функции.Теперь мы можем нарисовать схему схемы, как на следующем рисунке:
Здесь было бы лучше потратить некоторое время, чтобы построить эту схему в Logisim и смоделировать ее поведение.
Пример 2
Давайте теперь поработаем над другим примером. Давайте спроектируем логическую схему, которая принимает на вход 4-битное число и будет выводить «1», когда вход делится на 3.
Следуя только что упомянутой систематической процедуре, мы начнем с использования приведенной здесь таблицы истинности:
D С B A Z
0 0 0 0 0
0 0 0 1 0
0 0 1 0 0
0 0 1 1 1
0 1 0 0 0
0 1 0 1 0
0 1 1 0 1
0 1 1 1 0
1 0 0 0 0
1 0 0 1 1
1 0 1 0 0
1 0 1 1 0
1 1 0 0 1
1 1 0 1 0
1 1 1 0 0
1 1 1 1 1
Затем мы переносим таблицу истинности на карту Карно, чтобы попытаться упростить ее.Соответствующая карта Карно показана на следующем изображении:
Это важный пример, поскольку мы видим, что эту функцию нельзя упростить, используя карту Карно. Соответственно, функцию можно записать, как показано на следующем изображении:
А схему цепи можно нарисовать как на следующем изображении:
Здесь снова стоит отметить, что неплохо потратить некоторое время, чтобы построить эту схему в Logisim и смоделировать ее поведение.
Итоги урока
Поздравляем! Вы закончили свои первые два примера разработки логических схем. Теперь, когда мы прошли через все это, давайте вспомним, что мы узнали.
В этом уроке вы узнали, как перенести спецификацию системы в цифровую схему. Вы видели систематическую процедуру для такой передачи, которую можно определить с помощью этого списка:
Вычтите таблицу истинности из удобочитаемой спецификации.
Перенесите таблицу истинности в карту Карно, чтобы упростить функцию (если возможно).
Вычтите схему и нарисуйте схему затвора (и, если необходимо, проводную схему).
В основном, когда вы хотите разработать логическую схему, вы начинаете с понимания спецификации схемы, чтобы вы могли написать ее таблицу истинности. Затем вы попытаетесь упростить функцию, используя карты Карно или любые другие методы упрощения, чтобы, наконец, получить схему требуемой схемы.Это начало увлекательного пути обучения, который позволит вам создавать сложные системы, такие как ALU или даже полный ЦП.
Логические ворота — Уроки

Слово алгебра имеет несколько связанных значений в математике, но мы остановимся только на одном из них. Мы будем использовать слово алгебра для обозначения набора элементов, связанных с набором операций над элементами этого набора.
Булева алгебра — формальное определение

Определим набор из шести элементов $ T = (B, AND, OR, NOT, 0, 1) $, состоящий из
комплект $ B $,
две бинарные операции над элементами из множества $ B $, называемые И ($ \ cdot $) и ИЛИ (+),
одна унарная операция, называемая НЕ (строка поверх символа, например $ \ overline {x} $) и,
два отдельных элемента 0 и 1; оба из набора $ B $.
Иногда вместо И мы используем $ \ cdot $, вместо ИЛИ мы используем $ + $, а вместо НЕ мы ставим черту поверх символа вроде $ \ overline {x} $.
Затем для всех элементов $ a $, $ b $ и $ c $ из $ B $ определите набор $ A $ следующих аксиом
\ begin {align *}
a + (b + c) & = ( a + b) + c & a \ cdot (b \ cdot c) & = (a \ cdot b) \ cdot c & \ text {ассоциативность} \\
a + b & = b + a & a \ cdot b & = b \ cdot a & \ text {коммутативность} \\
a + 0 & = a & a \ cdot 1 & = a & \ text {identity} \\
a + (b \ cdot c) & = (a + б) \ cdot (a + c) & a \ cdot (b + c) & = (a \ cdot b) + (a \ cdot c) & \ text {дистрибутивность} \\
a + \ overline {a} & = 1 & a \ cdot \ overline {a} & = 0 & \ text {complements}
\ end {align *}
Обратите внимание, что аксиомы выше демонстрируют некоторую двойственность: каждый раз, когда мы заменяем $ + $ на $ \ cdot $ и 0 на 1 или наоборот, мы получаем вторую форму.Например, из $ a + 0 = a $ получаем $ a \ cdot 1 = a $. Булева алгебра — это набор из шести элементов $ T $ такой, что выполняются все аксиомы из набора $ A $.

С помощью аксиом мы можем доказывать множество разных вещей и формул. Все они важны, но очень часто используется один: законы Де Моргана
\ begin {align *}
\ overline {a + b} & = \ overline {a} \ cdot \ overline {b} \\
\ overline {a \ cdot b} & = \ overline {a} + \ overline {b}
\ end {align *}
С нашей точки зрения, наиболее важной является простейшая булева алгебра, двухэлементная булева алгебра, которая имеет только два элемента, 0 и 1.

Из аксиом мы можем вывести набор правил для операций AND, OR и NOT
 
 NOT 1 = 0 
 Доказательство: 
 a OR 0 = a 
 a OR NOT a = 1
  подставляя a: = 1, получаем 
  1 ИЛИ 0 = 1 
 1 ИЛИ НЕ 1 = 1 
  и, как следствие, 
  НЕ 1 = 0 
  НЕ 0 = 1 
 Доказательство: по аналогии мы можем доказать НЕ 0 = 1 
  ================================================= =============================== 
  0 И 0 = 0 
 Доказательство: 
 0 И 0 = [от идентичности] = (0 И 0) ИЛИ 0 = 
 = [от дополнений] = (0 И 0) ИЛИ (0 И (НЕ 0)) = 
 = [из НЕ 0 = 1] = (0 И 0) ИЛИ (0 И 1) = 
 = [из распределения] = 0 И (0 ИЛИ 1) = 
 = [из коммутативности] = 0 И (1 ИЛИ 0) = 
 = [из идентификатора] = 0 И 1 = 
 = [из НЕ 0 = 1] = 0 И (НЕ 0) = 
 = [из дополнений] = 0 
  0 И 1 = 0 
 Доказательство: из тождества а И 1 = а 
  1 AND 0 = 0 
 Доказательство: из компутативности a AND b = b AND a и далее у нас есть предыдущий случай 
  1 И 1 = 1 
 Доказательство: из тождества а И 1 = а 
  ================================================= =============================== 
  0 OR 0 = 0 
 Доказательство: из OR 0 = 
  0 ИЛИ 1 = 1 
 Доказательство: из вычислительной теории а ИЛИ b = b ИЛИ a и следующий случай 
  1 OR 0 = 1 
 Доказательство: из OR 0 = 
  1 ИЛИ 1 = 1 
 Доказательство: 
 По аналогии с 0 И 0 = 0 
 
 
В большинстве случаев мы рисуем приведенный выше набор правил в виде таблицы истинности .
a б И (а, б) ИЛИ (а, б) НЕ (а)
0 0 0 0 1
0 1 0 1 1
1 0 0 1 0
1 1 1 1 0
Todo (id = no todo id): logic_gates: таблицы стилей
Почему мы заботимся об этой алгебре

Булева алгебра имеет приложения в логике, интерпретируя 0 как FALSE, 1 как TRUE.Двухэлементная булева алгебра также используется для проектирования схем в электротехнике; здесь 0 и 1 представляют два разных состояния одного бита в цифровой схеме, обычно ВЫСОКОЕ и НИЗКОЕ напряжение. Цепи описываются выражениями, содержащими переменные, и два таких выражения равны для всех значений переменных тогда и только тогда, когда соответствующие схемы имеют одинаковое поведение ввода-вывода. Более того, каждое возможное поведение ввода-вывода может быть смоделировано подходящим логическим выражением.Это делает болевскую алгебру идеальным инструментом, который мы можем использовать при проектировании логических схем.

Что интересно, Бул представил свою алгебру в книге Математический анализ логики (1847 г.) и более подробно изложил ее в своей книге Исследование законов мышления (1854 г.). Что действительно может удручать любого из нас, кто хочет стать известным ученым, так это то, что при его жизни казалось, что его работа вообще не имела практического применения. Потребовалось несколько десятилетий, чтобы найти применение этой алгебре.В 1930-х годах Клод Шеннон столкнулся с этим во время учебы в Массачусетском технологическом институте, а в 1938 году он опубликовал статью, описывающую, как логический анализ может быть применен к схемам, использующим реле. Это имело непосредственное практическое применение, поскольку телефонные сети быстро росли, создавая сложные проблемы с коммутацией.
Функционально полный набор логических операторов

Прежде всего отметим, что мы можем определить четыре разных унарных оператора
 
 a o1 (a) o2 (a) o3 (a) o4 (a) 
 0 1 0 1 0 
 1 1 1 0 0 
 o1 - verum (утверждающий оператор; тавтология) 
 o2 - утверждение (проекция) 
 o3 - оператор НЕ (отрицание) 
 o4 - ложь 
 
и шестнадцать различных бинарных операторов
 
 ab o1 o2 o3 o4 o5 o6 o7 o8 o9 o10 o11 o12 o13 o14 o15 o16 
 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 
 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 
 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 
 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 
 o1 - противоречие 
 o2 - NOR = NOT OR 
 o3 - обратное отсутствие импликации 
 o4 - отрицание 
 o5 - материальное отсутствие импликации 
 o6 - отрицание 
 o7 - XOR (исключительная дизъюнкция) 
 o8 - NAND = NOT AND 
 o9 - AND 
 o10 - XNOR 
 o11 - функция проекции 
 o12 - материальная импликация (правило интерференции) 
 o13 - функция проекции 
 o14 - обратная импликация 
 o15 - OR 
 o16 - тавтология 
 
Вопрос в том, являются ли все они уникальными в том смысле, что их нельзя заменить комбинацией двух или более других операторов.
В логике функционально полный набор логических связок или логических операторов — это тот, который можно использовать для выражения всех возможных таблиц истинности путем объединения членов набора в логическое выражение. Хорошо известный полный набор связок — это {И, НЕ} и ИЛИ, НЕ. Что может быть удивительно, синглтон-наборы NAND и NOR также функционально завершены. Другими словами, существует комбинация только логических элементов И-НЕ (или только ИЛИ-ИЛИ), которая ведет себя как вентиль И, другая комбинация для получения поведения логического элемента ИЛИ и третья комбинация для получения функциональности логического элемента НЕ.
С точки зрения цифровой электроники, функциональная полнота означает, что каждый возможный логический элемент может быть реализован как сеть вентилей типов, предписанных набором. В частности, все логические вентили могут быть собраны либо только из двоичных вентилей И-НЕ, либо только из двоичных вентилей ИЛИ-НЕ.
Комплектность набора ворот NAND

Мы покажем, как получить логическую схему И, ИЛИ и НЕ на основе вентилей И-НЕ.
Todo (id = no todo id): logic_gates: улучшить качество изображений
НЕ

$$
NAND (a, a) = NOT (AND (a, a)) = NOT (a)
$$
или то же самое в другой форме
$$
\ overline {a \ cdot a } = \ overline {a}.
$$
И

\ begin {align *}
NAND (NAND (a, b), NAND (a, b)) & = NOT (AND (NAND (a, b), NAND (a, b))) = НЕ (NAND (a, b)) \\
& = NOT (NOT (AND (a, b)))
\ end {align *}
или то же самое в другой форме
$$
\ overline {\ overline {a \ cdot b} \ cdot \ overline {a \ cdot b}} = \ overline {\ overline {a \ cdot b}} = a \ cdot b.
$$
OR

\ begin {align *}
NAND (NAND (a, a), NAND (b, b)) & = NOT (AND (NOT (a), NOT (b))) = OR (NOT (NOT (a)), NOT (NOT (b))) \\
& = OR (a, b)
\ end {align *}
или то же самое в другой форме
$$
\ overline {\ overline {a \ cdot a} \ cdot \ overline {b \ cdot b}} = \ overline {\ overline {a} \ cdot \ overline {b}} = \ overline {\ overline {a}} + \ overline {\ overline {b} } = а + b.
$$
Комплектность ворот ИЛИ и НЕ

Мы покажем, как получить логическую схему И на основе вентилей ИЛИ и НЕ.

$ НЕ (ИЛИ (НЕ (a), НЕ (b))) = И (НЕ (НЕ (a)), НЕ (НЕ (b))) = И (a, b)

$ или то же самое в другой форме

$ \ overline {\ overline {a} + \ overline {b}} = \ overline {\ overline {a}} \ cdot \ overline {\ overline {b}} = a \ cdot b.
$$
Немного о приложении

Как правило, в информатике среди всех логических функций мы используем шесть из них
И, ИЛИ, НЕ, ИЛИ, ИЛИ, ИСКЛЮЧАЮЩЕЕ ИЛИ
Эти логические функции были определены логическими операторами в предыдущем разделе: И как o9, ИЛИ как o15, НЕ как o3, NAND как o8, NOR как o2, XOR как 07.
В электронике эти логические функции реализованы как логический вентиль , который представляет собой физические устройства, реализующие логическую функцию. Следующий набор символов используется для обозначения соответствующего логического элемента (реализующего соответствующую логическую функцию)

Имея заданную логическую схему (набор подключенных логических вентилей), мы можем сказать, как этот набор будет реагировать на входные сигналы. Другими словами, на основе схемы соединений логических вентилей мы можем создать таблицу отношений ввода-вывода (таблицу истинности для этой схемы).
В качестве примера рассмотрим очень полезную схему комбинационной логики, известную как схема цифрового компаратора . Целью цифрового компаратора является сравнение двух чисел: $ x $ и $ y $ и создание условия вывода или флага в зависимости от результата сравнения. Например, компаратор величин двух 1-битных входов будет производить следующие три выходных условия $ x \ gt y $, $ x = y $, $ x \ lt y $ в зависимости от того, больше ли $ x $, чем $ y $. , $ x $ равно $ y $, а $ x $ меньше $ y $
Существует два основных типа цифровых компараторов.
Компаратор идентичности — компаратор идентичности — это цифровой компаратор, который имеет только один выходной терминал, когда $ x = y $.
Компаратор величин — компаратор величин — это цифровой компаратор, который имеет три выходных терминала, по одному для равенства ($ x = y $), больше ($ x> y $) и меньше ($ x

Таблица истинности и логическая схема для этого компаратора представлены ниже. 901 10 x
Входы Выход
л х = у
0 0 1
0 1 0
1 0 0
1 1 1

Таблица истинности и логическая схема для этого компаратора представлены ниже. 901 10 x
Входы Выходы
л х = у x> y х <у
0 0 1 0 0
0 1 0 0 1
1 0 0 1 0
1 1 1 0 0
Проверить компаратор амплитуды

Чтобы убедиться, что данная логическая схема работает правильно, мы можем нарисовать поток сигналов, как я сделал ниже

. Теперь давайте обратим проблему из предыдущего раздела: Как найти логическую схему, реализующую предопределенные отношения ввода-вывода? Мы покажем один метод, не вдаваясь в подробности.
Todo (id = no todo id): logic_gates: напишите страницы о проектировании логических схем, картах Карно и т. Д.
Шаг 1: Что мы хотим, чтобы наша логическая схема делала?

Целью логической схемы, которую мы хотим создать, является сложение двух 1-битных чисел. Да, это очень простая задача, но 1-битный сумматор является составной частью более сложных 8-битных, 16-битных и обычно n-битных сумматоров.
Шаг 2: Определите соотношение ввода-вывода

Я предполагаю, что у вас есть базовые знания о нотации разрядов, особенно о системе с основанием 2, и вы знаете, что двоичное число 10 равно десятичному 2 (мы запишем это как $ 10_ {2} = 2_ {10} $).Как и для любой системы ценностей, достаточно сосредоточиться на одной позиции, потому что остальные позиции рассчитываются таким же образом, с учетом сигналов переноса. У нас есть следующие варианты добавления двух 1-битных чисел
 
 x = 0 x = 0 x = 1 x = 1 
 y = 0 y = 1 y = 0 y = 1
  + --------- сигнал переноса (выполнение) 
 | 
 1 
 0 0 1 1 - x 
 0 + 1 + 0 + 1 + - y 
 ----- ----- ----- ----- 
 0 1 1 10 
 
 
На основе этих вариантов мы можем создать таблицу истинности для 1-битного сумматора.
Входы Выходы
x y Стоимость (v $) Выполнить ($ c_ {out} $)
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1
Теперь мы включим в вышеупомянутый сигнал переноса из предыдущей позиции
 
 carry_in = 0 
 x = 0 x = 0 x = 1 x = 1 
 y = 0 y = 1 y = 0 y = 1
  0 0 0 0 - перенос 
 0 0 1 1 - x 
 0 + 1 + 0 + 1 + - y 
 ----- ----- ----- ----- 
 0 1 1 10 
  carry_in = 1 
 x = 0 x = 0 x = 1 x = 1 
 y = 0 y = 1 y = 0 y = 1 
  1 1 1 1 - перенос 
 0 0 1 1 - x 
 0 + 1 + 0 + 1 + - y 
 ----- ----- ----- ----- 
 1 10 10 11 
 
 
На основе этих вариантов мы можем создать таблицу истинности для 1-битного сумматора.
Входы Выходы
Перенести ($ c_ {in} $) х y Стоимость (v $) Выполнить ($ c_ {out} $)
0 0 0 0 0
0 0 1 1 0
0 1 0 1 0
0 1 1 0 1
1 0 0 1 0
1 0 1 0 1
1 1 0 0 1
1 1 1 1 1
Шаг 3. Найдите логические выражения, эквивалентные нашей таблице истинности
Логическое выражение для выполнения вывода

Начнем с вынесенного сигнала, так как он проще.Чтобы создать выражение, мы должны найти все случаи, когда выполнение равно 1 (ИСТИНА) — таких случаев четыре:
перенос равен 1, когда перенос равен 0, x = 1, y = 1,
или когда перенос равен 1, x = 0, y = 1,
или когда перенос равен 1, x = 1, y = 0,
или, наконец, когда перенос равен 1, x = 1, y = 1.
Другими словами, мы можем записать это как
 
 c_out = 1 тогда и только тогда, когда (
 (c_in, x, y) = (0, 1, 1) или 
 (c_in, x, y) = (1, 0, 1) или 
 (c_in, x, y) = (1, 1, 0) или 
 (c_in, x, y) = (1, 1, 1) 
) 
 
или эквивалентно
 
 c_out = 1 тогда и только тогда, когда (
 (NOT (c_in), x, y) = (1, 1, 1) или 
 (c_in, NOT (x), y) = (1, 1, 1) или 
 (c_in, x, NOT (y)) = (1, 1, 1) или 
 (c_in, x, y) = (1, 1, 1) 
) 
 
и наконец в более компактном виде

$ c_ {out} = \ overline {c_ {in}} xy + c_ {in} \ overline {x} y + c_ {in} x \ overline {y} + c_ {in} xy.

$ Мы можем проверить эту формулу, взяв все три кортежа от 0 до 1, и сравнить результаты с таблицей истинности, приведенной выше. Мы проверим это на двух из них
Для тройки $ (c_ {in}, x, y) = (0, 1, 1) $ получаем
$$
c_ {out} = \ overline {c_ {in}} xy + c_ {in } \ overline {x} y + c_ {in} x \ overline {y} + c_ {in} xy = \ overline {0} 11 + 0 \ overline {1} 1 + 01 \ overline {1} + 011 = 111 + 001 + 010 + 011 = 1 + 0 + 0 + 0 = 1.
$$
Для трех кортежей $ (c_ {in}, x, y) = (1, 0, 0) $ получаем
$$
c_ {out} = \ overline {c_ {in}} xy + c_ {in} \ overline {x} y + c_ {in} x \ overline {y} + c_ {in} xy = \ overline {1} 00 + 1 \ overline {0} 0 + 10 \ overline {0} + 100 = 000 + 110 + 101 + 100 = 0 + 0 + 0 + 0 = 0.
$$
Логическое выражение для вывода значения

Используя ту же технику, что и для выполнения сигнала, получаем

$ v = \ overline {c_ {in}} \ overline {x} y + \ overline {c_ {in}} x \ overline {y} + c_ {in} \ overline {x} \ overline {y} + c_ {in } ху.
$$
Шаг 4. Упростите логические выражения

Согласно правилам булевой алгебры, мы можем упростить формулы из предыдущего раздела следующим образом.
Формула для $ c_ {out} $:
\ begin {align *}
c_ {out} & = \ overline {c_ {in}} xy + c_ {in} \ overline {x} y + c_ {in} x \ overline {y} + c_ {in} xy \\
& \ overset {(1)} {=} \ overline {c_ {in}} xy + c_ {in} \ overline {x} y + c_ {in} x \ overline {y} + c_ {in} xy + c_ {in} xy + c_ {in} xy \\
& \ overset {(2)} {=} \ overline {c_ {in}} xy + c_ {in} xy + c_ {in} \ overline {x} y + c_ {in} xy + c_ {in} x \ над чертой {y} + c_ {in} xy \\
& \ overset {(3)} {=} (\ overline {c_ {in}} xy + c_ {in} xy) + (c_ {in} \ overline {x} y + c_ {in} xy) + (c_ {in} x \ overline {y} + c_ {in} xy) \\
& \ overset {(4)} {=} xy (\ overline {c_ {in}} + c_ {in}) + c_ {in} y (\ overline {x} + x) + c_ {in} x (\ над чертой {y} + y) \\
& \ overset {(5)} {=} xy (1) + c_ {in} y (1) + c_ {in} x (1) \\
& \ overset {(6)} {=} xy + c_ {in} y + c_ {in} x.
\ end {align *}
куда
Для каждого логического выражения мы можем взять один из его членов и повторять его столько раз, сколько захотим, например
\ begin {align *}
a & = a + a + a + a \\
a \ cdot b & = a \ cdot a \ cdot a \ cdot b \ cdot b
\ end {align *}
В этом случае мы сделали это с термом $ c_ {in} xy $.
Просто измените условия.
Grup термины в скобках.
Используйте дистрибутивность для извлечения общего термина.
Вычислить значения в скобках.
Используйте идентификатор .
Формула для $ v $:
\ begin {align *}
v & = \ overline {c_ {in}} \ overline {x} y + \ overline {c_ {in}} x \ overline {y} + c_ {in} \ overline {x} \ overline {y} + c_ {in} xy \\
& \ overset {(1)} {=} \ overline {c_ {in}} (\ overline {x} y + x \ overline {y}) + c_ {in} (\ overline {x} \ overline {y} + xy)
\ end {align *}
, где
Используйте дистрибутив для извлечения общего термина.
Теперь важно отметить, что введение новых символов $ a $ и $ b $, таких как
\ begin {align *}
a & = \ overline {x} y + x \ overline {y} \\
b & = \ overline {x} \ overline {y} + xy
\ end {align *}
получаем, что
$$
\ overline {a} = b
$$
Доказательство несложно (будем использовать De Законы Моргана: $ \ overline {x + y} = \ overline {x} \ cdot \ overline {y} $ и $ \ overline {x \ cdot y} = \ overline {x} + \ overline {y} $)
$$
\ overline {\ overline {x} y + x \ overline {y}} = \ overline {(\ overline {x} y)} \ cdot \ overline {(x \ overline {y})} = (\ overline {x} + y) \ cdot (x + \ overline {y}) = (x + \ overline {y}) x + (x + \ overline {y}) y = \ overline {x} \ overline {y} + ху.
$$
В итоге получаем
$$
v = \ overline {c_ {in}} a + c_ {in} \ overline {a}.
$$
Шаг 5: Подготовьте логическую схему на основе выражений Bolean

Пришло время нарисовать нашу схему

Мы также можем попробовать смоделировать наши схемы — хорошим выбором будет приложение Logisim (скачать проект Logisim)

Наконец, вы можете использовать реальные компоненты для создания этой схемы:
c_in = зеленый кабель, y = оранжевый кабель, x = белый кабель

Вышеупомянутый пример был выполнен в Autodesk Tinkercad.
Шаг 6: Используйте настоящие микросхемы для реализации логической схемы, которую мы нашли

Мы будем использовать следующие микросхемы с логическими вентилями
Мы не можем …
Не трогайте контакты микросхемы! Избегайте электростатических разрядов, чтобы не повредить чип.
Не может быть плавающих входов! Все входные контакты всегда должны быть подключены к известному напряжению. Это включает в себя входные контакты вентилей, которые не используются на микросхеме.
Будьте осторожны при использовании выхода логической микросхемы для питания чего-либо, например светодиода.В большинстве случаев следует использовать транзисторы.
Не связывайте вместе выходы двух или более логических вентилей.

Мы можем…
Мы можем подключить вход затвора напрямую к регулируемому источнику питания, как с положительной, так и с отрицательной стороны.
Мы можем подключить выход одного элемента напрямую ко входу другого элемента.
Выход одного затвора может питать входы нескольких других затворов. Точное количество зависит от микросхемы, но с запасом прочности мы можем предположить, что мы можем запитать как минимум десять входов одним логическим выходом.
Вывод отрицательного напряжения обозначается как один из $ VSS $, $ V_ {SS} $, $ VEE $, $ V_ {EE} $, $ GND $
Вывод положительного напряжения обозначается как один из $ VDD $, $ V_ {DD} $, $ VCC $, $ V_ {CC} $, $ V + $
Todo (id = no todo id): logic_gates: создать настоящий сумматор
Более подробную информацию о сумматорах вы можете найти в этой замечательной статье Двоичный сумматор

Постройте 4-битный сумматор (логическая схема, которая позволяет складывать два 4-битных числа).
Сумма произведений (9:38) | 4.2 Тематические видео | 4 Комбинационная логика | Вычислительные структуры | Электротехника и информатика
В этой лекции вы изучите различные методы создания комбинационных логических схем, реализующих конкретную функциональную спецификацию.
Функциональная спецификация — это часть статической дисциплины, которую мы используем для создания комбинационной логической абстракции схемы.
Один из подходов — использовать естественный язык для описания работы устройства.
У этого подхода есть свои плюсы и минусы.
В свою очередь, естественный язык может передавать сложные концепции в удивительно компактной форме, и это обозначение, которое большинство из нас умеет читать и понимать.
Но, если слова не составлены очень тщательно, могут возникать двусмысленности, вносимые словами с множественными интерпретациями или отсутствием полноты, поскольку не всегда очевидно, были ли учтены все возможные варианты.3 = 8 комбинаций трех входных значений, поэтому в таблице истинности 8 строк.
Систематически перечислить 8 комбинаций несложно, что позволяет легко гарантировать, что ни одна комбинация не будет пропущена при построении спецификации.
А поскольку выходные значения указаны явно, нет места для неправильной интерпретации желаемой функциональности!
Таблицы истинности — отличный выбор для устройств с небольшим количеством входов и выходов.64 ряда.
Хм, не уверен, насколько это практично!
Если мы введем правильное выходное значение для строки один раз в секунду, то на заполнение таблицы уйдет 584 миллиарда лет!
Другая альтернативная спецификация — использовать булевы уравнения для описания того, как вычислять выходные значения из входных значений с помощью булевой алгебры.
Мы используем логические операции И, ИЛИ и XOR, каждая из которых принимает два логических операнда, и НЕ, которая принимает один логический операнд.
Используя таблицы истинности, которые описывают эти логические операции, легко вычислить выходное значение из конкретной комбинации входных значений, используя последовательность операций, изложенных в уравнении.
Позвольте мне сказать несколько слов об обозначениях, используемых для булевых уравнений.
Входные значения представлены именем входа, в этом примере одним из «A», «B» или «C».
Значение цифрового входа 0 эквивалентно логическому значению FALSE, а значение цифрового входа 1 эквивалентно логическому значению TRUE.
Логическая операция NOT обозначается горизонтальной линией над логическим выражением.
В этом примере первым символом, следующим за знаком равенства, является буква «C» с линией над ней, что указывает на то, что значение C должно быть инвертировано, прежде чем оно будет использовано при вычислении остальной части выражения.
Логическая операция И представлена операцией умножения с использованием стандартной математической записи.
Иногда мы будем использовать явный оператор умножения — обычно записываемый как точка между двумя логическими выражениями — как показано в первом члене примера уравнения.
Иногда оператор И является неявным, как показано в оставшихся трех членах примера уравнения.
Логическая операция ИЛИ представлена операцией сложения, всегда отображается как знак «+».
Логические уравнения полезны, когда устройство имеет много входов.
И, как мы увидим, легко преобразовать логическое уравнение в принципиальную электрическую схему.
Таблицы истинности и булевы уравнения взаимозаменяемы.
Если у нас есть логическое уравнение для каждого вывода, мы можем заполнить выходные столбцы для строки таблицы истинности, оценив булевы уравнения с использованием конкретной комбинации входных значений для этой строки.
Например, чтобы определить значение Y в первой строке таблицы истинности, мы подставили бы логическое значение FALSE для символов A, B и C в уравнении, а затем использовали бы логическую алгебру для вычисления результата.
Мы можем пойти и другим путем.
Мы всегда можем преобразовать таблицу истинности в определенную форму булевого уравнения, называемую суммой произведений.
Давайте посмотрим, как… Начнем с просмотра таблицы истинности и ответа на вопрос «Когда Y имеет значение 1?» Или на языке булевой алгебры: «Когда Y ИСТИНА?».
Итак, Y — ИСТИНА, когда входы соответствуют строке 2 таблицы истинности, ИЛИ — строке 4, ИЛИ — строкам 7 ИЛИ 8.
Всего существует 4 комбинации входов, для которых Y — ИСТИНА.
Соответствующее логическое уравнение, таким образом, является операцией ИЛИ для четырех членов, где каждый член является логическим выражением, которое принимает значение ИСТИНА для конкретной комбинации входных данных.
Строка 2 таблицы истинности соответствует C = 0, B = 0 и A = 1.
Соответствующим логическим выражением является (НЕ C) И (НЕ B) И A, выражение, которое принимает значение ИСТИНА тогда и только тогда, когда C равно 0, B равно 0 и A равно 1.
Логическое выражение, соответствующее строке 4, это (НЕ C) AND B AND A.
И так далее для строк 7 и 8.
Подход всегда дает нам выражение в форме суммы произведений .
«Сумма» относится к операциям ИЛИ, а «продукты» относится к группам операций И.
В этом примере у нас есть сумма четырех членов продукта.
Нашим следующим шагом будет использование логического выражения в качестве рецепта для построения реализации схемы с использованием вентилей комбинационной логики.
Как разработчики схем мы будем работать с библиотекой комбинационных логических вентилей, которые либо предоставлены нам производителем интегральных схем, либо которые мы сами разработали как вентили CMOS с использованием переключателей NFET и PFET.
Одним из самых простых ворот является инвертор, схематический символ которого показан здесь.
Маленький кружок на выходном проводе указывает на инверсию, обычное соглашение, используемое в схемах.
Из его таблицы истинности видно, что инвертор реализует логическую функцию НЕ.
Логический элемент И выводит 1 тогда и только тогда, когда вход A равен 1 * и * вход B равен 1, отсюда и название «И».
Библиотека обычно включает логические элементы И с 3 входами, 4 входами и т. Д., Которые производят 1 выход тогда и только тогда, когда все их входы равны 1.
Логический элемент ИЛИ выдает 1, если вход A равен 1 * или * если вход B равен 1, отсюда и название «ИЛИ».
Опять же, библиотека обычно включает логические элементы ИЛИ с 3 входами, 4 входами и т. Д., Которые производят 1 выход, когда хотя бы один из их входов равен 1.
Это стандартные условные обозначения для вентилей И и ИЛИ.
Обратите внимание, что символ И на стороне ввода прямой, а символ ИЛИ изогнутый.
Немного попрактиковавшись, вы легко запомните, какие условные обозначения какие.
Теперь давайте воспользуемся этими строительными блоками, чтобы построить схему, реализующую уравнение суммы произведений.
Структура схемы в точности повторяет структуру булевого уравнения.
Мы используем инверторы для выполнения необходимых операций логического НЕ.
В уравнении суммы произведений инверторы работают с определенными входными значениями, в данном случае A, B и C. Чтобы схема была легко читаемой, мы использовали отдельный инвертор для каждой из четырех операций НЕ в логическое уравнение, но в реальной жизни мы можем один раз инвертировать вход C, чтобы получить сигнал NOT-C, а затем использовать этот сигнал всякий раз, когда требуется значение NOT-C.
Каждый из четырех терминов продукта построен с использованием логического элемента И с 3 входами.
И термины продукта объединяются вместе с использованием логического элемента ИЛИ с 4 входами.
Последняя схема имеет слой инверторов, слой логических элементов И и конечный логический элемент ИЛИ.
В следующем разделе мы поговорим о том, как построить логические элементы И или ИЛИ с большим количеством входов из компонентов библиотеки с меньшим количеством входов.
Задержка распространения для схемы суммы произведений выглядит довольно короткой: самый длинный путь от входов к выходам включает инвертор, логический элемент И и логический элемент ИЛИ.
Можем ли мы действительно реализовать какое-либо логическое уравнение в схеме с tPD, равным трем задержкам затвора?
На самом деле нет, поскольку построение И и ИЛИ с большим количеством входов потребует дополнительных уровней компонентов, что увеличит задержку распространения.
Мы узнаем об этом в следующем разделе.
Хорошая новость заключается в том, что теперь у нас есть простые методы преобразования таблицы истинности в соответствующее ей логическое уравнение суммы произведений и построения схемы, реализующей это уравнение.
Модуль 6 Раздел 1. Основные логические вентили
Как мы заявляли, компьютеры используют двоичную систему счисления для выполнения вычисление. Две двоичные цифры «0» и «1» могут быть представлены уровень напряжения на проводе.Например, никакое напряжение (0 вольт) не может представлять «0», где +5 вольт может означать «1». Мы также видели, что двоичный система счисления легко поддается представлению выражений булевой алгебры, где «0» означает ЛОЖЬ, а «1» означает ИСТИНА.
Подобно тому, как логические значения имеют электрический эквивалент в компьютере, так же выполняются основные операции соединения ( и ), дизъюнкции ( или ), и дополнение (, а не ). Каждую из этих операций можно вычислить с помощью устройства, называемого логическим вентилем .
Логический вентиль можно представить как черный ящик с проводами, идущими в него. и из него. Предположим, у нас есть логический вентиль для вычисления и . Модели и операция имеет два входа и один выход. Например, логическое выражение AB имеет два входа A и B и один выход, что является их соединением. Соответствующий логический вентиль для и будет иметь два входных провода, один из которых несет напряжение, которое представляет текущее значение A , а другое — напряжение, которое представляет текущее значение B .Этот вентиль будет иметь один выходной провод, и (на основе значений входных проводов) выводит результат операция на нем.
Поскольку мы будем использовать разные типы ворот для создания более крупных и сложных схем, нам нужен простой способ легко определить функцию ворот, которая появляется на принципиальной схеме. Мы используем разные формы для обозначения типов ворота. На рисунке ниже показаны три основных логических элемента и соответствующие Они выполняют логические операции. Это основные строительные блоки всех цифровых логических схем.
Также есть специальные ворота для nand , или и xor .
Обратите внимание на использование пузыря инверсии на чертеже , и , ни . Пузырь инверсии можно использовать для дополнения значение, входящее в ворота или выходящее из них. Вот несколько примеров инверсии использование пузыря:
Иногда нам нужны ворота, у которых больше двух входов.В таком футляров, рисуем их следующим образом:
домашних заданий
Нарисуйте ворота для следующих выражений
Предыдущий модуль: Логика, таблицы истинности, и логическая алгебра
Следующий раздел: Логические схемы и булева алгебра
Вернуться к Указатель модулей
Рисование и моделирование логических схем
В последнее время я пробовал много новых идей и делал то, что хотел делать раньше, но не знал как.Одна из таких идей заключалась в создании редактора карт для рисования дорожных сетей в графической среде и создания из него чего-то вычислимого, например графа. После создания прототипа у меня остались некоторые новые методы, которые, как я чувствовал, можно усовершенствовать, применив к быстрому несвязанному проекту.
Здесь графический интерфейс позволяет пользователю выбирать из набора логических вентилей (И, ИЛИ, ИСКЛЮЧАЮЩЕЕ ИЛИ и их соответствующие отрицания), помещать их в графическую среду и соединять их (напрямую или с помощью проводов) с другими такими вентилями.Затем схема преобразуется в логическое выражение, которое используется для генерации выходного состояния схемы на основе пользовательского контроля входных состояний. Если вы когда-либо использовали Multisim, Logisim или что-то подобное, вы увидите предполагаемое сходство.
Существуют ограничения и случаи, когда моделирование терпит неудачу, но в целом это очень простая, но эффективная программа, которая успешно работает в экспериментальной области.
Определение функции логического элемента
Программа использует одну функцию для обработки всех экземпляров используемых логических элементов.Графика ворот берется из pos = {x, y} с поворотом 0 по умолчанию. арность — количество входов, которые принимает вентиль (доступны 2, 3 и 4). режим определяет функцию ворот (И, ИЛИ и т. Д.), А return указывает результат логического шлюза при оценке ( «графика», для возврата графического элемента затвора, «узлов» для возврата положения его клеммы ввода / вывода и т. д.).
Я использовал стандарт IEEE для графики, так как ее было намного проще рисовать, а также исходя из личных предпочтений.
 logicGate = Функция [{положение, вращение, арность, режим, возврат},
  Который[
   (* нарисовать изображение ворот *)
   return == "графика",
   Повернуть [
    {
     (* Рамка *)
     {Белый, EdgeForm [Черный], Прямоугольник [поз]},
     (* символ - специфичный для режима *)
     Вставка [Стиль [
       Который[
        mode == «И» || mode == "И-НЕ", "&",
        mode == «ИЛИ» || mode == "NOR", "\ [GreaterEqual] 1",
        mode == "XOR" || mode == "XNOR", "= 1"
        ],
       40], поз + {0,5, 0,8}],
     (* строка вывода *)
     Строка [{pos + {1, 0.5}, pos + {1.5, 0.5}}],
     (* точка отрицания *)
     Если [mode == "NAND" || mode == "NOR" || mode == "XNOR",
      {Белый, EdgeForm [Черный], Диск [pos + {1.1, 0.5}, 0.1]}
      ],
     (* строки ввода *)
     Который[
      арность == 2,
      Таблица [Строка [{pos + {0, i / 4}, pos + {-0,5, i / 4}}], {i, {1, 3}}],
      арность == 3,
      Таблица [Строка [{pos + {0, i / 6}, pos + {-0.5, i / 6}}], {i, {1, 3, 5}}],
      арность == 4,
      Стол[
       Строка [{pos + {0, i / 8}, pos + {-0.5, i / 8}}], {i, {1, 3, 5, 7}}]
      ]
     }, вращение, pos + {0.5, 0,5}],
   (* укажите положение входных и выходных клемм *)
   return == "узлы",
   Который[
    арность == 2,
    <|
     «ввод» ->
      RotationTransform [вращение, поз. + {0,5, 0,5}] [
       Таблица [pos + {-0.5, i / 4}, {i, {1, 3}}]],
     «вывод» ->
      RotationTransform [вращение, положение + {0,5, 0,5}] [положение + {1,5, 0,5}]
     |>,
    арность == 3,
    <|
     «ввод» ->
      RotationTransform [вращение, позиция + {0,5, 0,5}] [
       Таблица [pos + {-0.5, i / 6}, {i, {1, 3, 5}}]],
     «вывод» ->
      RotationTransform [вращение, позиция + {0.5, 0.5}] [pos + {1.5, 0.5}]
     |>,
    арность == 4,
    <|
     «ввод» ->
      RotationTransform [вращение, позиция + {0,5, 0,5}] [
       Таблица [pos + {-0.5, i / 8}, {i, {1, 3, 5, 7}}]],
     «вывод» ->
      RotationTransform [вращение, положение + {0,5, 0,5}] [положение + {1,5, 0,5}]
     |>
    ],
   (* дает функцию ворот *)
   return == "функция",
   Который[
    mode == "И",
    А также,
    mode == "NAND",
    Нанд,
    mode == "ИЛИ",
    Или,
    mode == "NOR",
    Ни,
    mode == "XOR",
    Xor,
    mode == "XNOR",
    Xnor
    ]
   ]
  ]
 
Например, мы определяем логический элемент И с двумя входами, взятый из {0,0}, и возвращаем его графику, функцию и расположение входных / выходных клемм.
Управление функцией ворот
Перед тем, как пытаться обрабатывать набор ворот, нам нужно установить метод того, как можно управлять отдельными воротами. Интересно, как пользователь может управлять состояниями отдельных входов и правильно отображать соответствующий выход.
 (* установить значения по умолчанию *) arity = 2; inputState = Таблица [Истина, 2];
Panel @ Deploy @ Column [{
    Ряд[{
      (* выберите функцию ворот *)
      Control @ {{режим, "И",
         Стиль ["Функция", 14, "Субтитры"]}, {"И", "И-НЕ", "ИЛИ",
         «NOR», «XOR», «XNOR»}},
      (* выберите количество входов *)
      Ряд[{
        Стиль [«Входы», 14, «Субтитры»],
        Прокладка [3],
        Кнопка [2, arity = 2; inputState = Таблица [Истина, 2]],
        Кнопка [3, arity = 3; inputState = Таблица [Истина, 3]],
        Кнопка [4, arity = 4; inputState = Таблица [Истина, 4]]
        }]
      }, Проставка [5]],
    Динамический [
     Графика[{
       (* изображение ворот возврата *)
       logicGate [{0, 0}, 0, арность, режим, "графика"],
       (* рисовать индикаторы состояния входа *)
       Dynamic @ Transpose [{
          inputState /.{Истина -> Зеленый, Ложь -> Красный},

          Диск [#, 0.1] и / @
           logicGate [{0, 0}, 0, арность, «И», «узлы»] [«вход»]
          }],
       (* вставить элементы управления состоянием ввода *)
       Вставка [
          Кнопка["",
           Если [inputState [[#]] == True, inputState [[#]] = False,
              inputState [[#]] = True] & [#], ImageSize -> {35, 35},
           Внешний вид -> «Бескаркасный»],
          logicGate [{0, 0}, 0, arity, «И», «узлы»] [
            "ввод"] [[#]]] & / @ Диапазон [арность],
       (* вычислить и нарисовать индикатор состояния вывода *)
       {
        logicGate [{0, 0}, 0, arity, mode, "function"] @@
          inputState /.{Истина -> Зеленый, Ложь -> Красный},
        PointSize [0,05],
        Point [logicGate [{0, 0}, 0, арность, режим, «узлы»] [«вывод»]]}
       }, PlotRange -> {{-1, 2}, {-1, 1.7}}, ImageSize -> Large]
     ]
    }, Выравнивание -> центр, интервалы -> 2]
 
Первоначально постоянный список inputState создается с длиной, установленной функцией arity, и дает аргументы для функции ворот. Таким образом, возвращая функцию ворот и применяя ее к входному списку, мы получаем выход ворот.
 In [25]: = inputState
logicGate [{0, 0}, 0, arity, mode, "функция"]
logicGate [{0, 0}, 0, arity, mode, "функция"] @@ inputState

Out [25] = {Верно, Верно, Верно, Верно}

Out [26] = И

Out [27] = True
 
Замена через {True-> Green, False-> Red} как для списка ввода, так и для возвращенного состояния вывода обрабатывает конец графики.
 Dynamic @ Transpose [{
   inputState /. {Истина -> Зеленый, Ложь -> Красный},
   Диск [#, 0.1] и / @
    logicGate [{0, 0}, 0, арность, «И», «узлы»] [«вход»]
   }]
 
Пользователь управляет состоянием каждого входа, щелкая безрамочную кнопку, которая вставляется в графику в каждом из мест, указанных опцией «узлы» функций ворот.I-я кнопка заменяет i-ю запись в inputState либо True , либо False с 1 кнопкой на входной узел.
 (* вставить элементы управления состоянием входа *)
Вставка [Кнопка ["",
    Если [inputState [[#]] == True, inputState [[#]] = False,
       inputState [[#]] = True] & [#], ImageSize -> {35, 35},
    Внешний вид -> «Бескаркасный»],
   logicGate [{0, 0}, 0, arity, «И», «узлы»] [«вход»] [[#]]] & / @
 Диапазон [арность]
 
Генерация логического выражения
Теперь, когда структура управления установлена, следующим шагом будет разработка метода для возврата логического выражения из предполагаемого вывода графического интерфейса пользователя схемотехники.Я пропустил этот шаг, так как решил, что будет легче выполнить эту часть и работать в обратном направлении. Я представил конечный результат графического интерфейса в виде ребер графа, который будет представлять схему. Вот пример.
 net = Реверс / @ {
    "A" \ [DirectedEdge] "F1",
    "B" \ [DirectedEdge] "F2",
    «F4» \ [DirectedEdge] «F2»,
    «C» \ [DirectedEdge] «F4»,
    "D" \ [DirectedEdge] "F4",
    «E» \ [DirectedEdge] «F4»,
    «F2» \ [DirectedEdge] «F3»,
    «F1» \ [DirectedEdge] «F3»,
    «F3» \ [DirectedEdge] «X»
    };
 
Заполнители «F1», «F2» ,.. представляет произвольные функции, «A», «B», .. — входные данные выражения, а «X» — выход. Цель состоит в том, чтобы получить что-то, имеющее вид F3 [F1 [A], F2 [B, F4 [C, D, E]]]. Затем заполнители будут заменены соответствующими функциями и состояниями (например, «F1» -> Not, «F2» -> And, …, «A» -> True, «B» -> False, ..) и, таким образом, выражение вернет либо True , либо False . Немного поэкспериментировав с программированием экспрессии генов и нотацией карвы, я уже имел в виду подход, но в конечном итоге пришел к чему-то гораздо лучшему, чем мои предыдущие попытки.
Используя поиск в глубину на графике, мы начинаем с «X» и идем, пока не будет достигнут конец (терминал — или вход для конечного выражения). Поиск выполняется для всех путей и возвращает вершины после их посещения.
 В [54]: = scanList = {};
DepthFirstScan [График [сеть],
  "X", {"PostvisitVertex" -> (AppendTo [scanList, #] &)}];
scanList

Out [56] = {"B", "C", "D", "E", "F4", "F2", "A", "F1", "F3", "X"}
 
Затем список вершин переворачивается, и начальная точка («X») отбрасывается.
 В [57]: = выражение = Rest @ Reverse @ scanList

Out [57] = {"F3", "F1", "A", "F2", "F4", "E", "D", "C", "B"}
 
Читая слева направо, мы видим выражение emerge. «F4» — первая функция и «получает» следующие 3 элемента списка (ее арность равна 3, доступ к ней осуществляется через выходную степень вершины), поэтому мы хотим заменить F4, E, D, C в выражении список с F4 [E, D, C]. Затем список считывается до следующей функции, и процесс повторяется до тех пор, пока не закончатся считываемые функции.Таким образом,
 В [58]: = scanList = {}; DepthFirstScan [
 График [net], "X", {"PostvisitVertex" -> (AppendTo [scanList, #] &)}];
выражение = Rest @ Reverse @ scanList;
functionArity = AssociationThread [
   VertexList [сеть] ->
    VertexOutDegree [сеть]
   ];
functionList = Выберите [Ключи [functionArity], StringContainsQ [#, "F"] &];
Пока [functionList! = {},
  я = 1; Хотя [ContainsAny [functionList, {выражение [[- i]]}] == False,
    i ++];
  functionList =
   Удалить [список функций, положение [список функций, выражение [[- i]]] [[1]]];
  выражение =
   Добавить [Drop [
     выражение, {(-i), (-i) + functionArity [выражение [[- i]]]}],
    выражение [[- i]] @@
     выражение [[(- i) + 1 ;; (-i) + functionArity [выражение [[- i]]]]]]
  ];

x = выражение [[1]]

Out [63] = «F3» [«F2» [«B», «F4» [«E», «D», «C»]], «F1» [«A»]]
 
Теперь заменим заполнители функций, чтобы получить логическое выражение
 В [43]: = x /.{
  «F1» -> Нет,
  «F2» -> А,
  «F3» -> Или,
  «F4» -> Nand
  }

Out [43] = ("B" && ("E" \ [Nand] "D" \ [Nand] "C")) || ! "А"
 
Чтобы оценить выражение, мы заменяем заполнители терминала их желаемыми состояниями
 В [44]: = ("B" && ("E" \ [Nand] "D" \ [Nand] "C")) || ! «А» /. {
  «А» -> Верно,
  «Б» -> Верно,
  "C" -> Верно,
  "D" -> Верно,
  "E" -> Верно
  }

Out [44] = ложь
 
Теперь нужен графический интерфейс, который позволяет пользователю рисовать схемы и генерировать выходные данные, совместимые с этим методом.
Рисование логической схемы
Первый шаг — установить логические вентили в нужное положение и сохранить их в памяти. LocatorPane используется для передачи положения мыши в функцию logicGate , которая настроена на возврат графики.
 в рамке @ Dynamic [
   Обработчик события[
   LocatorPane [
    Динамический [пт],
    Динамический [
     (* интерфейс рисования схемы *)
     Графика[{
       Который[
        (* предварительный просмотр активных ворот в случае режима *)
        inputMode == "placeGate",
        logicGate [pt, \ [Theta], arity, mode, «графика»],

        (* предварительный просмотр *)
        inputMode == "drawWire",
        Если [Length [wirePoints]> 0,
         {
          Строка [Добавить [WirePoints, pt]],
          {PointSize [0.01], точка [wirePoints [[1]]]}
          }
         ]
        ],
       (* посмотреть схему *)
       схемаГрафическая
       (* сюжетные связи *)
       Если [Values [Присоединиться @@ Values [circuitData [[All, «input»]]]]! = {},
        {PointSize [0,01],
         Точка [Перекресток [
           Значения [Присоединиться к @@ Значения [circuitData [[Все, «ввод»]]]],
           Значения [Присоединиться к @@ Значения [circuitData [[Все, «вывод»]]]]]]}
        ]
       },
      PlotRange -> {{0, 8}, {0, 8}},
      Размер изображения -> Большой
      ]
     ],
    Внешний вид -> Нет
    ],
   {"MouseUp":> Который [
      inputMode == "placeGate", snapToProximalNode,
      inputMode == "drawWire",
      Который[
       Длина [wirePoints] == 0 && wireSnapTo =! = Null,
       AppendTo [WirePoints, WireSnapTo],
       Длина [wirePoints]> 0 && wireSnapTo == Null &&
        wireSnapToTerminate == Null,
       AppendTo [WirePoints, pt],
       Длина [wirePoints]> 0 && wireSnapTo == Null &&
        wireSnapToTerminate =! = Null,
       AppendTo [WirePoints, WireSnapToTerminate]
       ]
      ], PassEventsDown -> True
    }
   ]
  ]
 
После размещения кнопка используется для «установки» ворот в программу.Поведение кнопок меняется в зависимости от «режима» графического интерфейса пользователя (размещение ворот или рисование проводов), но каждый из них имеет аналогичный процесс: добавление графики в список, добавление данных в список. В случае затвора графический объект, возвращенный через logicGate [pt, \ [Theta], arity, mode, «graphics»] , добавляется к списку circuitGraphic , инициализированному как {} .
 AppendTo [circuitGraphic, logicGate [pt, \ [Theta], arity, mode, "graphics"]]
 
Однако для генерации любого полезного вывода необходимо также записать расположение узлов ворот и их функции.Ассоциация используется для легкого поиска и организации, поскольку узлы необходимо будет идентифицировать не только по их соответствующим воротам, но и в том случае, если они представляют вход или выход.
При нажатии на кнопку «Установить» создается ассоциация ворот (1,2,3 ..) с его функциями и узлами ввода и вывода. Узлы индексируются последовательно и классифицируются отдельно.
 AppendTo [circuitData,
 Длина [circuitData] + 1 -> <|
   "функция" -> logicGate [pt, \ [Theta], arity, mode, "function"],
   "ввод" -> AssociationThread [
     Если[
       Длина [circuitData] == 0,
       (Rest @ Range [0, arity] + Length [circuitData]),
       Самый@
        Диапазон [(Ключи [(Last @ circuitData) ["output"]] + 1) [[
          1]], (Ключи [(Last @ circuitData) ["output"]] + 1) [[1]] + arity]]
      -> logicGate [pt, \ [Theta], arity, mode, "nodes"] ["input"]],
   «вывод» -> <|
     Если[
       Длина [circuitData] == 0,
       Последний [(Rest @ Range [0, arity] + Length [circuitData])] + 1,
       Последний [Большинство @
          Диапазон [(Ключи [(Last @ circuitData) ["output"]] + 1) [[
            1]], (Ключи [(Last @ circuitData) ["output"]] + 1) [[1]] +
            arity]] + 1
       ]
      -> logicGate [pt, \ [Theta], arity, mode, "nodes"] ["output"] |>
   |>
 ]



В [78]: = circuitData

Вых [78] = <|
1 -> <|
«функция» -> И, «ввод» -> <| 1 -> {1.22, 5.91}, 2 -> {1.22, 6.41} |>, "output" -> <| 3 -> {3.22, 6.16} |>
|>,
 2 -> <|
"функция" -> И, "ввод" -> <| 4 -> {1.47, 3.62}, 5 -> {1.47, 4.12} |>, "вывод" -> <| 6 -> {3.47, 3.87} | >
|>,
 3 -> <|
«функция» -> И, «вход» -> <| 7 -> {5.22, 5.57}, 8 -> {5.22, 6.07} |>, «вывод» -> <| 9 -> {7.22, 5.82} | >
|>,
 4 -> <|
«функция» -> И, «ввод» -> <| 10 -> {3.415, 1.5}, 11 -> {3.415, 2.} |>, "вывод" -> <| 12 -> {5.415, 1.75} |>
|>
|>
 
Шлюзы, которые соединены друг с другом, будут идентифицированы путем поиска позиций узлов из двух разных ворот, но с точно таким же значением. (Эти значения используются в качестве местоположения точек, нарисованных при подключении между клеммами / проводами). Неразумно требовать, чтобы пользователь размещал ворота с такой точностью, чтобы они казались связанными, поэтому графический интерфейс обнаруживает любой экземпляр узлов из активных ворот (тот, который пользователь находится в процессе размещения), прибывающих в непосредственной близости с узлами из уже размещает ворота и «защелкивает» активные ворота на месте.Я подумал об использовании более традиционного интерфейса с сеткой, но решил, что метод размещения произвольной формы обеспечивает большую гибкость и интерес.
 snapToProximalNode: =
 Если [Values [Присоединиться @@ Values [circuitData [[All, «input»]]]]! = {},
  С участием[{

(* это узлы, принадлежащие уже размещенным воротам *)
    PlaceNodes = Присоединиться [
      Значения [Присоединиться к @@ Значения [circuitData [[Все, «ввод»]]]],
      Значения [Присоединиться к @@ Значения [circuitData [[Все, «вывод»]]]]
      ],

(* это узлы активного гейта *)
    activeNodes = Присоединиться [
      logicGate [pt, \ [Theta], arity, mode, «узлы»] [«вход»],
      {logicGate [точка, \ [тета], арность, режим, «узлы»] [«выход»]}
      ]
    },
   Заблокировать [{i},
    я = 1;
    В то время как[
(* для каждого активного узла, начиная с первого в списке, ищите размещенный узел, который находится в радиусе 0.2. *)
     Ближайшие [PlaceNodes, activeNodes [[i]], {1, 0.2}] == {} && i <= Length [activeNodes],
(* Если ничего не найдено, перейдите к следующему активному узлу *)
     Если [i  Чтобы  snapToProximalNode  оценивался автоматически, интерфейс на основе панели локатора оборачивается в обработчик событий, который выполняет привязку ворот (и проводов) при отпускании кнопки мыши.
 Рисование проводов включает аналогичные процедуры для привязки конца провода к любым ближайшим воротам. Провода могут быть протянуты только от существующего терминала, но могут заканчиваться где угодно. В вычислительном смысле, когда пользователь рисует провод, он фактически получает местоположение узла, в котором начинается провод, и изменяет его значение на положение конечной точки проводов, то есть простое расширение терминала ворот. Тот же экземпляр обработчика событий, упомянутый ранее, также добавляет местоположение мыши во временный список для рисования провода перед добавлением в список графики.
 После настройки инструментов графического интерфейса пользователя следующим шагом будет сбор информации из  circuitData  в ряд связанных узлов. Необходимо сделать две вещи:
 1- найти и подключить выходные узлы, которые присоединены к входным узлам других ворот
 2 - соединить выходные узлы ворот с его входными узлами для всех ворот.
 Для шага 1 все выходные узлы, начиная с первого в  circuitData , сравниваются на равенство с входными узлами - если есть совпадение, их идентификаторы (индексы из  circuitData ) формируют основу направленного ребра.При повторении мы получим что-то вроде F1-> a-> F2-> b ... но то, что на самом деле представлено, больше похоже на F1-> F2-> .. т.е. нам нужно представить подключенный вентиль его выходом. а не подключенным входом.
 Мы применяем аналогичный подход к шагу 2, когда при подключении соответствующих входов и выходов для каждого элемента мы игнорируем создание соединений между входами, которые уже подключены к другому элементу.
 Это сгенерирует список связанных вершин
 В [101]: = Модуль [{
  outputNodeID = Присоединиться к @@ Values [circuitData [[All, "output"]]],
  inputNodeID = Join @@ Values [circuitData [[All, "input"]]]
  },
 соединения = {};
 подключения = Заблокировать [{
    я = 1, j = 1
    },
   (* подключение узлов к узлам для разных ворот *)
   Делать[
    Пока [(outputNodeID [Keys [outputNodeID] [[i]]]] ==
        inputNodeID [Keys [inputNodeID] [[j]]]) == Ложь,
     Если [j <Длина [Ключи [inputNodeID]], j ++, j = 0; Перерыв[]]];
    Если [j! = 0,
     AppendTo [соединения,
      (* получить узел выхода, принадлежащий входящему узлу соединительного шлюза *)
      Ключи [outputNodeID] [[i]] \ [DirectedEdge] Блок [{k = 1},
        В то время как[
         ContainsAny [
           Ключи [circuitData [k] ["input"]], {Keys [inputNodeID] [[j]]}] ==
           Ложь, k ++
         ];
        Ключи [circuitData [k] ["output"]] [[1]]
        ]
      ]
     ];
    j = 1,
    {i, 1, длина [ключи [outputNodeID]]}
    ];
   (* соединить выходные узлы с входными узлами для тех же ворот, кроме случая \
вход уже подключен к выходному узлу другого гейта *)
   Делать[
    AppendTo [соединения,
     DirectedEdge @@@ Transpose [{
          #,
          Таблица [Ключи [circuitData [i] ["output"]] [[1]], Длина [#]]
          }] И [
      Извлечь [Ключи [circuitData [i] ["input"]],
       Позиция[
        ContainsAny [Значения [outputNodeID], {#}] & / @
         Поиск [inputNodeID, Keys [circuitData [i] ["input"]]], False]]]
     ],
    {i, 1, длина [circuitData]}
    ];
   Сгладить [соединения]
   ]
 ]
 
 Мы идентифицируем вершину, представляющую выход схемы, по ее исходной степени; будет 0.К нему присоединяется новая вершина, представляющая выходное состояние функции.
 В [103]: = (* добавить терминал функции *)
AppendTo [соединения,
 (Извлечь [VertexList [#], Position [VertexInDegree [#], 0]] и [
     График [Обратные / @ соединения]]) [[1]] \ [DirectedEdge] "f1"]
 
 Для вершин, представляющих функции, мы заменяем их заполнителями функций
 В [105]: = (* заполнители подфункций *)
Connections = (Обратные / @ соединения) /.
  Нормальный [AssociationThread [
    Ключи [outputNodeID] ->
     Таблица ["F" <> ToString [i], {i, 1, Length [Keys [outputNodeID]]}]]]
 
 Аналогично для входных данных
 В [106]: = (* подзаполнитель во входных заполнителях *)
соединения =
 соединения /.Тема [# -> ToUpperCase / @ Alphabet [] [[1 ;; Длина[#]]]] &[
  Извлеките [VertexList [График [соединения]],
   Позиция [VertexOutDegree [График [соединения]], 0]]]
 
 Список правил замены составлен на более поздние
 В [107]: = (* сгенерировать правила замены оценки *)
functionReplaceRules =
 Тема [Таблица [
    "F" <> ToString [i], {i, 1, Length [Keys [outputNodeID]]}] ->
   Значения [circuitData [[Все, «функция»]]]]

Out [107] = {"F1" -> И, "F2" -> И, "F3" -> И}
 
  соединений  теперь формирует граф, который удовлетворяет требованиям, изложенным ранее, и поэтому может быть преобразован в логическое выражение.
 Метод управления заданной ранее функцией вентилей расширен на несколько вентилей и добавлен аналогичный интерфейс для управления.
 Заключение 
 Хотя существуют некоторые довольно большие ограничения (пользователь не может объединить несколько выходов с одним и тем же входом), и к концу проекта я все еще не позаботился о включении базового шлюза НЕ, эти проблемы второстепенны после успеха проекта как эксперимент с новыми методами и возможность усовершенствовать существующие в другой обстановке.
  Вложения:  Логические и цифровые схемы 
 Современные цифровые компьютеры построены из цифровых логических схем, основными строительными блоками которых являются логические вентили, каждый из которых предназначен для реализации определенной логической функции.Информация хранится в «словах» данных, представляющих данные или инструкции, составленные из строк отдельных «битов» с двоичными значениями 1 или 0. Эти значения аналогичны предложениям булевой логики и утверждениям или выводам на их основе, которые были определены как «истина» или «ложь». Булева алгебра - это инструмент, используемый для разработки комбинаций вентилей для реализации более сложных функций, таких как математические операции, функции управления и хранение данных.
 
 Логическая алгебра 
 Булева алгебра основана на двузначной или двоичной схеме.Эти два значения могут быть выражены разными способами, например, истина или ложь, 1 или 0, а также «включено» или «выключено». Именно это свойство, которое было признано и разработано Клодом Шенноном в 1937 году, делает его настолько полезным для реализации логических функций с помощью электронных схем. Например, логическая 1 и логический 0 могут быть реализованы как два разных уровня напряжения в цепи, или по состоянию переключателя, или по наличию или отсутствию тока в цепи.
  Обозначение 
 Инженерное приложение логики Буля использует упрощенную версию исходной записи, как показано ниже,
  Логическое ИЛИ  эквивалентно логическому сложению и представлено знаком плюс  + , как в  A + B ≡A OR B .
 Может представлять  параллельных  переключающих контакта.
  Логическое И  эквивалентно логическому умножению, которое представлено точкой .  знак как в  A.B ≡ A AND B .
 Может представлять переключающие контакты  серии .
 Обратите внимание, что теперь принято опускать точку . Знак  (символ И) так, чтобы  A.B  записывается как  AB .
  Логическое НЕ  эквивалентно логическому дополнению или отрицанию и представлено чертой сверху  ‾‾  над соответствующей переменной, как в  ≡ НЕ A. 
 Может представлять  нормально замкнутых  переключающих контакта.
  Логический исключающий OR  или  XOR  не был исходным логическим оператором и имеет свой собственный специальный символ, как в  ≡   B + A , который истинен, если  A или B  истинны, но  НЕ  оба.
  Логические законы 
  Двойственность 
 Обратите внимание, что у каждого закона есть два выражения, (a) и (b), которые являются двойственными друг другу. Двойственность означает
 Замена каждой операции ИЛИ (+) выражения на И (.)  и каждой операции И (. ) на ИЛИ (+).
 Замена всех элементов 0 на 1 и наоборот.
 
  Коммутативный закон 
 (а)  A + B = B + A  
 (б)  A B = B A 
  Юридический отдел 
 (а)  (A + B) + C = A + (B + C)  
 (б)  (A B) C = A (B C) 
  Распределительное право 
 (а)  A (B + C) = A B + A C  
 (б)  A + (B C) = (A + B) (A + C) 
  Законы о личности 
 (а)  А + А = А  
 (б)  A A = A 
 (а)  AB + A = A  
 (б)  (А + В) (А +) = А 
  Законы о резервировании 
 (а)  A + A B = A  
 (б)  А (А + В) = А 
 (а)  0 + А = А  
 (б)  0 А = 0 
 (а)  1 + A = 1  
 (б)  1 А = А 
 (а)  A + = 1  
 (б)  А = 0 
 (а)  A + B = A + B  
 (б)  A (+ B) = AB 
 
  Закон об инволюции 
 (а) =  А 
  Теорема Де Моргана 
 (a)  =  (Разрыв верхней черты меняет OR на AND) 
 (b)  =  + (Разрыв верхней черты меняет И на ИЛИ)
 Примечание: не то же самое, что
 В дополнение к вышеупомянутой булевой алгебре были разработаны цифровые логические вентили для представления выражений исключающее ИЛИ и исключающее ИЛИ, расширяющих исходный диапазон логических законов.См. Выражения «исключающее ИЛИ» ниже.
 
 Логические ворота 
 Логические вентили могут иметь два или более входа и, за исключением некоторых особых случаев, один выход. Состояние входных и выходных клемм может быть только в одном из двух двоичных состояний, низком (0) или высоком (1), представленном двумя разными уровнями напряжения, обычно 0 вольт для логического 0 и от 3 до 5 вольт. для логической 1, в зависимости от используемой полупроводниковой технологии.Логические ворота также требуют источника питания.
 
 Транзистор как переключатель 
 Электронные затворы обычно конструируются из транзисторных схем, работа которых зависит от использования транзистора в качестве переключателя, а не усилителя, для которого он был первоначально изобретен. При отсутствии напряжения на базе нет тока через транзистор, который, таким образом, отключается, и выходное (коллекторное) напряжение будет высоким.Когда на базу подается «высокое» напряжение, транзистор включается и выходное (коллекторное) напряжение будет «низким». Подробнее читайте на странице о полупроводниках. 
 Ранней версией бистабильной схемы переключения был триггер Eccles and Jordan 1919 года, основанный на клапанах (вакуумных лампах). Более поздняя версия транзистора была одной из первых электронных схем, реализованных Робертом Нойсом в качестве интегральной схемы в 1959 году.
 Триггеры основаны на концепции обратной связи, в которой выход схемы подается обратно на вход, так что, когда вход высокий, выход низкий и наоборот.
 См. Ниже пример транзисторных ключей, используемых в электронной схеме, используемой для реализации трехвходового логического элемента ИЛИ-НЕ 
 
 Логические ворота и таблицы истинности 
 Таблицы истинности логической схемы показывают состояние выходной клеммы или клемм логических вентилей и логических схем для всех возможных комбинаций входов . Входные состояния ворот или схемы показаны в левых столбцах таблицы, а соответствующие выходные состояния показаны в правых столбцах.
 Таблицы напротив показывают диапазон общих логических вентилей с соответствующими им таблицами истинности.  Логические ворота  Таблицы истинности 
  И Гейтс   А   В   А.В 
 0  0  0  1
 0  1  0  1
 1  0  0  1
 1  1  1  0
  OR Gates   А   Б   А + В 
 0  0  0  1
 0  1  1  0
 1  0  1  0
 1  1  1  0
  Эксклюзивное ИЛИ Ворота   А   Б 
 0  0  0  1
 0  1  1  0
 1  0  1  0
 1  1  0  1
  А 
 0  1
 1  0
 Ворота XOR и XNOR 
 Элемент  Exclusive OR  (XOR) со входами  A,  и  B  реализует логическое выражение  =   B + A 
 Когда оба входа различны, на выходе устанавливается высокий уровень или логическая 1.
 Когда оба входа одинаковы, выход становится низким или логическим 0.
 Элемент  Exclusive NOR  (XNOR) со входами  A,  и  B  реализует логическое выражение  =   = AB + 
 Когда оба входа одинаковы, выход становится высоким или логической 1.
 Когда оба входа различны, выход становится низким или логическим 0.
 Вентили «Исключающее ИЛИ» обычно используются для сравнений и проверок на четность.
 
 Шифр Вернама 
 Шифр Вернама - это специальное приложение логики XOR. Также называется  Modulo 2 Addition,  он похож на цифровой сумматор, за исключением того, что цифры переноса игнорируются.
 Важный инструмент криптографии, его особое свойство состоит в том, что строку сообщения с открытым текстом можно зашифровать с помощью операции XOR со случайной строкой скремблера символов или ключом той же длины для создания действительно неразрывного зашифрованного текста.Однако зашифрованный текст можно расшифровать напрямую с помощью операции XOR с исходным ключом скремблера.
 Вернам использовал пятибитный код Бодо для представления каждого символа с исходной нотацией  +  и - для представления логических состояний, а не с более знакомыми 1 и  0 , используемыми сегодня. В примере напротив:
 Открытая буква A зашифровывается путем добавления случайной буквы скремблера, например буквы B.Это генерирует код Бодо для зашифрованного текста G.
 Путем добавления той же буквы скремблера B к зашифрованному тексту G восстанавливается исходная буква открытого текста.   Таблица истинности 
  Входы   Выход / 
  Ввод   Выход 
 Обычный текст  Скремблер  Шифрованный текст  Обычный текст
  А   В   = G   = А 
  +   +   -   + 
  +   -   +   + 
  -   -   -  –
  -   +   +  –
 –   +   +  –
 
 Три входа NOR Gate 
 Схема напротив представляет собой пример логического элемента ИЛИ-НЕ с тремя входами, показывающий электронную схему, из которой построен вентиль, вместе с символом схемы для логического элемента и таблицей истинности, связанной с вентилем.
 Применение логической 1 к любой из входных клемм A, B или C вызывает прохождение тока через нагрузочный резистор R4, который, в свою очередь, вызывает падение напряжения на выходной клемме Z до логического уровня 0.
 Только когда все входные клеммы установлены на логический 0, ток через нагрузочный резистор будет отключен, а напряжение на выходной клемме повысится до логического уровня 1.
 Таким образом, выход с логической 1 может быть только в том случае, если ни A, ни B, ни C не установлены на логическую 1. 
 Z = 
 Таблица истинности 
 А  Б  К 
 0  0  0  1
 0  1  0  0
 0  0  1  0
 0  1  1  0
 1  0  0  0
 1  1  0  0
 1  0  1  0
 1  1  1  0
 
 Цифровые логические схемы 
 Логическая логика используется для разработки сложных цифровых схем, выполняющих широкий спектр логических функций.Однако часто существует более одного способа реализовать логическую схему с использованием альтернативных типов вентилей. Ниже приведены некоторые примеры.
 
 Вьетнамки и защелки с установкой и сбросом 
 Триггер Set-Reset, состоящий из двух перекрестно соединенных, двух входов, вентилей ИЛИ-НЕ, является одной из фундаментальных схем цифровой логики. Это бистабильная схема, которая может хранить один бит данных в виде двоичного нуля или двоичного единицы и используется в качестве запоминающего устройства или защелки.
 Применение логической 1 к клемме установки  S  сохраняет 1 и устанавливает выходную клемму  Q  на логическую 1.
 Применение логической 1 к клемме сброса  R  очищает память, сохраняя вместо этого 0 и устанавливает  Q  в логический 0.
 является обратным или дополнительным к  Q 
 Триггеры или защелки также могут быть сконструированы из логических элементов NAND с аналогичными перекрестными соединениями.   Триггер Set-Reset с воротами NOR 
  Таблица истинности 
  Установка / сброс   Выход 
  S   р   Q   Результат 
 0  0  Без изменений
 0  1  0  1  Сброс защелки
 1  0  1  0  Набор защелок
 1  1  Не допускается
  Регистры  - это обычные запоминающие устройства, обеспечивающие временное хранение многобитовых слов данных, таких как 4, 8 или 16-битные слова.Они состоят из групп триггеров, каждая из которых хранит один бит информации, так что  n  триггеров используются для хранения  n бит  слова.
  Сумматоры 
 Схема напротив представляет собой однобитовый полусумматор, состоящий из пяти вентилей И-НЕ.
 Полусумматоры имеют только два входа для двух добавляемых битов и не могут принимать бит переноса с предыдущего каскада.Однако у них есть два выхода: один для суммы, а другой для вывода переноса из двухбитового сложения.  Таблица истинности 
 А  Б  Сумма  Перенести
 0  0  0  0
 1  0  1  0
 0  1  1  0
 1  1  0  1
 
 Полусумматор напротив - еще один пример того, как логические функции могут быть реализованы по-разному.В этом случае схему сумматора можно упростить, используя только два логических элемента, логический элемент «И» и логический элемент «исключающее ИЛИ» для выполнения той же функции полусумматора, что и в схеме выше. 
 Полные сумматоры предназначены для приема бита переноса из предыдущего каскада и, следовательно, имеют три входа. Схема ниже представляет собой пример однобитового полного сумматора, полностью состоящего из двух входных вентилей ИЛИ-НЕ. В этом случае, по существу, это два полусумматора с двумя входами, соединенные последовательно, причем входной бит переноса проходит в обход первого сумматора и добавляется к сумме двух входных битов из первого сумматора во втором сумматоре.
 Обратите внимание, что требуется 12 таких вентилей, чтобы просто сложить два отдельных бита плюс любой входной бит переноса из предыдущего этапа сложения и предоставить два выходных бита, представляющих сумму битов и любой связанный бит переноса. Логическая схема, предназначенная для сложения двух восьмибитных слов, потребует в восемь раз больше вентилей.
  Таблица истинности 
  Входы   Выходы 
  А   В   C _дюйм   Сумма   C _из 
 0  0  0  0  0
 0  0  1  1  0
 0  1  0  1  0
 0  1  1  0  1
 1  0  0  1  0
 1  0  1  0  1
 1  1  0  0  1
 1  1  1  1  1
 Может показаться странным использование такого количества ворот, когда схема может быть легко реализована с меньшим количеством более сложных ворот, но схемы, такие как сумматор выше, использовались в управляющем компьютере  Apollo , который доставил американских астронавтов на Луну. в 1969 г.Все его цифровые схемы были построены из трех входных вентилей ИЛИ-НЕ. Это было связано с тем, что им требовались высоконадежные полупроводниковые компоненты, и в то время (1966 г.), когда компьютерный дизайн был заморожен, технология интегральных схем все еще находилась в зачаточном состоянии, и НАСА хотело ограничить количество различных компонентов, используемых для тех, которые имеют проверенный послужной список. . Ворота NOR были выбраны, потому что они были одним из очень немногих вариантов, которые отвечали этому требованию, и потому, что ворота NOR были простыми и более универсальными, чем другие доступные ворота, для создания более сложных функций.
 
 Двоичная арифметика 
 Двоичный сумматор может быть адаптирован для выполнения других арифметических операций, таких как вычитание, умножение и деление, а также других более сложных математических функций, избегая необходимости использования нескольких специализированных процессоров, используя следующие принципы двоичной арифметики.
 Дополнение числа до 1 совпадает с числом, при этом все его единицы заменены на 0, а все его 0 заменены на единицы.Этот ход позволяет сумматору иметь дело с отрицательными числами и вычитанием.
 Дополнение до 2 совпадает с дополнением до единицы с добавлением дополнительной единицы к младшему биту.
 Знак положительного или отрицательного двоичного числа изменяется путем взятия его дополнения до 2.
 Сдвиг влево всех битов двоичного числа на 1 позицию аналогичен умножению числа на 2 (двоичное 10).
 Сдвиг вправо всех битов на 1 позицию аналогичен делению числа на 2 (двоичная 10).
 Число может быть увеличено до  n -й степени двойки, добавив  n  нулей в конец числа.
 Умножение многобитового числа на 1 дает то же самое число. Умножение его на 0 дает 0 и может быть проигнорировано. Это делает умножение очень простым.
 Деление многобитового числа 1 возвращает то же самое число.
 Деление любого числа 0 не допускается.
 Умножение двух многобитовых чисел включает повторение операций «сдвига и умножения влево»  n  раз в цикле, где  n  - количество битов в умножителе.
 Деление двух многобитовых чисел включает в себя повторение операций «сдвига вправо и деления»  mn  раз в цикле, где  m  - количество бит в делимом (делимое число), а  n  - это число количество бит в делителе.
 Подпрограммы выполняют серию инструкций для выполнения арифметических операций.
 Ниже приведены три наиболее распространенных примера.
 
  Вычитание 
 Для вычитания двоичного числа B (вычитаемое) из двоичного числа A (уменьшаемое).
 Складываем двойное дополнение B к A
 Если есть последний бит переноса, отбросьте его, и результат будет положительным.
 Если B больше, чем A, не будет бита переноса, и результатом будет два отрицательных дополнения к сумме.
 (Есть несколько другой способ сделать вычитание с дополнением до 1 для B вместо дополнения до 2.)
 
  Умножение 
 Это включает  n  шагов, где  n  - количество бит в умножителе.
 Шаг первый
 Начать с младшего значащего бита (LSB) умножителя.
 Если этот бит умножителя равен 1, добавьте множимое (умножаемое число) к произведению (результату умножения). (Начальная стоимость товара будет равна нулю)
 Если этот бит умножителя равен 0, игнорируйте и переходите к следующему шагу.
 На каждом последующем шаге:
 Множаемое сдвинуто на одну позицию влево.
 Проверяется следующий бит умножителя.
 Если этот бит равен 1, смещенное множимое добавляется к текущему значению произведения.
 Если этот бит равен 0, игнорируйте и переходите к следующему шагу.
 Повторите шаг  n  раз в цикле (пока множимое не будет умножено на каждый бит множителя).
 
  Отдел 
 Эта операция включает  m  -  n  шагов, где  m  - это количество бит в делимом (число, которое делится), а  n  - это количество бит в делителе.
 Примечание. Необходимо включить проверки и настроить операцию, чтобы избежать потенциальной проблемы деления на 0.
 Начните с выравнивания самого старшего бита (MSB) делителя непосредственно под MSB делимого.
 Сравните  n  бит делителя с соответствующими  n  битами делимого непосредственно выше.
 Если делитель больше делимого, установите 0 как первый бит частного (результат деления).
 Если делитель меньше делимого, вычтите делитель из дивиденда, чтобы получить новое делимое / остаток, и установите первый бит частного равным 1.
 Перейти к следующему шагу
 На каждом последующем шаге:
 Сдвиньте делитель на одну позицию вправо и сравните его со следующими  n  бит делимого
 Если делитель больше, чем соответствующие  n  бит делимого, установите следующий бит частного равным 0
 Если делитель меньше делимого, вычтите делитель из делимого, чтобы получить новое делимое / остаток, и установите следующий бит частного равным 1.
 Повторить шаг  m-n  раз в цикле (пока младшие биты делителя и делимого не выровняются вверх)
 Результатом вычитания на последнем шаге является повторное деление.
 
 Подпрограммы включают специальные контрольные точки для обнаружения и вставки дополнительных инструкций для работы с битами переноса и заимствования, переполнениями, отрицательными числами, остатками, делением на ноль, если делитель больше делимого.
 Подпрограммы, аналогичные приведенным выше, в комбинации логических схем, используются для расширения возможностей арифметико-логического блока компьютера (ALU), позволяя ему выполнять многие более сложные функции.
 Подробнее о компьютерной архитектуре
 
 Арифметика с плавающей запятой 
 Вычислительный блок компьютера имеет в сумке всего два аппаратных средства: « сдвиг, » и «, прибавьте », чтобы выполнять все свои математические операции.Все основные арифметические операции с четырьмя функциями, описанные в предыдущем разделе, были выполнены с помощью этих двух инструментов и всех соответствующих операций с целыми числами. Однако в практических приложениях даже самые простые математические вычисления предполагают работу с десятичными числами.
 Помимо этого, компьютер может также потребоваться для обработки трансцендентных функций, таких как логарифмы, экспоненциальные и тригонометрические функции, которые не могут быть представлены простыми алгебраическими выражениями и, следовательно, не могут быть обработаны с помощью простого  сдвига компьютера  и возможности  добавить .Однако трансцендентные функции могут быть расширены и выражены как бесконечный ряд более простых алгебраических выражений, каждое из которых может быть обработано основными операциями машины, но суммирование бесконечного ряда нецелесообразно. Требуется некоторая форма математического приближения. К счастью, начальные алгебраические члены ряда обычно, но не всегда, быстро сходятся к очень малым значениям, так что последующие члены можно безопасно игнорировать, не влияя серьезно на точность результата.Таким образом, трансцендентную функцию можно рассматривать как многочлен, состоящий только из нескольких первых значимых членов ряда. См. Примеры (ниже)
 Помимо точности, существует проблема масштаба. Трудно управлять как очень большими, так и очень маленькими числами в компьютерных регистрах данных и коммуникационных шинах практического размера. Некоторые примеры:
 Масса электрона около 0,000000000000000000000000000000836 кг.В научных обозначениях это пишется 9,10
 x 10 ^-31 кг.
 Масса Земли около 5972400000000000000000000 кг. В научных обозначениях это написано 5,9724 x 10 ²⁴ кг.
 Скорость света около 300000000 м / с (3,0 x 10 ⁸ м / с)
 Гравитационная постоянная Ньютона составляет около 0,0000000000667 Нм ² кг ^-2 (6.67 X 10 ^-11 Нм ² кг ^-2)
 Эти последние два числа могут даже входить в одно и то же уравнение.
 Проблема размера становится еще более сложной, когда числа представлены в их гораздо более длинной двоичной форме.
 Использование традиционных научных обозначений частично решает эту проблему, но вводит необходимость манипулировать положением десятичной точки.
 Эти проблемы точности, точности и масштаба решаются за счет использования арифметики с плавающей запятой, которая использует более удобную научную нотацию, но методы вычислений по-прежнему ограничиваются базовыми возможностями компьютера  shift  и  add .Однако эти базовые операции могут быть дополнены программными подпрограммами и дополнительной логикой и регистрами для хранения временных или промежуточных значений. Ниже приведены некоторые примеры вычислений с плавающей запятой:
 Сначала несколько определений:
  Обозначения номеров 
  Мантисса 
 Также называется  Significand,  содержит  все  цифры номера.Отрицательные значения представляют отрицательные числа. (Помните, что термин «мантисса» может вызвать путаницу, поскольку он также может относиться к дробной части десятичного логарифма.)
  База 
 Ссылочный номер, на котором основана экспонента.
  Показатель степени 
 Это мощность, на которую поднимается основание.
 Указывает, где располагается десятичная (или двоичная) точка относительно начала мантиссы.
  Система счисления корня 
 Двоичный эквивалент десятичной запятой в десятичных числах.
  Пример 
 В экспоненциальном представлении десятичное число 345,6 может быть представлено как 3,456 X 10 ², где 3456 - мантисса или мантисса, 10 - основание, а 2 - показатель степени.
  Число с плавающей запятой Преимущества 
 Они могут представлять числа самых разных величин (диапазон ограничен длиной показателя)
 Они обеспечивают одинаковую относительную точность для всех величин (точность ограничена длиной мантиссы)
 В вычислениях с использованием чисел как с очень большими, так и с очень маленькими величинами они позволяют сохранить точность обоих в результате.
  Операции с плавающей точкой (FP) 
 Операции с плавающей запятой могут быть реализованы аппаратно (схема) или программно (программный код). Однако программное обеспечение на два-три порядка медленнее, чем оборудование.
  Сдвиг бит 
 Сдвиг мантиссы влево на 1 бит уменьшает показатель степени на 1 и перемещает точку счисления вправо на одну позицию.
 Сдвиг мантиссы вправо на 1 бит увеличивает показатель степени на 1 и перемещает основание системы счисления влево на одно место.
  Базовые алгебраические функции FP 
  Дополнение FP 
 Совместите десятичные точки, увеличивая или уменьшая одну из степеней так, чтобы обе степени были одинаковыми. Это будет новая мантисса для суммы.
 Измените соответствующую мантиссу.
 Добавьте новые мантиссы, чтобы получить новую мантиссу на сумму.
  FP Вычитание 
 Совместите десятичные точки и измените мантиссу, как указано выше
 Вычесть с дополнением до 2
  FP Умножение 
 Умножьте мантиссы, чтобы получить новую мантиссу
 Сложите экспоненты, чтобы получить новую экспоненту
  Отделение FP 
 Разделите мантиссы, чтобы получить новую мантиссу
 Вычтите экспоненты, чтобы получить новую экспоненту
  Трансцендентальные и другие функции 
 Можно, но не обязательно практично, хранить все требуемые значения трансцендентных функций в справочных таблицах, хранящихся в памяти компьютера.Хотя это было бы удобно, во многих приложениях, однако, потребовались бы непрактично большие запоминающие устройства. Вместо этого необходимые значения должны быть рассчитаны по мере необходимости.
 Оценка значения трансцендентной функции включает в себя настройку цикла для вычисления значения каждого значимого члена в ряду по очереди и суммирования значений в отдельном аккумуляторе (с учетом знака). Чем больше членов в ряду, тем выше будет точность, но соответственно увеличится время обработки из-за увеличения количества вычислений.
 Часто возможно представить трансцендентную функцию, используя альтернативные математические методы приближения. Как и в случае вышеупомянутого компромисса между скоростью и точностью, альтернативные методы также предполагают аналогичные компромиссы. Ряд Тейлора - это обычное математическое разложение, хотя и не единственное, которое используется для аппроксимации значений трансцендентных функций. Ниже приведены некоторые типичные примеры с использованием серии Тейлора.
 Подробнее о сериале Тейлора.
 См. Также расширение CORDIC (ниже).
 
  Тригонометрические функции 
 Следующая серия представляет собой разложение Тейлора для синуса и косинуса, где переменная X измеряется в радианах.
 sin  (X)  ≈   х   
   Х   ³  +    Х   ⁵   
   Х   ⁷  +  .. .  +  (-1) ⁱ    Х   ^{(2i + 1)}  +  . . . 
 3!  5!  7!  (2i + 1)!
 
 cos ( X)  ≈  1   
   Х   ²  +    Х   ⁴   
   Х   ⁶  +  .. .  +  (-1) ⁱ    X   ⁽²ⁱ⁾  +  . . . 
 2!  4!  6!  (2i)!
 Обратите внимание, что эти две серии включают как положительные, так и отрицательные члены, а знаменатели включают возрастающие факториалы.Это означает, что члены очень быстро сойдутся к малым величинам.
 Отметим также, что компьютер обычно не вычисляет числовые значения факториалов, которые вместо этого извлекаются из справочных таблиц в памяти.
 Альтернативой ряду Тейлора для оценки значения синусоидальной функции является приближение Гастингса, которое примерно в три раза быстрее и лишь немного менее точно.
 Функция разделена на небольшое количество интервалов, и в каждом из них используется аппроксимация прямой линией.Наклоны отрезков прямой линии имеют знаменатели, являющиеся степенями двойки, поэтому для вычисления не требуются операции умножения или деления с плавающей запятой. Этот алгоритм использовался для тригонометрических вычислений в управляющем компьютере Apollo 11, который доставил астронавтов на Луну.
 
  Логарифмы 
  Экспоненциальная 
 Это разложение Тейлора для экспоненты ( e  ^z)
 эксп. ( Z )  ≈  1  +   Z  +    Z   ²  +    Z   ³  +    Z   ⁴  +    Z   ⁵  +  .. .  +    Z   ⁱ  +  . . . 
 2!  3!  4!  5!  (я)!
 Обратите внимание, что все члены в этом ряду положительны, а числители увеличиваются быстрее, чем знаменатели, поэтому ряды не сходятся, а расширяются.
 
  Квадратный корень 
 Квадратный корень не является трансцендентной функцией. Многочисленные способы вычисления квадратных корней были разработаны с тех пор, как первый формальный метод был предложен греческим математиком Героем Александрийским в первом веке нашей эры
 г. 
  Итерационный метод 
 Простой метод, основанный на принципах «угадать, проверить и уточнить», используется уже много лет.Он работает следующим образом, где a - желаемый квадратный корень  √  x
.
 Угадайте ответ  «а»  между 0 и x.
 Вычислить ²
 Найдите ошибку E в ответе E = x-a ²
 Если E положительное число, значит, a слишком мало. 
 Если E отрицательное число, a слишком большое.
 Если величина E достаточно мала, a =  √  x
 Если ошибка E слишком велика, измените  a,  вернитесь к шагу 2 и повторите.
 Величина E будет постепенно уменьшаться, пока не будет достигнута желаемая точность.
 Этот метод был разработан для использования с десятичными числами. Это не так удобно с двоичными числами и может привести к слишком большому количеству циклов, чтобы прийти к приемлемому ответу.Дополнительные шаги в этой простой программе могут улучшить это.
 
  Прямой метод 
 Квадратный корень можно вычислить напрямую, используя свойства натурального логарифма или логарифма с основанием 10, но сами логарифмы являются трансцендентными функциями, и значения должны быть сначала извлечены из подходящей процедуры аппроксимации, такой как приведенная выше.
 Метод зависит от следующих свойств натурального логарифма ( ln ):
  ln  X ⁿ = n  ln  X
 и
  e  ^{ln  X} = X
 Ответ дает: √x = e ^{( ln  X) / 2} с использованием натурального логарифма ( ln )
 В качестве альтернативы, используя логарифм по основанию 10 ( log ), ответ будет следующим: √x = 10 e ^{( log  X) / 2}
 (деление степени на 2 дает квадратный корень, как и в случае с логарифмическими таблицами).
 Карманные калькуляторы обычно используют этот метод вычисления квадратных корней.
 
  Алгоритмы аппроксимации CORDIC 
 Алгоритм   CORDIC - это итерационный метод вычисления трансцендентных функций с использованием только двоичных  сдвига  и  сложения  операций.
 Используя пример вычисления значения тангенса, X / Y = tan Θ, выраженного в форме tan (2 ^-n)
 Вектор из начала координат (ноль) поворачивается серией « n » малых шагов δΘ, так что сумма всех шагов равна.Накапливая соответствующие изменения значений его ортогональных координат δX и δY на каждом шаге, можно вычислить значения X и Y и, следовательно, касательную.
 Описанный Дж. Э. Волдером в 1959 году, алгоритм CORDIC был использован в первом научном портативном калькуляторе (HP-35), и с тех пор были разработаны и усовершенствованы варианты этой простой базовой концепции для аппроксимации широкого спектра трансцендентных функций.

(а) НЕ вентиль	(b) И ворота	(c) ИЛИ ворота

`x`	`y`	`x`	`y`	`x` `y`	`x` `y`	`x` `y`
0	0	1	1	1	0	1
0	1	1	0	0	0		1	0	0	1	0	0	1
1	1	0	0	0	1	0

* Красные со звездочкой не соответствуют стандартным алгебраическим тождествам.
		И		OR
коммутативный		`A` `B` = `B` `A`		`A` + `B` = `B` + `A`
ассоциативный		`A` ( `B` `C` ) = ( `A` `B` ) `C`		`A` + ( `B` + `C` ) = ( `A` + `B` ) + `C`
идентификационный номер		`A` ⋅ 1 = `A`		`А` + 0 = `А`
распределительный		`A` ( `B` + `C` ) = `A` `B` + `A` `C`	*	`A` + `B` `C` = ( `A` + `B` ) ( `A` + `C` ))
один / ноль		`А` ⋅ 0 = 0	*	`А` + 1 = 1
идемпотентность	*	`A` `A` = `A`	*	`A` + `A` = `A`
обратное	*	`A` `A` = 0	*	`A` + `A` = 1
Закон ДеМоргана	*	`A` `B` = `A` + `B`	*	`A` + `B` = `A` `B`
двойное отрицание	*	`А` = `А`

`x`	`y`	`z`	`o`	описание
0	0	1	1	`y` `z`
0	1	0	1	`x` `y` `z`
1	1		1	`x` `y` `z`
1	1	1	1	`x` `y` `z`

(a) Логический элемент NAND	(b) ворота NOR	(c) вентиль XOR	(d) вентиль XNOR

D	С	B	A	Z
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	0
1	1	0	0	1
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

Входы		Выходы
x	y	Стоимость (v $)	Выполнить ($ c_ {out} $)
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

Входы			Выходы
Перенести ($ c_ {in} $)	х	y	Стоимость (v $)	Выполнить ($ c_ {out} $)
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

D	С	B	A	Z
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	0
1	1	0	0	1
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1

Практическая работа №5,6 по Информатике и ИКТ

Как построить логическую схему по логическому выражению. Определение сигнала на выходе логической схемы по заданным значениям сигналов на всех входах этой схемы

Операция НЕ — логическое отрицание (инверсия)

Операция ИЛИ — логическое сложение (дизъюнкция, объединение)

Операция И — логическое умножение (конъюнкция)

Операция «ЕСЛИ-ТО» — логическое следование (импликация)

Операция «А тогда и только тогда, когда В» (эквивалентность, равнозначность)

Операция «Сложение по модулю 2» (XOR, исключающее или, строгая дизъюнкция)

Приоритет логических операций

Совершенная дизъюнктивная нормальная форма

Совершенная конъюнктивная нормальная форма

Создание выражений

Вкладка Выражение

Вкладка Минимизация

Виды задач на логические элементы.

Построение логической схемы по заданной логической функции.

Задача:

Решение:

Запись логической функции по заданной логической схеме.

Задача:

Решение:

Определение сигнала на выходе логической схемы по заданным значениям сигналов на всех входах этой схемы.

Задача:

Решение:

Ответ:

Построение таблицы истинности для заданной логической схемы.

Задача:

Решение:

Ответ:

Запишите логическую функцию соответствующую функциональной схеме

Примеры решения задач “Логические основы работы компьютера”

Вариант № 16

Построение логических схем выражений на примерах

Примеры решения задач «Логические основы работы компьютера»

Программа для построения логических схем

Опции формата

Внешний вид:

Ширина просмотра:

Поиск

Дополнительные ресурсы (левая колонка)

Конструктор логических схем

Логика и схемы

Содержание

1. Логические схемы

2. Построение логических схем

2.1. Логические выражения

2.2. Законы булевой алгебры

2.3. Сумма произведений

3. Упрощающие схемы

3.1. КПД схемы измерения

3.2. Карно карты

3.3. Более сложная карта Карно

4. Другие логические элементы и универсальность

Как разрабатывать логические схемы и логические вентили — видео и стенограмма урока

Пример 1

Пример 2

Итоги урока

Логические ворота — Уроки

Сумма произведений (9:38) | 4.2 Тематические видео | 4 Комбинационная логика | Вычислительные структуры | Электротехника и информатика

Модуль 6 Раздел 1. Основные логические вентили

домашних заданий

Рисование и моделирование логических схем

Определение функции логического элемента

Управление функцией ворот

Генерация логического выражения

Рисование логической схемы

Заключение

Логические и цифровые схемы

Логическая алгебра

Логические ворота

Транзистор как переключатель

Логические ворота и таблицы истинности

Логические ворота

Таблицы истинности

Ворота XOR и XNOR

Шифр ​​Вернама

Три входа NOR Gate

Z =

Таблица истинности

А

Шифр Вернама

D	С	B	A	Z
0	0	0	0	0
0	0	0	1	0
0	0	1	0	0
0	0	1	1	1
0	1	0	0	0
0	1	0	1	0
0	1	1	0	1
0	1	1	1	0
1	0	0	0	0
1	0	0	1	1
1	0	1	0	0
1	0	1	1	0
1	1	0	0	1
1	1	0	1	0
1	1	1	0	0
1	1	1	1	1