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

Ясно, что выяснение выполнимости А равносильно выяснению, является ли А противоречием или нет, что, в свою очередь, равносильно выяснению, яв­ ляется ли -пА тавтологией или нет. Если —А - тавтология, то А - противоречие, следовательно, А невыполнимо, если же —А - не тавтология, то А выполнимо. Проблема разрешимости (логики высказываний) полностью решается, на­ пример, с помош,ью таблиц истинности. При больших значениях п составление таблиц истинности (с 2" строками) является громоздкой операцией. Для реше­ ния проблемы разрешимости суш,ествуют и другие способы, основанные на приведении к так называемым нормальным формам, которые будут рассмотре­ ны позже. Множество форм U = [Ai, А2, An] называется (одновременно) выпол­ нимым тогда и только тогда когда суш,ествует означивание их атомов, при ко­ тором каждая форма из U принимает значение И. Пусть и = [Ai, А2, An]. Тогда имеют место следующие теоремы. Теорема 1.3. Если U выполнима, то U\ {Ai] выполнима для любого i, \<i<n. Теорема 1.4. Если U выполнима и В тавтология, то Uu {B] выполнима. Теорема 1.5. Если U невыполнима, то для любой формулы С множество форм Uu{C] невыполнимо. Теорема 1.6. Если U невыполнима и для некоторого i, \ < i < п, Ai является тавтологией, то U\ {Ai] невыполнима. § 4. Равносильность нронознцнональных форм Пропозициональные формы А и В называются равносильными, если при каждой совокупности значений всех пропозициональных букв, входящих в Л и В, эти формы принимают одинаковые истинностные значения. Например, форма —Л vB равносильна^ ^ 5 , в чем легко убедиться с помо­ щью таблиц истинности: А ^ В Л И Л Л И И И Л Л Н И И в этих таблицах результирующие столбцы совпадают, следовательно, эти фор­ мы равносильны. Далее, форма равносильна^. Действительно, имеем следующие таблицы: А Л Л И и ^ А V в И Л и л И л и и л и л л л и и и А V А & в л Л л л л л л л л и и и и л л и и и и и 12