Алгебраические понятия в информатике

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

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

Алгебраические понятия в информатике

Введение

алгебраический информатика логика булевский

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

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

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

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

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

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

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

Для выполнения и оформления курсовой работы был использован компьютер 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	1	1
1	0	0
1	1	1

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

А→В≠В→А

A→A=1

→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»

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

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

№	F
1	0	0	0	0
2	0	0	1	1	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 поставим в соответствие выражение ), все элементы соединим знаками дизъюнкции, для рассматриваемого примера получим

.

Построенная функция удовлетворяет заданной таблице истинности. Функция представляет дизъюнктивную нормальную форму (ДНФ). Кроме того, в каждую группу дизъюнкций входят все аргументы функции. Такая ДНФ называется совершенной, а каждая группа дизъюнкции называется конституентой единицы.

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

,

которая также удовлетворяет заданной таблице истинности и представляет собой конъюнктивную нормальную форму, в данном случае совершенную. Каждая конъюнкция называется конституентой нуля [4, с 54-55].

 

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

Логические основы компьютера

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

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

Переключательные схемы

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

Вентили, триггеры и сумматоры

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

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

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

Сумматоры широко используются в арифметико-логических устройствах (АЛУ) процессора и выполняют суммирование двоичных разрядов.

Полусумматор

Cложение в пределах одного разряда (без учета возможной пришедшей единицы из младшего разряда) можно реализовать изображенной ниже схемой, которая называется полусумматором (Рис.1). У полусумматора два входа (для слагаемых) и два выхода (для суммы и переноса). На схеме изображен полусумматор, состоящий из вентилей ИСКЛЮЧАЮЩИЕ ИЛИ и И.

Сумматор

В отличие от полусумматора сумматор учитывает перенос из предыдущего разряда, поэтому имеет не два, а три входа.

Чтобы учесть перенос приходится схему усложнять (Рис. 2). По-сути она получается, состоящей из двух полусумматоров.

Рис. 1. Схема полусумматора

Рис. 2. Схема сумматора

Логические элементы. Вентили

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

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

Соединив пару транзисторов различным способом, получают вентили ИЛИ-НЕ и И-НЕ. Эти вентили принимают уже не один, а два и более входных сигнала. Выходной сигнал всегда один и зависит от входных сигналов. В случае вентиля ИЛИ-НЕ получить высокое напряжение (логическую единицу) можно только при условии низкого напряжении на всех входах. В случае вентиля И-НЕ все наоборот: логическая единица получается, если все входные сигналы будут нулевыми. Как видно, это обратно таким привычным логическим операциям как И и ИЛИ. Однако обычно используются вентили И-НЕ и ИЛИ-НЕ, т.к. их реализация проще: И-НЕ и ИЛИ-НЕ реализуются двумя транзисторами, тогда как логические И и ИЛИ тремя.

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

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

Рис. 3. Основные вентили: НЕ, ИЛИ-НЕ, И-НЕ

Триггер как элемент памяти. Схема RS-триггера

Память (устройство, предназначенное для хранения данных и команд) является важной частью компьютера.

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

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

Разнообразие триггеров весьма велико. Наиболее простой из них так называемый RS-триггер, который собирается из двух вентилей. Обычно используют вентили ИЛИ-НЕ или И-НЕ.триггер на вентилях ИЛИ-НЕтриггер «запоминает», на какой его вход подавался сигнал, соответствующий единице, в последний раз. Если сигнал был подан на S-вход, то триггер на выходе постоянно «сообщает», что хранит единицу. Если сигнал, соответствующий единице, подан на R-вход, то триггер на выходе имеет 0. Не смотря на то, что триггер имеет два выхода, имеется в виду выход Q. (Q с чертой всегда имеет противоположное Q значение.)

Другими словами, вход S (set) отвечает за установку триггера в 1, а вход R (reset) - за установку триггера в 0. Установка производится сигналом, с высоким напряжением (соответствует единице). Просто все зависит от того, на какой вход он подается.

Большую часть времени на входы подается сигнал равный 0 (низкое напряжение). При этом триггер сохраняет свое прежнее состояние.

Выводы

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

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

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

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

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

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

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

 

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

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

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

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

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

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

ФИО сотрудника		Начислено за месяц, руб.		Совокупный доход с начала года, руб.
Васечкина М.М		4 890,00		26 000,00
Иванова И.И.		6 800,00		35 000,00
Кузнецова С.С.		5 350,00		42 000,00
Петрова А.А.		7 500,00		54 000,00
Сидорова К.К.		8 200,00		64 000,00
ФИО сотрудника	Стандартный налоговый вычет на физ. лицо, руб.		Количество детей, на которых предоставляется налоговый вычет		Размер налогового вычета за текущий месяц, руб.
Васечкина М.М	400,00		0
Иванова И.И.	400,00		2
Кузнецова С.С.	400,00		2
Петрова А.А.	400,00		1
Сидорова К.К.	400,00		3

	ООО "Гамма"
					Расчетный период
					с		по
					__.__.20__		__.__.20__
	РАСЧЕТНАЯ ВЕДОМОСТЬ
	Табельный номер	ФИО сотрудника	Начислено за месяц, руб.	НДФЛ, руб.			К выплате, руб.
	0001	Иванова И.И.
	0002	Петрова А.А.
	0003	Васечкина М.М
	0004	Сидорова К.К.
	0005	Кузнецова С.С.
	ИТОГО ПО ВЕДОМОСТИ
	Гл. Бухгалтер____________________________

 

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

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

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

. Лист 1 переименовать в лист с названием Сотрудники.

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

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

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

. Лист 2 переименовать в лист с названием Налоговый вычет.

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

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

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

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

=ЕСЛИ(Сотрудники!C3<50000;'Налоговый вычет'!B3+'Налоговый вычет'!C3*600;'Налоговый вычет'!C3*600)

Размножить введенную в ячейку D3 формулу для остальных ячеек (с D4 по D7) данной графы.

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

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

. На рабочем листе Ведомость MS Excel создать таблицу, в которой будет содержаться расчетная ведомость.

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

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

Рис. 7. Расположение таблицы «Расчетная ведомость» на рабочем листе Ведомость MS Excel.

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

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

=ПРОСМОТР(C8;Сотрудники!$A$3:Сотрудники!$A$7;Сотрудники!$B$3:Сотрудники!$B$7)

Размножить введенную в ячейку D8 формулу для остальных ячеек (с D9 по D12) данной графы.

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

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

=ПРОСМОТР(C8;'Налоговый вычет'!$A$3:$A$7;'Налоговый вычет'!$D$3:$D$7)

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

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

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

=(D8-E8)*13%

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

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

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

=D8-F8

Размножить введенную в ячейку G8 формулу для остальных ячеек (с G9 по G12) данной графы.

. Таким образом, проведя все расчеты, сформировали и заполнили форму расчетной ведомости по заработной плате за текущий месяц, которая представлена на рис. 8.

Рис. 8. Форма расчетной ведомости ООО «Гамма».

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

. На рабочем листе График MS Excel создать краткую таблицу (рис. 9).

Рис. 9. Краткая таблица

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

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

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

1. Андреева Е.В., Фалина И.Н. Системы счисления и компьютерная арифметика: Учебное пособие. М.: БИНОМ. Лаборатория знаний, 2004 - 256с.

. Булгакова И.Н. Дискретная математика. Элементы теории, задачи и упражнения. Часть 2: Учебное пособие для вузов (2-е издание). - Воронеж: Изд-во ВГУ, 2008. - 76 с.

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

. Информатика: учебник/ Б.В. Соболь - Изд. 3-е, дополн. и перераб. - Ростов н/Д: Феникс, 2007. - 446 с.

. Роганов Е.А., Тихомиров Н.Б., Шелехов А.М. Математика и информатика для юристов: Учебник. - М.: МГИУ, 2005. - 364 с.

. Чугайнова А.П. Алгебра высказываний. - http://www.krugosvet.ru (29.03.11.)

. Яшин В.Н. Информатика: аппаратные средства персонального компьютера: Учеб пособие. - М.: ИНФРА-М, 2008. - 254 с.