Игошин Математическая логика и теория алгоритмов (1019110), страница 16

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

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

если 6(А„..., А„) = О„то .0;(А„..., А„) = 0 для некоторого 1 <! < )с. Следовательно, Г(Аь ..., А„) = 0 и значит на этом же наборе принимает значение 0 некоторый совершенный дизъюнктивный одночлен Ьь входящий в ее СКН-форму. Но тогда этот олночлен совпадает с одночленом .0о Таким образом, каждый совершенный дизъюнктивный одночлен Ю; из СКН-формы для 6 входит в СКН-форму для формулы Г, т.е. СКН-форма для Гимеет вид: Га Ю, л Рз л ...

л Ю„л Л»„л ... л Л„где Ь»„, ..., Ь, — совершенные дизъюнктивные одночлены от переменных Хо ..., Х„, не входящие в СКН-форму для формулы 6. С) Разберите решение задачи М«2.39, л из Задачника. 5 7. Приложение алгебры высказываний к логико-математической практике Прямая и обратная теоремы. Многие математические теоремы имеют структуру, выражаемую формулой Х вЂ” » К Утверждение Х называется условием теоремы, а утверждение à — ее заключением. Например: «Если в четырехугольнике все стороны равны между собой (А,), то его диагонали перпендикулярны (В,)».

Символическая запись этой теоремы: А, » Вь Второй пример: «Если в четырехугольнике все стороны равны (А,), то его диагонали делятся точкой пересечения пополам (В;)». Символически: А, -+ В1. Третий пример; «Если в четырехугольнике все стороны равны между собой (А,), то его диагонали делят соответствующие углы пополам (В," )». Символически: А, -» В,". Рассмотрим еще такой пример; «Если один из углов треугольника прямой (Аз), то квадрат длины одной из сторон этого треугольника равен сумме квадратов длин двух других его сторон (Вз)». Символически: Аз — » Въ Тщательный анализ теоремы А, -» В, позволяет выявить в ней более сложную структуру: условие Аз представляет собой дизъюнкцию трех утверждений (Аз м А~ м А~"), где высказывание А; есть «а= 90'», высказывание А есть «О = 90'» и высказывание Аз" — «Т = 90'» (символами а, 11, Т обозначены величины углов треугольника).

Аналогично, заключение Вз также представляет собой дизъюнкцию трех утверждений: 64 В' ~ В~"ч В2", где В2 — высказывание «а' = Ьз+ съ», В~' — высказыва- 2 2 ние «Ьз = а + с»„В2" — высказывание «с = а2+Ьз» (символами а, Ь, с обозначены длины сторон треугольника, лежащие против углов величины а, К, у соответственно). Таким образом, теорема А1 — > В2 при более пристальном рассмотрении имеет вид (А', «А'2 ~ А2") » -» (В2 '~ В2 '~ Вг"). Далее, если некоторая теорема имеет форму Х-» г', утверждение Г-» Х называется обратным для данной теоремы.

Это утверждение может быть справедливым, и тогда оно называется теоремой, обратной для теоремы Х-» ); которая, в свою очередь, называется прямой теоремой. Если же утверждение У вЂ” > Хне выполняется, то говорят, что обратная теорема для теоремы Х вЂ” » 'г'неверна. Так, для теоремы А, — » В~ обратная теорема неверна, а для теоремы А2 -» В2 справедлива обратная теорема Вз — » Аз (проверьте!). Таким образом, при доказательстве теоремы нужно четко выделять, каково ее условие и что доказывается. Доказательство прямой теоремы не дает оснований для вывода о том, что и обратная теорема также верна. Обратная теорема требует специальной проверки.

Это обусловлено тем, что формулы Х-» 1'и г'-» Х выражающие структуры прямой и обратной теорем, не равносильны, в чем мы убедились на приведенных примерах. Их неравносильность можно усмотреть также из таблиц истинности данных формул. Структура теоремы А, — » В, достаточно проста. Рассмотрим теорему более сложной структуры: «В равных треугольниках против равных углов лежат равные стороны». Чтобы четко выделить условие данной теоремы и заключение, сформулируем ее следующим образом: «Если два треугольника равны (А), то из попарного равенства двух углов этих треугольников (В) следует равенство их противолежащих сторон (С)».

Символически теорема записывается так: А » (В » С), т.е. она имеет строение, описываемое формулой Р— » (Д-» Я). На основании равносильности, получающейся из тавтологии теоремы 3.1, м (правило перестановки посьиок), данная формула равносильна формуле Д -» (Р— > Я), а на основании равносильности теоремы 4.4, г (см. также тавтологию теоремы 3.1, и— правило объединения и разьединения посылок) она равносильна формуле (Рл Ц) -» Я. Следовательно, теорема А -» (В-» С) может быть сформулирована в виде В» (А -» С) «Если два угладвух треУгольников попарно равны (В), то из равенства этих треугольников (А) следует равенство сторон, противолежащих этим углам (С)».

Наконец, третий вид данной теоремы (А л В) -» С: «Если треУгольники равны (А) и в них два угла попарно равны (В), то и противолежащие стороны равны (С)». Таким образом, условие этой теоремы состоит из двух утверждений А и В или представляет собой их конъюнкцию А л В, а заключением является угверждение С.

Если теперь зададимся целью сформулировать теорему, обратную рассмотренной теореме А -» (В -» С), то столкнемся с И ош» 65 некоторыми трудностями, преодолеть которые помогает алгебра высказываний. Обратная теорема — такая, в которой условие и заключение прямой теоремы поменялись местами. В рассматриваемой прямой теореме два условия и одно заключение. Это приводит к тому, что получается не одна обратная теорема, а несколько. Так, обращение первых трех форм данной теоремы приводит к следующим обратным утверждениям: 1) ( — > С) -+ А: «Если из попарного равенства двух углов треугольников следует равенство их противолежащих сторон, то такие треугольники равны»; 2) (А -» С) -» В: «Если отрезки обладают тем свойством, что, будучи сторонами в равных треугольниках, они лежат против равных углов, то эти отрезки равны»; 3) С вЂ” » (А л В): «Если сторона одного треугольника равна стороне другого треугольника, то треугольники равны и углы, противолежащие этим сторонам, также равны».

Наконец, можем сформулировать еще два обратных утверждения, получающихся из суждений А — > ( — » С) и  — » (А -» С) перестановкой двух последних высказываний. Иначе говоря, эти обратные утверждения получаются перестановкой местами одного из двух условий прямой теоремы и ее заключения: 4) А -» (С вЂ” > В): «Если треугольники равны, то из попарного равенства двух их сторон следует равенство противолежащих углов»; 5) В -» (С -» А ): «Если угол одного треугольника равен углу другого треугольника, то из равенства противолежащих этим углам сторон вытекает равенство самих треугольников», Предлагается самостоятельно убедиться в том, что лишь второе и четвертое из обратных утверждений справедливы, т.е.

действительно являются теоремами, а остальные утверждения неверны. Необходимые и достаточные условия. С понятиями прямой и обратной теорем тесно связан вопрос о необходимых и достаточных условиях. Если некоторая математическая теорема имеет структуру, выражаемую формулой Х-» г, то высказывание )'называется необходимым условием для высказывания Х (другими словами, если Х истинно, то г'с необходимостью должно быть также истинным), а высказывание Хназывается досваточмым условием для высказывания г'(другими словами, для того чтобы )'было истинным, достаточно, чтобы истинным бьио высказывание Х). Посмотрим с этой точки зрения на первую теорему А, -+ Ви Необходимым условием равенства в четырехугольнике всех сторон является перпендикулярность его диагоналей. Иначе говоря, достаточным условием для перпендикулярности диагоналей четырехугольника является равенство всех его четырех сторон.

Одно и то же утверждение может иметь несколько необходимых условий. Так, необходимыми условиями равенства всех сторон четырехугольника являются, кроме указанного, деление диа- 66 гоналей точкой их пересечения пополам (В',), деление диагоналями соответствующих углов пополам (В",) и т.д. Аналогично, одно и то же утверждение может иметь несколько достаточных условий. Так, для перпендикулярности диагоналей четырехугольника достаточно также, чтобы в нем было две пары равных смежных сторон. После того как доказана теорема Х-« 'г', возникает вопрос, будет ли найденное необходимое условие достаточным или достаточное— необходимым.

Иначе говоря, будет ли верно утверждение У-«Х, называемое обратным по отношению к теореме Х-«Г. Известно, что условие перпендикулярности диагоналей четырехугольника (В,), необходимое для равенства всех его сторон (А,), не будет достаточным для такого равенства. Для проверки нужно привести пример четырехугольника с перпендикулярными диагоналями, у которого не все стороны равны (сделайте это!).

Если справедливы утверждения Х-« 'г'и г' — > Х т.е. справедливо Х<-~ ); то считают, что Х вЂ” необходимое и достаточное условие для ); и, наоборот, что т' — необходимое и достаточное условие для Х, или же что г является критерием (для) Х. Математическая наука изобилует утверждениями вида Х ~-«); представляющими собой необходимые и достаточные условия, и их приходится отыскивать в самых разных ее областях. Происходит это приблизительно следующим образом. Предположим, требуется найти необходимое и достаточное условие для некоторого утверждения Х Начинают с отыскания ряда необходимых условий для Х т.е.

Утверждений )ь )ь )и ..., следующих из Х: Х вЂ” > )ь Х вЂ” > У~, Х-«);, ... При этом каждый раз пытаются анализировать, не окажется ли то или иное найденное условие или какая-либо их совокупность (коньюнкция) достаточным условием для Х т.е. окажется ли истинной какая-либо из импликаций: 1; -«Х, ); — > Х, У; — «Х, (У; л )",) — « -«Х, (У; л 1;) -«Х, ()~ л 1;) — > Х, (У; л )'~ л Уэ) — «Х ...

Так, в примере с четырехугольником имеем два необходимых Условия В, и В; для свойства А, т.е. верны две теоремы: А, -«В„ А1-> В;. Затем, если ни одно из необходимых условий в отдельности не является достаточным (именно такая ситуация в данном пРимере), то пытаются проверять на достаточность всевозможные конъюнкции этих условий. Так, в указанном примере справедливо следующее утверждение: (В, л В;) -э А. (Убедитесь в этом самостоятельно.) Поэтому конъюнкция В, л В; является достаточным условием для свойства А.

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

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