§ 5.1. Основные понятия алгебры логики

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

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

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

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

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

Высказывания — элементы области алгебры логики и поэтому наряду со словом «высказывание» далее часто будет употребляться термин «элемент». В результате применения операций конъюнкции, дизъюнкции и отрицания к некоторому исходному набору элементов возникают новые комбинированные элементы которые называются булевыми функциями от элементов Чтобы подчеркнуть зависимость функций от данных элементов, часто пишут:

Рассмотрим две особо важные булевы функции: выражающие определенные связи между элементами

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

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

Среди всех булевых функций можно выделить функции, остающиеся истинными, безотносительно к тому, какие значения истинности принимают входящие в эти функции элементы, например , а также (5.1). Такие функции называют универсально истинными или тавтологиями. Поскольку все тавтологии не различаются между собой с точки зрения значений истинности, то их обозначают через Следовательно, можно записать и т. д. Отрицание I, т. е. I — универсально ложный элемент, обозначается через 0. Легко видеть, что для любого X соотношения тавтологии, так как не зависят от значения истинности Необходимо отличать тавтологически истинные элементы от функций, которые истинны вследствие сделанных предположений или физических законов. Первые

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

Приведем основные правила булевой алгебры:

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

Некоторые из этих формул могут быть выведены из других формул, например 19 устанавливается при помощи 3, 4, 6, 7, 12, 15 и 17 следующим образом: