Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 7
Текст из файла (страница 7)
В этих случаях посылки истинны и заключение ложно. Из таблицы истинности Случай 1э 9 г легко видеть, что это случаи 5 и 7. Следует обратить внимание, что любое умозаключение с посылками Н„Нз, Нз, ..., Н„и заключением С является правильным тогда и только тогда, когда высказывание (Н1 л Нз Л Нз л... л Н„) — ~ С есть тавтология. Заметим, что порядок следования посылок не является существенным, поскольку Н1 Я Нз = Нз л Н,. Примем в качестве правила вывода следующее умозаключение, в правильности которого легко убедиться. Это правильное умозаключение называется правилом отделения (тос(из роаепз).
Рассмотрим пример использования правила отделения. Предположим, 6— целое число. Пусть р и д заданы следующим образом р: 6 четно о: 6 делится на 2, так что р — д: если 6 четко, то Ь делится на 2. Правило отделения дает если Ь четное, то Ь делится на 2 6 четное 6 делится на 2 Т Т Т Т Т с' Т Г Т Т Ь" Р Ь' Т Т Р Т Р Г Р Т с' Г Г Т Т Е Ь' Т Т Т Т 1 Т Г Т Т Т Г Т Т 2 Т Е Т Р Т Г Т Р 3 Т Т Т Т Г Ь' Ь' Р 40 ГПЯВА 1.
Таблицы истинности, логика, доказательства Допустим, что высказывание если 6 четко, то 6 делится на 2 получено как свойство целых чисел и 6 = 12. Тогда обе посылки истинны, так что нет сомнения в том, что 12 делится на 2. С другой стороны, если 6 = 13, тогда р ложно, и хотя умозаключение правильно, нельзя утверждать что-либо о делимости 6 = 13 на 2.
Если одна из посылок ложна, то истинность заключения никоим образом не зависит от правильности умозаключения. Перечислим некоторые правила вывода, на которые мы будем ссылаться в дальнейшем: а) Правило отделения (Мойиз Ропепз) б) Силлогизм р 'ч и — ~т р — ~т в) Моа'из ТоВепз г) Расисирение р равд д) Специализация Рдг р е) Конъюнкция р с1 р ~д ж) Всибор р р — ~ (т~lз) т- с1 з — ~ с1 з) Исключаюсций выбор р'г д р — (т Л т) РАЗДЕЛ 1.4. Кксиометические системы: умозаключения и доказательстве 41 и) Сведение к абсурду Гзкедисгго аЫ АЬзигдит) р — +(т Л г) Если яблоко красное, то оно спелое Яблоко спелое локо красное В обозначениях р: яблоко красное яблоко спелое умозаключение принимает вид Р 'ч у р Из таблицы истинности Случай р д ((р — ~ у) Л у) — + р 1 Т Т Т 2 Т Е Е 3 с Т Т 4 Г Е Т Т Т Т Т Г Е Т с Т Т Г Г Т Т с Г очевидным образом следует неправильность умозаключения.
В случае 3 обе посылки р — у и д истинны; однако, заключение р таковым не является. Таким образом, умозаключение неправильно. Данный вид неправильного умозаключение называется ложной конверсией. Точно так же умозаключение Р ' Ч р Правильность всех перечисленных умозаключений можно показать с помощью таблиц истинности. Сведение к абсурду используется в методе доказательства, известном как доказательство от противного. Он состоит в следуюгцем: мы допускаем, что истинным является отрицание того высказывания, которое необходимо доказать; затем пытаемся прийти к противоречию.
Если это удается, исходное утверждение доказано. Обратите внимание, именно такое рассмотрение было основой ранее упомянутого метода доказательства правильности умозаключения, альтернативного использованию таблиц истинности. Таким образом, этот альтернативный метод рассуждения является правильным. Рассмотрим такое умозаключение: 42 ГПАВА 1. Таблицы истинности, логика, доказательства является неправильным и называется ложной инверсией. В большинстве аксиоматических систем теоремы и аксиомы могут быть весьма сложными, а их переплетение с правилами вывода — весьма запутанным. Сейчас мы попытаемся объяснить, что происходит в процессе доказательства и как доказательства конструируются.
Сложные доказательства обычно представляют собой длинную цепочку правильных умозаключений вышеуказанных типов. Поэтому доказательство можно определить как последовательность утверждений, каждое из которых истинно в силу одной из следующих причин: а) по предположению; б) по аксиоме или определению; в) по ранее доказанной теореме или лемме; г) выведено из предыдущих утверждений; д) логически эквивалентно предыдущему утверждению. Используя логическую символику, в качестве примера покажем, что Р 'Ч г- о г есть правильное умозаключение. Итак, из трех посылок следует заключение р, и мы доказали р.
В большинстве математических доказательств логика "скрыта" в том смысле, что о ней специально не упоминается. Предполагается, что читатель может отслеживать логику без посторонней помощи, а ее рассмотрение неизбежно усложнило бы сам процесс доказательства. В некоторых доказательствах, которые последуют ниже,мы заглянем за кулисы с тем, чтобы проиллюстрировать использование логики. ° УПРАЖНЕНИЯ 1. Используя таблицы истинности, докажите правильность следующих умозаключений. а) Правило силлогизма р — + д о г р- г РАЗДЕЛ 1.4.
Яксиоматлические систлемьи умозаключения и доказательства 43 б) Правило выбора р р — ~ (тЧв) т — о в — ~ я Я в) Правило сведения к абсурду (гебцсИо аб аЬзцгбшп) ги — ~(т Л т) 2. Покажите, что следующее умозаключение не является правильными: Р Я о — чт , т 3. Определите, какое из следующих умозаключений является правильным: а) р- о б) -рис р — т дат сыт т .'. р р в) р- о г) р ты о -(р Л Ч) р р тМ р 4. Определите, какое из следующих умозаключений является правильным: а) б) рыо р — ~т дат в) р — о г) ри д о- т т У о цайт р р т 5.
Установите правильность следующих умозаключений, используя метод, альтернативный применению таблиц истинности; а) вУГ б) р- о С- т о — ~т в- щ т т 'ч' гс р в) р- о г) р~l д о-ч в т М д в — ~г р гас в .. Рыв т'4в 6. Установите правильность следующих умозаключений, используя метод, аль- 44 ГЛАВА 1. Таблицы истинности, логика, доказательства Р д д- т т в — ~ ш тНш в) р- д г) д — ~ в в- 1 СНд ,, р~lв 7. Покажите правильность следуюших умозак вода и эквивалентные высказывания: а) (в Лс) б) ш — «1 Р +д т — ~ д т р в) (-р Н д) г) х- ш г — ~ в (х ы ш) — ~г (р л д) — в Р— + гЧт р — ~( ты в) , т т Ч в 8.
Докажите, что логическая эквивалентность двух высказываний означает, что эквиваленция двух высказываний есть тавтология. Иными словами, для высказываний р и д докажите, что означает то же самое, что и р д — тавтология. Вслед за этим докажите, что последнее утверждение эквивалентно утвер- ждению: как р — д, так и д — р являются тавтологиями. В случае, когда импликация р — д есть тавтология, говорят, что р имеет следствием д, и часто записывают это как р ~ д. 9. Найдите среди указанных ниже выражений тавтологии: а) р- (рлд); б) р- (равд); в) (р- д)- (д- р); г) Цр — д) л д) — р); д) Ир д) л д) р). тернативный методу таблиц истинности: а) в~/Ф б) 1- т р -РЧ д т'4 д р ,, т'4в лючений, используя правила вы- Ряздел яа, полнота е логике еыокезыеении 45 1.5. ПОПНОТА В ПОГИКЕ ВЫСКАЗЫВАНИЙ Кроме использования в логике, одно из важных применений таблиц истинности состоит в конструировании коммутационных схем.
Прежде, чем приступить к изучению коммутационных схем, мы рассмотрим вопрос о минимальном количестве логических связок, необходимых для выражения любого высказывания, образованного с помощью определенных нами выше логических связок. Известно, что р о можно выразить как (р — о) д(о — р), так что использовать удобно, но не необходимо. К тому же р У о эквивалентно (Р Л - 1) М (- Р Л о) Случай р о 1!Я Случай р о Р).Я 1 Т Т 2 Т Г 3 Р' Т 4 л' Г .р' Т Т Т 1 Т Т 2 Т Е 3 Г Т 4 Е Е Р Е й' Т Для того, чтобы показать, что любую связку можно заменить связкой ~, доста- точно показать это для пар связок - и л или - и Ч, поскольку возможность выразить любую связку одной из этих пар уже показана.
Эквивалентность р ~ р и -р устанавливается при помощи следующей таблицы истинности: Случай р 1 Т Т 2 Т Р 3 Г Т 4 Р г" Т л' Т Т л Т Г Т Р л Т л Точно так же таблица Случай р о (р ) р) ( (о ) о) 1 Т Т Т Г Т Т Т Е Т 2 Т л Т л' Т Т Р Т Г 3 л' Т Р' Т л Т Т л Т 4 л л' Р Т Е Е г' Т Р' Также р — о эквивалентно р'ио, поэтому нет необходимости использовать —, если применяется и и.
Кроме того, рлд эквивалентно ( р ь' о) и рь'о эквивалентно -( р л-о). Следовательно, любое высказывание может быть выражено через пару связок и л или и ~~, причем в любом случае необходимы обе связки. Однако существуют две связки, обладающие тем свойством, что любое высказывание может быть выражено с использованием только одной из них. Этн связки: ) — так называемый штрих Шеффера и 1 — так называемая слгрелка Пирса. Свои названия эти связки получили в честь математиков Г.Шеффера и Ч.Пирса. Этим связкам соответствуют таблицы истинности 46 ГЛАВА 1. Твблоцы истинности, логике, доказательства показывает, что (р ) р) ! (д ) д) эквивалентно р ~/ с.
Можно также показать, что (р ! о) ) (р ) д) эквивалентно рЛ4. Таким образом, если показать, что и л или - и ь' можно выразить, используя только 1, тогда и любую связку можно выразить, используя лишь 1. Предоставляем читателю показать, что р 1 р эквивалентно -р, (р 1 р) 1 (д 1 д) эквивалентно р л д, а (р 1 с) 1 (р 1 ц) эквивалентно р ч д. Заметим, что р ~ д эквивалентно -(р л д), а р 1 о эквивалентно -(р и д). поэтому в дальнейшем связка ! будет называться не-и, а связка 1 будет называться не-или. Допустим, что задана произвольная таблица истинности.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
