Интерпретация булевых формул с кванторами как игр для двух игроков
Версия от 05:40, 8 октября 2010; 192.168.0.2 (обсуждение)
Интерпретация булевых формул с кванторами как игр для двух игроков
Рассмотрим формулу
, где - квантор зависящий от чётности . Теперь возьмём двух игроков и первый будет ставить с нечётными номерами, а второй с чётными. Если в итоге получается истина, то побеждает первый игрок, если получается ложь, то выигрывает второй. Если истинна, то побеждает первый игрок, в противном случае побеждает второй (при правильных ходах). Пусть истинно, тогда отделим первый квантор. , тогда по предположению есть такой , что будет истинно. Верно и для любого с предположением для лжи. В итоге получаем, верное утверждение.