Раздел 8. Законы и тождества Булевой алгебры Тема 8.1.Формулы Булевой алгебры

Определение:Алфавитомназывается любой непустой набор символов. Элементы этого набора называются символами алфавита.

Определение:Словомв алфавитеназывается произвольная конечная (возможно пустая) последовательность символов из. Фиксируем некоторый конечный или счётный алфавит переменных.

Определение:Формулаалгебры логики определяется следующим образом (индуктивное определение):

• любая логическая переменная есть формула;

• если – формула, то– формула;

• если и– формулы, то– тоже формулы;

• других формул нет.

Определение:Подформулойформулыназывается любое подслово слова, которое само является формулой.

Для сокращения записи формул обычно принимаются следующие соглашения:

• если часть формулы заключена в скобки, то сначала производится действие в скобках;

• если над частью формулы стоит знак отрицания, то он заменяет собой скобки, в которые заключена эта часть формулы.

Принят следующий порядок выполнения операций:

• отрицание;

• конъюнкция;

• дизъюнкция;

• импликация и эквивалентность в порядке их записи.

Определение:Формула называетсятождественно истиннойилитавтологией, если она реализует функцию «тождественная единица», и тождественно ложной илипротиворечием, если 0.

Тема 8.2.Законы и тождества Булевой алгебры

Определение:Пусть логические формулы составлены из простейших высказываний. Если на любом наборе значений простых высказываний значенияисовпадают, тоиназываютсятождественными.

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

0	0	0	0	1	1	1	1	1
0	0	1	1	0	1	1	0	0
0	1	0	1	0	1	0	1	0
0	1	1	1	0	1	0	0	0
1	0	0	1	0	0	1	1	0
1	0	1	1	0	0	1	0	0
1	1	0	1	0	0	0	1	0
1	1	1	1	0	0	0	0	0

Пример 8.1:Составим таблицу истинности следующей формулы:

0	0	0	1	1	1
0	0	1	1	1	1
0	1	0	1	0	0
0	1	1	1	1	1
1	0	0	0	1	0
1	0	1	0	1	0
1	1	0	1	0	0
1	1	1	1	1	1

Пример 8.2:Составим таблицу истинности следующей формулы:

0	0	0	0	0	0	0
0	0	1	1	1	1	0
0	1	0	0	0	1	0
0	1	1	0	0	1	0
1	0	0	0	1	1	1
1	0	1	1	1	1	1
1	1	0	0	1	1	1
1	1	1	0	1	1	1

Как видите, построение таблиц истинности трудоёмкий, но тривиальный процесс.

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

– закон исключённого противоречия

– закон исключённого третьего

Законы идемпотентности:

Законы де Моргана

Закон навешивания двойного отрицания

Закон контрапозиции

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

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

– закон исключенного третьего, его часто объединяют с законом исключенного противоречия, от латинского (tertium non datur). Этот закон сформулирован Аристотелем. В «Метафизике» он писал: «Равным образом не может быть ничего посередине между двумя противоречащими друг другу суждениями, но об одном субъекте. Всякий отдельный предикат необходимо либо утверждать, либо отрицать».

Действительно, нельзя одновременно высказать две такие мысли об определённом объекте, например, числе, и обе мысли назвать истинными: «Это число простое» и «Это число непростое» и при этом иметь в виду одно и тоже число. Не нужно большого труда, чтобы определить, что только одна из них истинна. Например, «7 есть простое число» и «7 не есть простое число» - одно из этих высказываний обязательно ложно, третья же возможность обязательно исключается.

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

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

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

Когда одно из высказываний что-либо утверждает относительно единичного предмета или явления, а другое что-либо отрицает относительно этого же предмета или явления, взятого в одно и то же время и в одном и том же отношении. Например: «Нева впадает в Балтийское море», «Нева не впадает в Балтийское море». Оба эти высказывания не могут быть одновременно истинными или ложными, и невозможно никакое третье, среднее высказывание. Если кто-то выскажет, что «Нева впадает в Белое море», то такое высказывание не будет являться третьим, т.к. оно фактически совпадет со вторым.

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

Пусть имеется два таких высказывания «Все колхозы нашего района ввели правильный севооборот» и «Ни один колхоз нашего района не ввёл правильного севооборота».

В этом случае из ложности одного высказывания, например 1, не следует истинность 2 высказывания. Может оказаться, что истинно третье, промежуточное высказывание «Некоторые колхозы нашего района не ввели правильного севооборота». На эту тонкость применения закона указывал ещё Аристотель. Такие высказывания он называл противоположными.

Когда одно из высказываний что-либо утверждает относительно всего класса предметов или явлений, а другое высказывание это же самое отрицает относительно части предметов или явлений этого же класса. Такими высказываниями будут, например, «Все рыбы дышат жабрами» и «Некоторые рыбы не дышат жабрами». Одно из таких высказываний обязательно истинно, а другое ложно, а третьего быть не может. Оба эти высказывания не могут быть истинными или ложными одновременно.

Закон исключённого третьего распространяется и на тот случай, если одно из высказываний что-либо отрицает относительно всего класса предметов, а другое высказывание это же самое утверждает относительно части предметов этого класса. Оба эти высказывания не могут быть истинными одновременно.

Пример 8.3:между героем романа Тургенева «Рудин» и Пегасовым возник спор о существовании убеждений.

Вот часть их диалога

«– Прекрасно! – промолвил Рудин. – Стало быть, по-вашему, убеждений нет.

– Нет и не существует.

– Это Ваше убеждение?

– Да.

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

Все в комнате улыбнулись и переглянулись».

Теперь выпишем законы Булевой алгебры:

Коммутативный закон Ассоциативный закон

Дистрибутивный закон. Законы поглощения

На первый взгляд они не очевидны, докажем законы поглощения:

0	0	0	0	0	0
0	1	1	0	0	0
1	0	1	1	0	1
1	1	1	1	1	1

Выпишем приведённые ранее выражения операций через &,,