Преобразование двоичных чисел в десятичную систему счисления. 2 страница

III, Существует такое число, обозначаемое знаком 0 (нуль), при сложении которого с любым числом «а» получается в сумме то же число «а», а при перемножении его (то есть нуля) с любым числом, получается в произведении 0.

Отсюда формулы:

8)

9)

Существует еще число, обозначаемое знаком 1 и называемое единицей, при перемножении с которым любого числа «а» получается в произведении то же число:

10)

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

2.Алгебра высказываний

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

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

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

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

Условимся истинность высказывания обозначать единицей, а ложность — нулем.

Тогда каждое высказывание может быть приравнено числам 1 или 0, которые являются мерами истинности высказывания «а».

Соответственно, для любого высказывания «а»: либо а = 1, либо а = 0.

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

если: или а = 1 или b = 1, что согласно с обычной арифметикой:

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

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

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

Итак, «сумма» двух высказываний считается истинной, если истинно или а, или b, или оба слагаемых. Таким образом, слово «или» обозначается знаком +.

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

Это определение произведения соответствует обычной арифметике:

Первое равенство читается так: если и а и b истинны, то произведение: истинно. Значит, знак умножения «•» заменяет союз «и».

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

Таблица 5.Таблица умножения алгебры высказываний

a
b
a*b

Таблица 6. Таблица сложения алгебры высказываний

a
b
a+b

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

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

Таблица 7. Коммутативность алгебры высказываний

a	b	a + b	b + a	a * b	b * a

Меры истинности двух сумм: а + b и b+a (третий и четвертый столбцы) при всех возможных комбинациях мер истинности а и b совпадают, — следовательно, а + b и b+a в отношении истинности всегда одинаковы («равны»). То же имеем для произведений: а * b и b* a (пятый и шестой столбцы таблицы).

3.Некоторые особенности алгебры высказываний

1.В алгебре высказываний вводится новое действие: отрицание данного высказывания.

Определение. Для каждого высказывания «а» существует его отрицание «не-а».

-если высказывание «а» истинно (1), то его отрицание «не-а» ложно (0);

-если «а» ложно, то его отрицание «не-а» истинно (1).

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

11) а + не-а=1,

12) а * не-а = 0,

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

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

Вот некоторые примеры:

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

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

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

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

4.Физическое истолкование сложения и умножения в алгебре логики

Сложение и умножение по правилам алгебры логики имеют вполне конкретное истолкование.

Оно иллюстрируются на физических и технических явлениях, простейшее из которых — действие выключателей.

Предположим, что ток идет из какого-нибудь источника к потребителю через выключатель S.

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

Рис. 2

1.Имеются два выключателя S и Т на параллельных проводах.

Действие такой параллельной комбинации выключателей обозначим через S + T. Такая комбинация может дать замыкание или размыкание цепи. Возможны следующие варианты:

-если S и Т оба включены, то S + T замыкает цепь,

Рис.3

-если S включен а Т выключен, то S + T замыкает цепь,

Рис.4

-если S выключен а Т включен, то S + T замыкает цепь,

-если S выключен и Т выключен, то S + T размыкает цепь.

Рис.5

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

Таблица 8.

S
T
S+T

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

2.Пусть выключатели S и T соединены последовательно.

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

Рис.6

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

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

Таблица 9

S
T
ST

Эта таблица совпадает с таблицей меры истинности произведения двух высказываний.

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

Это открытие, сделанное в 1910 году физиком Эренфестом, стало ключевым при построении вычислительных машин.

5.Машина Тьюринга

Следующий шаг в обосновании вычислительной машины сделал Тьюринг в 1936 г. Он предложил описание «машины» простого рода, способной напечатать двоичное или десятичное разложение любого «определимого» (или, иначе, «вычислимого») действительного числа, такого, как числа и π.

Машина Тьюринга характеризуется тремя основными чертами:

1) Она имеет конечное множество S внутренних состояний определенных Тьюрингом как «состояния ума».

2) Она может «считывать» и «записывать» конечное множество А символов (ее алфавит, или словарь).

3) Ее поведение контролируется лентой, состоящей из бесконечного числа клеток и передвигаемой шагами мимо определенного места — считывающей головки.

Появление данного символа перед считывающей головкой влечет за собой три события:

1) внутреннее состояние заменяется новым состоянием

2) знак заменяется новым знаком ,

3) лента передвигается на одну позицию вперед или назад (или остается без движения), в зависимости от значения некоторой третьей функции χ равного +l, —1 или 0.

Коротко, поведение машины Тьюринга M=[S, A, f, ψ, χ] определяется двумя конечными множествами S и А и тремя функциями на множестве SxA, с областями значений S, A и {±1, 0} соответственно.

Таким образом, машина Тьюринга представляет собой механический автомат; она приводится в действие любой программой, состоящей из конечной цепочки 2r+1 символов, заранее записанных на ленте:

Эта цепочка называется программой, остальные клетки можно полагать пустыми или, что тоже, занятыми знаком - символом пустого множества.

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

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

Биркгоф отмечал, что многое указывает на то, что значительная часть нашего математического мышления допускает именно такое моделирование.

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

6 .Модель фон Неймана

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

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

Следовательно, вычислительной машине надо быть не только арифметической, но и логической машиной.

Нейман (1903-1957) предложил простую, но эффективную модель компьютера, включающую всего два устройства: центральный процессор и память.

Модель Неймана предполагает последовательное расположение команд в программе:

Рис 7.

К ее особенностям относятся:

1) хранимая программа: программы вместе с данными хранятся в памяти;

2) линейная память: линейное пространство адресов, которым присваиваются порядковые номера 0, 1, 2, …;

3) последовательное выполнение программы: каждая программа выполняется последовательно, начиная с самой первой команды, если нет специальных указаний. Для изменения этой последовательности с помощью команды перехода указывается адрес начала перехода;

4) отсутствие различий между данными и командами;

5) отсутствие различий в семантике данных.

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

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

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

Такое разбиение на элементарные операции называется «программа».

Таким образом, память одновременно содержит «данные», «результаты» и «операторы».

Функции центрального процессора: выполнение операторов над данными и управление порядком следования операторов.

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

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

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

7. Операторы машинного языка

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

Команды процессора можно разделить на четыре категории:

-вычислительные команды (сложение чисел, логическое «и»);

-команды обмена данными между памятью и процессором;

-команды проверки условия, чтобы при необходимости изменить порядок команд обмена;

-команды ввода-вывода.

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

Принцип работы ЭВМ становится ясным после рассмотрения алгоритма и схемы работы УУ. Номер пункта соответствует номеру в кружочке на рисунке 8.

1. В память ЭВМ загружена программа. Счётчик адреса команд (САК) содержит адрес первой команды.

2. Процессор (ЦП) считывает команду из оперативной памяти (ОП), используя адрес из САК. Команда поступает в регистр команд.

Арифметическое и логическое устройство

Регистр команд

Код операции

Код адреса

Блок управления операциями

Внешние устройства

Память (ОЗУ)

Счетчик адреса

³

⁴

⁷

¹

²

⁶

⁵

⁷

Рис.8

3. Из прочитанной команды выделяется код операции (КОП) и адрес ОП, по которым хранятся операнды команды. КОП поступает в блок управления операциями ЭВМ.

4. Продолжается чтение команды (данных), если это необходимо. Длина команды прибавляется к содержимому САК. Теперь САК содержит адрес команды, которая будет выполняться на следующем шаге.

5. По адресам операндов, выделенных из текущей команды, считываются данные из ОЗУ и поступают в АЛУ.

6. КОП передаётся в АЛУ, где производятся вычисления.

7. Полученный результат записывается в память ЭВМ. Длина команды прибавляется к содержимому САК. Теперь САК содержит адрес команды, которая будет выполняться на следующем шаге.

8.Структурное программирование

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

S

В

Рис 9.

Блок-схема – это ориентированная сеть, вершины которой могут быть только одного из трех типов базовых алгоритмических структур, показанных на рисунке 9.

На основе этих структур формируются основные алгоритмические конструкции:

(1)

S1

В

(2) (3)

S1

S2

S1

S2

В

В

S1

(4) (5)

В

S1

Рис. 10

Структурная блок-схема – это блок-схема, составленная как композиция из пяти элементарных алгоритмических конструкций, показанных на рисунке 10. Первая из них называется «композиция», вторая и пятая – «итерация», а третья и четвертая «выбор».

Структурным программированием называется процесс разработки алгоритмов на основе структурных блок схем.

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

9.Алгоритмическая система обработки данных

Вычислительную машину следует рассматривать как элемент алгоритмической системы обработки данных.

Содержательное определение алгоритмической системы предполагает:

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

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

- наличие множества результатов работы алгоритма.

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

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

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

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

Рассмотрим работу алгоритмической системы более детально.

Чтобы выполнить обработку информации, надо осуществить применение рассматриваемой функции f к некоторому данному (возможно, сложному),которое принадлежит множеству D, а f – произвольная функция, которую надо «вычислить»: перевод с русского на английский, нахождение среднего или максимума, вычисление параметров системы, преобразование символьных выражений и т.д. (Рис. 11).

D (данные)

К (критерий)

R (результат)

Входной код

Выходной код

(алгоритм)

(физическое представление структуры)

(физическое представление структуры данных)

Рис.11

Чтобы «промоделировать» f, необходимо располагать тремя физическими представлениями:

- D', физическим представлением множества данных D;

- R', физическим представлением множества результатов R;

- f ', физическим представлением функции обработки f, которое должно быть преобразованием или последовательностью преобразований, оперирующих над D' и дающих в результате элемент R';

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

Чтобы выполнить обработку информации и интерпретировать ее результат, необходимо располагать, кроме того, двумя кодами представлений ϕ и ψ:

- ϕ позволяет представить данное из D (абстрактное) с помощью элемента из D' (физического): это входной код;

- ψ позволяет интерпретировать элемент из R', результат автоматической обработки, в качестве представления результата, принадлежащего R: это выходной код.

Программа обработки информации, реализуемой функцией f, является, таким образом, данным, составленным из элементов, физически представимых (конструируемых) множеств D' и R', кодов ϕ и ψ и автоматизируемого преобразования f ', таких, что для всякого данного х (принадлежащего D) имеет место f(x) = ψ (f'(ϕ (x))).

Если ЭВМ позволяет получить такие физические представления, то решение задачи допускает автоматизацию вычислений.

10.Вопросы для самопроверки

1.Составьте таблицу ассоциативности алгебры высказываний.

2.Рассмотрите принципы структурного программирования с позиций семиотики.

3.Определите понятие «неструктурированное программирование»

4.Рассмотрите алгоритмическую систему с исполнителем, отличным от ЭВМ.

6.Технические средства реализации информационных процессов

1.Принцип функциональной модульности

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

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

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

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

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

Этот подход к проектированию, естественно, приводит к иерархии вложенных модулей.

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

Дата добавления: 2014-12-27