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

 

 

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

ФГБОУ ВПО

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

 

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

 

 

 

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

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

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

 

 

 

 

 

 

                                                                   Исполнитель:

Факультет: Финансово-кредитный

Направление: Бакалавр экономики

Группа: день

№ зачетной книжки

                     Руководитель

                                                   

 

                                                  

                                                   Владимир 2012

 

                                                    Содержание

Введение 3

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

1. Наука алгебра логики  4
2. Основные понятия алгебры логики 7
3. Применение алгебры логики в информатике 12

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

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

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

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

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

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

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

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

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

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

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

Заключение 21

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

Приложения 23

 

 

 

 

 

 

 

 

 

 

ВВЕДЕНИЕ

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

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

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

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

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

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

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

Практическая часть выполнена с использование 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