Фигура I Фигура II Фигура III Фигура IV

1. М P 1. P M 1. M P 1. P M

 

2. S M 2. S M 2. M S 2. M S

 

3. S – P 3. S – P 3. S – P 3. S – P

Рис. 3.

На всех фигурах рис. 3 цифрой 1 обозначена большая посылка, цифрой 2 – меньшая посылка, а цифрой 3 – заключение. Буква S обозначает меньший термин, буква P – больший, а буква M – средний термин.

Если в некоторой фигуре указать конкретно тип суждений, стоящих на местах посылок и заключения, то получим разновидность данной фигуры. Так, если в фигуре I положить, что большая посылка, меньшая посылка и заключение – это суждения типа A, то получим такой силлогизм:

1. Всякий M есть P

2. Всякий S есть M

3. Всякий S есть P.

Такого рода разновидности фигур называются их модусами. В каждой фигуре имеется 64 модуса, а во всех четырех фигурах их будет 256. Однако не во всех модусах заключение логически следует из посылок, т.е. оно не будет истинным. Поэтому правильными модусами будут только те из них, для которых имеет место логическое следование. А таких правильных модусов существует всего 24.

Для того чтобы правильные модусы было легче запомнить в средневековье для них придумали специальные словесные названия. Причем эти названия таковы, что все гласные буквы в них, идущие слева направо, соответствуют типу суждения большей посылки, меньшей посылки и заключению. Так, приведенный выше модус фигуры I называется B a rb a r a, что соответствует типам суждений большой, малой посылок и заключения AAA.

При изучении логики средневековым студентам приходилось буквально «зазубривать» наименования этих модусов. Чтобы иметь представление насколько это было нелегко, приведем названия 24-х правильных модусов из всех четырех фигур.

Фигура I	Фигура II	Фигура III	Фигура IV
Barbara (AAA)	Baroko (AOO)	Bokardo (OAO)	Camenos (AEO)
Celarent (EAE)	Cesare (EAE)	Disamis (IAI)	Dimaris (IAI)
Darii (AII)	Camestres (AEE)	Datisi (AII)	Camenes (AEE)
Ferio (EIO)	Festino (EIO)	Ferison (EIO)	Fresison (EIO)
Barbari (AAI)	Camestrop (AEO)	Daparti (AAI)	Bramantip (AAI)
Celaront (EAO)	Cesaro (EAO)	Felapton (EAO)	Fesaro (EAO)

Приведем в качестве примера для каждой из 4-х фигур категорических силлогизмов по одному модусу.

Фигура I

Все жидкости (M) теплопроводны (P).

Вода (S) – жидкость (M).

Вода(S) – теплопроводна (P).

 

Фигура II

Все ужи (P) – пресмыкающиеся (M).

Это животное (S) не является пресмыкающимся (M).

Это животное (S) не является ужом (P).

Фигура III

Все углероды (M) – простые тела (P).

Все углероды (M) – электропроводны (S).

Некоторые электропроводники (S) – простые тела (P).

Фигура IV

Все киты (P) – млекопитающие (M).

Ни одно млекопитающее (M) не есть рыба (S).

Ни одна рыба (S) не является китом (P).

Нетрудно убедиться, что фигура I соответствует модусу AAA, фигура II – модусу AEE, фигура III – модусу AAI, а фигура IV соответствует модусу AEE. Все приведенные умозаключения правильные, так как они входят в группу из 24-х правильных модусов.

Подводя итог краткому рассмотрению некоторых сведений из формальной логики, можно отметить следующее. Формальная логика знакомит с правилами различных видов умозаключений. Она дает в руки инструмент, который позволяет всегда получать истинное логическое следствие (заключение – высказывание) из истинных посылок. Если же при истинных посылках получаются ложные заключения, то значит, были применены неправильные формы умозаключений.

Поскольку предметом данного пособия является математическая логика, то следует указать два момента:

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

2. Для специальностей направления «Информатика и вычислительная техника» курс математической логики и теории алгоритмов не является обычным общеобразовательным курсом. Он является одной из тех специальных дисциплин, знания которой необходимы для решения задач создания систем искусственного интеллекта.

3.

Вопросы для самоконтроля

1. В чем сущность теории силлогизмов, созданной Аристотелем?

2. Назовите и охарактеризуйте формы чувственного познания.

3. Назовите и охарактеризуйте формы абстрактного мышления.

4. Приведите схему записи умозаключений в формальной логике.

5. В чем различие таких понятий как истинность и правильность, ложность и неправильность?

6. Назовите основные формально-логические законы.

7. Раскройте содержательный смысл закона тождества.

8. Раскройте содержательный смысл закона противоречия.

9. Раскройте содержательный смысл закона исключенного третьего.

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

11. Приведите схему и поясните утверждающий способ рассуждения.

12. Приведите схему и поясните отрицающий способ рассуждения.

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

14. Приведите схемы и поясните отрицающе-утверждающий способ рассуждения.

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

16. Как устроен логический квадрат и в чем его сущность?

 

 

2. Элементы теории множеств

2.1. Понятие множества. Способы задания множеств

 

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

Однако такое положение сохранялось до тех пор, пока в математике не возникла необходимость рассмотреть это понятие более строго. Это сделал впервые немецкий математик Г. Кантор (1845 – 1918), который и является создателем теории множеств. Несмотря на относительно строгий подход к понятию множества, канторовская теория множеств считается наивной (в соответствии со «Словарем русского языка» С.И. Ожегова слово наивный употребляется в смысле простодушный, неопытный), поскольку позже обнаружилось, что в этой теории возникают противоречия, которые стали именоваться парадоксами. Некоторые из этих парадоксов мы рассмотрим в конце данного раздела.

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

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

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

N – множество всех натуральных чисел 1, 2, 3,…;

Z – множество целых чисел есть множество, полученное в результате добавления к множеству N новых объектов – числа нуль и отрицательных целых чисел, т.е. 0, – 1, – 2, … Говорят, что множество Z получено путем расширения множества N;

Q – множество рациональных чисел, получающееся как естественное расширение множества целых чисел путем добавления новых объектов. Такими новыми объектами являются рациональные дроби, которые могут быть представлены в виде отношения m/n взаимно простых (несократимых) натуральных чисел;

R – множество всех действительных (вещественных) чисел, получающееся дополнением множества Q иррациональными числами, т.е. числами, которые нельзя представить в виде простых дробей. Примерами иррациональных чисел являются и др., поскольку их нельзя представить в виде отношения m/n;

C – множество комплексных чисел. Дать простое пояснение получению множества комплексных чисел, как в предыдущих случаях, не удается. Укажем лишь, что один из способов построения множества C заключаетсяв расширении множества R путем присоединения к нему нового числового объекта – корня уравнения x² + 1 = 0.

Мы знаем, что комплексное число обозначается как a + bi, где a и b – действительные числа, а символ i, определяемый из условия i² = – 1, называется мнимой единицей.

Между множеством и его элементами существует простое отношение принадлежности, для обозначения которого используется символ . Так, если X некоторое множество, а x – его элемент, то пишут что читается так: «x принадлежит множеству X». Если элемент x не принадлежит множеству X, то пишут

Примеры:

Тот факт, что множество X состоит из конечного числа элементов x ₁, x ₂,…, x_n обозначается с помощью фигурных скобок при этом порядок записи элементов внутри фигурных скобок значения не имеет.

Множество может состоять из любого числа элементов: одного, двух и т.д. Более того, оказывается удобным считать множеством даже пустое множество, т.е. множество, не содержащее ни одного элемента. Пустое множество обозначают символом . Таким образом, если множество X не содержит ни одного элемента, то пишут

Два множества A и B считаются равными, т.е. A = B, если они состоят из одних и тех же элементов. В противном случае A ≠ B. При этом многократно повторяющийся элемент считается как один. Так { a, b, c } = { b, a, c } = { b, a, c, c, a }. Но { a, b, c } ≠{ a, 2, 3 }, так как эти множества состоят из разных элементов, хотя их мощности и равны. Не являются равными и множества {{ a, b }} и { a, b } так как множество {{ a, b }} состоит из одного элемента{ a, b }, который сам является множеством, а множество { a, b } состоит их двух элементов: букв a и b.

Исходя из приведенных примеров, следует, что нужно различать множество, состоящее из одного элемента, например множество { a } и сам элемент этого множества a.

Множества могут быть конечными и бесконечными. Множество является конечным, если каждому его элементу можно сопоставить некоторое конечное натуральное число. Иначе говоря, элементы конечного множества можно «пересчитать» за конечное число шагов n. Число элементов конечного множества X называют его мощностью и обозначают символом .

Множество, не являющееся конечным, называется бесконечным. Если для сравнения конечных множеств используются их мощности, то при сравнении бесконечных множеств дело обстоит несколько сложнее. В качестве «эталона» для сравнения бесконечных множеств используют простейшее бесконечное множество N всех натуральных чисел. При этом все бесконечные множества делятся на два класса: счетных и несчетных множеств.

Если бесконечное множество можно привести во взаимно однозначное соответствие с натуральным рядом чисел, то такое множество называют счетным. В противном случае его называют несчетным. Например, множество квадратов целых чисел 1, 2, 4, 9,…, n² является бесконечным, но счетным, так как оно приводится во взаимно однозначное соответствие с натуральным рядом чисел путем сопоставления каждому его элементу того числа натурального ряда, квадратом которого он является.

Примером несчетного множества является множество действительных чисел интервала 0 ˂ x ≤ 1. Это утверждение сформулировано и доказано Г. Кантором в виде теоремы. Суть ее доказательства состоит в том, что действительные числа, лежащие между нулем и единицей, представляются в виде бесконечных десятичных дробей. И как бы мы не нумеровали эти действительные числа, используя все натуральные числа, всегда найдется такое действительное число из указанного интервала, которое будет пропущено. Очевидно, что несчетным будет и множество действительных чисел, лежащих в любом интервале.

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

В таких случаях используют понятие «формы от x» или иначе высказывательной формы. Содержанием этого понятия является некоторое свойство, которое обозначают символом P, а множество X, все элементы которого обладают этим свойством, записывают одним из способов: { x | P (x)}, { x | и P (x)}, { | P (x)}. Так запись { | x > 0} означает множество всех таких целых чисел, которые обладают свойством быть больше нуля. Иначе говоря, это множество всех положительных целых чисел. Напомним, что множество Z содержит как положительные, так и отрицательные целые числа, а также число 0.

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

Множество {2, 3, 4, 5, 6, 7, 8, 9, 10}, заданное перечислением, в «форме от x» можно записать так: | . Множество всех четных натуральных чисел в «форме от x» можно задать в виде { x, n N | x = 2 n }. В форме перечисления это множество задать нельзя, так как тогда надо было бы перечислить бесконечное число четных чисел, что невозможно. Если же это множество записать, как это часто делают, в виде x = 2, 4,…,2 n,…, не оговаривая, какие значения принимает n, то такая запись будет некорректной, так как не ясно, какие значения принимает n. Если же для n указать значения, то мы снова приходим к «форме от x».

Упражнения

1. Равны ли множества:

1) {0, 1, 2} и {0, 2, 1}; 2) {0, 1} и {{0,1}}?

2. Даны множества: A = {0, 1}; B = {{0, 1}, 2}; и C = {{{0, 1}, 2}}.

Верны ли принадлежности 1) 2)

3. Перечислите все элементы множества, заданного в «форме от х»:

1) 2) ;

3) ; 4) ;

5) ; 6) .

4. Ниже приведены множества, заданные в «форме от x». Задайте эти множества, перечислением всех элементов:

1) ; 2) ; 3) ;

4) ; 5); ; 6) ;

7) ; 8) ; 9) .

5. Можно ли задать перечислением всех элементов множества:

1) ; 2) ; 3) ;

4) ?

6. Верны ли следующие соотношения:

1) 1Î{1,2}; 2) 3Ï{0,1}; 3) 3ÏÆ; 4) ÆÎÆ; 5) ÆÎ{Æ};

6) {0,1}Î{{{0,1},2},{1,2},0,1}; 7) {1,2}Ï{{1,2},1,2}; 8) {1,2}Î{{1,2}}?

Части множеств

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

 

Несмотря на то, что множество есть единое целое, оно, тем не менее, состоит из различимых объектов. Поэтому можно говорить об отдельных частях множества. Например, русские являются частью множества, составляющего все население России, а множество A = {0, 2, 4, 6, 8} четных цифр является частью множества B = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} всех цифр десятичной системы счисления.

В теории множеств для части множества вводится специальный термин – подмножество для указания отношения между множествами или их подмножествами – отношение включения. Если А и В множества, то говорят, что А включено в В (символически это записывается ), если каждый элемент множества A является и элементом множества B. В этом случае также говорят, что A является подмножеством множества B или, что B включает A (символически записывается ). Таким образом, символические записи или означают, что для каждого x, если , то .

Если и , то пишут и говорят, что множество A строго включено во множество B или B строго включает A .

Например: ,

Отношение включения обладает следующими основными свойствами:

– рефлексивность;

Если и , то A = B – симметричность;

если и , то – транзитивность.

Следует отметить, что нельзя смешивать отношение принадлежности, обозначаемое символом , и отношение включения, обозначаемое символами , . Символ принадлежности применяется для указания отношения между множеством и его элементами, а символы включения , – для указания отношения между множествами. Так, например, правильными будут записи: a) b) c) ; d) ;

e) .

Первая строка записей a) и b) не требует пояснений. Запись c) правильна, так как слева от символа стоит множество , но во множество оно входит как элемент. Записи d) и e) также правильны, так как символы включения и строгого включения применены к множествам соответственно. Очевидно, что запись – неправильна, так как символ здесь применен к множествам.

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

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

Множество-степень

 

В некоторых случаях необходимо знать не отдельные подмножества некоторого множества, а все подмножества этого множества. Множество всех подмножеств множества A называется множеством-степенью множества A и обозначается символом P (A). Таким образом, P (A) является сокращенным обозначением для «формы от x»

Например, если A = {1, 2, 3}, то

P (A) = { , {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, {1, 2, 3}}.

Интерес вызывает вопрос о мощности множества P (A). Нетрудно заметить, что перечисление всех подмножеств множества A получается перебором всех сочетаний пустого, одно, двух и трехэлементных подмножеств множества A. Если множество A состоит из n элементов, то мощность множества-степени P (A) будет определяться выражением

| P (A)| = (1)

где

(2)

а сочетания и определяют несобственные подмножества множества A (пустое множество и само множество A).

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

| P (A)| = . (3)

Вычисление при различных k для наглядности удобно выполнять по так называемому треугольнику Паскаля, который строится следующим образом. В вершине треугольника стоит единица, которая определяется по формуле (2) при n = k = 0. Для n = 1 число k будет принимать два значения: 0 и 1. Поэтому из формулы (2) мы получим два значения числа сочетаний: соответственно 1 и 1. Эти значения будут представлять основание первого треугольника.

Для n = 2 число k будет принимать три значения: 0, 1 и 2. Поэтому получаем три значения числа сочетаний – соответственно 1, 2 и 1. Они будут представлять основание второго треугольника. Аналогично для n = 3 будем иметь четыре значения для числа сочетаний – 1, 3, 3, 1, которые будут представлять основание третьего треугольника и т.д.

По треугольнику Паскаля очень просто вычисляются различные значения сочетаний, не используя формулу (2). Для получения каждого значения числа сочетаний в следующем основании треугольника нужно сложить предыдущее и последующее значения числа сочетаний из основания предыдущего треугольника.

Обобщение всего сказанного представим в виде таблицы 1, в первом столбце которой запишем различные значения n, во втором столбце – числа 2 ⁿ , в третьем столбце представим треугольник Паскаля, в четвертом – числа, получающиеся путем суммирования чисел, стоящих в основаниях соответствующего треугольника Паскаля или, что то же самое, рассчитанные по формуле (2).

Таблица 1

n		Треугольник Паскаля
		1 1
		1 2 1
		1 3 3 1
		1 4 6 4 1
		1 5 10 10 5 1
…	…	…	…

 

Из приведенной таблицы видим, что второй и четвертый столбцы табл. 1 полностью совпадают, что и доказывает формулу 3.