Постройте пример полного непротиворечивого множества формул,каждая формула в котором содержит не менее 2016 переменных.

задан 8 Окт '17 20:54

изменен 8 Окт '17 21:59

1

Пропущено слово "пример", а также сделаны две опечатки в слове "непротиворечивого". Мы ведь говорим "протИвник" и "рЕчь", а не "протЕвник" и "рИчь" :)

По содержанию вопроса: непонятно, для какого исчисления он ставится? Одно дело -- исчисление высказываний, другое -- исчисление предикатов. Следовало бы также уточнить используемую аксиоматику и систему правил вывода. А также того, что понимается под полным множеством формул.

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

(8 Окт '17 21:41) falcao

Опечатки случайны) Вопрос по исчислению высказываний.

Аксиоматика:(A1):F→(G→F); (A2):(F→(G→H))→((F→G)→(F→H)); (A3):(¬G→¬F)→((¬G→F)→G);

Правила вывода: modus ponens

Мн-во формул Г называется полным,если для любой формулы А из Г выводима одна из формул А или $$\bar A$$

(9 Окт '17 0:00) vs13131313
10|600 символов нужно символов осталось
1

Рассмотрим все формулы, которые истинны на наборе из единиц, то есть при условии истинности значений всех высказывательных переменных. Для краткости назовём их "хорошими". Сюда войдут все тавтологии ИВ -- в частности, все аксиомы. Если формула получена из двух "хороших" при помощи MP, то она также "хорошая": из |A|=1 и |A->B|=1 следует |B|=1.

Данное множество непротиворечиво, потому что вывести одновременно формулу X и формулу not(X) невозможно. Оно полно, так как одна из этих формул принимает значение 1 на наборе из единиц, то есть является "хорошей".

Сделать так, чтобы в запись всех формул входило много переменных, довольно просто. Если X -- формула, а T -- тавтология, то импликация T->X логически эквивалентна X. Поэтому достаточно все формулы вида X заменить на T->X, где T -- фиксировнная тавтология с большим числом переменных. Построить такую тавтологию очень легко: достаточно взять формулу A вида p(1)->p(2)->...->p(n) с правонормированной расстановкой скобок, где n достаточно велико, и положить T равной A->A.

Честно говоря, последнее выглядит как некий "изыск", то есть совершенно ненужное, хотя и лёгкое в реализации, усложнение.

ссылка

отвечен 9 Окт '17 2:45

по сути можно же взять любую тавтологию с большим числом переменных. Например, x_1 -> x_2 -> ... x_n -> 1?

(9 Окт '17 22:42) vs13131313
1

@vs13131313: если Вы возьмёте только одну тавтологию, то такая система не будет полной. Ведь следствиями тавтологий будут только тавтологии. Но среди формул ИВ имеется большинство таких, которые тавтологиями не являются, и их отрицания тоже не являются. Самый простой пример -- любая высказывательная переменная. Она и истинной, и ложной может быть.

Если имелась в виду одна вспомогательная тавтология с большим числом переменных, то, конечно, её построить легко. Только обычно константы в запись формул не входят, и 1 надо заменить на что-то типа x->x. Тогда это подойдёт на роль T.

(9 Окт '17 23:11) falcao

@falcao Да, имелась в виду одна вспомогательная тавтология с большим числом переменных.Спасибо за ответ.

Еще непонятен один момент:"Оно полно, так как одна из этих формул принимает значение 1 на наборе из единиц, то есть является "хорошей".", как из этого следует полнота?

(9 Окт '17 23:49) vs13131313
1

@vs13131313: рассмотрим две формулы, одна из которых является отрицанием другой. Если одна из них принимает значение 1 на каком-то наборе, то другая принимает значение 0, и наоборот. Значит, ровно одна из формул принадлежит рассматриваемому множеству. Это и означает полноту (с учётом того, что вторая из формул невыводима ввиду непротиворечивости). Вообще, тут задействован самый простой эффект, который только может быть.

(10 Окт '17 0:59) falcao
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×4,520
×1,476
×26

задан
8 Окт '17 20:54

показан
548 раз

обновлен
10 Окт '17 0:59

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru