Пренекс нормальная форма

Формализм логики первого порядка

Формула исчисления предикатов находится в нормальной форме пренекса ^[1] ( PNF ), если она записана как строка кванторов и связанных переменных , называемая префиксом , за которой следует часть без кванторов, называемая матрицей . ^[2] Вместе с нормальными формами в логике высказываний (например, дизъюнктивной нормальной формой или конъюнктивной нормальной формой ) она обеспечивает каноническую нормальную форму , полезную при автоматизированном доказательстве теорем .

Каждая формула классической логики логически эквивалентна формуле в пренексной нормальной форме. Например, если , и являются формулами без кванторов с показанными свободными переменными, то ${\displaystyle \phi (y)}$ ${\displaystyle \psi (z)}$ ${\displaystyle \rho (x)}$

${\displaystyle \forall x\exists y\forall z(\phi (y)\lor (\psi (z)\rightarrow \rho (x)))}$

находится в пренексной нормальной форме с матрицей , а ${\displaystyle \phi (y)\lor (\psi (z)\rightarrow \rho (x))}$

${\displaystyle \forall x((\exists y\phi (y))\lor ((\exists z\psi (z))\rightarrow \rho (x)))}$

логически эквивалентен, но не в пренексной нормальной форме.

Преобразование в предварительную форму

Любая формула первого порядка логически эквивалентна (в классической логике) некоторой формуле в пренексной нормальной форме. ^[3] Существует несколько правил преобразования, которые можно рекурсивно применять для преобразования формулы в предварительную нормальную форму. Правила зависят от того, какие логические связки встречаются в формуле.

Соединение и дизъюнкция

Правила конъюнкции и дизъюнкции гласят, что

${\displaystyle (\forall x\phi )\land \psi }$эквивалентно (мягкому) дополнительному состоянию или, что то же самое, (это означает, что существует хотя бы один человек), ${\displaystyle \forall x(\phi \land \psi )}$ ${\displaystyle \exists x\top }$ ${\displaystyle \lnot \forall x\bot }$

${\displaystyle (\forall x\phi )\lor \psi }$эквивалентно ; ${\displaystyle \forall x(\phi \lor \psi )}$

и

${\displaystyle (\exists x\phi )\land \psi }$эквивалентно , ${\displaystyle \exists x(\phi \land \psi )}$

${\displaystyle (\exists x\phi )\lor \psi }$эквивалентно при дополнительном условии . ${\displaystyle \exists x(\phi \lor \psi )}$ ${\displaystyle \exists x\top }$

Эквиваленты действительны, когда не появляется как свободная переменная ; если действительно появляется свободным в , можно переименовать связанный в и получить эквивалент . ${\displaystyle x}$ ${\displaystyle \psi }$ ${\displaystyle x}$ ${\displaystyle \psi }$ ${\displaystyle x}$ ${\displaystyle (\exists x\phi )}$ ${\displaystyle (\exists x'\phi [x/x'])}$

Например, на языке колец ,

${\displaystyle (\exists x(x^{2}=1))\land (0=y)}$эквивалентно , ${\displaystyle \exists x(x^{2}=1\land 0=y)}$

но

${\displaystyle (\exists x(x^{2}=1))\land (0=x)}$не эквивалентно ${\displaystyle \exists x(x^{2}=1\land 0=x)}$

потому что формула слева истинна в любом кольце, когда свободная переменная x равна 0, а формула справа не имеет свободных переменных и ложна в любом нетривиальном кольце. Поэтому сначала будет переписано как , а затем приведено в пренексную нормальную форму . ${\displaystyle (\exists x(x^{2}=1))\land (0=x)}$ ${\displaystyle (\exists x'(x'^{2}=1))\land (0=x)}$ ${\displaystyle \exists x'(x'^{2}=1\land 0=x)}$

Отрицание

Правила отрицания гласят, что

${\displaystyle \lnot \exists x\phi }$эквивалентно ${\displaystyle \forall x\lnot \phi }$

и

${\displaystyle \lnot \forall x\phi }$эквивалентно . ${\displaystyle \exists x\lnot \phi }$

Импликация

Существует четыре правила импликации : два, которые удаляют кванторы из антецедента, и два, которые удаляют кванторы из консеквента. Эти правила можно получить, переписав импликацию как и применив вышеизложенные правила дизъюнкции и отрицания. Как и в случае с правилами дизъюнкции, эти правила требуют, чтобы переменная, выраженная количественно в одной подформуле, не появлялась свободной в другой подформуле. ${\displaystyle \phi \rightarrow \psi }$ ${\displaystyle \lnot \phi \lor \psi }$

Правила удаления кванторов из антецедента таковы (обратите внимание на изменение кванторов):

${\displaystyle (\forall x\phi )\rightarrow \psi }$эквивалентно (в предположении, что ), ${\displaystyle \exists x(\phi \rightarrow \psi )}$ ${\displaystyle \exists x\top }$

${\displaystyle (\exists x\phi )\rightarrow \psi }$эквивалентно . ${\displaystyle \forall x(\phi \rightarrow \psi )}$

Правила удаления кванторов из консеквента таковы:

${\displaystyle \phi \rightarrow (\exists x\psi )}$эквивалентно (в предположении, что ), ${\displaystyle \exists x(\phi \rightarrow \psi )}$ ${\displaystyle \exists x\top }$

${\displaystyle \phi \rightarrow (\forall x\psi )}$эквивалентно . ${\displaystyle \forall x(\phi \rightarrow \psi )}$

Например, когда диапазон количественной оценки представляет собой неотрицательное натуральное число (а именно ), утверждение ${\displaystyle n\in \mathbb {N} }$

${\displaystyle [\forall n\in \mathbb {N} (x<n)]\rightarrow (x<0)}$

логически эквивалентно утверждению

${\displaystyle \exists n\in \mathbb {N} [(x<n)\rightarrow (x<0)]}$

Первое утверждение гласит, что если x меньше любого натурального числа, то x меньше нуля. Последнее утверждение гласит, что существует некоторое натуральное число n такое, что если x меньше n , то x меньше нуля. Оба утверждения верны. Первое утверждение верно, потому что, если x меньше любого натурального числа, оно должно быть меньше наименьшего натурального числа (ноля). Последнее утверждение верно, поскольку n=0 делает импликацию тавтологией .

Обратите внимание, что расстановка скобок подразумевает объем количественной оценки , что очень важно для смысла формулы. Рассмотрим следующие два утверждения:

${\displaystyle \forall n\in \mathbb {N} [(x<n)\rightarrow (x<0)]}$

и его логически эквивалентное утверждение

${\displaystyle [\exists n\in \mathbb {N} (x<n)]\rightarrow (x<0)}$

Первое утверждение гласит, что для любого натурального числа n , если x меньше n , то x меньше нуля. Последнее утверждение гласит, что если существует некоторое натуральное число n такое, что x меньше n , то x меньше нуля. Оба утверждения ложны. Первое утверждение не справедливо для n=2 , поскольку x=1 меньше n , но не меньше нуля. Последнее утверждение не выполняется для x=1 , поскольку натуральное число n=2 удовлетворяет условию x<n , но x=1 не меньше нуля.

Пример

Предположим , что , и являются формулами без кванторов и никакие две из этих формул не имеют общих свободных переменных. Рассмотрим формулу ${\displaystyle \phi }$ ${\displaystyle \psi }$ ${\displaystyle \rho }$

${\displaystyle (\phi \lor \exists x\psi )\rightarrow \forall z\rho }$.

Рекурсивно применяя правила, начиная с самых внутренних подформул, можно получить следующую последовательность логически эквивалентных формул:

${\displaystyle (\phi \lor \exists x\psi )\rightarrow \forall z\rho }$.

${\displaystyle (\exists x(\phi \lor \psi ))\rightarrow \forall z\rho }$,

${\displaystyle \neg (\exists x(\phi \lor \psi ))\lor \forall z\rho }$,

${\displaystyle (\forall x\neg (\phi \lor \psi ))\lor \forall z\rho }$,

${\displaystyle \forall x(\neg (\phi \lor \psi )\lor \forall z\rho )}$,

${\displaystyle \forall x((\phi \lor \psi )\rightarrow \forall z\rho )}$,

${\displaystyle \forall x(\forall z((\phi \lor \psi )\rightarrow \rho ))}$,

${\displaystyle \forall x\forall z((\phi \lor \psi )\rightarrow \rho )}$.

Это не единственная форма пренекса, эквивалентная исходной формуле. Например, если в приведенном выше примере иметь дело с консеквентом перед антецедентом, пренексная форма

${\displaystyle \forall z\forall x((\phi \lor \psi )\rightarrow \rho )}$

может быть получен:

${\displaystyle \forall z((\phi \lor \exists x\psi )\rightarrow \rho )}$

${\displaystyle \forall z((\exists x(\phi \lor \psi ))\rightarrow \rho )}$,

${\displaystyle \forall z(\forall x((\phi \lor \psi )\rightarrow \rho ))}$,

${\displaystyle \forall z\forall x((\phi \lor \psi )\rightarrow \rho )}$.

Расположение двух кванторов универсальности с одинаковой областью действия не меняет значения/истинного значения утверждения.

Интуиционистская логика

В правилах преобразования формулы в пренексную форму широко используется классическая логика. В интуиционистской логике неверно, что каждая формула логически эквивалентна предшествующей формуле. Связка отрицания — одно из препятствий, но не единственное. Оператор импликации также трактуется в интуиционистской логике иначе, чем в классической логике; в интуиционистской логике его невозможно определить с помощью дизъюнкции и отрицания.

Интерпретация BHK иллюстрирует, почему некоторые формулы не имеют интуиционистски эквивалентной пренексной формы. В этой интерпретации доказательство

${\displaystyle (\exists x\phi )\rightarrow \exists y\psi \qquad (1)}$

— это функция, которая при наличии конкретного x и доказательства даёт конкретный y и доказательство . В этом случае допускается вычисление значения y на основе заданного значения x . Доказательство ${\displaystyle \phi (x)}$ ${\displaystyle \psi (y)}$

${\displaystyle \exists y(\exists x\phi \rightarrow \psi ),\qquad (2)}$

с другой стороны, выдает одно конкретное значение y и функцию, которая преобразует любое доказательство в доказательство . Если каждый удовлетворяющий x может быть использован для построения удовлетворяющего y , но ни один такой y не может быть построен без знания такого x , то формула (1) не будет эквивалентна формуле (2). ${\displaystyle \exists x\phi }$ ${\displaystyle \psi (y)}$ ${\displaystyle \phi }$ ${\displaystyle \psi }$

Правила преобразования формулы в предварительную форму, которые не работают в интуиционистской логике:

(1) подразумевает , ${\displaystyle \forall x(\phi \lor \psi )}$ ${\displaystyle (\forall x\phi )\lor \psi }$

(2) подразумевает , ${\displaystyle \forall x(\phi \lor \psi )}$ ${\displaystyle \phi \lor (\forall x\psi )}$

(3) подразумевает , ${\displaystyle (\forall x\phi )\rightarrow \psi }$ ${\displaystyle \exists x(\phi \rightarrow \psi )}$

(4) подразумевает , ${\displaystyle \phi \rightarrow (\exists x\psi )}$ ${\displaystyle \exists x(\phi \rightarrow \psi )}$

(5) подразумевает , ${\displaystyle \lnot \forall x\phi }$ ${\displaystyle \exists x\lnot \phi }$

( x не фигурирует как свободная переменная в (1) и (3); x не фигурирует как свободная переменная в (2) и (4)). ${\displaystyle \,\psi }$ ${\displaystyle \,\phi }$

Использование предварительной формы

Некоторые исчисления доказательств будут иметь дело только с теорией, формулы которой записаны в пренексной нормальной форме. Эта концепция важна для разработки арифметической и аналитической иерархии .

Доказательство Гёделя его теоремы о полноте для логики первого порядка предполагает, что все формулы были преобразованы в предварительную нормальную форму.

Аксиомы Тарского для геометрии — это логическая система, все предложения которой могут быть записаны в универсально-экзистенциальной форме , особый случай пренексной нормальной формы, в которой каждый квантор универсальности предшествует любому квантору существования , так что все предложения могут быть переписаны в форме , где это предложение, не содержащее квантора. Этот факт позволил Тарскому доказать разрешимость евклидовой геометрии . ${\displaystyle \forall u}$  ${\displaystyle \forall v}$  ${\displaystyle \ldots }$  ${\displaystyle \exists a}$  ${\displaystyle \exists b}$  ${\displaystyle \phi }$ ${\displaystyle \phi }$

Смотрите также

• Арифметическая иерархия
• Гербрандизация
• сколемизация

Примечания

1. Термин «prenex» происходит от латинского praenexus «связанный или связанный спереди», причастия прошедшего времени от praenectere [1] (архивировано по состоянию на 27 мая 2011 г. в [2]).
2. Хинман, П. (2005), с. 110
3. Хинман, П. (2005), с. 111

Рекомендации

• Ричард Л. Эпштейн (18 декабря 2011 г.). Классическая математическая логика: семантические основы логики. Издательство Принстонского университета. стр. 108–. ISBN 978-1-4008-4155-4.
• Питер Б. Эндрюс (17 апреля 2013 г.). Введение в математическую логику и теорию типов: к истине через доказательство. Springer Science & Business Media. стр. 111–. ISBN 978-94-015-9934-4.
• Эллиот Мендельсон (1 июня 1997 г.). Введение в математическую логику, четвертое издание. ЦРК Пресс. стр. 109–. ISBN 978-0-412-80830-2.
• Хинман, Питер (2005), Основы математической логики , AK Peters , ISBN 978-1-56881-262-5