Логическое следование формул логики предикатов - Равносильные преобразования формул и логическое следование формул логики предикатов

Понятие логического следования для формул логики предикатов соответствует понятию логического следования для формул алгебры высказываний. Формула логики предикатов называется Логическим следствием формулы, если при всякой интерпретации, при которой превращается в тождественно истинный предикат, формула также превращается в тождественно истинный предикат. Запись: . Как и в алгебре высказываний, . Также две формулы равносильны тогда и только тогда, когда каждая из них является логическим следствием другой. Поэтому здесь целесообразно еще раз обратить внимание на такие тавтологии, имеющие форму импликации, для которых обратные импликации тавтологиями не являются. Так, закон о перестановке разноименных кванторов (теорема 21.14, пункт в) приводит к логическому следованию:

Причем обратное следование не выполняется.

Аналогичные примеры логических следований дают тавтологии, связанные с пронесением кванторов через знаки логических операций, которые мы обсуждали в предыдущем параграфе:

Наконец обратим внимание на тавтологии теоремы 21.13, выражающие законы удаления квантора общности и введения квантора существования

При условии, что предметная переменная у не входит свободно в формулу. Из этих тавтологий получаются следующие логические следования:

    1) -- правило удаления квантора общности или Правило универсальной конкретизации); 2) -- правило введения квантора существования (или Правило экзистенциального обобщения).

Эти правила можно представить также в следующих видах:

При условии, что ни в одну формулу из совокупности и в формулу предметная переменная не входит свободно.

Обоснуем, например, первое из этих правил (второе обоснуйте самостоятельно). По условию, т. е. формула превращается в тождественно истинный предикат при всякой такой - интерпретации, при которой в тождественно истинные предикаты превращаются все формулы из совокупности. Пусть мы имеем такую интерпретацию и при ней формула превращается в тождественно истинный предикат от переменных. Тогда, по определению квантора общности, предикат от переменных также будет тождественно истинным. Это и означает, что.

Похожие статьи




Логическое следование формул логики предикатов - Равносильные преобразования формул и логическое следование формул логики предикатов

Предыдущая | Следующая