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

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

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

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

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

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

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

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

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

(ФИО) 

группа ФБ-ЭФ 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.

            Таблица 1

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

                                                        Таблица 3

 Ответ :

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ПРИМЕР 2

    __              __           _

F=AB C  v  ABC  v  ABC  v  ABC                   CДНФ

       Таблица  4

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

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

ПРИМЕР 3

                _                     _       _    _     _

F= ( A  v  B  v  C )(A  v  B  v  C )(A  v  B  v  C)       СКНФ

        Таблица 5

                   Преобразование логических  выражений

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

Выполняя  преобразования необходимо соблюдать  несколько правил:

1. Если некоторые части выражения заключены в скобки ,то каждая часть преобразуется  отдельно до минимально возможного результата.
2. В первую очередь преобразуются части выражения ,над которыми стоят общие отрицания .
3. При преобразованиях  ,связанных с изменением логической операции ,необходимо следить за тем ,что бы не нарушался порядок выполнения действий .
4. Раскрывать скобки надо только после того ,как выполнены все другие возможные упрощения .

            Применение в вычислительной технике и информатике

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

                                                        Заключение.

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

                                             Приложение  1

Числа от 0 до 16 различных систем счисления 

                                              Список литературы

1. Мадер В.В  школьнику об алгебре логике (серия «Мир знаний»)-М: Просвещение ,1993
2. «Программное обеспечение ЭВМ и информационные технологии»   Б.Г. Трусов, И.В. Рудаков, Ю.И. Терентьев, С.С. Комалов, С.В. Горин, В.А. Крищенко
3. «Компьютер» Ю. Л. Кетков, изд. «Дрофа» 1997 г.
4. Фалина  И.Н. Андреева Е.В. Системы счисления и компьютерная арифметика. 1998