Мне непонятна теорема "Подстановка" в той интерпретации, которую привел Бертран Майер в книге "Почувствуй класс". Эта теорема приведена на стр. 117, а ISBN 978-5-9963-0573-5.

Написано следущее:

Для любых булевых выражений u, v и e, если u = v является тавтологией и e’ – это выражение, полученное из e заменой каждого вхождения u на v, то e = e’ – это тавтология

P.S.: Здесь символом '=' показано эквивалентность. Другими словами, u = v следует читать как "u эквивалентно v".

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

задан 31 Авг '14 18:19

изменен 1 Сен '14 17:41

%D0%92%D0%B8%D1%82%D0%B0%D0%BB%D0%B8%D0%BD%D0%B0's gravatar image


9917

По-моему, смысл как раз в том и заключается, что структура выражения $%e$% совершенно неважна.

(31 Авг '14 18:23) cartesius

Если честно, то думал об этом, но тогда никак не понимаю слов "из выражения e". Зачем приводить источник, не сказав о том, как он устроен?

(31 Авг '14 18:27) sys_dev
10|600 символов нужно символов осталось
1

Смысл этого утверждения таков. Допустим, нами доказана логическая эквивалентность двух формул, то есть некая тавтология вида $%P\leftrightarrow Q$%, где $%P$% и $%Q$% -- какие-то логические формулы. Тогда, если имеется "сложная" формула $%\Phi$%, содержащая одно или несколько вхождений $%P$% в качестве подформулы, то можно эти вхождения заменить на $%Q$%, получая новую формулу $%\Phi'$%. Утверждается, что полученная формула будет логически эквивалента исходной, то есть формула $%\Phi\leftrightarrow\Phi'$% окажется тавтологией.

Например, нетрудно доказать тавтологичность следующей формулы: $%(a\to b)\leftrightarrow((\neg a)\lor b)$%. Она позволяет выражать импликацию через другие логические связки. Тогда, если у нас есть формула $%\Phi$% наподобие $%(a\to b)\land c$%, то после замены она превратится в формулу $%\Phi'$% вида $%((\neg a)\lor b)\land c$%, про которую можно утверждать, что она будет логически эквивалента формуле $%\Phi$%.

ссылка

отвечен 31 Авг '14 18:38

Прошу прощение за глупый вопрос, но что такое "вхождение P" ?

(31 Авг '14 18:40) sys_dev

@sys_dev, вхождение - имеется в виду вхождение в состав большего выражения, т.е. является частью большей формулы. Например, $%a\to b$% входит в выражение $%(a\to b)\land c$%. Это и есть вхождение.

(31 Авг '14 18:46) cartesius

Формула -- это последовательность символов. Под вхождением одной последовательности символов в другую понимается, грубо говоря, подстрока. Например, про строку $%axyzzabxyzac$% можно сказать, что она имеет два вхождения подстроки $%xyz$%. Понятно, что в формулу $%\Phi$% из приведённого мной примера таким же образом входит $%(a\to b)$%.

(31 Авг '14 18:48) falcao

@cartesius, про меня проверить: Под символами '->' и '^' понимается операции вхождения и конъюнкция, все верно?

(31 Авг '14 18:50) sys_dev

$%\rightarrow$% - операция импликации. $%a\rightarrow b$% - это то же самое, что $%(\neg a)\lor b$%, как написано выше. Вторая операция - действительно, конъюнкция, все верно.

(31 Авг '14 18:55) cartesius
1

@falcao, @cartesius, возьму таблицу истинности для импликации отсюда: http://markx.narod.ru/bool/impecv.htm

И мне не понятно, почему вариант False, True дает True?

Возьму утверждение "Если солнце выглянет, то будет светлее". Тогда, если следовать этой таблице, на это утверждение возможен вариант "Солнце не выглянуло, но стало светлее". Как такое возможно?

Другими словами, я жду, что Следствие происходит из Посылки. И следствие не возможно без посылки. Возможно "следует" в логической импликации и "следует" в естественном языке - это абсолютно разные вещи.

(31 Авг '14 19:47) sys_dev

@sys_dev: Ваша последняя догадка совершенно справедлива. Используемое в математике понятие импликации отличается от "обиходного". В частности, оно не подразумевает никакой причинно-следственной связи. В этом смысле фраза "если у меня чешется левое ухо, то дважды два четыре" будет считаться истинной вне зависимости от истинности её посылки. Если Вас эти аспекты интересуют более подробно, то предлагаю задать отдельный вопрос. Комментарии здесь слишком короткие.

(31 Авг '14 21:02) falcao
показано 5 из 7 показать еще 2
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×311

задан
31 Авг '14 18:19

показан
363 раза

обновлен
31 Авг '14 21:02

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

по почте:

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

по RSS:

Ответы

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

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