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

64 А*( Х 1, Х 2,..., Х Ц) ~ B *(XI,X2....,X^, что и требовалось доказать. § 7. Свойства операций штрих Шеффера, стрелка Пирса и сложения по модулюдва Из определений операций / (штрих Шеффера) и J- (стрелка Пирса) следует, что: М х1у=1(х&у), (3.10) xJ-y=](xvy). (3-11) • Теорема 3.6. Для каждой формулы существует равносильная формула, содержащая только связку /, либо только связку I Доказательство. Докажем, что можно оставить только связку / . П о теореме 3.5 для каждой формулы существует равносильная ей формула, содержащая только 7 и v. Далее легко убедиться, например, с помощью таблиц истинности или, используя (3.10), что 1х~х 1х, xvy~(x /х) !(у fy). Таким образом, 7 и v'можно исключить и оставить только связку / Теперь покажем, что можно оставить только Согласно теореме 3.5 можно оставить только связки 7и &. С помощью таблиц истинности или по (3.11) легко показать, что 1х ~ xJ-х; х&у ~ (x-l x)J-fyJ-у), следовательно, остается только связка J.. Теорема доказана. Теперь покажем, что нет другой бинарной связки, кроме /, обладающей тем свойством, что через нее можно выразить все остальные. Теорема 3.7. Единственными бинарными связками, каждой из которых достаточно для выражения всех формул, являются связки J-n I. Доказательство. Предположим, что ° является достаточной в указанном смысле связкой. Если бы 1°1 было 1, то любая формула, построенная с помощью только лишь °, принимала бы значения 1, когда все входящие в нее переменные принимают значение 1. Следовательно, формула д: £ & 7х не могла быть выраженной только через Итак, 1°1 =0. Далее выясним, чему равняется 0 ° 0. Если бы 0° О = О, то любая формула, построенная с помощью только лишь °, принимала бы значение О, когда значения переменных равны 0. Следовательно, формула 1х не могла бы быть выраяссна только через Поэтому 0° О = 0. Таким образом, имеем таблицу: