Математическая Логика, 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), которого вы обманываете

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

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