II.3 Элементы математической логики

Примеры:

1. Факторные модели (прогноз производительности труда)

2. Балансовые модели (определение необходимых объемов производства)

3. Игровые модели (определение стратегий при нескольких вариантах развития внешних факторов)

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

5. Модели управления запасами (определение уровня запасов ресурсов, минимизация расходов на доставку и хранение запасов)

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

 

II.3 Элементы математической логики.

Начало исследований в области формальной логики было положено работами Аристотеля в IV в. до нашей эры. Однако математические подходы к этим вопросам впервые были указаны Дж. Булем. В честь него алгебру высказывания называют булевой (булевской) алгеброй, а логические значения − булевыми (булевскими). Основу математической логики составляет алгебра высказываний. Алгебра логики используется при построении основных узлов ЭВМ (дешифратор, сумматор, шифратор).

Алгебра логики оперирует с высказываниями. Под высказыванием понимают повествовательное предложение, относительно которого можно утверждать, истинно оно или ложно. Например, выражение «Расстояние от Москвы до Киева больше, чем от Москвы до Тулы» истинно, а выражение «5 < 3» - ложно.

Высказывания (логические переменные) принято обозначать буквами латинского алфавита (иногда − с индексами): () и т. д. Если высказывание С истинно, это обозначается как С = 1 (С = t, true), а если оно ложно, то С = 0 (С = f, false).

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

Конъюнкция.Соединение двух (или нескольких) высказываний в одно с помощью союза И (OR) называется операцией логического умножения, или конъюнкцией. Эту операцию принято обозначать знаками «Ù, &» или знаком умножения «´,». Сложное высказывание истинно только в том случае, когда истинны оба входящих в него высказывания. Истинность такого высказывания задается табл. 1.7.

Таблица 1.7.

Таблицы истинности конъюнкции и логической суммы высказываний

Конъюнкция	Дизъюнкция
А	В		А	В

 

Дизъюнкция. Объединение двух (или нескольких) высказываний с помощью союза ИЛИ (OR) называется операцией логического сложения, или дизъюнкцией. Эту операцию обозначают знаками «Ú» или знаком сложения «+». Сложное высказывание AÚB истинно, если истинно хотя бы одно из входящих в него высказываний (см. табл. 1.7).

В последнем столбце табл. 1.7 размещены результаты модифицированной операции ИЛИ − Исключающее ИЛИ (XOR). Отличается от обычного ИЛИ последней строкой (см. также рис. 1.1, в).

Инверсия. Присоединение частицы НЕ (NOT) к некоторому высказыванию называется операцией отрицания (инверсии) и обозначается Ā; (или А). Если высказывание А истинно, то Ā; ложно, и наоборот (табл. 1.8).

Таблица 1.8

Таблица истинности отрицания

А	Ā;

 

Следует отметить, что помимо операций И, ИЛИ, НЕ в алгебре высказываний существует ряд других операций. Например, операция эквивалентности (эквиваленции) А~В (АºВ, A ↔ B, eqv B) (табл. 1.9).

Таблица 1.9

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

Эквивалентность	Импликация
А	В	А~В	А	В	А®В

 

Другим примером может служить логическая операция импликацииили логического следования (А®В, A IMP B), иначе говоря, «ЕСЛИ А, то В» (табл. 1.9).

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

Таблица 1.10

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

А	В

Если рассматривать буквы А,В,С … в качестве перемен­ных, принимающих два значения 1 и 0, то в этом случае ло­гическая формула является булевой функцией.

Для правильного вычисления значения логических формул необходимо задать порядок выполнения логичес­ких операций. Сначала выполняется операция отрицания «‾», затем конъюнкция «Ù», дизъюнкция «Ú», затем импликация → и, последней, эквивалентность ↔. Как и в алгебре, скобки необходимы для изменения по­рядка действий (т.е. первыми выполняются операции, заключенные в скобки), а равноправные операции вычисляются слева направо.

Рассмотрим пример вычисления значений логической формулы:

Необходимо сначала определить и , затем выполнить дизъюнкцию Ú , после этого подсчи­тать значение выражения, стоящего в скобках А ↔ Ú , далее выполнить конъюнкцию высказываний Ù и, на­конец, соединить вычисленные значения высказываний левой и правой части исходной формулы с помощью импликации.Порядок выполнения операций будет таков:

Высказывания, у которых таблицы истинности совпадают, называются равносильными. Для обозначения равносильных высказываний используют знак «=» (A = B). Рассмотрим сложное высказывание – табл..

Таблица

Таблица истинности выражения

А		В

 

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

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