Prenex нормальная форма - Prenex normal form

А формула из исчисление предикатов в Prenex^[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)}$

потому что формула слева верна в любом кольце, когда свободная переменная Икс равно 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 \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)}$

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

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

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

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

(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 }$,

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

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

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

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

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

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

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

Примечания

1. Термин «пренекс» происходит от латинский 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 г.). Введение в математическую логику, четвертое издание. CRC Press. С. 109–. ISBN  978-0-412-80830-2.
• Хинман, П. (2005), Основы математической логики, А. К. Питерс, ISBN  978-1-56881-262-5