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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение:

НЕ    Операция, выражаемая словом "не", называется отрицанием и обозначается чертой над высказыванием.  Высказывание   истинно, когда A ложно, и ложно, когда A истинно.   Пример. "Луна — спутник Земли" (А); "Луна — не спутник Земли" ( ).

И    Операция, выражаемая связкой "и", называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой " ^. " (может также обозначаться знаками /\ или &). Высказывание А ^. В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание   "10 делится на 2 и 5 больше 3"   истинно, а высказывания     "10 делится на 2 и 5 не больше 3",     "10 не делится на 2 и 5 больше 3",     "10 не делится на 2 и 5 не больше 3"     —   ложны.

ИЛИ    Операция, выражаемая связкой "или" (в неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны.   Например, высказывание   "10 не делится на 2 или 5 не больше 3"   ложно,     а высказывания "10 делится на 2 или 5 больше 3",   "10 делится на 2 или 5 не больше 3",   "10 не делится на 2 или 5 больше 3"     —   истинны.

ЕСЛИ-ТО   Операция, выражаемая связками   "если ..., то",  "из ... следует",  "... влечет ...",  называется импликацией (лат. implico — тесно связаны) и обозначается знаком → . Высказывание А→В  ложно тогда и только тогда, когда  А  истинно,  а  В  ложно.

Каким же образом импликация связывает  два элементарных высказывания? Покажем это на примере высказываний: "данный четырёхугольник — квадрат" (А) и "около данного четырёхугольника можно описать окружность" (В). Рассмотрим составное высказывание А→В , понимаемое как "если данный четырёхугольник квадрат, то около него можно описать окружность". Есть три варианта, когда высказывание А→В   истинно:

1. А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность;
2. А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника);
3. A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность.

Ложен только один вариант, когда А истинно, а В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

В обычной речи связка   "если ..., то" описывает причинно-следственную связь между высказываниями. Но в логических операциях смысл высказываний не учитывается. Рассматривается только их истинность или ложность. Поэтому не надо смущаться "бессмысленностью" импликаций, образованных высказываниями, совершенно не связанными по содержанию.   Например, такими: "если президент США — демократ, то в Африке водятся жирафы",   "если арбуз — ягода, то в бензоколонке есть бензин".

РАВНОСИЛЬНО   Операция, выражаемая связками "тогда и только тогда", "необходимо и достаточно", "... равносильно ...", называется эквиваленцией или двойной импликацией и обозначается знаком  ↔  или  ~.   Высказывание  А↔В  истинно тогда и только тогда, когда значения А и В совпадают.       Например, высказывания     "24 делится на 6 тогда и только тогда, когда 24 делится на 3",    "23 делится на 6 тогда и только тогда, когда 23 делится на 3"   истинны,   а высказывания   "24 делится на 6 тогда и только тогда, когда 24 делится на 5",   "21 делится на 6 тогда и только тогда, когда 21 делится на 3"   ложны.

Высказывания А и В, образующие составное высказывание А↔В , могут быть совершенно не связаны по содержанию, например:     "три больше двух" (А),     "пингвины живут в Антарктиде" (В). Отрицаниями этих высказываний являются высказывания   "три не больше двух" ( ),   "пингвины не живут в Антарктиде" ( ).   Образованные из высказываний А и В составные высказывания   ↔    и А↔В истинны, а высказывания   A↔    и ↔  B — ложны.

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

Импликацию можно выразить через  дизъюнкцию  и  отрицание: А↔ В = v В. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию: А↔ В = ( v В) . ( v А).

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

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

 

 

1.4. Логическая формула.

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

Определение логической формулы: Всякая логическая переменная и символы "истина" ("1") и "ложь" ("0") — формулы. Если  А и В — формулы, то , А . В, А v В ,  А→B , А↔В   —  формулы. Никаких других формул в алгебре логики нет.

В качестве примера  рассмотрим высказывание "если я куплю яблоки или абрикосы, то приготовлю фруктовый пирог". Это высказывание формализуется в виде (A v B) →C. Такая же формула соответствует высказыванию   "если Игорь знает английский или японский язык, то он получит место переводчика".

Как показывает анализ формулы (A v B) →C, при определённых сочетаниях значений переменных A, B и C она принимает значение "истина", а при некоторых других сочетаниях — значение "ложь" (разберите самостоятельно эти случаи). Такие формулы называются выполнимыми.

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

В качестве другого  примера рассмотрим формулу А ^. , которой соответствует, например, высказывание "Катя самая высокая девочка в классе, и в классе есть девочки выше Кати". Очевидно, что эта формула ложна, так как либо А, либо обязательно ложно. Такие формулы называются тождественно ложными формулами или противоречиями. Высказывания, которые формализуются противоречиями, называются логически ложными высказываниями.

Если две  формулы А и В одновременно, то есть при одинаковых наборах значений входящих в них переменных, принимают  одинаковые значения, то они называются равносильными.

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

 

 

Заключение.

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

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

Объектами алгебры высказываний являются высказывания. Высказывание - это истинное или ложное повествовательное  предложение. Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием. Например, предложение "Луна — спутник Земли" есть простое высказывание, предложение "Не сорить!" не является высказыванием.

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

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

 

 

Глава 2:  Практическая часть.

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

Наименование  экономической задачи: расчет отчислений налога на доходы физических лиц за текущий месяц и составление расчетной ведомости. Цель решения задачи – определение НДФЛ и суммы к выплате. Поставленная задача решается в бухгалтерии предприятия.

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

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

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

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

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

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

 

Таблица 2.1.1. Данные для расчета налоговых вычетов

ФИО сотрудника	Стандартный налоговый  вычет на физ. лицо, руб.	Количество  детей, на которых предоставляется  налоговый вычет	Размер налогового вычета за текущий месяц, руб.
Васечкина М.М.	400,00
Иванова И.И.	400,00	2
Кузнецова С.С.	400,00	2
Петрова А.А.	400,00	1
Сидорова К.К.	400,00	3

 

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

 

ООО "Гамма"

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

с

по

_._.20_

_._20_

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

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

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

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

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

НДФЛ, руб.

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

0001

Иванова И.И.

0002

Петрова А.А.

0003

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

0004

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

0005

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

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

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

______________________________________