Алгебра Дж. Буля и ее применение в теории и практике информатики

Алгебра Дж. Буля и ее применение в теории и практике информатики

Информация, с которой имеют дело различного рода автома-тизированные информационные системы, обычно называется дан-ными., а сами такие системы — автоматизированными системами обработки данных (АСОД). Различают исходные (входные), про-межуточные и выходные данные.

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

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

Прежде всего различают двоичное и двоично-десятичное пред-ставления чисел. В двоичном представлении используется двоич-ная система счисления с фиксированным числом двоичных раз-рядов (чаще всего 32 или, для малых ЭВМ, 16 разрядов, включая разряд для представления знака числа). Если нулем обозначать плюс, а единицей — минус, то 1 010 означает целое число +(2³+2^l)= + l0, а 10 001 100— число— (2³ + 2²) = —12 (для простоты взято 8-разрядное представление). Заметим, что знак числа в машинном представлении часто оказывается удобным ставить не в начале, а в конце числа.

В случае вещественных чисел (а фактически, с учетом огра-ниченной разрядности, дробных двоичных чисел) употребляются две формы представления: с фиксированной и с плавающей за-пятой. В первом случае просто заранее уславливаются о месте нахождения занятой, не указывая ее фактически в коде числа. Например, если условиться, что запятая стоит между 3-м и 4-м разрядами справа, то код 1 010 будет означать число 1,010= (1 + 0 * 2^-1 + 1 * 2^-2 + 0 * 2^-3) = 1,25. Во втором слу-чае код числа разбивается на два кода в соответствии с пред-ставлением числа в виде х = а * ^2b. При этом число, а (со зна-ком) называется мантиссой, а число b (со знаком) — характеристи-кой числа х. О положении кода характеристики и мантиссы (вместе с их знаками) в общем коде числа также устанавлива-ются заранее.

Для экономии числа разрядов в характеристике b ее часто представляют в виде b = ^2kb₁, где k — фиксированная константа (обычно k =2). Вводя еще одну константу m и полагая b = 2^kb₂ — m, можно избежать также использования в коде харак-теристики знака (при малых b₂ > 0 число b отрицательно, а при больших — положительно).

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

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

Тип булева переменная присваивается элементарным данным, способным принимать лишь два значения: «истина» (и) и «ложь» (л). Для представления булевых величин обычно исполь-зуется двоичный алфавит с условием и = 1, = 0.

Как известно, моделью в математике принято называть любое множество объектов, на которых определены те или иные преди-каты. Под предикатом здесь и далее понимается функция у = f (x_i, …, x_n), аргументы (x_i, .., x_n) которой принадлежат данному множеству М, а значение (у) может являться либо истиной, либо ложью. Иными словами, предикат представляет собой переменное (зависящее от параметров (Xi, .., Хn} выска-зывание. Оно описывает некоторое свойство, которым может обладать или не обладать набор элементов (Xi, …, Xn) множе-ства М.

Число п элементов этого набора может быть любым. При л = 2 возникает особо распространенный тип предиката, который носит наименование бинарного отношения или просто отноше-ния. Наиболее употребительными видами отношений являются отношения равенства (=) и неравенства (). Эти отношения естественно вводятся для элементарных данных любого дан-ного типа. Тем самым соответствующий тип данных превращает-ся в модель.

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

Любое множество М, как известно, превращается в алгебру, если на нем задано некоторое конечное множество операций. Под операцией понимается функция у = f (Xi, . ., Хп), аргументы н значение которой являются элементами множества М. При л = 1 операция называется унарной, а при п = 2 — бинарной. Наиболее распространенными являются бинарные операции.

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

Особое место в машинной информатике занимает булева алгебра, вводимая на множестве величин типа булевых. Ее основу составляют две бинарные операции: конъ-юнкция («и»), дизъюнкция («или») и одна унарная операция: отрицание («не»). Конъюнкция обозначается символом / и за-дается правилами 0 / 0 = 0, 0 / 1=0, 1 / 0 = 0, 1 / 1=1. Для дизъюнкции используются символ V и правила 0 V 0 = 0, 0 V 1 == 1, 1 V 0=1, 1 V 1 = 1. Наконец, отрицание меняет значение булевой величины на противоположное: 0=1, 1=0. Последовательность выполнения операций производится в по-рядке убывания приоритетов от к / и далее к V (если спе-циальной расстановкой скобок не оговорено противное). Напри-мер, порядок действий в формуле a / b / c / d соответству-ет прямо указанному скобками порядку:

((a) / b) V (с / a)).

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

Поскольку любая алфавитная (буквенно-цифровая) информа-ция может быть закодирована в двоичной форме, то подобным образом могут быть закодированы условия и решения задач ил любой области знаний. Если число таких задач конечно (хо-тя, может быть, и очень велико), то существуют максимальная длина т кода условий этих задач и максимальная длина n кода nх решений. В таком случае решения всех данных задач (в двоичном коде) могут быть получены из их условий с по-мощью некоторой системы булевых функций y_i=f_i(x_i, х₂, … …, x_m) (i == 1, …, n). В свою очередь все эти функции могут быть выражены через элементарные булевы операции конъюнк-ции, дизъюнкции и отрицания.

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

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

Имея запас таких элементов, можно строить более сложные

х

y

x

y

x

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

u = x / y / z и v = (x V y V z).

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

Из сказанного ясно, что можно построить комбинационную схему для решения любого конечного множества задач, решения которых однозначно определяются их условиями (подавае-мыми на вход схемы). В частности, если ограничиться какой-ли-бо фиксированной точностью представления вещественных чисел (разрядностью), то можно в принципе построить комбинацион-ную схему, вычисляющую любую заданную вещественную функ-цию у = f (x_i, …, x_n) (в двоичных кодах).

На практике, однако, оказывается, что уже схема умножителя (вычисляющая функцию у = X₁ * Х₂) при разрядности (двоичной) 32 и более оказывается столь сложной, что умножение в совре-менных ЭВМ предпочитают реализовать другим, так называемым алгоритмическим способом, о котором речь пойдет ниже.

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

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

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

Существует гораздо более эффективный путь решения ука-занной проблемы, основанный па введении в схему в дополнение к уже перечисленным логическим элементам так называемых элементов памяти. Помимо своих входных и выходных сигналов, элемент памяти характеризуется еще третьим информационным параметром—так называемым состоянием этого элемента. Со-стояние элемента памяти может меняться (но не обязательно) лишь в заданные дискретные моменты времени t_1,t₂, … под влиянием сигналов, появляющихся на его входах в эти моменты. Наиболее употребительна так называемая синхронная организа-ция работы элементов памяти, при которой моменты их возмож-ных переключении (изменении состояния) следуют друг за дру-гом через один и тот же фиксированный промежуток времени t = const, называемый тактом. Эти моменты определяются обычно с помощью импульсов, вырабатываемых специальным тактирующим синхрогенератором. Количество тактовых импуль-сов, выдаваемых им в течение одной секунды, называется так-товой частотой.

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

В простейшем случае множество элементов памяти организу-ется в так называемый регистр, т. е. в (конечную) линейно упо-рядоченную последовательность элементов, называемых разряда-ми (ячейками) регистра. Разряды нумеруются последовательны-ми натуральными числами 1, 2, …, п. Число п этих разрядов на-зывается длиной регистра.

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

Заметим еще раз, что в подавляющем большинстве случаев у = а.

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

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

Процессоры

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

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

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