Алгебра и начала анализа.

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

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

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

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

Прежде всего различают двоичное и двоично-десятичное пред¬ставления чисел. В двоичном представлении используется двоич¬ная система счисления с фиксированным числом двоичных раз¬рядов (чаще всего 32 или, для малых ЭВМ, 16 разрядов, включая разряд для представления знака числа). Если нулем обозначать плюс, а единицей — минус, то 00001010 означает целое число +(23+2l)= + l0, а 10001100— число— (23 + 22) = —12 (для простоты взято 8-разрядное представление). Заметим, что знак числа в машинном представлении часто оказывается удобным ставить не в начале, а в конце числа.

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

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

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

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

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

Как известно, моделью в математике принято называть любое множество объектов, на которых определены те или иные преди¬каты. Под предикатом здесь и далее понимается функция у = f(xi, ..., xn), аргументы (xi, ..., xn) которой принадлежат данному множеству М, а значение (у) может являться либо истиной, либо ложью. Иными словами, предикат представляет собой переменное (зависящее от параметров (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х решений. В таком случае решения всех данных задач (в двоичном коде) могут быть получены из их условий с по¬мощью некоторой системы булевых функций yi=fi(xi, х2, ... ..., xm) (i == 1, ..., n). В свою очередь все эти функции могут быть выражены через элементарные булевы операции конъюнк¬ции, дизъюнкции и отрицания.

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

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

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

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

х

y

x

y

x

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

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

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

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

На практике, однако, оказывается, что уже схема умножителя (вычисляющая функцию у = X1 • Х2) при разрядности (двоичной) 32 и более оказывается столь