В нашей онлайн базе уже более 10821 рефератов!

Список разделов
Самое популярное
Новое
Поиск
Заказать реферат
Добавить реферат
В избранное
Контакты
Украинские рефераты
Статьи
От партнёров

Новости
Загрузка...
Крупнейшая коллекция рефератов
Предлагаем вам крупнейшую коллекцию из 10821 рефератов!

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

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

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

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

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

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

Прежде всего различают двоичное и двоично-десятичное пред­ставления чисел. В двоичном представлении используется двоич­ная система счисления с фиксированным числом двоичных раз­рядов (чаще всего 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, p = 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.

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

х

z = x / y

[1] 2 3

скачать реферат скачать реферат

Новинки
Интересные новости
загрузка...

Заказ реферата
Заказать реферат
Счетчики

Rambler's Top100

Ссылки
Все права защищены © 2005-2017 textreferat.com