ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ  ИНСТИТУТ

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

КУРСОВАЯ  РАБОТА

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

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

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

                                                  Винокурова Ольга Юрьевна

                                                                   Специальность                            МО

                                                      Группа                                    301

                                                                  № зачетной книжки     №09МПД48118

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

                                                                          Шмелев Вячеслав Викторович   
 
 
 
 
 
 
 
 
 
 

Москва 2011 

Содержание

Введение 3

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

1.1. Основные понятия. 4

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

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

1.4. Примеры применения алгебры высказываний в информатике Ошибка! Закладка не определена.

Заключение Ошибка! Закладка не определена.

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

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

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

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

Введение 
 

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

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

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

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

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

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

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

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

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

1. Теоретическая часть
1. Основные понятия.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

А→В≠В→А

A→A=1

0→A=1

1→A=A

A→1=1

A→0= Ā 

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

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

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

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

Двоичная  система счисления.

         Двоичная система  счисления была придумана математиками и философами ещё до появления  компьютеров (XVII — XIX вв.). Мысль о  двоичной системе принадлежит Лейбницу, который полагал, что при трудных  исследованиях в теории чисел  она может иметь большие преимущества перед десятичной системой. Кроме  того, при всяких арифметических операциях  действия над числами, написанными  в бинарной системе, облегчаются  в высшей степени.

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

         В двоичной системе не существует "таблицы  сложения", которую нужно бы было запоминать, так как "перенос в  старший разряд" начинается с 1 + 1 = 10. При сложении больших чисел  необходимо лишь складывать по столбцам или разрядам, как в десятичной системе, памятуя лишь о том, что  как только сумма в столбце  достигает числа 2, двойка переносится  в следующий столбец (влево) в  виде единицы старшего разряда.

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

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

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

         Деление "углом" в двоичной системе выполняется  быстро, при этом нет необходимости  в пробных делителях. По существу, деление становится своего рода непрерывным  вычитанием, которое отличается необычайной "прозрачностью".

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

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

         Выдающийся математик  Лейбниц говорил: "Вычисление с  помощью двоек... является для науки  основным и порождает новые открытия... При сведении чисел к простейшим началам, каковы 0 и 1, везде появляется чудесный порядок". Позже двоичная система была забыта, и только в 1936 — 1938 годах американский инженер  и математик Клод Шеннон нашёл замечательные применения двоичной системы при конструировании электронных схем. Рассмотрим пример представления числа в двоичной системе счисления:

         Пример 1. Переведём число 2000 в двоичную систему.

         1. Делим 2000 на основание  новой системы  счисления — 2:

         2000:2=1000(0 - остаток),

         1000:2=500(0),

         500:2=250(0),

         250:2=125(0),

         125:2=62(1),

         62:2=31(0),

         31:2=15(1),

         15:2=7(1),

         7:2=3(1),

         3:2=1(1)

         2. Собираем последнее  частное от деления  (всегда равно  1) и остатки от  деления и записываем  их по порядку,  начиная снизу  :

         2000₁₀==11111010000₂

Для проверки переведём  полученное число  в десятичную систему  счисления, для этого:

1. Выделим двоичные  разряды числа,  то есть, степени  числа 2, начиная  с 0-й:

2. Запишем сумму  произведений 0 и  1 на соответствующую  степень числа  2 (см. представление  числа в р-ричной  системе счисления):

0*2⁰+0*2¹+0*2²+0*2³+l*2⁴+0*2⁵+l*2⁶+l*2⁷+l*2⁸+l*2⁹+l*210= 16+64+128+256+512+1024=2000

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

Из этого  следует два вывода:

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

     Заключение 
 
 

      В результате работы были выполнены поставленные задачи.

      Выявлено  основное понятие булевой алгебры  – высказывание. Высказывания обозначаются латинскими буквами и могут принимать  одно из двух значений: ЛОЖЬ (обозначается 0) или ИСТИНА (обозначается 1).

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

      Был выявлен порядок логических операций. Первыми выполняются операции в  скобках, затем операции в следующем  порядке: отрицание, конъюнкция и дизъюнкция слева направо, импликация, эквиваленция.

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

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

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

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

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

    В бухгалтерии предприятия ООО  «Гамма» производится расчет налоговых  вычетов, предоставляемых сотрудникам, и формирование платежных ведомостей. Данные для выполнения расчета налоговых  вычетов приведены на рис. 1. Стандартный  налоговый вычет предоставляется  каждому сотруднику в размере 400 руб. до тех пор, пока совокупный доход  с начала года не превысит 50000 руб., налоговый  вычет на ребенка предоставляется  в размере 600 руб. НДФЛ – налог  на доходы физических лиц (13%) рассчитывается с начисленной суммы за минусом  размера налогового вычета.

    1. Построить таблицы по приведенным  ниже данным.

    2. Выполнить расчет размера налогового  вычета, предоставляемого сотрудникам  в текущем месяце, результаты  вычислений представить в виде  таблицы (рис. 2.).

    3. Сформировать и заполнить форму  расчетной ведомости по заработной  плате за текущий месяц (рис. 3).

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

    Рис. 1. Данные для расчета налоговых  вычетов