Дискретная математика

63 Теорема 3.4. Для каждой формулы А существует равносильная ей формула, содержащая либо только связки 7, либо только 7, v, либо только 1, =>. Доказательство. Покажем, что можно оставить только связки / и По предыдущей теореме можно оставить только связки 7, &, v. Связку v. исключим по (3.5). В результате останутся только 7 и &. Остальные утверждения теоремы доказываются аналогичным образом. Рассмотрим формулы, содержащие только связки 7, &, v. Как уже установлено, всякая формула может быть приведена преобразованиями равносильности к формуле, содержащей только 7, &, v. Будем говорить, что связка & двойственна связке v n наоборот. V*' Формулы А и А* называются двойственными, если одна получается из другой заменой каждой связки & и ^на двойственную. Например, если А =(xv ]y)&z, то А* =(jc & ]y)vz. Отношение двойственности взаимно: если А двойственно А*, то А* двойственно А. Следующую теорему считают законом двойственности. Теорема 3.5. Если формулы А и В равносильны, то и двойственные им формулы А* иВ* таюке равносильны. Доказательство. Пусть А VL В равносильны, а Х],Х2,—,Х„ - переменные, входящие в А или В. Будем считать, что xi,x2,...,x „ входят и в Л, и в В. Если бы это было не так, например, В не содержала бы Х1^(1 £ к <п), входящего ь А, то В можно заменить равносильной формулой Вюск&Ък, содержащей эту переменную. Таким образом, всегда можем добиться, чтобы А vi В содержали все переменные xi,x2,...,Xn. По условию Afxj,xz...,xn) ~ B{xj,x?,...,xJ. (3.8) Если формулы А и В равносильны, то, очевидно, равносильны и их отрицания, поэтому из (3.8) получим, что 1 A( XI,X2,...,X ^ ~ lB (XI,X2,...,X,). в формулах последнего соотношения добьемся, чтобы 7 относилась только к переменным. При этом согласно законам де Моргана связки & а v поменяются на двойственные. Следовательно, получим А*(1x1,1x2,.... IxJ ~В*(1хи 1X2,..., 1х„). (3.9) Равносильность формул А*(1х\,1х2,...,1х^ и B*(lxi,lx2,...,lx^ означает, что они принимают одинаковые значения при любых совокупностях значений переменных д:;,х2,...,х„. Поэтому, если вместо переменных подставить lxi,]x2,...,lx „, то формулы останутся равносильными. Учитывая, что 7 1х равносильно х, из (3.9) получим