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

62 § 6. Зависимости между булевыми функциями Операции (связки) 7, &, v, =>, =,+, / я J- es ЯВЛЯЮТСЯ независимыш друг от друга в том смысле, что одни из них можно выражать через другие так, что при этом получаются равносильные формулы. Легко видеть, что х+у~1(х=у). '•/ (3.1) Связка = может быть выражена через связки и & т основании соотношения х=у ~ fx=^y) & (у=> х). Для доказательства этой равносильности достаточно составить таблицы истинности и убедиться, что результирующие столбцы этих таблиц совпадают. Для импликации имеем: х:^у~ Ixvy. V . (3.2) Таким образом, связку = можно выразить через /, c& и v . X =у~ (Ixvy) & (1 yvx). V (3.3) Так как jc равносильно 1(1х), то х&у равносильно 1(1х)&1 (1у), а последнее согласно закону де Моргана равносильно 1(1хvly), следовательно. х&у ~ 1(1х vly). (3.4) Аналогичным образом можно получить следующее: XV)' ~ 1(1х & 1у). (3.5) Из соотношения (3,2) заменой 7х нах получаем, что xvy ~ lx=i>y. (3.6) Также легко убедиться, что: х1у -1 (х&у), x-ly ~ 1 (xvy). (3.7) Имеют место следующие теоремы. Теорема 3.3. Для каждой формулы А существует равносильная ей формула, содержащая только связки /, &, v, причем связка 7 относится только к переменным. Доказательство. Связи! =,+, / и i можтю исютючить согласно соотношениям (3.2), (3.3), (3.1) н (3.7), При этом останутся только связки 7, &, V. Если связка 1 стоит перед некоторой скобкой, то на основании законов де Моргана можно внести 7 под скобки, при этом связка & меняется на v, а на ей, а связки, отличные от 7, <&, ц не появятся. Внеся 7 под скобки, пере которыми они стоят, добьемся, чтобы 7 относилась только к переменным. Теорема доказана.