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

- «конъюнкция» ( и ). Эту функцию называют также логическим умножением. В соответствии с этим вместо знака & используется знак · или между и знак вообще опускается. Таким образом, записи: , и выражают одно и то же;

- «дизъюнкция» ( или ). Эту функцию называют также логическим сложением;

- «импликация» (из следует ). Эту функцию называют также логическим следованием; переменную - посылкой, а переменную - заключением;

- «эквиваленция» ( тогда и только тогда, когда );

- «сложение и по модулю 2» (т. е. нахождение остатка от деления (обычной) суммы на 2).

- «функция Шеффера».

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

Под сложностью формулы А понимается сложность терма, реализующего функцию .

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

Если А формула над В и - её подформула, то может входить в А неоднократно. Так, подформула входит в формулу

трижды, т. е. можно говорить о первом, втором и третьем её вхождении в эту формулу.

Пример1.5.1 Проверим, что выражение

является формулой.

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

шаг 0 -

подформулы сложности 0;

шаг 1 -

подформула сложности 1;

шаг 2 -

подформула сложности 2;

шаг 3 -

подформула сложности 3;

шаг 4 -

подформула сложности 4;

шаг 5 -

подформула сложности 5;

шаг 6 -

подформула сложности 6;

шаг 7 .

Так как данное выражение удалось получить в качестве подформулы (на последнем шаге 7), то оно является формулой над В сложности 7.

Упражнение 1.5.1 Проверить, что данные выражения являются термами над В:

а) ;

б) .

Используя таблицы 10 и 11 можно по формуле А найти табличное задание функции , которая представима этой формулой. Для вычисления значения функции на данном наборе значений для переменных необходимо най ти значения всех её подформул на этом наборе, начиная с подформул сложности 0 и заканчивая подформулой сложности (т. е. самой формулой).

Пример1.5.2 Вычислим значение формулы А из примера 1.5.1 на наборе .

Подставляя значения подформул (на наборе ), выписанных на предыдущих шагах, в подформулы последующих шагов и, используя таблицы 10 и 11, получаем:

шаг 0 1;0;0;

шаг 1 ;

шаг 2 ;

шаг 3 ;

шаг 4 ;

шаг 5 ;

шаг 6 ;

шаг 7 .

Таким образом, .

Пример1.5.3 Найдём табличное задание функции , где

.

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

; ; ; .

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

							А
0	0	0	1	0	0	0	0
0	0	1	0	0	0	0	0
0	1	0	1	0	0	1	1
0	1	1	0	1	0	1	0
1	0	0	0	0	1	1	0
1	0	1	0	0	1	1	0
1	1	0	0	0	1	0	0
1	1	1	0	1	0	1	0

Упражнение 1.5.2 Найти табличное задание функции , если:

а) ;

б) .

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

На множестве всех формул над В определяется бинарное отношение «» - равносильности: две формулы и (над В) называются равносильными, если функции

и , представимые этими формулами, равны.

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

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

- законы коммутативности ;

- законы ассоциативности ;

-

- законы идемпотентности ;

- законы де Моргана;

- законы поглощения;

- законы оперирования с константами;

29 - закон двойного отрицания.

Упражнение 1.6.1 Доказать, что если некоторую переменную любой из равносильностей 1 – 29 заменить произвольной формулой над В, то равносильность останется верной.

Упражнение 1.6.2 Доказать равносильности 1 – 29.

Упражнение 1.6.2 Доказать, что отношение равносильности является отношением эквивалентности на множестве всех формул алгебры логики.

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

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

Упражнение 1.6.4 Пусть - такая последовательность формул над В, что:

а) , ;

б) получается из применением к ней элементарного преобразования (). Доказать, что .

Пример1.6.1 Докажем, что формулы А и В, где

;

,

равносильны.

Рассмотрим последовательность формул:

;

;

;

;

;

;

;

.

В этой последовательности :

а) , ;

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

получается из заменой подформулы формулой (смотри равносильность 20);

получается из заменой подформулы на константу 0 (смотри равносильность 28);

получается из заменой подформулы на константу 1 (смотри равносильность 27);

получается из заменой подформулы формулой (смотри равносильности 1, 21 и упражнение 1.6.1);

получается из заменой подформулы формулой (смотри равносильность 18 и упражнение 1.6.1);

получается заменой на равносильную ей формулу (смотри равносильность 14 и упражнение 1.6.1);

получается из заменой подформулы формулой (смотри равносильность 18 и упражнение 1.6.1).

Отсюда получаем (смотри упражнение 1.6.4), что .

На практике вместо последовательности формул записывают цепочку равносильностей:

.

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

а) ;

.