Методические рекомендации по изучению дисциплины (стр. 5 )

Предложение Если А(А) – тавтология, а В – произвольная формула алгебры высказываний, то формула также является тавтологией.

Доказательство: Пусть А(А)=А(А;А1;А2;…;Ап) и В=В(В1;В2;…;Вт). Заметим, что среди переменных из наборов А;А1;А2;…;Ап и В1;В2;…;Вт могут быть и совпадающие. Тогда (8)

Если бы формула (8) оказалась не тавтологией, то нашелся бы такой набор

значений истинности для переменных В1;В2;…;Вт; А1;А2;…;Ап соответственно, что

. (9)

Пусть (tÎ{и;л}). Тогда из (9) получаем, что

,

т. е. формула А(А;А1;А2;…;Ап) на наборе для переменных А;А1;А2;…;Ап оказалась бы ложной, но это противоречило бы тому, что она тождественно истинна. ÿ

2 Пусть А и (А®В) – произвольные формулы алгебры высказываний. Будем говорить, что формула В получается применением к ним оператора заключения М. Р. и писать:

В = М. Р. (А; (А®В

(М. Р. – первые буквы латинских слов modus ponens, которые в переводе означают – правило заключения.)

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

Предложение Если формулы А и (А®В) являются тавтологиями, то формула В также является тавтологией.

Доказательство: Пусть формулы А(А1;А2;…;Ап) и А(А1;А2;…;Ап)®В(В1;В2;…;Вт) (среди переменных из наборов А1;А2;…;Ап и В1;В2;…;Вт могут быть и совпадающие переменные) являются тавтологиями. Предположим, что формула В тавтологией не является и такой набор значений истинности для переменных В1;В2;…;Вт соответственно, что . Так как формула (А®В) является тавтологией, то уравнение

А(А1;А2;…;Ап)®В(τ1; τ 2;…; τ т) = и,

т. е. уравнение

А(А1;А2;…;Ап)®л = и

должно быть разрешимо относительно А1;А2;…;Ап. Следовательно существует такой набор значений истинности для переменных А1;А2;…;Ап, что

. (11)

С другой стороны, в силу того, что А – тавтология:

(12)

Из (11) и (12) следует противоречие, так как формула не может на одном и том же наборе значений для переменных быть одновременно и истинной и ложной. Следовательно, В(В1;В2;…;Вт) – тавтология. ÿ

Отношение равносильности

Двуместные операции +; ×; - – сложения, умножения, вычитания, заданные естественным образом на множестве действительных чисел обладают определенными свойствами. Из школьной алгебры, в частности, нам известны переместительный, сочетательный и распределительный законы, которые в буквенной алгебре записываются так:

1 - переместительные законы для сложения и умножения;

2 - сочетательные законы для сложения и умножения;

3 - распределительный закон умножения относительно сложения.

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

Следующий этап развития алгебры высказываний связан с выявлением и использованием аналогичных возможностей для логических операций &; Ú; ®; « и Ø.

Определение Формулы А=А(А1;А2;…;Ап) и В=В(А1;А2;…;Ап) называются равносильными (символически АºВ), если на любом наборе значений истинности для переменных А1;А2;…;Ап соответственно, эти формулы принимают одинаковые значения.

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

Пример Проверим, что формулы:

а) и ;

б) и

являются равносильными.

а)	А	В		;	А	В
	л	л	и		л	л	и
	л	и	и		л	и	и
	и	л	и		и	л	и
	и	и	л		и	и	л

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

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

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

А	В		А
л	л	л	л
л	и	л	л
и	л	и	и
и	и	и	и

Упражнение Пусть А=А(А1;А2;…;Ап) произвольная формула алгебры высказываний. Положим:

.

Показать, что В(А1;А2;…;Ат) º С(А1;А2;…;Ат) тогда и только тогда, когда для любых формул В и С.

Упражнение Доказать, что А(А1;А2;…;Ат) º В(А1;А2;…;Ат) тогда и только тогда, когда формула А(А1;А2;…;Ат) « В(А1;А2;…;Ат) является тавтологией.

Выражение АºВ не является формулой алгебры высказываний. В дальнейшем такие выражения будем называть равносильностями, а формулы А и В – левой и правой ее частями соответственно. Если формулы А и В действительно являются равносильными, то будем говорить, что равносильность АºВ имеет место (или является верной), в противной случае – не имеет места (или является неверной).

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

1 А&В º В&А коммутативность

2 АÚВ º ВÚА операций & и Ú;

3 (А&В)&С º (А&В)&С ассоциативность

4 (АÚВ)ÚС º (АÚВ)ÚС операций & и Ú;

5 (А&В)ÚС º (АÚС)&(ВÚС) дистрибутивность

6 (АÚВ)&С º (А&С)Ú (В&С) операций & и Ú относительно друг друга;

7 А&А º А законы

8 АÚА º А идемпотентности;

9 А&В º АÚВ законы

10 АÚВ º А&В де Моргана;

11 А®В º АÚВ законы

12 А«В º (А®В)&(В®А) выражающие одни

13 А&В º АÚВ операции через

14 АÚВ º А&В другие;

15 А&и º А

16 А&л º л

17 АÚи º и

18 АÚл º А законы оперирования

19 А&А º л с константами и; л;

20 АÚА º и

21 л®А º и

22 А®л º А

23 А º А закон двойного отрицания

24 (А&В)ÚА º А законы

25 (АÚВ)&А º А поглащения.

Упражнение Проверить, что вышеприведенные равносильности 1-25 – верны.

Левые и правые части равносильностей 1-25 зависят только от исходных высказываний А; В; С. Если любую из этих переменных заменить одновременно в обеих частях каждой из равносильностей 1-25 произвольной формулой, то равносильность останется верной. Более того, как показывает упражнение 2.5.4, замена этой переменной в левой части одной формулой, а в правой части формулой, ей равносильной, также не нарушает любой из этих равносильностей. В этом плане на равносильности 1-25 можно смотреть, как на схемы, из которых указанными подстановками получаются новые равносильности. Продолжая аналогично с элементарной алгеброй, заметим, что на основе любого закона сокращенного умножения именно таким путем получаются новые тождества. Так, например, тождество

получается из базового тождества (схемы)

, (1)

когда в (1) сначала и заменяется на a+b, а затем v – на ху одновременно в обеих частях этого тождества (кроме того здесь неявно используются и другие свойства операций +; × и -).

Упражнение Доказать, что если А(А;А1;А2;…;Ап) º В(А;А1;А2;…;Ап) и С(В1;В2;…;Вт) º D(В1;В2;…;Вт), то .

Упражнение 2.5.5 Доказать, что

а) А º А;

б) если А º В, то В º А;

в) если А º В и В º С, то А º С

для любых формул А; В; С алгебры высказываний.

Используя равносильности 1-25, упражнения 2.5.4 и 2.5.5 можно осуществлять равносильные преобразования формул алгебры высказываний. При этом под равносильным преобразованием формулы А(А1;А2;…;Ап) понимается переход от этой формулы к любой равносильной ей формуле А1(А1;А2;…;Ат). Неоднократное применение такого перехода приводит к цепочке равносильностей:

А º А1; А1 º А2; …; Аt º Аt+1. (2)

На основе свойств отношения равносильности (упражнение 2.5.5) из цепочки равносильностей (2) получаем

А º А1 º А2 º …º Аt+1,

в частности А º Аt+1.

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

Пример Докажем, что формула А(А;В;С) и В(А;В;С) равносильны, где

; .

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

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

Упражнение Доказать, что данные равносильности имеют место:

а) ;

б) .

Пример Докажем, что формула

А(А;В;С) = (А®С)®((В®С)®((АÚВ)®С))

является тождественно истинной.

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

(А®С)®((В®С)®((АÚВ)®С))

º

º

º

º

º

º

º .

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

а) ;

б) .

Определение Формула алгебры высказываний называется приведенной, если в ее состав входят только операции &; Ú; Ø, причем отрицание действует только на исходные переменные.

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

а) Используя равносильности ; приводим формулу А к формуле А1, в которую входят только операции &; Ú; Ø. (отметим, что после реализации этого шага операция Ø может действовать не только на простые высказывания, т. е. подформулы сложности 0, но и на такие подформулы В, для которых S(В) ³ 1).

б) Используя равносильности ; ; приводим формулу А1 к формуле А2, имеющей приведенную форму.

Пример Преобразовать данные формулы к приведенной форме:

а) ;

б) .

а)

;

б)

.

Упражнение Перейти от данных формул к приведенным формам:

а) ;

б) ;

в) .

Упражнение Доказать следующие равносильности:

- обобщенные законы дистрибутивности

-

обобщенные законы де Моргана для любых В1; …; Вп; D алгебры высказываний.