Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Теорема 1.10. Если пропозициональные формыЛ и в равносильны, то и двойственные им формыЛ* ив * также равносильны. Доказательство. Пусть Л и В равносильны, aAi,A2,...,An - буквы, входящие в А или В. Будем считать, что Ai,A2,...,An входят в Л, и вв . Если бы это было не так, например, В не содержала бы Ak(l^^), входящего в А, то В можно заменить равносильной формой BvAk& —iAk, содержащей эту букву. Таким образом, всегда можем добиться, чтобы А иВ содержали все буквы А i, А 2,..., А п . По условию A (A i ,A2,...,A „) B(A I ,A2,...,A„). (1-7) Если формы А и В равносильны, то, очевидно, равносильны и их отрицания, поэтому из (1.7) получим, что ^A(Aj,A2,...,An)-^B(Aj,A2,...,A^. (1-8) В формах соотношения (1.8) добьемся, чтобы —i относилась только к буквам. При этом согласно законам де Моргана связки & я v поменяются на двойственные. Следовательно, получим Л* (^Aj, ^А2,..., - в * h A j , ^А2,...,^ A J . (1.9) По определению равносильности форм равносильность Л *(^ —i^7, - пА2,..., —^Ап) и B*( —IAI, —1A2,..., —IA„J означает, что они принимают одинаковые значения при любых совокупностях значений букв Aj,A2,...,A „. Поэтому, если вместо букв АI,А2,...,An подставить -nAj, —,А2,..., —iA„, то формы останутся равносильными. Учитывая, что —i—iA равносильно А, из (1.9) получим A*(Ai,A2,...,An) ~ B^(Ai,A2,...,An), что и требовалось доказать. § 6. Нормальные формы Элементарной суммой (элементарным произведением) называют дизъюнкцию (конъюнкцию) пропозициональных букв либо их отрицаний. Одну букву тоже будем рассматривать как элементарную сумму или как элементарное произведение. Элементарную сумму часто называют дизъюнктом, а слагаемые этой суммы литералами {литерами). Примеры элементарных сумм: А, А vB, А vBv —A vC. Примеры элементарных произведений: —А, А&В, -А&С&А&В. Очевидно, что элементарная сумма является тавтологией (общезначимой формулой), тогда и только тогда, когда в ней содержится хотя бы одна пара слагаемых, из которых одно есть некоторая буква, а другое - отрицание этой буквы. Также ясно, что элементарное произведение будет противоречием тогда и только тогда, когда в нем содержится хотя бы одна пара множителей, из которых один множитель является отрицанием другого. 16