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

Федеральное государственное

Образовательное бюджетное учреждения

Высшего профессионального  образования

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

КАФЕДРА ПРИКЛАДНОЙ ИНФОРМАТИКИ 

Курсовая  работа по информатике 

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Исполнитель: Фильчагова К. П.

(ФИО) 

группа ФБ-ЭФ 117

 Руководитель: Шмелев В.В.

 (должность, ФИО) 

 

 

 

 

г.Москва   2012

                                                      Содержание

1. Содержание ---------------------------------------------------------------2
2. Введение ------------------------------------------------------------------- 3
3. Возникновение логики--------------------------------------------------4
4. Конъюнкция и дизъюнкция--------------------------------------------5
5. Таблица истинности -----------------------------------------------------6
6. Логическая функция ----------------------------------------------------10
7. Преобразование логических выражений -------------------------14
8. Применение в вычислительной технике и информатике------15
9. Заключение ---------------------------------------------------------------16
10. Приложение --------------------------------------------------------------17
11. Список литературы -----------------------------------------------------18 
    

                                                     Введение

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

 Высказывание – повествовательное предложение, относительно которого определенно и объективно можно сказать истинно оно или ложно (ЛОЖЬ или ИСТИНА, 0 или 1, TRUE или FALSE).

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

                                    

 

 

 

 

 

                                        Возникновение логики.

 

          Понятие логики как науки появилось ещё в  XIX в., т.е. задолго до появления науки информатики и компьютеров. Элементы математической логики можно найти уже в работах древнегреческих философов. В XVII в. Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам. Однако как самостоятельный раздел математики логика начала формироваться только с середины XIX в.. Для того чтобы рассуждать, человеку необходим какой-либо язык. Не удивительно, что математическая логика начиналась с анализа того, как говорят и пишут люди на естественных языках. Этот анализ привёл к тому, что выяснилось существование формулировок, которые невозможно разделить на истинные и ложные, но, тем не менее, выглядят осмысленным образом. Это приводило к возникновению парадоксов, в том числе в одной из фундаментальных наук математики. Тогда было решено создать искусственные формальные языки, лишённого «вольностей» языка естественного.

 

 

 

 

 

 

 

                               Конъюнкция и дизъюнкция 

      Конъюнкция : соответствует союзу: «и», обозначается знаком ^, обозначает логическое умножение. Конъюнкция двух логических ~ истинна тогда и только тогда , когда оба высказываний истинны. Можно обобщить для любого количества переменных  А^В^С = 1 если А=1, В=1, С=1.

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

            Таблица 1

Логическая  операция соответствует союзу ИЛИ, обозначается знаком v, иначе называется ЛОГИЧЕСКОЕ СЛОЖЕНИЕ. Дизъюнкция двух логических переменных ложна тогда и галька тогда, когда оба высказывавия ложны. Это определение можно обобщить для любого количества логических переменных, объединенных дизъюнкцией. A v В v С = 0, только если А = О, В = О, С - 0. Таблица истинности дизъюнкции имеет следующий вид:

A	B	Av В
1	1	1
1	0	1
0	1	1
0	0	0

                Таблица 2

                                                  

                                                             Таблица истинности

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

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

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

Построение  таблицы истинности логической функции :

Для любой  сложный логической функции ,записанной в виде логического выражения может быть построена таблица истинности.  Количество наборов в таблице определяется числом различных переменных , которые входят в запись логической функции и равно 2 в степени n,где n- число переменных . Порядок записи наборов всегда одинаковый и представляет собой последовательность двоичных чисел от 0 до 2 в степени n-1 ,записанных n разрядами .Так для функции ,зависящей от трех переменных ,это будут триады ,а для функции ,зависящей от четырех переменных –триады (приложение 1). Часто наборы называют порядковыми  номерами ,соответствующими двоичному числу  ,- нулевой ,первый ,седьмой  и  т . д .

 

 

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

• подсчитать количество переменных n в логическом выражении;
• определить число строк в таблице m = 2n;
• подсчитать количество логических операций в формуле;
• установить последовательность выполнения логических операций с учетом скобок и приоритетов;
• определить количество столбцов в таблице: число переменных плюс число операций;
• выписать наборы входных переменных ;
• провести заполнение таблицы истинности по столбикам, выполняя логические операции в соответствии с установленной в п.4 последовательностью
• Наборы входных переменных, рекомендуют перечислять следующим образом:
• определить количество наборов входных переменных;
• разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки 0, а нижнюю —1;
• разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами 0 или 1, начиная с группы 0;
• продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа.

 

 

 

                       Приоритеты операций :

• операции в скобках ()
• отрицание
• конъюнкция
• дизъюнкция
• импликация
• эквивалентность

  ПРИМЕР  1

                        3

        _             ͞_ ͞͞͞   ͞

F =AB v C v BC v A

       4  5    6   1  2

A	B	C	_ B	_ C	_ BC	_  BCvA		_ AB	_ AB vC	F
							_ BCvA
0	0	0	1	1	0	0	1	0	0	1
0	0	1	1	0	0	0	1	0	1	1
0	1	0	0	1	1	1	0	0	0	0
0	1	1	0	0	0	0	1	0	1	1
1	0	0	1	1	0	1	0	1	1	1
1	0	1	1	0	0	1	0	1	1	1
1	1	0	0	1	1	1	0	0	0	0
1	1	1	0	0	0	1	0	0	1	1

                                                        Таблица 3

 

 Ответ :

« функция  F =0 на наборах 2,6» или «функция F=1 на наборах 0,1,3,4,5,7»

Обычно выбирают вариант с наименьшим количеством  наборов .

                 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

                                         Логическая функция

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

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

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

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

В элементарные конъюнкции и дизъюнкции не могут  входить одинаковые переменные или  переменные со своими отрицаниями. Количество переменных в элементарной конъюнкции и дизъюнкции называется  рангом.

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

Совершенная дизъюнктивная  нормальная форма  (СДНФ) – это форма ,в которой  функция представляется в виде дизъюнкции элементарных конъюнкций .

Совершенная конъюнктивная нормальная форма (СКНФ) – это форма ,в которой функция представляется в виде конъюнкции элементарных дизъюнкций .

Для любой  логической функции можно составит только одну СДНФ и только одну  СКНФ.

Для СДНФ и  СКНФ должны соблюдаться два условия :

1. все элементарные конъюнкции и дизъюнкции имеют одинаковый ранг, т.е  количество элементов в них одинаковые .
2. в элементарные конъюнкции и дизъюнкции входят все переменные или их отрицания ,от которых зависит функция .

 

Функции в  СДНФ и СКНФ записываются  с помощью  таблиц истинности . по определенным правилам .

Правило записи СДНФ:

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