0
1

Формулы первого порядка с предикатными символами $%B(x), P(x, y)$% будем интерпретировать на непустых словах в алфавите $%\{0, 1\}$% так: переменные формулы это номера позиций в слове, $%B(i)$% означает, что на $%i$%-м месте стоит $%1$%, $%P(i, j)$% означает, что $%i < j$%. Тогда замкнутая формула $%F$% определяет множество $%L_F$% тех слов, на которых её интерпретация истинна. Проверьте можно ли определить следующие множества слов формулами первого порядка: слова вида $%0^n1^n$%.

задан 12 Дек '20 22:40

изменен 12 Дек '20 22:51

Внешне скорее думается на то, что нельзя. Какого-то совсем простого "одноходового" аргумента не просматривается. Тогда встаёт вопрос, "на что" эта задача может быть, то есть на применение какой теории?

(13 Дек '20 2:31) falcao

@falcao Да, ответ на задачу - нельзя, но вот в том и дело, что я даже и не знаю каких-то методов доказательства того, что что-то нельзя определить логикой первого порядка, думал как-то связать то, что $%0^n1^n$% это КС-язык, с тем, что его нельзя определить вот такими формулами, но не помогло. Возможно, теорема Гёделя о неполноте как-то может помочь.

(13 Дек '20 13:18) Lobster

Нет, теорема Гёделя о неполноте тут совсем никак не поможет -- она о другом. Нужно привлекать какие-то изучаемые в курсе факты, которые к этому имеют отношение. Хотелось бы иметь хотя бы общее представление о том, какие темы рассматривались. Могли быть какие-то общие теоремы о выразимости языков, например. Или приёмы доказательства невыразимости.

(13 Дек '20 13:47) falcao

@falcao http://vyalyy.narod.ru/da3-100722.pdf Эта задача в книге Журавлева "Дискретный анализ. Формальные системы и алгоритмы" на странице 127 - номер 3.13 пункт ж). Там выше есть примеры решенных задач, возможно они помогут.

(13 Дек '20 15:31) Lobster

@Lobster: там дана достаточная информация в плане того, что считается нужным использовать. Я подумаю в этом направлении.

Одного из авторов этой книги я даже знаю лично :) Книга вроде хорошая.

(13 Дек '20 15:45) falcao

@falcao Спасибо!:) Не на физтехе ли вы учились?

(13 Дек '20 15:46) Lobster

@Lobster: нет, я учился на мехмате МГУ.

(13 Дек '20 15:48) falcao

@falcao я узнал, что доказательство можно провести с помощью игр Эренфойхта, выразимы в точности те множества, которые можно представить регулярными выражениями без итерации (звездочки Клини). Уже есть от чего отталкиваться, буду пытаться доказать:)

(16 Дек '20 2:39) Lobster

@Lobster: да, это так. Хорошее описание того, как при помощи игры Эренфойхта можно доказывать, что те или иные модели элементарно эквивалентны или наоборот, есть в книге Верещагина и Шеня.

Более общий факт о выразимости, скорее всего, получается сложнее.

(16 Дек '20 3:22) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

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

Присоединяйтесь!

отмечен:

×467
×56
×40
×34
×29

задан
12 Дек '20 22:40

показан
223 раза

обновлен
16 Дек '20 3:22

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru