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

По определению равносильности форм равносильность A*(\Aь^A2,...^ и В*(] А 1.1 Аг. ...Л ^4„) означает, что они принимают одинаковые значения при любых совокупностях значений букв АьАъ...,А„. Поэтому, если вместо, букв АиАъ---,А„ подставить '] А Ъ'] А 2,.-.,]А„, ТО формы останутся равносильными. Учитывая, что 11/4 равносильно .4, из (1.9) иояучям А*(АьА2,..-.Ап) ~ В*(А\,А2,...,А„), что и требовалось доказать. Каких цветов в саду весеннем нет! В. Шекспир § 8. Нормальные формы Известно, что в математическом анализе среди всевозможных функций выделяют элементарные (основные) функции: степенные, показательные, тригонометрические и т.п. Среди пропозициональных форм выделим некоторые как элементарные, а далее из них можно получать более сложные. Элементарной суммой (элементарным произведением) называ­ ют дизъюнкцию (конъюнкцию) пропозициональных букв либо их от­ рицаний. Одну букву тоже будем рассматривать как элементарную сумму или как элементарное произведение. Элементарную сумму часто называют дизъюнктом, а слагаемые этой суммы — литералами {литерами). Примеры элементарных сумм: А, A-vB, A-vBvlivC. Примеры элементарных произведений: IA, А&В, IA&C&A&B. Легко доказать следующие теоремы. Теорема 1.7. Чтобы элементарная сумма была тавтологией (общезначимой формулой), необходимо и достаточно, чтобы в ней содержалась хотя бы одна пара слагаемых, из которых одно есть неко­ торая буква, а другое - отрицание этой буквы. 31