Привести примеры пропозициональных предложений, для которых $%\not\vdash \phi \to \psi,\not \vdash\phi \to \neg \psi$% (в системе доказательств из предыдущего вопроса). Здесь $%\not \vdash \chi$% значит, что не существует формального доказательства, которое из отсутствия предположений выводило бы $%\chi$%.

Эта система доказательств sound и complete. То есть можно воспользоваться этим, и тогда вышеуказанное эквивалентно тому, что $%\not\models \phi \to \psi,\not \models \phi \to \neg \psi$% (и тут используется и soundness, и completeness), то есть что $%\phi \to \psi,\phi \to \neg \psi$% не тавтологии. Пример: $%\phi=p_1,\psi=p_2$%. Тогда $%p_1\to p_2,p_1\to \neg p_2$% не являются тавтологиями. Это верно?


Привести пример пропозициональных предложений, для которых $%\vdash \phi \to \psi,\vdash\phi \to \neg \psi$%. Также по soundness и completeness Достаточно привести пример тавтологий $%\phi \to \psi.\phi\to \neg \psi$%. Возьмем $%\phi=p_1\lor \neg p_1,\psi =p_1$%. Верно?

задан 9 Фев 21:32

изменен 9 Фев 22:00

Первый пример верен, второй нет. Из A V B невыводимо ни A, ни B. Тут надо брать в качестве ф любую тождественную ложь. Например, отрицание того же A V not(A), или отрицание A->A. Из тождественно ложного утверждения выводимо любое. Можно также взять в качестве ф формулу A and not(A).

(9 Фев 22:56) falcao

А есть ли смысл усложнять и брать что-то типа A and not(A), если можно просто взять F?

И верно ли, что в каждом из пунктов используется и soundness, и completeness? (Т.е. с одним из них не обойтись?)

(9 Фев 23:30) logic

@logic: я в начале сказал про тождественную ложь. Если константу F можно брать, то это самый простой пример. Упоминание A and not(A) возникло в контексте Вашего примера -- там по смыслу должно быть and вместо or.

После того, как доказана теорема о полноте исчисления высказываний, становится возможным заменить относительно сложное утверждение о выводимости (синтаксическую) на более простую проверку истинности (семантическую). Поскольку исчисление полно и непротиворечиво по факту, мне трудно ответить на Ваш вопрос. Это примерно как меня бы спросили, что будет если 2x2=4, но 3x3 не 9.

(10 Фев 2:15) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

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

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

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

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

отмечен:

×780

задан
9 Фев 21:32

показан
65 раз

обновлен
10 Фев 2:15

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

по почте:

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

по RSS:

Ответы

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

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