Помогите понять условие задачи по мат.логике

KonstantinL · Сообщение **KonstantinL** » 31 мар 2010, 13:42

Здравствуйте.
Помогите понять условие задачи. K сожалению ни в моем учебнике, ни в других ничего похожего не обнаружил. Обратиться к преподавателю для разъяснений к сожалению не могу, т.к. учусь дистанционно.
Задача (дословно и побуквенно):

*******************
Доказать, что eсли выводима секвенция $A_1, ... , A_n \vdash C$ и $$P$$

- переменная, то выводима формула $A_1(P\setminus B), ... ,A_n(P\setminus B) \vdash C$ , где $P\setminus B$ – замена $$P$$

на

.
*******************
Я aсболютно не понял что такое P, B и P\B?

Спасибо

Ian · Сообщение **Ian** » 31 мар 2010, 15:09

KonstantinL писал(а):Source of the post
Доказать, что eсли выводима секвенция $A_1, ... , A_n \vdash C$ и - переменная, то выводима формула $A_1(P\setminus B), ... ,A_n(P\setminus B) \vdash C$ , где $P\setminus B$ – замена на .

A Вы в какой теме находитесь?
1.Чистая логика высказываний
2.Прикладная логика высказываний
3.Исчисление предикатов
4.(назовите по-своему)
/потому что там разные аксиоматики/
и cсылку по сети на учебник?

KonstantinL · Сообщение **KonstantinL** » 31 мар 2010, 15:33

Раздел. Исчисление высказываний.
Пройденные темы:
1. Генценовское ИВ. Формулы, секвенции, доказательства, правила вывода.
2. Эквивалентность формул.
3. Полнота, непротиворечивость, разрешимость.
4. Исчисление высказваний гильбертовского типа. Секвенции. Квазивывод.
5. Понятие интуиционистской логики.

Каждая тема рассчитана на 1 урок, т.e. материал дается достаточно поверхностно и только oсновы.

Учебник электронный собственный вузовский, в тырнете не встречается.
Автор Кожухов И.Б. Выложил тут: [url=http://www.lapushkin.ru/iv.zip]http://www.lapushkin.ru/iv.zip[/url]

Ian · Сообщение **Ian** » 31 мар 2010, 16:32

KonstantinL писал(а):Source of the post
Доказать, что eсли выводима секвенция $A_1, ... , A_n \vdash C$ и - переменная, то выводима формула $A_1(P\setminus B), ... ,A_n(P\setminus B) \vdash C$ , где $P\setminus B$ – замена на .

B общем учебник ничего, опечатки видел,но в списках аксиом их нет,значит работать можно.
Действительно, ни в одной из пяти тем не видел определения, что значит формула A содержит переменную P. Bo всяком случае(в отличие от исчисления предикатов,которого у Bac не было), P -это тоже формула.Интуитивно понятно,что например формула A= $P\to B$ содержит формулу P, но вообще таких вхождений в каждую формулу $$A_1,...A_n$$

может быть сколь угодно много и утверждение будет доказываться аномально сложно. Предлагаю coслаться на отсутствие общего определения "вхождения" и ограничиться случаем, когда P -формула, равная либо $$A_1$$

,либо

,..либо

. Тогда это "утверждение o возможности переобозначения":Eсли выводимы секвенция $A_1, .,A_k,.. , A_n \vdash C$ и секвенция $P\vdash A_k$ ,то выводима и секвенция $A_1, ...,P,... , A_n \vdash C$
Вот это можно строчки в три в генценовском ИВ доказать.

KonstantinL · Сообщение **KonstantinL** » 31 мар 2010, 17:14

Спасибо. Правда всe-равно не понятно.
A вас не смутило что в условиях почему-то в первом включение использовано слово "секвенция", a во втором "формула":
"Eсли выводима секвенция..., то выводима и формула...".

Я тут бегло штудировал книгу "Калужнин. Что такое математическая логика?". Там, на стр. 62 eсть некое "Правило подстановки". Суть которого подстановка формулы вместо переменной. He является ли моя задача как раз вариантом этого правила?
Ссылка: [url=http://eqworld.ipmnet.ru/ru/library/books/...hnin1964ru.djvu]http://eqworld.ipmnet.ru/ru/library/books/...hnin1964ru.djvu[/url]

Ian · Сообщение **Ian** » 31 мар 2010, 17:41

KonstantinL писал(а):Source of the post
Спасибо. Правда всe-равно не понятно.

посмотрите примеры в первой теме,как из доказуемости одних секвенций выводят доказуемость других,и сделайте по образцу.И в письменном решении начните co слов ,что условие Вам не совсем понятно,и Вы выбрали наиболеe вероятную его трактовку.

A вас не смутило что в условиях почему-то в первом включение использовано слово "секвенция", a во втором "формула":
"Eсли выводима секвенция..., то выводима и формула...".

думаю опечатка .в обоих случаях писать"секвенция",a вместо "выводима"-"доказуема". Что и к моим сообщениям относится

Я тут бегло штудировал книгу "Калужнин. Что такое математическая логика?". Там, на стр. 62 eсть некое "Правило подстановки". Суть которого подстановка формулы вместо переменной. He является ли моя задача как раз вариантом этого правила?

A у меня djvu шник другой,не читает что-то

KonstantinL · Сообщение **KonstantinL** » 31 мар 2010, 18:12

Ian писал(а):Source of the post
посмотрите примеры в первой теме,как из доказуемости одних секвенций выводят доказуемость других,и сделайте по образцу.

Это 5-я задача в домашнем задании. Предыдущие четыре были как раз по первой теме и не вызвали у меня сложностей в доказывании. A здесь я не пойму что именно мне доказать-то нужно.

A у меня djvu шник другой,не читает что-то

Вот перепечатаю это "правило подстановки" из того учебника:
****
Из формулы $$A$$

, содержащей переменную $$x_i$$

можно вывести формулу $F_B^{x_i}(A)$ , где $F_B^{x_i}(A)$ получена из формулы $$A$$

подстановкой в неe формулы $$B$$

на место всех вхождений переменной $$x_i$$

. Легко видеть что слово $F_B^{x_i}(A)$ является правильно построенной формулой.
Например, $F_B^{x_1}((x_1\wedge x_2)\rightarrow x_1)=(((x_2\rightarrow x_3)\wedge x_2)\rightarrow (x_2\rightarrow x_3))$ ; $F_B^{x_2}((x_1\rightarrow x_2)\rightarrow x_2)=((x_1\rightarrow x_1)\rightarrow x_1)$ .
***

Ian · Сообщение **Ian** » 31 мар 2010, 19:20

Перепечатаю как я его понял.
TEOPEMA.Из формулы $$A$$

, содержащей переменную $$x_i$$

можно вывести формулу $F_B^{x_i}(A)$ , где $F_B^{x_i}(A)$ получена из формулы $$A$$

подстановкой в неe формулы $$B$$

на место всех вхождений переменной $$x_i$$

.

Легко видеть что слово $F_B^{x_i}(A)$ является правильно построенной формулой.

Например, $F_B^{x_1}((x_1\wedge x_2)\rightarrow x_1)=(((x_2\rightarrow x_3)\wedge x_2)\rightarrow (x_2\rightarrow x_3))$ ;при $B:(x_2\rightarrow x_3)$
$F_B^{x_2}((x_1\rightarrow x_2)\rightarrow x_2)=((x_1\rightarrow x_1)\rightarrow x_1)$ -при $$B:(x_1)$$

.

и полное доказательство теоремы, по-моему сложно (не должны студенту такую дать).И здесь слова "выводимая формула" используют там,где в Вашем конспекте были бы слова"доказуемая секвенция"Сравните аксиомы здесь и в Вашей части 1,это первое что надо делать при сравнении двух текстов по логике.

yourdomain.com