Математическая логика и теория алгоритмов

ная форма может быть приведена преобразованиями равносильности к такому виду. Будем говорить, что связка & двойственпа связке v , и наоборот. Пропозициональные формы Л и А* называются двойственными, если одна получается из другой заменой каждой связки c& и v на двой­ ственную. Например, если Л то Л* ={А &1 J 5) V C. Отношение двойственности взаимно: если Л двойственноЛ*, то А* двойственно А. Следующую теорему счт-агат законом двойственности. Теорема 1.6. Если пропозициональные формы А м В равно­ сильны, то и двойственные им формы и В* также равносильны. Доказательство. Пусть А и В равносильны, а Ai,A2,...,A „ - буквы, входящие в А или В. Будем считать, что Ai,A2,...,A „ входят и в Л, и в J B. Если бы это было не так, например, В не содержала бы входящего в А, то В можно заменить равносильной формой BvAi&l А /с, содержащей эту букву. Таким образом, всегда можем добиться, чтобы Л и В содержали все буквы А иAz,..., А п. По условию A(AI,A2 A „)~B(AUA2,...,A„). ' ( 1 . 7 ) Если формы А и В равносильны, то, очевидно, равносильны и их отрицания, поэтому из (1.7) получим, что '\ А ( А \, А2,...,АП ) ^'\ В ( А ], А2,...,А „). (1 -8) В пропозициональных формах соотношения (1.8) добьемся, чтобы 1 относилась только к буквам. При этом согласно законам де Моргана связки & и v поменяются на двойственные. Следо­ вательно, получим Л*(\A,^A2,...^A„)~Б*(\A,^Aъ...^An). (1-9) 30