Введение в математическую логику (стр. 2 )

в) Либо студент сдает сессию, либо его отчисляют.

Решение

а) Альтернативная дизъюнкция, так как предполагается одно условие из двух, но не оба вместе.

б) Дизъюнкция (хотя, если говорящий «честен», то возможна альтернативная дизъюнкция).

в) Альтернативная дизъюнкция.

Пример 1.5

Тождественно ли истинны высказывания и формулы:

а) Если Земля столкнется с Солнцем, то пойдет дождь;

б) ;

в) .

Решение

а) Тождественно-истинно, так как посылка – ложна, а из лжи следует все что угодно.

б) Импликация ложна в единственном случае, когда из истины следует ложь. Если истинно, то P и Q принимают одинаковые истинностные значения. Значит, импликация истинна и внешняя импликация – тоже. Если ложно, то внешняя импликация всегда истинна. Итак, вся формула – тождественно-истинна.

По-другому исследование можно провести, построив таблицу истинности для нашей формулы. Построим сокращенную таблицу истинности (т. е. для каждой переменной будем отводить только по одному столбцу, в месте ее первого вхождения в формулу; для каждой логической связки – тоже по одному столбцу, используя при этом запись самой формулы):

Здесь приведена сокращенная таблица истинности формулы: сначала заполняются столбцы возможных значений P и Q, таких наборов будет ; затем – столбцы для «внутренних» логических связок (эквивалентность и правая импликация) и, наконец, столбец для внешней (левой) импликации, который и дает истинностные значения всей формулы. Цифры под таблицей показывают порядок заполнения столбцов. Поскольку на любых наборах истинностных значений переменных формула принимает только значение 1, то она является тождественно-истинной.

в) Рассмотрим сразу таблицу истинности:

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

Пример 1.6

Составить таблицы истинности для формул:

а) ;

б) ;

в) ;

г) .

Решение

а)

б)

в)

г)

Задачи

1.1. Записать в виде формул логики высказываний, обозначив за переменные элементарные высказывания:

а) достаточные условия экстремума в точке для функции f(x);

б) необходимые условия экстремума в точке для функции f(x);

в) необходимые и достаточные условия экстремума в точке для функции f(x);

1.2. Определить, является ли данная последовательность формулой:

а) ;

б) ;

в) ;

г) .

1.3. Сколькими способами можно расставить скобки в последовательности, чтобы получилась формула:

а) ;

б) ?

1.4. Выписать все подформулы формулы:

а) ;

б) .

в) ;

г) .

1.5. Составить таблицы истинности для формул;

а) ;

б) ;

в) ;

г) .

1.6. Доказать выполнимость формул:

а) ;

б) ;

в) .

1.7. Доказать тождественную истинность формул:

а) ;

б) ;

в) ;

г) ;

д) ;

е) ;

ж) ;

з) .

1.8. При каких значениях переменных X, Y, Z, U, V, W следующие формулы ложны:

а) ;

б)

;

в) ;

г) ;

д) ?

1.2. Упрощение формул. Тождественные преобразования.
Доказательство равносильности, тождественной
истинности и тождественной ложности
формул и булевых функций

Сводка теории

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

Во-первых, в отдельно стоящих формулах (или если границы формулы ясны из контекста) можно опускать внешние скобки.

Во-вторых, как и арифметические операции, связки и кванторы можно упорядочить по их «силе», т. е. расположить в определенном порядке, считая, что те символы, которые в этом порядке находятся правее, «связывают сильнее», т. е. их следует выполнять в первую очередь:

Таким образом, дизъюнкция и конъюнкция связывают сильнее, чем импликация, но слабее, чем отрицание. Конъюнкция связывает сильнее дизъюнкции. Слабее всего связывает эквивалентность. Равноправны в отношении связывания кванторы (об этом подробно в разделе 2), они связывают сильнее, чем любые логические связки.

По сравнению с общим определением формулы формального языка для формул логики высказываний (далее в этом разделе – просто формул) внесем следующие уточнения:

1)  в качестве пропозициональных букв (индивидных переменных) будем рассматривать только простые высказывания x, y, z, ... B, B={1,0};

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

При таком подходе любая формула будет полностью определяться своей таблицей истинности.

Булевой функцией (или функцией алгебры логики, логической функцией) называется всякая функция n переменных (n = 1, 2, ...) с областью определения , множество значений которой содержится в B.

Любую булеву функцию можно, очевидно, задать таблицей истинности точно такого же вида, как те таблицы, которые сопоставляются формулам. Если таблица истинности, задающая булеву функцию f, совпадает с таблицей истинности некоторой формулы Ф, то говорят, что формула Ф представляет (или задает, или реализует ) функцию f.

Две формулы Ф и называются равносильными (что обозначается Ф ), если они представляют одну и ту же булеву функцию.

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

Булевы функции (от любого числа переменных), принимающие значение 1 независимо от значений аргументов, называются (как и реализующие их формулы) тавтологиями (или тождественно-истинными).

Булевы функции (и реализующие их формулы), всегда принимающие значение 0, называются противоречиями (или тождественно-ложными).

Убедиться в тождественной истинности или тождественной ложности конкретной формулы можно по той же таблице истинности (итоговый столбец таблицы будет содержать только соответствующую константу).

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

	(ассоциативность дизъюнкции)	(I.1)
	(коммутативность дизъюнкции)	(I.2)
	(ассоциативность конъюнкции)	(I.3)
	(коммутативность конъюнкции)	(I.4)
	(дистрибутивность конъюнкции по отношению к дизъюнкции)	(I.5)
	(дистрибутивность дизъюнкции по отношению к конъюнкции)	(I.6)
	(идемпотентность или «законы поглощения»)	(I.7) (I.8)
	(«закон отрицания отрицания»)	(II.1)
	(«законы де Моргана»)	(II.2) (II.3)
		(III.1)
		(III.2)
	(«закон контрапозиции»)	(III.3)
		(IV.1)
		(IV.2)
		(IV.3)
		(IV.4)
		(IV.5)
		(IV.6)
	(«закон противоречия»)	(IV.7)
	(«закон исключенного третьего»)	(IV.8)

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

Во всякой алгебре (в том числе и в булевой алгебре функций) соотношение
Ф Ф означает, что формулы Ф и Ф описывают одну и ту же булеву функцию f. Следовательно, если какая-либо формула Ф содержит Ф в качестве подформулы, то замена Ф на Ф не изменяет элемента булевой алгебры f, над которым производятся операции в формуле Ф; поэтому Ф', полученная из Ф такой заменой, равносильна Ф. Это утверждение есть правило замены подформул, которое позволяет по имеющимся равносильностям получать формулы, равносильные данной.

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

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

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

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

Примеры

Пример 1.7

Доказать равносильность формул, используя их таблицы истинности:

а) ;

б) ;

в) .

Решение

а) Сравним таблицы истинности для правой и левой частей:

Итоговые столбцы таблиц истинности (выделены фоном) совпадают, значит, формулы равносильны.

б)

Итоговый столбец совпадает с первым столбцом, значит, эта формула равносильна Х.

в)

Пример 1.8

Исключить возможно большее число скобок:

а) ;

б) .

Ответы

а) ;

б) .

Пример 1.9

Восстановить максимальное число скобок, ориентируясь на формальное определение формулы:

а) ;

б) .

Ответы

а) ;

б) .

Пример 1.10

Оптимизировать формулы:

а) ;

б) .

Решение

а) Удаляя «лишние» скобки, получим:

.

б) Применяя последовательно основные логические законы (III.2.), (II.1.), (I.5.), (IV.8.) и (IV.1.) и удаляя «по пути» скобки, получим:

.

Пример 1.11

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

а);

б) .

Решение

а) Преобразуем левую формулу к виду правой формулы, последовательно применив логические законы (I.6.), (I.6.) и (I.2.):

.

б) Применим к левой формуле логические законы (III.1.), (II.2.) и (II.1.):

.

Пример 1.12

Определить, является ли формула тавтологией, противоречием или ни тем, ни другим:

а) ;

б) ;

в) ;

г) .

Решение

а) Приведем формулу к наиболее простому виду, последовательно исключая импликации по логическому закону (III.1.) и убирая двойные отрицания по закону (II.1.):

.

Полученная формула не является логической константой, следовательно, исходная формула не является ни тавтологией, ни противоречием.

б) Применим логические законы (II.2.), (IV.7.) и (IV.2.):

.

Исходная формула – противоречие.

в) Применим (III.1), (I.6), (IV.8) и (IV.1):

Исходная формула не является ни тавтологией, ни противоречием.

г) Применим (III.1), (II.3), (II.2), (II.1), (I.2), (IV.1), (I.5), (IV.3):

Исходная формула не является ни тавтологией, ни противоречием.

Задачи

1.9. Доказать равносильность формул, используя таблицы истинности:

а) ;

б) .

1.10. Доказать равносильность формул задачи 1.9, используя основные логические законы.

1.11. Доказать равносильность формул (некоторые из них часто тоже относят к основным логическим законам):

а)	(поглощение);
б)	(поглощение);
в)	(склеивание);
г)	(обобщенное склеивание);
д)
е) ,	где F – произвольная формула.

1.12. Доказать, что:

а) ;

б) ;

в) .

1.13. Построить формулу U такую, чтобы данная формула была тождественно истинной:

а) ;

б) .

1.14. Построить формулу от трех переменных, которая истинна в том и только в том случае, когда ровно две переменные ложны.

1.15. Построить формулу от трех переменных, которая принимает такое же значение, как и большинство (меньшинство) переменных.

1.3. Нормальные формы формул логики высказываний

Сводка теории

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

Всякая дизъюнкция элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ).

Следует отметить, что ДНФ функции (или формулы) может быть не единственной.

Алгоритм приведения к ДНФ может быть описан с привлечением приведенных ранее равносильностей или основных логических законов (см. разд. 1.2). Сначала с помощью закона (II.1) и законов де Моргана (II.2), (II.3) все отрицания «спускаются» до переменных. Затем раскрываются скобки, с помощью логических законов (I.7), (I.8), (IV.7) и (IV.8) удаляются лишние конъюнкции и повторения переменных в конъюнкциях, а с помощью логических законов (IV.1.) – (IV.6) удаляются константы.

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

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

Совершенной дизъюнктивной нормальной формой (СДНФ) относительно переменных называется ДНФ, в которой нет одинаковых элементарных конъюнкций и все элементарные конъюнкции правильны и полны относительно переменных .