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

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

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

Теоретический раздел
Часовой пояс: UTC + 4 часа [ Летнее время ]
MathHelpPlanet.com RSS-лента Математического форума

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


Тавтологии логики предикатов

Тавтологии логики предикатов


Нахождение тавтологий является одной из важнейших задач логики предикатов, как и алгебры высказываний. Но если в алгебре высказываний имеется общий метод определения, является или нет данная формула тавтологией (это — метод составления таблицы истинности для формулы), то в логике предикатов такого общего метода не существует. Каждая формула подлежит изучению индивидуальным методом на тождественную истинность. Дело здесь в том, что каждое высказывание имеет только одно из двух логических значений: "истина" или "ложь"", тогда как значение предиката зависит от выбора значений его предметных переменных, который, вообще говоря, можно сделать бесконечным числом способов.


Рассмотрим наиболее важные тавтологии логики предикатов. О значении тавтологий алгебры высказываний подробно говорилось ранее. Все сказанное там сохраняет свое значение и для тавтологий логики предикатов. Но, как уже отмечалось, язык логики предикатов более тонок, а поэтому тавтологии логики предикатов более тонко отражают процессы логических умозаключений.


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


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


Доказательство. Пусть [math]F(X_1,X_2,\ldots,X_n)[/math] — тавтология алгебры высказываний и


[math]P_1(x_1,x_2,\ldots,x_{m_1}),\quad P_2(y_1,y_2,\ldots,y_{m_2}),\quad \ldots,\quad P_n(z_1,z_2,\ldots,z_{m_n})[/math]

являются предикатные переменные. Подставим их в данную формулу вместо пропозициональных переменных [math]X_1,X_2,\ldots,X_n[/math] соответственно. Получим формулу логики предикатов: [math]F\bigl(P_1(x_1,\ldots,x_{m_1}),\ldots, P_n(z_1,\ldots,z_{m_n})\bigr)[/math]. Если теперь вместо предикатных переменных подставить произвольные конкретные предикаты [math]A_1(x_1, \ldots, x_{m_1}),\ldots, A_n(z_1,\ldots,z_{m_n})[/math], то формула превратится в конкретный предикат [math]F\bigl(A_1(x_1,\ldots,x_{m_1}),\ldots, A_n(z_1, \ldots, z_{m_n})\bigr)[/math]. Этот предикат тождественно истинный, потому что подстановка вместо предметных переменных [math]x_1,\ldots,x_{m_1},\ldots, z_1, \ldots, z_{m_n}[/math] любых конкретных предметов [math]a_1, \ldots, a_{m_1},\ldots,c_1, \ldots, c_{m_n}[/math] из соответствующих множеств превращает данный предикат в высказывание [math]F\bigl(A_1(x_1,\ldots,x_{m_1}),\ldots, A_n(z_1, \ldots, z_{m_n}) \bigr)[/math], которое может быть получено также в результате подстановки в исходную тавтологию [math]F(X_1,X_2,\ldots,X_n)[/math] алгебры высказываний вместо пропозициональных переменных [math]X_1,X_2,\ldots,X_n[/math] конкретных высказываний [math]A_1(a_1, \ldots, a_{m_1}),\ldots, A_n(c_1, \ldots, c_{m_n})[/math] соответственно и потому истинно. Следовательно, формула [math]F(P_1,P_2,\ldots,P_n)[/math] логики предикатов также является тавтологией. Теорема доказана.


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




Законы де Моргана для кванторов


Теорема 21.9 (законы де Моргана для кванторов). Следующие формулы логики предикатов являются тавтологиями:


а) [math]\lnot (\forall x)(P(x)) \leftrightarrow (\exists x)(\lnot P(x))[/math];
б) [math]\lnot (\exists x)(P(x)) \leftrightarrow (\forall x)(\lnot P(x))[/math].

Доказательство. Докажем тождественную истинность формулы а). (Тождественную истинность формулы б) предлагается проверить самостоятельно.) Данная формула замкнута, т. е. не имеет свободных предметных переменных. Поэтому, подставив в эту формулу вместо предикатной переменной [math]P(x)[/math] любой конкретный одноместный предикат [math]A(x)[/math], определенный на некотором множестве [math]M[/math], получим высказывание


[math]\lnot (\forall x)\bigl(A(x)\bigr) \leftrightarrow (\exists x)\bigl(\lnot A(x)\bigr).[/math]
(1)

Для доказательства его истинности нужно убедиться, что обе части эквивалентности одновременно истинны или одновременно ложны. В самом деле, высказывание [math]\lnot (\forall x)(A(x))[/math] истинно тогда и только тогда, когда высказывание [math](\forall x)(A(x))[/math] ложно, что возможно на основании определения 20.1 тогда и только тогда, когда предикат [math]A(x)[/math] опровержим. Далее, опровержимость предиката [math]A(z)[/math] означает выполнимость его отрицания [math]\lnot A(x)[/math] (обдумайте это!), что равносильно на основании определения 20.3 истинности высказывания [math](\exists x)(\lnot A(x))[/math]. Итак, высказывание [math]\lnot (\forall x)(A(x))[/math] истинно тогда и только тогда, когда истинно высказывание [math](\exists x)(\lnot A(x))[/math]. Следовательно, высказывание (1) истинно, что и доказывает тождественную истинность формулы а).


Непосредственно из этой теоремы и закона двойного отрицания (теорема 3.1, в) вытекает следствие.


Выражение кванторов одного через другой


Следствие 21.10. Следующие формулы логики предикатов являются тавтологиями:


а) [math](\forall x)(P(x)) \leftrightarrow \lnot (\exists x)(\lnot P(x))[/math];
б) [math](\exists x)(P(x)) \leftrightarrow \lnot (\forall x)(\lnot P(x))[/math].

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




Пронесение кванторов через конъюнкцию и дизъюнкцию


Теорема 21.11 (законы пронесения кванторов через конъюнкцию и дизъюнкцию). Следующие формулы логики предикатов являются тавтологиями:


а) [math](\forall x) (P(x)\land Q(x)) \leftrightarrow (\forall x)(P(x)) \land (\forall x)(Q(x))[/math];
б) [math](\exists x) (P(x)\lor Q(x)) \leftrightarrow (\exists x) (P(x)) \lor (\exists x)(Q(x))[/math];
в) [math](\forall x)(P(x)\lor Q) \leftrightarrow (\forall x)(P(x))\lor Q[/math];
г) [math](\exists x)(P(x)\land Q) \leftrightarrow (\exists x)(P(x))\land Q[/math].

Доказательство. а) Подставим вместо предикатных переменных [math]P(x)[/math] и [math]Q(x)[/math] конкретные предикаты [math]A(x)[/math] и [math]B(x)[/math], определенные на некотором множестве [math]M[/math]. Формула превратится в высказывание


[math](\forall x)\bigl(A(x)\land B(x)\bigr) \leftrightarrow (\forall x)\bigl(A(x)\bigr)\land (\forall x)\bigl(B(x)\bigr).[/math]
(1)

Докажем его истинность. На основании определения 20.1 высказывание [math](\forallx)\bigl(A(x)\land B(x)\bigr)[/math] истинно тогда и только тогда, когда предикат [math]A(x)\land B(x)[/math] тождественно истинен, что на основании следствия 19.7 возможно в том и только в том случае, когда оба предиката [math]A(x)[/math] и [math]B(x)[/math] тождественно истинны. Далее, тождественная истинность предикатов [math]A(x)[/math] и [math]B(x)[/math] равносильна, ввиду определения 20.1, истинности высказываний [math](\forall x)(A(x))[/math] и [math](\forall x)(B(x))[/math] соответственно, что равносильно истинности их конъюнкции [math](\forall x)(A(x))\land (\forall x)(B(x))[/math]. Итак, левая и правая части эквивалентности (1) одновременно истинны и одновременно ложны, что дает истинность всего высказывания (1) и тождественную истинность Доказываемой формулы.


Тождественную истинность формул б) и в) предлагается доказать в качестве упражнения.


г) В этой формуле [math]Q[/math] — нульместная предикатная переменная. Поэтому подставим в данную формулу вместо [math]P(x)[/math] конкретный одноместный предикат [math]A(x)[/math], определенный на некотором множестве [math]M[/math], а вместо [math]Q[/math] — конкретное высказывание [math]B[/math]. Формула превратится в высказывание


[math](\exists x)\bigl(A(x)\land B\bigr) \leftrightarrow (\exists x)\bigl(A(x)\bigr)\land B\,.[/math]
(2)

Докажем его истинность. Действительно, на основании определения 20.3 высказывание [math](\exists x)(A(x)\land B)[/math] истинно тогда и только тогда, когда предикат [math]A(x)\land B[/math] выполним. Последнее возможно, если и только если предикаты [math]A(x)[/math] и [math]B[/math] выполнимы. (Напомним, что в конце предыдущего параграфа было условлено под выполнимостью нульместного предиката (высказывания) понимать его истинность.) Далее, выполнимость предиката [math]A(x)[/math] и истинность высказывания [math]B[/math] равносильны истинности высказываний [math](\exists x)(A(x))[/math] и [math]B[/math], а значит, и истинности их конъюнкции [math](\exists x)(A(x))\land B[/math]. Следовательно, высказывание (2) истинно для любых [math]A(x)[/math] и [math]B[/math], а поэтому рассматриваемая формула — тавтология.




Полезно проанализировать и сопоставить между собой тавтологии, связанные с пронесением кванторов через различные логические операции, представленные в теоремах 21.11 и 21.12. Особая важность этих тавтологий будет обнаружена в следующей лекции, где рассматриваются равносильные преобразования формул логики предикатов. Здесь же мы имеем следующее. Квантор общности безоговорочно проносится через конъюнкцию, а также выносится из обоих членов конъюнкции (эта процедура важна для будущих равносильных преобразований формул), а квантор существования — через дизъюнкцию (теорема 21.11, пункты а, б). Проблемы начинаются при столкновении квантора общности с дизъюнкцией и квантора существования с конъюнкцией. Здесь общезначимыми являются формулы не с эквивалентностями, а с импликацией:


[math]\vDash (\exists x)\bigl(P(x)\land Q(x)\bigr)\to \bigl((\exists x)(P(x))\land (\exists x)(Q(x))\bigr);[/math]
(3)

[math]\bigl((\forall x)(P(x))\land (\forall x)(Q(x))\bigr)\to (\forall x)\bigl(P(x)\lor Q(x)\bigr).[/math]
(4)

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


Для формулы (3) такими предикатами могут служить, например, следующие предикаты, заданные над множеством всех вещественных чисел [math]\mathbb{R}:[/math] "[math]x<1[/math]" и "[math]x>2[/math]". Они посылку обратной импликации превращают в истинное высказывание [math](\exists x)(x<1)\land (\exists x)(x>2)[/math], а заключение — в ложное высказывание [math](\exists x)(x<1\land x>2)[/math].


Для формулы (4) подойдут предикаты, также заданные над [math]\mathbb{R}:[/math] "[math]x \leqslant 0[/math]" и "[math]x>0[/math]", превращающие посылку обратной импликации в истинное высказывание [math](\forall x)(x \leqslant 0\lor x>0)[/math], а следствие — в ложное высказывание [math](\forall x)(x \leqslant 0)\lor (\forall x)(x>0)[/math].


Отметим, что тем не менее равносильное пронесение квантора общности через дизъюнкцию и квантора существования через конъюнкцию возможно. Это тот случай, когда один из членов дизъюнкции или конъюнкции не зависит от той предметной переменной, квантор по которой проносится (см. теорему 21.11, пункты в, г).




Пронесение кванторов через импликацию предикатов


Теорема 21.12 (законы пронесения кванторов через импликацию). Следующие формулы логики предикатов являются тавтологиями:


а) [math](\forall x)(P(x)\to Q) \leftrightarrow ((\exists x)(P(x))\to Q)[/math];
б) [math](\exists x)(P(x)\to Q) \leftrightarrow ((\forall x)(P(x))\to Q)[/math];
в) [math](\forall x)(Q\to P(x)) \leftrightarrow (Q\to (\forall x)(P(x)))[/math];
г) [math](\exists x)(Q\to P(x)) \leftrightarrow (Q\to (\exists x)(P(x)))[/math].

Доказательство. Отметим, что предикатная переменная [math]Q[/math] в этих формулах может быть не только нульместной, но и любой n-местной, важно лишь, чтобы в нее не входила предметная переменная х. Итак, пусть [math]Q[/math] есть [math]Q(y_1,\ldots,y_n)[/math]. Будем считать для краткости, что [math]Q[/math] есть одноместная предикатная переменная [math]Q(y)[/math]. Тогда:


а) предположим, что данная формула не является тавтологией. В этом случае существуют такие конкретные предикаты [math]A(x)[/math] и [math]B(x)[/math], определенные на множествах [math]M[/math] и [math]M_1[/math] соответственно, что предикат (от [math]y[/math])


[math](\forall x)\bigl(A(x)\to B(y)\bigr) \leftrightarrow \bigl((\exists x)(A(x))\to B(y)\bigr)[/math]

опровержим, т.е. обращается в ложное высказывание при подстановке вместо предметной переменной [math]y[/math] некоторого конкретного предмета [math]b\in M_1[/math]


[math]\lambda\bigl[ (\forall x)\bigl(A(x(\to B(b)\bigr) \leftrightarrow \bigl((\exists x)(A(x))\to B(b)\bigr)\bigr]=0.[/math]

Эквивалентность ложна, если ее члены принимают разные значения истинности, т. е. здесь могут представиться две возможности:


первая

[math]\lambda\bigl[(\forall x)\bigl(A(x)\to B(b)\bigr)\bigr]=1;[/math]
(1)

[math]\lambda\bigl[(\exists x)\bigl(A(x)\bigr)\to B(b)\bigr]=0[/math]
(2)

и вторая

[math]\lambda\bigl[(\forall x)\bigl(A(x)\to B(b)\bigr)\bigr]=0;[/math]
(3)

[math]\lambda\bigl[(\exists x)\bigl(A(x)\bigr)\to B(b)\bigr]=1.[/math]
(4)

Рассмотрим первую возможность. Из формулы (2), по определению 1.7 импликации, имеем


[math]\lambda\bigl[(\exists x)(A(x))\bigr]=1;[/math]
(5)

[math]\lambda\bigl[B(b)\bigr]=0.[/math]
(6)

Далее, из формулы (5) и по определению 20.3 квантора существования заключаем, что предикат [math]A(x)[/math] выполним, т.е.


[math]\lambda\bigl[A(a)\bigr]=1[/math]
(7)

для некоторого [math]a\n M[/math]. Вернемся к соотношению (1). По определению 20.1 квантора общности предикат [math]A(x)\to B(b)[/math] тождественно истинен. В частности, если вместо предметной переменной [math]x[/math] подставить [math]a\n M[/math], то получим истинное высказывание [math]\lambda\bigl[A(a)\to B(b)\bigr]=1[/math]. Но, учитывая (6) и (7), получаем противоречие:


[math]\lambda\bigl[A(a)\to B(b)\bigr]= \lambda\bigl[A(a)\bigr]\to \lambda\bigl[B(b)\bigr]=1\to 0=0.[/math]

Рассмотрим вторую возможность, выраженную в соотношениях (3), (4). Из формулы (3), на основании определения 20.1 квантора общности, следует, что предикат [math]A(x)\to B(b)[/math] опровержим, т.е. [math]\lambda\bigl[A(a)\to B(b)\bigr]=0[/math] для некоторого [math]a\n M[/math]. Тогда по определению импликации 1.7 получим


[math]\lambda\bigl[A(a)\bigr]=1,\qquad \lambda\bigl[B(b)\bigr]=0.[/math]
(8)

Учитывая второе из соотношений (8), из соотношения (4) заключаем, что [math]\lambda\bigl[(\exists x)(A(x))\bigr]=0[/math]. Последнее означает тождественную ложность предиката [math]A(x)[/math] (см. определение 20.3). В частности, для предмета [math]a\in M[/math] имеем [math]\lambda\bigl[A(a)\bigr]=0[/math], что противоречит первому из соотношений (8).


Итак, в каждом случае приходим к противоречию, доказывающему невозможность сделанного предположения. Следовательно, данная формула — тавтология.


г) Предположим, что данная формула не является тавтологией. Тогда существуют такие конкретные предикаты [math]A(x)[/math] и [math]B(y)[/math], определенные на множествах [math]M[/math] и [math]M_1[/math] соответственно, что предикат (от [math]y[/math])


[math](\exists x)\bigl(B(y)\to A(x)\bigr) \leftrightarrow \bigl(B(y)\to (\exists x)(A(x))\bigr)[/math]

опровержим, т. е. обращается в ложное высказывание при подстановке вместо предметной переменной [math]y[/math] некоторого конкретного предмета [math]b[/math] из [math]M_1:[/math]


[math]\lambda\bigl[(\exists x)\bigl(B(b)\to A(x)\bigr) \leftrightarrow \bigl(B(b)\to (\exists x)(A(x))\bigr)\bigr]=0.[/math]

Эквивалентность ложна в двух случаях. Во-первых, когда


[math]\lambda\bigl[(\exists x)\bigl(B(b)\to A(x)\bigr)\bigr]=1;[/math]
(1)

[math]\lambda\bigl[B(b)\to (\exists x)\bigl(A(x)\bigr)\bigr]=0,[/math]
(2)
и, во-вторых, когда
[math]\lambda\bigl[(\exists x)\bigl(B(b)\to A(x)\bigr)\bigr]=0;[/math]
(3)

[math]\lambda\bigl[B(b)\to (\exists x)\bigl(A(x)\bigr)\bigr]=1.[/math]
(4)

Рассмотрим первый случай. Из соотношения (2), по определению 1.7 импликации, заключаем:


[math]\lambda\bigl[B(b)\bigr]=1;[/math]
(5)

[math]\lambda\bigl[(\exists x)(A(x))\bigr]=0.[/math]
(6)

Соотношение (6) свидетельствует о том, что предикат [math]A(x)[/math] тождественно ложен (определение 20.3). Далее, соотношение (1) показывает, на основании того же определения 20.3, что предикат [math]B(b)\to A(x)[/math] выполним. Учитывая соотношение (5), получаем: существует такой элемент [math]a\in M[/math], что [math]\lambda[A(a)]=1[/math]. Последнее противоречит доказанной выше тождественной ложности предиката [math]A(x)[/math].


Получить противоречие во втором случае, выраженном в соотношениях (3), (4), предлагается самостоятельно. Таким образом, рассматриваемая формула — тавтология.


Докажите тождественную истинность двух оставшихся формул.




Проанализируем теперь ситуацию, связанную с пронесением кванторов через импликацию, а также с их вынесением за знак импликации. В случаях, когда один из членов импликации (посылка или заключение) не зависит от той предметной переменной, по которой проносится квантор, равносильность также возможна. Но ситуация здесь несколько отличается от той, которая имеет место в случаях конъюнкции и дизъюнкции. Если от предметной переменной, стоящей под знаком квантора, не зависит посылка импликации, то соответствующий квантор без изменения проносится к заключению импликации (теорема 21.12, пункт в). Если же от предметной переменной, стоящей под знаком квантора, не зависит заключение импликации, то соответствующий квантор при пронесении его к посылке импликации переворачивается, т. е. меняется на противоположный: квантор общности — на квантор существования, а квантор существования — на квантор общности (теорема 21.12, пункты а, б).


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


[math]\vDash (\exists x)\bigl(P(x)\to Q(x)\bigr) \leftrightarrow \bigl((\forall x)(P(x))\to (\exists x)(Q(x))\bigr).[/math]

В то же время, если мы рассмотрим аналогичную формулу для квантора общности:


[math](\forall x)\bigl(P(x)\to Q(x)\bigr) \leftrightarrow \bigl((\exists x)(P(x))\to (\forall x)(Q(x))\bigr).[/math]

то она уже не будет тавтологией. Тавтологией будет лишь импликация:

[math]\vDash \bigl( (\exists x)(P(x))\to (\forall x)(Q(x))\bigr)\to (\forall x)\bigl(P(x)\to Q(x)\bigr).[/math]

Докажите это самостоятельно. То, что обратная импликация не будет тавтологией, подтверждает пример двух предикатов [math]P(x)\colon[/math] "[math]x[/math] делится на 4" и [math]Q(x)\colon[/math] "x четно", заданных над множеством натуральных чисел.


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


[math]\begin{aligned} &\vDash (\forall x)\bigl(P(x)\to Q(x)\bigr)\to \bigl((\forall x)(P(x))\to (\forall x)(Q(x))\bigr);\\ &\vDash (\forall x)\bigl(P(x)\to Q(x)\bigr)\to \bigl((\exists x)(P(x))\to (\exists x)(Q(x))\bigr). \end{aligned}[/math]

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


В то же время аналогичная конструкция с квантором существования


[math](\exists x)\bigl(P(x)\to Q(x)\bigr)\to \bigl((\exists x)(P(x))\to (\exists x)(Q(x))\bigr)[/math]

уже не будет тавтологией. Пример: [math]P(x)\colon[/math] "[math]x[/math] — четно", [math]Q(x)\colon[/math] "[math]x<1[/math]", [math]x\in \mathbb{N}[/math]. Не будет тавтологией и обратная импликация. Пример: [math]P(x)\colon[/math] "[math]x>2[/math]" и [math]Q(x)\colon[/math] "[math]x<1[/math]", [math]x\in \mathbb{R}[/math].




Удаление квантора общности и введение квантора существования


Теорема 21.13 (законы удаления квантора общности и введения квантора существования). Следующие формулы логики предикатов являются тавтологиями:


а) [math](\forall x)(P(y))\to P(y)[/math];
б) [math]P(y)\to (\exists x)(P(x))[/math].

Доказательство. Проверим, что формула а) тождественно истинна (соответствующую проверку для формулы б) выполнить самостоятельно). Предположим, что формула а) не тождественно истинна. Это значит: существует такой предикат [math]A(x)[/math], определенный на некотором множестве [math]M[/math], что предикат (от [math]y[/math]) [math](\forall x)(A(x))\to A(y)[/math] опровержим, т.е. превращается в ложное высказывание при подстановке вместо у некоторого [math]a\in M\colon[/math] [math]\lambda\bigl[(\forall x)(A(x)\to A(a))\bigr]=0[/math]. Последнее означает, что


[math]\lambda\bigl[(\forall x)(A(x))\bigr]=1;[/math]
(1)

[math]\lambda\bigl[A(a)\bigr]=0.[/math]
(2)

Из соотношения (1) заключаем, что предикат [math]A(x)[/math] тождественно истинный. Но это противоречит соотношению (2). Следовательно, сделанное предположение неверно, и данная формула — тавтология.




Законы коммутативности для кванторов


Теорема 21.14 (законы коммутативности для кванторов). Следующие формулы логики предикатов являются тавтологиями:


а) [math](\forall x)(\forall y)(P(x,y)) \leftrightarrow (\forall y)(\forall x)(P(x,y))[/math];
б) [math](\exists x)(\exists y)(P(x,y)) \leftrightarrow (\exists y)(\exists x)(P(x,y))[/math];
в) [math](\exists y)(\forall x)(P(x,y)) \to (\forall x)(\exists y)(P(x,y))[/math].

Доказательство. Тождественная истинность первых двух формул достаточно очевидна (проверьте самостоятельно).


Предположим, что формула в) — не тавтология. Тогда существует такой предикат [math]A(x,y)[/math], определенный на множествах [math]M_1[/math] и [math]M_2[/math], что высказывание


[math](\exists y)(\forall x)(A(x,y)) \to (\forall x)(\exists y)(A(x,y))[/math]

ложно. Импликация ложна, если и только если
[math]\lambda\bigl[(\exists y) (\forall x)(A(x,y))\bigr]=1;[/math]
(1)

[math]\lambda\bigl[(\forall x) (\exists y)(A(x,y))\bigr]=0.[/math]
(2)

Из соотношения (1) по определению квантора существования следует, что предикат (от [math]y[/math]) [math](\forall x)(A(x,y))[/math] выполним, т.е. [math]\lambda\bigl[(\forall x)(A(x,b))\bigr]=1[/math] для некоторого [math]b\in M_2[/math]. Последнее, по определению 20.1 квантора общности, означает, что предикат [math]A(x,b)[/math] тождественно истинен на [math]M_1[/math]. Следовательно, тождественно истинным на [math]M_1[/math] будет и одноместный (от [math]x[/math]) предикат [math](\exists x)(A(x,y))[/math]. Но тогда, по определению квантора общности, [math]\lambda\bigl[(\forall x)(\exists y)(A(x,y))\bigr]=1[/math], что противоречит соотношению (2). Следовательно, данная формула — тавтология. Теорема доказана.


Во всех доказанных тавтологиях предикатные переменные нульместны, одноместны или (в последней теореме) двухместны. Сохранится ли тождественная истинность этих формул, если считать, что входящие в них предикатные переменные зависят от произвольного числа предметных переменных? Положительный ответ содержится в следующей теореме.




Теорема 21.15. Если в тавтологиях теорем 21.9–21.14 считать, что предикатные переменные зависят от произвольного конечного числа предметных переменных, то полученные формулы будут также тавтологиями логики предикатов.


Доказательство. При доказательстве теоремы 21.12 уже была предпринята попытка к расширению смысла приведенных там тавтологий: под предикатной переменной [math]Q[/math] понималась n-местная предикатная переменная [math]Q(y_1,y_2,\ldots,y_n)[/math]. Можно было бы и под одноместной предикатной переменной [math]P(x)[/math] понимать m-местную предикатную переменную [math]P(x_1,x_2,\ldots,x_m)[/math], а квантор общности рассматривать по [math]x_1[/math] считая, что [math]x_1[/math] не входит в число предметных переменных предикатной переменной [math]Q(y_1,y_2,\ldots,y_n)[/math].


Докажем, например, тождественную истинность формулы из теоремы 21.11, в, считая [math]P[/math] m-местной предикатной переменной [math]P(x_1,x_2,\ldots,x_m)[/math], a [math]Q[/math] — n-местной предикатной переменной [math]Q(y_1,y_2,\ldots,y_n)[/math]. Причем пусть [math]x_1[/math] не содержится среди предметных переменных [math]y_1,y_2,\ldots,y_n[/math], хотя некоторые (или все) из переменных [math]x_2,\ldots,x_m[/math] могут содержаться среди переменных [math]y_1,y_2,\ldots,y_n[/math]. Итак, требуется доказать тождественную истинность формулы


[math]\begin{aligned}&(\forall x_1)\bigl(P(x_1,x_2,\ldots,x_m)\lor Q(y_1,y_2,\ldots,y_n)\bigr) \leftrightarrow\\ &\leftrightarrow (\forall x_1)\bigl(P(x_1,x_2,\ldots,x_m)\bigr) \lor Q(y_1,y_2,\ldots,y_n). \end{aligned}[/math]
(1)

Подставим вместо предикатных переменных [math]P[/math] и [math]Q[/math] конкретные предикаты [math]A(x_1,x_2,\ldots,x_m)[/math] и [math]B(y_1,y_2,\ldots,y_n)[/math], определенные на множествах [math]M_1,M_2,\ldots,M_m[/math] и [math]N_1,N_2,\ldots,N_n[/math] соответственно. Получим (m-1+n)-местный предикат


[math]\begin{aligned}&(\forall x_1)\bigl(A(x_1,x_2,\ldots,x_m)\lor B(y_1,y_2,\ldots,y_n)\bigr) \leftrightarrow\\ &\leftrightarrow (\forall x_1)\bigl(A(x_1,x_2,\ldots,x_m)\bigr) \lor B(y_1,y_2,\ldots,y_n). \end{aligned}[/math]
(2)

определенный на множествах [math]M_1,M_2,\ldots,M_m[/math] и [math]N_1,N_2,\ldots,N_n[/math] (в случае, если некоторые переменные [math]x_2,\ldots,x_m[/math] встречаются среди переменных [math]y_1,y_2,\ldots,y_n[/math] "местность" полученного предиката будет меньше). Докажем тождественную истинность данного предиката. Для этого проверим, что он превратится в истинное высказывание для произвольных элементов [math]a_2,\ldots,a_m[/math] и [math]b_2,\ldots,b_n[/math] множеств [math]M_2,\ldots,M_m[/math] и [math]N_2,\ldots,N_n[/math] соответственно. Действительно, рассмотрим одноместный (от [math]x_1[/math]) предикат [math]A(x_1,a_2,\ldots,a_m)[/math], определенный на множестве [math]M_1[/math] и полученный из предиката [math]A(x_1,x_2,\ldots,x_m)[/math] в результате подстановки вместо предметных переменных [math]x_2,\ldots,x_m[/math] элементов [math]a_2,\ldots,a_m[/math] соответственно, и высказывание [math]B(b_1,b_2,\ldots,b_n)[/math]. Подставим их в тавтологию теоремы 21.11, в вместо одноместной предикатной переменной [math]P(x)[/math] и нульместной предикатной переменной [math]Q[/math] соответственно. Получим истинное высказывание


[math]\begin{aligned}&(\forall x_1)\bigl(A(x_1,a_2,\ldots,a_m)\lor B(b_1,b_2,\ldots,b_n)\bigr) \leftrightarrow\\ &\leftrightarrow (\forall x_1)\bigl(A(x_1,a_2,\ldots,a_m)\bigr) \lor B(b_1,b_2,\ldots,b_n). \end{aligned}[/math]

Это же высказывание получится, если в предикат (2) подставить вместо его предметных переменных [math]x_2,\ldots,a_m[/math] и [math]y_1,y_2,\ldots,y_n[/math] элементы [math]a_2,\ldots,a_m[/math] и [math]b_1,b_2,\ldots,b_n[/math] соответственно. Итак, любые предикаты превращают формулу (1) в тождественно истинный предикат. Следовательно, эта формула — тавтология.




Замечание 21.16. В распространении взгляда на тавтологии, выраженного в теоремах 21.9–21.14, можно пойти еще дальше: считать, что буквы [math]P[/math] и [math]Q[/math] представляют собой произвольные формулы логики предикатов, а не просто n-местные предикатные переменные (представляющие собой на основании определения 21.1 так называемые элементарные или атомарные формулы). Получаемые формулы также будут тавтологиями логики предикатов.


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


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


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

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