Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]


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

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


Понятие равносильности формул


Определение 22.1. Две формулы, F и H логики предикатов называются равносильными на множестве M, если при любой подстановке в эти формулы вместо предикатных переменных любых конкретных предикатов, определенных на M, формулы превращаются в равносильные предикаты. Если две формулы равносильны на любых множествах, то их будем называть просто равносильными. Равносильность формул будем обозначать так: F\cong H.


Приведем пример двух неравносильных формул логики предикатов. Покажем, что


(\forall x)\bigl(P(x)\lor Q(x)\bigr)\ncong (\forall x)\bigl(P(x)\bigr)\lor (\forall x)\bigl(Q(x)\bigr).

В самом деле, подставим вместо предикатных переменных P(x) и Q(x) конкретные предикаты A(x) и B(x), определенные на множестве \mathbb{N} соответственно, где A(x) есть "x — четно", а B(x) есть "x — нечетно". Тогда левая формула превратится в высказывание (нульместный предикат) "каждое натуральное число либо нечетно, либо четно", которое истинно. Правая формула превращается в высказывание (нульместный предикат) "либо каждое натуральное число четно, либо каждое натуральное число нечетно", которое ложно.


Нетрудно понять на основании определений 22.1 и 21.6, что формулы F и H равносильны тогда и только тогда, когда формула F\leftrightarrow H является тавтологией:


F\cong H~~ \Leftrightarrow~~ \vDash F \leftrightarrow H\,.

Это замечание вместе с теоремами 21.9–21.14 позволяет указать наиболее важные примеры равносильных формул.


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




Приведенная форма для формул логики предикатов


Равносильные преобразования позволяют приводить формулы к тому или иному более удобному виду. Один из таких видов носит название приведенной формы.


Определение 22.2. Приведенной формой для формулы логики предикатов называется такая равносильная ей формула, в которой из операций алгебры высказываний имеются только операции \lnot,\,\land,\,\lor, причем знаки отрицания относятся лишь к предикатным переменным и к высказываниям.


Теорема 22.3. Для каждой формулы логики предикатов существует приведенная форма.


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


Если формула не имеет логических связок, т. е. является атомарной, то она сама имеет приведенную форму. Предположим, что всякая формула, содержащая не больше k-1 логических связок, обладает приведенной формой. Покажем теперь, что приведенной формой обладает также и всякая формула, содержащая к логических связок. Пусть F— такая формула. Тогда, на основании определения 21.1, она имеет один из следующих видов:


\lnot F_1,~~ (F_1\land F_2),~~ (F_1\lor F_2),~~ (F_1\to F_2),~~ (F_1\leftrightarrow F_2),~~ (\forall\xi)(F_1),~~ (\exists\xi)(F_1).

Каждая из формул F_1,\,F_2 содержит логических связок не более k-1, а поэтому, по предположению индукции, обладает приведенной формой. Пусть F_{1}^{\ast} и F_{2}^{\ast} — приведенные формы для формул F_1 и F_2 соответственно. Отсюда формулы


(F_{1}^{\ast}\land F_{2}^{\ast}),\quad (F_{1}^{\ast}\lor F_{2}^{\ast}),\quad (\forall\xi)(F_{1}^{\ast}),\quad (\exists\xi)(F_{1}^{\ast})

являются приведенными формами для формул (F_1\land F_2),~ (F_1\lor F_2),~ (\forall\xi)(F_1),~~ (\exists\xi)(F_1) соответственно.


Остается рассмотреть случаи, когда F имеет один из следующих видов: \lnot F_1,~ (F_1\to F_2) или (F_1\leftrightarrow F_2).


Пусть F есть \lnot F_1. Тогда формула \lnot F_{1}^{\ast} может не быть приведенной формой для формулы \lnot F_1. Строго говоря, для этого случая следует провести доказательство также методом математической индукции по числу логических связок формулы F_{1}^{\ast}. Если F_{1}^{\ast} атомарна, т.е. F_{1}^{\ast} — предикатная переменная P, то (\lnot F_{1})^{\ast} есть \lnot P — приведенная форма. Если же F_{1}^{\ast} — составная формула, то задача сводится к пронесению знака \lnot через кванторы и операции \land и \lor (другие логические операции не входят в приведенную форму F_{1}^{\ast}). Это пронесение осуществляется на основании равносильностей из логики предикатов и алгебры высказываний, называемых законами де Моргана (см. теоремы 21.9 и 4.4, пункты р, с). Итак, если F есть \lnot F_1 и F_1 обладает приведенной формой F_{1}^{\ast}, то мы сможем найти приведенную форму и для F.


Далее, пусть F есть (F_1\to F_2). Тогда на основании теоремы 4.4 (пункт у) формула F равносильна формуле (\lnot F_1\lor F_2). Заменив формулы F_1 и F_2 на равносильные им приведенные формы F_{1}^{\ast} и F_{2}^{\ast} соответственно, получим равносильную формулу (F_{1}^{\ast}\lor F_{2}^{\ast}), которая, вообще говоря, не является приведенной. Но, на основании предыдущего абзаца, можно найти для формулы \lnot F_{1}^{\ast} приведенную форму F_{1}^{\ast\ast}. Тогда ясно, что формула (F_{1}^{\ast\ast}\lor F_{2}^{\ast}) имеет приведенный вид и равносильна исходной формуле F.


Наконец, если F есть (F_1\leftrightarrow F_2), то на основании равносильности теоремы 4.4, (пункт ч) F равносильна формуле \bigl((F_1\to F_2)\land (F_2\to F_1)\bigr). В предыдущем абзаце было показано, как найти приведенные формы (F_{1}^{\ast\ast}\lor F_{2}^{\ast}) и (F_{2}^{\ast\ast}\lor F_{1}^{\ast}) для формул (F_1\to F_2) и (F_2\to F_1) соответственно. Тогда ясно, что формула (F_{1}^{\ast\ast}\lor F_{2}^{\ast}) и (F_{2}^{\ast\ast}\lor F_{1}^{\ast}) имеет приведенный вид и равносильна исходной формуле F.


Итак, в любом случае формула F обладает приведенной формой. Теорема доказана.




Предваренная нормальная форма для формул логики предикатов


Еще одним удобным видом формулы, к которому ее можно привести равносильными преобразованиями, является предваренная нормальная форма.


Определение 22.4. Предваренной нормальной формой для формулы логики предикатов называется такая ее приведенная форма, в которой все кванторы стоят в ее начале, а область действия каждого из них распространяется до конца формулы, т. е. это формула вида (K_1x_1)\ldots(K_mx_m)\bigl(F(x_1,\ldots,x_n)\bigr), где K_i есть один из кванторов \forall или \exists (i=1,\ldots,m),~m \leqslant n, причем формула F не содержит кванторов и является приведенной формулой. (Заметим, что кванторы в формуле могут отсутствовать вовсе.)


Теорема 22.5. Для каждой формулы логики предикатов существует предваренная нормальная форма.


Доказательство. Проведем доказательство по индукции, следуя правилу построения формул логики предикатов (определение 21.1).


Если формула атомарна, то она сама представляет собой предваренную нормальную форму. Поскольку каждая формула F равносильна формуле, полученной из более простых формул F_1 и F_2 с помощью операций \lnot,\land,\lor,\forall,\exists (операции \to и \leftrightarrow выражаются через \lnot,\land и \lor), то теперь остается научиться находить предваренные нормальные формы для формул


\lnot F_1,\quad (F_1\land F_2),\quad (F_1\lor F_2),\quad (\forall\xi)(F_1),\quad (\exists\xi)(F_1),

если известны предваренные нормальные формы F_{1}^{\ast} и F_{2}^{\ast} формул F_1 и F_2 соответственно. Пусть, например, F_{1}^{\ast} имеет вид


(\forall x_1) (\forall x_2) (\exists x_3)\ldots (\exists x_n)\bigl(G_1(x_1,\ldots,x_n)\bigr)

a F_{2}^{\ast} имеет вид (\exists y_1)(\forall y_2)\ldots (\forall y_m)\bigl(G_2(y_1,\ldots,y_m)\bigr).


Рассмотрим формулу \lnot F_1. Поскольку F_1\cong F_{1}^{\ast}, то \lnot F_1\cong \lnot F_{1}^{\ast}. Но формула \lnot F_{1}^{\ast}, в свою очередь, равносильна, на основании законов де Моргана для кванторов (теорема 21.9), формуле


(\exists x_1)(\exists x_2)(\forall x_3)\ldots (\forall x_n)\bigl(\lnot G_1(x_1,\ldots,x_n)\bigr).

Остается по законам де Моргана для конъюнкции и дизъюнкции (теорема 4.4, пункты р, с) пронести знак отрицания до предикатных переменных: \lnot G_1\cong\lnot G_{1}^{\ast}. Тогда \lnot F_1 будет иметь предваренную нормальную форму


(\exists x_1)(\exists x_2)(\forall x_3)\ldots (\forall x_n)\bigl(G_{1}^{\ast}(x_1,\ldots,x_n)\bigr).

Далее, покажем, как отыскивается предваренная нормальная форма для F, если F есть (F_1\land F_2). Поскольку при переименовании связанной переменной формула, очевидно, переходит в равносильную, то можно считать, что переменные x_1,\ldots,x_n не входят в формулу F_{2}^{\ast}, а переменные y_1,\ldots,y_m не входят в F_{1}^{\ast}. Ясно, что F_1\land F_2\cong F_{1}^{\ast}\land F_{2}^{\ast}, но последняя формула еще не представляет собой предваренной нормальной формы. Покажем, как ее можно преобразовать к такой форме. На основании равносильности (получаемой из тавтологии) теоремы 21.11, а формула ( F_{1}^{\ast}\land F_{2}^{\ast}) равносильна формуле


(\forall x_1)\bigl[(\forall x_2)(\exists x_3)\ldots (\exists x_n) \bigl(G_1(x_1, \ldots, x_n) \bigr)\land (\exists y_1)(\forall y_2)\ldots (\forall y_m)\bigl(G_2(y_1,\ldots,y_m)\bigr)\bigr]

Теперь можно производить равносильные преобразования под знаком квантора \forall x_1 в квадратных скобках, потому что в результате связывания квантором по одной и той же переменной x_1 двух равносильных формул мы снова получим равносильные формулы. Тогда, на основании той же равносильности, последняя формула равносильна формуле


(\forall x_1)(\forall x_2) \bigl[(\exists x_3)\ldots (\exists x_n) \bigl(G_1(x_1, \ldots, x_n) \bigr)\land (\exists y_1)(\forall y_2)\ldots (\forall y_m)\bigl(G_2(y_1,\ldots,y_m)\bigr)\bigr]

И так далее. Наконец, на основании равносильности (получаемой из тавтологии) теоремы 21.11 (пункт г) последняя формула равносильна формуле


(\forall x_1)(\forall x_2) (\exists x_3)\ldots (\exists x_n) \bigl[\bigl(G_1(x_1, \ldots, x_n) \bigr)\land (\exists y_1)(\forall y_2)\ldots (\forall y_m)\bigl(G_2(y_1,\ldots,y_m)\bigr)\bigr]

Таким же образом кванторы, стоящие перед формулой G_2, выносятся за квадратные скобки. В результате получим формулу


(\forall x_1)(\forall x_2) (\exists x_3)\ldots (\exists x_n)~ (\exists y_1)(\forall y_2)\ldots (\forall y_m) \bigl[\bigl(G_1(x_1, \ldots, x_n) \bigr)\land \bigl(G_2(y_1, \ldots, y_m)\bigr) \bigr]

равносильную формуле (F_1\land F_2) и являющуюся предваренной нормальной формой этой формулы.


Аналогичным образом при помощи равносильностей (получаемых из тавтологий) теоремы 21.11 (пункт б) можно построить предваренную нормальную форму для формулы (F_1\lor F_2), исходя из предваренных нормальных форм F_{1}^{\ast} и F_{2}^{\ast} формул F_1 и F_2 соответственно.


Наконец, нетрудно понять, что формула (\forall\xi)(F_{1}^{\ast}) равносильна формуле (\forall\xi)(F_1) и является ее предваренной нормальной формой. Аналогично, (\exists\xi)(F_{1}^{\ast}) — предваренная нормальная форма для формулы (\exists\xi)(F_1).


Итак, в каждом случае F обладает предваренной нормальной формой. Теорема доказана.




Логическое следование формул логики предикатов


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


(\exists y)(\forall x)\bigl(F(x,y)\bigr)\vDash (\forall x)(\exists y)\bigl(F(x,y)\bigr),

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


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


\begin{aligned} (\exists x)\bigl(P(x)\land Q(x)\bigr)&\vDash (\exists x)\bigl(P(x)\bigr)\land (\exists x)\bigl(Q(x)\bigr);\\[2pt] (\forall x)\bigl(P(x)\bigr)\lor (\forall x)\bigl(Q(x)\bigr)&\vDash (\forall x)\bigl(P(x)\lor Q(x)\bigr);\\[2pt] (\exists x)\bigl(P(x)\bigr)\to (\forall x)\bigl(Q(x)\bigr)&\vDash (\forall x)\bigl(P(x)\to Q(x)\bigr);\\[2pt] (\forall x)\bigl(P(x)\to Q(x)\bigr)&\vDash (\forall x)\bigl(P(x)\bigr)\to (\forall x)\bigl(Q(x)\bigr);\\[2pt] (\forall x)\bigl(P(x)\to Q(x)\bigr)&\vDash (\exists x)\bigl(P(x)\bigr)\to (\exists x)\bigl(Q(x)\bigr).\end{aligned}

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


\vDash (\forall x)\bigl(F(x)\bigr)\to F(y),\qquad \vDash F(y)\to (\exists x)\bigl(F(x)\bigr)

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


1) (\forall x)(F(x))\vDash F(y) — правило удаления квантора общности или правило универсальной конкретизации);

2) F(y)\vDash (\exists x)(F(x)) — правило введения квантора существования (или правило экзистенциального обобщения).


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


\frac{\Gamma\vDash F(x)}{\Gamma\vDash (\forall x)(F(x))}\,;\qquad \frac{\Gamma, F(x)\vDash G}{\Gamma, (\exists x)(F(x))\vDash G}\,,

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

Обоснуем, например, первое из этих правил (второе обоснуйте самостоятельно). По условию \Gamma\vDash F(x), т.е. формула F(x) превращается в тождественно истинный предикат при всякой такой -интерпретации, при которой в тождественно истинные предикаты превращаются все формулы из совокупности \Gamma. Пусть мы имеем такую интерпретацию и при ней формула F(x) превращается в тождественно истинный предикат F_0(x,y_1,\ldots,y_n) от переменных x,y_1,\ldots,y_n. Тогда, по определению квантора общности, предикат (\forall x)(F_0(x,y_1,\ldots,y_n)) от переменных y_1,\ldots,y_n также будет тождественно истинным. Это и означает, что \Gamma\vDash (\forall x)(F(x)).

Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Кнопка "Поделиться"
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.

Часовой пояс: UTC + 3 часа [ Летнее время ]


Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved