Пример 4.Рассмотрим составное высказывание «Если я – Ваша женщина и Вы – мой мужчина, то я никогда не перестану любить Вас. Я перестала любить Вас

Прежде всего, выделим простые высказывания, из которых и составлено рассматриваемое составное высказывание. Естественно считать, что эти простые высказывания в данном случае таковы:

P = «Я – Ваша женщина»,

Q = «Вы – мой мужчина»,

R = «Я никогда не перестану любить Вас».

В этих обозначениях для высказывания «Если я – Ваша женщина и Вы – мой мужчина, то я никогда не перестану любить Вас» формальным опредставлением является импликация (P Ù Q)® R. Далее, для высказывания «Я перестала любить Вас», которое по сути является от-рицанием простого высказывания «Я никогда не перестану любить Вас», формальным пред-ставлением является отрицание Ø R. Высказывание «Если я – Ваша женщина и Вы – мой мужчина, то я никогда не перестану любить Вас. Я перестала любить Вас» состоит из двух фраз (до и после запятой), в которых излагаются две последовательные части одной и той же «истории». Ни одна из не является ни следствием, ни причиной другой. В подобных случаях естественно считать, что данное высказывание является конъюнкцией двух высказываний, а его формальное представления также является конъюнкцией двух выражений, уже сопоставленных этим частям. В рассматриваемом случае имеем

((P Ù Q)® R)ÙØ R ■

Пример 5. Рассмотрим составное высказывание «Если я – Ваша женщина и Вы – мой мужчина, то я никогда не перестану любить Вас. Я перестала любить Вас. Значит, я – не Ваша женщина или Вы – не мой мужчина»

Вся история является импликацией. Её посылкой является текст до слова «значит», а зак-лючением – текст после слова «значит». Посылка уже проанализирована, и её формальное представление найдено в примере 4: ((P Ù Q)® R)ÙØ R. Формальным представлением заключения «Я – не Ваша женщина или Вы – не мой мужчина» является выражение Ø P ÚØ Q. Таким обра-зом, формальным представлением всего рассматриваемого высказывания является импликация

(((P Ù Q)® R) ÙØ R)®(Ø P ÚØ Q). (2) ■

Примеры 3, 4 и 5 ясно демонстрируют, что выделение исходных простых высказываний и построение сопровождающих формул требует содержательных рассуждений и не сводится к чисто формальным операциям.

Обратим внимание на то, что один и тот же символ может встречаться в одном и том же выражении несколько раз, как в формуле (2) из примера 5.

Непосредственно перед примером 1 говорилось об использовании выражения «высказыва-ние А» вместо более длинного и неудобного выражения «высказывание, обозначенное симво-лом А». При описании базовых операций в разделе 2.1 в том же смысле использовались выра-жения D Ù E, G E и т.д. Аналогично, вместо общего выражения «формальное представление Φ составного высказывания W», будет писать «выражение Φ», «высказывание, представленное выражением Φ», и т.д. Однако надо иметь в виду, что речь идёт об объектах разной природы – неформальных высказываниях и их формальных представлениях. Упомянутая «вольность язы-ка» допустима в тех – впрочем, широко распространённых – случаях, когда такая замена не приводит к неоднозначности понимания и ошибкам. Забегая вперёд, скажем, что примерно то же самое относится к выражениям «множество А», «кортеж α» и т.д. Соответствующие выраже-ния будут использоваться без дополнительных разъяснений.

Пример 6. Пусть P означает высказывание «Крис собирает видеофильмы» и Q означает высказывание «Джек играет на трубе». Тогда по этим двум простым высказываниям можно определить следующее составное высказывание: «Крис собирает видеофильмы и Джек не иг-рает на трубе». Используя введённые обозначения P и Q, представим его в виде P ÙØ Q. Здесь и далее используется соглашение, по которому знак отрицания имеет самый высокий приоритет. Это соглашение позволяет в данной формуле не использовать скобок. Точно также предполагается, что конъюнкция «важней» дизъюнкции (в том же смысле, что и в выражении ab + c, где сначала делается умножение, а потом – сложение). В остальных случаях очерёдность операций определяется расстановкой скобок ■

Пример 7. Рассмотрим высказывание «Женат я или не женат, я счастлив». Обозна-чим высказывание «я женат» символом P, высказывание «я счастлив » символом Q. Тогда дан-ное составное высказывание имеет формальный вид

(P ÚØ P) ® Q ■ (3)

Конечно, такое соответствие между содержательным высказыванием и его представле-нием вида (1) – (3) далеко не всегда столь очевидно, а сама процедура построения такого соот-ветствия вряд ли может быть полностью формализована. Хотя в рассматриваемых далее приме-рах всё это делается сравнительно просто, но тренировка здесь, как и во всякой не до конца формализованной деятельности, совершенно необходима. Образцами для такой формализации служат как примеры 3 – 6, так и примеры, приводимые ниже.

Пример 8. Представим высказывание «Если пол грязный, то я должен вымыть его» в формальном виде. Для этого прежде всего определим входящие в него простые высказывания. Положим P = «Пол грязный», Q = «Я должен вымыть его». Тогда рассматриваемое высказы-вание представляется в виде P ® Q, т.е. оно является импликацией ■

Пример 9. Представим высказывание «Если пол грязный, то я должен вымыть его. Пол грязный» в формальном виде. В данном случае у нас есть два последовательных высказывания, разделённых точкой: «Если пол грязный, то я должен вымыть его» и «Пол грязный». По-скольку оба высказывания относятся к одной «истории», то естественно рассматривать всё высказывание как конъюнкцию этих двух составляющих его простых высказываний. Конечно, это не теорема, и этот факт не может быть формально доказан. Это – вопрос соглашения, но та-кое соглашение, как минимум, не противоречит здравому смыслу. В большинстве тех случаев, когда высказывания разделены не точкой, а точкой с запятой, просто запятой, или союзом «и», составное высказывание также естественно представлять как конъюнкцию. Точно так же это делалось и в примере 4. Но надо быть внимательным и никогда не забывать о здравом смысле.

Первое высказывание (см. пример 8) представлено как импликация P ® Q, где P = «Пол грязный», Q = «Я должен вымыть его». Поэтому 1-ая часть рассматриваемого составного вы-сказывания уже представлена, как P ® Q. С учётом нашего соглашения о разделяющей точке по-лучаем следующее формальное представление: (P ® Q)Ù P, где P и Q – те же, что в примере 8 ■

Пример 10. Представим высказывание «Если пол грязный, то я должен вымыть его. Пол грязный. Поэтому я должен вымыть его» в формальном виде.

В данном случае 1-ая часть высказывания: «Если пол грязный, то я должен вымыть его. Пол грязный» уже представлена в формальном виде в примере 9: (P ® Q)Ù P. 2-ая часть исход-ного составного высказывания после слова «поэтому» такова: «Я должен вымыть его», что совпадает с высказыванием Q из примеров 8 и 9. Таким образом, мы имеем составное высказы-вание ((P ® Q)Ù P)? Q. Осталось «раскрыть» знак вопроса. В разделе 2.1 указывалось, что логи-ческие союзы «Если …, то …», «Поэтому», «Потому что», «Поскольку» и т.д. соответствуют импликации, в которой слева стоит посылка («причина»), а справа – заключение («следствие из данной причины»). Таким образом, исходное составное высказывание представляется в виде

((P ® Q)Ù P)® Q. (4)

Заметим, что в исходном высказывании перед словом «Поэтому» стоит точка. Однако здесь пишется импликация, а не конъюнкция, поскольку здесь явно сказано, что всё, стоящее перед точкой, является причиной, а всё, стоящее после связки «Поэтому», является заключени-ем. Содержание же всей этой простой истории таково. Мыть грязный пол – это моя обязан-ность, и если уж он грязный, то я должен его помыть. Ещё раз подчеркнём, что все рассуждения не являются формальными, но зато они являются правдоподобными. Заметим также, что при замене 2-ой точки на точку с запятой или запятую смысл рассказа не изменится и, значит, его формальное представление останется тем же самым ■

Пример 11. Представим высказывание «Если я видел дальше других, то потому, что я стоял на плечах гигантов» в формальном виде. (If I have seen farther than others, it is because I stood on the shoulders of giants (quote from Sir Isaac Newton)).

Положим

P = «Я стоял на плечах гигантов»,

Q = «Я видел дальше других».

Тогда рассматриваемое высказывание представляется импликацией P ® Q.

Заметим, что в исходной фразе заключение («Я видел дальше других») написано впереди посылки («Я стоял на плечах гигантов»). Действительно, что здесь заключение, а что посыл-ка, непосредственно определяется содержанием фразы, суть которой в том, что если стоишь вы-ше, то и видишь дальше (а не наоборот!). В то же время в формально определённой имплика-ции посылка всегда записывается слева от стрелки, а заключение – справа, т.е. посылка пред-шествует следствию. Это ещё раз демонстрирует, что при формализации высказывания надо ис- ходить в первую очередь из его содержания. Одна и та же простая мысль может быть записана на русском (и на любом другом) языке многими способами, но её формальное представление от этого не меняется ■

В следующих примерах 12 – 16 рассматривается несколько более сложная ситуация.

Пример 12. Представим высказывание «Все мужчины созданы равными» в формальном виде.

Положим

P = «Быть мужчиной»,

R = «Бытьсозданным равным».

Естественно переформулировать исходное высказывание «Все мужчины созданы равными» следующим образом: «Если Вы – мужчина, то Вы созданы равным». При этом смысл выска-зывания не изменился. Но это модифицированное высказывание можно записать как имплика-цию P ® R при выше определённых P и R ■

Пример 13. Представим высказывание «Все люди, созданные равными, являются жен-щинами» в формальном виде.

Положим

Q = «Быть женщиной»,

R = «Бытьсозданным равным».

Естественно переформулировать исходное высказывание «Все люди, созданные равными, яв-ляются женщинами» следующим образом: «Если Вы созданы равным, то Вы – женщина». При этом смысл высказывания не изменился. Но это модифицированное высказывание можно записать как импликацию R ® Q при выше определённых Q и R ■

Пример 14. Представим высказывание «Все мужчины созданы равными. Все люди, соз-данные равными, являются женщинами» в формальном виде.

Данное высказывание является конъюнкцией высказываний из примеров 12 и 13. Поэтому оно может быть представлено в виде

(P ® R) Ù (R ® Q) ■

Пример 15. Представим высказывание «Все мужчины являются женщинами» в фор-мальном виде.

Положим, как в примерах 12 и 13

P = «Быть мужчиной»,

Q = «Быть женщиной».

Естественно переформулировать исходное высказывание «Все мужчины являются женщина-ми» следующим образом: «Если Вы – мужчина, то Вы – женщина». При этом смысл выска-зывания не изменился. Но это модифицированное высказывание можно записать как имплика-цию P ® Q при выше определённых P и Q ■

Пример 16. Представим высказывание «Все мужчины созданы равными. Все люди, соз-данные равными, являются женщинами. Поэтому все мужчины являются женщинами» в формальном виде.

Это высказывание по структуре напоминает высказывания из примеров 5 и 10. Действи-тельно, данное высказывание, как и высказывания из примеров 5 и 10, является импликацией. Её посылка такова: «Все мужчины созданы равными. Все люди, созданные равными, явля-ются женщинами»; её заключение таково: «Все мужчины являются женщинами».

Посылка представлена в примере 14 формулой (P ® R) Ù (R ® Q). Заключение представлено в примере 15 формулой P ® Q. Таким образом, исходное высказывание можно записать в виде

(P ® R) Ù (R ® Q))®(P ® Q). (5)

Ясно, что заключение «Все мужчины являются женщинами» является ложным выска-зыванием. Но здесь следует ещё раз подчеркнуть, что операции над высказываниями и их формальные представления осуществляются независимо от истинности или ложности участву-ющих в этих операциях простых высказываний ■

Более подробно методы формального анализа высказываний на основе сопоставляемых их формальных выражений рассматренного в примерах 3 – 16 вида демонстрируются а разделе 5-3, сразу после введения в рассмотрение булевых функций и связанных с ними понятий

Задания

Задание 1. Указать, какие из следующих предложений являются высказываниями. Для высказываний установить значение истинности.

01. 7-го декабря 1941 года было воскресенье.

02. Слушайте, мои дети, и вы узнаете о ночной скачке Пола Ривера.

03. 5+8=13 и4-3=1

04. Некоторые числа отрицательны.

05. Куда Вы идёте сегодня вечером?

06. Эндрю Джексон был президентом Соединённых Штатов в 1867 году.

07. Один галлон молока весит больше 4 фунтов.

08. У меня есть пистолет «Смит и Вессон» ■

 

Задание 2. Пусть P и Q – высказывания из примера 6. Представить следующие составные высказывания в формальном виде.

01. Крис собирает видеофильмы или Джек играет на трубе.

02. Крис не собирает видеофильмы или Джек не играет на трубе.

03. Крис не собирает видеофильмы и Джек играет на трубе.

04. Ни Крис не собирает видеофильмы, ни Джек не играет на трубе.

05. Либо Крис собирает видеофильмы, либо Джек играет на трубе.

06. Если Джек не играет на трубе, то Крис собирает видеофильмы.

07. Крис собирает видеофильмы, если и только если Джек не играет на трубе.

08. Крис собирает видеофильмы, потому что Джек не играет на трубе.

09. Если Джек не играет на трубе, то Крис собирает видеофильмы, и Джек играет на трубе.

10. Если Джек не играет на трубе, то Крис собирает видеофильмы, или, если Крис собира-ет видеофильмы, то Джек играет на трубе ■

 

Задание 3. Представить заданные высказывания в формальном виде. См. примеры 3 – 16 для образца.

01а. Если Эдди едет в город, то Мейбл останется дома.

01б. Если Мейбл не останется дома, то Рита будет готовить.

02. «Мужчина состоит из мужа и чина» (Чехов).

03а. Я покупаю машину или я уезжаю на каникулы.

03б. Я не покупаю машину.

03в. Я уезжаю на каникулы.

04а. Если бы человек мог быть в двух местах одновременно, я был бы с Вами.

04б. Я не был с Вами.

04в. Человек не может быть в двух местах одновременно.

05а. «Если мы будем следовать по стопам Ньютона, то это не будет прогрессом» (Алдос Хаксли).

05б. Мы не следуем по стопам Ньютона.

06а. Джефф любит играть в гольф.

06б. Если Джоан любит шить, то Джефф не любит играть в гольф.

6в. Если Джоан не любит шить, то Брэд поёт в хоре.

07а. Если дерево заражено сосновым короедом, то оно умрёт.

07б. Люди сажают деревья в День Дерева, и оно не умрёт.

07в. Если люди сажают деревья в День Дерева, то оно не заражено сосновым короедом.

08а. Если я напишу чек, он не будет принят.

08б. Если банк гарантирует его, он будет принят.

09а. Кристина Алигера поёт или Рики Мартин – не подростковый идол.

09б. Если Рики Мартин – не подростковый идол, то Бритни Спирс не выиграет Американ-ский Музыкальный Приз.

09в. Бритни Спирс выиграла Американский Музыкальный Приз.

10а. Если я чувствую Вас всей кожей, то Вы глубоко в моём сердце.

10б. Если Вы глубоко в моём сердце, то Вы – не часть меня.

10в. Вы глубоко в моём сердце или Вы часть меня.

11а. Если Отис – диск-жокей, то он живёт в Лексингтоне.

11б. Он живёт в Лексингтоне и он сдвинут на истории.

12. Если Канада – союзник Соединённых Штатов, то Соединённые Штаты относятся к Ка-наде дружески.

13а. Если Вы спите во время утренних занятий по математике, то Вы хорошо отдохнёте.

13б. Если Вы хорошо отдохнёте, то Вы хорошо сдадите тест по математике.

14а. Мы сбалансируем бюджет или уменьшим налоги,

14б. Если мы сбалансируем бюджет или уменьшим налоги, то будет больше денег для борьбы с загрязнением.

14в. Если мы не сбалансируем бюджет, то мы не уменьшим налоги.

15а. Если у товара низкая цена, то у него нет качества.

15б. Если у товара нет низкой цены или нет качества, то он ненадёжен.

16а. Если тест отрицателен, то Вы не нуждаетесь в лечении.

16б. Если тест положителен, то Вы нуждаетесь в лекарствах.

17а. Если Дэйв одинок сегодня вечером, то он не пойдёт в гости.

17б. Если Дэйв не одинок сегодня вечером или он не пойдёт в гости, то он будет писать свою курсовую работу ■

 

Предметный указатель

 

Высказывание,

простое

составное

тождественно истинное

Высказывания,

значение истинностное

логическое

Дизъюнкция

Дизъюнкция разделительная

Импликация

Импликации,

антецедент

заключение

консеквент

посылка

Истина

Истинности таблица

Конъюнкция

Ложь

Логические союзы

частицы

Отрицание

Эквивалентность

Глава 2. Множества

1. Множества и подмножества

2. Диаграммы Венна и операции над множествами

3. Алгоритмы выполнения теоретико-множественных операций

4. Проверка равенства двух множеств

5. Задания

6. Предметный указатель

 

Множества и подмножества

Понятие множества (как и уже рассмотренное понятие высказывания) является для нас ис-ходным, неопределяемым. Можно говорить о множестве студентов в данной аудитории, мно-жестве книг в библиотеке и т.д. Множество составлено из элементов, способных обладать неко-торыми свойствами и находиться между собой и с элементами других множеств в неких отно-шениях. Важно, что элементы множества являются различными и (хотя бы в принципе) разли-чимыми. Мы будем обозначать сами множества прописными, а их элементы – строчными бук-вами латинского алфавита. Высказывание «х есть элемент множества X» символически записы-вают так: х Î X. Эта связь между элементом и множеством называется принадлежностью. От-рицание этого высказывания записывают так: х Ï X. Множества X и Y называют равными, если они состоят из одних и тех же элементов. Высказывание о равенстве множеств X и Y записыва-ют в виде: X = Y, а отрицание этого высказывания (т.е. высказывание, состоящее в том, что мно-жества X и Y не равны) – в виде X ≠ Y.

Для удобства вводят так называемое пустое множество, т.е. множество, не содержащее элементов. Его изображают символом Æ. Таким образом, если х – некоторый элемент (объект), то принадлежность х ÎÆ – всегда ложное высказывание. Наряду с пустым множеством полезно ввести в рассмотрение и так называемое универсальное множество. Это множество состоит из всех элементов, имеющих отношение к определённой рассматриваемой ситуации. Например, при анализе успеваемости (или проведении социологического опроса) студентов в качестве универсального выступает множество всех студентов данного института или города; в экономи-ческом исследовании в качестве универсального часто выступает множество всех фирм данной страны или группы стран, и т.д. Универсальное множество обычно обозначается буквой U. За-метим, что при переходе от одной ситуации к другой универсальное множество (в отличие от пустого множества) может измениться.

Может случиться так, что все элементы множества X являются одновременно элементами множества Y, т,е.

х Î X ® х Î Y. (1)

В этом случае говорят, что X есть подмножество, или часть Y, что записывается так:

X Í Y. (2)

Из (1) и (2) получаем, что X Í Y тогда и только тогда, когда истинна импликация х Î X ® х Î Y. Из определения операции эквивалентности следует, что (X = Y) (X Í Y)Ù(Y Í X). Отрица-ние высказывания (2) записывается как X Ë Y. X Ì Y означает, что (X Í Y)Ù(X ≠ Y).

Множество может быть задано перечислением своих элементов, получением элементов множества из уже полученных элементов либо из других объектов (порождающей процедурой) или описанием свойств, которыми должны обладать его элементы (разрешающей процедурой). В настоящей главе будут рассматриваться только конечные множества. Конечное множество можно задать (хотя бы в принципе) списком, в котором и перечисляются все его элементы. Список заключается в фигурные скобки, а сами элементы отделяются друг от друга запятыми. Задание множества разрешающей процедурой рассматривается далее, в разделе 4-2.1, порожда-ющей процедурой – в разделе 5.2.

Пример 1. Множество имён летних месяцев: {июнь, июль, август} ■

Пример 2. В описаниях «больших» конечных множеств используются многоточия. Мно-жество неотрицательных целых чисел, не превосходящих 50, записывают как {0, 1, …, 50}. За-метим, что почёркнутые в предыдущей фразе слова как раз описывают свойство всех элементов данного множества, выделяющее их из всех остальных объектов. Такие свойства называются характеристическими ■

Пример 3. Многоточия можно использовать только в тех случаях, когда не возникает дву-смысленности. Если A = {3, 5, 7, …, 19}, то неясно, является ли A множеством нечётных чисел, лежащих в интервале от 3 до 19, или это множество простых чисел из того же интервала, т.е. возможны разные «расшифровки» неопределённости, скрывающейся за многоточием ■

Обратим внимание на следующее. Элемент a надо отличать от одноэлементного множест-ва { a }: это объекты разной природы. Нельзя написать, что a ={ a } или a Í{ a }. Но можно на-писать истинное высказывание a Î{ a }. Элементами множеств могут быть другие множества. Множество, элементами которого служат все подмножества множества X, обозначается симво-лом B (Х). Его называют булеаном множесгва X.

Пример 4. Вставить знак , , Î или Ï вместо пробела, чтобы получить истинное выс-казывание:

(a) {3, 4, 5, 6} _______ {3, 4, 5, 6, 8}.

Поскольку каждый элемент множества {3, 4, 5, 6} принадлежит и множеству {3, 4, 5, 6, 8}, то 1-ое множество является подмножеством 2-го, так что надо вставить Í.

(b) 1 _______ {2, 4, 6, 8}.

Элемент 1не принадлежит множеству {2, 4, 6, 8}. Поэтому между ними надо вставить Ï■