Лекции по дисциплине «Информатика» (стр. 2 )

f3(x1,x2)=x1, f5(x1,x2)=x2, f10(x1,x2)=x2 и f12(x1,x2)=x1.

Рассмотрим часто встречающиеся ПФ. Функция f1(x1,x2) реализует операцию конъюнкции или логического произведения. Как видим из табл.2.3 , функция f1(x1,x2) равна 1, когда и x1 и x2 равны 1. Конъюнкция обозначается как

f1(x1,x2)=x1 & x2 = x1 Ù x2 = x1 x2 (читается x1 и x2).

Функция f7(x1,x2) реализует операцию дизъюнкцию или логического сложения. Функция равна 1, когда или x1 или x2 равны 1. Дизъюнкция обозначается как

f7(x1,x2)=x1 Ú x2.

Функция f14(x1,x2) реализует операцию отрицания конъюнкции. Из табл.2.3 видно, что когда конъюнкция f1(x1,x1) равна 0, то функция f14(x1,x2) равна 1, а если f1(x1, x2) равна1, то f14(x1,x2) равна 0, т. е. f14(x1,x2)=f1(x1,x2). Эта операция получила название “штрих Шеффера” и обозначается различными способами:

 

Функция f8(x1, x2) реализует операцию отрицания дизъюнкции. По аналогии с функцией отрицания конъюнкции, из табл.2.3 видно, что f8(x1, x2)=f7(x1, x2). Эта операция также получила отдельное название – “стрелка Пирса” и обозначается следующим образом:

 

Функция f6(x1, x2) реализует операцию логической неравнозначности или еще ее называют суммой по модулю два. ПФ равна 1, если аргументы x1 и x2 не равны между собой.

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

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

- дизъюнкция, конъюнкция и отрицание;

- отрицание конъюнкции;

- отрицание дизъюнкции и другие.

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

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

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

Формулы для отрицания:

Формулы для дизъюнкции:

Формулы для конъюнкции:

 

Правило действия со скобками:

 

Операция поглощения:

 

Операция склеивания:

Формулы де Моргана:

 

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

Пример 2.2. Выражение

 

можно упростить следующим образом:

 

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

Рассмотрим некоторые логические элементы с одним и двумя входами, реализующие ПФ от одного и двух аргументов.

Логический элемент НЕ (инвертор). Инвертор реализует ПФ НЕ. В схемах инвертор изображается следующим образом (рис.2.4).

 

Рис.2.4. Графическое обозначение

логического элемента НЕ

 

Рис.2.5. Диаграммы сигналов, Рис.2.6. Временные диаграммы

соответствующих логическим сигналов на входе и выходе

значениям “0” и”1” элемента НЕ

На вход инвертора подается цифровой сигнал, величина напряжения которого соответствует значению аргумента ПФ. Например, если x=1, то это напряжение составляет +5 В, а если х=0 , то 0 В (рис.2.5). На выходе инвертора получается сигнал, представляющий значение функции отрицания НЕ, т. е. значение, обратное входному (рис.2.6) : y=1 (на выходе +5 В, если на входе 0 В) или y=0 (на выходе 0 В, если на входе +5 В). Нужно сказать, что на временной диаграмме инвертора допущена некоторая условность: судя по диаграмме, переключение цифрового сигнала происходит мгновенно, в действительности же любой физический процесс в логических элементах протекает за определенное время.

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

 

Рис.2.7. Графическое обозначение

логического элемента И

Рис.2.8. Временные диаграммы сигналов на входе и выходе логического элемента И

Логический элемент ИЛИ. Этот элемент реализует ПФ дизъюнкции или логического сложения. Иногда логический элемент ИЛИ называют дизъюнктором или схемой сборки: сигнал, соответствующий уровню логической единицы, возникает на выходе, если хотя бы на один из входов придет сигнал логической единицы. На рис.2.9 приведено схематическое представление элемента, а на рис.2.10 - временная диаграмма.

 

Рис.2.9. Графическое обозначение

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

Рис.2.10. Временные диаграммы

сигналов на входе и выходе

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

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

 

Рис.2.11. Последовательное Рис.2.12. Графическое

соединение элементов И и НЕ обозначение элемента И-НЕ

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

 

Рис.2.13. Последовательное Рис.2.14. Графическое

соединение элементов ИЛИ и НЕ обозначение элемента ИЛИ-НЕ

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

Аналитическая запись переключательной функции.

Построение схем на элементах заданного базиса

Для аналитического представления ПФ используют правило ее записи по единицам:

- в таблице истинности выбирают все наборы, на которых ПФ равна единице;

- выписывают произведения аргументов, соответствующих этим наборам. При этом, если в этом наборе аргумент равен 1, то он вписывается в произведение без изменения, если же он равен 0, то он вписывается со знаком отрицания;

- все полученные произведения соединяются знаком дизъюнкции.

Пример 2.3. Построить схему сумматора по модулю два на элементах И, ИЛИ, НЕ. Таблица истинности для ПФ f6(x1,x2) логической неравнозначности представлена в табл.2.3.

В соответствии с правилом записи ПФ по единицам получим:

Тогда схема сумматора по модулю два будет иметь вид (рис.2.15):

 

Рис. 2.15. Схема сумматора по модулю два на элементах И, ИЛИ, НЕ

Можно построить схему сумматора только на элементах И-НЕ. Для этого, используя формулы де Моргана, преобразуем выражение f6(x1,x2) следующим образом:

 

По этому выражению построим схему сумматора по модулю два на элементах И-НЕ (рис.2.16):

 

Рис.2.16. Схема сумматора по модулю два на элементах И-НЕ

Сумматор по модулю два можно построить и на элементах ИЛИ-НЕ:

 

Схема представлена на рис.2.17.

 

Рис.2.17. Схема сумматора по модулю два на элементах ИЛИ-НЕ

.  Раздел 3

.  Арифметические основы информатики

Лекция 4. Системы счисления

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

- возможность представления любого числа в рассматриваемом, заранее назначенном диапазоне величин;

- единственность представления (любая комбинация символов соответствует одному и только одному числу);

- простоту операций с числами.

Все системы счисления разделяются на два больших класса – непозиционные и позиционные.

В непозиционной системе счисления значения символов не зависят от положения в числе. Для образования таких систем используют, в основном, операции сложения и вычитания. Например, система с одним символом-палочкой встречалась у многих народов. Для изображения числа в этой системе нужно записать определенное множество палочек, равное данному числу. Эта система не эффективна, т. к. запись числа получается длинной. Другим примером непозиционной системы счисления является римская система, использующая набор следующих символов: I, V, X, L, C, D и т. д. В этой системе имеются отклонения от правила независимости значения цифры от положения в числе. В числах IV и VI символ I принимает соответственно значения –1 и +1.

В позиционной системе счисления значение каждой цифры изменяется от ее положения (или позиции) в числе. Например, если взять число в привычной для нас десятичной системе: 903,87 – эта последовательность цифр представляет собой не что иное, как сокращенную запись выражения:

903,87=9´102+0´101+3´100+8´10-1+7´10-2.

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

Количество различных цифр, применяемых в позиционной системе счисления, называется ее основанием (для десятичной системы - от 0 до 9- десять ).

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

A(p) = an-1 an-2 … a1 a0, a-1 … a-m

в р-ичной системе означает число

 

где ai - цифры системы счисления, n и m – число целых и дробных разрядов числа.

Обычно в качестве двух младших цифр во всех системах счисления используются знаки 0 и 1. При этом основание системы счисления р записывается в виде последовательности цифр 10 (это не десять, а один ноль!). В скобках указывают систему счисления, в которой записывается число, т. е 10(р).

В вычислительной технике широко используются двоичная, восьмеричная и шестнадцатеричная системы счисления. При этом для представления чисел в двоичной системе используются две цифры 0 и 1, в восьмеричной – 0, 1,…,7 и в шестнадцатеричной – цифры 0, 1,…,9 и знаки A, B, C, D, E, F (часто вместо этих знаков записывают символы

).

Пример 3.1. В качестве примера возьмем двоичное число 1001,1101(2). В соответствии с равенством (3.1 ) двоичное число можно определить следующим образом:

1001,1101(2)=1´23+0´22+0´21+1´20+1´2-1+1´2-2 + 0´2-3 + 1´2-4.

Если по правилам десятичной арифметики выполнить действия в правой части приведенного равенства, то можно получить значение этого числа в десятичной системе счисления (десятичный эквивалент двоичного числа):

1001, 1001(2)=9,8125(10) .

В табл. 3.1 приведены эквиваленты десятичных чисел в двоичной, восьмеричной и шестнадцатеричной системах счисления.

Таблица 3.1

Десятичная	Эквиваленты в системах счисления	Десятичная	Эквиваленты в системах счисления
цифра	p=2	p=8	p=16	цифра	p=2	p=8	p=16
0	0	0	0	8	1000	10	8
1	1	1	1	9	1001	11	9
2	10	2	2	10	1010	12	A
3	11	3	3	11	1011	13	B
4	100	4	4	12	1100	14	C
5	101	5	5	13	1101	15	D
6	110	6	6	14	1110	16	E
7	111	7	7	15	1111	17	F

Для записи одного и того же значения в различных системах счисления требуется разное число позиций или разрядов. Например, 96(10)=140(8)=1100000(2). Чем меньше основание системы счисления, тем больше длина числа (длина разрядной сетки). Если длина разрядной сетки задана, то это ограничивает максимальное по абсолютному значению число, которое можно записать.

Пусть длина разрядной сетки равна числу N. Тогда

A (p )max = pN - 1.

Если же задано максимальное абсолютное значение числа, то длина разрядной сетки N равна:

N=logP (A(P)max+1).

Интервал числовой оси, заключенный между максимальным и минимальными числами, называется диапазоном представленияÌ (ДП) чисел в данной системе счисления для заданной длины разрядной сетки: