НГУ

Форумы НГУ
Текущее время: Пн авг 26, 2019 9:43 am

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




Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.
Автор Сообщение
СообщениеДобавлено: Пт май 09, 2008 4:25 pm 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
Пытаюсь придумать пример полной и одновременно непротиворечивой теории.

Алфавит состоит из символов A={X,’,-->,(,)}
( ‘ – означает «Не»)
1.Формулы определяются следующим образом:
А) Если X переменная, то X-->X – есть формула системы.
Б) если F – формула, то (F)’ – так же формула
В) если F – формула, то (F-->F) – так же формула
Г)Ни каких формул кроме получаемых по пунктам а-в нет.

Вот примеры формул нашей системы:
1.(X-->X)
2.(X-->X)’
3.((X-->X )-->( X-->X))
4. ((X-->X )-->( X-->X))’
5.((X’-->X’ )-->( X’-->X’))
6. ((X’-->X’ )-->( X’-->X’))’
7.((X-->X )’-->( X-->X)’)’
8. ((X-->X )’-->( X-->X)’)’’
9. ((((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)) )’-->( ((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)))’)’
10. ((((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)) )’-->( ((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)))’)’’
3. Аксиомы.
Имеется три схемы аксиом:
А)(F-->(G-->F))
Б) (F-->(G-->H)) -->((F-->G) -->(F-->H))
В)((G’-->F’) -->((G’-->F) -->G))
Где F,G,H – произвольные формулы нашей системы.
4.Имеется одно правило вывода – MP.
Т.е. если F и F-->G - формулы то G – так же формула.
Всё, описание системы закончено. Эта формальная аксиоматическая система будет одновременно полна и непротиворечива. Что бы в этом убедится, нужно заметить,что все теоремы нашей системы – есть тавтологии алгебры высказываний. В соответствии с теоремой о полноте формализованного исчисления высказываний, мы будем иметь, что каждая тавтология алгебры высказываний будет выводима в нашей системе. Но в нашей системе присутствуют либо тождественно истинные, либо тождественно ложные формулы. Причём если F – тождественно ложна, то F’ – тождественно истинна. Значит хотя бы одна из формул F или F’ – будет выводится в нашей системе то есть система будет полна. А поскольку, если F – тавтология, то F’ – тождественно ложная формула, а в нашей системе теоремами являются только тавтологии, то следовательно одна из них не выводима, что означает непротиворечивость.

Верно ли я рассуждал? Так же меня интересует вопрос: когда я определял формулы этой теории, я искуственно запретил существовуание в ней формул X и X', то есть объявил что сама переменная и её отрицание формулой не является. Я не пойму - так можно делать или нельзя? Запрет на то, что переменная яляется формулой связан с тем, что она не является тавтологией, и следовательно ни она сама ни её отрицание невыводимы в нашей системе.

P.S.
В теореме Гёделя о неполноте, речь идет не о том, что все формальные системы либо неполны либо противоречивы, а лишь об определённом классе систем. Но я не разу не встречал примера полной и одновременно непротиворечивой теории. Не могли бы вы такой пример привести? Тот пример, когда речь идёт о формализованном исчислении высказываний и предикатов - не годится. Ведь там, как я понимаю, речь идёт о другом виде полноты -
о полноте по отношения к алгебре высказываний и исчислению предикатов соответственно.

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Сб май 10, 2008 12:17 am 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Заранее извиняюсь: времени очень мало, так что отвечаю схематично.

Если коротко, то весь предыдущий пост -- увы, сплошное недоразумение. А если чуть подлиннее, то...

Amigo писал(а):
Пытаюсь придумать пример полной и одновременно непротиворечивой теории.

Пример есть в третьем посте Вашей "родной" темы "Теорема Гёделя о неполноте".

Цитата:
Алфавит состоит из символов A={X,’,-->,(,)}
( ‘ – означает «Не»)
1.Формулы определяются следующим образом:
А) Если X переменная, то X-->X – есть формула системы.

Что значит "Если X переменная, то..."? А что если X -- не переменная? :-) У Вас же в алфавите всего одна буква -- X. А если не одна, то алфавит Вы указали не тот, что имеете в виду. Впрочем, это мелочь.

Цитата:
Вот примеры формул нашей системы:
5.((X’-->X’ )-->( X’-->X’))
6. ((X’-->X’ )-->( X’-->X’))’
9. ((((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)) )’-->( ((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)))’)’
10. ((((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)) )’-->( ((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)))’)’’

Это не формулы: сочетание X' Вы запретили.

Кроме того, наблюдается явный перемудреж. (Или недомудреж -- тут уж как поглядеть.) Элементарной формулой Вы зачем-то сделали длинную строку X-->X, хотя могли бы просто заменить ее одной буквой X. Что от этого изменится-то? Ровным счетом ничего. Имеется элементарный "изоморфизм".

Цитата:
4.Имеется одно правило вывода – MP.
Т.е. если F и F-->G - формулы то G – так же формула.

Надеюсь, это -- просто смешная опечатка, и Вы на самом деле понимаете, что правила вывода вовсе не предназначены для того, чтобы уточнять понятие формулы. Что такое формула, мы уже знаем и без правил вывода.

Цитата:
все теоремы нашей системы – есть тавтологии алгебры высказываний.

Вроде. да. (Я не успел вникнуть в Ваши аксиомы, но они действительно похожи на тавтологии.)

Цитата:
В соответствии с теоремой о полноте формализованного исчисления высказываний, мы будем иметь, что каждая тавтология алгебры высказываний будет выводима в нашей системе.

А это-то с какой стати?

Цитата:
система будет полна

Я бы хотел взглянуть на вывод формулы (X->X) или ее отрицания (X->X)'. (И не забывайте, что X -- это (по Вашему же определению) не формула!) :-)

Цитата:
я искуственно запретил существовуание в ней формул X и X', то есть объявил что сама переменная и её отрицание формулой не является. Я не пойму - так можно делать или нельзя?

Делайте что угодно, только не попадайтесь в собственные искусственные ловушки. :-)

Цитата:
В теореме Гёделя о неполноте, речь идет не о том, что все формальные системы либо неполны либо противоречивы, а лишь об определённом классе систем.

Очень рекомендую вернуться к нашему родному языку предикатов. (Ибо Теорема Гёделя -- о нем.)

Цитата:
Но я не разу не встречал примера полной и одновременно непротиворечивой теории.

Вы его просто не заметили. :-)

Цитата:
Тот пример, когда речь идёт о формализованном исчислении высказываний и предикатов - не годится. Ведь там, как я понимаю, речь идёт о другом виде полноты -
о полноте по отношения к алгебре высказываний и исчислению предикатов соответственно.

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

Итого: ой. :-)

Я искренне уважаю Ваше стремление разобраться во всей этой кухне, но Вы настолько далеки от цели, что я даже не представляю, каким боком Вас к ней подтолкнуть. :-)

P.S. Надо бы Вам живьем хорошенько побеседовать с кем-нибудь, кто уже успел все это просечь. Приезжайте к нам в гости, что ли? :-)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Сб май 10, 2008 2:46 am 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
AGu писал(а):

Цитата:
Алфавит состоит из символов A={X,’,-->,(,)}
( ‘ – означает "Не")
1.Формулы определяются следующим образом:
А) Если X переменная, то X-->X – есть формула системы.

Что значит "Если X переменная, то..."? А что если X -- не переменная? :-) У Вас же в алфавите всего одна буква -- X. А если не одна, то алфавит Вы указали не тот, что имеете в виду. Впрочем, это мелочь.

Да, глупо, согласен. Я просто не нашёл лучше способа выразиться.
Для моих целей было необходимо, что бы переменная X формулой не была. Впрочем это не помогло, как Вы потом показали.
AGu писал(а):
Цитата:
Вот примеры формул нашей системы:
5.((X’-->X’ )-->( X’-->X’))
6. ((X’-->X’ )-->( X’-->X’))’
9. ((((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)) )’-->( ((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)))’)’
10. ((((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)) )’-->( ((X’-->X’ )-->( X’-->X’))-->((X’-->X’ )-->( X’-->X’)))’)’’

Это не формулы: сочетание X' Вы запретили.

Точно, опять "прощёлкал".
AGu писал(а):
Кроме того, наблюдается явный перемудреж. (Или недомудреж -- тут уж как поглядеть.) Элементарной формулой Вы зачем-то сделали длинную строку X-->X, хотя могли бы просто заменить ее одной буквой X. Что от этого изменится-то? Ровным счетом ничего. Имеется элементарный "изоморфизм".

Изоморфизма я не вижу пока, а сделал я это для следующего:
если отдельно взятую переменную Х – объявить формулой, то столкнемся с тем фактом, что ни эта формула ни её отрицание не будет выводима в нашей системе. Это следует из того, что формула Х – опровержима, вместе с тем, в нашей системе выводимы те и только те формулы, которые являются тавтологиями. Поэтому, я хотел начать стартовать не с формулы Х а с Х-->Х, которая тавтология и потому выводима, т.е. является теоремой. Вот вывод этой формулы:
1.(F-->((F-->F)-->F)) -->((F-->(F-->F)) -->(F-->F))
2.F-->((F-->F) -->F)
3.(F-->(F-->F))-->(F-->F)
4.F-->(F-->F)
5.F-->F
Здесь: строчка (1) представляет собой аксиому Б), в которой в качестве формул F и H взята формула F, а в качестве формулы G взята формула F-->F. Строчка (2) представляет собой аксиому А),
в которой в качестве формулы G берётся формула F-->F. Строчка (3) получена из строчек (1) и (2) по правилу MP. Строчка (4) получена из аксиомы А), где в качестве G – взята F. Наконец, строчка (5) получена из строчек (3) и (4) по правилу MP.

Правда этот вывод действителен, только если мы в аксиомы можем подставлять не только то, что я объявил формулами, но ещё и переменную Х. Я не очень понял этом момент с переменными и формулами т.е. можно ли поступать так, что мы объявили конструкции переменных формулами, а сами переменные нет, но затем дали себе право подставлять в аксиомы не только формулы но и переменные?


AGu писал(а):
Цитата:
4.Имеется одно правило вывода – MP.
Т.е. если F и F-->G - формулы то G – так же формула.

Надеюсь, это -- просто смешная опечатка, и Вы на самом деле понимаете, что правила вывода вовсе не предназначены для того, чтобы уточнять понятие формулы. Что такое формула, мы уже знаем и без правил вывода.

Когда я писал этот текст, то над этим вопросом задумался специально. Дело в том, что в учебнике по которому я занимаюсь,
стоит слово "формула". Хотя из других учебников, мне известно, что обычно в этом месте должно стоять слово "теорема". Но мало ли… вдруг, думаю, я чего то не понял, напишу на всякий случай как в учебнике, если что поправят. :-)
AGu писал(а):
Цитата:
В соответствии с теоремой о полноте формализованного исчисления высказываний, мы будем иметь, что каждая тавтология алгебры высказываний будет выводима в нашей системе.

А это-то с какой стати?

А это не я :-), это автор так утверждает. Я занимаюсь по книге В.И. Игошина "Математическая логика и теория алгоритмов". На самом деле я эти аксиомы "слизал" у него. Он там проводит доказательство этого факта на нескольких страницах, опираясь на свойства так называемых "q-двойников". Я бы сообщил Вам подробней суть доказательства. Но дело в том, что когда я слышу
выражение "q-двойник" – то немедленно переворачиваю страницу.
В надежде вернуться к ней, в последующие, более спокойные времена…
AGu писал(а):
Цитата:
В теореме Гёделя о неполноте, речь идет не о том, что все формальные системы либо неполны либо противоречивы, а лишь об определённом классе систем.

Очень рекомендую вернуться к нашему родному языку предикатов. (Ибо Теорема Гёделя -- о нем.)

Конечно! сейчас разберусь с этим кругом вопросов, и сразу к исчислению предикатов!

AGu писал(а):
Цитата:
Тот пример, когда речь идёт о формализованном исчислении высказываний и предикатов - не годится. Ведь там, как я понимаю, речь идёт о другом виде полноты -
о полноте по отношения к алгебре высказываний и исчислению предикатов соответственно.

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

Погодите, разве теория предикатов полна в том смысле, что для всякой формулы сформулированной в этой теории, либо она сама либо её отрицание выводимы? Вот в формализованном исчислении высказываний, формула Х и Х’– не выводима. Следовательно ФИВ – не есть полная теория. Причём, я пытался пополнить её при помощи дополнительных аксиом, но всякий раз приходил к тому, что ФИВ становилось противоречивым. Хотя, возможно, я плохо пополнял. Но ведь, наша совокупность аксиом в ФИВ такова, что она порождает множество тавтологий, и следовательно, присоеденение к этой совокупности ещё одной тавтологии – не сможет пополнить совокупность теорем системы. Добавление же, тождественно ложной формулы- аксиомы, не есть гуд, поскольку, если F-тождественно ложна, то F’ – тождественно истинна, следовательно, выводима в нашей системе, и система становится противоречивой. Если же мы к схеме аксиом добавим опровержимую формулу F, то вместе с ней… дальше я не могу додуматься, но все мои попытки поступить таким образом, были обречены.- Всегда мне удавалось вывести какую-нибудь формулу G и одновременно G’.
AGu писал(а):
P.S. Надо бы Вам живьем хорошенько побеседовать с кем-нибудь, кто уже успел все это просечь.

Да, было бы не плохо, но… к сожалению, специалист в области логики, весьма редкостная разновидность интеллигента, и в наших краях это видимо вымерший вид. У меня много друзей, которые учатся на матфаке (я там то же учился некоторое время), никто из них в этих вопросах не сечёт вообще. Они говорят, что такие вещи как формальные аксиоматические системы, даются им в курсе логики, лишь как упоминание, что, дескать, да, знайте, такие есть. И поверьте, тот бред, который тут несу я, еще цветочки…
AGu писал(а):
Приезжайте к нам в гости, что ли?

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

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Сб май 10, 2008 4:32 am 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
Кажется я допёр почему, в случае добавления к нашей системе аксиом опровержимой формулы она становится противоречивой.
Причины тому следующие:
Пусть F - опровержимая формула добавленная в качестве аксиомы в нашу систему. Согласно аксиоме (А) будем иметь, что (F-->(G-->F))
так же аксиома. По правилу МР получим, что (G-->F) - теорема нашей системы. Пусть G-тавтология. Потставим формулу G в аксиому (А) вместо F, на место G - подставим F. Получим аксиому:(G-->(F-->G)).
По правилу МР - из формул G и (G-->(F-->G)), получаем теорему
(F-->G). Таким образом имеем две теоремы:
1.(F-->G)
2.(G-->F)
или (G<-->F), но G- тавтология, а F - опровержима, пришли к противоречию. То есть из предположения, что добавив к нашей системе опровержимую формулу алгебры высказываний, мы приходим к тому, что она является тавтологией т.е. не может быть равна лжи при любых значениях переменных. Значит наше предположение о том, что мы можем получить формулу Х или Х' - при помощи добавления к системе опровержимой формулы - не верно. А поскольку мы рассмотрели все случаи пополнения нашей системы, то следовательно, наша система неполна и непополнима. При этом, Формулой, которая в ней не выводится т.е. ни она сама ни её отрицание не являются теоремами нашей системы является формула Х.

Если моё рассуждение верно, то я хотел бы понять, как именно я его получил. Я ведь его получил "рассуждая в общем", а не внутри системы. То есть я не смог доказать, что если формула F-опровержима,
то это влечёт за собой противоречивость системы.

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


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

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Amigo писал(а):
AGu писал(а):
Кроме того, наблюдается явный перемудреж. (Или недомудреж -- тут уж как поглядеть.) Элементарной формулой Вы зачем-то сделали длинную строку X-->X, хотя могли бы просто заменить ее одной буквой X. Что от этого изменится-то? Ровным счетом ничего. Имеется элементарный "изоморфизм".
Изоморфизма я не вижу пока
Ну как же? Если в Вашем посте все вхождения (X-->X) заменить на X, то все Ваши верные изречения останутся верными, а неверные -- неверными. Вот вам и "изоморфизм". :-)
Amigo писал(а):
в нашей системе выводимы те и только те формулы, которые являются тавтологиями.
Не понимаю, на каком основании Вы делаете это заключение. Да, все формулы, выводимые в Вашем исчислении (назовем его ИВА), являются тавтологиями и тем самым выводимы в классическом исчислении высказываний (ИВ). Но почему любая тавтология выводима в ИВА? Вы ведь модифицировали ИВ и в результате существенно уменьшили совокупность выводимых формул. Например, как я уже намекал, формула (X-->X) не выводима в ИВА.
Amigo писал(а):
я хотел начать стартовать не с формулы Х а с Х-->Х, которая тавтология и потому выводима
В каком исчислении? В ИВ -- да. Но не в ИВА.
Amigo писал(а):
Вот вывод этой формулы:
1.(F-->((F-->F)-->F)) -->((F-->(F-->F)) -->(F-->F))
2.F-->((F-->F) -->F)
3.(F-->(F-->F))-->(F-->F)
4.F-->(F-->F)
5.F-->F
Ну и что? Вы построили вывод (F-->F), где F -- формула. А у Вас X -- это не формула (я ведь предостерегал).
Amigo писал(а):
Правда этот вывод действителен, только если мы в аксиомы можем подставлять не только то, что я объявил формулами, но ещё и переменную Х.
Во-во.
Amigo писал(а):
Я не очень понял этом момент с переменными и формулами т.е. можно ли поступать так, что мы объявили конструкции переменных формулами, а сами переменные нет, но затем дали себе право подставлять в аксиомы не только формулы но и переменные?
Странный вопрос. Разве не очевидно, что такой подход недопустим? Все определения должны быть предельно четкими, включая определения таких понятий, как формула и аксиома.
Amigo писал(а):
AGu писал(а):
Цитата:
В соответствии с теоремой о полноте формализованного исчисления высказываний, мы будем иметь, что каждая тавтология алгебры высказываний будет выводима в нашей системе.
А это-то с какой стати?
А это не я :-), это автор так утверждает.
Автор наверняка имел в виду ИВ, а не ИВА. :-)
Amigo писал(а):
Погодите, разве теория предикатов полна в том смысле, что для всякой формулы сформулированной в этой теории, либо она сама либо её отрицание выводимы?
Я здесь имел в виду другую полноту (все тавтологии выводимы). Значит, я и впрямь неправильно Вас понял. Это радует. :-)
Amigo писал(а):
Кажется я допёр почему, в случае добавления к нашей системе аксиом опровержимой формулы она становится противоречивой.
Вы все еще настаиваете на Вашей "нашей системе"? Мы же, вроде, с ней уже разобрались, она неполна во всех смыслах. По-моему, уже давно пора переходить к предикатам. :-)
Amigo писал(а):
Пусть F - опровержимая формула добавленная в качестве аксиомы в нашу систему. Согласно аксиоме (А) будем иметь, что (F-->(G-->F))
так же аксиома. По правилу МР получим, что (G-->F) - теорема нашей системы. Пусть G-тавтология.
Повторяю, G не обязана выводиться в ИВА.
Amigo писал(а):
Потставим формулу G в аксиому (А) вместо F, на место G - подставим F. Получим аксиому:(G-->(F-->G)).
По правилу МР - из формул G и (G-->(F-->G)),
Здесь Вы предполагаете, что G выводима в ИВА. Ну ладно, пусть G -- тавтология, выводимая в ИВА.
Amigo писал(а):
получаем теорему
(F-->G). Таким образом имеем две теоремы:
1.(F-->G)
2.(G-->F)
или (G<-->F), но G- тавтология, а F - опровержима, пришли к противоречию.
Простите, к противоречию -- с чем? Вы показали, что формула (G<-->F) выводима в ИВА+F. Никакого противоречия я здесь не вижу.
Amigo писал(а):
То есть из предположения, что добавив к нашей системе опровержимую формулу алгебры высказываний, мы приходим к тому, что она является тавтологией
Удивительное заключение. Откуда оно взялось? Неужели Вы и впрямь считаете, что заменив ИВА на ИВА+F, Вы тем самым не испортили совокупность выводимых формул, и они все остались тавтологиями? Кстати, F тоже выводима в ИВА+F (с очень коротким доказательством :-)). Неужто тогда и F -- тоже тавтология? Этак Вы заключите, что любая формула является тавтологией.
Amigo писал(а):
мы приходим к тому, что она является тавтологией т.е. не может быть равна лжи при любых значениях переменных.
Вообще-то, "т.е." -- значит "что то же самое"? Тогда Вы либо забыли определение понятия тавтологии, либо, что еще хуже, путаетесь в расшифровке отрицания кванторного высказывания.
Amigo писал(а):
Если моё рассуждение верно, то я хотел бы понять, как именно я его получил. Я ведь его получил "рассуждая в общем", а не внутри системы.
"К счастью", по дороге Вы успели наделать столько ошибок, что понимать уже нечего. :-)


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вс май 11, 2008 12:15 am 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Как уже отмечалось, теорема Гёделя относится к исчислению предикатов (ИП), а не к исчислению высказываний (ИВ). Тем не менее, понятие полноты формально применимо и к таким бескванторным аксиоматическим системам, как ИВ. Это верно уже потому, что язык ИВ является частным случаем языка ИП. А именно, формулы ИВ можно рассматривать как формулы ИП без равенства с сигнатурой, состоящей лишь из нульместных предикатных символов (выступающих в роли пропозициональных переменных).

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

Самый простой из таких примеров -- разумеется, пустой. Т.е. V, A и R -- пустые. Формул нет, аксиом нет, правил вывода нет. Множество выводимых формул, как и множество всех формул, пусто. Система, очевидно, полна и непротиворечива. Извольте откушать, уважаемый заказчик.

Не нравится? Жаль. Мы очень старались. А что именно не нравится? Пустая сигнатура? Нет проблем, минуточку...

Берем любую непустую сигнатуру V, в качестве A берем множество всех формул с четным числом отрицаний, а множество правил вывода R оставляем пустым. Цель достигнута? Очевидно, да. Вкусно, дорогой заказчик?

Как, опять мы не угодили? Что на этот раз? Ах, нужно чтобы R содержало любимое MP? Или даже чтобы R только из MP и состояло?

Для вас -- все, что угодно. Вместо пустого R в предыдущем примере возьмите R={MP}. Как легко видеть, MP не нарушает четность числа отрицаний. (Действительно, если каждая из формул F и F->G имеет четное число отрицаний, то формула G тоже обладает этим приятным свойством.) Следовательно, система остается полной и непротиворечивой, так как в ней по-прежнему выводимы те и только те формулы, которые содержат четное число отрицаний. Приятного аппетита, милый заказчик.

Неужели снова что-то не так? В нашей системе не все тавтологии выводимы? Аксиоматика A не содержит классические аксиомы ИВ?

Ничего не поделаешь, заказчик всегда прав. Берем сигнатуру V={T} (т.е. T будет нашей единственной пропозициональной переменной), в качестве A берем классическую аксиоматику ИВ, расширенную аксиомой T, а в качестве R -- наше незабвенное {MP}. Несложно понять, что в такой (V,A,R) выводимы те и только те формулы, которые истинны при значении T=1. Осталось заметить, что для любой формулы F сигнатуры {T} при значении T=1 истинна ровно одна из формул F, ~F. Любезный заказчик, кушайте на здоровье. А если вам что-то опять не понравится -- ничего страшного, у нас еще очень много рецептов, включая такую экзотику, как фугу в курарном соусе.


Последний раз редактировалось AGu Вс май 11, 2008 4:09 pm, всего редактировалось 1 раз.

Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс май 11, 2008 3:00 am 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
AGu писал(а):
Несложно понять, что в такой (A,V,R) выводимы те и только те формулы, которые истинны при значении T=1. Осталось заметить, что для любой формулы F сигнатуры {T} при значении T=1 истинна ровно одна из формул F, ~F.

Я сегодня весь день думал над чем то подобным, я пополнил аксиматику ИВ ещё одной аксиомой - Х. (алфавит состоял из одной буквы Х). Так вот, размышляя над этой системой, я надеялся найти противоречие, но мне это не удалось. Хотел бы у Вас спросить: если аксиоматику ИВ пополнить аксиомой Х (а алфавит состоит из одной буквы - Х) то будет ли она полной и непротиворечивой?
И ещё, разьясните пожалуйста подробней - почему в (A,V,R) выводимы те и только те формулы, которые истинны при значении T=1. И для любой формулы F сигнатуры {T} при значении T=1 истинна ровно одна из формул F, ~F ?

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс май 11, 2008 3:19 am 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
Да, и ещё один вопрос: В вашем исчислении формулами являются только те комбинации знаков, в которых число отрицаний чётно.
То есть, если T - у Вас формула, то уже Т' - формулой не является.
Как же вы докажите полноту? Для неё же нужно что бы формулы c нечётным количеством знаков отрицания существовали, а в Вашем исчислении их нет.

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс май 11, 2008 2:15 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Amigo писал(а):
разьясните пожалуйста подробней - почему в (A,V,R) выводимы те и только те формулы, которые истинны при значении T=1.
Вот цепочка равносильных утверждений:

ИВ+T |- F
ИВ |- (T -> F)
(T -> F) является тавтологией
для любых значений переменных из истинности T следует истинность F
F истинна при T=1

Amigo писал(а):
И для любой формулы F сигнатуры {T} при значении T=1 истинна ровно одна из формул F, ~F ?
Нетушки, такую тривиальщину я разъяснять не буду -- просто чтобы не унижать Вас. :-)

Amigo писал(а):
Да, и ещё один вопрос: В вашем исчислении формулами являются только те комбинации знаков, в которых число отрицаний чётно.
Речь про второй и третий примеры? Тогда Вы перепутали понятия формулы и аксиомы. Множество формул там классическое, а аксиомами считаются все формулы с четным числом отрицаний.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс май 11, 2008 8:38 pm 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
Всё, я вник в Вашу систему, красивая штука получилась, спасибо за пример. Единственно, как я понимаю, вэтом выводе:
ИВ+T |- F
ИВ |- (T -> F)
-вы опирались на теорему дедукции. Мне трудно понять доказательство этой теоремы (а на веру принимать не приятно), потому, хотел бы попросить Вас, коротко сообщить почему эта формула выводима из ИВ?
Т.е. почему вы считаете, что (T -> F) - есть теорема ИВ?

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


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

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Amigo писал(а):
ИВ+T |- F
ИВ |- (T -> F)
-вы опирались на теорему дедукции. Мне трудно понять доказательство этой теоремы (а на веру принимать не приятно), потому, хотел бы попросить Вас, коротко сообщить почему эта формула выводима из ИВ?
Т.е. почему вы считаете, что (T -> F) - есть теорема ИВ?

Вы будете смеяться, но благодаря полноте ИВ (той самой полноте, которая не та самая :-)) выводимость формулы (T -> F) в ИВ следует из ее тавтологичности. Мне было проще сослаться на дедукцию, но так уж и быть, намекну, как просечь тавтологичность (T->F) прямиком. Итак, почему F истинна при T=1? А потому, что при T=1 истинны все формулы, встречающиеся в выводе формулы F из ИВ+T (который у нас имеется по предположению). Последнее легко показать индукцией по позиции формулы в выводе: аксиомы ИВ истинны при T=1 (ибо они тавтологии), сама T истинна при T=1 и, кроме того, MP сохраняет истинность при T=1 (надеюсь, с последним сами справитесь).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс май 11, 2008 10:25 pm 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
Давайте сформулируем теорему следующим образом: Формула F ИВ
выводима в ИВ+T, тогда и только тогда, когда F=1 при Т=1.
Доказательство
Достаточность:
Пусть F=1 при Т=1, покажем что она выводима в ИВ+Т. Действительно, так как T-->F - есть тавтология, то следовательно, в силу полноты ИВ она выводима. Тогда по МР из посылок Т и T-->F
вытекает F. (правда я непойму почему,T-->F будучи тавтологией выводима? Ведь это, искуственная тавтология (т.е. она не представляет "графической" тавтологии, о которых как я понимаю только и дёт речи в ИВ) и фактически, мы могли бы ссылаться только на то, что формула 1-->1 - выводима в нашем исчислении, но в его сигнатуре вообще нет знака "1", потому вывод не обоснован полностью).

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вс май 11, 2008 11:14 pm 
Не в сети
Опытный автор

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Amigo писал(а):
я непойму почему,T-->F будучи тавтологией выводима? Ведь это, искуственная тавтология (т.е. она не представляет "графической" тавтологии, о которых как я понимаю только и дёт речи в ИВ)
Искусственных тавтологий не бывает. Если формула T-->F действительно является тавтологией, то она всенепременно будет "графической", можете не сомневаться. Т.е. в этом случае формула F будет такой, что запись T-->F примет интуитивно тавтологичный вид -- на манер T-->T или T-->(T-->T).


Вернуться к началу
 Профиль  
 
 Заголовок сообщения:
СообщениеДобавлено: Вт май 13, 2008 11:22 pm 
Не в сети
Частый гость

Зарегистрирован: Пт апр 11, 2008 4:38 am
Сообщения: 27
Спасибо за разъяснение вопроса. Теперь у меня другая фишка -
пытаюсь уже двое суток придумать пример теории, сигнатура которой, состоит уже из двух символов V={X,Y}. Вроде вышло… не знаю…
вообщем, разрешите представить Вашему вниманию теорию (XY_ИВ).

Теория (XY_ИВ).

Сигнатура V={X,Y}
Множество формул (XY_ИВ)= Множество формул ИВ
А={аксиоматика ИВ}+P+X+Y, где P=(x-->y’)’
R={MP}
Теорема:
Система (XY_ИВ) полна и непротиворечива.
Доказательство

Докажем предварительно лемму:
Лемма:
Формула F выводима в (XY_ИВ), тогда и только тогда, когда
F=1 при y=1 и x=1.
Доказательство
Необходимость: пусть F – некоторая выводимая формула в (XY_ИВ), т.е. (XY_ИВ) |-- F , тогда, поскольку (XY_ИВ)=ИВ+P+X+Y, то по теореме о дедукции будем иметь:
ИВ |-- (P-->(X--> (Y-->F)), и следовательно
(P-->(X--> (Y-->F)) – тавтология. Последнее может быть, лишь если при P=1 (X--> (Y-->F))=1.Но P=1 тогда и только тогда, когда y=1 и x=1. Тогда, очевидно и F=1.
То есть мы доказали, что (P-->(X--> (Y-->F)) тогда и только тогда тавтология, когда F=1 при X=1 и Y=1.
Достаточность:
пусть F – некоторая формула (XY_ИВ) обладающая свойством, что при y=1,x=1, F=1. Покажем, что она выводима, имеем:
(P-->(X--> (Y-->F)), поскольку при P=0,
(P-->(X--> (Y-->F))=1 а при P=1,c учётом условия: y=1,x=1, F=1, формула (X--> (Y-->F))=1, то следовательно
(P-->(X--> (Y-->F))=1, т.е. формула (P-->(X--> (Y-->F)) –
есть тавтология и значит выводима в ИВ. Теперь, поскольку,
P,X,Y – есть аксиомы, то применяя достаточное количество раз
правило МР, получим F. Ч.Т.Д.
Лемма доказана.


Теперь разобьем все формулы системы (XY_ИВ) на два класса:
А)все формулы, которые при y=1,x=1 дают значение 1
Б) все формулы, которые при y=1,x=1 дают значение 0.
Согласно лемме - все формулы класса (а) выводимы и не одна формула класса (Б) не выводима. Заметим теперь, что если формула F принадлежит классу (Б), то F’ принадлежит классу (А), следовательно одна из формул F или F’ выводима в нашем исчислении. Таким образом полнота доказана.
Непротиворечивость следует из того, что ни одна из формул класса (Б) не выводима. Теорема доказана.
Верно ли я рассуждал?
* * * * * * * * * * * *
Пока я думал над этим примером, мне в голову пришла мысль как построить полную и непротиворечивую теорию включающую в себя ИВ, сигнатура которой состоит из n переменных. Для этого достаточно доказать, что существует такая формула от n-переменных, истинная тогда и только тогда, когда все переменные одновременно равны единице.
(к слову: на формулу P – я набрёл, спустя десяток часов размышлений; так, что существование такой формулы для меня отнюдь не очевидно).
Как же можно это доказать? Подскажите пожалуйста.

_________________
Единственный способ установить границы возможного - это выйти за них в невозможное.


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

Зарегистрирован: Пн май 02, 2005 7:27 pm
Сообщения: 435
Ребят, ау, кто-нибудь, подсобите Amigo. :-)
(А я, с вашего позволения, уйду в работу на несколько дней.)


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу 1, 2  След.

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


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

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


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

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