Применение алгебры логики в информатике

Тема: Применение алгебры логики в информатике

Раздел: Бесплатные рефераты по информатике

Тип: Курсовая работа | Размер: 369.38K | Скачано: 230 | Добавлен 04.03.14 в 19:47 | Рейтинг: 0 | Еще Курсовые работы

Вуз: ВЗФЭИ

Год и город: Уфа 2012

Оглавление

1. Теоретическая часть 4

1.1. Общие положения 4

1.2. Представления чисел 4

1.3. Булева алгебра 7

1.4. Построение комбинаторных схем 9

1.5. Использование алгебры логики в современной информатике 11

2. Практическая часть 13

2.1. Постановка задачи 13

2.1.1. Цель решения задачи 13

2.1.2. Условие задачи 13

2.2. Компьютерная модель решения задачи 14

2.2.1. Информационная модель решения задачи 14

2.2.2. Аналитическая модель решения задачи 15

2.2.3. Технология решения задачи MS Excel 15

2.3. Результаты компьютерного эксперимента и их анализ 23

2.3.1. Результаты компьютерного эксперимента 23

2.3.2. Анализ полученных результатов 24

Заключение 25

Список использованной литературы 26

 

Введение

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

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

В практической части рассмотрено решение экономической задачи с использованием табличного процессора MS Excel.

 

1. Теоретическая часть

1.1. Общие положения

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

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

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

1.2. Представления чисел

Прежде всего, различают двоичное и двоично-десятичное пред­ставления чисел. В двоичном представлении используется двоич­ная система счисления с фиксированным числом двоичных раз­рядов (чаще всего 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 ее часто представляют в виде b = ^2kb₁, где k – фиксированная константа (обычно k=2). Вводя еще одну константу m и полагая b = 2^kb₂ – m, можно избежать также использования в коде харак­теристики знака (при малых b₂>0 число b отрицательно, а при больших – положительно).

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

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

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

Как известно, моделью в математике принято называть любое множество объектов, на которых определены те или иные преди­каты. Под предикатом здесь и далее понимается функция у = f(x_i, ..., x_n), аргументы (x_i, ..., x_n) которой принадлежат данному множеству М, а значение (у) может являться либо истиной, либо ложью. Иными словами, предикат представляет собой переменное (зависящее от параметров {Xi, ..., Хn}) выска­зывание. Оно описывает некоторое свойство, которым может обладать или не обладать набор элементов (Xi, ..., Xn) множе­ства М.

Число n элементов этого набора может быть любым. При n=2 возникает особо распространенный тип предиката, который носит наименование бинарного отношения или просто отноше­ния. Наиболее употребительными видами отношений являются отношения равенства (=) и неравенства (¹). Эти отношения естественно вводятся для элементарных данных любого дан­ного типа. Тем самым соответствующий тип данных превращает­ся в модель.

Применительно к числам (целым или вещественным) естест­венным образом вводятся также отношения порядка >, <, >, £, ³. Тем самым для соответствующих типов данных определяются более богатые модели.

Любое множество М, как известно, превращается в алгебру, если на нем задано некоторое конечное множество операций. Под операцией понимается функция у=f(Xi, . .., Хп), аргументы и значение которой являются элементами множества М. При n=1 операция называется унарной, а при n=2 – бинарной. Наиболее распространенными являются бинарные операции.

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

 

1.3. Булева алгебра

Особое место в машинной информатике занимает булева алгебра, вводимая на множестве величин типа булевых. Ее основу составляют две бинарные операции: конъ­юнкция («и»), дизъюнкция («или») и одна унарная операция: отрицание («не»). Конъюнкция обозначается символом /\ и за­дается правилами 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х решений. В таком случае решения всех данных задач (в двоичном коде) могут быть получены из их условий с по­мощью некоторой системы булевых функций y_i=f_i(x_i, х₂, ... ..., x_m) (i == 1, ..., n). В свою очередь все эти функции могут быть выражены через элементарные булевы операции конъюнк­ции, дизъюнкции и отрицания.

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

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

Рис. 1. Элементарные буле­вы функции

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

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

 

1.4. Построение комбинаторных схем

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

Рис. 2. Комбинаторная схема

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

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

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

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

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

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

 

1.5. Использование алгебры логики в современной информатике

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

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

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

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

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

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

 

2. Практическая часть

2.1. Постановка задачи

2.1.1. Цель решения задачи

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

Цель решения данной задачи состоит в том, чтобы рассчитать и проанализировать результаты деятельности пекарни.

2.1.2. Условие задачи

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

Ведомость продаж

Наименование	Количество, шт	Цена, руб	Сумма, руб
-	i	k	Sik

Латинские буквы в таблице указывают на элементы соответствующих расчетных формул.

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

Структура документа «Прайс-лист»

Наименование	Цена, руб

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

Структура результирующего документа

«Итоговая ведомость»

Наименование	Количество, шт	Цена, руб	Сумма, руб
…	…	…	Сi
Итого	…	…	C

Кроме того, информацию, находящуюся в таблицах для анализа, необходимо представить в виде диаграммы.

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

 

2.2. Компьютерная модель решения задачи смотрте в файле

 

Заключение

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

Подробно изложена практическая часть работы, которая предполагает решение экономической задачи, при помощи таблиц Excel. Суть задания практической части состоит в том, чтобы на основе представленных данных о ценах и количестве определенного товара (хлеба) сформулировать и заполнить форму итоговой ведомости продаж, результаты вычислений представить в графическом виде. Работа выполняется на портативном компьютере (типа ноутбук) с процессором Intel Celeron M. Для оформления теоретической и практической части используется пакет программ Microsoft: текстовый редактор Microsoft Office и табличный процессор Microsoft Excel.

 

Список использованной литературы

1. Информатика в экономике: учебное пособие / под ред. Б.Е. Одинцова, А.Н. Романова. – М.: Вузовский учебник, 2008.
2. Секреты кибернетики / В.Н. Касаткин, А.Ф. Верлань. – Киев: «Радянська школа», 1971.
3. Нестандартная математика в школе / М.В. Возлинская. – М.: «Лайда», 1993.
4. Логика и комбинаторика / Составитель А.А. Егоров // Приложение к журналу КВАНТ. – 2002. – № 5.

---

Понравилось? Нажмите на кнопочку ниже. Вам не сложно, а нам приятно).

---

Чтобы скачать бесплатно Курсовые работы на максимальной скорости, зарегистрируйтесь или авторизуйтесь на сайте.

Важно! Все представленные Курсовые работы для бесплатного скачивания предназначены для составления плана или основы собственных научных трудов.

---

Друзья! У вас есть уникальная возможность помочь таким же студентам как и вы! Если наш сайт помог вам найти нужную работу, то вы, безусловно, понимаете как добавленная вами работа может облегчить труд другим.

Добавить работу

---

Если Курсовая работа, по Вашему мнению, плохого качества, или эту работу Вы уже встречали, сообщите об этом нам.

---

Добавление отзыва к работе

Добавить отзыв могут только зарегистрированные пользователи.

---

Похожие работы

• Применение алгебры высказываний в информатике
• Применение алгебры логики в информатике (понятия, формулы)