Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

3. Ранее были рассмотрены связанные между собой условные высказывания, включающие в качестве компонент высказывания р и д. Ими являлись Используя таблицы истинности, докажите, что Р чан Р. Р ч ч Р ч ' Р Р з РАЭДЕП ЯЗ. Эквивалентные высказывания 33 импликация, конверсия (для р — д), контрапозиция (для р — д), инверсия (для р — д). 34 ГЛА8А 1. Таблицы истинности, логика, доказательства Импликация эквивалентна своей контрапозиции, но не эквивалентна своей конверсии. Часто используется выражение если р, то д, и наоборот. На самом деле это означает если р, то д, и если д, то р, или (р о) л (о р), что эквивалентно р а, или р, если и гполько если о.

Докажите, что р — д = д — -р, не используя непосредственно таблицы истинности. На основании этого результата докажите, что инверсия импликации эквивалентна ее конверсии. 4. Используя логически эквивалентные высказывания и не применяя непосредственно таблицы истинности, покажите, что а) р= (рлз) — ( злр). б) -(р о) = (р Л -о) Ч (о Л -р). 5.

Преобразуйте следующие высказывания к виду если р, то д: а) Он кентавр, только если он имеет шесть ног. б) Чтобы быть преуспевающим политиком, нужно бьипь избранным. в) Достаточно иметь деньги, чтобы быть популярным. 6. Преобразуйте следующие высказывания к виду если р, то д: а) г)еобходимо иметь шлем, чтобы играть в американский футбол. б) Только если я читаю Шекспира, я литературно образован.

в) Для меня сдать этот курс достаточно, чтобы получить диплом. 7. Дано высказывание Если я голосую, то я хороший гражданин. а) Сформулируйте конверсию этого выражения. б) Сформулируйте инверсию этого выражения. в) Сформулируйте контрапозицию этого выражения. 8. Дано высказывание Если я не буду выплачивать ссуду, у меня отберут участок. а) Сформулируйте конверсию этого высказывания. б) Сформулируйте инверсию этого высказывания. в) Сформулируйте контрапозицию этого высказывания.

1.4. АКСИОМАТИЧЕСКИЕ СИСТЕМЫ: УМОЗАКЛЮЧЕНИЯ И ДОКАЗАТЕЛЬСТВА Математики в большинстве своем имеют дело с теоремами и их доказательствами. Теоремы представляют собой "истинные" утверждения относительно рассматриваемых математических систем. Например, утверждение Гипотенуза прямоугольного треугольника длиннее любого из катетов — это известная из геометрии теорема Евклида.

Это утверждение считается истинным, поскольку оно "выводимо" из ранее принятых или выведенных истин геометрии Евклида. ««АЗДЕЛ 1.4. Аксиоматические системы: умозаключения и доказательстве 35 Математическая система начинается с неопределяемых понятий и утверждений, точно описывающих фундаментальные характеристики или истинные утверждения относительно этих понятий, которые математики используют для образования системы. Эти фундаментальные характеристики называются аксиомами или постулатами. Утверждения, выведенные (доказанные) только на основе этих фундаментальных свойств (аксиом и постулатов) и ранее доказанных утверждений с помощью логических правил, называются теоремами.

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

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

Важно, что логические правила, которые используются для вывода новых теорем из аксиом, постулатов и ранее доказанных в данной системе теорем, не порождают в качестве "теорем" ложные высказывания. Эти логические правила называются правилами вывода. Умозаключение состоит из совокупности утверждений, называемых гипотезами, или посылками, и утверждения, называемого заключением. Правильным умозаключением называется такое умозаключение, заключение которого истинно всякий раз, когда истинны его гипотезы. Правила вывода выбираются так, чтобы они были правильными умозаключениями. Умозаключения часто представляют в виде Н1 Нз гипотезы Нз С заключение Символ означает "следовательно".

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

В частности, используя правила вывода, легко проверить правильность умозаключения Р— 'Ч и- т т — «з з — «Ф 36 ГЛАВА 1. Таблицы истинности, логика, доказательства Проверка того же утверждения с использованием таблиц истинности намного сложнее. Однако, при помоши таблиц истинности мы можем доказать ложность утверждения, чего правила вывода сделать не позволяют. Рассмотрим умозаключение р р 'я д — > т ,, рдддт Таблицы истинности для посылок и заключения имеют следуюший вид. Случай р о т РЛ6Лт 1 Т Т Т 2 Т Т Г 3 Т Р Т 4 Т Г Е 5 т Т Т 6 Е Т Е 7 Е т Т 8 Г т Г Заметим, что, когда истинны все посылки (что имеет место в случае 1), истинным также является и заключение, а само умозаключение является правильным.

Рассмотрим умозаключение равд р — ~т о — т т Построим для него таблицу истинности. Случай р РЛ6 Р— +о о — +т т 1 2 3 4 5 6 7 8 Т Т Т Т Т т Т Г Т Т Е Г т Т Т Г Т Е Е Е Т Г Г т Т Т Т Т Е Е Е 1 Т Т Т Т Т Т Е с 1 Т Т Г Е Т Т Т Т 2 Т р Т Е Т Т Т Т 2 Т Е Т Т Т т Т Т 3 Т Г Т Т Т Г Т Т 3 Т Е Е Т Т Т К Т Е Т Г Т Е РАЗОЕЛ 1.4. Аксиометические системы: умозакякмения и оокезегпельстее 37 Мы снова приходим к выводу, что, когда все посылки истинны (что имеет место в случаях 1, 3 и 5), заключение истинно, и умозаключение правильно. Однако, если рассмотреть следующее умозаключение р 'ч д — ~т т и посмотреть на его таблицу истинности, Случай р д т р — + г7 мы обнаружим, что хотя в случае 1 истинны и посылки, и заключение, в случаях 5 и 7 посылки истинны, а заключение ложно.

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

Если д — т истинно, а т ложно, то 7 должно быть ложно. Аналогично, если р — т истинно, тогда р должно быть ложно. Но тогда р и д ложно, что приводит к противоречию с утверждением, что заключение ложно, а посылки истинны. На основании этого делаем вывод, что умозаключение правильно. 1 Т Т 2 Т Т 3 Т Г 4 Т Г 5 Г Т 6 Г Т 7 Г Г 8 Г Г Т Г Т Г Т Г Т Г Т Т Г Г Т Т Т Т 1 Т Г Т Т Т Г Т Т 2 Т Г Т Г Т Г Т Г 3 Т Т Т Т Г Г Г Г 38 ГЛАВА 1. Таблицы истинности, логика, доказательства Рассмотрим умозаключение Снова попытаемся свести рассмотрение к случаю, когда заключение ложно, а посылки истинны. Если р — 1 ложно, то р должно быть истинно и 1 ложно. Поскольку 1 ложно, то из истинности з — г следует, что з ложно. Если з ложно и г — з истинно, то г ложно.

Если г ложно и д — г истинно, то д должно быть ложно. Но поскольку р истинно, а д ложно, то р — д ложно, что невозможно. Опять приходим к противоречию с тем, что заключение ложно, а все посылки истинны. Таким образом, умозаключение правильно. Рассмотрим умозаключение Р— 'Я о — ~т рЧ г Если заключение ложно, то и р и т — оба ложны. Однако, если д ложно, то р — д и д — т — оба истинны. Поскольку обе посылки истинны, а заключение ложно, то умозаключение неправильно. Если посмотреть на таблицу истинности данного умозаключения, Случай р <у г р — д д — + т.

р ~/ г легко заметить, что рассмотренный случай соответствует строке 8 таблицы истинности, откуда следует неправильность умозаключения. Рассмотрим умозаключение Р Ч д — г т р Если заключение ложно, это означает, что р ложно. Но если посылки истинны, то г истинно. В этом случае р — д и д — т истинны вне зависимости от того, 1 Т Т Т 2 Т Т Р 3 Т Г Т 4 Т с Г 5 Р Т Т 6 с Т Р 7 Р Р Т 8 Г Р с Т Т Р Г Т Т Т Т 1 Т Г Т Т Т Г Т Т 2 Т Т Т Т Р Р Т Р РЯЗДЕЛ П4.

Яксиоматические системы: умоэаклкиения и докаэательстеа 39 истинно д или ложно. Таким образом, имеется два случая, когда можно показать неправильность нашего умозаключения: (1) р ложно, о истинно, г истинно и (2) р ложно, о ложно, г истинно.

Характеристики

Список файлов книги