С помощью правил естественного вывода доказать выводимость формулы в теории L. Правилом замены эквивалентным не пользоваться. (¬(¬X ∪ Z) ⊃ ¬(Y ⋂ ¬Z)) ≡ (¬ X ∪ ¬Y ∪ Z)

задан 11 Окт '17 20:48

@flamingo: логические исчисления -- это примерно как языки программирования. Под L можно понимать, вообще говоря, что угодно. Такое обозначение есть в учебнике Мендельсона, то там логическими связками являются только отрицание и импликация. Нужно точное описание правил. Естественный вывод -- это очень хорошая современная идея, и её я бы применял как можно чаще. Но без дополнительной информации тут в принципе ничего сделать нельзя.

Наверное, вместо объединения и пересечения там всё-таки дизъюнкция и конъюнкция?

(11 Окт '17 21:06) falcao

@falcao Да, дизъюнкция и конъюнкция, конечно

(11 Окт '17 21:50) flamingo

@flamingo: а где ссылка на описание исчисления? Я вроде бы привёл доводы в пользу того, что она обязательна. Почему-то примерно в 90% случаев приходится вещи этого рода дополнительно уточнять.

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

(11 Окт '17 22:47) falcao

@flamingo: эта ссылка не соответствует Вашему условию. По ней L означает то же, что в Мендельсоне, и это хорошо известная вещь. Но там нет в сигнатуре конъюнкций или дизъюнкций. Кроме того, правила естественного вывода -- вещь более современная. Мендельсон был издан очень давно. Это хорошая книга, но о естественном выводе там нет ничего. Хотя я всегда эти вещи трактовал именно в таком духе, и у меня даже некоторые заметки на эту тему были написаны.

(12 Окт '17 2:01) falcao

@falcao Ну я так думаю, что (¬(¬X ∪ Z) ⊃ ¬(Y ⋂ ¬Z)) можно представить как (¬X ∪ Z) ∪ ¬(Y ⋂ ¬Z)). И тогда правомерно ¬X -> ¬X ∪ Z -> ¬X ∪ Z ∪ ¬(Y ⋂ ¬Z)). Аналогично из Z -> ¬X ∪ Z ∪ ¬(Y ⋂ ¬Z)). Но вот как без закона де Моргана вывести, что ¬Y -> ¬X ∪ Z ∪ ¬(Y ⋂ ¬Z)), я не знаю. Но вообще, насколько я поняла задание, можно использовать помимо импликации и отрицания конъюнкцию и дизъюнкцию, вместе с их выводами

(22 Окт '17 22:13) flamingo

@flamingo: мы не можем по своему усмотрению заменять формулы на логически эквивалентные. Должна быть задана чёткая система аксиом и правил вывода. Скорее всего, имелось в виду то, что здесь было выписано в одном из комментариев. При наличии чётких правил, я там изложил решение.

(22 Окт '17 22:32) falcao

@falcao Да, наверно, те же правила, как и там. Исходя из этого в правую сторону получилось ¬X ∪ Z -> ¬X ∪ Z ∪ ¬Y, ¬Y ∪ Z -> ¬X ∪ Z ∪ ¬Y, и так как (¬(¬X ∪ Z) ⊃ ¬(Y ⋂ ¬Z)) можно представить как (¬X ∪ Z) ∪ ¬(Y ⋂ ¬Z)), то в правую сторону этого достаточно. Все же не могли бы вы, пояснить, как в левую сторону можно доказать?

(22 Окт '17 23:49) flamingo

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

(23 Окт '17 1:40) falcao
показано 5 из 9 показать еще 4
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×1,193

задан
11 Окт '17 20:48

показан
652 раза

обновлен
23 Окт '17 1:40

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

по почте:

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

по RSS:

Ответы

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

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