Изменения

# === Язык. === Добавим к языку исчисления высказываний новые конструкции с предикатами

*<выражение>}&::=&\s{<импликация>}\\*<импликация>}&::=&\s{<дизъюнкция>} | \s{<дизъюнкция>} <tex> \rightarrow \s{</tex> <импликация>}\\*<дизъюнкция>}&::=&\s{<конъюнкция>} | \s{<дизъюнкция>} <tex> \vee \s{</tex> <конъюнкция>}\\*<конъюнкция>}&::=&\s{<терм>} | \s{<конъюнкция>} \& \s{<терм>}\\\s{*<терм>}&::=&\s{<предикат>} | \s{<предикат>} (\s{<аргументы>}) \\&|&<tex>\exists\s{</tex> <переменная><терм>} | <tex>\forall\s{</tex> <переменная><терм>}\\\s{*<аргументы>}&::=&\s{<переменная>}\\\s{*<аргументы>}&::=&\s{<переменная>,<аргументы>}\end{eqnarray*}\end{bnf}

# (a) ''индивидные'' переменные --- мы будем записывать их маленькими латинскими буквами из начала алфавита (b) предикаты (они обобщили пропозициональные переменные) (c) кванторы: всеобщности (<tex> \forall </tex>) и существования (<tex> \exists </tex>). === Аксиомы. ===  \begin{{Определение |definition}=Дана некоторая формула <tex>s</tex>. Будем говорить, что переменная $y$ свободна для $x$ подстрока <tex>s_1</tex> строки <tex>s</tex> является подформулой, если она в точности соответствует какому-то одному нетерминалу в дереве разбора строки <tex>s</tex>.}} {{Определение |definition=при подстановке Если в формулу $входит подформула, полученная по правилам для кванторов (то есть, <tex>\psi$ (forall x \alpha</tex> или просто свободна для подстановки вместо $<tex>\exists x$\alpha</tex>), если после подстановки ни одно ее вхождение не станет связаннымто мы будем говорить, что формула <tex>\alpha</tex> находится в области действия данного квантора по переменной <tex>x</tex>. Также, будем говорить, что любая подформула формулы <tex>\alpha</tex> находится в области действия данного квантора.\end{definition}}

Чтобы получить список аксиом для исчисления предикатов, возьмем все схемы{{Определение аксиом исчисления высказываний и дополним их следующими двумя схемами.|definition=Здесь $Если некоторое вхождение переменной <tex>x</tex> находится в области действия квантора по переменной <tex>x$ - переменная</tex>, $\psi$ - некоторая формула, $y$ - некоторая переменнаято такое вхождение мы назовем '''связанным'''.Запись $Вхождение переменной <tex>x</tex> непосредственно рядом с квантором (<tex>\psi[forall x := y]$ будет означать результат подстановки $y$ в $\psi$ вместо всех dots</tex>) мы назовем '''связывающим'''. Те вхождения переменных, которые не являются связанными или связывающими, назовем '''свободными'''. Формула, не имеющая свободных вхождений $x$. Пусть $y$ свободно для подстановки вместо $x$переменных, называется '''замкнутой'''.}}

\begin{tabular}{lll}Определение |definition=(11) & $\forall{Будем говорить, что переменная <tex>y</tex> свободна для <tex>x}(</tex> при подстановке в формулу <tex>\psi) \rightarrow </tex> (\psi[или просто свободна для подстановки вместо <tex>x := \alpha]</tex>)$\\ , если после подстановки <tex>y</tex> вместо свободных вхождений <tex>x</tex> ни одно ее вхождение не станет связанным. (12) & $(\psi[x := \alpha]) \rightarrow \exists{x}(\psi)$\end{tabular}

ЗаметимЧтобы получить список аксиом для исчисления предикатов, что если взять формулу $\exists x A(x,y)$, то по схеме возьмем все схемы аксиом (11),исчисления высказываний и дополним их следующими двумя схемами.если игнорировать ограничение на свободу для подстановкиЗдесь <tex>x</tex> {{---}} переменная, следующее утверждение должно быть тавталогией: $<tex>\forall psi</tex> {{---}} некоторая формула, <tex>y </tex> {{---}} некоторая формула.Запись <tex>\exists psi[x A(x,:= y]</tex> будет означать результат подстановки <tex>y) \rightarrow </tex> в <tex>\exists psi</tex> вместо всех свободных вхождений <tex>x A (x,</tex>. Пусть <tex>y</tex> свободно для подстановки вместо <tex>x)$. Однако, оно ей не является</tex>.

(11) <tex>\forall{x}(\psi) \rightarrow (\psi[x := \alpha]) </tex>  (12) <tex>(\psi[x := \alpha]) \rightarrow \exists{x}(\psi) </tex> Заметим, что если взять формулу <tex>\exists x A(x,y)</tex>, то по схеме аксиом (11),если игнорировать ограничение на свободу для подстановки, следующее утверждение должно быть тавтологией: <tex> \forall y \exists x A(x,y) \rightarrow \exists x A (x,x) </tex>. Однако, оно ей не является. Пример, когда нарушение свободы для подстановки приводит к противоречию: <tex>\forall{x}(\psi) \to (\psi[x := \alpha]) \\\psi := \exists a \lnot P(a) = P(b), x := b, \alpha := a \\\forall b \exists a (\lnot P(a) = P(b)) \to \exists a (\lnot P(a) = P(a)) \\</tex> Такой предикат <tex>P</tex>, очевидно, существует (если в предметном множестве больше одного элемента). Тогда <tex>\exists a (\lnot P(a) = P(a))</tex> Противоречие, следовательно, <tex>z</tex> должен быть свободен для подстановки вместо <tex>\alpha</tex>. Все аксиомы, порожденные данными схемами в новом языке, мы назовем аксиомами исчисления

# === Правила вывода.===

Пусть $<tex>x$ </tex> не входит свободно в $<tex>\phi$</tex>. Тогда рассмотрим следующие дополнительные

<tex> \begin{tabular}{lll}$\inferfrac {(\phi) \rightarrow \forall{x}(\psi)}{(\phi) \rightarrow \forall{x}(\psi)}$ &</tex>$\infer{<tex> \existsfrac {x}(\psi) \rightarrow (\phi)}{\exists{x}(\psi) \rightarrow (\phi)}$\end{tabular}</tex>

%<<Не входит свободно>> - это также важный вопрос.%Рассмотрим формулу $A(x) \rightarrow A(x)$. Легко показать, что такая%формула общезначима и доказуема. Однако, $(\exists{x}A(x)) \rightarrow A(x)$%не является общезначимой, если $A(x)$ не общезначимаКомментарии: достаточно взять в качестве %оценки свободной переменной $x$ то значение, на котором $A(x)$ ложна.%Вывод из гипотез также вполне можно расширить на исчисление предикатов.

<!-- По-моему, в следующем абзаце бред. // Андрей Рыбак --> "Не входит свободно" - это также важный вопрос.Рассмотрим формулу <tex>A(x) \beginrightarrow A(x)</tex>. Легко показать, что такаяформула общезначима и доказуема. Однако, <tex>(\exists{x}A(x)) \rightarrow A(x)</tex>не является общезначимой, если <tex>A(x)</tex> не общезначима: достаточно взять в качестве оценки свободной переменной <tex>x</tex> то значение, на котором <tex>A(x)</tex> ложна.Вывод из гипотез также вполне можно расширить на исчисление предикатов. === Итог === {{Определение |definition}=Формальная система, составленная из указанного языка, множества аксиом и множестваправил вывода, называется '''исчислением предикатов'''. \end{definition}}

вместо оценки для переменных $<tex>f_P$ </tex> в исчислении высказываний ввестиоценку для предикатов: для каждого $<tex>k$</tex>-местного предиката $<tex>P^k_n$ </tex> определитьфункцию $<tex>f_{P^k_n}: D^k \rightarrow V$</tex>.

\begin{{Определение|id=valid|definition}=Формула в исчислении предикатов общезначима, если она истинна на любом предметном множестве $<tex>D$</tex>, при любой оценке предикатов, и при любых оценках свободных индивидных переменных.\end}} {{Определение |definition=Пусть имеется некоторое исчисление предикатов с множеством аксиом <tex>A</tex>, и пусть дан некоторый (возможно, пустой) список <tex>\Gamma</tex> ''замкнутых'' формул исчисления предикатов. Тогда, вывод формулы <tex>\alpha</tex> в исчислении с аксиомами <tex>A \cup \Gamma</tex> мы назовем выводом из допущений <tex>\Gamma </tex>, и будем записывать это как <tex>\Gamma \vdash \alpha </tex>.}}

\begin{theorem}{Теорема|statement=

\end{theorem|proof= Упражнение.}}

\begin{theorem}{Теорема|statement=

\end{theorem} \begin{|proof}=

2 новых правила вывода. Упражнение.\end{proof}}

\begin{theorem}{Теорема|statement=

\end{theorem}|proof=Без доказательства.   [[Лекция 3 | <<]][[Лекция 5 | >>]]}}