Оглавление

1.Элементы теории множеств и математической логики

1.1.Понятие множества. Отношения между множествами

Понятие множества является одним из основных понятий математики.

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

Приведем примеры, поясняющие содержание понятия множества:

— множество строк на этой странице;

— множество домов на данной улице;

— множество целых чисел;

— множество студентов в аудитории.

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

Множество можно описать одним из следующих способов:

— в виде списка или таблицы: все элементы множества непосредственно перечисляются. Этот способ удобен, если множество невелико (смотрите примеры 1 и 4);

— указанием способа конструирования множества, когда задается определенное правило, выражаемое словами или формулами, в соответствии с которыми можно сказать, принадлежит данный объект к рассматриваемому множеству или нет (примеры 2 и 3).

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

В том случае, когда х является элементом множества А, пишут так: А = {x}.

Запись А = {x: P} означает множество всех х, удовлетворяющих условию Р.

Пример 1.

Запись А = {1,2,5,7} означает, что множество А состоит из четырех элементов 1,2,5,7.

Пример 2.

Х = {х: х является студентом, рост которого больше 170 сантиметров}. Это множество описано способом конструирования.

Пример 3.

А= {у: у> 3} означает множество всех чисел, больших трех. Описано методом правила.

Пример 4.

Запись А= {а,б,м,н,и,ю,ч} означает, что множество А состоит из семи элементов а,б,м,н,и,ю,ч, которые являются буквами русского алфавита.

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

В этой таблице все реальные символы закодированы в тексте книги определенным числом звездочек (*) — от 1 до 6.

Если х является элементом множества А, то говорят, что х принадлежит А и записывают: х*А (x€A); если х множеству А не принадлежит, то пишут х **A (x перечеркнутый€ А).

Для того, чтобы выразить тот факт, что А — подмножество множества В, пользуются символом включения: А **** В. Это следует читать: « А содержится в В».

Отрицание включения обозначим символами — *****.

Так, например, если А есть множество четных чисел, то 2*A (2 € А), а число 5 (перечеркнутый€) А (не принадлежит), 5**A.

Подчеркнем, что каждый элемент может входить во множество только один раз.

Так, например, множество различных цифр числа 354577312 будет содержать только элементы 3,5,4,7,1,2.

Множества бывают конечными и бесконечными

Множество называется конечным, если оно содержит конечное число элементов (смотрите примеры 1 и 4), в противном случае оно является бесконечным (пример 3).

К конечным множествам относятся, в частности, одноэлементные множества, состоящие только из одного элемента. Необходимо различать объекты а и {а}:

а — один элемент некоторого множества, {а} — одноэлементное множество.

Если множество не имеет элементов, то его называют пустым

и мы обозначим его, в соответствии с таблицей, символами — ***.

Пример 5.

*** = {х: х — действительное число, квадрат которого равен -1}.

Пример 6.

*** = {х: х — лев, живущий на Луне}.

Необходимо различать следующие множества: *** {***}, {0}. Последние два множества не являются пустыми, т.к. каждое из них содержит по одному элементу. Второе служит примером множества, элемент которого, в свою очередь, представляет собой множество.

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

Определение 1.

Если каждый элемент множества А является также и элементом множества В, то множество А называется частью или подмножеством множества В.

Для того, чтобы выразить тот факт, что А — подмножество множества В, пользуются символом включения (****): А **** В. Это следует читать: « А содержится в В».

Отрицание включения (смотрите таблицу кодировки символов) обозначим символом — *****.

Отметим, что пустое множество *** и само множество В являются также подмножествами множества В, т.е. (***) **** В и В****В.

Пример 7.

А = {а,б,м,н,и,ю,ч} есть подмножество множества букв русского алфавита В = {а,б,в,…}.

Пример 8.

М = {{2,3}, {4,5,6}} — двухэлементное множество, элементами которого являются два других множества.

К = {{2,3}, {4,5,6},9,10,11} — пятиэлементное множество,

причем М *** К.

Пример 9.

L = {3,4, {3,4}} — трехэлементное множество, причем, 3*L и 4*L, но и {3,4} * L.

Определение 2.

Два множества А и В называются равными, если А* В и В *А.

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

2.Операции над множествами. Основные законы

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

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

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

Определение 1.

Совокупность элементов, принадлежащих универсальному множеству ******, но не принадлежащих подмножеству А, называется дополнением подмножества А.

Обозначим его («не А»). Таким образом, «неA» = {х: х* (******), х ** А}.

С помощью диаграммы Эйлера-Венна можно представить универсальное множество в виде прямоугольника, а подмножество А — в виде круга, расположенного внутри этого прямоугольника.

Тогда, очевидно, что заштрихованная область будет

соответствовать дополнению (см. рис.1.1).

Замечание. Из определения дополнения множества А следует, что дополнение дополнения множества А есть множество А.

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

Определение 2.

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

Объединение множеств обозначают разными символами («U"или «+»). В нашем случае: А + В = {х: х * А или х * В}.

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

Операцию объединения таких множеств иллюстрирует диаграмма Эйлера-Венна (см. рис.1.2). В качестве результата такой операции выступает множество С.

Пусть Р = {х:-1 <= х <1},Q = {х:0 <х <1}. Тогда P+Q = {х:-1 <= х <1}. Или P+Q = Р.

Определение 3.

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

Пересечение множеств часто обозначают символом «подкова». Таким образом, в нашем случае: А (знак подковы) В = {х: х * А и х * В} (2).Часто эту операцию называют операцией пересечения множеств,

поэтому знак «x» здесь вполне уместен.

Иллюстрацией служит соответствующая диаграмма (см. рис.1.3). В качестве результата такой операции выступает множество С.

Пример 14.

Пусть А = {1,2,3,5} и В = {1,5,7,9}. Тогда А x В = {1,5}.

Если множества А и В не имеют общих элементов, то они называются непересекающимися.

Определение 4.

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

2.Что можно сказать о множестве В по отношению ко множеству А?

Таким образом, в нашем случае: А \ В = {х: х * А и х ** В} (3).

Операцию разности таких множеств иллюстрирует диаграмма Эйлера-Венна (см. рис.1.4). В качестве результата такой операции выступает множество С.

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

Ниже, в виде таблицы, показаны основные законы алгебры множеств (Где: ****** — универсум, А,В,С — его любые подмножества)

3.Алгебра высказываний

АЛГЕБРА ВЫСКАЗЫВАНИЙ является составной частью одного из современных быстро развивающихся разделов математики — математической логики.

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

Основными элементами математической логики служат так называемые высказывания или суждения.

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

Приведем примеры высказываний:

А — «Санкт-Петербург — культурная столица России» (и).

В — «Слон — большая рыба» (л).

С — «Снег черный» (л).

D — «5 <9» (и).

Е — «100 делится на 5» (и).

F — «10> 20» (л).

Если высказывание A истинно, то пишут A = 1, если ложно, то используют запись A = 0.

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

Не каждое предложение может быть высказыванием.

Например, такие фразы как «Сегодня хорошая погода», «Подайте мне книгу», «Да здравствует 128 группа!» « x> 0» не являются высказываниями, поскольку об истинности или ложности того, что утверждается в этих предложениях, говорить нет смысла.

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

Различают высказывания простые (элементарные) и сложные (составные).

Повествовательное предложение, в котором говорится об одном-единственном событии, называется простым высказыванием. Приведенные выше высказывания A,B,C,D,E,F рассматриваются как элементарные — их нельзя разделить на более простые.

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

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

Например, предложение «Если 2х2=5, то внешний угол треугольника равен сумме двух внутренних, не смежных с ним» в контексте разговора выглядит полной бессмыслицей. В алгебре логики оно представляет собой высказывание, в котором первая часть ложь, а вторая — истина.

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

Основными операциями над высказываниями являются:

— отрицание;

— конъюнкция;

— дизъюнкция;

— имликация;

— эквиваленция.

Определение 1.

Отрицанием высказывания А называется такое высказывание, которое истинно, когда А ложно, и ложно, когда А истинно. Обозначим его («не А»).

Например, если А = 3х2 = 6, то неA = 3Х2 не равно 6. Здесь А — истинное высказывание, а неA — ложное.

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

Таблица 1

Такие таблицы получили название таблиц истинности.

Определение 2. Конъюнкцией (или логическим умножением) двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания А и В. Обозначается А _^ В («А и В»).

Конъюнкция — это логическая связка «и»: если хотя бы одно из составляющих высказывания ложно, то и полученное из них с помощью союза «и» сложное высказывание также ложно.

Например, для высказываний «3> 1», «125 делится на 5» конъюнкция будет истинным высказыванием т.к. «3> 1 и 125 делится на 5». А для высказываний « Студент Петров — отличник» и «Слон — насекомое» конъюнкция будет ложным высказыванием:

«Студент Петров — отличник и Слон — насекомое».

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

Таблица 2

Определение 3.

Дизъюнкцией (или логическим сложением) двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда истинно хотя бы одно из них, т. е. когда истинно А или В, или А и В вместе («А или В»).

Например, высказывание A — «Декабрь — зимний месяц», В — «Летом иногда идет дождь», определим высказывание A+B — «Декабрь — зимний месяц или летом иногда идет дождь». Установить истинность логической суммы можно с помощью следующей таблицы:

Таблица 3

Определение 4.

Импликацией двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда А истинно, а В ложно, и истинно при всех других логических значениях высказываний А и В («А влечет В», «Если А, то В»).

Например, «Если 36 делится на 4,то 36 — четное число» истинная импликация двух высказываний:" «Число 36 делится на 4» и «36 — четное число».

Установить истинность импликации можно с помощью следующей таблицы:

Таблица 4

Определение 5. Эквиваленцией (или эквивалентностью) двух высказываний А и В называется такое высказывание, которое истинно тогда и только тогда, когда истинны оба высказывания А и В или оба ложны, и ложно в остальных случаях («А эквивалентно В», « А тогда и только тогда, когда В»).

Установить истинность эквиваленции можно с помощью следующей таблицы:

Таблица 5

Эквивалентными являются, например, высказывания

Это можно проверить, составив таблицу истинности этих высказываний:

Таблица 6

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

Тождественные высказывания. Эквивалентные высказывания. Формулы Августа де Моргана

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

Доказать это можно составив таблицу истинности этих высказываний.

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

Тождественно истинные или тождественно ложные высказывания, если они встречаются в формулах, заменяются в них, соответственно единицей или нулем:

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

Таблица 7

Формулы, выделенные жирным шрифтом, называются формулами Августа де Моргана (1806–1871). Используя эти формулы, можно, в частности, преобразовывать высказывания: сложные заменять более простыми.

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

A + A = A,

AA = A,

A +1 = A.

Это приводит к необычности действий над многочленами алгебры высказываний.

Пусть нужно перемножить два сложных высказывания:

(A + B) (A + C) = AA + AC + AB + BC = A + AB + AC + BC.

Рассмотрим теперь два первых слагаемых

A + AB = A (1 + B) = A1 = A и аналогично A+ AC = A.

Таким образом, окончательно получаем (A + B) (A + C) = A+ BC.

Преобразование A + AB = A очень часто встречается в алгебре высказываний и называется «поглощение».

Есть еще один вид столь же часто встречающегося тождественного преобразования, которое называется «склеивание».

Суть его состоит в следующем: (склеивание произошло по символу B):

4.Решение типовых задач

Задача 1:

Множество А содержит 20 элементов, В — 12, Пересечение множеств А и B — 7 элементов. Сколько элементов содержит объединение множеств А и В?

Решение.

Сумма элементов множеств А и В содержит 20 +12 = 32 элемента, но в этой сумме имеется 7 элементов, которые входят в оба множества. Разность 32 — 7 = 25 позволяет устранить этот недостаток.

Ответ: множество А и В содержит 25 элементов.

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

Задача 2:

Студенты Алексей (А), Борис (Б) и Григорий (Г) откопали древний сосуд. О том, где и когда он был изготовлен, каждый из них высказал по два предположения:

А: «Это сосуд греческий и сосуд изготовлен в V веке»;

Б: «Это сосуд финикийский и сосуд изготовлен в III веке»;

Г: «Это не греческий сосуд и изготовлен он в IV веке».

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

Где и в каком веке изготовлен сосуд?

Решение:

Введем обозначения простых высказываний:

«Это сосуд греческий» — G;

«Это сосуд финикийский» — F;

«Сосуд изготовлен в V веке» — 5;

«Сосуд изготовлен в III веке» — 3;

«Сосуд изготовлен в IV веке» — 4.

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

Формула высказывания Алексея имеет вид G5. Преподаватель сказал, что Алексей прав только в одном из своих утверждений, поэтому либо G = 1, либо 5 = 1. Истинным будет высказывание, то есть высказывание «Сосуд греческий и изготовлен не в 5 веке или сосуд не греческий и изготовлен в 5 веке». Аналогично, высказывание Бориса можно представить формулой и высказывание Григория формулой.

Полученные формулы можно рассматривать как логические уравнения и решать систему:

.

Первое высказывание умножается на второе:

.

Произведение — ложно потому, что сосуд не может быть изготовлен одновременно в Греции и Финикии, произведение — ложно потому, что сосуд не может быть изготовлен одновременно в 3 и 5 вв. После исключения этих высказываний получается следующее уравнение:. Это уравнение умножается на третье логическое уравнение составленной системы:

.

Высказывания исключены как ложные. Из полученного высказывания следует, что «Сосуд изготовлен в Финикии и сосуд изготовлен в 5 веке». Это утверждение согласуется с данными поставленной задачи.

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

«Методы эти позволяют Вам обрести ясность мысли, способность находить собственное оригинальное решение трудных задач, вырабатывают у Вас привычку к систематическому мышлению и, что особенно ценно, умение обнаруживать логические ошибки, изъяны и пробелы тех, кто не пытался овладеть привлекательным искусством логики. Попытайтесь. Вот все, о чем я прошу вас», — Льюис Кэрролл (псевдоним Чарльза Лютвиджа Доджсона (1832–1898)) — известный английский математик и литератор.

5.Упражнения к главе 1

1.Какие из множеств А = {x.y.p,g,5,7}; B = {x: x — песчинка в Европе}; C = {x: x кратно 3}; D = {x: x — число между 0 и 1} являются конечными, а какие бесконечными?

Ответ: А и В — конечные, С и D — бесконечные.

2.Какие пары следующих множеств не пересекаются: A = {x,y,z};

B = {1,2,4,y}; C = {a,b,c,z}; D = {1,x,a}; F = 2,3,b,c}?

Ответ: AC; BC; BD; DF; AF.

3. Какие из следующих множеств являются пустыми:

X = {x: x есть решение уравнения x — 2 = 0}; Y = {y: y кенгуру в Антарктиде};

W = {x: x человек, возраст которого> 200 лет}?

Ответ: Y;W.

4. Какие из следующих множеств: A = {1,2,a,b}; B = {1,0,2,a,b}; C = {b,b,2,1,a,a}; D = {1,2,3,a,b} равны?

Ответ: А = С.

5. Запишите множества В = {xN: x <7} и C = {xR: +9 = 0} в элементах (в список).

Ответ: B = {1,2,3,4,5,6}; C = {}.

6. Каково соотношение между множествами: A = {xR:2x = 3}; B = {xQ:2x^2 — 7x +6 = 0}?

Ответ: А = {3/2}; B = {2, 3/2}; A*** B.

Ответ: А = {3/2}; B = {2, 3/2}; A B.

6.Тест по теме «Элементы множеств»

1. Что означает это равенство?

А = {х, у,…,z}

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

2.Что можно сказать о множестве В по отношению ко множеству А?

3. Какое действие над множествами А и В изображено на рисунке?

4. Какое действие над множествами А и В изображено на рисунке?

5.Какое действие над множествами А и В записано математически?

6.Какое действие над множествами А и В записано математически?

7.Какое множество записано и что это означает?

8.Какие множества называются равными?

9.Как называется такое изображение?

10.Как называется множество:

а) коров, которые пасутся на лугу;

б) учителей, работающих в одной школе;

в) функций, графиками которых являются параболы.

Ответы:

1.Множество А состоит из элемементов х,у…,z.

2. Множество А включает в себя множество B.

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

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

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

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

7.Пустое множество.

8. Множества состоящие из одинаковых элемементов.

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

10. a) стадо; б) педагогический коллектив; в) квадратная функция.