В.И. Игошин - Задачи и упражнения по математической логике и теории алгоритмов - 2007 (1019105), страница 16

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

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

Р е ш е н и е. а) Точка лежит на перпендикуляре к отрезку, проведенном через середину этого отрезка, тогда и только тогда, когда она равноудалена от концов этого отрезка. 3.24. Руководствуясь определением импликации (таблицей истинности этой операции), сформулируйте: а) достаточное, но не необходимое условие истинности импликации; б) необходимое, но не достаточное условие ложности импликации; в) необходи- 79 мое и достаточное условие ложности импликации; г) необходимое и достаточное условие истинности импликации.

3.25. Используя только законы алгебры высказываний, выясните, какие из приведенных ниже высказываний следуют из высказывания «Если целое число л делится на 6, то л также делится на Згс а) Чтобы и делилось на 3, достаточно, чтобы оно делилось на 6; б) Чтобы п делилось на 6, достаточно, чтобы оно делилось на 3; в) Чтобы п не делилось на 3, необходимо, чтобы л не делилось на 6; г) Число и делится на 6 тогда и только тогда, когда оно делится на 3; д) Число и делится на 3 тогда и только тогда, когда оно делится на 6.

3.26. На основе законов алгебры высказываний выясните, какие из приведенных ниже высказываний будут истинны, если истинно высказывание: «Равные треугольники подобны»; а) Треугольники равны только в случае их подобия; б) Подобие треугольников является необходимым условием их равенства; в) Треугольники подобны только в случае их равенства; г) Равенство треугольников является достаточным условием их подобия; д) Подобие треугольников является необходимым и достаточным условием их равенства; е) Для того чтобы треугольники не были равны, достаточно, чтобы они не были подобны. У к а з а н и е. Запишите данное высказывание символически: А -+ В, обозначив через А высказывание «Треугольники равны» и через  — «Треугольники подобны», Затем, используя эти обозначения, запишите символически каждое из предлагаемых высказываний и сравните полученную формулу с формулой, отражающей структуру данного истинного высказывания.

3.27. Пользуясь основными законами (тавтологиями) алгебры высказываний, докажите, что следующие составные высказывания истинны: а) Действительное число а больше 2 или меньше -1 в том и только в том случае, когда из того, что а не больше 2, следует, чтоа<-1; б) Если справедливо утверждение„что каждое алгебраическое уравнение с действительными коэффициентами нечетной степени имеет по меньшей мере один действительный корень, то справедливо и утверждение, что каждое алгебраическое уравнение с действительными коэффициентами, не имеющее действительного корня, имеет четную степень; в) Два утверждения; «Система и линейных однородных уравнений с л неизвестными имеет единственное решение тогда и только 80 тогда, когда определитель системы отличен от нуля» и «Система л линейных однородных уравнений с и неизвестными имеет по меньшей мере два решения тогда и только тогда, когда определитель системы равен нулю», одновременно истинны или ложны; г) Если дифференцируемая функция непрерывна, то невозможно, чтобы функция была дифференцируема и разрывна; д) Если справедливо, что невырожденная матрица имеет обратную, то справедливо также, что матрица вырождается или имеет обратную.

Р е ш е н и е. а) Введем обозначения для простейших высказываний: А: «а > 2» и В: «а ( -1». Тогда составное высказывание символически записывается так: (А л В) +» (-1А -+ В). Оно истинно на основании тавтологии задачи 1.28, д, потому что получается из этой тавтологии в результате подстановки вместо ее пропозициональных переменных Р и Д конкретных высказываний А и В соответственно. Упрощение систем высказываний. Решить задачи 3.28 — 3.31.

3.28. Администрация небольшого завода спешно дала в связи с неожиданным приходом инспектора следующую директиву по службе безопасности, в соответствии с которой должно выполняться по меньшей мере одно из следующих правил: а) Инспектору не разрешается курить на заводе; б) Если инспектору разрешается курить на заводе, то рабочие должны быть предупреждены об этом, и бригадир должен принять меры к быстрому уничтожению окурков; в) Рабочие должны быть предупреждены, или бригадир должен принять меры к быстрому уничтожению окурков; г) Или рабочие должны быть предупреждены и бригадир должен принять меры к быстрому уничтожению окурков, или инспектору не разрешается курить на заводе.

Как можно упростить эти правила? Р е ш е н и е. Введем следующие обозначения для простейших правил (высказываний), содержащихся в директиве: А: Инспектору разрешается курить на заводе; В: Рабочие должны быть предупреждены о том, что инспектору разрешено курить; С: Бригадир должен принять меры к быстрому уничтожению окурков.

Теперь директивные правила примут соответственно следующий вид: -1А; А -+ (В л С); В ч С; (В л С) ч -тА. Поскольку по меньшей мере одно из перечисленных правил должно выполняться, должна быть истинна и их дизъюнкция: -1А ч (А -+ (В л С)) ч (В ч С) ч ((В л С) ч -1А) — = ... Преобразуем это сложное высказывание, используя свойства участвующих в нем логических операций: 81 ... — = ~А ч -1А ч (В л С) ч (В ч С) ч (В л С) ч -~А — = ~А ч (В л С)ч В ч ~ С— = ~Ач((Вл С) ч В) ч С= — ~Ам Вч С=А-+(Вм С).

Таким образом, вся директива может быть сформулирована следующим образом: если инспектору разрешается курить на заводе, то либо рабочие должны быть предупреждены об этом, либо бригадир должен принять меры к быстрому уничтожению окурков. 3.29. Администрация морского порта издала следующие распоряжения: а) Если капитан корабля получает специальное указание, он должен покинуть порт на своем корабле; б) Если капитан не получает специального указания, он не должен покидать порта или впредь лишается возможности захода в этот порт; в) Капитан или лишается впредь возможности захода в этот порт, или не получает специального указания. Как можно упростить эту систему распоряжений? 3.30. Командир осажденной крепости послал следующие три сообщения: а) Если нам удастся получить продовольствие, то нам не будет угрожать смерть от голода; б) Если нам не удастся получить продовольствие, то нам или будет угрожать смерть от голода, или мы попытаемся прорвать кольцо окружения; в) Если нам будет угрожать смерть от голода, то мы попытаемся прорвать кольцо окружения.

Покажите, как можно сократить эти сообщения, не меняя их смысла. 3.31. На факультативном занятии по математической логике учитель сообщил ученикам 8-го класса, собирающимся в туристический поход по родному краю, следующие сведения о готовящемся походе: а) Будут приобретены новые палатки, новые рюкзаки, и 8-й класс пойдет в поход; б) Палатки и рюкзаки приобретаться не будут, и 8-й класс в поход не пойдет; в) Будут приобретены новые палатки, рюкзаки приобретаться не будут, 8-й класс пойдет в поход; г) Неверно, что либо будут приобретены новые палатки„либо не будут приобретены новые рюкзаки, либо 8-й класс пойдет в поход.

Отметив, что по крайней мере одно из четырех сообщений абсолютно верно, учитель попросил учеников наилучшим образом упростить всю полученную информацию и представить ее в виде одного простого условия. Правильные и неправильные рассуждения. Решить задачи 3.32— 3.43. 82 3.32.

Я пойду или в кино на новую кинокомедию (А), или на занятия по математической логике (В). Если я пойду в кино на новую кинокомедию, то я от всей души посмеюсь (С). Если я пойду на занятия по математической логике, то испытаю большое удовольствие от следования по путям логических рассуждений (Р). Следовательно, или я от всей души посмеюсь, или испытаю большое удовольствие от следования по путям логических рассуждений. Справедливо ли проведенное рассуждение? Р е ш е н и е. Учитывая символические обозначения высказываний, приведенные в условии, запишем посылки нашего рассуждения: А ч В, А -э С, В -э Р.

Покажем, что для формул алгебры высказываний имеет место следующее логическое следование: Х~ г', Х-+ У, У-+ )Р'!= У~ И~ где Х г', У, И" — пропозициональные переменные. В самом деле, предположим, что это следование неверно, т.е. найдугся такие конкретные высказывания А„Ап Ан Ад, что Л(Аь ч Аг) = 1, Л(А~ -+ Аз) = 1, ЦАг -+ А~) = 1, но ЦАз '~ А4) = = О. Тогда из последнего равенства следует, что Л(Аз) = О и Л(А,) = О.

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

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