Pages: | 1 |

| 3 | 4 | ... | 6 |

«С. В. Мациевский ВЫСШАЯ МАТЕМАТИКА ДЛЯ ГУМАНИТАРИЕВ Учебное пособие Издательство Российского государственного университета им. И. Канта 2010 УДК 51(075) ББК 22.11я73 М 367 Рецензенты: доцент кафедры высшей математики ...»

-- [ Страница 2 ] --

2. При бросании 3 костей сумма всех вероятностей из таблицы распределения, другими словами, сумма его статистического ряда также равна 1:

3. График функция распределения для числа очков при бросании костей также имеет колоколообразный вид (см. рис. 10 и 11).

§ 4. Случайная величина 1°. Определение математического ожидания Хотя редукция к случайной величине позволяет при каждом опыте регистрировать 1 число, но при многократных испытаниях все равно получается много чисел.

Однако существует удобный метод, который позволяет и в этом случае охарактеризовать все многочисленные испытания только 1 числом! Это единственный экспериментальный параметр, конечно, является некоторым средним.

Примеры.

1. При подкидывании 2 монет найдем среднее следующим образом: умножим каждое значение случайной величины на ее вероятность, а затем полученные произведения сложим.

Получим среднее, которое обозначим M:

2. При подкидывании 3 монет найдем такое же среднее:

3. Теперь при подкидывании 4 монет:

Теперь можно сформулировать понятие математического ожидания.

Математическое ожидание.

Число, равное сумме произведений каждого значения случайной величины на ее вероятность, называется средним значением, или математическим ожиданием, случайной величины. Обозначение: M.

Это действительно среднее.

Действительно, вероятность выпадения орла равна 1, и матожидание для 2 монет равно далее. Эти математические ожидания отмечены на рисунках 2, 4 и 6.

Снова напомним, что в приложениях результаты эксперимента очень удобно представлять одним числом — матожиданием измеряемой случайной величины.

Если отметить матожидание на графиках функции распределения, то в случае равновероятных исходов, например, бросании монет или игральных костей, получим место оси симметрии функции распределения (значение матожидания отмечено треугольником на рисунках 2, 4 и 6).

Приведем пример, как на практике, в конкретной бизнес-ситуации, используется матожидание.

Задача.

По данным статистики в США вероятность 25-летнему человеку прожить 1 год составляет 0,992. Страховая компания страхует жизнь такого человека на год на сумму 1000, страховой взнос составляет всего 10.

Какую прибыль ожидает получить компания?

Решение. Ясно, что величина прибыли, которую нужно оценить в среднем, является случайной величиной. Причем она имеет два значения: +10, если застрахованный не умрет, и 990, если умрет.

Вероятность первого исхода равна, по условию, 0,992. Кроме этого случая, возможен еще только противоположный случай, вероятность которого в сумме с первой вероятностью равна 1. Поэтому вероятность второго исхода равна 0,008. Получаем следующее распределение нашей случайной величины:

Теперь можно легко посчитать ожидаемую прибыль, равную матожиданию прибыли. Получаем 2:

Разберем примеры из другой серии.

Примеры.

1. При бросании 2 костей найдем среднее следующим образом: умножим каждое значение случайной величины на ее вероятность, а затем полученные произведения сложим.

Получим среднее, которое обозначим M:

2. При бросании 3 костей найдем такое же среднее:

§ 4. Случайная величина Для вычисления числителей вероятностей случайных величин можно воспользоваться треугольником Паскаля, который изображен на рисунке 8.

Треугольник Паскаля.

Треугольник Паскаля начинается с двух единиц.

Крайние числа треугольника Паскаля равны 1.

Внутренние числа треугольника Паскаля равны сумме ближайших двух чисел сверху и сверху слева из предыдущего ряда.

n-й ряд треугольника Паскаля состоит из нужных числителей для вероятностей количества выпадения m орлов для n монет, а знаменатели равны 2n.

Продуктивно рассматривать не одно событие или случайную величину, а много. Случайные величины возникают в приложениях как результаты измерений, причем либо сами измерения подвержены случайным ошибкам, либо объекты измерения выбираются случайным образом.

Закон больших чисел.

Тем не менее справедливо следующее правило:

даже когда результаты отдельных измерений сильно колеблются, Это явление устойчивости средних и отражает закон больших чисел.

Пример.

В литературе можно найти сведения, что при подкидывании монеты герб выпадал следующие количества раз:

1) в десяти сериях по 1000 подкидываний (бросал один заключенный) — 502, 511, 497, 529, 504, 476, 507, 528, 504, 529;

2) в серии 24 000 раз (бросал Пирсон) — 12 012;

3) в серии 4040 раз (бросал Бюффон) — 2048.

Следовательно, частоты выпадений герба группируются около 0,5, хотя и не равны никогда этому числу.

1.1. Какие значения принимает случайная величина — количество орлов при подкидывании 5 монет?

1.2. Какие значения принимает случайная величина — количество очков при подкидывании 2 костей?

1.3. Какие значения принимает случайная величина — количество орлов при подкидывании 3 монет?

1.4. Какие значения принимает случайная величина — количество орлов при подкидывании 4 монет?

1.5. Какие значения принимает случайная величина — количество орлов при подкидывании 2 монет?

2.1. Сколько случаев выпадения 2 орлов при подкидывании 4 монет?

2.2. Сколько случаев выпадения 10 очков при подкидывании 3 костей?

2.3. Сколько случаев выпадения 3 орлов при подкидывании 4 монет?

2.4. Сколько случаев выпадения 2 орлов при подкидывании 3 монет?

2.5. Сколько случаев выпадения 7 очков при подкидывании 2 костей?

§ 4. Случайная величина 3.1. Чему равно математическое ожидание количества орлов при подкидывании монет?

3.2. Чему равно математическое ожидание количества очков при подкидывании костей?

3.3. Чему равно математическое ожидание количества орлов при подкидывании монет?

3.4. Чему равно математическое ожидание количества орлов при подкидывании монет?

3.5. Чему равно математическое ожидание количества очков при подкидывании костей?

4.1. Чему равно в треугольнике Паскаля 2-е число в 10-й строке?

4.2. Чему равно в треугольнике Паскаля 3-е число в 5-й строке?

4.3. Чему равно в треугольнике Паскаля 3-е число в 6-й строке?

4.4. Чему равно в треугольнике Паскаля 3-е число в 10-й строке?

4.5. Чему равно в треугольнике Паскаля 4-е число в 6-й строке?

1. Пусть n — номер варианта от 1 до 8. Построить распределение, нарисовать график функции распределения и найти математическое ожидание для числа орлов на n + 4 монетах.

2. Пусть n — номер варианта от 9 до 16. Построить распределение, нарисовать график функции распределения и найти математическое ожидание для числа орлов на n 4 монетах.

Теория множеств и математическая логика 70 Глава 2. Теория множеств и математическая логика § 5. Множества и подмножества 1°. Множество. Множество как элемент другого множества.................

2. Множества, составленные из других множеств..............................

Акимов О. Е. Дискретная математика: логика, группы, графы.— М.: Лаборатория Базовых Знаний, 2003.

Курант Р., Роббинс Г. Что такое математика? Элементарный очерк идей и методов / Пер. с англ. под ред. А. Н. Колмогорова.— Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

Болтянский В. Г., Савин А. П. Беседы о математике. Книга 1. Дискретные объекты.— М.: ФИМА, МЦНМО, 2002.

Гарднер М. Математические новеллы: 2-е изд., испр. и доп. / Пер. с англ.— М.: Мир, 2000.

Множество, n-элементное, пустое, конечное и бесконечное множество, подмножество, надмножество, универсальное множество, диаграмма Эйлера — Венна, полная диаграммы Эйлера — Венна, булеан, решетка, упорядоченная пара, декартово произведение, парадоксы парикмахера, определения натуральных чисел, Рассела, рефлексивности, Деда Мороза, Тристрама Шенди.

§ 5. Множества и подмножества 1°. Множество. Множество как элемент другого множества Основные, базовые математические понятия лежат в основе всех других определений и потому определению не поддаются. Тем не менее определим или, точнее, опишем понятие множества.

Множество.

Множество — набор любых объектов. Объекты, входящие в множество, называются его элементами и образуют состав множества.

Ни повторяемость, ни порядок элементов не влияет на состав множества.

Кроме того, множество — это один объект!

Множества обозначают прописными латинскими буквами A, …, Z, а их абстрактные элементы — строчными латинскими буквами a, …, z. Множества задают с помощью перечисления их элементов в фигурных скобках: {…}.

Для обозначения принадлежности элемента множеству используется значок, для обозначения не принадлежности — значок.

Примеры.

Запишем три множества по три элемента:

Множество A состоит из трех слов-элементов улица, фонарь и аптека.

Множество B состоит из трех букв-элементов a, b и c.

Множество C состоит из трех чисел-элементов 1, 2 и 3.

Обозначим принадлежность элементов нашим трем множествам:

Рассмотрим интересное понятие количества элементов множества.

n-элементное, пустое, конечное и бесконечное множеств о.

Множество, состоящее только из одного элемента, называется одноэлементным, из двух элементов — двухэлементным, из трех — трехэлементным и так далее. Множество, состоящее из n элементов, называется n-элементным.

Множество, совсем не имеющее никаких элементов, называется нульэлементным, или пустым, и имеет специальное обозначение: {}.

Множество называется конечным, если оно содержит конечное количество элементов, и бесконечным, если содержит бесконечное количество элементов.

Примеры.

Запишем три новых множества:

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

Обратит внимание, что множества и {} — разные. Множество — пустое и не содержит никаких элементов, а множество {} — одноэлементное и содержит один элемент — другое множество.

Поэтому множество D состоит из одного элемента — пустого множества.

Множество E содержит два элемента: множества {a, b} и {a, b, c}.

Множество F содержит тоже два элемента: множества и {a}.

В заключении приведем серию множеств, отличающихся друг от друга:

Первое множество в серии не содержит элементов, второе имеет один элемент — пустое множество, единственный элемент третьего — множество, которое содержит пустое множество, четвертого — множество, которое содержит множество, которое содержит пустое множество, и так далее.

Фигурные скобки — это не круглые. Двойные фигурные скобки нельзя заменить на одинарные, как это можно сделать с круглыми.

Теперь, основываясь на понятии множества, определим подмножество.

Подмножество. Надмножество.

Подмножество некоторого данного множества — это любое множество, состоящее из произвольного количества элементов данного множества. Данное множество по отношению к своим подмножествам называется надмножеством.

Для обозначения включения подмножества в множество используется значок, для обозначения не включения — значок.

Пример.

Рассмотрим множество U, состоящее из двенадцати студентов, пронумерованных числами от 1 до 12: U = {1, 2, …, 12}.

Предположим, что студенты с номерами 1, 2, 3 и 4 не достигли 18 лет, а студенты 1, 5 и 6 являются отличниками.

Обозначим множество студентов, не достигших 18 лет, буквой A, а отличников — буквой B. Тогда A = {1, 2, 3, 4}, B = {1, 5, 6}.

Итак, множество U включает два подмножества: A и B, а множества A и B, в свою очередь, включены в множество U. Обозначение: A U, B U.

Множество U по отношению к множествам A и B называется универсальным, поскольку элементы для A и B берутся только из U.

§ 5. Множества и подмножества Отметим, что, по определению, любое подмножество — это тоже какое-то множество.

Универсальное множество.

Универсальное множество — это множество, которое включает все остальные рассматриваемые множества. Обозначение: U.

Пример.

Присмотримся к полученной в последнем примере конструкции: множеству U и двум его подмножествам A и B. Очевидно, что имеются еще четыре готовых подмножества универсального множества U:

1) C0 = {7, 8, 9, 10, 11, 12} — студенты, которые не обладают ни одним из названных свойств;

2) C1 = {2, 3, 4} — студенты, которые обладают только свойством A;

3) C2 = {5, 6} — студенты, которые обладают только свойством B;

4) C3 = {1} — студенты, которые обладают сразу обоими свойством A и B.

Эти множества — подмножества не только универсального множества U, но и подмножества его подмножеств A и B. Выпишем цепочки принадлежности множеств друг другу:

Диаграмма Эйлера — Венна.

Диаграмма Эйлера — Венна — это графическое изображение множеств в виде плоских пересекающихся фигур.

Пример.

Изобразим все наши множества U, A, B, C0, C1, C2 и C3 графически на диаграмме Эйлера — Венна, где универсальное множество U представлено в виде прямоугольника, а множества A и B — в виде пересекающихся кругов (см.

рис. 1).

На рисунке 1 в качестве примера показано то, что называется полной диаграммой Эйлера — Венна. На этой диаграмме универсальное множество разбито двумя множествами на 4 части.

Полная диаграмма Эйлера — Венна Полная диаграмма Эйлера — Венна — диаграмма Эйлера — Венна, на которой показаны все возможные случаи пересечения множеств.

Говорят, что полная диаграмма Эйлера — Венна имеет всю полноту общности, поскольку на ней представлены элементы, принадлежащие всем возможным случаям пересечения множеств. Неполная же диаграмма Эйлера — Венна не представляет всей полноты общности.

Примеры.

1. Пусть множество A = {1, 5} B = {1, 2, 3, 4, 5} U = {1, 2, …, 12}, как показано на рисунке 2. Говорят, что это не общий, а частный случай взаимного расположения множеств A и B: множество A включено в множество B. Здесь универсальное множество двумя разными подмножествами разбито на 3 части.

2. Пусть A = {1, 5} и B = {2, 3, 4} не имеют общих элементов, A U, B U, U = {1, 2, …, 12}. И в этом частном случае взаимного расположения различных множеств A и B они разбивают универсальное множество на 3 части.

§ 5. Множества и подмножества 2. Множества, составленные из других множеств Подмножество. Надмножество.

Итак, подмножество — это множество, все элементы которого принадлежат также другому множеству — надмножеству.

Конечно, в надмножестве могут быть элементы, которых нет в подмножестве.

В математике считается по определению, что пустое множество является подмножеством любого множества A: A.

Интересные конструкции получаются в том случае, если выписать все возможные разные подмножества какого-нибудь множества.

Булеан.

Булеан — это множество, составленное из всех подмножеств некоторого множества.

Другими словами, булеан — это множество всех подмножеств некоторого множества.

Обозначение булеана множества A: (A).

Примеры.

1. Рассмотрим следующий простейший абстрактный пример. Выпишем булеан, то есть множество всех подмножества, одноэлементного множества A = {a}, которое имеет всего два подмножества:

2. Выпишем булеан, то есть все подмножества двухэлементного множества B = {a, b}, их всего четыре:

3. Выпишем булеан, то есть все подмножества трехэлементного множества C = {a, b, c}, их всего восемь:

Теперь можно сформулировать теорему, доказательство которой слишком просто, чтобы его здесь приводить.

Т е о р е м а 4. Множество из n элементами имеет 2n подмножеств.

Все подмножества конечного множества, то есть булеан, удобно рисовать в виде решетки.

Решетка.

Решетка — диаграмма, на которой линией соединены подмножества, отличающиеся ровно на один элемент, причем подмножества с одинаковым количеством элементов располагаются на одном уровне.

Примеры.

1. Сначала на рисунке 5 нарисуем решетку булеана одноэлементного множества {a}: {a}.

2-элементное множество: {a} 0-элементное множество:

Рис. 5. Решетка булеана одноэлементного множества {a} 2. Теперь на рисунке 6 изобразим решетку булеана двухэлементного множества {a, b}:

{a} {a, b}, {b} {a, b}.

2-элементное множество:

Рис. 6. Решетка булеана двухэлементного множества {a, b} 3. Наконец, на рисунке 7 представим решетку булеана трехэлементного множества {a, b, c} {a} {a, b}, {a} {a, c}, {b} {a, b}, {b} {b, c}, {c} {a, c}, {c} {b, c};

{a, b} {a, b, c}, {a, c} {a, b, c}, {b, c} {a, b, c}.

3-элементное множество:

2-элементные множества:

0-элементное множество:

Рис. 7. Решетка булеана трехэлементного множества {a, b, c} § 5. Множества и подмножества 3°. Декартово произведение множеств Перед определением декартового произведения необходимо ввести понятие упорядоченной пары элементов двух множеств: первый член пары — это элемент одного множества, второй — другого.

Упорядоченная пара.

Пара объектов (a, b) называется упорядоченной, если положение объектов в паре фиксировано, их нельзя менять местами.

Обратите внимание, что пары (a, b) и (b, a) — разные.

Декартово произведение.

Декартовым, или прямым, произведением множеств A и B называется множество всех упорядоченных пар элементов A и B:

Примеры.

1. Найдем {a, b} {c, d, e}: {(a, c), (a, d), (a, e), (b, c), (b, d), (b, e)}.

Изобразим это декартово произведение графически:

Рис. 8. Декартово, или прямое, произведение множеств Таким образом, элементами декартового произведения двух множеств являются пары элементов исходных множеств. Причем упорядочены элементы в парах, а не сами пары!

2. Система прямоугольных координат — это декартово произведение множества действительных чисел на себя: (рис. 9).

Не делается никаких априорных предположений ни о природе элементов множества, ни о способе их включения во множество. Предметом теории множеств является изучение таких свойств множеств, которые не зависят от природы составляющих их элементов.

Именно поэтому с заданием множества следует быть осторожным. Например, множество всех молекул жидкости, налитой в стакан, не является точно определенным вследствие процессов испарения и конденсации.

Парадоксы конечных множеств показывают, что иногда «задание» множества, кажущееся четким, может оказаться некорректным.

1. Парадокс парикмахера.

В одном взводе был взводный парикмахер (парикмахеры в армии раньше назывались брадобреями). Командир приказал ему (видимо, взвод был большой и брадобрей не справлялся) брить тех и только тех солдат, которые не бреются сами.

Принадлежит ли этому множеству сам парикмахер?

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

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

Получающийся парадокс показывает, что это множество не определено корректно.

2. Парадокс определения натуральных чисел.

Зададим множество всех натуральных чисел, которые можно определить при помощи не более двадцати слов русского языка. Это множество конечно потому, что множество всех слов русского языка конечно.

Рассмотрим сумму всех натуральных чисел, каждое из которых определяется не более чем двадцатью словами русского языка.

Вопрос: принадлежит ли число, заданное этой суммой, нашему множеству?

Эта сумма — число, описанное не более чем двадцатью словами русского языка, поэтому оно должно принадлежать нашему множеству, то есть совпадать с одним из его чисел.

Но это невозможно, так как эта сумма больше каждого из слагаемых — больше каждого элемента нашего множества.

3. Парадокс Рассела.

Обычно множества, с которыми приходится иметь дело, и все далее рассматриваемые множества в этой книге, не содержат себя в качестве элемента.

Вот и рассмотрим множество, состоящее их всех тех множеств, которые не содержат самое себя в качестве своего элемента.

§ 5. Множества и подмножества Но возникает следующий вопрос: содержит ли это множество себя в качестве элемента?

Если это множество содержит себя в качестве элемента, то это противоречит определению этого множества.

А если это множество не содержит себя, то получается снова противоречие:

тогда это множество по определению должно быть своим элементом.

4. Парадокс рефлексивности.

Прилагательное русского языка назовем рефлексивным, если оно обладает свойством, которое определяет.

Например, прилагательное «русский» — рефлексивное, а прилагательное «английский» — нерефлексивное, прилагательное «трехсложный» — рефлексивное (это слово состоит из трех слогов), а прилагательное «четырехсложный»—нерефлексивное (состоит из пяти слогов).

Зададим множество всех рефлексивных прилагательных.

Рассмотрим прилагательное «нерефлексивный». Оно рефлексивное или нет?

Если оно рефлексивно, следовательно, оно нерефлексивно по своему значению.

Если же оно нерефлексивно, значит, оно обладает свойством, которое определяет, то есть рефлексивно.

Эти парадоксы говорят о том, что нельзя создавать множества произвольными словосочетаниями.

Эти парадоксы возникают по той причине, что в них на одном уровне размещены предметы с разных структурных уровней, которые по отношению друг к другу являются объектом и субъектом.

Самый простой способ избежать подобных некорректных обращений с объектами и субъектами — рассматривать используемые множества только как подмножества одного всеобъемлющего конкретно заданного универсального множества.

2°. Парадоксы бесконечных множеств Следующие парадоксы демонстрируют нарушение принципа «часть меньше целого» для бесконечных множеств. Нарушение этого принципа может быть использовано для определения бесконечных множеств и для того, чтобы отличать бесконечные множества от конечных.

1. Парадокс Деда Мороза.

На Новый год к детишкам пришел математический Дед Мороз с мешком конфет. Конфет в мешке бесконечно много, и они занумерованы натуральными числами. На каждой конфете написан ее номер, и для каждого натурального числа есть ровно одна конфета с этим номером.

За одну минуту до полночи Дед Мороз взял конфету № 1 и подарил детям. Через полминуты он дал детям конфеты № 2 и № 3 (наверно, подумал, что мало дал), но при этом конфету №1 забрал (видимо, дети не успели ее съесть). Еще через четверть минуты он дал детям конфеты № 4, № 5, № 6 и № 7, но забрал конфеты № 2 и № 3. И так далее: щедрый Дед Мороз каждый раз дает вдвое больше конфет, чем на предыдущем шаге.

При этом количество конфет у детей стремительно возрастает (но начинает закрадываться подозрение…).

Вопрос: сколько конфет будет у детей в полночь?

Давайте разбираться последовательно.

У кого будет в полночь первая конфета? У Деда Мороза.

А вторая конфета? У Деда Мороза: он забрал ее себе за четверть минуты до полночи.

У кого будет n-я конфета? Хитрый математический Дед Мороз ее тоже забрал.

Итак, каждая конкретная конфета в полночь окажется у Деда Мороза. Что же получается? После каждого шага у детей становится в два раза больше конфет, а в полночь происходит катастрофа!

2. Парадокс Тристрама Шенди.

В романе Стерна «Жизнь и мнения Тристрама Шенди, джентльмена» герой обнаруживает, что ему потребовался целый год, чтобы изложить события первого дня его жизни, и еще один год понадобился, чтобы описать второй день. В связи с этим герой сетует, что материал его биографии будет накапливаться быстрее, чем он сможет его обработать, и он никогда не сможет ее завершить.

«Теперь я утверждаю,— возражает на это математик Рассел,— что если бы он жил вечно и его работа не стала бы ему в тягость, даже если бы его жизнь продолжала быть столь же богатой событиями, как вначале, то ни одна из частей его биографии не осталась бы ненаписанной».

Действительно, события n-го дня Шенди мог бы описать за n-й год и, таким образом, в его автобиографии каждый день оказался бы запечатленным.

Иначе говоря, если бы жизнь длилась бесконечно, то она насчитывала бы столько же лет, сколько дней.

На самом деле парадоксов тут никаких нет. Все дело в том, что бесконечные множества устроены существенно сложнее конечных, и интуиция тут не всегда срабатывает правильно.

§ 5. Множества и подмножества 1. Множество. Множество как элемент другого множества 1.1. Сколько элементов содержит множество A = {{1, 2}, {3, 4}}?

1.2. Сколько элементов содержит множество A = {{1, 2}, 3, 4}?

1.3. Сколько элементов содержит множество A = {1, 2, 3, 4}?

1.4. Сколько элементов содержит множество A = {}?

1.5. Сколько элементов содержит множество A = {{}}?

2.1. Какие отношения сравнения верны, если A = {1, 2, 3} и B = {2, 3, 4}?

2.2. Какие отношения сравнения верны, если A = {1, 2, 3} и B = {4, 5, 6}?

2.3. Какие отношения сравнения верны, если A = {3, 2, 3} и B = {2, 3, 4}?

2.4. Какие отношения сравнения верны, если A = {3, 2, 3} и B = {3, 2, 3}?

2.5. Какие отношения сравнения верны, если A = {3, 2, 3} и B = {2, 2, 2}?

3.1. Сколько частей на полной диаграмме с 2 множествами?

3.2. Сколько частей на полной диаграмме с 3 множествами?

3.3. Сколько частей на полной диаграмме с 4 множествами?

3.4. Сколько частей на полной диаграмме с 1 множеством?

3.5. Сколько частей на неполной диаграмме с 2 разными множествами?

1) Сколько элементов содержит булеан ({, {a}, {b}, {a, b}})?

2) Сколько элементов содержит булеан ()?

3) Сколько элементов содержит булеан ({, {a}})?

4) Сколько элементов содержит булеан ({, {}})?

5) Сколько элементов содержит булеан ({})?

1.1. Сколько множеств участвует в прямом произведении?

1.2. Сколько элементов содержит прямое произведение, если множества, участвующие в произведении, имеют 2 и 3 предмета?

1.3. Какой пары нет в прямом произведении (1, 0)(2, 1, 0)?

1.4. Какая пара есть в прямом произведении (2, 1)(4, 3, 2)?

1.5. Какая пара является координатами какой-нибудь точки на координатной плоскости на прямой y = x (биссектриса первого квадранта)?

Пусть n — номер варианта от 1 до 16.

1. Выпишите все 16 подмножеств 4-элементного булеана множества и нарисуйте решетку из этих 16 подмножеств.

2. Нарисуйте в виде таблицы, как на рисунке 8, декартово произведение двух множеств 1. Основные операции на множествах. Логические переменные................ 2°. Логические переменные. Таблица истинности.......................... 2*. Другие операции на множествах и логические связки...................... 2°. Операция симметрической разности множеств......................... 3. Некоторые законы теоретико-множественных и логических операций....... Акимов О. Е. Дискретная математика: логика, группы, графы.— М.: Лаборатория Базовых Знаний, 2003.

Карпов Ю. Г. Теория автоматов.— СПб.: Питер, 2002.

Гарднер М. Математические новеллы: 2-е изд., испр. и доп. / Пер. с англ.— М.: Мир, 2000.

Объединение, пересечение, разность, симметрическая разность, эквивалентность и импликация множеств, логическая связка, логическая связка «или», «и», «не», «исключающее или», «тогда и только тогда», «если…, то», дизъюнкция, логическая переменная, логическое значение, логическая операция, таблица истинности, конъюнкция, дополнение множества, отрицание, разность, эквивалентность, импликация, законы идемпотентности, коммутативности, ассоциативности, дистрибутивности, нуля и единицы, де Моргана, обобщенные де Моргана.

§ 6. Операции на множествах, логические связки 1. Основные операции на множествах. Логические переменные 1°. Операция объединения множеств Операции на множествах начнем изучать с помощью универсального множества U = {1, 2, …, 12}.

где — символ объединения множеств. Рис. 1. Объединение множеств A B Таким образом, объединением охватываются три множества C1, C2 и C3, которые на диаграмме (рис. 1) закрашены.

Сформулируем определение объединения множеств для общего абстрактного случая.

Объединение множеств.

Объединение множеств содержит элементы обоих множеств, причем общие элементы входят по одному разу.

Обозначение объединения множеств A и B: A B.

Рассмотрим объединение множеств с логической точки зрения.

Логическая связка «или». Дизъюнкция.

Логически операция объединения двух множеств характеризуется так:

элемент принадлежит 1-му множеству или 2-му множеству.

То, что x принадлежит A или B или им обоим, выражается формулой где — символ нашей логической операции, которая называется логической связкой «или», которая также называется дизъюнкцией.

Обратите внимание, что логическая связка «или» относится именно к свойствам какого-то объекта x: объект x обладает свойствами A или B.

2°. Логические переменные. Таблица истинности С точки зрения логики вместо одной предметной переменной x, принимающей значения 1, 2, …, 12 на универсуме U, удобно для элементов множеств A и B ввести две логические переменные a и b.

Логическая переменная. Логическое значение.

Областью определения логической переменной являются два логических значения: 1 для истины и 0 для лжи.

Примеры.

Элементы множества C0 не принадлежат ни множеству A, ни множеству B, поэтому логические значения для элементов множества C0 будут a = 0 и b = 0.

Элементы C1 принадлежат A и не принадлежат B, поэтому a = 1 и b = 0.

Элементы C2 не принадлежат A и принадлежат B, для них a = 0 и b = 1.

Элементы C3 принадлежат как A, так и B, для них a = 1 и b = 1.

Теперь объединение множеств можно рассматривать как логическую операцию, или логическую функцию, от двух логических аргументов.

Логическая операция.

Логическая операция, или логическая функция, она же логическая связка,— это функция логических переменных, значением которой является логическое значение.

Логическая функция — это самая простая функция. Логические функции удобно задавать в обычном табличном виде значения аргументов — значение функции.

Учитывая, что объединение множеств A B состоит из трех множеств C1, C2 и C3, запишем операцию объединения множеств в табличном виде (см.

табл. 2).

Таблица истинности.

Табличный вид логической функции называется таблицей истинности.

Итак, дизъюнкция — это логическая функция от двух аргументов.

Эту таблицу очень легко запомнить: дизъюнкция равна 0 тогда и только тогда, когда оба логических аргумента равны 0.

Обратите внимание, что между таблицей истинности и диаграммой Эйлера — Венна существует взаимно однозначное соответствие (сравните табл. 2 и рис. 1):

1) число единиц в последнем столбце совпадает с числом закрашенных областей на диаграмме;

2) четыре комбинации логических переменных a и b отвечают четырем областям C0, C1, C2 и C3.

§ 6. Операции на множествах, логические связки Пересечение множеств.

На примере универсального множества U = {1, 2, …, 12} пересечением множеств A множества (см. рис. 3):

где — символ пересечения множеств. Рис. 3. Пересечение множеств A B Пересечение охватывает множество C3, закрашенное на диаграмме (рис. 3).

Пересечение множеств.

Пересечение множеств содержит элементы, общие для обоих множеств.

Обозначение пересечения множеств A и B: A B.

Значки объединения и пересечения множеств легко запомнить. Объединение напоминает чашку, в которой все накапливается, и латинскую букву U (по-английски чашка — CUP). А пересечение напоминает шапку, с которой почти все скатывается, и латинскую букву A (по-английски шапка — CAP).

Логическая связка «и». Конъюнкция.

Логически операция пересечения двух множеств характеризуется так:

элемент принадлежит 1-му множеству и 2-му множеству, то есть где или & — символ логической связки «и», которая называется конъюнкцией.

Обратите внимание, что логическая связка «и» относится именно к свойствам какого-то объекта x: объект x обладает свойствами A и B.

Конъюнкция — логическая функция двух аргументов с таблицей истинности 4. Эту таблицу очень легко запомнить: конъюнкция равна 1 тогда и только тогда, когда обе логические переменные равны 1.

Между таблицей истинности и диаграммой Эйлера — Венна существует взаимно однозначное соответствие (сравните табл. 4 и рис. 3):

1) число единиц в последнем столбце равно числу закрашенных областей;

2) четыре комбинации логических переменных a и b отвечают четырем областям C0, C1, C2 и C3.

Дополнение множества.

На примере универсального множества U = {1, 2, …, 12} дополнением множества A называется множество содержащее A элементы, не входящие во множество A (см. рис. 5):

где — символ дополнения множества. Рис. 5. Дополнение множества A Дополнение состоит из множеств C0 и C2, закрашенных на диаграмме (рис. 5).

Дополнение множества.

Дополнение множества A обозначается и содержит те и только те элементы универсального множества U, которых нет в A.

Рассмотрим операцию дополнения множеств с логической точки зрения.

Логическая связка «не». Отрицание.

Логически операция дополнения множества характеризуется так: элемент не принадлежит множеству.

То, что x не принадлежит множеству A, записывается так:

где ¬ — символ логической связки «не», которая называется отрицанием.

Логическая связка «не» относится именно к свойствам какого-то объекта x:

объект x не обладает свойством A.

Отрицание — логическая функция одного аргумента с таблицей истинности 6. Эту таблицу очень легко запомнить: значение функции противоположно значению аргумента.

Между таблицей истинности и диаграммой Эйлера — Венна существует взаимно однозначное соответствие (сравните табл. 6 и рис. 5):

1) число единиц в последнем столбце совпадает с числом закрашенных областей на диаграмме;

2) две комбинации логической переменной a отвечают двум областям C0 и C1.

Очевидно, что точно так же можно определить дополнение множества B (или отрицание свойства B), но математики считают, что это то же самое в смысле определение понятий.

§ 6. Операции на множествах, логические связки 2*. Другие операции на множествах и логические связки Разность множеств.

Разность множеств A и B — множество A\B, содержащее элементы, входящие в A и B содержит элементы A без элементов B.

Рассмотрим операцию разности множеств с логической точки зрения.

Разность.

Логически операция разности множеств характеризуется так: элемент принадлежит 1-му множеству и не принадлежит 2-му множеству:

Разность — логическая функция двух аргументов с таблицей истинности 8, которую легко запомнить: разность равна 1 тогда и только тогда, когда 1-я логическая переменная равна 1, а 2-я — 0.

2°. Операция симметрической разности множеств Симметрическая разность.

Симметрической разностью множеств A и B называется множество A B, содержащее элементы, входящие в A и не вхо- A B дящие в B, и элементы, входящие в B и не входящие в A, то есть объединение обоих разностей (см. рис. 9):

Рассмотрим операцию симметрической разности множеств с логической точки зрения.

Логическая связка «исключающее или».

Логически операция симметрической разности множеств характеризуется так: элемент принадлежит или только 1-му множеству или только 2-му множеству:

где — символ логической связки исключающее «или», или разделяющее «или».

Исключающее «или» — логическая функция двух аргументов с таблицей истинности 10, которую легко запомнить: исключающее или равно 1 тогда и только тогда, когда логические переменные имеют разные значения.

Логическая связка исключающее «или» относится к свойствам какого-то объекта x: объект x обладает свойствами либо A, либо B. Но не теми и другими. В этом состоит отличие исключающего «или» от обычного, или включающего, или соединяющего «или».

3°. Операция эквивалентности множеств Эквивалентность множеств.

Эквивалентностью множеств A и B называется множество A B, содержащее элементы, входящие либо и в A, и в B, лиC бо ни в A, ни в B, то есть эквивалентность множеств совпадает с дополнением симC метрической разности (см. рис. 11):

Изучим операцию эквивалентности множеств с логической точки зрения.

Логическая связка «тогда и только тогда». Эквивалентность.

Логически операция эквивалентности множеств характеризуется так: элемент или принадлежит обоим множествам, или не принадлежит им:

где или — символ логической связки «тогда и только тогда», или «если и только если», которая называется эквивалентностью.

§ 6. Операции на множествах, логические связки Эквивалентность — логическая функция двух аргументов с таблицей истинности 12, которую легко запомнить: эквивалентность равна 1 тогда и только тогда, когда логические переменные имеют равные значения.

Эквивалентность противоположна исключающему или: там, где одна связка равна 1, другая — 0, и наоборот.

4°. Операция импликации множеств Импликация множеств.

Импликацией множеств A и B называется множество A B, содержащее все элементы, входящие в B и не входящие в A, A B то есть импликация множеств совпадает с дополнением разности (см. рис. 13):

= {1, 5, 6, 7, 8, 9, 10, 11, 12} = C2 C3 C4. Рис. 13. Импликация множеств A B Изучим операцию импликации множеств с логической точки зрения.

Импликация.

Логически операция эквивалентности множеств характеризуется так: элемент не принадлежит только 1-му множеству A без 2-го множества:

где — символ логической связки «если…, то», которая называется импликацией.

Импликация — логическая функция двух аргументов с таблицей истинности 14, которую легко запомнить: импликация равна 0 тогда и только тогда, когда 1-я логическая переменная равна 1, а 2-я — 0 (см. табл. 14).

Импликация противоположна разности: там, где одна связка равна 1, другая равна 0, и наоборот.

3. Некоторые законы теоретико-множественных Выпишем основные теоретико-множественные и логические законы и соотношения. В этом пункте приведены законы, в следующем — соотношения.

Образцы доказательств приведем в последнем пункте.

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

1. Законы идемпотентности.

2. Законы коммутативности.

3. Законы ассоциативности.

4. Законы дистрибутивности.

5. Законы нуля и единицы.

6. Законы де Моргана.

7. Обобщенные законы де Моргана.

§ 6. Операции на множествах, логические связки Теоретико-множественные и логические соотношения также запишем сразу на двух языках: сначала на языке теории множеств, затем на языке логики.

1. Разность выражается через пересечение и дополнение, или конъюнкцию и отрицание:

2. Симметрическая разность выражается через объединение и разность, а исключающее или — через дизъюнкцию и разность:

3. Эквивалентность выражается через дополнение и симметрическую разность, или отрицание и симметрическую разность:

4. Эквивалентность выражается через пересечение и импликацию, или через конъюнкцию и импликацию:

5. Импликация выражается через дополнение и разность, или отрицание и разность:

6. Импликация выражается через объединение и дополнение, или дизъюнкцию и отрицание:

С помощью полных диаграмм Эйлера — Венна доказывают законы теоретико-множественных операций.

Докажем первый закон ассоциативности (рис. 15) Сначала нарисуем множество A B, затем — множество C, в итоге объединим две картинки вместе и получим множество (A B) C.

Затем нарисуем множество A, затем — множество B C, в итоге объединим две картинки вместе и получим множество A (B C).

Полученные множества одинаковы, поскольку картинки совпадают.

С помощью таблиц истинности также доказывают законы теоретикомножественных операций.

Снова докажем первый закон ассоциативности Сначала в первых трех столбцах выпишем все восемь различных комбинаций значений логических переменных a, b и c. В четвертом столбце выпишем значение логической функции a b, используя значения первых двух столбцов с переменными a и b. В итоге в пятом столбце выпишем значение логической функции (a b) c, используя значения четвертого и третьего столбцов.

Затем в шестом столбце выпишем значение логической функции b c, используя значения второго и третьего столбцов с переменными b и c. В итоге в седьмом столбце выпишем значение логической функции a (b c), используя значения первого и шестого столбцов.

Ясно видно, что в таблице 16 закрашенные столбцы — четвертый и шестой — совпадают.

§ 6. Операции на множествах, логические связки 1.1. Чему равно {1, 2, 3} {2, 3, 4}?

1.2. Чему равно {1, 2, 2} {3, 3, 3}?

1.3. Чему равно {1, 2, 2} {3, 4, 5}?

1.4. Чему равно {1, 2, 2} {2, 2, 2}?

1.5. Чему равно {1, 1, 1} {1, 1, 1}?

2.1. Чему равно {1, 2, 3} {4, 5, 6}?

2.2. Чему равно {1, 2, 2} {1, 1, 2}?

2.3. Чему равно {1, 2, 2} {3, 4, 5}?

2.4. Чему равно {1, 2, 3} {1, 2, 3}?

2.5. Чему равно {1, 1, 1} {1, 1, 1}?

3.1. Чему равно дополнение {5, 5, 6} до {1, 2, 3, 4, 5, 6}?

3.2. Чему равно дополнение {3, 4, 5, 6} до {1, 2, 3, 4, 5, 6}?

3.3. Чему равно дополнение {6, 5, 4} до {1, 2, 3, 4, 5, 6}?

3.4. Чему равно дополнение {6, 5, 5} до {1, 2, 3, 4, 5, 6}?

3.5. Чему равно дополнение {5, 5, 6, 4} до {1, 2, 3, 4, 5, 6}?

4.1. Чему равно {1, 2, 3}\{4, 5, 6}?

4.2. Чему равно {1, 2, 2}\{1, 1, 2}?

4.3. Чему равно {1, 2, 2}\{3, 4, 5}?

4.4. Чему равно {1, 2, 3}\{2, 2, 3}?

4.5. Чему равно {1, 1, 1}\{1, 1, 1}?

5. Операция симметрической разности множеств 5.1. Чему равно {1, 2, 3} {4, 4, 4}?

5.2. Чему равно {1, 4, 4} {2, 3, 4}?

5.3. Чему равно {1, 2, 2} {2, 2, 2}?

5.4. Чему равно {1, 2, 3} {1, 2, 3}?

5.5. Чему равно {1, 1, 1} {1, 1, 1}?

6.1. Чему равно {1, 2, 3} {4, 4, 4}?

6.2. Чему равно {1, 4, 4} {2, 3, 1}?

6.3. Чему равно {1, 2, 2} {2, 2, 1}?

6.4. Чему равно {1, 2, 3} {1, 2, 3}?

6.5. Чему равно {1, 1, 1} {1, 1, 1}?

§ 6. Операции на множествах, логические связки 2.1. Чему равно A B, если A = {1, 2, 3, 3}, B = {2, 2, 3, 4}, U = {1, 2, 3, 4, 5}?

1) {2, 2, 3, 3}. 2) {1, 2, 3, 4}. 3) {4, 4, 5, 5}. 4) {1, 2, 3, 3}. 5) {2, 3, 4, 5}.

2.2. Чему равно A B, если A = {1, 2, 3, 3}, B = {2, 2, 3, 4}, U = {1, 2, 3, 4, 5}?

1) {2, 2, 3, 3}. 2) {1, 2, 3, 4}. 3) {4, 4, 5, 5}. 4) {1, 2, 3, 3}. 5) {2, 3, 4, 5}.

2.3. Чему равно ¬A, если A = {1, 2, 3, 3}, B = {2, 2, 3, 4}, U = {1, 2, 3, 4, 5}?

1) {2, 2, 3, 3}. 2) {1, 2, 3, 4}. 3) {4, 4, 5, 5}. 4) {1, 2, 3, 3}. 5) {2, 3, 4, 5}.

2.4. Чему равно A B, если A = {1, 2, 3, 3}, B = {2, 2, 3, 4}, U = {1, 2, 3, 4, 5}?

1) {2, 2, 3, 3}. 2) {1, 2, 3, 4}. 3) {4, 4, 5, 5}. 4) {1, 2, 3, 3}. 5) {2, 3, 4, 5}.

2.5. Чему равно B A, если A = {1, 2, 3, 3}, B = {2, 2, 3, 4}, U = {1, 2, 3, 4, 5}?

1) {2, 2, 3, 3}. 2) {1, 2, 3, 4}. 3) {4, 4, 5, 5}. 4) {1, 2, 3, 3}. 5) {2, 3, 4, 5}.

8.1. Какой закон является законом идемпотентности?

8.2. Какой закон является законом коммутативности?

8.3. Какой закон является законом ассоциативности?

8.4. Какой закон является законом дистрибутивности?

8.5. Какой закон является законом де Моргана?

98.1. Какой соотношение связывает разность с пересечением и дополнением?

9.2. Какой соотношение связывает симметрическую разность с объединением и разностью?

9.3. Какой соотношение связывает эквивалентность с дополнением и симметрической разностью?

9.4. Какой соотношение связывает эквивалентность с пересечением и импликацией?

9.5. Какой соотношение связывает импликацию с объединением и дополнением?

Пусть n — номер варианта от 1 до 16. Докажите двумя способами:

а) с помощью диаграмм Эйлера — Венна;

б) с помощью таблиц истинности.

Для вариантов 1 и 9: второй закон ассоциативности.

Для вариантов 2 и 10: первый закон дистрибутивности.

Для вариантов 3 и 11: второй закон дистрибутивности.

Для вариантов 4 и 12: первый закон де Моргана.

Для вариантов 5 и 13 второй закон де Моргана.

Для вариантов 6, 14 и 15: первый обобщенный закон де Моргана.

Для вариантов 7, 8 и 16: второй обобщенный закон де Моргана.

§ 7. Логические модели утверждений Обратное Противоположное заключение обратному заключение 1. Моделирование союзов «или» и «и» и отрицания...........................

2. Прямое, противоположное и обратное заключение.........................

1°. Прямое, противоположное и обратное заключения.....................

2°. Доказательство от противного. Равносильность.........................

3. Необходимые и достаточные условия. Равносильность......................

Косовский Н. К., Тишков А. В. Логики конечнозначных предикатов на основе неравенств.— СПб.: Изд-во С.-Петерб. ун-та, 2000.

Мендельсон Э. Введение в математическую логику.— М.: Наука, 1976.

Адаменко А. Н., Кучуков А. М. Логическое программирование и Visual Prolog.— СПб.: БХВ-Петербург, 2003.

Бизам Д., Герцег Я. Многоцветная логика. 175 логических задач.— М.: Мир, 1978.

Заключение, посылка, вывод, прямое заключение, противоположное заключение, обратное заключение, противоположное обратному заключение, доказательство от противного, эквивалентные заключения, эквивалентные утверждения, необходимое условие, достаточное условие § 7. Логические модели утверждений 1. Моделирование союзов «или» и «и» и отрицания Разумеется, будем рассматривать не все возможные утверждения, а только те, которые моделируются с помощью множеств и логических связок.

Математическая логика используется для моделирования свойств множеств. Моделирование самих множеств осуществляется с помощью понятия «множество».

При описании множеств используется союз «и», а также запятая, его заменяющая. Например, рассмотрим утверждение:

Данное утверждение описывает множество, состоящее из трех элементов:

профессора физики, профессора биологии и профессора математики.

Интересен случай, когда в качестве элемента множества используется сам союз «и». Рассмотрим такое утверждение:

Здесь описывается множество, состоящее из двух элементов: А и Б.

Но последнее модельное утверждение можно записать несколько по-другому, изменив его синтаксис:

Здесь уже описывается множество трех элементов: А, Б и И.

Поскольку при произнесении эти утверждения звучат примерно одинаково, этим пользуются, задавая следующий вопрос, синтаксис которого записан в некотором «усредненном» виде:

Любой конкретный ответ на такой вопрос, трактуя его как одну из рассмотренных ранее двух утверждений, можно всегда признать неправильным.

При описании множеств точно так же, как и союз «и», может использоваться союз «или», а также запятая, его заменяющая. Например, рассмотрим утверждение:

Эти интереснейшие задачи могут быть предложены людям, компьютерам или даже представителям внеземных цивилизаций.

Данное утверждение описывает множество, состоящее из трех элементов:

люди, компьютеры и представители внеземных цивилизаций.

Интересен случай, когда в качестве элементов множества используется один и тот же объект, как это сделано, например, в следующем утверждении:

Во времена социализма наука работала или на военных, Здесь описано множество, состоящее из одного элемента.

2°. Моделирование свойств множеств Как множества, так и их свойства с помощью союза «или» моделируются одними и те ми же средствами. Например, рассмотрим уже встречавшееся ранее утверждение:

Можно сказать, что данное утверждение описывает множество, состоящее из трех элементов: люди, компьютеры и представители внеземных цивилизаций. А можно сказать и то, что здесь описывается тот факт, что задачи могут быть предложены трем объектам множества как по отдельности, так и в любом сочетании, хоть всем трем сразу.

Итак, союз «или» может описывать дизъюнкцию свойств множеств объектов.

Точно также и по поводу союза «и» в описаниях множеств можно сказать, что союз «и» описывает дизъюнкцию свойств множеств объектов. Однако на практике при использовании технических устройств дизъюнкция передается исключительно только союзом «или».

Наиболее часто такое использование союза «или» применяется при поиске информации, например, в Интернете. Следует иметь в виду, что в поисковых машинах Интернета дизъюнкция, или операция «или», часто обозначается вертикальной палочкой |. Например, следующая строка поиска в поисковой машине заставит поисковую машину найти все веб-страницы, на которых речь идет о математике или информатике или о том и о другом.

Совершенно аналогично на практике при использовании технических устройств конъюнкция, или операция «и», передается исключительно только союзом «и», который часто обозначается амперсандом &. Например, следующая строка поиска в поисковой машине заставит поисковую машину найти все веб-страницы, на которых речь идет о математике и информатике одновременно.

При передаче в обыденной речи операций логического «или» и логического «и» может использоваться как союз «или», так и союз «и». Но имеется логическая операция, которая передается только союзом «или».

Возможно, наиболее часто в обыденной речи союз «или» используется для передачи логической операции «исключающее или». Например, в утверждении Если клиент мертв, то его либо можно оживить, либо нельзя союз «или» моделируется логической операцией «исключающее или»: клиент может быть либо жив, либо мертв, но не одновременно. Кстати, связка «либо … либо» тоже моделируется логической операцией «исключающее или».

§ 7. Логические модели утверждений Рассмотрим, как отрицание передается в естественном языке. Проще всего это сделать на конкретных примерах.

Примеры.

1. Возьмем утверждение Посмотрим, как можно построить отрицания этого утверждения.

Наиболее простой и безошибочный способ — применить отрицание сразу ко всему утверждению:

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

Каким образом можно упростить это отрицание? Рассмотрим два способа.

1) Если в утверждении имеется глагол, то отрицание можно перенести со всего утверждения на этот глагол при условии, что получается осмысленное утверждение:

2) Если в утверждении имеется прилагательное или дополнение, то отрицание можно перенести со всего утверждения на это прилагательное или дополнение при условии, что получается осмысленное утверждение:

2. Возьмем утверждение Применим отрицание сразу ко всему утверждению:

Неверно, что треугольник является прямоугольным.

Применим отрицание к глаголу:

Применим отрицание к прилагательному:

Рассмотрим, как используется закон двойного отрицания. Проще всего это сделать на конкретных примерах.

Пример.

1. Возьмем утверждение Посмотрим, как можно построить двойное отрицание этого утверждения, которое, разумеется, равносильно исходному утверждению. Имеем 4 способа:

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

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

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

2. Прямое, противоположное и обратное заключение 1°. Прямое, противоположное и обратное заключения Утверждение. Заключение, посылка и вывод.

Утверждение — высказывание, которое либо истинно, либо ложно.

Рассмотрим утверждения, которые моделируются импликацией, то есть следованием. Схема таких утверждений такова: из посылки следует вывод. Подобные утверждения также называются заключением. Но посылка и вывод — это тоже утверждения. Таким образом, заключение — это утверждение, которое связывает следованием два утверждения: посылку и вывод.

Приведем известное утверждение, которое является заключением:

Перепишем это утверждение так, чтобы было явно видно, что это заключение, в виде посылка вывод, то есть по схеме «если…, то»:

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

Очевидно, что это истинное заключение. Это будет наше прямое заключение. Из прямого заключения можно легко получить противоположное, обратное и противоположное обратному заключения.

Прямое и противоположное заключения.

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

Выпишем заключение, противоположное прямому.

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

Ясно, что получилось ложное заключение. Истинное будет таким:

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

Обратное заключение.

Обратным заключением называется утверждение, полученное из произвольного прямого заключения перестановкой местами посылки и вывода.

Сформулируем заключение, обратное прямому.

Если у четырехугольника все углы равны, то это квадрат.

И это заключение ложно. Вот истинное:

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

Заключение, противоположное обратному.

Заключением, противоположным обратному (или обратным противоположному), называется утверждение, полученное из произвольного прямого заключения перестановкой местами посылки и вывода, взятых с отрицанием.

Другими словами, заключение, противоположное обратному:

1) либо получается из противоположного построением обратного;

2) либо получается из обратного построением противоположного.

Заключение, противоположное обратному, имеет вид:

Если у четырехугольника углы не равны, то это не квадрат.

А вот это заключение снова истинно! И это не случайно.

§ 7. Логические модели утверждений 2°. Доказательство от противного. Равносильность Имеет место следующее правило: заключение, противоположное обратному истинному, всегда истинно. Аналогично заключение, противоположное обратному ложному, всегда ложно. Другими словами, прямое заключение и заключение, противоположное обратному, либо оба истинны, либо оба ложны.

Доказательство от противного.

На этом основано доказательство от противного, когда вместо прямого доказывается заключение, противоположное обратному: берется отрицание вывода прямого заключения и доказывается его отрицание посылки.

Также не случайно, что противоположное и обратное заключения были оба ложны: противоположное и обратное заключения также либо оба истинны, либо оба ложны, поскольку если одно из них взять за прямое, то другое будет противоположным обратному.

Эквивалентные заключения.

Такие заключения, которые либо оба истинны, либо оба ложны независимо от того, какие посылки и выводы в них входят, называются логически равносильными, или эквивалентными.

Логически эквивалентные заключения равносильны в силу своей логической структуры. Получаем следующую схему.

Рис. 1. Связь прямых, противоположных и обратных заключений.

Двойными стрелками соединены логически равносильные заключения Эквивалентные утверждения.

Если у истинного заключения обратное тоже истинно (или, что то же самок, противоположное истинно), то у таких заключений посылка и заключение являются эквивалентными утверждениями.

Например, теорема Пифагора Если треугольник прямоугольный, то c2 = a2 + b2, где a, b, c — длины сторон имеет истинные противоположную и обратную теоремы соответственно:

Если треугольник не прямоугольный, то c2 a2 + b2, где a, b, c — длины сторон;

Если c2 = a2 + b2, где a, b, c — длины сторон, то треугольник прямоугольный.

Поэтому утверждения «c2 = a2 + b2, где a, b, c — длины сторон треугольника», и «треугольник прямоугольный» равносильны.

3. Необходимые и достаточные условия. Равносильность 1°. Достаточные и необходимые условия Необходимые и достаточные условия получаются при следовании одних утверждений из других.

Необходимое и достаточное условие.

Если из одного утверждения следует другое, то первое утверждение называется достаточным условием для второго, а второе — необходимым условием для первого.

Другими словами, для выполнения, для истинности второго утверждения достаточно выполнения, истинности первого, а из истинности первого утверждения необходимо следует истинность второго.

Перепишем это определение в терминах теории множеств. Для этого достаточно увидеть, что множество, описываемое достаточным условием, является подмножеством условия, описываемым необходимым условием.

Необходимое и достаточное условия.

Если множество объектов, задаваемых одним утверждением, является подмножеством объектов, задаваемых другим утверждением, то первое утверждение называется достаточным условием для второго, а второе — необходимым условием для первого.

Другими словами, для того, чтобы элементу принадлежать надмножеству, ему достаточно принадлежать подмножеству (но не наоборот!), и если элемент принадлежит подмножеству, то тем самым он необходимо принадлежит и надмножеству (но не наоборот!).

Рассмотрим эти тесно связанные понятия на примере конкретных случаев, чтобы лучше в них разобраться.

Примеры.

1. Из истинности заключения Если четырехугольник квадрат, то все его углы равны.

следует, что истинность утверждения «четырехугольник квадрат» достаточна для того, чтобы утверждение «все углы четырехугольника равны» тоже было истинно.

Окончательно получаем:

«четырехугольник квадрат» достаточно для «все углы четырехугольника равны».

В более формальном виде с использованием логических связок это заключение можно записать следующим образом:

Четырехугольник квадрат все углы четырехугольника равны.

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

Четырехугольник квадрат все углы четырехугольника равны.

§ 7. Логические модели утверждений На диаграмме Эйлера — Венна это заключение можно изобразить так, как показано на рисунке 2.

Рис. 2. Четырехугольник квадрат все углы четырехугольника равны А если наоборот?

Истинность «четырехугольник квадрат» не следует из истинности «все углы четырехугольника равны», поэтому второе утверждение недостаточно для первого. Ведь если «все углы четырехугольника равны», то четырехугольник может быть не квадратом, а прямоугольником с разными сторонами.

Достаточным условием для «четырехугольник квадрат» будет «все углы и все стороны четырехугольника равны»:

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

2. Из истинности того же заключения Если четырехугольник квадрат, то все его углы равны.

следует, что из истинности утверждения «четырехугольник квадрат» необходимо следует, что утверждение «все углы четырехугольника равны» истинно.

Окончательно получаем:

«все углы четырехугольника равны» необходимо для «четырехугольник квадрат».

А если наоборот?

Истинность «четырехугольник квадрат» не следует из истинности «все углы четырехугольника равны», поэтому первое утверждение не является необходимым для второго. Ведь если «все углы четырехугольника равны», то четырехугольник может быть не квадратом, а прямоугольником с разными сторонами.

Необходимым условием для «все углы четырехугольника равны» будет «четырехугольник прямоугольник»:

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

Рассмотрим еще два примера.

Примеры.

1. Заключение Если четырехугольник квадрат, то все его стороны равны.

истинно, поэтому:

1) «четырехугольник квадрат» достаточно для «все стороны четырехугольника равны»;

2) «все стороны четырехугольника равны» необходимо для «четырехугольник квадрат».

Другими словами, Четырехугольник квадрат все стороны четырехугольника равны.

Четырехугольник квадрат все стороны четырехугольника равны.

На диаграмме Эйлера — Венна это заключение можно изобразить так, как показано на рисунке 3.

Рис. 3. Четырехугольник квадрат все стороны четырехугольника равны 2. Заключение Если все стороны четырехугольника равны, то это квадрат ложно, поэтому:

1) «все стороны четырехугольника равны» недостаточно для «четырехугольник квадрат». Достаточным будет «все углы и все стороны четырехугольника равны»:

Все углы и все стороны четырехугольника равны четырехугольник квадрат, Все углы и все стороны четырехугольника равны четырехугольник квадрат;

2) «четырехугольник квадрат» не является необходимым для «все стороны четырехугольника равны». Необходимым будет «четырехугольник ромб»:

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

§ 7. Логические модели утверждений Итак, из заключения Если четырехугольник квадрат, то все его углы равны следует, что утверждение «четырехугольник квадрат» является достаточным для утверждения «все углы четырехугольника равны», а второе утверждение является необходимым для первого.

А наоборот неверно.

Наоборот получается, если посылка и вывод эквивалентны. Эквивалентность называют еще равносильностью.

Равносильность.

Равносильность — другое название для эквивалентности.

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

Точно так же для квадрата необходимо, чтобы у него были равны и стороны, и углы, и наоборот, для равенства сразу и сторон, и углов необходимо, чтобы был квадрат.

Так получается потому, что утверждения «четырехугольник квадрат» и «все стороны и все углы четырехугольника равны» равносильны.

В более формальном виде с использованием логических связок это заключение можно записать следующим образом:

Четырехугольник квадрат все углы и все стороны четырехугольника равны.

Учитывая равенство множеств, описываемых посылкой и выводом, это заключение можно записать так:

Четырехугольник квадрат = все углы и все стороны четырехугольника равны.

На диаграмме Эйлера — Венна это заключение можно изобразить так, как показано на рисунке 4.

Рис. 4. Четырехугольник квадрат = все углы и все стороны четырехугольника равны 1. Моделирование союзов «или» и «и» и отрицания 1.1. Пусть высказывание A = «На улице идет дождь», B = «Над моей головой раскрыт зонтик». Тогда дизъюнкция этих высказываний равна:

1) «На улице не идет дождь».

2) «Над моей головой не раскрыт зонтик».

3) «На улице идет дождь и над моей головой раскрыт зонтик».

4) «На улице идет дождь или над моей головой раскрыт зонтик».

5) «Если на улице идет дождь, то над моей головой раскрыт зонтик».

1.2. Пусть высказывание A = «На улице идет дождь», B = «Над моей головой раскрыт зонтик». Тогда конъюнкция этих высказываний равна:

1) «На улице не идет дождь».

2) «Над моей головой не раскрыт зонтик».

3) «На улице идет дождь и над моей головой раскрыт зонтик».

4) «На улице идет дождь или над моей головой раскрыт зонтик».

5) «Если на улице идет дождь, то над моей головой раскрыт зонтик».

1.3. Пусть высказывание A = «На улице идет дождь», B = «Над моей головой раскрыт зонтик». Тогда отрицание высказывания A равна:

1) «На улице не идет дождь».

2) «Над моей головой не раскрыт зонтик».

3) «На улице идет дождь и над моей головой раскрыт зонтик».

4) «На улице идет дождь или над моей головой раскрыт зонтик».

5) «Если на улице идет дождь, то над моей головой раскрыт зонтик».

1.4. Пусть высказывание A = «На улице идет дождь», B = «Над моей головой раскрыт зонтик». Тогда отрицание высказывания B равна:

1) «На улице не идет дождь».

2) «Над моей головой не раскрыт зонтик».

3) «На улице идет дождь и над моей головой раскрыт зонтик».

4) «На улице идет дождь или над моей головой раскрыт зонтик».

5) «Если на улице идет дождь, то над моей головой раскрыт зонтик».

1.5. Пусть высказывание A = «На улице идет дождь», B = «Над моей головой раскрыт зонтик». Тогда импликация высказываний A и B равна:

1) «На улице не идет дождь».

2) «Над моей головой не раскрыт зонтик».

3) «На улице идет дождь и над моей головой раскрыт зонтик».

4) «На улице идет дождь или над моей головой раскрыт зонтик».

5) «Если на улице идет дождь, то над моей головой раскрыт зонтик».

§ 7. Логические модели утверждений 2. Прямое, противоположное и обратное заключение 2.1. Что является отрицанием заключения «Если на улице идет дождь, то над моей головой раскрыт зонтик»?

1) «Над моей головой раскрыт зонтик, если на улице идет дождь».

2) «Если на улице не идет дождь, то над моей головой не раскрыт зонтик».