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

Запись j=y4 в логике высказываний означает, что^ является тав­ тологией (общезначимой). Докалсем следующую теорему. Теорема 3.2. А\=В тогда и только тогда, когда \'Л=>В. Доказательство. Построим таблицу истинности для A=i>B. Пусть имеем, что Л |= В, тогда в каждой строке таблице, где /4=Я, будет В—Иу следовательно, А ^ В тавтология, то есть |= ^=>5, Если же имеем |=А ^ В , то в таблице истинности дляА ^ В всюду, где А-И, должно быть В=И, следовательно, получим/11= В. Пропозициональная форма 5 называется логмческгш следствием пропозициональных форм т>\, если для каждой сово­ купности значений пропозициональных букв, при которых формы y4i, A2y...jAm одновременно равны И, форма В тоисе принимает значение И. В этом случае записываем: ai, (ЗЛ) Выяснение, будет ли В логическим следствием из y4z,...y4, „, /71 >1, называют проблемой дедукции. Очевидно, что имеет место следующая теорема. Теорема 3,3. Для произвольных формул логики высказыва­ н и й и м е ю т место соотношения: At y42f-,A „, ^ А\&А2&,..&А„, , (3.2) для любого г. (3.3) Теорема 3.4. Если формула (3.4) является противоречием, то В является логичес1шм следствием из A\f A^f"^ Ащ, т.е.: (3.5) 90