Элементарный курс математической логики (стр. 2 )

где верхний индекс T обозначает операцию транспонирования.

Приведем названия и обозначения для некоторых функций из табл.2:

g0(x1,x2)=0 – логическая константа ложь,

g1(x1,x2)=x1&x2 – конъюнкция (обозначается также x1Ùx2 , x1x2 ,

произносится “x1 и x2”),

g6(x1,x2)=x1Åx2 – сложение по модулю 2,

g7(x1,x2)=x1Úx2 – дизъюнкция (произносится “x1 или x2”),

g8(x1,x2)=x1¯x2 – стрелка Пирса,

g9(x1,x2)=x1~x2 – эквивалентность,

g13(x1,x2)=x1®x2 – импликация (произносится “если x1, то x2”),

g15(x1,x2)=1 – логическая константа истина.

Заметим, что некоторые функции зависят не от всех указанных аргументов. Так, например, функция g12(x1,x2) принимает значение, противоположное первому аргументу, независимо от значений второго аргумента, то есть g12(x1,x2)= . Переменная x2 играет для функции g12(x1,x2) роль несущественной (фиктивной) переменной.

Пусть теперь y1=f1(x1,…,xn),..., ym=fm(x1,…,xn) – логические функции n переменных, g(y1,…,ym) – логическая функция m переменных.

Тогда суперпозиция

g(f1(x1,…,xn),...,fm(x1,…,xn)) (4)

данных функций определяет новую логическую функцию n переменных. Выражение (4) принято называть логической формулой. Число аргументов для функций f1(x1,…,xn),..., fm(x1,…,xn) всегда можно сделать одинаковым за счет введения несущественных переменных.

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

Таблица 3.

x1	x2
0	0	1	1
0	1	1	1
1	0	0	0
1	1	0	1

Сравнивая табл.3 и табл.2, видим, что для всех наборов (x1,x2) выполняется равенство f(x1,x2) = g13(x1,x2). Значит, формулы и x1® x2 задают одну и ту же функцию – импликацию. Логические формулы, которые задают одну и ту же функцию, называются равносильными. ■

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

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

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

– коммутативность;

(xÚy)Úz = xÚ(yÚz), (x&y)&z = x&(y&z) – ассоциативность;

xÚ0 = x, x&0 = 0, xÚ1 = 1, x&1 = x; – свойства констант;

– двойное отрицание;

– закон исключенного третьего; (5)

– закон противоречия;

– идемпотентность;

x&(yÚz) = (x&y)Ú(x&z), xÚ(y&z) = (xÚy)&(xÚz) – дистрибутивность;

– правила де Моргана.

Доказательство равенств (5) можно провести непосредственно. Для этого достаточно сравнить таблицы истинности для левой и правой части каждого из равенств.

Пример 5. Докажем, что равенство выполняется тождественно, то есть для любого набора значений (x,y). Это будет означать равносильность логических формул из левой и правой частей равенства. Составим таблицу истинности, для удобства пронумеровав столбцы.

Таблица 4.

1	2	3	4	5	6	7
0	0	0	1	1	1	1
0	1	1	0	1	0	0
1	0	1	0	0	1	0
1	1	1	0	0	0	0

Сравнивая содержимое столбцов 4 и 7 в табл.4, убеждаемся в тождественном выполнении данного равенства. ■

Между тождествами (5) и (1) обнаруживается аналогия, если установить соответствие между множествами и логическими функциями:

Таблица 5.

Множества	Логические функции
Æ	0
U	1
AÈB	xÚy
AÇB	x&y

2.2. Представление логической функции в нормальной форме

Элементарная конъюнкция ранга переменных – это формула вида

(6)

при условии, что каждая переменная встречается в (6) в точности один раз. Величины – параметры, которые принимают значения из множества {0;1}.

Принято также

(7)

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

Таблица 6.

x	s	xs
0	0	1
0	1	0
1	0	0
1	1	1

Как видно из табл.6, формула (7) определяет правило

(8)

Справедлива следующая теорема.

Теорема 1. Любую логическую функцию f(x1,…,xn) можно представить в виде

(9)

где m£ n и дизъюнкция берется по всем 2m наборам значений переменных x1,…,xm.

Пусть a1,…, an – произвольный фиксированный набор значений переменных x1,…,xn. Подставим этот набор на место переменных в обе части равенства (9). Получим

. (10)

При этом

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

С учетом свойств, представленных среди формул (5), выражение (10) для преобразуется к виду

,

то есть к тождеству. Так как набор произвольный, то теорема 1 доказана полностью. ■

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

(11)

Рассмотрим теперь логическую формулу

(12)

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

Теорема 2. Любая логическая функция, отличная от константы 0, может быть представлена в совершенной дизъюнктивной нормальной форме, то есть

(13)

Используем результат теоремы 1. Следуя формуле (9), рассмотрим разложение функции при .

Получим .

Далее, используя свойства (5), перегруппируем слагаемые в дизъюнкции и произведем сокращения. Тогда

что совпадает с формулой (13). Теорема 2 полностью доказана. ■

Проиллюстрируем полученные теоретические результаты следующими примерами.

Пример 6. Разложить функцию по переменной p.

Рассмотрим таблицу истинности данной логической функции.

Таблица 7.

p	q , r
1	2	3	4	5
0 0 0 0	0 , 0 0 , 1 1 , 0 1 , 1	0	1	1 0 1 1
0	0
1	1
1	0
1 1 1 1	0 , 0 0 , 1 1 , 0 1 , 1	1	1	1 1 1 1
1	1
0	1
0	1

Заметим, что верхняя и нижняя части табл.7 соответствуют случаям p=0 и p=1. В верхней и нижней частях столбца 2 наборы значений (q,r) следуют в лексикографическом порядке. Следовательно, содержимое столбца 5 следует понимать как столбцы значений для двух функций аргументов q,r. Тогда в силу формулы (11) имеем