Математическая Логика, 01 семинар (от 26 сентября)
Материал из eSyr's wiki.
(Содержимое страницы заменено на «== From Ebaums Inc to MurkLoar. == We at EbaumsWorld consider you as disgrace of human race. Your faggotry level exceeded any imaginab...») |
(Отмена правки № 1431 участника 81.169.129.126 (обсуждение)) |
||
Строка 1: | Строка 1: | ||
- | == | + | Предыдущий семинар | [[Математическая Логика, 02 семинар (от 10 октября)|Следующий семинар]] |
- | + | ||
- | + | '''Задачи:''' http://mathcyb.cs.msu.su/paper/zakh/all_tasks.pdf | |
- | + | ||
+ | == Задача 1.1 == | ||
+ | ''Каждый любит сам себя. Значит, кто-то кого-то любит.'' | ||
+ | |||
+ | === Решение === | ||
+ | Опишем алфавит: | ||
+ | * '''Константы:''' нет | ||
+ | * '''Операции:''' нет | ||
+ | * '''Отношение:''' | ||
+ | ** «любить». Двуместное. Обозначим его как L<sup>(2)</sup>(x, y): «х любит y» | ||
+ | |||
+ | На первый взгляд, используя дословный перевод, получим нечто вроде | ||
+ | |||
+ | * «Каждый любит сам себя»: φ<sub>1</sub>: ∀x L<sup>(2)</sup>(x, х) | ||
+ | * «Значит, кто-то кого-то любит» φ<sub>2</sub>: ∃x (∃y L<sup>(2)</sup>(x, y)) | ||
+ | * φ<sub>1</sub> → φ<sub>2</sub> | ||
+ | |||
+ | Но это верно не в полной мере, так как построенное утверждение верно и в том случае, когда левая часть не является истиной. Например, в мире где все друг другу безразличны, данная импликация будет выполняться, хотя в исходной фразе сказано противоположное. Следовательно, правильной будет формула следующего вида: | ||
+ | |||
+ | * φ<sub>1</sub> & (φ<sub>1</sub> → φ<sub>2</sub>) | ||
+ | |||
+ | С подобными тонкостями мы будем сталкиваться на данном шагу. И с подобными тонкостями сталкиваются постоянно при заполнении баз знании. Поэтому не следует удивляться, что заполненная наспех экспертная система не будет работать. | ||
+ | |||
+ | == Задача 1.2 == | ||
+ | ''Если задача имеет решение, то математик может ее решить. Я — математик, но не могу решить этой задачи. Значит, задача неразрешима.'' | ||
+ | |||
+ | === Решение === | ||
+ | Опишем алфавит: | ||
+ | * '''Константы:''' | ||
+ | ** «я» — местоимение, обозначающее автора высказывания. Вполне себе обозначение предмета | ||
+ | ** «эта задача» — указание на совершенно конкретную задачу | ||
+ | * '''Операции:''' нет | ||
+ | * '''Отношение:''' | ||
+ | ** M<sup>(1)</sup>(x): «х — математик» | ||
+ | ** D<sup>(1)</sup>(y): «х — разрешимая задача» | ||
+ | ** S<sup>(2)</sup>(x, y): «х умеет решать y» | ||
+ | |||
+ | Сразу (не вдаваясь в суть фразы, анализируя только её структуру) понятно, что фраза будет иметь вид φ<sub>1</sub> & φ<sub>2</sub> & (φ<sub>1</sub> & φ<sub>2</sub> → φ<sub>3</sub>). Начнём строить φ<sub>1</sub>, φ<sub>2</sub>, φ<sub>3</sub>: | ||
+ | * «Если задача имеет решение, то математик может ее решить». Не совсем понятно, какая задача здесь подразумевается — любая или конкретная. Аналогично с математиком. Исходя из повседневной логики, можно предположить, что имеются в виду конкретные задачи. Или конкретные математики. Но также имеет право на жизнь мир, где любой математик может решать любую задачу. Возникает неопределённость. Подобных неопределённостей в естественных языках полно, и подавляющую их часть мы упускаем и не обращаем на них внимание. Тем не менее, эта преоблема неоднозначности смысла существует; особенно часто с ней сталкиваются специалисты в сфере международного права, кода необходимо перевести документ так, чтобы он понимался на разных языках одинаково. В некоторых языках избегать многозначности подобного рода помогают артикли. При наличии контекста также можно было бы попытаться разрешить чась неоднозначностей. В данном же случае возможно несколько вариантов, одинаково имеющих право на жизнь: | ||
+ | ** φ<sub>1</sub>: ∀x (D(x) → ∀y (M(y) → S(y, x))) | ||
+ | ** φ<sub>1</sub>: ∀x (D(x) → ∃y (M(y) & S(y, x))) | ||
+ | ** φ<sub>1</sub>: ∃x (D(x) & ∃y (M(y) & S(y, x))) | ||
+ | *: ''Можно заметить, что при смене квантора всеобщности (∀) на квантор существования (∃) импликация (→) меняется на конъюнкцию (&). Это — одна из закономерностей построения формул на языке предикатов.'' | ||
+ | * «Я — математик, но не могу решить этой задачи». Здесь всё достаточно одназначно, отношение двух констант: | ||
+ | ** φ<sub>2</sub>: M(я) & ¬S(я, эта задача) | ||
+ | * «Задача неразрешима». Возникает вопрос, какая задача имеется в виду: какая-то задача вообще или некая определённая задача? В этом случае разрешить этот вопрос помогает контекст: только что говорилось об этой задаче, следовательно, в данном случая она же подразумевается и в этом предложении. Но тут возникает другая, не менее сложная, проблема: каковы границы контекста и приоритеты его применения? Как далеко распространяется контекст? На одно предложение, два, три, абзац, страницу? И какой контекст необходимо использовать, когда их можно использовать несколько? Обычно используется контекст, упоминавшийся последним. Но не всегда это так. Тем не менее, данное предложение можно проинтепретировать однозначно: | ||
+ | ** φ<sub>3</sub>: ¬D(эта_задача) | ||
+ | |||
+ | == Задача 1.3 == | ||
+ | ''Вы можете обманывать всех иногда, вы можете обманывать кого-то всегда, но вы не можете обманывать всех всегда.'' | ||
+ | |||
+ | === Решение === | ||
+ | Опишем алфавит: | ||
+ | * '''Константы:''' | ||
+ | ** «вы» — константа обозначающая предмет, персону, которой обращено высказывание | ||
+ | * '''Операции:''' нет | ||
+ | * '''Отношение:''' | ||
+ | ** L<sup>(3)</sup>(x, y, t): «х обманывает y в момент времени t» | ||
+ | |||
+ | Структура этой фразы достаточно проста: φ<sub>1</sub> & φ<sub>2</sub> & φ<sub>3</sub>. Рассмотрим каждую из функций подробнее: | ||
+ | |||
+ | * «Вы можете обманывать всех иногда». Для этой части фразы можно построить два вариант функции: | ||
+ | ** φ<sub>1</sub>: ∀x ∃t (D(вы, x, t)) | ||
+ | ** φ<sub>1</sub>: ∃t ∀x (D(вы, x, t)) | ||
+ | *: Эти два варианта несильно отличаются, но смысл имеют разный. Первый вариант говорит о том, что для каждого х существует такой момент времени t, когда его можно обмануть, и этот момент может отличаться для разных x. Второй же вариант говорит о том, существует такой момент t, в который все могут быть обмануты. Оба варианта теоретически подходят (ещё один пример неоднозначности), но по жизненному опыту (что есть понятие весьма расплывчатое) ближе второй вариант. Отсюда же можно сделать вывод: ''порядок кванторов играет роль''. | ||
+ | * «Вы можете обманывать кого-то всегда». Ситуация аналогична предыдущей части фразы. Можно два варианта формулы с различным смыслом: | ||
+ | ** φ<sub>2</sub>: ∃x ∀t (D(вы, x, t)) — существует x, которого обманывают в каждый момент времени t | ||
+ | ** φ<sub>2</sub>: ∀t ∃x (D(вы, x, t)) — в каждый момент времени t есть x (необязательно один и тот же для всех t), которого вы обманываете | ||
+ | *: Опять же, оба вариант имеют право на существование, но ближе к духу фразы первый вариант | ||
+ | * «Вы не можете обманывать всех всегда» | ||
+ | |||
+ | {{Математическая Логика}} | ||
+ | {{Lection-stub}} |
Текущая версия
Предыдущий семинар | Следующий семинар
Задачи: http://mathcyb.cs.msu.su/paper/zakh/all_tasks.pdf
Содержание |
[править] Задача 1.1
Каждый любит сам себя. Значит, кто-то кого-то любит.
[править] Решение
Опишем алфавит:
- Константы: нет
- Операции: нет
- Отношение:
- «любить». Двуместное. Обозначим его как L(2)(x, y): «х любит y»
На первый взгляд, используя дословный перевод, получим нечто вроде
- «Каждый любит сам себя»: φ1: ∀x L(2)(x, х)
- «Значит, кто-то кого-то любит» φ2: ∃x (∃y L(2)(x, y))
- φ1 → φ2
Но это верно не в полной мере, так как построенное утверждение верно и в том случае, когда левая часть не является истиной. Например, в мире где все друг другу безразличны, данная импликация будет выполняться, хотя в исходной фразе сказано противоположное. Следовательно, правильной будет формула следующего вида:
- φ1 & (φ1 → φ2)
С подобными тонкостями мы будем сталкиваться на данном шагу. И с подобными тонкостями сталкиваются постоянно при заполнении баз знании. Поэтому не следует удивляться, что заполненная наспех экспертная система не будет работать.
[править] Задача 1.2
Если задача имеет решение, то математик может ее решить. Я — математик, но не могу решить этой задачи. Значит, задача неразрешима.
[править] Решение
Опишем алфавит:
- Константы:
- «я» — местоимение, обозначающее автора высказывания. Вполне себе обозначение предмета
- «эта задача» — указание на совершенно конкретную задачу
- Операции: нет
- Отношение:
- M(1)(x): «х — математик»
- D(1)(y): «х — разрешимая задача»
- S(2)(x, y): «х умеет решать y»
Сразу (не вдаваясь в суть фразы, анализируя только её структуру) понятно, что фраза будет иметь вид φ1 & φ2 & (φ1 & φ2 → φ3). Начнём строить φ1, φ2, φ3:
- «Если задача имеет решение, то математик может ее решить». Не совсем понятно, какая задача здесь подразумевается — любая или конкретная. Аналогично с математиком. Исходя из повседневной логики, можно предположить, что имеются в виду конкретные задачи. Или конкретные математики. Но также имеет право на жизнь мир, где любой математик может решать любую задачу. Возникает неопределённость. Подобных неопределённостей в естественных языках полно, и подавляющую их часть мы упускаем и не обращаем на них внимание. Тем не менее, эта преоблема неоднозначности смысла существует; особенно часто с ней сталкиваются специалисты в сфере международного права, кода необходимо перевести документ так, чтобы он понимался на разных языках одинаково. В некоторых языках избегать многозначности подобного рода помогают артикли. При наличии контекста также можно было бы попытаться разрешить чась неоднозначностей. В данном же случае возможно несколько вариантов, одинаково имеющих право на жизнь:
- φ1: ∀x (D(x) → ∀y (M(y) → S(y, x)))
- φ1: ∀x (D(x) → ∃y (M(y) & S(y, x)))
- φ1: ∃x (D(x) & ∃y (M(y) & S(y, x)))
- Можно заметить, что при смене квантора всеобщности (∀) на квантор существования (∃) импликация (→) меняется на конъюнкцию (&). Это — одна из закономерностей построения формул на языке предикатов.
- «Я — математик, но не могу решить этой задачи». Здесь всё достаточно одназначно, отношение двух констант:
- φ2: M(я) & ¬S(я, эта задача)
- «Задача неразрешима». Возникает вопрос, какая задача имеется в виду: какая-то задача вообще или некая определённая задача? В этом случае разрешить этот вопрос помогает контекст: только что говорилось об этой задаче, следовательно, в данном случая она же подразумевается и в этом предложении. Но тут возникает другая, не менее сложная, проблема: каковы границы контекста и приоритеты его применения? Как далеко распространяется контекст? На одно предложение, два, три, абзац, страницу? И какой контекст необходимо использовать, когда их можно использовать несколько? Обычно используется контекст, упоминавшийся последним. Но не всегда это так. Тем не менее, данное предложение можно проинтепретировать однозначно:
- φ3: ¬D(эта_задача)
[править] Задача 1.3
Вы можете обманывать всех иногда, вы можете обманывать кого-то всегда, но вы не можете обманывать всех всегда.
[править] Решение
Опишем алфавит:
- Константы:
- «вы» — константа обозначающая предмет, персону, которой обращено высказывание
- Операции: нет
- Отношение:
- L(3)(x, y, t): «х обманывает y в момент времени t»
Структура этой фразы достаточно проста: φ1 & φ2 & φ3. Рассмотрим каждую из функций подробнее:
- «Вы можете обманывать всех иногда». Для этой части фразы можно построить два вариант функции:
- φ1: ∀x ∃t (D(вы, x, t))
- φ1: ∃t ∀x (D(вы, x, t))
- Эти два варианта несильно отличаются, но смысл имеют разный. Первый вариант говорит о том, что для каждого х существует такой момент времени t, когда его можно обмануть, и этот момент может отличаться для разных x. Второй же вариант говорит о том, существует такой момент t, в который все могут быть обмануты. Оба варианта теоретически подходят (ещё один пример неоднозначности), но по жизненному опыту (что есть понятие весьма расплывчатое) ближе второй вариант. Отсюда же можно сделать вывод: порядок кванторов играет роль.
- «Вы можете обманывать кого-то всегда». Ситуация аналогична предыдущей части фразы. Можно два варианта формулы с различным смыслом:
- φ2: ∃x ∀t (D(вы, x, t)) — существует x, которого обманывают в каждый момент времени t
- φ2: ∀t ∃x (D(вы, x, t)) — в каждый момент времени t есть x (необязательно один и тот же для всех t), которого вы обманываете
- Опять же, оба вариант имеют право на существование, но ближе к духу фразы первый вариант
- «Вы не можете обманывать всех всегда»
|
|
Ссылки
Официальная страница курса | Задачи
Проведение экзамена | Решение задач: Решение задач методички | Решение задач варианта экзамена 2004 года | Алгоритмы решения задач