НГУ
http://forum.nsu.ru/

Глупый вопрос по логике
http://forum.nsu.ru/viewtopic.php?f=24&t=17778
Страница 1 из 1

Автор:  orlang [ Вт окт 23, 2007 8:07 pm ]
Заголовок сообщения:  Глупый вопрос по логике

Вопрос таков:
Как доказывать полноту/неполноту теории?
В самых несложных случаях.."для студентов". Заумные методы с кучей непонятных слов, пожалуйста, не излагаqnt

Автор:  Коба [ Вт окт 23, 2007 9:46 pm ]
Заголовок сообщения: 

Сходить на семинар по матлогике и послушать, что скажет преподаватель. Самый действенный метод!!!

P. S. Днём дал на семинаре домашнее задание, в котором требуется доказать полноту теории, а вечером тут уже ветку завели. Какова оперативность, однако! :)

Автор:  slb [ Ср окт 24, 2007 2:43 am ]
Заголовок сообщения: 

Фигня а не оперативность :) Оперативность была бы, если бы народ с 6132 тему завёл (тоже с полными/неполными теориями разбирались): у них семинар не "днём", а "ближе к вечеру" ;-)

Автор:  MaxVT [ Ср окт 24, 2007 5:27 pm ]
Заголовок сообщения:  Re: Глупый вопрос по логике

orlang писал(а):
Вопрос таков:
Как доказывать полноту/неполноту теории?
В самых несложных случаях.."для студентов". Заумные методы с кучей непонятных слов, пожалуйста, не излагаqnt

Надо начинать с определения:
теория T полна в сигнатуре $\sigma$, если для любого предложения Ф сигнатуры $\sigma$ выполняется: $Ф\in T$ или $\neg Ф\in T$, то есть либо само предложение выводимо из аксиом теории Т, либо выводимо его отрицание.

Например, пусть мы хотим доказать неполноту какой-то теории. Тогда нам надо найти какое-то предложение той же сигнатуры такое, что ни само предложение, ни его отрицание невыводимы из аксиом теории Т. Так как нам проще работать с семантикой, то воспользуемся теоремой о полноте, и тогда нам необходимо будет найти такое предложение, что ни оно, ни его отрицание не являются тождественно истинными.

Пример. Докажем, что теория равенства Е (аксиомы смотреть в Лавров, Максимова, часть 2, параграф 7) неполна в сигнатуре с одним символом "=".
Решение. Пусть А -- модель теории Е. Возьмем предложение $Ф=\forall x\forall y(x=y)$.
Если носитель модели А неодноэлементен, то ясно, что формула Ф не будет тождественно истинной. Итак, Ф\not\in E.
Теперь рассмотри отрицание Ф -- это будет $\neg Ф=\exists x\exists y(\neg(x=y))$. Если носитель модели А одноэлементен, то уже $\neg Ф$ не будет тождественно истинным. Итак, $\neg Ф\not\in E$.
Значит, Е неполна.

Если я где ошибся, просьба меня поправить.
Очень жаль, что наши замечательные преподаватели только мораль почитали и посмеялись, а ведь мало ли какие ситуации бывают у студентов. От того, что кто-то прочитает на форуме, как решается задача, хуже ему не станет, и ни от кого не убудет.

Автор:  Коба [ Ср окт 24, 2007 5:35 pm ]
Заголовок сообщения:  Re: Глупый вопрос по логике

MaxVT писал(а):
Очень жаль, что наши замечательные преподаватели только мораль почитали и посмеялись, а ведь мало ли какие ситуации бывают у студентов. От того, что кто-то прочитает на форуме, как решается задача, хуже ему не станет, и ни от кого не убудет.


Угу, мало ли какие. Например, пропустил семинар, а на следующем домашку спросят, которую не знаешь, как решать :)

Автор:  orlang [ Ср окт 24, 2007 5:58 pm ]
Заголовок сообщения: 

Во-первых:
Кто сказал, что я с группы 6133(или хотя бы 6132)?
Поэтому, Коба может вообще свои умозаключения, достойные обычного выпендрежа, оставить где-нибудь в другом месте.
P.S.(для считающего себя очень умным преподавателя) я ни одной пары пока не пропустил.
Во-вторых:
Я попросил помочь. Если вам нечего сказать по вопросу или вам просто не хочется, не надо писать "лишь бы написать". Последнее как раз,по-моему, имело место и не очень соответствует культуре поведения университета.
В-третьих, что плохого в том, что не получив конструктивного ответа пока ни на семинаре, ни на лекции, я решил помочь разобраться?
Я, кажется, конкретную домашку решать не просил.

В-четвертых, спасибо Максиму))

Автор:  Pavel E. Alaev [ Ср окт 24, 2007 6:26 pm ]
Заголовок сообщения: 

orlang писал(а):
Как доказывать полноту/неполноту теории?

Обычно неполнота доказывается прямо по определению, как уже писал MaxVT - указывается предложение, которое ни само не лежит в теории, ни его отрицание. Проверка делается через теорему о полноте ИП.

Полнота часто оказывается сложной проблемой, тут есть только разные достаточные признаки. Один из самых простых: если язык (сигнатура) счётен, k - некоторая бесконечная мощность, у теории нет конечных моделей и всё её модели мощности k изоморфны, то теория полна.

К нему можно прибавить простой случай теорий конечных моделей: если n - натуральное число, любая модель теории имеет мощность n и все модели теории изоморфны, то теория полна.

Есть много других методов доказательства полноты, но они обычно довольно громоздки.

Автор:  orlang [ Ср окт 24, 2007 7:15 pm ]
Заголовок сообщения: 

Спасибо.
Остается применить))

Автор:  sxe [ Вс окт 28, 2007 5:49 pm ]
Заголовок сообщения: 

slb писал(а):
Фигня а не оперативность :) Оперативность была бы, если бы народ с 6132 тему завёл (тоже с полными/неполными теориями разбирались): у них семинар не "днём", а "ближе к вечеру" ;-)

А вот если бы завели на семинаре! Вот это была бы оперативность!

Страница 1 из 1 Часовой пояс: UTC + 7 часов
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/