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

 

Федеральное государственное  образовательное бюджетное учреждение  высшего профессионального образования

 

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

 

 

                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                  

 

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

 

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

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

 

                                                      

                              

 

 

 

                                                            Исполнитель: Петрова Ольга  

                                                            Николаевна

                                                        Специальность: бакалавр

                                                                менеджмента   

                                                             Группа: ФНО день                            

                     № зачетной книжки:100.10/120276

                                                            Руководитель:  Кручинин И. И

                                                                          

 

                                             Калуга 2013г

                                                    

                                                       Содержание

 
 
Введение ………………………………………………………………………..3

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

 

1.1. Основные понятия. Логические  операции 4

1.2. Логические выражения.  Порядок логических операций 8

1.3. Основные законы алгебры  логики 9

1.4. Табличное и алгебраическое  задание булевских функций 10

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

 

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

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

2.2. Описание алгоритма  решения задачи 20

 

Заключение 26

 

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

                                     

Введение

 

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

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

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

- дать основные понятия  алгебры высказываний и рассмотреть  логические операции;

- выявить порядок логических  операций;

- рассмотреть основные  законы алгебры логики;

- раскрыть табличное и  алгебраическое задание булевских  функций.

Для выполнения и оформления курсовой работы был использован  компьютер IBM PC совместимый, ЦПУ Intel® Celeron® 2800 МГц, ОЗУ 1.0 Гб с программным обеспечением Microsoft® Windows® XP SP2. 

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

 

 

 

 

 

 

 

 

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

1.1. Основные понятия.  Логические операции

 

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

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

Алгебра высказываний (булева алгебра) названа так по имени  математика Джорджа Буля (1825-1864), внесшего значительный вклад в разработку алгебры логики [7, с 57].

Основное понятие булевой  алгебры – высказывание. Под простым высказыванием понимается повествовательное предложение, о котором можно сказать истинно оно или ложно. Восклицательное или вопросительное предложения не являются высказываниями [2, с 2]. Высказывания обозначаются латинскими буквами и могут принимать одно из двух значений: ЛОЖЬ (0) или ИСТИНА (1). Например, содержание высказывания А: «дважды два равно четырем» истинно А=1, а высказывание В: «три больше пяти» всегда есть ЛОЖЬ. Два высказывания А и В называются равносильными, если они имеют одинаковые значения истинности, записывается А=В [1, 48].

Логические операции

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

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

С помощью логических операций можно вычислить истинность или  ложность некоторого высказывания [3, с 54].

Операцией отрицания А называют высказывание Ā (или ¬А, говорят не А), которое истинно тогда, когда А ложно, и ложно тогда, когда А истинно. Например, если событие А состоит в том, что «завтра будет снег», то Ā «завтра НЕ будет снега», истинность одного утверждения автоматически означает ложность второго. Отрицание – унарная (т.е. для одного операнда) логическая операция. Ей соответствует языковая конструкция, использующая частицу НЕ.

Это правило можно записать в виде следующей таблицы:

А	Ā
0	1
1	0

Такая таблица называется таблицей истинности.

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

Таблица истинности этой операции имеет вид:

 

А	В	А&B
0	0	0
0	1	0
1	0	0
1	1	1

 

Дизъюнкцией (логическим сложением) двух высказываний А и В является новое высказывание С, которое истинно, если истинно хотя бы одно высказывание. Записывается (при этом говорят: С равно А ИЛИ В). Пример: пусть высказывание А состоит в том, что «студент может добираться домой на автобусе», событие В «студент может добираться домой на троллейбусе», событие С «студент добрался домой на автобусе ИЛИ троллейбусе», т.е. данная операция применяется, если два высказывания связываются союзом ИЛИ.

Таблица истинности такой  операции следующая:

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

 

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

Таблица истинности импликации следующая:

А	В	А→В
0	0	1
0	1	1
1	0	0
1	1	1

 

Импликация имеет следующие  свойства:

А→В≠В→А

A→A=1

0→A=1

1→A=A

A→1=1

A→0= Ā

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

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

А	В	А↔В
0	0	1
0	1	0
1	0	0
1	1	1

 

Эквиваленция имеет следующие свойства:

 

1.2. Логические  выражения. Порядок логических  операций

 

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

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

Первыми выполняются операции в скобках, затем операции в следующем  порядке: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция [4, с 52].

В настоящее время существуют достаточно много программных продуктов, с помощью которых можно реализовать различные логические функции. Логические функции широко используются и программе MS Excel. Для вызова необходимо выполнить следующие команды: [Кнопка «Пуск» - Программы – MS Office – Microsoft Excel] и далее команду: [Вставка – Функция]. В открывшемся окне (рис. 1.) «Мастер функций – шаг 1 из 2», выберем «Категория: «Логические» и далее можно выбрать необходимую логическую функцию: ЕСЛИ, И, ИЛИ, ИСТИНА, ЛОЖЬ, НЕ. В этом же окне можно получить справку по каждой из этих функций [7, с 63].

 

Рис. 1. Диалоговое окно «Мастер  функций – шаг 1 из 2»

 

 

1.3. Основные законы  алгебры логики

 

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

Для простоты записи приведем основные законы алгебры логики для  двух логических переменных А и В. Эти законы распространяются и на другие логические переменные [7, с 59].

1. Закон противоречия: ; .

2. Закон исключенного  третьего: ; .

3. Закон двойного отрицания:  ;  .

4. Законы де Моргана:  ; .

5. Законы повторения: ; ; ; .

6. Законы поглощения: ; .

7. Законы исключения констант: ; ; ; ; ; ; ; .

8. Законы склеивания: ; .

9. Законы контрапозиции:  .

Для логических переменных справедливы и общематематические законы. Для простоты записи приведем общематематические законы для трех логических переменных A, B, C:

1. Коммуникативный закон:  ; .

2. Ассоциативный закон:  ; .

3. Дистрибутивный закон:  .

1.4. Табличное и  алгебраическое задание булевских  функций

 

Задать булевскую функцию  можно, определяя ее значение для  всех наборов значений аргументов. Каждый аргумент может иметь два  значения: 0 и 1, следовательно, n аргументов могут принимать различных наборов. Пусть, например, булевская функция имеет три аргумента: , , . Общее число наборов ; зададим таблицу истинности функции, указав для каждого набора значение функции.

№				F
1	0	0	0	0
2	0	0	1	1
3	0	1	0	0
4	0	1	1	1
5	1	0	0	0
6	1	0	1	1
7	1	1	0	0
8	1	1	1	1

 

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