|
|
|
Алгебра Дж. Буля и ее применение в теории и практике информатики |
|
Алгебра Дж. Буля и ее применение в теории и практике информатики
Информация, с которой имеют дело различного рода автоматизированные информационные системы, обычно называется данными., а сами такие системы автоматизированными системами обработки данных (АСОД). Различают исходные (входные), промежуточные и выходные данные.
Данные разбиваются на отдельные составляющие, называемые элементарными данными или элементами данных. Употребляются элементы данных различных типов. Тип данных (элементарных) зависит от значений, которые эти данные могут принимать.
В современной безбумажной информатике среди различных типов элементарных данных наиболее употребительными являются целые и вещественные числа, слова (в некотором подалфавите байтового алфавита) и так называемые булевы величины. Первые два типа величин нуждаются в пояснении только в связи с конкретными особенностями их представления в современных ЭВМ.
Прежде всего различают двоичное и двоично-десятичное представления чисел. В двоичном представлении используется двоичная система счисления с фиксированным числом двоичных разрядов (чаще всего 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 2 3
|
|
|
|
 |
НА САЙТЕ: |
 |
, ,
|
|
