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

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ФГБОУ ВПО

«Финансовый университет при правительстве российской федерации»

Кафедра Экономической теории

Курсовая работа

по дисциплине «Информатика»

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

Владимир 2012

Содержание

алгебра логика задача компьютерный

Введение

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

1.1 Наука алгебра логики

1.2 Основные понятия алгебры логики

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

ВВЕДЕНИЕ

Тема теоретической части курсовой работы: Применение алгебры логики в информатике. Алгебра логики является составной частью одного из современных быстро развивающихся разделов математики - математической логики. Математическая логика применяется в информатике, позволяет моделировать простейшие мыслительные процессы. Одним из занимательных приложений алгебры высказываний - решение логических задач.

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

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

Для достижения цели необходимо ответить на следующие вопросы:

- наука алгебра логики

- основные понятия алгебры логики

- применение алгебры логики в информатике (к построению схем, обработке знаний и т.д.)

Практическая часть выполнена с использование MS Excel и MS Word.

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

1.1 Наука алгебра логики

Алгебра логики возникла в середине ХIХ века в трудах английского математика Джорджа Буля. Её создание представляло собой попытку решать традиционные логические задачи алгебраическими методами.

Отцом алгебры логики по праву считается английский математик 19-го столетия Джорж Буль (1815-1864). Именно он построил один из разделов формальной логики в виде некоторой «алгебры», аналогичной алгебре чисел, но не сводящейся к ней. Алгебра в широком смысле слова - наука об общих операциях, аналогичных сложению и умножению, которые могут выполняться не только с числами, но и над другими математическими объектами. Существуют алгебры натуральных чисел, многочленов, векторов, матриц, множеств и т.д.

Большой вклад в становление и развитие алгебры логики внесли Августус де Морган (1806-1871), Уильям Стенли Джевонс (1835-1882), П.С. Порецкий(1846 - 1907), Чарлз Сандерс Пирс (1839-1914), А.А. Марков (1903-1979), А.Н. Колмогоров (1903-1987) и др.

Долгое время алгебра логики была известна достаточно узкому классу специалистов. Прошло почти 100 лет со времени создания алгебры логики Дж. Булем, прежде чем в 1938 Клод Шеннон (1916-2001) показал, что алгебра логики применима для описания самых разнообразных процессов, в том числе функционирования релейно-контактных и электронно-ламповых схем.

Алгебра логики явилась математической основой теории электрических и электронных переключателей схем, используемых в ЭВМ. В компьютерных науках её предпочитают называть не алгеброй логики, а Булевой алгеброй - по имени её создателя.

Алгебра логики изучает свойства функций, у которых и аргументы, и значения принадлежат заданному двухэлементному множеству (например, {0,1}).Иногда вместо термина «алгебра логики» употребляют термин «двузначная логика».

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

Действительно, мало-мальски сложное действие невозможно без обратной связи, без анализа условий выполнения. Например, «ЕСЛИ нам хочется пить, ТО мы пьём, ИНАЧЕ мы даже не думаем об этом». «ЕСЛИ компьютер не работает И питание включено, ТО компьютер сгорел». «ЕСЛИ точка левее левой стороны квадрата ИЛИ правее правой, ТО точка расположена не в квадрате». «Ревёт ли зверь в лесу глухом, трубит ли рог, гремит ли гром...». «Кошелёк или жизнь». Помимо манипуляций константами «да» и «нет» логические переменные могут являться результатом применения к числам операторов отношения (меньше, больше, равно и т.п.). В компьютерах булевы переменные представляются (кодируются) битами (разрядами двоичной системы счисления), где 1 означает истину, а 0 - ложь. Манипуляции высказываниями и их комбинациями используются для получения некоего единственного результата, который можно использовать, например, для выбора той или иной последовательности действий. Поскольку логические переменные кодируются по тем же принципам, что и числа, символы и прочая информация, то можно комбинировать операции логики с операциями арифметики для реализации различных алгоритмов.

Таким образом, алгебра логики (другое название - Булева алгебра) - это область математики. Она оперирует величинами, которые могут принимать два значения (булевых значения). Эти два значения могут быть обозначены как угодно, лишь бы по-разному. Самые распространенные варианты:

0, 1

F, T

false, true

ложь, истина

Л, И

При применении булевой алгебры в вычислительной технике, булевы значения - это 0 и 1. Они представляют собой состояние ячейки памяти объёмом в 1 бит или наличие/отсутствие напряжения в электрической схеме. Алгебра логики позволяет строить сложные электронные узлы, элементы которых работают согласно этой математической теории. При применении булевой алгебры в логических построениях в математике, булевы значения - это «ложь» и «истина». Они определяют истинность или ложность некоторого высказывания. Под высказываниями понимаются математические формулы. При применении булевой алгебры в повседневных рассуждениях, булевы значения - это также «ложь» и «истина». Они представляют собой оценку истинности или ложности некоторого высказывания. Под высказываниями понимаются фразы, которые удовлетворяют строго определенному списку свойств.

Алгебра логики применяется:

1) для упрощения сложных логических формул и доказательств тождеств;

2) при решении логических задач;

3) в контактных схемах;

4) при доказательствах теорем;

5) в базах данных при составлении запросов.

1.2 Основные понятия алгебры логики

Объектом логики как науки выступает абстрактное мышление. Логика изучает абстрактное мышление как средство познания объективного мира, исследует формы и законы, в которых происходит отражение мира в процессе мышления. Основными формами абстрактного мышления являются:

- понятия

- суждения,

- умозаключение.

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

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

Пример сложного суждения: "Наступила осень, и лебеди улетают". Оно состоит из двух простых суждений.

Умозаключение -- прием мышления, посредством которого из исходного знания получается новое знание; из одного или нескольких истинных суждений, называемых посылками, мы по определенным правилам вывода получаем заключение. Есть несколько видов умозаключений. Все металлы -- простые вещества. Литий -- металл. Литий -- простое вещество.

Все металлы - вещества. Железо - металл. Железо - вещество

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

Формальная логика -- наука о законах и формах правильного мышления.

Математическая логика изучает логические связи и отношения, лежащие в основе дедуктивного (логического) вывода.

Логика высказываний послужила основным математическим инструментом при создании компьютеров. Она легко преобразуется в битовую логику: истинность высказывания обозначается одним битом (0 - ЛОЖЬ, 1 - ИСТИНА); тогда операция ¬ приобретает смысл вычитания из единицы; ? - немодульного сложения; & (или ?) - умножения; - - равенства; ? - в буквальном смысле сложения по модулю 2 (исключающее Или - XOR); ? - непревосходства суммы над 1 (то есть A?B = (A + B) <= 1).

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

Логическое выражение

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

латинского алфавита. Существуют разные варианты обозначения истинности и ложности переменных:

Истина	И	True	T	1
Ложь	Л	False	F	0

Связки «НЕ», «И», «ИЛИ» заменяются логическими операциями инверсия, конъюнкция, дизъюнкция. Это основные логические операции, при помощи которых можно записать любое логическое выражение.

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

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

Приоритет логических операций:

- Инверсия

- Конъюнкция,

- Дизъюнкция

Конъюнкция

Конъюнкция: соответствует союзу: «и», обозначается знаком^, обозначает логическое умножение.

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

А^В^С = 1

если А=1, В=1, С=1.

А	В	А^B
1	1	1
1	0	0
0	1	0
0	0	0

Дизъюнкция

Логическая операция соответствует союзу ИЛИ, обозначается знаком v, иначе называется ЛОГИЧЕСКОЕ СЛОЖЕНИЕ.

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

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

A v В v С = 0,

только если А = О, В = О, С - 0.

Таблица истинности дизъюнкции имеет следующий вид:

А	В	А v B
1	1	1
1	0	1
0	1	1
0	0	0

Инверсия

Логическая операция соответствует частице не, обозначается ¬ или Ї и является логическим отрицанием.

Инверсия логической переменной истинна, если переменная ложна и наоборот: инверсия ложна, если переменная истинна.

A	¬А
1	0
0	1

высказывания у которых таблицы истинности совпадают называются равносильными.

ИМПЛИКАЦИЯ И ЭКВИВАЛЕНТНОСТЬ

Импликация «если А, то В», обозначается А > В

А	В	А > В
0	0	1
0	1	1
1	0	0
1	1	1

Эквивалентность «А тогда В и только тогда», обозначается А ~ В

А	В	А~ B
0	0	1
0	1	0
1	0	0
1	1	1

При вычислении значения логического выражения (формулы) логические операции вычисляются в определенном порядке, согласно их приоритету:

инверсия,

конъюнкция,

дизъюнкция,

импликация и эквивалентность.

Операции одного приоритета выполняются слева направо. Для изменения порядка действий используются скобки.

Например: дана формула

Порядок вычисления:

- инверсия

- конъюнкция

- дизъюнкция

- импликация

- эквивалентность.

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

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

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

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

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

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

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

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

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

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

Цель решения данной задачи состоит в расчете стоимости стеклопакетов (документ «Стоимость стеклопакетов и выполняемых работ», «Доход предприятия от выполненных работ») Решение задачи заключается в организации межтабличных связей с использованием функций ПРОСМОТР для автоматического формирования стоимости товара.

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

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

№ п/п	Наименование модели	Размеры, мм	Стоимость стеклопакета, руб.	Стоимость монтажа, руб.	Стоимость подоконников, руб.	Общая стоимость
	n		Zn	Rn	Cn	Sn

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

Этаж	Модель стеклопакета	Количество стеклопакетов
n		Kn

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

				Скидка-8,5%
Этаж	Количество устанавленных стеклопакетов, шт	Стоимость одного стеклопакета с учетом подоконников и монтажа, руб	Стоимость установленных стеклопакетов, руб	Стоимость стеклопакетов с учетом скидки, руб
n	Kn	Rn	Zn	Cn
Итого общая стоимость стеклопакетов, руб		S

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

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

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

Рис.1. Информационная модель взаимосвязи исходных и результирующих данных

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

Требуется рассчитать:

- общую стоимость стеклопакетов и выполняемых работ

Sn=Zn+Rn+Cn

- стоимость установленных стеклопакетов

S=Kn*Zn

- стоимость стеклопакетов на каждом этаже и в здании с учетом скидки в 10%.

S=S-(10%*8.5%)-S

- общую сумму стеклопакетов

S=?S

Где Sn-стоимость стеклопакетов и выполняемых работ товара, Zn-стоимость, Kn- количество устанавливаемых стеклопакетов товара.

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

1. Запустить табличный процессор MS Excel.

2. Создать книгу с именем «Курсовая работа, вариант № 9».

3. Лист 1 переименовать в лист «Стоимость стеклопакетов и выполняемых работ».

4. На листе «Стоимость стеклопакетов и выполняемых работ» создать таблицу с исходными данными.

5. Лист 2 переименовать в лист «Количество стеклопакетов, устанавливаемых в доме.

6. На листе «Количество стеклопакетов, устанавливаемых в доме» создать таблицу с исходными данными.

7. Лист 3 переименовать в лист «Доход предприятия от выполненных работ».

8. На листе «Доход предприятия от выполненных работ» создать таблицу «Доход предприятия от выполненных работ»

9. Произвести заполнение таблицы «Доход предприятия от выполненных работ», (организовав межтабличные связи), через функцию ПРОСМОТР, а так же произвести расчет по формулам.

10. Отразим таблицу «Доход предприятия от выполненных работ» с конечными результатами.

11. Графическое представление результатов результирующего документа.

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

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

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

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

Таким образом, формирование сводной таблицы на основе «Доход предприятия от выполненных работ» позволяет решить поставленную задачу - отслеживать стоимость стеклопакетов, и тем самым помогает анализировать количество проданных стеклопакетов конкретной модели. Создание различных диаграмм (гистограмм, графиков) на основе данных сводных таблиц средствами MS Excel позволяет не только наглядно представлять результаты обработки информации для проведения анализа с целью принятия решений, но и достаточно быстро осуществлять манипуляции в области их построения в пользу наиболее удобного представления результатов визуализации по задаваемым пользователем (аналитиком) параметрам.

ЗАКЛЮЧЕНИЕ

Итак, алгебра высказываний является составной частью одного из современных быстро развивающихся разделов математики -- математической логики. Математическая логика применяется в информатике, позволяет моделировать простейшие мыслительные процессы. Одним из занимательных приложений алгебры высказываний -- решение логических задач.

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

Объектами алгебры высказываний являются высказывания. Высказывание - это истинное или ложное повествовательное предложение. Повествовательное предложение, в котором говорится об одном единственном событии, называется простым высказыванием.

С помощью программы MS Excel я рассчитала стоимость стеклопакетов и доход от установки стеклопакетов по этажам и на основании этого представила в графическом виде.

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

1. Романов А.Н., Одинцов Б.Е. Информационные системы в экономике (лекции, упражнения и задачи): Учеб. пособие. - М.: Вузовский учебник, 2008. - 300 с.

2. Информационные системы и технологии управления: Учебник / Под. ред. Г.А. Титоренко. - М.: ЮНИТИ-ДАНА, 2010. - 591 с.

3. Экономическая информатика / Под ред. В.П. Косарёва и Л.В. Ерёмина. Москва: Финансы и статистика, 2001. 592 с.

4. Сайт-портфолио преподавателя Тлупова Заурбека Аликовича- http://www.zaurtl.ru/UkVT/UKVT8.html

5. Интернет-источник: http://ru.wikipedia.org

Размещено на Allbest.ru

...