В настоящее время в обыденной жизни для кодирования числовой информации используется десятичная система счисления с основанием 10, в которой используется 10 элементов обозначения: числа 0, 1, 2, … 8, 9. В первом (младшем) разряде указывается число единиц, во втором - десятков, в третьем - сотен и т.д.; иными словами, в каждом следующем разряде вес разрядного коэффициента увеличивается в 10 раз.

В цифровых устройствах обработки информации используется двоичная система счисления с основанием 2, в которой используется два элемента обозначения: 0 и 1. Веса разрядов слева направо от младших разрядов к старшим увеличиваются в 2 раза, то есть имеют такую последовательность: 8421. В общем виде эта последовательность имеет вид:

…2 5 2 4 2 3 2 2 2 1 2 0 ,2 -1 2 -2 2 -3 …

и используется для перевода двоичного числа в десятичное. Например, двоичное число 101011 эквивалентно десятичному числу 43:

2 5 ·1+2 4 ·0+2 3 ·1+2 2 ·0+2 1 ·1+2 0 ·1=43

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

Бит или двоичный разряд определяет значение одного какого-либо знака в двоичном числе. Например, двоичное число 101 имеет три бита или три разряда. Крайний справа разряд, с наименьшим весом, называется младшим, а крайний слева, с наибольшим весом, - старшим .

Байт определяет 8-разрядную единицу информацию, 1 байт=23 бит, например, 10110011 или 01010111 и т.д., 1 кбайт = 2 10 байт, 1 Мбайт = 2 10 кбайт = 2 20 байт.

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

Основанием шестнадцатеричной системы счисления является число 16=2 4 , в которой используется 16 элементов обозначения: числа от 0 до 9 и буквы A, B, C, D, E, F. Для перевода двоичного числа в шестнадцатеричное достаточно двоичное число разделить на четырёхбитовые группы: целую часть справа налево, дробную - слева направо от запятой. Крайние группы могут быть неполными.

Каждая двоичная группа представляется соответствующим шестнадцатеричным символом (таблица 1). Например, двоичное число 0101110000111001 в шестнадцатеричной системе выражается числом 5C39.

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

Двоично-десятичный код образуется заменой каждой десятичной цифры числа четырёхразрядным двоичным представлением этой цифры в двоичном коде (См. таблицу 1). Например, число 15 представляется как 00010101 BCD (Binary Coded Decimal). При этом в каждом байте располагаются две десятичные цифры. Заметим, что двоично-десятичный код при таком преобразовании не является двоичным числом, эквивалентным десятичному числу.

1.2 Логические основы ЭВМ

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

Таблица 1 – Коды чисел от 0 до 15

Десятичное число	Коды
	Двоичный	16-ричный	Двоично-десятичный
0	0000	0	000
1	0001	1	0001
2	0010	2	0010
3	0011	3	0011
4	0100	4	0100
5	0101	5	0101
6	0110	6	0110
7	0111	7	0111
8	1000	8	1000
9	1001	9	1001
10	1010	A	00010000
11	1011	B	00010001
12	1100	C	00010010
13	1101	D	00010011
14	1110	E	00010100
15	1111	F	00010101

1.2.1 Основные положения алгебры логики

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

В общем виде логическая формула функции двух переменных записывается в виде: y =f (X 1 , X 2), где X 1 , X 2 - входные переменные.

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

Таблица 2 – Полный набор функций одной переменной

X	Y1	Y2	Y3	Y4
0	1	0	1	0
1	0	1	1	0

Y1 - Инверсия, Y2 - Тождественная функция, Y3 - Абсолютно истинная функция и Y4 – Абсолютно ложная функция.

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

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

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

Таблица 3 Названия и обозначения логических операций

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

Таблица 4 – Таблицы истинности основных функций двух переменных

Дизъюнкция			Конъюнкция			Исключающее ИЛИ			Стрелка Пирса			Штрих Шеффера
X1	X2	Y	X1	X2	Y	X1	X2	Y	X1	X2	Y	X1	X2	Y
0	0	0	0	0	0	0	0	0	0	0	1	0	0	1
0	1	1	0	1	0	0	1	1	0	1	0	0	1	1
1	0	1	1	0	0	1	0	1	1	0	0	1	0	1
1	1	1	1	1	1	1	1	0	1	1	0	1	1	0

Дизъюнкция. В отличие от обычного арифметического или алгебраического суммирования здесь наличие двух единиц даёт в результате единицу. Поэтому при обозначении логического суммирования предпочтение следует отдать знаку (∨) вместо знака (+) .

Первые две строчки таблицы истинности операции дизъюнкции (x 1 =0) определяют закон сложения с нулём : x ∨ 0 = x , а вторые две строчки (x 1 = 1) - закон сложения с единицей : x ∨ 1 = 1.

Конъюнкция. Таблица 4 убедительно показывает тождественность операций обычного и логическог умножений. Поэтому в качестве знака логического умножения возможно использование привычного знака обычного умножения в виде точки .

Первые две строчки таблицы истинности операции конъюнкции определяют закон умножения на ноль : x ·0 = 0, а вторые две - закон умножения на единицу: x ·1 = x.

Исключающее ИЛИ. Под функцией «Исключающее ИЛИ» понимают следующее: единица на выходе появляется тогда, когда только на одном входе присутствует единица. Если единиц на входах две или больше, или если на всех входах нули, то на выходе будет нуль.

Надпись на обозначении элемента ИСКЛЮЧАЮЩЕЕ ИЛИ «=1» (Рисунок 1, г) как раз и обозначает, что выделяется ситуация, когда на входах одна и только одна единица.

Эта операция аналогична операции арифметического суммирования, но, как и другие логические операции, без образования переноса. Поэтому она имеет другое название сумма по модулю 2 и обозначение ⊕, сходное с обозначением арифметического суммирования.

Стрелка Пирса и штрих Шеффера. Эти операции являются инверсиями операций дизъюнкции и конъюнкции и специального обозначения не имеют.

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

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

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

Например, в сложной логической функции аргументами являются X 1 ∨X 2 и .

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

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

Рисунок 1 – УГО логических элементов: а) Инвертор, б) ИЛИ, в) И, г) Исключающее ИЛИ, д) ИЛИ-НЕ, е) И-НЕ.

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

Рисунок 2 – Пример реализации сложной логической функции

Как видно из рисунка 2, логическое уравнение показывает, из каких ЛЭ и какими соединениями можно создать заданное логическое устройство.

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

1.2.3 Законы и тождества алгебры логики

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

1 Переместительный: X ∨ Y = Y ∨ X; X · Y = Y · X.

2 Cочетательный: X ∨ Y ∨ Z = (X ∨ Y) ∨ Z = X ∨(Y ∨ Z); X · Y · Z = (X · Y) · Z = X· (Y· Z).

3 Идемпотентности: X ∨ X = X; X · X = X.

4 Распределительный: (X ∨ Y)· Z = X· Z ∨ Y· Z.

5 Двойное отрицание: .

6 Закон двойственности (Правило де Моргана):

Для преобразования структурных формул применяется ряд тождеств:

X ∨ X · Y = X; X(X ∨ Y) = X - Правила поглощения.

X· Y ∨ X· = X, (X ∨ Y)·(X ∨ ) = X – Правила склеивания.

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

1 Отрицание - логическое действие первой ступени.

2 Конъюнкция - логическое действие второй ступени.

3 Дизъюнкция - логическое действие третьей ступени.

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

Основные действия над числами - это сложение и вычитание.

• 1. Сложение двоичных чисел
• 0 + 0 = 0 0+1 = 1 1+0=1
• 1 + 1=0 + единица переноса в старший разряд, т.е. 1 + 1=10 2 .

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

Пример 1. Сложить в двоичной системе

• 2. Вычитание двоичных чисел осуществляется в соответствии со следующими правилами:
• 0-0 = 0 1-0=1 1-1=0 10 2 -1 = 1

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

Операции над положительными и отрицательными числами

Распространенными формами представления чисел со знаками является их представление в прямом, обратном и дополнительном коде.

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

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

Пример 1. Представьте положительное число 127ю=1111111 2 в прямом коде: 0 1111111

Пример 2. Представьте отрицательное число - 1)0 в прямом коде:

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

Пример 3. Представьте отоинательное число - 1 ш в обратном коде:

Пример 4. Представьте отпиттятетткнпе хшг.тто - 1 77 10 в обратном коде:

Код модуля числа Обратный код числа

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

Пример 5. Представьте отрицательное число - 1ю в дополнительном коде: 11111111

Пример 6. Представьте отрицательное число -127ю в дополнительном коде:

Сложение чисел в дополнительном коде

Пример 1. Выполните следующую арифметическую операцию «-5+3».

Наши действия в этом случае таковы:

3. Осуществим сложение чисел.

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

Ответ: - 2, следовательно, все действия выполнены верно.

Пример 2. Выполните следующую арифметическую операцию «5 - 3». Выполняя операцию вычитания и представляя отрицательное число в дополнительном коде, можно операцию вычитания заменить сложением.

1. Представим числа в двоичном коде:

2. Отрицательное число следует представить в дополнительном коде. Для этого инвертируем все разряды числа, кроме знакового, и в младший разряд результата добавим единицу.

3. Осуществим сложение чисел.

• 4. Если результат получился положительным, то единицу переноса из знакового разряда отбрасывают.
• 5. Полученное число следует перевести в десятичную систему счисления. Ответ: + 2, следовательно, все действия выполнены верно.

Связь между алгеброй логики и двоичным кодированием

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

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

Так, например, предложение «8 - четное число» следует считать высказыванием, так как оно истинное. Предложение «Москва - столица Бельгии» тоже высказывание, так как оно ложное.

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

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

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

Из этого следует:

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

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

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

Простейшими логическими элементами компьютеров являются электронные схемы «И», «ИЛИ», «НЕ», «И-НЕ», «ИЛИ-HE». Каждый логический элемент имеет свое условное обозначение, которое выражает его логическую функцию, но не указывает на то, какая именно электронная схема в нем реализована. Это упрощает запись и понимание сложных логических схем.

Работу логических элементов, как и логических функций, описывают с помощью таблиц истинности. Таблица истинности - это таблица, в которую записаны значения логической функции для каждого из 2 П наборов аргументов на входе. Например, полная таблица истинности выражения с тремя переменными содержит 2 3 =8 строчек, если заданы только 6 из них, то можно найти 2 8 " 6 =2 2 =4 разных логических выражения, удовлетворяющие этим 6 строчкам. Для того чтобы полностью определить логическую функцию, достаточно перечислить либо все наборы, при которых эта функция принимает значения, равные 1, либо все наборы, при которых эта функция принимает значения, равные 0.

Элементарные логические функции и логические элементы

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

Функция отрицания - это логическая функция от одного аргумента, которая принимает значение 1, если аргумент равен 0, и принимает значение 0, если аргумент равен 1, и называется отрицанием (инверсией) или логической функцией «НЕ».

В обыденной речи мы часто пользуемся словом «НЕ», или словами «НЕВЕРНО, ЧТО», когда хотим что-то отрицать. Пусть, например, кто-то сказал: «На улице холодно». (Обозначим это высказывание А.) Если вы не согласны, вы скажете: «На улице НЕ холодно». Или: «Неверно, что на улице холодно». (Ваше высказывание обозначим В.) Нетрудно заметить, что значения истинности высказываний А и В находятся в определенной связи: если А истинно, то В ложно, и наоборот.

Запись логической функции «НЕ» можно обозначить как F = X, где черта над переменной - признак инверсии, либо как -iX. Логическая функция «НЕ» от одного аргумента описывается таблицей истинности (табл. 8).

Таблица 8. Таблица истинности для логической функции «НЕ»

Логический элемент «НЕ» (инвертор) реализует операцию отрицания. Если на входе этого логического элемента 0, то на выходе 1, а когда на входе 1, на выходе 0.

Условное обозначение инвертора на структурных схемах приведено на рис. 12.

Рис. 12.

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

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

Функцию логического умножения называют также конъюнкцией или функцией «И». Элементарная функция логического умножения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 9).

Таблица 9. Таблица истинности для логической функции «И»

При записи логической функции «И» возможны следующие варианты: F=X AY;

F=XY, где знаки «Л», «&», « » - знаки, обозначающие операцию логического умножения. Все варианты записи равнозначны.

Рис. 13.

Логический элемент «И» реализует конъюнкцию двух или более логических значений. Условное обозначение на структурных схемах конъюнкции с двумя входами представлено на рис. 13.

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

Функцию логического сложения называют также дизъюнкцией или логической функцией «ИЛИ». Сообщая: «Петров смотрит телевизор или смотрит в окно», мы имеем в виду, что хотя бы одно Петров делает. При этом Петров может одновременно смотреть телевизор и смотреть в окно. И в этом случае дизъюнкция будет истинна.

Элементарная дизъюнкция зависит от двух аргументов и описывается следующей таблицей истинности (табл. 10).

Таблица 10. Таблица истинности для логической функции «ИЛИ»

Рис. 14.

При записи логической функции «ИЛИ» возможны следующие варианты:

где знаки «V», «+» обозначают операцию логического сложения.

Логический элемент «ИЛИ» реализует дизъюнкцию двух или более логических значений. Когда хотя бы на одном входе элемента «ИЛИ» будет единица, на ее выходе также будет единица. Условное обозначение на структурных схемах логического элемента «ИЛИ» с двумя входами представлено на рис. 14.

Функция отрицания от логического умножения «И-НЕ» принимает значение 0, когда все аргументы равны 1, и 1 - во всех остальных случаях. Функция отрицания от логического умножения зависит от двух аргументов и описывается следующей таблицей истинности (табл. 11).

Таблица 11. Таблица истинности для функции отрицания от логического умножения

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

Рис. 15.

Логический элемент «И-НЕ» состоит из элемента «И» и инвертора и осуществляет отрицание результата функции И. Условное обозначение на структурных схемах логического элемента «И-НЕ» с двумя входами представлено на рис. 15.

Функция отрицания от логического сложения принимает значение 1, когда все аргументы равны 0, и значение 0 - во всех остальных случаях.

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

Таблица 12. Таблица истинности для функции отрицания от логического сложения

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

Рис. 16.

Логический элемент «ИЛИ-HE» состоит из элемента «ИЛИ» и инвертора и осуществляет отрицание результата логической функции «ИЛИ». Условное обозначение на структурных схемах логического элемента «ИЛИ-HE» с двумя входами представлено на рис. 16.

В сложных выражениях с использованием логических операций «И», «ИЛИ», «НЕ» сначала выполняется операция отрицания «НЕ», затем операция конъюнкции «И». В последнюю очередь выполняется операция дизъюнкции «ИЛИ». Для того чтобы изменить указанную последовательность выполнения операций, в выражениях следует использовать скобки. Кроме перечисленных функций, одной из важнейших операций является импликация (следование), которая обозначается -> и описывается соответствующей таблицей (табл. 13).

Таблица 13. Таблица истинности для функции импликации

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

Рассмотрим высказывание: «Если завтра будет хорошая погода, то я пойду гулять». Здесь А= Завтра будет хорошая погода и В= Я пойду гулять. Ясно, что человек окажется лжецом лишь в том случае, если погода действительно окажется хорошей, а гулять он не пойдет. Если же погода будет плохой, то независимо от того, пойдет он гулять или нет, во лжи его нельзя обвинить: обещание пойти гулять он давал лишь при условии, что погода будет хорошей.

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

Импликация заведомо истинна, если условие А ложно. Другими словами, из неверного условия может следовать все, что угодно. Например, высказывание «Если 2>3, то крокодилы летают» является истинным.

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

Таблица 14. Таблица истинности для функции эквиваленции

Например, сообщая: «Я получу паспорт тогда и только тогда, когда мне исполнится 14 лет», человек утверждает не только то, что после того, как ему исполнится 14 лет, он получит паспорт, но и то, что паспорт он сможет получить только после того, как ему исполнится 14 лет.

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

а эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию:

Каким выражением может быть F?

Построим таблицу истинности для всех предложенных в ответе выражений:

Вычислим логические выражения для четырех предложенных ответов. Видим, что совпали значения логических выражений в столбцах X v Y v Z и F, следовательно, правильный ответ 3.

Пример 2. Для какого из указанных значений X истинно высказывание

Видно, что высказывание представляет собой отрицание выражения ((Х>2) -> -> (Х>3)). Оно истинно, когда ((Х>2) -> (Х>3)) ложно. Импликация ложна в единственном случае: левое высказывание истинно (в нашем случае Х>2 истинно для Х=3 и Х=4), а правое ложно (это справедливо для Х=1, Х=2 и Х=3). Поэтому единственный вариант, когда эта импликация ложна (следовательно, исходное выражение истинно), - третий.

Основные законы алгебры логики

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

Таблица 15. Правила преобразования логических выражений

двойного отрицания	Отрицать отрицание какого-нибудь высказывания - то же, что утверждать это высказывание
переместительный (коммутативный)	А Л В = В Л А	А V В = В V А
сочетательный (ассоциативный)	(А Л В) Л С = А А (В Л С)	(A v В) v С = A v (В v С)
распределительный (дистрибутивный)	(А Л В) V С = (А V В) А (А VC)	Aa(BvC) = AaBvAa С
де Моргана	А В = А" + В отрицание логического произведения эквивалентно логической сумме отрицаний множителей	А + В = А -В отрицание логической суммы эквивалентно логическому произведению отрицаний слагаемых
поглощения	А А (А V В) = А	А V А А В = А
склеивания	(А V В) Л (-А V В) = В	(А А В) v (-А V В) = В
исключения третьего (операция переменной с ее инверсией)	для каждого высказывания имеются лишь две возможности: это высказывание либо истинно, либо ложно.

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

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

Под упрощением формулы, не содержащей операций импликации и эквивален- ции, понимают равносильное преобразование, приводящее к формуле, которая:

• - либо содержит по сравнению с исходной меньшее число операций конъюнкции и дизъюнкции и не содержит отрицаний неэлементарных формул;
• - либо содержит меньшее число вхождений переменных.

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

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

Пример 1.

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

Пример 2.

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

Пример 3. Какое логическое выражение равносильно выражению

По правилу де Моргана выполним преобразование

Пользуясь правилом двойного отрицания, в итоге получаем: , следовательно, правильный ответ 2.

Контрольные вопросы и задания

• 1. Расскажите о правилах двоичной арифметики.
• 2. Прямой, обратный и дополнительный коды числа - поясните разницу между ними.
• 3. Какая связь существует между двоичным кодированием и алгеброй логики?
• 4. Какие элементарные логические функции и логические элементы вы знаете? Приведите в качестве примеров их таблицы истинности.
• 5. Выполните сложение следующих чисел:

6. Выполните вычитание следующих чисел:

• 7. Опишите связь между алгеброй логики и двоичным кодированием. Приведите примеры логических высказываний.
• 8. Что такое таблица истинности?
• 9. Дайте характеристику логической функции НЕ. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции НЕ.
• 10. Дайте характеристику логической функции И. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции И.
• 11. Дайте характеристику логической функции ИЛИ. Приведите ее таблицу истинности. Придумайте несколько высказываний с использованием функции ИЛИ.
• 12. Расскажите о логической операции «импликация». Приведите ее таблицу истинности.
• 13. Какое логическое высказывание эквивалентно выражению -i (A v -iB д С)?

14. Дан фрагмент таблицы истинности выражения F.

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

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

Непозиционныесистемы для записи числа используют множество символов. Значение символа не зависит от местоположения его в числе(римская СС).

Позиционная система счисления– когда от позиции цифры в числе зависит ее вес(555 –единицы, десятки, сотни). Всякая позиционная СС характеризуетсяоснованием,т.е. количеством цифр, используемых для записи числа. За основание СС можно принять любое натуральное число.

10ая– использует 10 цифр → 0, 1… 9

2ая– 2 цифры → 0, 1

Люди предпочитают 10ую(это удобно, видимо потому, что с древних времен считали по пальцам).

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

Для ее реализации нужны устройства всего с двумя устойчивыми состояниями (есть ток, нет тока). Это надежнее, чем, например, 10ая;

возможно применение аппарата булевой алгебры;

двоичная арифметика проще десятичной;

представление информации с помощью 2-х состояний более надежно.

Недостаток: - быстрый рост разрядов.

В компьютере используются также 8аяи 16аясистемы.

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

При вводе информация кодируется, при выводе декодируется.

Обозначение цифр в 2ой системе:0, 1, 10, 11(3), 100(4), 101(5), 110(6), 111(7), 1000(8), 1001(9), 1010(10)и т.д.

Обозначение цифр в 8-ой системе: 0, 1, 2 … 7, 10(8), 11(9), 12(10)……17(15), 20(16), 21(17)и т.д.

Обозначение цифр в 16ой системе: 0, 1, 2 … 9, A(10), B(11),C(12) ... F(15), 10(16), 11(17) и т. д.

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

Aq=an-1qn-1+an-2qn-2+…+a0q0 , где

A– само число;

q– основание системы счисления;

ai– цифры, принадлежащие алфавиту данной системы счисления;

n– число целых разрядов числа.

Пусть в десятичной системе задано число37510.

Каждая позиция, занимаемая цифрами, называется разрядом числа.Разряды имеют названия иномера:разряд единиц (0), разряд десятков (1), разряд сотен (2). Названия определяютвес (012). Число в позиционной системе счисления представляет собой сумму степеней основания, умноженную на соответствующий коэффициент, который должен быть одной из цифр данной системы счисления. Достаточно просуммировать веса единичных разрядов.

37510=5*100+7*101+3*102 = 5+70+300=375

Это называется разложением числа по степеням основания.

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

1011012=1*20+0*21+1*22+1*23+0*24+1*25=1+0+4+8+0+32=4510

101102=0*20+1*21+1*22+0*23+1*24=0+2+4+0+16=2210

1000012=1*20+0*21+0*22+0*23+0*24+1*25=1+32=3310

178=1*81+7*80= 8+1=1510

77648= 7*83+7*82+6*81+4*80 = 3584+448+48+4 =408410

1716= 1*161+7*160= 16+7 = 2310

3AF16=3*162+10*161+15*160=768+160+15=94310

1A16= 1*161+10*160= 16+10 = 2610

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

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

Представление информации в компьютере .

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

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

Непозиционные системы для записи числа используют множество символов. Значение символа не зависит от местоположения его в числе(римская СС ).

Позиционная система счисления – когда от позиции цифры в числе зависит ее вес(555 –единицы, десятки, сотни). Всякая позиционная СС характеризуется основанием , т.е. количеством цифр, используемых для записи числа. За основание СС можно принять любое натуральное число.

10 ая – использует 10 цифр → 0, 1… 9

2 ая – 2 цифры → 0, 1

Люди предпочитают 10 ую (это удобно, видимо потому, что с древних времен считали по пальцам).

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

Для ее реализации нужны устройства всего с двумя устойчивыми состояниями (есть ток, нет тока). Это надежнее, чем, например, 10 ая ;

возможно применение аппарата булевой алгебры;

двоичная арифметика проще десятичной;

представление информации с помощью 2-х состояний более надежно.

Недостаток : - быстрый рост разрядов.

В компьютере используются также 8 ая и 16 ая системы.

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

При вводе информация кодируется, при выводе декодируется.

Обозначение цифр в 2 ой системе: 0, 1, 10, 11(3), 100(4), 101(5), 110(6), 111(7), 1000(8), 1001(9), 1010(10) и т.д.

Обозначение цифр в 8-ой системе: 0, 1, 2 … 7, 10(8), 11(9), 12(10)……17(15), 20(16), 21(17) и т.д.

Обозначение цифр в 16 ой системе: 0, 1, 2 … 9, A (10), B (11), C (12) ... F (15), 10(16), 11(17) и т. д.

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

A q =a n-1 q n-1 +a n-2 q n-2+…+ a 0 q 0 , где

A – само число;

q – основание системы счисления;

a i – цифры, принадлежащие алфавиту данной системы счисления;

n – число целых разрядов числа.

Пусть в десятичной системе задано число 375 10 .

Каждая позиция, занимаемая цифрами, называется разрядом числа . Разряды имеют названия и номера: разряд единиц (0), разряд десятков (1), разряд сотен (2). Названия определяют вес (012) . Число в позиционной системе счисления представляет собой сумму степеней основания, умноженную на соответствующий коэффициент, который должен быть одной из цифр данной системы счисления. Достаточно просуммировать веса единичных разрядов.

А 10 =375

375 10 =5*10 0 +7*10 1 +3*10 2 = 5+70+300=375

Это называется разложением числа по степеням основания.

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

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

10110 2 =0*2 0 +1*2 1 +1*2 2 +0*2 3 +1*2 4 =0+2+4+0+16=22 10

100001 2 =1*2 0 +0*2 1 +0*2 2 +0*2 3 +0*2 4 +1*2 5 =1+32=33 10

17 8 =1*8 1 +7*8 0 = 8+1=15 10

7764 8 = 7*8 3 +7*8 2 +6*8 1 +4*8 0 = 3584+448+48+4 =4084 10

17 16 = 1*16 1 +7*16 0 = 16+7 = 23 10

3 AF 16 =3*16 2 +10*16 1 +15*16 0 =768+160+15=943 10

1 A 16 = 1*16 1 +10*16 0 = 16+10 = 26 10

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

33 10 = ? 2

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

33 10 = 100001 2

Двоичная система счисления является стандартом при конструировании компьютеров.

Десятичная система счисления используется для организации ввода / вывода информации. Двоичная СС – для организации машинных операций по преобразованию информации. 8-миричная и 16-тиричная системы используются для более короткой и удобной записи, т. к. требует меньше разрядов(для записи программ в машинных кодах).

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

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

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

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

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

Системы счисления, в которых значение знака не зависит от того места, которое он занимает в числе, называются непозиционными. Наиболее известным примером непозиционной системы счисления является римская. В этой системе используется 7 знаков (I, V, X, L, С, D, М), которые соответствуют следующим величинам:

I(1) V(5) X(10) L(50) C(100) D(500) M(IOOO)

Примеры: III(три), LIХ(пятьдесят девять), DLV(пятьсот пятьдесят пять).

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

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

В позиционной системе счисления любое число можно представить в виде:

Основание системы счисления N показывает, во сколько раз “вес” i- го разряда больше (i – 1) разряда. Целая часть числа отделяется от дробной части точкой (запятой).

Пример 1. А 10 = 37,25. В соответствии с формулой (1) это число формируется из цифр с весами разрядов

Теоретически наиболее экономичной системой счисления является система счисления с основанием е = 2,71828…, находящимися между числами 2 и 3.

Во всех современных ЭВМ для представления числовой информации используется двоичная система счисления. Это обусловлено:

· более простой реализацией алгоритмов выполнения арифметических и логических операций;

· более надежной физической реализацией основных функций, так как они имеют всего два состояния (0 и 1);

· экономичностью аппаратурной реализации всех схем ЭВМ.

При N =2 число различных цифр, используемых для записи чисел, ограниченно множеством из двух цифр (нуль и единица). Кроме двоичной системы счисления широкое распространение получили и производные системы:

· двоичная - {0,1};

· десятичная, точнее двоично-десятичное представление десятичных чисел, - {0,1,2,…,9};

· шестнадцатеричная - {0,1,…,9,A,B,C,D,E,F}. Здесь шестнадцатеричная цифра А обозначает число 10, В – число 11,…, F – число 15;

· восьмеричная (от слова «восьмерик») - {0,1,2,3,4,5,6,7}. Она широко используется для специализированных ЭВМ.

Таблица 1 – Представление чисел в различных системах счисления