Дж. Андерсон - Дискретная математика и комбинаторика (2004) (1127091), страница 5
Текст из файла (страница 5)
Для этой импликации имеем: конверсия: Если он популярен, то он играет в футбол инверсия: Если он нг играет в футбол, то он не популярен контрапозиция: Если он не популярен, то он не играет в футбол Важно понимать, что высказывания Если он живет в Детройте, то Боб навесгпит его и Боб навестит его, если он живет в Детройте по сути являются одним и тем же высказыванием. Однако высказывание Если Боб навестит его, то он живет в Детройте не совпадает с предыдущими высказываниями. Не важен порядок, в котором р и у присутствуют в предложении, а важно, какая 1 Т Т 2 Т Е 3 Е Т 4 Г Г Г Т Е Т Е Т Т Е Е Г Е Е Е Т Т Е Р Т Т Т Ф РАЗДЕЛ ПЗ.
Зквоввлвнтныв высказывания 29 часть предложения является частью "если", а какая часть является частью "то". Может показаться, что при замене если р, то а на о, если р получается конверсия, но с логической точки зрения последнее высказывание совпадает с исходным. Часть (ж) теоремы, которая будет сформулирована ниже, говорит о том, что импликация и ее контрапозиция логически эквивалентны. Эквивалентность и контрапозиция условных высказываний имеют в математике большое значение, Зачастую гораздо легче доказать теорему от противного, чем дать ее прямое доказательство.
Используя эквивалентность импликации и ее контрапозиции, нетрудно показать, что конверсия и инверсия импликации имеют одну и ту же таблицу истинности. В то же время импликация и ее конверсия (или инверсия) имеют различные таблицы истинности. Непонимание этого факта — источник распространенных ошибок в так называемых "логических" рассуждениях. ТЕОРЕМА 1.3. Используя таблицы истинности, можно доказать следующие логические эквивалентности: а) Законы идемпотентноети РЛраз р; РЧР=Р.
б) Закон двойного отрицания -(-р) = — р в) Законы де Моргана -(р ь' д) — = Р л -у; -(р л в) = -р г -о. г) Свойства коммутативности рло=олр; равд= — дь'р д) Свойства ассоциативности рл(балт) ь— з (рло) лт; р г(в'гт) = (р'го) гт. е) Свойства дистрибутивности р л (в и т) = (р л о) ь'(р л т); рч (в л т) = (р ч у) л (р ь' т). ж) Закон контрапозиции Р ч— = ч Р. з) Другие полезные свойства р- в= -рь д; р о — = (р о) л(о р). 30 ГЛАВА 1. Таблииы истинности, логика, доказательства (рЛ(р о)) - о.
Ему соответствует таблица истинности Случай р (р Л (р а)) 1 Т 2 Т г 3 Е Т 4 с Е Т Т Т л с с л Е Т Е Т Т Т Т Т Е Т Т Т с Столбец, обозначенный звездочкой, дает истинностные значения исходного сложного высказывания. Высказывание истинно во всех четырех возможных случаях, следовательно, является тавтологией. Имея логически истинное высказывание-тавтологию, легко построить логически ложное высказывание-противоречие.
Для этого достаточно взять отрицание логически истинного высказывания. Поэтому высказывание -((р Л (р а)) о) логически ложно. Давайте теперь рассмотрим некоторые свойства, связанные с логически истинными и логически ложными высказываниями. Пусть символ Т обозначает высказывание, которое есть тавтология, поэтому имеет таблицу истинности, состояшую из одних Т. Символом Г обозначим противоречие, т.е.
высказывание, таблица истинности которого содержит л во всех строках. Используя таблицы Отметим, что благодаря свойству ассоциативности высказывания (рлд) Аг и рЛ(уЛг) могут быть записаны в виде рдддг. Аналогично, (рну)Чг и рЧ(г1'иг) можно записать просто как ры дч г. Высказывание, истинное во всех случаях, называется логически истинным, или тавтологией; высказывание, построенное так, что оно ложно в каждом случае, называется логически ложным, или противоречием. Теоремы в математике являются примерами тавтологий.
Было бы неприятно сознавать, что математические теоремы справедливы, к примеру, только в 80 процентах случаев. Высказывание Он сдаст или не сдаст экзамен есть пример тавтологии, поскольку либо одно событие, либо другое обязательно должно иметь место. Каждое высказывание вида р и р — тавтология. Шекспир должен был бы провозгласить: "Быть или не быть, это и есть тавтология".
Высказывание Если сдаст, то сдаст— тоже тавтология, хотя оно и не отличается глубиной. Примером тавтологии является высказывание Если он богат и удачлив, то он удачлив. Высказывание Она движется в направлении Техаса и она не движется в направлении Техаса всегда ложно, т.к. нельзя делать одновременно и то, и другое. Следовательно, это противоречие. Рассмотрим высказывание вида РлэдЕЛ 1.3. Эквивалентные высказывания 31 истинности, можно показать, что Р— Г, Т, Р Г, Т, Т. В каждом высказывании можно заменить любую его компоненту на логически эквивалентное ей высказывание.
Полученное в результате такой замены высказывание будет логически эквивалентно исходному, поскольку истинностное значение высказывания зависит исключительно от истинностных значений составляющих его компонент (но не от их формы или сложности). Например, Здесь мы впервые использовали законы логики и фиксированное множество "истинных высказываний" для образования новых "истинных" высказываний. Условные высказывания могут выражаться в виде различных языковых конструкций, но символически все они записываются как р — д. Вот несколько примеров таких конструкций: Если р, то д. р достаточно для д.
р является достаточным условием для д. д необходимо для р. д является необходимым условием для р. р, только если о (или: только если у, то р). Таблица для р — о показывает, что если р — у истинно и р истинно, тогда д должно быть истинным, т.е. истинность р достаточна для истинности д. Поэтому р достаточно для а имеет тот же смысл, что и р — о. Таким образом, если д ложно и д необходимо для р, тогда р должно быть ложно. Поэтому, если у истинно, тогда -р должно быть истинно и д — р. Но последнее выражение — контрапозиция для р — о; следовательно, у необходимо для р имеет то же значение, что и р — д. Анализ значения р только если у проводится аналогично.
Получаем, что р может быть истинным, только если д истинно. Если д не истинно, то р не может р Л р Л Г р У Т р ~/ Г р Л -р р У -р р — ' р (с/Ч т') Ч (р Л т) :— с/Ч (тЧ (р Л т) = о Н ((т Н р) Л (т / т)) д ~l ((т Х/ р) Л Т) вв ун(тУР) = — оы(рыт) = — (о /р)ыт = (р / д) / т . свойство ассоциативности свойство дистрибутивности эквивалентность эквивалентность свойство коммутативности свойство ассоциативности свойство коммутативности 32 ГЛАВА 1. Таблицы истинности, логика, доказательства быть истинным. Но это эквивалентно утверждению, что если д истинно, то р должно быть истинно и д — р. Последнее есть контрапозиция высказывания р — д, поэтому р только если д имеет то же значение, что и р — д.
Ранее было установлено, что порядок простых высказываний в составе условного высказывания не имеет значения; важно то, какое из простых высказываний следует за если (или в данном случае только если), а какое следует за то. Поэтому утверждения Только накопив денег, Фрзд сможет поступить в колледж и Фрэд сможет поступить в колледж, только если накопит денег рассматриваются как одно и то же высказывание.
ПРИМЕР 1.4. Приведите следующие высказывания к виду р — ~ д или у — р: а) Он добьется успеха, только если будет усердно работать. б) Он счастлив, только если управляет автомобилем. в) Наличия денег достаточно, чтобы быть счастливым. г) Наличие денег необходимо, чтобы быть счастливым. д) Чтобы победить на выборах, нужно набрать достаточно голосов. Ответ: а) Если через р обозначить высказывание Он добьется успеха, а через о — Он будет усердно работать, то высказывание если р, то д, или р — д примет вид Если он добивается успеха, то он работает усердно. б) Если р обозначает Он управляет автомобилем, а у — Он счастлив, то высказывание д только если р, или д — р имеет вид Если он счастлив, то он управляет автомобилем. в) Пусть р обозначает У него есть деньги, а у есть Он счастлив. Тогда высказывание р достаточно для д, или р — д может быть записано как Если у него есть деньги, он счастлив.
г) Пусть р обозначает У него есть деньги, а д обозначает Он счастлив. Тогда высказывание р необходимо для д, или у — р будет иметь вид Если он счастлив, то у него есть деньги. д) Пусть р обозначает Он победит на выборах, а д обозначает Он получит достаточное количество голосов, тогда высказывание д необходимо для р, или если р, то о, или р — о может быть записано в виде Если он победит на выборах, то он получит достаточное количество голосов. и Вернемся к рассмотрению логической связки . Поскольку высказывания вида р д и (р — д) А (д — р) логически эквивалентны, то р д означает то же, что и р тогда и только тогда, когда д, или р если и только если д.
Пусть, например, р обозначает высказывание Джим будет играть в футбол, а у — высказывание Джейн организует поддержку зригпелей. Тогда р д может быть выражено как Джим будет играть в футбол, если и только если Джейн организует поддержку зрителей. Следующие языковые конструкции, выражающие эквиваленцию высказыва- ний р д, равносильны: р если и только если д. р необходимо и достаточно для д.
р есть необходимое и достаточное условие для д. Пусть имеется высказывание Сэм играет в гольф тогда и только тогда, когда тепло, тогда ожидается, что если будет тепло, то мы увидим Сэма, играющего в гольф, и если Сэм играет в гольф, то погода, безусловно, теплая. Точно так же, если имеется высказывание Быть счастливым является необходимым и достаточным условием, чтобы быть удачливым, то имеется в виду, что если Джон счастливчик, то он и удачлив, а если Джону везет, то он, конечно, счастливчик. ° УПРАЖНЕНИЯ 1.
Используя таблицы истинности, докажите следующие эквивалентности: а) Закон де Моргана -(р Л а) = — -р Ч -а. б) Свойство ассоциативности связки Ч РЧ(уЧ т) = (РЧд)Чт. в) Свойство дистрибутивности связки или относительно и р Ч (а Л т) = (р Ч а) Л (р Ч т). г) Эквивалентность импликации и высказывания со связкой или Р у — = Р Чу. 2. Используя пункт (г) предыдущего упражнения, покажите, что отрицание для р — о эквивалентно р л а.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
