Логика

[arseniiv]

Должно быть , вроде бы. Из этого ваше докажется двумя подстановками вместо сигмы.

[RawonaM]

Из этого ваше докажется двумя подстановками вместо сигмы.

Не понял.

[RawonaM]

Вот еще интересная штука:
По индукции определено множество I высказываний, в которых есть только импликация и атом p.
Нужно доказать, что I линейно предупорядоченное.

Я думаю, что тут для начала нужно по структурной индукции показать, что может быть F только в той модели, где p=F.
Ибо каждое высказывание в форме в итоге сводится к p и b может быть F только если p=F. В общем, рекурсия. Как это правильно сформулировать, не знаю.

А уж из того, что есть модель для всего множества и того, что у него всего один атом, прямо истекает его линейность, т.к. есть у этого множества есть всего две модели по значению атома.

[Gerbarius]

если для любых и при условии и следует выполнимость формулы , то формулы множества совместно выполнимы

А в обратную сторону это же тоже верно, правильно? Вроде как тривиально.

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

Вот такой еще вопрос:
эквивалентны ли два утверждения
1) тавтология
2) для любых верно следующее:

Мне кажется что да, но я не уверен почему-то. Вроде как доказал

Да. А если доказали, то откуда неуверенность? 
На самом деле здесь условие можно заменить на , так как выполняется всегда.

[RawonaM]

Да. А если доказали, то откуда неуверенность? 

Из-за другой логики, точнее из теории вероятности Есть задание «доказать или опровернгуть», в нем два пункта. Если оба пункта нужно доказывать или оба пункта нужно опровергать, то всегда есть подозрение, что закралась ошибка. Ну что же, выходит, что в этот раз оба пункта были верны

[arseniiv]

Не понял.

Что-то я и сам запутался. Подставить можно всё, а вот следует ли из этого что-нибудь...

[Gerbarius]

Вот еще интересная штука:
По индукции определено множество I высказываний, в которых есть только импликация и атом p.
Нужно доказать, что I линейно предупорядоченное.

Я думаю, что тут для начала нужно по структурной индукции показать, что может быть F только в той модели, где p=F.
Ибо каждое высказывание в форме в итоге сводится к p и b может быть F только если p=F. В общем, рекурсия. Как это правильно сформулировать, не знаю.

А уж из того, что есть модель для всего множества и того, что у него всего один атом, прямо истекает его линейность, т.к. есть у этого множества есть всего две модели по значению атома.

Здесь потенциально возможны четыре распределения истинностных значений для каждой формулы. И если бы нашлись две формулы, одна из которых принимает значение T при p=T и F при p=F, а другая в точности противоположные значения, то ни одна из них не следовала бы из другой. То есть фактически нужно показать, что таких двух формул нет (остальные случаи "линейности" не мешают).
На самом деле любая формула в I является либо тавтологией, либо эквивалентна p, то есть принимает T при p=T и F при p=F. Это как раз легко доказывается структурной индукцией (или натуральной по "глубине" построения формулы). Можно, кстати, доказывать и то свойство, которое вы предложили, оно тоже подойдёт.
Чтобы структурной индукцией доказать, что все формулы из I обладают нужным свойством, нужно лишь показать, что p обладает этим свойством, и что обладает нужным свойством, коль скоро им обладают как , так и . А больше ничего и не требуется.

[RawonaM]

Благодарю за помощь!
Запечатал задание, почти неделю над ним сидел.
Таки курс не из простых.

Теперь надо за до конца недели сделать теорвер и дискретку, потом браться за следующее задание по логике...

[RawonaM]

Бесит нелогичная логика.

Вот смотрите: на форуме курса сказали, что означает "нет такой модели, которая выполняет бету", а означает «есть такая модель, которая выполняет альфу и не выполняет бету». Нелогично, по-моему.

[RawonaM]

Впрочем, может и логично...

[RawonaM]

на форуме курса сказали, что означает "нет такой модели, которая выполняет бету"

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

[arseniiv]

В другом месте на форуме сказали, что это означает, что «не все модели выполняют бету»...

Скорее всего, именно это (у нас была алгебра высказываний, но алгебры предикатов не было, хотя было исчисление предикатов, как и высказываний). А для первого употребления надо писать тогда .

[RawonaM]

Скорее всего, именно это

Мне тоже так кажется. Тем более, что задание тут получается неправильное, если с тем вариантом.

[RawonaM]

Вроде контрадикцию как-то по другому обозначают.

[RawonaM]

Мне нужно доказать, что система выводов, включаяющая две аксиомы из системы Гильберта и единственное правило вывода Modus Ponens обладает свойством дедукции.
Мне кажется я доказал это с помощью только одной аксиомы, поэтому терзают сомнения.

Также спрашивается, если добавить к MP еще какое-то правило, то изменится ли свойство. Вот это я не врубаюсь. Система должна быть sound. Вроде кажется, что ничего не изменится, но вопрос подозрителен.

[Gerbarius]

включаяющая две аксиомы из системы Гильберта

Какие именно?
Эти что ли?


Или другие какие-то?

обладает свойством дедукции

Под этим имеется в виду справедливость дедукционной теоремы?
То есть, что из следует ?

[RawonaM]

включаяющая две аксиомы из системы Гильберта

Какие именно?
Эти что ли?


Или другие какие-то?

Да, эти.

обладает свойством дедукции

Под этим имеется в виду справедливость дедукционной теоремы?
То есть, что из следует ?

Точнее, что это следует в обе стороны.

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

Вторую сторону затрудняюсь. Написано примечание, что для начала рекомендуется доказать . Доказал, но не пойму куда его притулять.

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

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

[Gerbarius]

Тут нужно рассмотреть все случаи, как может быть получен вывод .
Их всего три.
1) входит в или - аксиома. Тогда по определению . Отсюда и из   получаем .
2) - это . В этом случае как раз и нужно , а точнее,
что , что впрочем следует из первого.
Этот случай к предыдущему, если что, не сводится, так как может не быть аксиомой и может
не входить в , а потому может быть неверно (а именно на этом основаны рассуждения в предыдущем случае).
3) получено по правилу modus ponens из и . Допускаем, что мы можем построить выводы и . Тогда вывод строится при помощи этих выводов и аксиомы .
Отсюда дедукционная теорема следует в силу обычной математической индукции по длине вывода (или в силу дедуктивной индукции, если она вам знакома).
Можно привести  и вполне конкретный алгоритм построения нужного вывода. означает, что у нас есть вполне конкретный вывод, который можно, например, представить в виде дерева (в данном случае бинарного). В узлах дерева мы записываем утверждения вида . Утверждения во внутренних узлах получаются из утверждений в дочерних узлах по правилу modes ponens, а утверждения в конечных узлах получаются как в случаях 1 и 2. Затем мы просто последовательно преобразуем это дерево в другое, где  поддеревья с корневым узлом преобразуются в поддеревья с корневым узлом . Сначала преобразуются поддеревья, состоящие из конечных узлов, по алгоритму, рассмотренному в случаях 1 и 2, а затем и все остальные, для которых уже преобразованы оба дочерних поддерева, по алгоритму, описанному в случае 3, пока не будет преобразовано всё дерево.

Также спрашивается, если добавить к MP еще какое-то правило, то изменится ли свойство. Вот это я не врубаюсь. Система должна быть sound. Вроде кажется, что ничего не изменится, но вопрос подозрителен.

Аксиомы можно добавлять какие угодно. То рассуждение, которое я привёл выше, не изменится никак. Но если добавить новое правило вывода, то появляется ещё один случай, который нужно рассматривать отдельно. В этом случае справедливость дедукционной теоремы может быть нарушена. Например, если добавить правило подстановки, что из можно вывести , где получено из подстановкой некоторой формулы вместо некоторого атома (во всех вхождениях этого атома в ), то дедукционая теорема уже не будет верна. Например, из подстановкой можно получить , но получить нельзя. Хотя дедукционная теорема может и в таких случаях всё же оказаться справедливой, если наложить соответствующие ограничения на выводы, с которыми мы имеем дело.

[RawonaM]

Отсюда дедукционная теорема следует в силу обычной математической индукции по длине вывода

У вас получилось так компактно это написать...
Наши почему-то всегда пишут доказательство по индукции в полной форме, т.е. базис индукции (доказательтво в одну строку) и шаг индукции (доказательтво в n строк), хотя по сути они в основном повторяют друг друга.

Спасибо, вроде теперь стало понятно, а то я совсем не в ту сторону копал.

[RawonaM]

Допускаем, что мы можем построить выводы и .

Как же вы это можете допустить? Вы же это доказываете...
Или я чего-то недопонял.

[Gerbarius]

Допускаем, что мы можем построить выводы и .

Как же вы это можете допустить? Вы же это доказываете...
Или я чего-то недопонял.

Доказывается-то всё индукцией, а это фактически индуктивное предположение, которое используется при обосновании шага индукции. Правда, в случае обычной математической индукции всё выглядит несколько сложнее по форме. То есть в этом случае нужно сначала явно рассмотреть базис индукции, который включает в себя случаи 1 и 2 (только они возможны для выводов длины 1), а затем, допустив, что дедукционная теорема справедлива для всех выводов длины , показать что она справедлива и для выводов длины (шаг индукции). Обоснование шага индукции включает в себя повторное рассмотрение случаев 1 и 2 и случай 3. При рассмотрении случая 3 длина каждого из выводов и будет меньше длины рассматриваемого вывода , а значит, к ним применимо индуктивное предположение. То есть фразу

Допускаем, что мы можем построить выводы и .

нужно понимать в том смысле, что эти выводы можно построить в силу индуктивного предположения.

Но в случае дедуктивной индукции всё несколько проще, хотя и не принципиально. Попробую рассказать про неё. Допустим, у нас есть класс высказываний, (в нашем случае это выражения вида ), и из них выделен класс "теорем" следующим образом:
1) Выделен класс "аксиом", то есть высказываний, которые "автоматически" считаются теоремами. В нашем случае это выражения вида , где либо входит в , либо является аксиомой в рассматриваемой нами системе гильбертовского типа.
2) Выделен ряд правил вывода, каждое из которых из заданного числа посылок-"теорем" строит заключение-"теорему". В нашем случае есть единственное правило .
3) "Теоремы" - это те и только те высказывания, которые могут быть "выведены" из "аксиом" при помощи конечного числа применений правил вывода.
Тогда, чтобы доказать, что некоторое свойство справделиво для всех "теорем", достаточно доказать, что
оно справедливо для всех "аксиом", и что для всякого правила вывода его заключение обладает этим свойством, коль скоро им обладают его посылки. В этом и состоит принцип дедуктивной индукции.
В нашем случае применение дедуктивной индукции просто сводится к рассмотрению случаев 1, 2, 3 буквально в том виде, как я написал. В этом случае

Допускаем, что мы можем построить выводы и .

это просто (индуктивное) предположение, что доказываемое свойство справедливо для посылок применения правила modus ponens.

[RawonaM]

Например, если добавить правило подстановки, что из можно вывести , где получено из подстановкой некоторой формулы вместо некоторого атома (во всех вхождениях этого атома в ), то дедукционая теорема уже не будет верна. Например, из подстановкой можно получить , но получить нельзя.

P* ведь должен следовать логически из P, да? Иначе же система не будет sound.
Например вроде сойдет.

А точно из этого нельзя получить ?
Это же тавтология...

[Gerbarius]

Например, если добавить правило подстановки, что из можно вывести , где получено из подстановкой некоторой формулы вместо некоторого атома (во всех вхождениях этого атома в ), то дедукционая теорема уже не будет верна. Например, из подстановкой можно получить , но получить нельзя.

P* ведь должен следовать логически из P, да? Иначе же система не будет sound.
Например вроде сойдет.

А точно из этого нельзя получить ?
Это же тавтология...

Я забыл добавить, что мой контрпример относится к обычному классическому исчислению высказываний, но надеюсь, это не вызвало недоразумений.
не обязано ни из чего следовать. Оно просто получается из некоторым формальным преобразованием. Нас ведь спрашивают, что будет, если добавить ещё одно правило, но в выборе этого правила нас никто не ограничивает, а потому для построения контрпримера можно взять любое удобное правило. Опять-таки для контрпримера достаточно указать ровно один случай, когда дедукционная теорема не выполняется. Конечно, можно получить, но уже нет, и одного этого только достаточно, чтобы заключить, что дедукционая теорема при добавлении к классическому исчислению высказываний правила подстановки справедлива не будет. Замечу, кстати, что под невыводимостью  , конечно, имеется в виду невыводимость в системе, к которой добавлено правило подстановки. Строго говоря, это не совсем очевидно, но можно показать, что в классическом исчислении высказываний с единственным правилом modus ponens, из следует , а потому добавление правила подстановки не увеличивает множество доказуемых формул. Тогда  невыводимо (даже с правилом подстановки) просто потому, что это не тавтология.

[RawonaM]

В задании требуется чтобы система была sound, т.е. чтобы все, что можно вывести, следовало логически.

[Gerbarius]

В задании требуется чтобы система была sound, т.е. чтобы все, что можно вывести, следовало логически.

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