Схемы логических выражений. Основы логики: построение логических схем

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

Логические операции конъюнкции, дизъюнкции, инверсии реализуются в ЭВМ с помощью следующих элементарных схем.

Конъюнкция – логический элемент «и»:

Этот элемент выполняет операцию логического умножения (конъюнкция): f = x 1 Ù x 2 Ùx 3 Ù…Ùx n ; и имеет n входов и один выход.

Дизъюнкция – логический элемент «или»:

Этот элемент выполняет операцию логического сложения (дизъюнкция): f = x 1 Ú x 2 Úx 3 Ú…Úx n ; и имеет n входов и один выход.

Инверсия – логический элемент «не»:

Этот элемент выполняет операцию логического отрицания (инверсии): f = ; и имеет один вход и один выход.

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

Пример выполнения контрольного задания

Задание:

Дана функция,

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

2. Упростить логическую функцию (используя законы булевой алгебры) и выполнить проверку преобразования таблицей истинности.

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

Выполнение:

1. Составим таблицу истинности для заданной функции:

x	y

2. Составим функциональную логическую схему по заданной функции:

3. Упростим заданную функцию, используя законы булевой алгебры:

а) по закону де Моргана – 9

б) по закону идемпотентности - 13

в) закон отрицание отрицания – 1

г) закон дистрибутивности – 6

д) свойства 1 и 0 – 19

е) свойства 1 и 0 – 16

Таким образом, упрощенная функция имеет вид:

4. Составим таблицу истинности для упрощенной функции:

x	y

Таким образом, сравнивая таблицы истинности для исходной и упрощенной функций (их последние столбцы) делаем вывод о правильности проведенных преобразований.

5. Составим функциональную логическую схему по упрощенной функции:

Задание для выполнения контрольной работы

Дана функция f(x,y), номер функции в таблице соответствует порядковому номеру студента по списку.

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

5. Упростить логическую функцию (используя законы булевой алгебры) и выполнить проверку преобразования таблицей истинности.

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).

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

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

Задача:

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

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

Решение:

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

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

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

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

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

Задача:

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

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

Решение:

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

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

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

Задача:

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

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

Решение:

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

Ответ:

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

Задача:

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

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

Решение:

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

Ответ:

Цели урока:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ход урока

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

Добрый день!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программа - тренажер "Построение логических схем"

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

Логической функции в компьютере соответствует некоторая схема из вентилей. Этот принцип даёт такой подход к созданию компьютера :

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

Полученную функцию упрощают, используя законы алгебры логики.

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

Схема из вентилей реализуется на физическом уровне из электронных элементов.

Приведём пример реализации 3-го этапа . Дана функция

Получить логическую схему функции.

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

Рис. 5. Схема реализации функции (формула (28))

Возможно решение и обратной задачи, когда дана логическая схема, нужно получить логическую функцию. Например, на рис. 6 дана логическая схема. Требуется написать для неё логическую функцию.

Рис. 6. Схема реализации функции f ( x , y , z )

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

Так для схемы на рисунке 6 в первую очередь выполняться три операции: x∙y, и. Затем операция инвертирования суммы:
, далее ещё одна операция логического сложения результатов предыдущих операций:
. Последней будет выполняться операция инвертирования результата логического умножения:
. Таким образом, искомая функция имеет вид.