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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

 

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

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

Сумматор

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

Разнообразие триггеров  весьма велико. Наиболее простой из них так называемый RS-триггер, который собирается из двух вентилей. Обычно используют вентили ИЛИ-НЕ или И-НЕ.

RS-триггер на  вентилях ИЛИ-НЕ

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

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

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

Рис. 4. Схема RS-триггера на вентилях ИЛИ-НЕ

 

 

 

 

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

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

Вариант 7

Торговое предприятие  ООО «Электрон» осуществляет розничную  продажу бытового оборудования и  средств вычислительной техники (СВТ). Для продвижения товара предприятие  организует рекламную кампанию, на осуществление которой формируется  бюджет в зависимости от объема продаж и показателя отчислений на рекламу. Данные, на основании которых выполняется расчет рекламного бюджета предприятия, приведены на рис. 7.1 и 7.2.

Для решения задачи необходимо следующее.

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

2. Рассчитать объем продаж  предприятия по каждому месяцу  за текущий год (рис. 7.1).

3. Организовать межтабличные  связи для автоматического формирования рекламного бюджета с использованием функций ВПР или ПРОСМОТР.

4. Сформировать и заполнить  итоговую таблицу, содержащую  расчет рекламного бюджета предприятия ООО «Электрон» по месяцам и за текущий год (рис. 7.3).

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

Объем продаж

Месяц	Объем продаж бытовой  техники, руб.		Объем продаж СВТ, руб.		Объем продаж всего за месяц, руб.
Январь		121 562		278 365
Февраль		165 897		456 325
Март		459 325		258 963
Апрель		256 987		333 478
Май		128 965		236 985
Июнь		222 655		325 654
Июль		179 258		289 741
Август		258 963		569 258
Сентябрь		165 321		456 921
Октябрь		147 852		324 512

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

 

Информационная  модель решения задачи.

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

Ведомость объема продаж

Таблица показателей отчисления на рекламу

 

 

 

                                                            

Таблица. Расчет рекламного бюджета  предприятия

                                                             

Где диаграмма – это  графическое представление результата расчета рекламного бюджета по месяцам.

 

 

Аналитическая модель решения задачи.

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

• Объем продаж всего за месяц (табл.1). Для этого необходимо сложить столбцы объем продаж бытовой техники и объем продаж СВТ.
• Рассчитать рекламный бюджет по месяцам. Для этого столбец объем продаж (всего за месяц) надо перемножить соответственно на показатели рекламных отчислений.
• Рассчитать рекламный бюджет за год. Для этого надо найти сумму всех строк  рекламного бюджета по месяцам.

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

Решение задачи в Exсel.

1. Запустим программу  Excel.

2. Заполним таблицу «Объем  продаж».

3. Заполним столбец «Объем  продаж всего за месяц». Для  этого в ячейку D4 введем формулу: (=B4+C4).

И растянем эту ячейку вниз до D15.

 

4. Создадим таблицу «Показатели  отчислений на рекламу».

 

 

 

 

5. Составим таблицу «Рекламный  бюджет».

 

5. Заполним таблицу «Рекламный  бюджет» с помощью создания  связи между таблицами. Для  этого выделим ячейку B28 и нажмем на функцию. Выберем там функцию ПРОСМОТР.

 

 

Выделим необходимые нам  диапазоны. После чего автоматически  значения из табл. «Объем продаж» подставятся  в табл. «Рекламный бюджет».

 

 

6. Тоже самое проделаем со столбцом «показатели отчислений на рекламу».

 

 

 

 

7. В итоге получаем  таблицу.

8. Вычислим строку всего  за год. 

Для этого выделим столбцы  «объем продаж всего за месяц» и  «показатели отчислений на рекламу» и нажмем функцию сумма (∑).

 

 

9. Вычислим столбец Рекламный  бюджет. Для этого перемножим  столбцы «объем продаж всего  за месяц» и «показатели отчислений  на рекламу». Введем формулу (=В28*С28). Растянем значения до конца.  И получим.

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

Для этого зайдем в вкладку  Вставка – Гистограмма- Выбрать данные.

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

 

Анализ полученных результатов.

Таким образом, формирование сводных таблиц на основе «Ведомости объема продаж», «Показателей отчислений на рекламу» позволяет решить поставленную задачу – отслеживать объемы продаж и контролировать рекламный бюджет. Создание различных диаграмм (гистограмм, графиков) на основе данных сводных таблиц средствами MS Excel позволяет наглядно представлять результаты обработки информации.

 

 

 

 

 

Заключение

 

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

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

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

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

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

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

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

 

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

 

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