НГУ

Форумы НГУ
Текущее время: Чт фев 21, 2019 2:18 am

Часовой пояс: UTC + 7 часов




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
 Заголовок сообщения: Глупый вопрос по логике
СообщениеДобавлено: Вт окт 23, 2007 8:07 pm 
Не в сети
Частый гость

Зарегистрирован: Ср янв 17, 2007 6:53 pm
Сообщения: 61
Вопрос таков:
Как доказывать полноту/неполноту теории?
В самых несложных случаях.."для студентов". Заумные методы с кучей непонятных слов, пожалуйста, не излагаqnt


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт окт 23, 2007 9:46 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
Сходить на семинар по матлогике и послушать, что скажет преподаватель. Самый действенный метод!!!

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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 24, 2007 2:43 am 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт сен 07, 2001 7:00 am
Сообщения: 2844
Откуда: Станислав Березнюк
Фигня а не оперативность :) Оперативность была бы, если бы народ с 6132 тему завёл (тоже с полными/неполными теориями разбирались): у них семинар не "днём", а "ближе к вечеру" ;-)

_________________
Мордор жил, Мордор жив, Мордор будет жить!


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Глупый вопрос по логике
СообщениеДобавлено: Ср окт 24, 2007 5:27 pm 
Не в сети
Опытный автор

Зарегистрирован: Сб окт 14, 2006 1:00 am
Сообщения: 628
Откуда: Максим
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$.
Значит, Е неполна.

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения: Re: Глупый вопрос по логике
СообщениеДобавлено: Ср окт 24, 2007 5:35 pm 
Не в сети
Непрерывный писатель

Зарегистрирован: Пт июн 18, 2004 10:34 pm
Сообщения: 4435
Откуда: Сергей Подзоров
MaxVT писал(а):
Очень жаль, что наши замечательные преподаватели только мораль почитали и посмеялись, а ведь мало ли какие ситуации бывают у студентов. От того, что кто-то прочитает на форуме, как решается задача, хуже ему не станет, и ни от кого не убудет.


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

_________________
Don't let the sun blast your shadow
Don't let the milk float ride your mind


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 24, 2007 5:58 pm 
Не в сети
Частый гость

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 24, 2007 6:26 pm 
Не в сети
Весьма плодовитый автор

Зарегистрирован: Чт сен 27, 2001 7:00 am
Сообщения: 1637
orlang писал(а):
Как доказывать полноту/неполноту теории?

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

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

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

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


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Ср окт 24, 2007 7:15 pm 
Не в сети
Частый гость

Зарегистрирован: Ср янв 17, 2007 6:53 pm
Сообщения: 61
Спасибо.
Остается применить))


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс окт 28, 2007 5:49 pm 
Не в сети
Начинающий автор

Зарегистрирован: Вс июн 18, 2006 4:39 pm
Сообщения: 285
slb писал(а):
Фигня а не оперативность :) Оперативность была бы, если бы народ с 6132 тему завёл (тоже с полными/неполными теориями разбирались): у них семинар не "днём", а "ближе к вечеру" ;-)

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


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

Часовой пояс: UTC + 7 часов


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

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


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

Найти:
Перейти:  
Создано на основе phpBB® Forum Software © phpBB Group
Русская поддержка phpBB