Cтраница 3
В самом деле, каковы бы ни были формулы 51 и S3, можно предполагать, что они содержат одни и те же переменные. Если бы это было не так и формула 91, например, не содержала переменной V, входящей в 93, то 51 можно было бы заменить равносильной формулой Щ & ( 1 / V V), которая уже содержит переменную V. Таким образом, любые две формулы можно заменить равносильными им формулами, содержащими одинаковые переменные. Если 91 и 93 - равносильные формулы, то в силу единственности совершенных нормальных форм, как дизъюнктивные, так и конъюнктивные нормальные формы этих формул должны полностью совпадать. Таким образом, сравнение совершенных нормальных форм формул 91 и 93 решает вопрос об их равносильности. [31]
Применение любого правила вывода предполагает предварительную проверку его посылки. Простота этой проверки является основным требованием при построении элементарных преобразований. Понятие простоты не уточняется, поскольку проверка посылок обычно производится содержательными средствами. Обычно считается, что критерий простоты выдержан, если процесс проверки посылки сводится к выяснению графического совпадения или несовпадения конструктивных объектов, упоминаемых в правиле вывода. Правила вывода / и 2 удовлетворяют этому интуитивному представлению о простоте, поскольку при попытке применить правило 2 к двум отношениям равносильности Fi - Fz и F3 - Fb нужно только обнаружить, содержится ли F в Fa, а для применения правила 1 нужно обнаружить тождественность функций а и Э, что легко сделать, если считать, что аир представлены в совершенной нормальной форме. [32]
В самом деле, каковы бы ни были формулы 51 и S3, можно предполагать, что они содержат одни и те же переменные. Если бы это было не так и формула 91, например, не содержала переменной V, входящей в 93, то 51 можно было бы заменить равносильной формулой Щ & ( 1 / V V), которая уже содержит переменную V. Таким образом, любые две формулы можно заменить равносильными им формулами, содержащими одинаковые переменные. Если 91 и 93 - равносильные формулы, то в силу единственности совершенных нормальных форм, как дизъюнктивные, так и конъюнктивные нормальные формы этих формул должны полностью совпадать. Таким образом, сравнение совершенных нормальных форм формул 91 и 93 решает вопрос об их равносильности. [33]
Если в полученном выражении окажутся одинаковые слагаемые, то, удалив все, кроме одного из них, мы получим опять равносильное выражение. Наконец, можно удалить все те слагаемые, которые содержат какую-нибудь переменную вместе с ее отрицанием, так как слагаемые представляют собой тождественно ложные выражения. Если бы все слагаемые оказались таковыми, то, значит, вся сумма тождественно ложна. А тогда и формула 91 тождественно ложна и в силу этого не имеет совершенной дизъюнктивной нормальной формы. После удаления всех слагаемых, содержащих какую-нибудь переменную вместе е ее отрицанием, мы получим дизъюнктивную нормальную форму формулы 51, которая удовлетворяет условиям а), Ь), с), d) и, следовательно, является совершенной нормальной формой. Заметим, что нам нет необходимости знать заранее, является ли 51 тождественно ложной или нет. [34]