23 Что такое транслятор, компилятор, интерпретатор.

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

Трансляторы реализуются в виде компиляторов или интерпретаторов. С точки зрения выполнения работы компилятор и интерпретатор существенно различаются.

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

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

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

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

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

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

24 Алгебра логики. Что такое логическая формула.

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

Основные объекты логики – предложения, которые могут быть либо истинными, либо ложными.

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

Л - И

0 - 1

false - true

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

Х1 Х2 . . . Хn	f(X1, X2, …Xn)
Набор значений аргументов	Значение функции (0 или 1)

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

Определение логической формулы:

1. Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") - формулы.

2. Если А и В - формулы, то , (А

· В), (А v В), (А ® B), (А « В) - формулы.

3. Никаких других формул в алгебре логики нет.

В п. 1 определены элементарные формулы; в п. 2 даны правила образования из любых данных формул новых формул.

В качестве примера рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B) ® C; такая же формула соответствует высказыванию "если Игорь знает английский или японский язык, то он получит место переводчика".

Как показывает анализ формулы (A v B) ® C , при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях - значение "ложь" (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми.

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

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

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

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

25. Основные логические устройства компьютера. (Сумматор, триггер).

Основные логические устройства компьютера (сумматор, регистр).

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

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

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

Логический элемент НЕ. На вход А логического элемента последовательно подаются два сигнала, на выходе получается последовательность из двух сигналов,

значения которых определяются в соответствии с таблицей истинности логического отрицания (рис. 13).

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

При сложении двоичных чисел образуется сумма в данном разряде, при этом возможен перенос в старший разряд. Обозначим слагаемые (А, В), перенос (Р) и сумму (S). Построим таблицу сложения одноразрядных двоичных чисел с учетом переноса в старший разряд (табл. 4).

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

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

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

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

Для построения триггера достаточно двух логических элементов «ИЛИ» и двух элементов «НЕ».

В обычном состоянии на входы триггера подан сигнал «О», и триггер хранит «О». Для записи «1» на вход S (установочный) подается сигнал «1». При последовательном рассмотрении прохождения сигнала по схеме видно, что триггер переходит в это состояние и будет устойчиво находиться в нем и после того, как сигнал на входе S исчезнет. Триггер запомнил «1», т. е. с выхода триггера Q можно считать «1».

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

Что такое триггер.

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

Термин «триггер» происходит от английского слова trigger – защелка, спусковой крючок. Для обозначения этой схемы в английском языке чаще употребляется термин flip – flop, что в переводе означает «хлопанье». Это звукоподражательное название электронной схемы указывает на ее способность почти мгновенно переходить из одного электрического состояния в другое и наоборот.

Самый распространенный тип триггера – так называемый RS – триггер ( S и R соответственно от английских слов set – установка и reset – сброс). Условное обозначение триггера – на рис.6. Он имеет два симметричных входа S и R и два симметричных выхода Q и , причем выходной сигнал Q является логическим отрицанием сигнала. На каждый из двух входов S и R могут подаваться входные сигналы в виде кратковременных импульсов. Наличие импульса на входе будем считать единицей, а его отсутствие – нулем.

На рис. 7 показана реализация триггера с помощью вентилей ИЛИ-НЕ, в таблице 6 – соответствующая таблица истинности.

Таблица 6

S	R	Q
0	0	Запрещено
0	1	1	0
1	0	0	1
1	1	Хранение бита

Проанализируем возможные комбинации значений входов R и S триггера, используя его схему и таблицу истинности схемы ИЛИ-НЕ (см. табл. 5).

Если на входы триггера подать S = «1», R = «0», то (независимо от состояния) на выходе Q верхнего вентиля появится «0». После этого на входах нижнего вентиля окажется R = «0», Q = «0» и выход станет равным «1».

Точно так же при подаче «0» на вход S и «1» на вход R на выходе появится «0», а на Q – «1».

Если на входы S и R подана логическая «1», то состояние Q и не меняется.

Подача на оба входа R и S логического «0» может привести к неоднозначному результату, поэтому эта комбинация входных сигналов запрещена.

Поскольку один триггер может запомнить только один разряд двоичного кода, то для запоминания байта нужно 8 триггеров, для запоминания килобайта соответственно 8*210=8192 триггеров. Современные микросхемы памяти содержат миллионы триггеров.

Что такое сумматор.

Сумматор – это электронная логическая схема, выполняющая суммирование двоичных чисел.

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

В зависимости от системы счисления различают:

• двоичные;

• двоично-десятичные (в общем случае двоично-кодированные);

• десятичные;

• прочие (например, амплитудные).

По количеству одновременно обрабатываемых разрядов складываемых чисел:

• одноразрядные,

• многоразрядные.

Условное обозначение одноразрядного сумматора приведено на рис. 8.

При сложении чисел А и В в одном i –м разряде приходится иметь дело с тремя цифрами:

1. цифра а_iпервого слагаемого;

2. цифра b_iвторого слагаемого;

3. перенос р_i-1 из младшего разряда.

В результате сложения получаются две цифры:

1) цифра с_iдля суммы;

2) перенос рi из данного разряда в старший.

В реальных электронных схемах сумматор изображается так.

Таким образом, одноразрядный двоичный сумматор есть устройство с тремя входами и двумя выходами.

Обозначением полного двоичного сумматора служат буквы SM. Работу его отражает таблица истинности – табл.7.

Таблица 7

Входы				Выходы
Первое слагаемое	Второе слагаемое	Перенос	Сумма		Перенос
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

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

Дополнительно, для сравнения - схема полусумматрора:

26. Схемы И, ИЛИ, НЕ, И-НЕ, ИЛИ-НЕ.

Схема И реализует конъюнкцию двух или более логических значений.

Условное обозначение на структурных схемах схемы И с двумя входами представлено на рис.1, а таблица истинности в таблице 1.

Таблица 1

х	у	х * у
0	0	0
0	1	0
1	0	0
1	1	1

Единица на выходе схемы И будет тогда и только тогда, когда на всех входах будут единицы. Когда хотя бы на одном входе будет ноль, на выходе также будет ноль.

Связь между выходом z этой схемы и входами х и у описывается отношением z = х * у (читается как «х и у»).

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

Схема ИЛИ реализует дизъюнкцию двух или более логических значений.

Когда хотя бы на одном входе схемы ИЛИ будет единица, на ее выходе также будет единица.

Условное обозначение схемы ИЛИ знак «1». Связь между выходом z этой схемы и входами х и у описывается соотношением z = х + у (читается как «х или у»). Рис.2 и таблица 2.

Таблица 2

х	у	х + у
0	0	0
0	1	1
1	0	1
1	1	1

Схема НЕ (инвертор) реализует операцию отрицания.

Связь между входом х этой схемы и выходом z можно записать соотношением z = ,

где читается как «не х» или «инверсия х».

Если на входе схемы 0, то на выходе 1. Когда на входе 1, на выходе 0. Условное обозначение инвертора - на рис.3, а таблица истинности – в таблице 3

Таблица 3

х
0	1
1	0

Схема И-НЕ состоит из элемента И и инвертора и осуществляет отрицание результата схемы И.

Связь между выходом z и входами х и у схемы записывают следующим образом:

z = , гдечитается как «инверсия х и у». Условное обозначение схемы И-НЕ представлено на рис. 4, а таблица истинности схемы И-НЕ – в таблице 4.

Таблица 4

х	у
0	0	1
0	1	1
1	0	1
1	1	0

Схема ИЛИ-НЕ состоит из элемента ИЛИ и инвертора и осуществляет отрицание результата схемы ИЛИ.

Связь между выходом z и входами х и у схемы записывают следующим образом:

z = , гдечитается как «инверсия х или у».

Таблица 5

х	у
0	0	1
0	1	0
1	0	0
1	1	0

Условное обозначение схемы ИЛИ-НЕ представлено на рис. 5, а таблица истинности схемы ИЛИ-НЕ – в таблице 5.