Логические основы работы ЭВМ

ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ПРОФЕССИОНАЛЬНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ РЕСПУБЛИКИ АДЫГЕЯ

АДЫГЕЙСКИЙ ПЕДАГОГИЧЕСКИЙ КОЛЛЕДЖ ИМ. Х. АНДРУХАЕВА

Логические основы работы ЭВМ

Методические указания

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

Майкоп, 2019

Понятие высказывания

Высказывание – это любое утверждение, относительно которого можно сказать, истинно оно или ложно. Приведем примеры высказываний:

• Число 14 делится на 2 и 7.

• Париж – столица Испании.

• Хабаровск стоит на Амуре.

• 3 1.

Высказывания «Число 14 делится на 2 и 7» и «Хабаровск стоит на Амуре» истинны, а высказывания «Париж – столица Испании» и «3 1» ложны.

По своей сути высказывания фактически являются двоичными объектами, и потому истинному значению высказывания ставят в соответствие 1 (Истина,True), а ложному – 0 (Ложь, False). В дальнейшем будем обозначать

высказывания буквами латинского алфавита.

Например, запись А = 1 означает, что высказывание А истинно.

Высказывания могут быть простыми и сложными. Простые высказывания соответствуют логическим переменным, которые принимают значение 0 или 1. Сложные высказывания являются аналогом логических функций и могут образовываться путем объединения переменных с помощью логических операций. Любая логическая функция может быть задана с помощью таблицы истинности, в левой части которой записываются возможные наборы переменных (аргументов), а в правой – соответствующие им значения функции. Это возможно по той причине, что все сочетания логических аргументов легко перечислить.

Из вышеприведенных высказываний второе и третье являются простыми, а первое высказывание, образованное из простых высказываний «Число 14 делится на 2» и «Число 14 делится на 7», является сложным высказыванием.

Логические операции над логическими переменными Отрицание

Операция отрицания является унарной, т.к. имеет один аргумент. Иначе ее

называют инверсией, дополнением, НЕ и обозначают X или _¬X, NOT X.

Отрицанием А некоторого высказывания А называется такое высказывание, которое истинно, когда А ложно, и ложно, когда А истинно.

Определение отрицания может быть записано с помощью таблицы истинности:

X	X
0	1
1	0

Логическое умножение

Операцию логического умножения еще называют конъюнкцией, логическим И. Для обозначения данной операции используют символы Λ, &, точку, которую можно опускать, AND.

Конъюнкцией двух высказываний X и Y называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания X и Y.

Определение конъюнкции может быть записано в виде таблицы истинности:

X	Y	X&Y
0	0	0
0	1	0
1	0	0
1	1	1

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

X₁ & X₂ & X₃ &...& X_n истинна тогда и только тогда, когда истинны все высказывания X₁, X₂, X₃, ...X_n, следовательно, принимает значение «ложь», когда ложно хотя бы одно из этих высказываний.

Логическое сложение

Операцию логического сложения иначе называют дизъюнкцией, логическим ИЛИ. Для обозначения логического сложения используют символы V, +, OR.

Таким образом, дизъюнкцией двух высказываний называется такое новое высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из этих высказываний.

Определение дизъюнкции может быть записано в виде таблицы истинности:

X	Y	X V Y
0	0	0
0	1	1
1	0	1
1	1	1

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

X₁ V X₂ V X₃ V... V X_n истинна тогда и только тогда, когда истинно хотя бы одно из этих высказываний, а, следовательно, принимает значение «ложь», когда все высказывания ложны.

Логическое следование

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

Импликацией X → Y называется высказывание, которое ложно тогда и только тогда, когда X истинно и Y ложно.

Определение импликации может быть записано в виде таблицы истинности:

X	Y	X → Y
0	0	1
0	1	1
1	0	0
1	1	1

Логическое тождество

Операцию логического тождества иначе называют эквиваленцией, эквива-

лентностью и для обозначения используют символы =, ↔, ~.

Таким образом, эквиваленцией двух высказываний X и Y называется такое высказывание, которое истинно тогда и только тогда, когда оба эти высказывания А и В истинны или оба ложны.

Определение эквиваленции может быть записано в виде таблицы истинности:

X	Y	X ↔ Y
0	0	1
0	1	0
1	0	0
1	1	1

Операция исключающее ИЛИ

Операция исключающее ИЛИ (неравнозначность, сложение по модулю два) обозначается символом  и отличается от логического ИЛИ только при X=1 и Y=1. Таким образом, неравнозначностью двух высказываний X и Y называют такое высказывание, которое истинно тогда и только тогда, когда одно их этих высказываний истинно, а другое ложно.

Определение данной операции может быть записано в виде таблицы истинности:

X	Y	X Y
0	0	0
0	1	1
1	0	1
1	1	0

Операция исключающее ИЛИ фактически сравнивает на совпадение два двоичных разряда.

Логические операции инверсии, дизъюнкции, конъюнкции образуют полную систему логических операций, из которых можно построить сколь угодно сложное логическое выражение. При вычислении значения логического выражения принято следующее старшинство (приоритет) логических операций: сначала выполняется инверсия, затем конъюнкция и в последнюю очередь – дизъюнкция. Для изменения указанного порядка используют скобки.

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

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

Закон тождества

Всякое высказывание тождественно самому себе: Х = Х.

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

Закон означает отсутствие показателей степени:

Х V Х = Х,

Х & Х = Х.

Закон исключения констант

Для логического сложения Х V 1 = 1, Х V 0 = Х.

Для логического умножения Х & 1 = Х, Х& 0=0.

Закон поглощения

Для логического сложения Х V (Х & Y) = X.

Для логического умножения X & (X V Y) = X.

Закон противоречия

Высказывание не может быть одновременно истинным и ложным. Если вы-

сказывание X истинно, то его отрицание X должно быть ложным. Следовательно, логическое произведение высказывания и его отрицания должно быть ложно:

X & X = 0.

Закон исключенного третьего

Высказывание может быть либо истинным, либо ложным, третьего не дано. Это означает, что результат логического сложения высказывания и его отрицания всегда принимает значение «истина»:

X V X = 1.

Закон двойного отрицания

Если дважды отрицать некоторое высказывание, то в результате мы получим исходное высказывание:

ХХ .

Законы общей инверсии (законы де Моргана)

XY = X &Y ,

X&Y = X V Y .

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

Закон переместительный (коммутативности)

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

X & Y = Y & X,

X V Y = Y V XА.

Закон сочетательный (ассоциативности)

Если в логическом выражении используются только операция логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять: (X & Y) & Z = X & (Y & Z), (X V Y) V Z= X V (Y V Z).

Закон распределительный (дистрибутивности)

В отличие от обычной алгебры, где за скобки можно выносить только общие множители, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые.

Дистрибутивность умножения относительно сложения: (X & Y) V (X & Z) = X&(Y V Z).

Дистрибутивность сложения относительно умножения:

(X V Y) & (X V Z) = X V (Y & Z)

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

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

• регистры;

• комбинационные преобразователи кодов (шифратор, дешифратор, мультиплексор и др.);

• счетчики (кольцевой, синхронный, асинхронный);

• арифметико-логические узлы (сумматор, узел сравнения).

Из этих узлов строятся интегральные микросхемы очень высокого уровня интеграции: микропроцессоры, модули ОЗУ, контроллеры внешних устройств и т.д.

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

Окончание табл. 1

Логическая функция	Условные обозначения логических элементов
Дизъюнкция (ИЛИ) Z = X V Y
	Х Y	1	Z
Исключающее ИЛИ Z = X  Y	Х =1 Z Y
Инверсия конъюнкции (И – НЕ) Z = X&Y
Инверсия дизъюнкции (ИЛИ – НЕ) Z = XY

Решение задач Пример 1

Какой логической операции соответствует таблица истинности, приведенная ниже?

F = X.

Таблица истинности соответствует операции отрицания.

Пример 2

Найти значение логического выражения

A V В & С при А=0 (False), B=1 (True), C=0(False).

Решение: подставим значения переменных в выражение и вычислим его согласно приоритету выполнения операций:

A V В & С = 0 V 1&0 = 0 V 1&1 = 0 V 1 = 1 (True).

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

Пример 3

Найти значение логического выражения

(a 2) V (a≠5) при a = 5, z = – 4.

Решение: подставим значения переменных в выражение и вычислим его согласно приоритету выполнения операций:

(5 2) V (5≠5) = 0 V 0 V 0 = 0.

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

Пример 4

Упростить логическое выражение: (А & В) V (А & B ). Правильность упрощения проверить с помощью таблиц истинности.

Решение: воспользуемся законом дистрибутивности и вынесем за скобки А:

(A & B) V (A & B ) = А & (B V B ).

По закону исключенного третьего В V B =1, следовательно,

А & (В V B ) = А & 1 = А.

Таким образом, в результате упрощения получили (А & В) V (А & B ) =А.

Составим таблицу истинности (табл. 2) для выражения (А & В) V (А & B ).

Таблица 2

	А	В	B	А & В	A & B	(A & B) V (A & B )
	0	0	1	0	0	0
	0	1	0	0	0	0
	1	0	1	0	1	1
	1	1	0	1	0	1

Из таблицы истинности видно, что справедливо (А & В) V (А & B )= А.

Ответ: (А & В) V (А & B ) =А.

Пример 5

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

Рис. 1

Решение: используя обозначения логических элементов (табл. 1), составим логическое выражение

F = X&YZ.

Заполним для F таблицу истинности (табл. 3).

Таблица 3

Задано логическое выражение F = XY&Z. Cоставить логическую схему

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

Решение: используя обозначения логических элементов (табл. 1), составим логическую схему (рис. 2).

Заполним для F таблицу истинности (табл. 4).

Таблица 4

	X	Y	Z	X V Y	XY	Z	XY&Z
	0	0	0	0	1	1	1
	0	0	1	0	1	0	0
	0	1	0	1	0	1	0
	0	1	1	1	0	0	0
	1	0	0	1	0	1	0
	1	0	1	1	0	0	0
	1	1	0	1	0	1	0
	1	1	1	1	0	0	0

Задания для самостоятельного решения Задание 1

Какой логической операции соответствует таблица истинности (табл. 5)?

Таблица 5

Задание 2

Какой логической операции соответствует таблица истинности (табл. 6)?

Таблица 6

Задание 3

1. A & В V С	при А = False, B = True, C = False.
2. (х = у) V (z	при х = 5, у = 7, z = 0.
3. A V B	при А = False, B = False.
4. (a -10) & (a≠5)	при a = 8, z = – 6.
5. AB & С Задание 4	при А = False, B = False, С = True.

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

Упростить логическое выражение AB V АВ. Правильность упрощения проверить с помощью таблицы истинности. Задание 5

Доказать данное равенство с помощью таблицы истинности.

X ↔ Y = (X&Y) V (Х&Y).

Задание 6

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

Рис. 3

Задание 7

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

Задание 8

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

Задание 9

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

X&YZ = F;

XY&Z = F;

XY&Z = F.

Библиографический список

1. Могилев А. В. Информатика : учеб. пособие для студ. высш. учеб. заведений / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – М. : Издательский центр «Академия», 2008. – 848 с.

2. Могилев А. В. Практикум по информатике : учеб. пособие для студ. высш. учеб. заведений / А. В. Могилев, Н. И. Пак, Е. К. Хеннер. – М. :

Издательский центр «Академия», 2008. – 608 с.

1. Алексеев П. А. Информатика / П. А. Алексеев. – М. : СОЛОН-Р, 2002 – 368 с.

2. Акулов О. А. Информатика : учеб. пособие для студ. вузов / О.А. Акулов, Н. В. Медведев. – М. : Омега-Л, 2005. – 552 с.

3. Лихтарников Л. М. Математическая логика. Курс лекций. Задачникпрактикум и решения : учеб. пособие / Л. М. Лихтарников,

Т. Г. Сукачева. – СПб. : Лань, 2008. – 288 с.

Оглавление

Понятие высказывания 3

Логические операции над логическими переменными 3

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

Решение задач 10

Задания для самостоятельного решения 13

Библиографический список 15

Главный редактор Л. А. Суевалова

Редактор Т. Ф. Шейкина

Оператор компьютерной верстки Е. Н. Ермишко

Подписано в печать 07.06.11 . Формат 6084 ¹/₁₆. Бумага писчая. Гарнитура «Таймс».

Печать цифровая. Усл. печ. л. 0,93 . Тираж 200 экз. Заказ 141.

Издательство Тихоокеанского государственного университета.

680035, Хабаровск, ул. Тихоокеанская, 136.

Отдел оперативной полиграфии

издательства Тихоокеанского государственного университета 680035, Хабаровск, ул. Тихоокеанская, 136.

 Тихоокеанский государственный университет, 2011