2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 11  След.
 
 Re: Математическая логика (по Мендельсону)
Сообщение06.06.2011, 22:05 
Заслуженный участник
Аватара пользователя


04/04/09
1351
«Предложение 2.7. Во всяком исчислении предикатов первого порядка всякая теорема является логически общезначимой.
Доказательство. В силу свойства (VII) понятия истинной формулы (см. стр. 60), аксиомы, задаваемые схемами (1) — (3), логически общезначимы. В силу свойств (X) (следствие) и (XI), логически верны аксиомы, порождаемые схемами (4) — (5). В силу (III) и (VI), правила вывода МР и Gen сохраняют свойство логической общезначимости. Таким образом, всякая теорема любого исчисления предикатов логически общезначима

Пополним список переводческих ляпов. Что значит «логически верны»? Задавать этот вопрос Мендельсону бессмысленно у него во всех трех случаях написано «logically valid» т. е. в русской терминологии «логически общезначимы».

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение08.06.2011, 02:27 
Заслуженный участник
Аватара пользователя


04/04/09
1351
Несколько странных странностей.

Странность 1. «Всякое предложение какого-нибудь формального или естественного языка называется логически истинным (в исчислении предикатов), если оно является частным случаем некоторой логически общезначимой формулы, и называется логически ложным (в исчислении предикатов), если оно есть частный случай некоторого противоречия (в исчислении предикатов).» Страница 63.
Или в оригинале: «Any sentence of a formal or natural language which is an instance of a logically valid wf is called logically true, and an instance of a contradictory wf is said to be logically false

Прежде чем разбирать этот отрывок, я хотел бы понять, что значит для предложения быть «частным случаем некоторой логически общезначимой формулы». Есть только определение частного случая пропозициональной формы. Страница 60. Причем этот отрывок отсутствует в четвертом и пятом изданиях. Я бы не привязывался к этому отрывку. Он стоит особняком и не мешает пониманию текста.
Но,
Странность 2. В доказательстве того факта, что каждая теорема исчисления первого порядка является логически общезначимой (стр. 71), используется такой оборот: «В силу свойства (VII) понятия истинной формулы (см. стр. 60), ...». Или в оригинале: «By property (VII) of the notion of truth (cf. page 53), ...». Но на странице 60 в свойстве (VII) нет ничего об истинной формуле. Там речь идет о формуле, истинной в данной интерпретации (определение на странице 59).
Вообще говоря, вся фраза: «В силу свойства (VII) понятия истинной формулы (см. стр. 60), аксиомы, задаваемые схемами (1) — (3), логически общезначимы.» не пострадает (и станет более осмысленной), если кусок «понятия истинной формулы» просто выкинуть: «В силу свойства (VII) [...] аксиомы, задаваемые схемами (1) — (3), логически общезначимы.» Так как схемы (1) — (3) действительно логически общезначимы как частные случаи тавтологий.

(Оффтоп)

Но некоторые свойства моего характера (склочность) заставляют меня спросить: может быть, я что-то не понял?

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение10.06.2011, 22:27 
Заслуженный участник
Аватара пользователя


04/04/09
1351

(Оффтоп)

Продолжаю неделю переводчика.

«2. Если формула $\mathscr A$ не содержит кванторов и доказуема в исчислении предикатов, ...» Страница 72. А что значит «формула доказуема»? Лезем в оригинал. Там напечатано «provable». Вроде бы правильно. Но... переводчик на странице 36 перевел «proof» как «вывод». Поэтому, конечно, должно быть «2. Если формула $\mathscr A$ не содержит кванторов и выводима в исчислении предикатов, ...» Но это мелочь. Вот более таинственная история.

«Лемма 2.10. Множество всех выражений всякой теории первого порядка счетно (следовательно, счетны в частности: множество всех термов, множество всех формул, множество всех замкнутых формул).
Доказательство. Отнесем каждому символу $u$ нечетное число $g(u)$ по следующему правилу: $ g( ( )=3$, $g( ) ) = 5$, $g(,) = 7$, $g(\neg) = 9$, $g(\to) = 11$, $g(x_k)=5+8k$, $g(a_k)=7+8k$ , $g(f_k^n) =9+ 8\cdot (2^{n} \cdot 3^{n})$, $g(A_k^n) =11+ 8\cdot (2^{n} \cdot 3^{n})$ [; при этом полагаем $g(\forall x_i)=g((x_i))$]. Теперь выражению $u_0u_1\cdots u_r$ отнесем число $2^{g(u_0)}3^{g(u_1)}\cdots p_r^{g(u_r)}$, Где $p_i$$i$-e простое число.»

Что значит "при этом полагаем $g(\forall x_i)=g((x_i))$"? Я поставил этот кусок в квадратные скобки т. к. его нет в первом русском издании 1971 года. Он появился во втором русском издании 1976 года. Как я уже и писал в первых изданиях оригинала забыли ввести в символы теории К символ квантора $\forall$. Здесь же он явно нужен так как нужно значение $g(\forall)$. Что такое $g(\forall x_i)$ вообще тайна, ведь функция $g$ требует в качестве аргумента только один символ, а здесь их сразу два ($ x_i$ рассматривается как единый символ). Еще большую таинственность предает этой истории факт, что во втором английском издании выражение $\forall x_i$ обозначается как $(x_i)$.

В пятом английском издании в символы теории К введен символ $\forall$. И доказательство переделано так: «First assign a distinct positive integer $g(u)$ to each symbol $u$ as follows: $g( ( )=3$, $g( ) ) = 5$, $g(,) = 7$, $g(\neg) = 9$, $g(\to) = 11$, $g(\forall) =13$, $g(x_k)=13+8k$, $g(a_k)=7+8k$ , $g(f_k^n) =1+ 8\cdot (2^{n} \cdot 3^{n})$, $g(A_k^n) =3+ 8\cdot (2^{n} \cdot 3^{n})$. Then, to an expression $u_0u_1\cdots u_r$, associate the number $2^{g(u_0)}3^{g(u_1)}\cdots p_r^{g(u_r)}$, where $p_j$ is the $j$th prime number, starting with $p_0=2$

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение17.06.2011, 19:02 
Заслуженный участник
Аватара пользователя


04/04/09
1351
Виктор Викторов в сообщении #451726 писал(а):
Есть такая «Лемма 1.12. Пусть $\mathscr A$ есть формула, а $B_1, \cdots, B_k$ — пропозициональные буквы, входящие в $\mathscr A$, и пусть задано некоторое распределение истинностных значений для $B_1, \cdots, B_k$. Пусть тогда $B'_i$ есть $B_i$, если $B_i$ принимает значение И, и $\neg B_i$, если $B_i$ принимает значение Л, и пусть, наконец, $\mathscr A'$ есть $\mathscr A$, если при этом распределении $\mathscr A$ принимает значение И, и $\neg \mathscr A$, если $\mathscr A$ принимает значении Л. Тогда $B'_1, \cdots, B'_k\vdash \mathscr A'$.» Страница 43.
Виктор Викторов в сообщении #451726 писал(а):
...каждой пропозициональной форме соответствует ровно столько тавтологий сколько строк в истинностной таблице этой пропозициональной формы.
Есть и соответствующее доказательство. Но меня заинтересовал вопрос: как это продемонстрировать? Вот к чему я пришел.
Пусть у нас есть формула $\mathscr A$. Это любое высказывание может быть тавтология, а может быть и нет. И пусть все пропозициональные буквы этого высказывания: $A_1, A_2, \cdots, A_i, \cdots, A_n$. Тогда существуют ровно столько «выводимостей», ассоциированных с формулой $\mathscr A$, сколько строк у таблицы истинности этой формулы. И все они выглядят так: $?A_1, ?A_2, \cdots, ?A_i, \cdots, ?A_n\vdash  ? \mathscr A$. Надо только правильно вместо знака «?» поставить символ $\neg$ или оставить это место пустым. Формула $?A_1, ?A_2, \cdots, ?A_i, \cdots, ?A_n\vdash  ? \mathscr A$ после использования теоремы дедукции приводит к $\vdash  ?A_1\wedge ?A_2\wedge \cdots\wedge ?A_i\wedge \cdots\wedge ?A_n\to ?\mathscr A$ . Это импликация и её посылкой является конъюнкция. А конъюнкция почти всегда ложна и поэтому данная импликация почти всегда истинна. Но что будет, когда это «почти всегда» не срабатывает, и конъюнкция истинна? Тогда все члены этой конъюнкции истинны. Вот тут-то и срабатывает «правильное» распределение символа $\neg$. Что это за случай когда все члены конъюнкции истинны? Посмотрим на строку распределения истинностных значений: там где стоит «истина» мы просто убираем знак вопроса, а там где стоит «ложь» заменяем знак вопроса на символ $\neg$. Это единственный способ получить истинную конъюнкцию. Вот теперь осторожно! Импликация может оказаться ложной! Но и мы настороже. Опять смотрим на строку распределения истинностных значений. Если высказывание $\mathscr A$ истинно, то проблем нет. А если оно ложно, то поставим перед ним символ $\neg$ и сделаем его истинным. Таким образом, единственный «подозрительный» случай тоже дает истинностное значение «истина» и высказывание $?A_1\wedge ?A_2\wedge \cdots\wedge ?A_i\wedge \cdots\wedge ?A_n\to ?\mathscr A$ -- тавтология.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение24.06.2011, 17:46 
Заслуженный участник
Аватара пользователя


04/04/09
1351
В седьмом томе Большого академического словаря русского языка слово «интерпретация» описано как «истолкование, разъяснение смысла, значения чего-л.» (стр. 329).
Понадобилось мне лезть в этот словарь потому, что в математической логике дается определение термина «интерпретация» а как быть, если я хочу использовать слово «интерпретация» не в смысле этого определения мне не было ясно. Поэтому я пришёл к компромиссному решению: в этом случае я буду писать «истолкование (интерпретация)». Теперь к делу.

«Формулы имеют смысл только тогда, когда имеется какая-нибудь интерпретация входящих в нее символов. Под интерпретацией мы будем понимать всякую систему, состоящую из непустого множества $D{,}$ называемого областью интерпретации, и какого-либо соответствия, относящего каждой предикатной букве $A_j^n$ некоторое n-местное отношение в $D{,}$ каждой функциональной букве $f_j^n$ — некоторую n-местную операцию в $D$ (т. е. функцию, отображающую $D^n$ в $D$) и каждой предметной постоянной $a_i$ — некоторый элемент из $D{.}$» Страница 57.

И хотя первая и вторая фразы этого текста в пятом издании разделены разными разностями, но все равно меня этот текст удивляет. Вторая фраза дает определение интерпретации, и получается, что без, скажем, области интерпретации и разговаривать не о чем. Но вернем в первой фразе обычный смысл слову «интерпретация»: Формулы имеют смысл только тогда, когда имеется какое-нибудь истолкование (интерпретация) входящих в нее символов. Разве обязательно истолковывать эту фразу только в смысле определения данного дальше? Очевидно, что нет.

«... для логики предикатов синтаксический метод теорий первого порядка равносилен семантическому методу, использующему понятия интерпретации, модели, логической общезначимости и т. п.» Страница 79.

Вот теперь всё на своих местах. Определение интерпретации имеет смысл только для семантического метода. А при применении синтаксического метода теорий первого порядка нужно только истолкование (интерпретация) сигнатуры. Жить только с синтаксическим методом, конечно, не очень удобно (и это мягко сказано), но речь-то идет о принципе.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение25.06.2011, 02:34 
Заслуженный участник
Аватара пользователя


04/04/09
1351
Одним из важных результатов пятого параграфа «Теоремы о полноте» является теорема Гёделя:
«Следствие 2.14. (Теорема Гёделя [1930] о полноте.) Во всяком исчислении предикатов первого порядка теоремами являются все те и только те формулы, которые логически общезначимы.» Страница 78.
Но почему она названа теоремой о полноте? Речь идет о «всяком исчислении предикатов первого порядка».

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение25.06.2011, 03:28 
Заслуженный участник
Аватара пользователя


06/10/08
6422
Есть два понятия полноты - дедуктивная и семантическая.
Дедуктивная - это когда для любой формулы $F$ выводима $F$ или $\neg F$
Семантическая - это когда все формулы, истинные в некотором класса интерпретаций, выводимы.
Теорема Геделя о полноте утверждает полноту исчисления предикатов первого порядка относительно класса всех возможных интерпретаций.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение25.06.2011, 03:35 
Заслуженный участник
Аватара пользователя


04/04/09
1351
Спасибо. Первое понятие я знал, а второе - нет.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение28.06.2011, 01:23 
Заслуженный участник
Аватара пользователя


04/04/09
1351
«Предложение 2.12*). Всякая непротиворечивая теория первого порядка имеет счетную модель (т. е. модель со счетной областью).» Страница 75. После этого следует интересное доказательство этого предложения на три страницы, включая следующее определение: «Назовем замкнутым термом всякий терм, не содержащий переменных.» Страница 76.

К пятому изданию это предложение было разбито на три части (по моему к лучшему) и добавилось одно экзотическое определение.
«DEFINITI0NS
1. A closed term is a term without variables.
2. A theory K is a scapegoat theory if, for any wf $\mathscr B(x)$ that has $x$ as its only free variable, there is a closed term $t$ such that
$$\vdash_K (\exists x)\neg \mathscr B(x)\Rightarrow \neg \mathscr B(t)$$LEMMA 2.15 Every consistent theory K has a consistent extension K' such that K' is a scapegoat theory and K' contains denumerably many closed terms.» Страницы 80-81.

«LEMMA 2.16 Let $J$ be a consistent, complete scapegoat theory. Then $J$ has a model M whose domain is the set $D$ of closed terms of $J$.» Страница 82.

«PROPOSITION 2.17* Every consistent theory K has a denumerable model.» Страница 83.

В моем несовешенном переводе:
Определения.
1. Назовем замкнутым термом каждый терм, не содержащий переменных.
2. Назовем теорию K теорией козла отпущения, если для каждой формулы $\mathscr B(x)$, содержащей $x$ в качестве своей единственной свободной переменной, существует замкнутый терм $t$ такой, что
$$\vdash_K (\exists x)\neg \mathscr B(x)\Rightarrow \neg \mathscr B(t)$$Лемма 2.15 Каждая непротиворечивая теория K имеет непротиворечивое расширение K' такое, что K' -- теория козла отпущения и K' содержит счетное множество замкнутых термов.
Лемма 2.16 Пусть $J$ непротиворечивая полная теория козла отпущения. Тогда $J$ имеет модель M, чьей областью является множество $D$ всех замкнутых термов теории $J$.
Предложение 2.17* Всякая непротиворечивая теория K имеет счетную модель.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение28.06.2011, 11:44 
Заслуженный участник
Аватара пользователя


28/09/06
10834
Xaositect в сообщении #462008 писал(а):
Теорема Геделя о полноте утверждает полноту исчисления предикатов первого порядка относительно класса всех возможных интерпретаций.
Ой, а напомните пожалуйста: Что именно является "истинным в классе всех возможных интерпретаций" (т.е. "логически общезначимым")? Вопрос в том, что предложение в языке исчисления предикатов можно сформулировать только тогда, когда определён хотя бы один функциональный символ и хотя бы один - предикатный. Т.е. мы должны считать, что определено столько функциональных и предикатных символов, а также переменных, сколько нам нужно (хотя прикладных аксиом в системе нет)?

P.S. Я раньше уже где-то получал ответ на этот вопрос, но, сорри, подзабыл...

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение28.06.2011, 14:40 
Заслуженный участник
Аватара пользователя


04/04/09
1351
«Формула $\mathscr A$ называется истинной (в данной интерпретации) тогда и только тогда, когда она выполнена на всякой последовательности из $\sum$.» Страница 59.
«Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации.» Страница 62.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение28.06.2011, 15:01 
Заслуженный участник
Аватара пользователя


28/09/06
10834
Виктор Викторов в сообщении #463060 писал(а):
«Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации.» Страница 62.
Это-то понятно. Проблема в том, что без предикатных и функциональных символов нельзя записать ни одной формулы. А если есть какие-то предикатные и функциональные символы, то значит есть какая-то теория (а не голое исчисление предикатов). Т.е. мы говорим об истинности формулы теории, а не формулы исчисления предикатов.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение28.06.2011, 16:47 
Заслуженный участник
Аватара пользователя


04/04/09
1351
epros в сообщении #463007 писал(а):
Что именно является "истинным в классе всех возможных интерпретаций" (т.е. "логически общезначимым")?
Виктор Викторов в сообщении #463060 писал(а):
«Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации.» Страница 62.
epros в сообщении #463063 писал(а):
Это-то понятно.
Этот вопрос разрешён.
Теперь по поводу теории и «голого исчисления предикатов» по Мендельсону. На странице 66 дается определение: «Теория первого порядка, не содержащая собственных аксиом, называется исчислением предикатов первого порядка.» Но... «в исчислении предикатов» появляется раньше (например на странице 62). Я проверил второе английское издание. Никакого исчисления предикатов, появляющегося без всякого определения, начиная со страницы 54 русского издания, там просто нет. У меня есть пять изданий Мендельсона и мне жаль 15-ти долларов на первое английское издание (с которого и сделан русский перевод). Что касается «Проблема в том, что без предикатных и функциональных символов нельзя записать ни одной формулы», то, по моему, срабатывает импликация с ложной посылкой.

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение28.06.2011, 17:08 
Заслуженный участник
Аватара пользователя


28/09/06
10834
Виктор Викторов в сообщении #463107 писал(а):
На странице 66 дается определение: «Теория первого порядка, не содержащая собственных аксиом, называется исчисление предикатов первого порядка.»
Ага, понятно. Значит, мы можем смело считать "логически общезначимыми", например, такие вещи, как:
$\forall x,y,z ~ (x+y=z \to x+y=z)$,
не смущаясь тем, что мы не позаботились предварительно определить переменные $x$, $y$ и $z$, а также двухместный функциональный символ $+$ и двухместный предикатный символ $=$.

Виктор Викторов в сообщении #463107 писал(а):
Что касается «Проблема в том, что без предикатных и функциональных символов нельзя записать ни одной формулы», то по моему срабатывает импликация с ложной посылкой.
В смысле? Раз не существует ни одной формулы, то импликация, содержащая в посылке "если формула истинна в любой интерпретации", истинна? :-)
Какое-то тогда содержание у понятия "логической общезначимости" получается ... гхм ... юридически ничтожным...

 Профиль  
                  
 
 Re: Математическая логика (по Мендельсону)
Сообщение28.06.2011, 17:42 
Заслуженный участник
Аватара пользователя


04/04/09
1351
epros в сообщении #463118 писал(а):
Виктор Викторов в сообщении #463107 писал(а):
На странице 66 дается определение: «Теория первого порядка, не содержащая собственных аксиом, называется исчисление предикатов первого порядка.»
Ага, понятно. Значит, мы можем смело считать "логически общезначимыми", например, такие вещи, как:
$\forall x,y,z ~ (x+y=z \to x+y=z)$,
не смущаясь тем, что мы не позаботились предварительно определить переменные $x$, $y$ и $z$, а также двухместный функциональный символ $+$ и двухместный предикатный символ $=$.

(Оффтоп)

Ваш комментарий напоминает анекдот: «Дайте водицы напиться, а то негде переночевать».
Ещё раз: слова в скобках во фразе «Формула $\mathscr A$ называется логически общезначимой (в исчислении предикатов), если она истинна в каждой интерпретации» скорее всего домыслы переводчика. Во втором издании эта фраза звучит так: «Формула $\mathscr A$ называется логически общезначимой, если она истинна в каждой интерпретации.» Логическая общезначимость не существует без интерпретации. А где «проживают» формулы хорошо сказал Xaositect:
Xaositect в сообщении #445328 писал(а):
Виктор Викторов в сообщении #445277 писал(а):
Вопрос первый: Интерпретация чего? Ответ: Интерпретация символов, входящих в формулы. Есть ли какое-нибудь обобщающее название этих формул? Это ли потом будет интепретацией теории?
Интерпретация сигнатуры(алфавита). То есть мы пока сопоставляем значение только символам. Потом определяется выполнимости формулы при конкретных значениях переменных и общезначимости формулы, а потом уже можно говорить об интерпретации теории - это такая интерпретация, в которой общезначимы все формулы, выводимые в этой теории.
В Вашем же комментарии нужны ещё и собственные аксиомы.

(Оффтоп)

Лучше не смешивать котлеты с мухами.


-- Вт июн 28, 2011 10:52:34 --

epros в сообщении #463118 писал(а):
Раз не существует ни одной формулы, то импликация, содержащая в посылке "если формула истинна в любой интерпретации", истинна? :-)
Если нет формул, то все формулы истинны на всех интерпретациях и, соответственно, общезначимы. Вырожденный случай.

(Оффтоп)

epros в сообщении #463118 писал(а):
Какое-то тогда содержание у понятия "логической общезначимости" получается ... гхм ... юридически ничтожным...
Уже нанял адвоката.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 157 ]  На страницу Пред.  1 ... 3, 4, 5, 6, 7, 8, 9 ... 11  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group