Интерпретация булевых формул с кванторами как игр для двух игроков

Материал из Викиконспекты
Версия от 03:58, 8 октября 2010; Zarubkin (обсуждение | вклад) (Новая страница: «'''Интерпретация булевых формул с кванторами как игр для двух игроков''' Рассмотрим формул…»)
(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

Интерпретация булевых формул с кванторами как игр для двух игроков

Рассмотрим формулу [math]\exists x_1 \forall x_2 \exists x_3 \dots Q x_n = \Psi(x_1,\dots ,x_n)[/math], где [math]Q[/math] - квантор зависящий от чётности [math]n[/math]. Теперь возьмём двух игроков и первый будет ставить [math]x[/math] с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если [math]\Psi[/math] истинна, то побеждает второй игрок, в противном случае побеждает первый (при правильных ходах). Пусть [math]\Psi[/math] истинно, тогда отделим первый квантор. [math]\exists x_1\Phi(x1)[/math], тогда по предположению есть такой [math]x_1[/math], что [math]\Phi(x_1)[/math] будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.