Изменения

Итак, есть выражение <tex>\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)</tex>. Если выражение <tex>\Psi</tex> истинно, то у игрока «существует» есть такие ходы, чтобы прийти к победе. Если же выражение <tex>\Psi</tex> ложно, то у игрока «для всех» есть такие ходы, чтобы прийти к победе. Докажем в случае, когда выражение <tex>\Psi</tex> принимает истинное значение.

{{ТеоремаДокажем |statement=<tex>\Psi(x_1,\dots ,x_n) = \exists x_1 \forall x_2 \exists x_3 \dots Q x_n</tex> {{---}} выражение.# Если выражение <tex>\Psi</tex> истинно, то у игрока «существует» есть такие ходы, чтобы прийти к победе.# Если же выражение <tex>\Psi</tex> ложно, то у игрока «для всех» есть такие ходы, чтобы прийти к победе.|proof=# Доказательство по индукции.#* '''База:''' квантор один.Для одного квантора. #*: Если этот единственный квантор {{---}} «любой», то какой бы параметр не поставил игрок «для всех» выражение будет истинно по предположениюусловию теоремы. #*: Если единственный квантор {{---}} «существует», то , по предположению условию, есть такой параметр, что выражение будет истинно. Его и подставит игрок «существует», после чего сразу победит.#* '''Переход:''' теорема верна, когда выражение <tex>\Psi<br/tex>Пусть теперь верно для любого количества кванторов состоит не превосходящих более, чем из <tex>n-1</tex>. Докажем кванторов, докажем, что она верна и для выражений, состоящих из <tex>n</tex> кванторов. #*: Пусть первый квантор «существует», тогда <tex>\Psi = \exists x_1 \Phi</tex>. По предположению условию теоремы найдётся такой параметр <tex>x_1</tex>, что <tex>\Phi</tex> истинно. Но в выражении выражение <tex>\Phi \: </tex> состоит из <tex>n-1</tex> кванторквантора, значит , для <tex>\Phi</tex> есть набор ходовигрока «существует», при котором он выигрывает. С выбранным <tex>x_1</tex> и полученным набором ходов мы получим победную получаем выигрышную стратегию. #*: Пусть теперь первый квантор «для всех», тогда <tex>\Psi = \forall x_1 \exists x_2 \Phi</tex>. По предположению найдётся такой параметр условию теоремы для любого параметра <tex>x_2x_1</tex> для любого параметра найдётся такой параметр <tex>x_1x_2</tex>, что <tex>\Phi</tex> истинно. Но в выражении выражение <tex>\Phi \: </tex> содержит <tex>n-2</tex> квантора, значит , для <tex>\Phi</tex> есть набор ходовигрока «существует», при котором он выигрывает. С выбранным <tex>x_2</tex> и полученным набором ходов мы получим победную выигрышную стратегию. # Доказательство существования победной выигрышной стратегии для игрока «для всех» при ложном выражении <tex>\Psi</tex> аналогично.}}