Нормальная предварительная форма

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

Формула исчисления предикатов находится в предваренной ^[1] нормальной форме ( ПНФ ), если она записана в виде строки кванторов и связанных переменных , называемой префиксом , за которой следует часть, свободная от кванторов, называемая матрицей . [ ^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 г.). Классическая математическая логика: семантические основы логики. Princeton University Press. стр. 108–. ISBN 978-1-4008-4155-4.
• Питер Б. Эндрюс (17 апреля 2013 г.). Введение в математическую логику и теорию типов: к истине через доказательство. Springer Science & Business Media. стр. 111–. ISBN 978-94-015-9934-4.
• Эллиот Мендельсон (1 июня 1997 г.). Введение в математическую логику, четвертое издание. CRC Press. стр. 109–. ISBN 978-0-412-80830-2.
• Хинман, Питер (2005), Основы математической логики , AK Peters , ISBN 978-1-56881-262-5