2014 dxdy logo

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

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


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему
 
 Обоснование схемы доказательства
Сообщение12.01.2017, 16:57 
Аватара пользователя


11/03/12
586
Беларусь, Минск
В учебнике "Алгебра и теория чисел", написанном Л. Я. Куликовым, есть такое упражнение: "Обоснуйте следующие схемы доказательств:
(a) $\frac{A \to  \lnot B}{B  \to \lnot A};$ ...
Правильно, ли я понимаю, что для выполнения упражнения нужно показать, что утверждение, записанное под чертой, является следствием утверждения, записанного над чертой, и это можно сделать, например, если заметить, что оба утверждения эквивалентны, и воспользоваться правилом удаления эквиваленции $\frac{P \leftrightarrow Q}{P \to Q}$? Или такие упражнения нужно выполнять иначе?

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 17:43 
Заслуженный участник


08/04/08
8556
angor6 в сообщении #1184026 писал(а):
Правильно, ли я понимаю, что для выполнения упражнения нужно показать, что утверждение, записанное под чертой, является следствием утверждения, записанного над чертой
Да

angor6 в сообщении #1184026 писал(а):
и это можно сделать, например, если заметить, что оба утверждения эквивалентны, и воспользоваться правилом удаления эквиваленции $\frac{P \leftrightarrow Q}{P \to Q}$?
Можно и так. В метатеории можно доказывать утверждения естественным образом.

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 18:30 
Заслуженный участник


27/04/09
28128
Вообще вы можете просто эквивалентными преобразованиями привести $A\to\neg B$ к $B\to\neg A$, а когда формулы эквивалентны, каждая из них — логическое следствие другой. Или вы можете построить таблицы истинности и показать логическое следствие в лоб.

angor6 в сообщении #1184026 писал(а):
например, если заметить, что оба утверждения эквивалентны, и воспользоваться правилом удаления эквиваленции $\frac{P \leftrightarrow Q}{P \to Q}$
Главное не путать эквивалентность и логическое следствие метатеориии с $\leftrightarrow$ и $\to$ теории.

-- Чт янв 12, 2017 20:36:58 --

Вообще, чтобы в будущем не возникла путаница, $\frac{F_1,\ldots,F_n}G$ обычно не является синонимом $F_1,\ldots,F_n\vDash G$ как в этой книге, а обозначает правило вывода или выводимость по какому-то правилу вывода; и хотя от правил вывода и требуют $(\vDash F_1)\mathbin\&\ldots\mathbin\&(\vDash F_n)\Rightarrow(\vDash G)$ для любых $F_1,\ldots,F_n,G$, соответствующих структуре правила ($\mathbin\&,\Rightarrow$ — конъюнкция и импликация из метатеории), но это всё же не то же самое что $F_1,\ldots,F_n\vDash G$.

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 19:24 
Аватара пользователя


11/03/12
586
Беларусь, Минск
Sonic86
arseniiv
Благодарю Вас за ответы! Я рад, что правильно выполнил упражнение, с которым встретился впервые. К сожалению, что такое метатеория, я не знаю. Надеюсь, что на данном этапе самообразования для меня это несущественно. Досадно, конечно, что используемый мной учебник, исходя из сообщения уважаемого arseniiv, неточен. Придётся смириться и с этим...

Я предполагаю, что упражнение можно было бы выполнить так. Предположим, что истинными являются формулы $ A\to\neg B $ и $ B. $ Если формула $ A $ истинна, то из первой посылки имеем истинную формулу $ \neg B $, что противоречит истинности формулы $ B $. Значит, формула $ A $ ложна, и истинна формула $ \neg A $ и с ней формула $ B\to\neg A. $ Это правильно?

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 19:44 
Заслуженный участник


27/04/09
28128
angor6 в сообщении #1184078 писал(а):
К сожалению, что такое метатеория, я не знаю.
Это та теория, в которой сейчас определяются понятия формулы, логического следования и прочего, в данном случае неформальная теория, утверждения которой в основном записываются словами. Главное тут то, что это не та же самая теория, которую мы рассматриваем, иначе, в принципе, можно прийти к парадоксам с самоссылающимися высказываниями и подобному (хотя мы можем строить и рассматривать теории с самоссылающимися высказываниями специально — но это далеко от целей рассматриваемой книги).

angor6 в сообщении #1184078 писал(а):
Досадно, конечно, что используемый мной учебник, исходя из сообщения уважаемого arseniiv, неточен.
Нет, почему неточен — просто автор решил немного посокращать углы. Я удивлён, что он вообще стал говорить о формулах, если книга про алгебру и теорию чисел, а не матлогику.

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 19:55 


03/06/12
2742
arseniiv в сообщении #1184050 писал(а):
Вообще, чтобы в будущем не возникла путаница, $\frac{F_1,\ldots,F_n}G$ обычно не является синонимом $F_1,\ldots,F_n\vDash G$

Вы имеете ввиду, что в той книги определение
arseniiv в сообщении #1184050 писал(а):
, $\frac{F_1,\ldots,F_n}G$

как и
arseniiv в сообщении #1184050 писал(а):
$F_1,\ldots,F_n\vDash G$

такое
Изображение
да?

(Оффтоп)

Не сочтите за занудство, просто расставляю все точки над и.


-- 12.01.2017, 21:03 --

angor6 в сообщении #1184026 писал(а):
В учебнике "Алгебра и теория чисел", написанном Л. Я. Куликовым

Вообще, честно говоря, такие книги для
angor6 в сообщении #1184078 писал(а):
самообразования

мало что дают: ну решу я задачу, а толку-то: ответов нет, правильно-неправильно решил, бо-о-льшой вопрос.

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 20:05 
Заслуженный участник


27/04/09
28128
Да. См. низ стр. 18 и верх стр. 19 (если у нас одинаковые издания, я что-то не посмотрел и не сохранял и уже закрыл).

angor6 в сообщении #1184078 писал(а):
Я предполагаю, что упражнение можно было бы выполнить так. Предположим, что истинными являются формулы $ A\to\neg B $ и $ B. $ Если формула $ A $ истинна, то из первой посылки имеем истинную формулу $ \neg B $, что противоречит истинности формулы $ B $. Значит, формула $ A $ ложна, и истинна формула $ \neg A $ и с ней формула $ B\to\neg A. $ Это правильно?
Практически. (Т. е. кто-то сочтёт это достаточным, хотя, по-моему, это слишком кратко, и если вдруг есть путаница импликаций и следствия, установить это по данному тексту будет нельзя.)

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 20:15 


03/06/12
2742
arseniiv в сообщении #1184099 писал(а):
Да. См. низ стр. 18 и верх стр. 19.

А у меня низ стр. 14 и верх стр. 15. (по нумерации на страницах книги).

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 20:18 
Аватара пользователя


11/03/12
586
Беларусь, Минск
arseniiv
arseniiv в сообщении #1184099 писал(а):
angor6 в сообщении #1184078 писал(а):
Я предполагаю, что упражнение можно было бы выполнить так. Предположим, что истинными являются формулы $ A\to\neg B $ и $ B. $ Если формула $ A $ истинна, то из первой посылки имеем истинную формулу $ \neg B $, что противоречит истинности формулы $ B $. Значит, формула $ A $ ложна, и истинна формула $ \neg A $ и с ней формула $ B\to\neg A. $ Это правильно?
Практически. (Т. е. кто-то сочтёт это достаточным, хотя, по-моему, это слишком кратко, и если вдруг есть путаница импликаций и следствия, установить это по данному тексту будет нельзя.)

Насколько я понимаю, стрелка, направленная вправо, в контексте используемого мной учебника обозначает импликацию.

-- 12.01.2017, 19:31 --
Sinoid
Sinoid в сообщении #1184096 писал(а):
angor6 в сообщении #1184026 писал(а):
В учебнике "Алгебра и теория чисел", написанном Л. Я. Куликовым

Вообще, честно говоря, такие книги для
angor6 в сообщении #1184078 писал(а):
самообразования

мало что дают: ну решу я задачу, а толку-то: ответов нет, правильно-неправильно решил, бо-о-льшой вопрос.

Согласен с Вами. Поэтому вместе с этим учебником я использую ещё и задачник, составленный Л. Я. Куликовым, А. И. Москаленко, А. А. Фоминым. В нём к большей части заданий есть ответы и указания. Кроме того, рассчитываю выяснять интересующие меня вопросы на этом форуме. Учебник же я выбрал, прельстившись возможностью изучить несколько разделов математики на сносном хотя бы для школьных учителей математики уровне по одному источнику.

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 21:04 


03/06/12
2742
Кстати, про
arseniiv в сообщении #1184050 писал(а):
выводимость

Вот когда в метатеории пишут
arseniiv в сообщении #1184050 писал(а):
$F_1,\ldots,F_n\vDash G$

при этом имеют ввиду истинность этой самой выводимости, верно? Так что получается, понятие истинности/ложности присутствует и в метаматематике. Верно?

(Оффтоп)

Извините за перехват темы, сейчас закончу.

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 21:16 
Заслуженный участник


27/04/09
28128

(Оффтоп)

angor6 в сообщении #1184108 писал(а):
Насколько я понимаю, стрелка, направленная вправо, в контексте используемого мной учебника обозначает импликацию.
Всё правильно понимаете, хотя я говорил немного не о том, хотя это не важно.

Sinoid в сообщении #1184130 с небольшими изменениями писал(а):
Вот когда в метатеории пишут $F_1,\ldots,F_n\vDash G$, при этом имеют ввиду истинность этой самой выводимости, верно?
Это не выводимость, выводимость обозначается $\vdash$. А это же логическое следствие.

Sinoid в сообщении #1184130 писал(а):
Так что получается, понятие истинности/ложности присутствует и в метаматематике. Верно?
Я не чувствую, что понимаю, что́ стоит отвечать на такой вопрос, если метатеория не формализована. Если формализована в какой-то метаметатеории, то ответ будет дан тем, как именно. Может, это просто система вывода, и об интерпретациях формул, а потому и истинности, ничего не говорится.

 Профиль  
                  
 
 Re: Обоснование схемы доказательства
Сообщение12.01.2017, 21:44 
Аватара пользователя


11/03/12
586
Беларусь, Минск
arseniiv

(Оффтоп)

Я надеюсь, что разницу между импликацией и следствием понимаю.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 12 ] 

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



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

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


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

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