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

⚡ 👉🏻👉🏻👉🏻 ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻

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

Данные разбиваются на отдельные составляющие, называ­емые элементарными данными
или элементами данных.
Употреб­ляются элементы данных различных типов. Тип данных
(элемен­тарных) зависит от значений, которые эти данные могут принимать.
В современной безбумажной информатике среди различных типов элементарных данных наиболее употребительными явля­ются целые
и вещественные
числа, слова
(в некотором подалфавите байтового алфавита) и так называемые булевы величины.
Первые два типа величин нуждаются в пояснении только в связи с конкретными особенностями их представления в современ­ных ЭВМ.
Прежде всего различают двоичное и двоично-десятичное пред­ставления чисел. В двоичном
представлении используется двоич­ная система счисления
с фиксированным числом двоичных раз­рядов (чаще всего 32 или, для малых ЭВМ, 16 разрядов, включая разряд для представления знака числа). Если нулем обозначать плюс, а единицей — минус, то 00001010 означает целое число +(2 3
+2 l
)= + l0, а 10001100— число— (2 3
+ 2 2
) = —12 (для простоты взято 8-разрядное представление). Заметим, что знак числа в машинном представлении часто оказывается удобным ставить не в начале, а в конце числа.
В случае вещественных
чисел (а фактически, с учетом огра­ниченной разрядности, дробных двоичных чисел) употребляются две формы представления: с фиксированной
и с плавающей за­пятой.
В первом случае просто заранее уславливаются о месте нахождения занятой, не указывая ее фактически в коде числа. Например, если условиться, что запятая стоит между 3-м и 4-м разрядами справа, то код 00001010 будет означать число 00001,010= (1 + 0 • 2 -1
+ 1 • 2 -2
+ 0 • 2 -3
) = 1,25. Во втором слу­чае код числа разбивается на два кода в соответствии с пред­ставлением числа в виде х = а •
2
b
. При этом число а (со зна­ком) называется мантиссой,
а число b (со знаком) — характеристи­кой
числа х.
О положении кода характеристики и мантиссы (вместе с их знаками) в общем коде числа также устанавлива­ются заранее.
Для экономии числа разрядов в характеристике b
ее часто представляют в виде b =
2k
b 1
,
где k —
фиксированная константа (обычно k
=2). Вводя еще одну константу m
и полагая b =
2 k
b 2
—m ,
можно избежать также использования в коде харак­теристики знака (при малых b 2
>
0 число b
отрицательно, а при больших — положительно).
В двоично-десятичном
представлении обычные десятичные цифры (а также запятая и знак) кодируются двоичными циф­рами. При этом для экономии места часто используется так на­зываемый упакованный код,
когда с помощью одного байта ко­дируется не одна, а две десятичные цифры. Подобное представ­ление позволяет в принципе кодировать числа любой значности. На практике обычно все же ограничивают эту значность, хотяистоль большими пределами, что можно считать их неограни­ченными.
Тип данных «произвольное слово во входном алфавите» не нуждается в специальных пояснениях. Единственное условие — необходимость различать границы отдельных слов. Это достига­ется использованием специальных ограничителей и указателей длины слов.
Тип булева переменная
присваивается элементарным данным, способным принимать лишь два значения: «истина» (и) и «ложь» (л). Для представления булевых величин обычно исполь­зуется двоичный алфавит с условием и = 1, p = 0.
Как известно, моделью
в математике принято называть любое множество объектов, на которых определены те или иные преди­каты. Под предикатом
здесь и далее понимается функция у
= f(x i
, ...,x n
), аргументы ( x i
, .
..,
x n

)
которой принадлежат данному множеству М,
а значение (у)
может являться либо истиной, либо ложью. Иными словами, предикат представляет собой переменное (зависящее от параметров ( 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
соответству­ет прямо указанному скобками порядку:
В принципе могут быть введены и другие операции, однако оказывается, что любую такую операцию можно выразить в виде формулы, использующей только конъюнкции, дизъюнкции и отрицания. Таким образом, введенный набор операций является для булевой алгебры универсальным.

Поскольку любая алфавитная (буквенно-цифровая) информа­ция может быть закодирована в двоичной форме, то подобным образом могут быть закодированы условия и решения задач ил любой области знаний. Если число таких задач конечно (хо­тя, может быть, и очень велико), то существуют максимальная длина т
кода условий этих задач и максимальная длина n кода nх решений. В таком случае решения всех данных задач (в двоичном коде) могут быть получены из их условий с по­мощью некоторой системы булевых функций y i
=f i
(x i
,
х
2

, ... ...,
x m
) (i
== 1, ...,n). В свою очередь все эти функции могут быть выражены через элементарные булевы операции конъюнк­ции, дизъюнкции и отрицания.
Существуют различные способы представления булевых ве­личин (двоичных цифр) в виде тех или иных физических (обыч­но электрических) сигналов (высокое и низкое напряжение, им­пульсы тока разной полярности и т. п.).
Выбрав форму представления (двоичных) сигналов, можно построить элементарные устройства, называемые обычно логиче­скими вентилями
(или логическими элементами),
которые реали­зуют элементарные булевы операции. Иными словами, выходные
сигналы этих устройств представляют собой элементарные буле­вы функции (результат выполнения элементарных булевых опе­раций) от входных сигналов, как это показано на рис. 1.
Имея запас таких элементов, можно строить более сложные
схемы, подсоединяя выходы одних элементов к входам других. Если при таких соединениях избегать воз­никновения замкнутых контуров (например, подсоединения выхода элемента на один из его собствен­ных входов), то возникает класс схем, называемых обычно комбина­ционными схемами.
Такие схемы находятся в однозначном соответст­вии с формулами булевой алгебры, так что с их помощью может быть выражена любая система булевых функций. Например, схема, изображенная на рис. 2, реа­лизует систему булевых функций
u = x /\ y \/ ù z
и v = ù(x Vy V z).
На практике построение комбинационных схем усложняется, поскольку сигналы при прохождении через вентили ослабляют­ся, искажают свою первоначальную форму, запаздывают. Поэто­му необходимо наряду с логическими элементами включать в схему различного рода согласующие элементы
(усилители, фор­мирователи сигналов и др.). Задача этих элементов—сделать схему работоспособной и надежной.
Из сказанного ясно, что можно построить комбинационную схему для решения любого конечного множества задач, решения которых однозначно определяются их условиями (подавае­мыми на вход схемы). В частности, если ограничиться какой-ли­бо фиксированной точностью представления вещественных чисел (разрядностью), то можно в принципе построить комбинацион­ную схему, вычисляющую любую заданную вещественную функ­цию у
= f(x i
,
...,
x n

)
(в двоичных кодах).
На практике, однако, оказывается, что уже схема умножителя
(вычисляющая функцию у =
X 1

•
Х
2

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

Следует заметить, что успехи микроэлектроники делают воз­можным построение все более сложных схем. Если еще в 60-е годы каждый логический элемент собирался из нескольких физи­ческих элементов (транзисторов, диодов, сопротивлений и др.), то уже к началу 80-х годов промышленностью выпускаются так называемые интегральные схемы,
содержащие многие сотни и даже тысячи логических вентилей. При этом важно подчеркнуть, что не только сами логические элементы, но и соединения меж­ду ними (т. е. вся схема в целом) изготовляются одновременно в едином технологическом процессе на тонких пластинках хими­чески чистого кремния и других веществ размерами в доли квад­ратного сантиметра. Благодаря этому резко уменьшилась стои­мость изготовления схем и повысилась их надежность.
Обладая возможностью реализовать любые ф и к с и р о в а н н ы е зависимости между входными и выходными сигналами» комбинационные схемы неспособны обучаться, адаптироваться к изменяющимся условиям. На первый взгляд кажется, что такая адаптация обязательно требует структурных изменений
в схеме,. т. е. изменения связей между ее элементами, а возможно, и со­става этих элементов. Подобные изменения нетрудно реализовать путем механических переключении. Однако такой путь практи­чески неприемлем из-за резкого ухудшения практически всех параметров схемы (быстродействия, габаритов, надежности и др.).
Существует гораздо более эффективный путь решения ука­занной проблемы, основанный па введении в схему в дополнение к уже перечисленным логическим элементам так называемых э лементов памяти.
Помимо своих входных и выходных сигналов, элемент памяти характеризуется еще третьим информационным параметром—так называемым состоянием
этого элемента. Со­стояние элемента памяти может меняться (но не обязательно) лишь в заданные дискретные моменты времени t 1,
t 2
, ... подвлиянием сигналов, появляющихся на его входах в эти моменты. Наиболее употребительна так называемая синхронная
организа­ция работы элементов памяти, при которой моменты их возмож­ных переключении
(изменении состояния) следуют друг за дру­гом через один и тот же фиксированный промежуток времени D t =
const, называемый тактом.
Эти моменты определяются обычно с помощью импульсов, вырабатываемых специальным тактирующим синхрогенератором.
Количество тактовых импуль­сов, выдаваемых им в течение одной секунды, называется так­товой частотой.

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

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

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

Название: Алгебра Дж. Буля и ее применение в теории и практике информатики
Раздел: Рефераты по математике
Тип: реферат
Добавлен 16:54:45 23 мая 2006 Похожие работы
Просмотров: 44
Комментариев: 18
Оценило: 3 человек
Средний балл: 5
Оценка: неизвестно   Скачать

Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.

Реферат: Алгебра Дж. Буля и ее применение в теории и практике информатики
Дипломная работа по теме Положения Конституции Республики Казахстан
Реферат по теме Развитие анатомии в России
Контрольная работа по теме Исторический и классовый характер воспитания
Контрольная Работа На Тему Порядок Увольнения Работника И Оплаты Сверхурочного Труда
Методика Написания Эссе
Реферат: Computers Essay Research Paper COMPUTERSCould one imagine
Продать Сочинение По Литературе
Контрольная Работа На Тему Текстовий Редактор Ms Word
Курсовая работа по теме Классификация юридических лиц в Российской Федерации и странах континентального права
Гарантии И Компенсации Курсовая Работа
Судьба Бедной Лизы Сочинение
Изложение: Утилита "Поверхность"
Лист Для Реферата Расчерченный
Контрольная работа: Иностранные инвестиции
Курсовая работа: Виды неформальных отношений в различных организациях
Сочинение: Андрей Болконский и Родион Раскольников
Сочинение Про Осень На Башкирском Языке
Доклад: Совершенствование норм, регламентирующих подготовку дел к разбирательству в арбитражном суде, и проблемы практики
Доклад: Государственный Исторический Музей. Скачать бесплатно и без регистрации
Реферат по теме Учет основных средств и нематериальных активов в зарубежных странах (Англия, США)
Реферат: Цифровые фотоаппараты
Реферат: Пути преодоления кризиса в исполнительной власти
Статья: Формирование и регулирование цен на сельскохозяйственную продукцию в западных странах