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

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

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

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

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

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

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

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

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

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

Как известно, моделью в математике принято называть любое множество объектов, на которых определены те или иные предикаты. Под предикатом здесь и далее понимается функция у = f(x_i, .., x_n), аргументы (x_i, .., x_n) которой принадлежат данному множеству М, а значение (у) может являться либо истиной, либо ложью. Иными словами, предикат представляет собой переменное (зависящее от параметров (Xi, .., Х} высказывание. Оно описывает некоторое свойство, которым может обладать или не обладать набор элементов (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 /\ \/ c /\ù d соответствует прямо указанному скобками порядку:

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

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

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

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

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

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

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

х