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

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

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

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

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

/\

 

/>       y />

z = x   V   y   />

V

        x

/>/>      y

/> /> /> /> />   /> <td/> /> />

/>/>/>               x/>/>

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

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

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

/>

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

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

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

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

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

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

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

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

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

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

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

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

Процессоры

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

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

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

Списоклитературы

Для подготовки данной работы были использованыматериалы с сайта www.refcentr.ru/