Алгебра высказываний в информатике

Тип работы:
Контрольная
Предмет:
Программирование


Узнать стоимость

Детальная информация о работе

Выдержка из работы

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

По дисциплине:

«Информатика»

Тема:

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

Омск 2011

Введение

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

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

Для решения экономической задачи в практической части была выбрана среда табличного процессора MS Excel.

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

Так же MS Excel программа, не требующая знаний программирования и проста в использовании для поиска результата нашей задачи.

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

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

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

Логика — наука о правильном мышлении, которая регламентирует формы и методы интеллектуальной познавательной деятельности, формализуемой с помощью языка.

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

Сократ из Афин (469−399 до н.э.) — знаменитый античный философ, учитель Платона, воплощенный идеал истинного мудреца в исторической памяти человечества. Учение Сократа было устным; все свободное время он проводил в беседах с приезжими и местными гражданами, политиками и обывателями, друзьями и незнакомыми на различные темы, например, что есть добро и что — зло, что прекрасно, а что безобразно, что добродетель и что порок, как приобретается знание и т. д.

Булева алгебра (алгебра логики, алгебра суждений) — раздел математики, в котором изучаются логические операции над высказываниями.

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

Элементарные преобразователи информации

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

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

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

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

Ниже приведены условные обозначения (схемы) базовых логических элементов, реализующих логическое умножение (конъюнктор), логическое сложение (дизъюнктор) и отрицание (инвертор).

Структурные формулы и функциональные схемы логических устройств

Сигнал, выработанный одним логическим элементом можно подавать на вход другого логического элемента. Это дает возможность образовывать цепочки из отдельных логических элементов. На рисунке 15 показаны примеры таких цепочек.

Рисунок 1. Конъюнктор, дизъюнктор и инвертор

Рисунок 2. Цепочка из нескольких логических элементов

На рисунке 2 а) элемент ИЛИ (дизъюнктор) соединен с элементом НЕ (инвертор), а на рисунке 2 б) — элемент И (конъюнктор) с элементом НЕ (инвертор). Каждую такую цепочку будем называть логическим устройством: поскольку она состоит из нескольких элементов.

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

На рисунке 3 приведен пример более сложной функциональной схемы.

Рисунок 3. Сложная функциональная схема

Составить логическую схему по функциональной формуле достаточно просто. Например, функциональная схема, изображенная на рисунке 3, имеет два входа A и B. До поступления на конъюнктор B отрицается, а затем отрицается результат логического умножения.

Алгоритм решения такой задачи начинается с построения таблицы истинности. Затем в таблице следует определить одну или несколько строк, с результатом равным 1. На следующем шаге необходимо выписать комбинацию входных переменных, соединенных логическим умножением. Если входная переменная в нужной нам строке имеет значение 0, то она должна войти в логическое выражение с отрицанием. Полученные таким образом конъюнкции требуется логически сложить. Далее полученную формулу нужно сократить с использованием логических законов.

Двоичный одноразрядный сумматор

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

Работа в любом заданном разряде при сложении кодов сводится к сложению трех одноразрядных двоичных чисел. Устройство, которое выполняет такую работу, называется сумматором.

Триггер. Моделирование памяти

Рассмотренные выше преобразователи информации могут работать лишь со словами, записанными с помощью двух символов: 0 и 1. Но преобразование информации имеет больший смысл если сконструировать устройство, запоминающее, вспоминающее и забывающее двоичные слова.

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

Для изготовления такого устройства достаточно иметь логические элементы И, ИЛИ и НЕ. Рассмотрим принцип действия триггера, не вдаваясь в его внутреннюю конструкцию.

Обратимся к так называемому триггеру со счетным входом. Его условное обозначение представлено на рисунке 24. Такой триггер имеет один вход и два выхода, причем, если на первом выходе демонстрируется единица, то на втором 0 и наоборот.

Рисунок 4. Условное обозначение триггера

Триггер работает по следующему принципу. Пусть в некоторый момент времени на выходах демонстрируется 1 и 0. Подадим на вход триггера 1, через доли секунды выходы триггера будут показывать 0 и 1, то есть значения на выходах сменятся на противоположные. Такое положение будет сохраняться до тех пор, пока на вход триггера опять не подадут 1. Другими словами, каждая кратковременная подача сигнала 1 на вход триггера «переключает» его, то есть заставляет демонстрировать на выходах значения, противоположные начальным. Сигналы, снимаемые с выходов триггера, могут является входами для других устройств.

Несколько триггеров, можно объединить в группу, которую называют регистром.

Регистр представляет собой группу триггеров.

Рисунок 5. Регистр из трех триггеров

На рисунке 5 показан регистр, состоящий из трех триггеров. Такой регистр можно использовать для запоминания и демонстрации трехразрядных чисел или двоичных слов, состоящих из трех букв. Регистр, состоящий из n триггеров можно рассматривать как простейшее запоминающее устройство (ЗУ) для n-разрядных двоичных слов. Оперативная память компьютера конструируется в виде набора регистров. Каждый регистр представляет собой ячейку памяти, каждая ячейка памяти в ЗУ имеет свой номер. Из всего вышесказанного можно сделать вывод, что компьютер состоит из огромного числа отдельных логических элементов, образующих все узлы и память.

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

2. 1 Общая характеристика задачи

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

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

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

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

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

алгебра информатика дизъюнктор налоговый

Ф.И.О. сотрудника

Начислено за месяц, руб.

Совокупный доход с начала года, руб.

Васечкина М.М.

4 890,00

26 000,00

Иванова И.И.

6800,00

35 000,00

Кузнецова С.С.

5 350,00

42 000,00

Петрова А.А.

7 500,00

54 000,00

Сидорова К.К.

8 200,00

64 000,00

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

Ф.И.О. сотрудника

Стандартный налоговый вычет на физ. лицо, руб.

Количество детей, на которых предоставляется налоговый вычет

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

Васечкина М.М.

400,00

Иванова И.И.

400,00

2

Кузнецова С.С.

400,00

2

Петрова А.А.

400,00

1

Сидорова К.К.

400,00

3

Рис. 4.2. Размер налоговых вычетов, предоставляемых сотрудникам в текущем месяце

ООО «Гамма»

Расчетный период

с

по

__. __20__

__. __. 20__

РАСЧЕТНАЯ ВЕДОМОСТЬ

Табельный номер

Ф.И.О. сотрудника

Начислено за месяц, руб.

Размер налогового вычета, руб.

НДФЛ, руб.

К выплате, руб.

0001

Иванова И.И.

0002

Петрова А.А.

0003

Васечкина М.М.

0004

Сидорова К.К.

0005

Кузнецова С.С.

ИТОГО ПО ВЕДОМОСТИ

Гл. бухгалтер

Рис. 4.3. Расчетная ведомость

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

1. Запустить табличный процессор MS Excel.

2. Создать книгу с именем «Гамма»

3. Лист 1 переименовать в лист с названием Данные.

4. На рабочем листе Данные MS Excel создать таблицу данных для расчета налоговых вычетов.

5. Заполнить таблицу данных для расчета налоговых вычетов исходными данными (рис. 1).

Расположение таблицы «Данные для расчета налоговых вычетов» на рабочем листе Данные MS Excel

6. Лист 2 переименовать в лист с названием Размер.

7. На рабочем листе Размер MS Excel создать таблицу, в которой будет содержаться размер налоговых вычетов, предоставляемых сотрудникам в текущем месяце.

8. Заполнить таблицу «Размер налоговых вычетов» исходными данными (рис. 2).

9. Заполнить графу Размер налогового вычета за текущий месяц, руб. таблицы «Размер налоговых вычетов, предоставляемых сотрудникам в текущем месяце», находящейся на листе Размер следующим образом:

Занести в ячейку D2 формулу:

=B2+C2*600 и размножить введенную в ячейку D2 формулу до ячейки D4 включительно.

Расположение таблицы «Размер налоговых вычетов, предоставляемых сотрудникам в текущем месяце» на рабочем листе Размер MS Excel

10. Лист 3 переименовать в лист с названием Ведомость.

11. На рабочем листе Ведомость MS Excel создать форму ведомости.

12. Заполнить графу Начислено за месяц, руб. формы «Расчетная ведомость», находящаяся на листе Ведомость следующим образом:

В ячейку С8 занести формулу:

= Данные! B3;

В ячейку С9 занести формулу:

=Данные! B5;

В ячейку С10 занести формулу:

=Данные! B2;

В ячейку С11 занести формулу:

=Данные! B6;

В ячейку С12 занести формулу:

=Данные! B4.

13. Заполнить графу Размер налогового вычета, руб. следующим образом:

В ячейку D8 занести формулу:

=Размер! D3

В ячейку D9 занести формулу:

=Размер! D5

В ячейку D10 занести формулу:

=Размер! D2

В ячейку D11 занести формулу:

=Размер! D6

В ячейку D12 занести формулу:

=Размер! D4

14. Заполнить графу НДФЛ, руб. следующим образом:

В ячейку E12 занести формулу:

=(C8-D8)*13% и размножить введенную в ячейку Е8 формулу для остальных ячеек (с Е9 по Е12) данной графы.

15. Заполнить графу К выплате, руб. следующим образом:

В ячейку F8 занести формулу:

=C8-E8 и размножить введенную в ячейку F8 формулу для остальных ячеек (с F9 по F12) данной графы.

Форма расчетной ведомости фирмы ООО «Гамма»

16. Лист 4 переименовать в лист с названием График.

17. На рабочем листе График MS Excel создать краткую таблицу, данные взять из формы «Расчетная ведомость» (рис. 4).

Краткая таблица

18. Результаты вычислений представить графически (рис. 5).

Графическое представление результатов вычислений

Заключение

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

Законы Буля: Закон двойного отрицания, закон коммутативности конъюнкции, законы ассоциации конъюнкции, закон дистрибутивности конъюнкции, алгебра логики названная булевой алгеброй. Общий вид булевой функции: F (Х1, Х2,… Xn), где Хi — произвольная величина. Функция может принимать значения либо 0, либо 1. Задача анализа следующая: по именующейся электронной схеме составить логическую функцию путём формальных преобразований при помощи законов алгебры; минимизировать эту функцию и реализовать её меньшим количеством электронных элементов.

Задачи синтеза схем — по логической функции, описывающий некоторый процесс, определить количество необходимых элементов схемы и возможные способы их реализации. Кроме описанных двух задач анализа и синтеза схем компьютера, математическая логика применяется при составлении программ и при формулировании логических условий, применений пакетов прикладных программ. Часто логическая функция задаётся не с помощью единичного выражения, а табличным способом. Существует алгоритм, по которому таблично заданную функцию можно преобразовать к виду логического выражения.

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

1. Информатика в экономике: Учеб. пособие /Под ред. проф. Б. Е. Одинцова, проф. А. Н. Романова. — М.: Вузовский учебник, 2008. — 478 с.

2. Босова Л. Л. Арифметические и логические основы ЭВМ. Серия «Информатика в школе». — М.: Информатика и образование, 2000. — 208 с.

3. Логика для всех — http: //ntl. narod. ru/logic/course/valentin. html, (05. 05. 09)

4. Полунов Ю. Л. Алгебра для компьютера — http: //www. computer-museum. ru/frgnhist/boologic. htm, (05. 05. 09)

5. Решение задачи с помощью алгебры логики. — Российская Академия Образования, Лаборатория дистанционного обучения, Институт Содержания и Методов Обучения — http: //www. ioso. ru/distant/do/curse/logic/ logic9. htm, (05. 05. 09)

6. Угринович Н. Информатика и информационные технологии. Учебник для 10−11 классов. — М.: Лаборатория Базовых Знаний. 2003.

ПоказатьСвернуть
Заполнить форму текущей работой