Математическая Логика, 01 семинар (от 26 сентября)

Материал из eSyr's wiki.

Предыдущий семинар | Следующий семинар

Задачи: http://mathcyb.cs.msu.su/paper/zakh/all_tasks.pdf

[править] Задача 1.1

Каждый любит сам себя. Значит, кто-то кого-то любит.

[править] Решение

Опишем алфавит:

• Константы: нет
• Операции: нет
• Отношение:
  • «любить». Двуместное. Обозначим его как L⁽²⁾(x, y): «х любит y»

На первый взгляд, используя дословный перевод, получим нечто вроде

• «Каждый любит сам себя»: φ₁: ∀x L⁽²⁾(x, х)
• «Значит, кто-то кого-то любит» φ₂: ∃x (∃y L⁽²⁾(x, y))
• φ₁ → φ₂

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

• φ₁ & (φ₁ → φ₂)

С подобными тонкостями мы будем сталкиваться на данном шагу. И с подобными тонкостями сталкиваются постоянно при заполнении баз знании. Поэтому не следует удивляться, что заполненная наспех экспертная система не будет работать.

[править] Задача 1.2

Если задача имеет решение, то математик может ее решить. Я — математик, но не могу решить этой задачи. Значит, задача неразрешима.

[править] Решение

Опишем алфавит:

• Константы:
  • «я» — местоимение, обозначающее автора высказывания. Вполне себе обозначение предмета
  • «эта задача» — указание на совершенно конкретную задачу
• Операции: нет
• Отношение:
  • M⁽¹⁾(x): «х — математик»
  • D⁽¹⁾(y): «х — разрешимая задача»
  • S⁽²⁾(x, y): «х умеет решать y»

Сразу (не вдаваясь в суть фразы, анализируя только её структуру) понятно, что фраза будет иметь вид φ₁ & φ₂ & (φ₁ & φ₂ → φ₃). Начнём строить φ₁, φ₂, φ₃:

• «Если задача имеет решение, то математик может ее решить». Не совсем понятно, какая задача здесь подразумевается — любая или конкретная. Аналогично с математиком. Исходя из повседневной логики, можно предположить, что имеются в виду конкретные задачи. Или конкретные математики. Но также имеет право на жизнь мир, где любой математик может решать любую задачу. Возникает неопределённость. Подобных неопределённостей в естественных языках полно, и подавляющую их часть мы упускаем и не обращаем на них внимание. Тем не менее, эта преоблема неоднозначности смысла существует; особенно часто с ней сталкиваются специалисты в сфере международного права, кода необходимо перевести документ так, чтобы он понимался на разных языках одинаково. В некоторых языках избегать многозначности подобного рода помогают артикли. При наличии контекста также можно было бы попытаться разрешить чась неоднозначностей. В данном же случае возможно несколько вариантов, одинаково имеющих право на жизнь:
  • φ₁: ∀x (D(x) → ∀y (M(y) → S(y, x)))
  • φ₁: ∀x (D(x) → ∃y (M(y) & S(y, x)))
  • φ₁: ∃x (D(x) & ∃y (M(y) & S(y, x)))

  Можно заметить, что при смене квантора всеобщности (∀) на квантор существования (∃) импликация (→) меняется на конъюнкцию (&). Это — одна из закономерностей построения формул на языке предикатов.

• «Я — математик, но не могу решить этой задачи». Здесь всё достаточно одназначно, отношение двух констант:
  • φ₂: M(я) & ¬S(я, эта задача)
• «Задача неразрешима». Возникает вопрос, какая задача имеется в виду: какая-то задача вообще или некая определённая задача? В этом случае разрешить этот вопрос помогает контекст: только что говорилось об этой задаче, следовательно, в данном случая она же подразумевается и в этом предложении. Но тут возникает другая, не менее сложная, проблема: каковы границы контекста и приоритеты его применения? Как далеко распространяется контекст? На одно предложение, два, три, абзац, страницу? И какой контекст необходимо использовать, когда их можно использовать несколько? Обычно используется контекст, упоминавшийся последним. Но не всегда это так. Тем не менее, данное предложение можно проинтепретировать однозначно:
  • φ₃: ¬D(эта_задача)

[править] Задача 1.3

Вы можете обманывать всех иногда, вы можете обманывать кого-то всегда, но вы не можете обманывать всех всегда.

[править] Решение

Опишем алфавит:

• Константы:
  • «вы» — константа обозначающая предмет, персону, которой обращено высказывание
• Операции: нет
• Отношение:
  • L⁽³⁾(x, y, t): «х обманывает y в момент времени t»

Структура этой фразы достаточно проста: φ₁ & φ₂ & φ₃. Рассмотрим каждую из функций подробнее:

• «Вы можете обманывать всех иногда». Для этой части фразы можно построить два вариант функции:
  • φ₁: ∀x ∃t (D(вы, x, t))
  • φ₁: ∃t ∀x (D(вы, x, t))

  Эти два варианта несильно отличаются, но смысл имеют разный. Первый вариант говорит о том, что для каждого х существует такой момент времени t, когда его можно обмануть, и этот момент может отличаться для разных x. Второй же вариант говорит о том, существует такой момент t, в который все могут быть обмануты. Оба варианта теоретически подходят (ещё один пример неоднозначности), но по жизненному опыту (что есть понятие весьма расплывчатое) ближе второй вариант. Отсюда же можно сделать вывод: порядок кванторов играет роль.

• «Вы можете обманывать кого-то всегда». Ситуация аналогична предыдущей части фразы. Можно два варианта формулы с различным смыслом:
  • φ₂: ∃x ∀t (D(вы, x, t)) — существует x, которого обманывают в каждый момент времени t
  • φ₂: ∀t ∃x (D(вы, x, t)) — в каждый момент времени t есть x (необязательно один и тот же для всех t), которого вы обманываете

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

• «Вы не можете обманывать всех всегда»