Всё для Учёбы — студенческий файлообменник
1 монета
zip

Лекции по Математической логике (Кулик Б. А.)

Логика естественных рассуждений

Пособие к курсу лекций по темам "Логика естественных рассуждений" и "Прикладная математика"

для студентов Санкт-Петербургского Университета Культуры и Искусств (СПбГУКИ)

Часть первая. Полисиллогистика

По материалам книги Б.А. Кулик. Логика естественных рассуждений. СПб, Изд-во "Невский диалект", 2001.

В подготовке данного курса лекций принимала участие студентка СПбГУКИ Полина Иванова

Санкт-Петербургский Университет Культуры и Искусств

2008 Оглавление

Предисловие 2

1. Суждение 3

2. Основные понятия алгебры множеств 5

3. E-структуры: определение и основные свойства 12

4. Графы и частично упорядоченные множества 15

5. Анализ E-структур с помощью графов 21

6. Коллизии в рассуждениях 24

7. Инварианты E-структур 29

8. Экзистенциальные суждения 33

9. Формирование и проверка гипотез 39

10. Отрицания и антитезы в E-структурах 48

11. Абдуктивный вывод 51

Заключение 53

Список литературы 55

Предисловие Наша жизнь так устроена, что мы постоянно вынуждены в чем-то убеждать друг друга, побуждать собеседника к каким-то действиям или обосновывать целесообразность своих поступков или своего бездействия. Это происходит не только в быту, но и во всех сферах: в науке, трудовой деятельности, политике и т.д. Побуждать можно силой, угрозами – это к логике не имеет отношения. Можно убеждать собеседника, используя обман или с помощью психологического воздействия или методов «лингвистического программирования». Это тоже не логика, а, скорее, методы PR технологий. Хотя обман нередко распознается с помощью логического анализа. И в житейской практике логика нужна каждому человеку, хотя бы для того, чтобы не стать жертвой обмана и осуществлять критический анализ тех своих заблуждений, которые причиняют нам крупные или мелкие неприятности.

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

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

Корректность методов логического анализа в настоящее время трактуется неоднозначно. Многие считают, что методы логического анализа корректны в силу того, что они проверены многовековой практикой применения логики. Для логики, являющейся фундаментом познавательных способностей человека, такой «эмпирический» критерий явно недостаточен. Здесь мы будем использовать другую, в настоящее время менее популярную, точку зрения: логические методы корректны той мере, в какой они математически обоснованы.

Среди специалистов по логике до сих пор идут дискуссии о том, как преподавать логику. В основном эти дискуссии вращаются вокруг проблемы соотношения логики и математики. Наиболее распространенными в настоящее время являются два подхода: 1) логика вполне самостоятельная наука, лежащая в основе всех наук, включая математику; 2) в основе логики лежит теория формальных систем (ТФС), которая начала бурно развиваться в начале XX столетия. С точки зрения преподавания логики оба этих подхода имеют ряд недостатков: они трудно усваиваются студентами и к тому же плохо приспособлены для анализа естественных рассуждений и решения логических задач. В предлагаемой методике, основные положения которой опубликованы в научных изданиях [2-5], излагается иной подход, в котором основные логические соотношения и способы анализа основаны на простых математических структурах. Это позволяет использовать при анализе рассуждений простые методы, подобные вычислениям, и, кроме того, дает возможность учащимся освоить некоторые основополагающие понятия современной математики, которые в настоящее время используются не только в логике, но и в многих других областях и, в частности, в информационных технологиях.

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

Анализ показывает, что полисиллогистика охватывает лишь незначительную часть структур и методов, применяющихся в настоящее время в анализе рассуждений. Более емкими по своим аналитическим возможностям являются методы, изложенные в разделе «Алгебра кортежей». Эти методы используются и в математической логике, и в системах искусственного интеллекта. Однако подробное рассмотрение полисиллогистики не только дань уважения к системе рассуждений, просуществовавшей более двух тысячелетий, но и возможность проследить тесные связи между математикой и логикой. Здесь же рассматриваются основные математические структуры (множества, графы, частично упорядоченные множества), которые лежат в основе алгебраического подхода в логическом анализе рассуждений и обоснований.

В подготовке данного курса лекций принимала активное участие студентка СПбГУКИ Полина Иванова. С ее помощью в тексте были исправлены неточности и опечатки и, кроме того, своими вопросами и замечаниями она помогла мне сделать изложение этого курса более понятным для студентов.

1. Суждение

В основе классической логики лежит структура, которая называется «суждение». Это понятие было разработано Аристотелем (384-322 гг. до н.э.). Им была создана система анализа рассуждений, которая в настоящее время известна как силлогистика.

В общем случае суждение – это некоторое высказывание, в котором сформулирован какой-то фрагмент наших знаний или представлений о мире (например, «Некоторые грибы ядовиты»). В Аристотелевой силлогистике принято, что каждое суждение состоит из двух частей – «субъекта» и «предиката». Логический смысл суждения заключается в том, что «предикат» рассматривается как присущий данному «субъекту» признак или условие его существования. «Предикат» может быть выражен и в отрицательной форме (например, «Ни один пингвин не летает»). «Субъект» суждения обычно сопровождается логическими «приставками» (в логике они называются кванторами): «все» или «некоторые». В силлогистике отрицание, как правило, к «субъектам» не применяется и в основном используется для предикатов, а кванторы применяются только к "субъектам".

В нашем подходе мы будем использовать суждение в более широком смысле. Во-первых, в одном суждении может быть более одного «предиката» и, во-вторых, в суждениях разрешается использовать отрицание не только для «предикатов», но и для «субъектов» —такое допущение, кстати, используется и в «Символической логике» Л. Кэрролла [1].

В классической силлогистике для суждения предусмотрено только четыре формы: «Все A есть B», «Все A не есть B», «Некоторые A есть B» и «Некоторые A не есть B». Эти формы (или типы) были выделены еще Аристотелем. Они соответствуют обычным предложениям, в которых выражаются отношения между частью и целым, видом и родом, объектом и свойством. Если внимательно присмотреться к предложениям естественного языка, то окажется, что многие из них можно без потери смысла представить в виде таких отношений. Сама грамматическая структура предложения, сформированная в течение многих тысячелетий существования человечества, во многом соответствует структуре этих отношений.

Каждое "нормальное" предложение состоит из подлежащего, сказуемого и второстепенных членов предложения (определений, дополнений и обстоятельств места, времени и т.д.). В такой общепринятой грамматической форме выражаются многие предложения в житейских разговорах, литературных произведениях, а также в философских и научных рассуждениях на всех национальных языках. В лингвистике известно немало структурных членений предложения. Мы здесь рассмотрим вариант, в котором выделяются три основных структурных элемента простого предложения: подлежащее, определение и сказуемое вместе с дополнениями и обстоятельствами, которые находятся под его управлением (например, «родился в Курске», «оказался не у дел», «приедет во вторник», «является представителем фирмы IBM» и т.д.).

При анализе логической формы суждения подлежащее во многих случаях можно рассматривать как субъект суждения. Предикатами суждения являются конструкции, состоящие из сказуемых с управляемыми ими обстоятельствами или дополнениями. Например, в предложении «Кенгуру живут в Австралии» субъектом является кенгуру как один из видов животных, а предикатом – существа, живущие в Австралии.

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

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

Заметим, что в форме суждения можно выразить не только многие предложения естественного языка, но и такие логические конструкции, как определения или толкования терминов; факты реальной жизни; многие математические теоремы; законы природы и т. д. Каждый предикат суждения по смыслу является необходимым признаком или необходимым условием существования субъекта. Предикаты в логике тесно связаны со следствиями: если доказано, что B является предикатом A, то тем самым доказано, что B является следствием A.

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

2. Основные понятия алгебры множеств.

Алгебра множеств лежит в основе многих разделов современной математики. Для нее практически невозможно установить точную дату открытия и назвать имя первооткрывателя. Алгебра множеств постепенно развивалась на фоне многочисленных попыток найти строгое математическое основание для Аристотелевой логики. Некоторые предпосылки этой алгебры содержатся в трудах Лейбница. В разработку основ этой алгебры внесли значительный вклад многие известные логики и математики (Ж. Д. Жергонн, А. де Морган, Дж. Венн и др.). Но особая заслуга в ее развитии и распространении принадлежит Леонарду Эйлеру.

В 1736 г. в "Письмах к германской принцессе о различных физических и философских материях" Л. Эйлер в популярной форме изложил свое понимание Аристотелевой силлогистики. При этом он использовал наглядные схемы, которые впоследствии получили название "круги Эйлера". В дальнейшем круги Эйлера стали использовать не только в учебных курсах по логике, но также и при изложении азов многих основополагающих разделов современной математики, в которых используется алгебра множеств (например, в [6]). Здесь мы также воспользуемся этими наглядными отображениями, позволяющими достаточно быстро овладеть абстрактными понятиями алгебры множеств.

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

В основе силлогистики лежат простые суждения, представленные четырьмя типами: A – общеутвердительное (все X есть Y); E – общеотрицательное (все X не есть Y); I – частноутвердительное (некоторые X есть Y); O – частноотрицательное (некоторые X не есть Y). Отметим, что в трудах Аристотеля смысл суждений отличается от общепринятого – этот смысл вместе с обозначениями утвердился в логике после работ известного схоласта Петра Испанского. Сам Аристотель не употреблял в суждениях двусмысленную связку «есть» и формулировал суждения следующим образом:

A: Y присуще всем X

E: Y не присуще всем X

I: Y присуще некоторым X

O: Y не присуще некоторым X

Термины X и Y можно представить как некоторые совокупности (множества, классы) в виде кругов Эйлера. Жергонн выделил 5 возможных соотношений между ними (рис. 1).

Рис. 1

Каждый тип Жергонновых отношений имеет собственное название:

G1 – совпадение или равнозначность;

G2 – левостороннее включение;

G3 – частное совпадение;

G4 – правостороннее включение;

G5 – несовместимость.

Жергонн показал, что каждый тип Аристотелевского суждения соответствует некоторым типам этих отношений, в частности:

- типу A соответствует G1 или G2;

- типу E соответствует G5;

- типу I: соответствует G1 или G2 или G3 или G4;

- типу O: соответствует G3 или G4 или G5.

Например, суждение типа I означает, что некоторая непустая часть множества или класса X содержится в Y. Посмотрев на рисунок, нетрудно убедиться, что этому условию удовлетворяют все типы Жергонновых отношений кроме G5. В логике слово "некоторые" используется в широком смысле: "хотя бы один, но не исключено, что и все". Жергонновы отношения часто использовались для строгого обоснования не только правил вывода для простого силлогизма, в котором в качестве посылок используются только два суждения, но и для более сложных умозаключений, когда в качестве посылок допускается произвольное число суждений – в этом случае мы имеем дело с полисиллогизмом. Вершиной анализа такого рода можно считать работы английского логика и философа Дж. Венна (1834–1923).

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

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

1) носитель – некоторая совокупность объектов (например, числа, геометрические фигуры, слова, множества и т.д.);

2) совокупность отношений (например, больше, меньше, равно и т.д);

3) совокупность операций (например, сложение, умножение, пересечение и т.д).

Заметим, что смысловая разница между отношением и операцией заключается в следующем: если задано некоторое отношение между объектами, то о нем можно только сказать, истинно оно для данных объектов или нет (например, отношение "2 > 3" является ложным отношением), в то время как в результате некоторой операции с объектами получается некоторый новый объект (например, "2+3=5").

В алгебре множеств носителем является некоторая совокупность множеств. Основными понятиями алгебры множеств считаются множество и элемент. Соотношение между ними называется отношением принадлежности и обозначается знаком "". Запись

bA

переводится с символического языка как "b является элементом множества A" или "элемент b принадлежит множеству A". Если известны все элементы множества (например, a, b и c), то общепринятой является такая запись множества:

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

Множества могут быть заданы двумя способами: с помощью формулировки характерных признаков (например, множество K содержит только четные числа, не превышающие числа 8) или с помощью перечисления элементов (например, K = {0, 2, 4, 6, 8})

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

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

"" – строго включено;

"" – включено или равно.

Запись AB означает, что множество A включено в множество B, т.е. все элементы множества A являются одновременно элементами множества B, но при этом невозможно равенство этих множеств. Запись AB означает, что множество A включено в множество B, но при этом не исключается, что они могут быть равными. Изображение отношения включения (AB) с помощью кругов Эйлера показано на рисунке 2. В данном случае не обязательно использовать правильные круги. Для изображения множества может подойти любая замкнутая фигура.

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

P ={a, b, c, d, e}; Q ={b, d, a}; R ={a, c, f},

то, сравнивая элементы этих множеств, можно утверждать, что QP, но в то же время отношение RP для этих множеств неверно, так как элемент f из множества R не является элементом множества P.

Порядок перечисления элементов для множеств несущественен. Например, множества {b, d, a}; {a, b, d}; {d, a, b} – это по сути одно и то же множество. Если же порядок перечисления множеств является существенным, то в этом случае мы имеем дело не с множествами, а с последовательностями или с упорядоченными множествами (некоторые сведения о них приведены ниже). Математические свойства последовательностей существенно отличаются от математических свойств множеств.

Заметим, что различие отношений принадлежности и включения можно иллюстрировать следующим примером. Допустим, aP, из чего следует, что a является элементом, а P – множеством. Можно ли в этом случае записать a  P? Оказывается, нельзя, потому что отношение включения применимо только для двух множеств. Правильной в этом случае является запись {a}  P, в которой слева записан не элемент, а одноэлементное множество.

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

Определение 1. Множества A и B равны, если справедливо как AB, так и BA.

Заметим, что в математике это определение является доказанной теоремой. Если множества связаны отношениями AB или AB, то в этом случае множество A называют подмножеством множества B. Среди всех возможных подмножеств произвольного множества A обязательно содержится также и само множество A. Другими словами, для любого множества A всегда справедливо AA.

В алгебре множеств особо выделяется и часто используется множество, которое называется «пустое множество» (обозначается «»). Интуитивно пустое множество означает множество, не содержащее никаких элементов. Но это интуитивное определение не раскрывает полностью его сути и роли в алгебре множеств. В большей степени его суть раскрывается в следующем предложении, которое можно отнести к одной из аксиом алгебры множеств:

Пустое множество включено в любое множество.

В математических рассуждениях, когда нам надо доказать, что при заданных условиях множество X не существует (или существует), мы сводим доказательство существования к доказательству отношения X= (или X). Часто такой метод позволяет намного упростить доказательство.

Если множество задано перечислением элементов, то можно записать совокупность всех подмножеств этого множества. Например, для множества A={a, b, c} такая совокупность состоит из восьми подмножеств:

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

Обратите внимание, что само множество А является подмножеством самого себя. Доказано простое соотношение, позволяющее сразу же узнать общее число всех возможных подмножеств множества, содержащего ровно N элементов. Оказывается, что для любого N такое число равно 2N. Например, для нашего множества A={a, b, c} число всех возможных подмножеств равно 23.

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

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

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

Определение 2. Дополнением множества A называется множество , содержащее все элементы универсума, которые не являются элементами множества A.

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

Пример 1. Пусть U={a, b, c, d} и P={a, c}. Тогда ={b, d}.

Определим еще две основные операции – пересечение и объединение множеств.

Определение 3. Пересечением множеств A и B называется множество C, которое содержит все элементы, принадлежащие одновременно как A, так и B.

Операция пересечения множеств обозначается символом "". Символически определение 3 можно записать как формулу

C = AB.

Например, пересечением множества всех студентов данного вуза и множества всех участников КВН, является множество студентов данного вуза, участвующих в КВН. Другой пример: пересечением множества всех чисел, делящихся на 2, и множества всех чисел, делящихся на 3, является множество всех чисел, делящихся на 6.

В логике операции пересечения соответствует логическая связка «И» (обозначается как  или ). Если речь идет об объектах со свойствами P или Q, то логическая формула PQ означает, что речь идет только об объектах, которым присущи оба этих свойства. Если, допустим, свойствам P и Q соответствуют некоторые множества SP и SQ, то пересечение этих множеств SPSQ, будет состоять из элементов, каждому из которых одновременно присущи свойства P и Q. При вычислении пересечения двух множеств, необходимо выбрать из этих множеств только те элементы, которые содержатся как в том, так и в другом множествах.

Пример 2. Пусть A={a, b, c, d} и P={a, c, f}. Тогда AP = {a, c}.

Возможна ситуация, когда при вычислении пересечения двух множеств оказывается, что эти множества не содержат общих элементов. Тогда пересечением этих множеств является пустое множество. Например, Q={a, c,} и R={b, d}. Тогда Q  R = .

Определение 4. Объединением множеств A и B называется множество C, все элементы которого являются элементами хотя бы одного из этих множеств.

Операция объединения множеств обозначается символом "". Символически определение 4 можно записать как формулу

C=AB

В логике операции объединения соответствует логическая связка «ИЛИ» (обозначается «»). Если речь идет об объектах со свойствами P или Q, то логическая формула PQ означает, что речь идет только об объектах, которым присуще хотя бы одно из этих свойств. При этом допускается, что объекты, которым присущи оба этих свойства, также относятся к этому классу объектов.

Пример 3. Пусть A={a, b, c, d} и P={a, c, f}. Тогда AP = {a, b, c, d, f}.

Обратите внимание, что в примере 3 элементы a и c, которые содержатся в каждом из множеств A и B, в объединении C не удваиваются, а содержатся как однократные. В математике и ее приложениях иногда используют множества с кратными элементами (они называются мультимножествами), но нам такие множества не понадобятся. В таких множествах нарушаются некоторые законы обычной алгебры множеств.

Операции дополнения, пересечения и объединения являются основными операциями алгебры множеств.

Определение 5. Разностью множеств A и B называется множество C=A\B, которое содержит только те элементы множества A, которые не являются одновременно элементами множества B.

Пример 4. Пусть A={a, b, c, d} и B={a, c, f}. Тогда A\B = {b, d}.

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

A\B = A .

Если в примере 4 задать универсум, например, U = {a, b, c, d, e, f}, то нетрудно убедиться в справедливости этого равенства:

= {b, d, e}; тогда A\B =A = {b, d}.

В то же время операцию дополнения можно выразить с помощью операции разности: =U\A. На рисунке 3 соответствующие операции над множествами изображены с помощью «кругов Эйлера». Серым цветом показаны результаты операций.

Рис. 3

Здесь хотелось бы обратить внимание на следующее важное обстоятельство. Для множеств A и B, у которых нет общих элементов, справедливы следующие соотношения:

AB =  ; A  ; B  .

Ситуацию, соответствующую этим соотношениям, можно наглядно отобразить с помощью диаграммы Эйлера (рис. 4).

Рис. 4

Теперь у нас вполне достаточно понятий для того, чтобы отобразить в виде математической формулировки заданные суждения. Например, суждение "Все члены палаты лордов носят титул пэра" мы расчленяем на субъект "члены палаты лордов" (A) и предикат "носят титул пэра" (B). Тогда математической формулой данного суждения будет

A  B. Это означает, что все члены палаты лордов включены в множество тех, кто носит титул пэра. Более сложное суждение, например, "Все члены палаты лордов носят титул пэра и находятся в здравом рассудке" можно выразить, используя два предиката: "носят титул пэра" (B) и "находятся в здравом рассудке" (С). Тогда мы получим следующую математическую формулировку:

A(B  C). (1)

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

A(B  ), (2)

где D – предикат "принимают участие в скачках на мулах".

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

Рис. 5 Рис. 6

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

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

Законы алгебры множеств – это по сути теоремы, которые выводятся из основных определений и аксиом. Часто приводятся 26 или 28 законов алгебры множеств. Здесь мы приведем без доказательства лишь некоторые из них, необходимые для ясного понимания дальнейшего. Пусть A, B, C – некоторые произвольные множества в универсуме U. Тогда законами алгебры множеств являются следующие соотношения между ними.

1. =A.

Пример 5. Пусть U={a, b, c, d} и P={a, c}. Тогда ={b, d} и ={a, c}=P.

В алгебре множеств это соотношение (двойное дополнение) носит название закон инволюции. В логике этот закон известен под названием закон отрицания отрицания (или закон двойного отрицания): не (не-A) – то же самое, что и A.

2. A  =  (множество и его дополнение не имеют общих элементов)

В логике этому закону соответствует закон непротиворечия (утверждение и его полное отрицание логически несовместимы).

3. A  = U.

В логике этому закону соответствует закон исключенного третьего (совмещение любого утверждения и его полного отрицания не допускает присутствия какого-либо третьего промежуточного варианта).

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

4. = U; 5. = 

6. A = ; 7. A = A;

8. AU = A; 9. AU = U.

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

10. Если AB , то справедливы следующие соотношения:

10a. AB = A; 10b. AB = B;

10c. B = U; 10d. A = .

Соотношение 10d можно выразить также с помощью операции разности множеств:

10e. Из AB следует A\B = .

Следующие законы в логике и алгебре множеств называются законами де Моргана:

11a. =  ; 11b =  .

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

12a. Если AB и BC, то AC (закон транзитивности включения);

12b. Если AB, то справедливо также и  (закон контрапозиции).

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

Пусть нам необходимо вывести некоторые законы для двух множеств X и Y. Рассмотрим диаграмму Эйлера (рисунок 7), на которой изображены эти множества и объемлющий их универсум (U).

Рис. 7 Выделим на диаграмме участки a, b, c и d, которые не имеют внутренних границ, т.е. выполним разбиение нашего универсума на непересекающиеся друг с другом множества. Такое разбиение позволяет нам представить эти множества как элементы, из которых состоят универсум U и множества X и Y. Тогда для них справедливы соотношения:

U = {a, b, c, d}; X = {a, b}; Y = {b, c}.

Примем эти соотношения в качестве исходных данных и докажем для этого общего представления данной системы из двух множеств один из законов де Моргана =  . Тогда получим:

1) XY = {b}; 2) = {a, c, d};

3) = {c, d}; 4) = {a, d};

5)  ={a, c, d};

6) сравнивая 2 и 5, заключаем, что =  , что и требовалось доказать.

Закон транзитивности (12a) интуитивно понятен. Рассмотрим обоснование закона контрапозиции (12b). Схема на рисунке 7 нам не подходит, так как между множествами X и Y нет соотношения включения. Однако, если убрать из схемы область a, то получим то, что нам нужно: X  Y. Полученный результат можно выразить в виде следующих равенств:

U = {b, c, d}; X = {b}; Y = {b, c}.

Приступим к доказательству. Для этого вычислим

1) = {c, d}; 2) = {d};

3) сравнивая и , убедимся, что  , что и требовалось доказать.

3. E-структуры: определение и основные свойства

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

Пример 6. Пусть задана следующая совокупность суждений:

1) Всякие малые дети неразумны;

2) Все, кто укрощает крокодилов, заслуживают уважения;

3) Все неразумные люди не заслуживают уважения.

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

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

Математик и логик Чарльз Л. Доджсон (многим он известен как Льюис Кэрролл – автор знаменитых сказок про Алису), разработал оригинальную методику решения не только силлогизмов, но и полисиллогизмов. Наша методика существенно отличается от методики Кэрролла, но начальные этапы решения таких задач почти полностью совпадают. С самого начала надо определить основные термины, из которых состоит система посылок, ввести для них обозначения и выбрать подходящий универсум. Здесь ясно, что основными терминами данной задачи являются следующие: «малые дети» (C), «разумные люди» (S), «те, кто укрощает крокодилов» (T) и «те, кто заслуживает уважения» (R). Очевидно, что эти основные термины представляют какие-то множества в универсуме «люди». Их отрицаниями соответственно будут следующие термины: «не малые дети» ( ), «неразумные люди» ( ), «те, кто не укрощает крокодилов» ( ) и «те, кто не заслуживает уважения» ( ).

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

1) C (множество малых детей включено в множество неразумных людей);

2) TR (множество укротителей крокодилов включено в множество людей,

заслуживающих уважения);

3)  (множества неразумных включено в множество не заслуживающих уважения).

Сразу отметим, что в состав терминов системы мы обязательно включаем не только «позитивные» термины (C, S, T и R), но и их отрицания (для множеств – дополнения): , , и . Тем самым мы определили некоторую структуру, которая состоит из системы множеств S = (, U, C, S, T, R, , , , ) и некоторых отношений включения между этими множествами, формулировка которых содержится в посылках. Дадим более общее и более точное определение этих структур.

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

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

Теперь дадим определение логической структуры Эйлера (сокращенно E структуры).

Определение 7. E-структурой называется совокупность терминов, соотношения между которыми определяются некоторым множеством суждений, называемых посылками.

Таким образом, пример, приведенный в начале раздела, можно математически выразить как E структуру с множеством базовых терминов L = {C, S, T, R, , , , } и заданными посылками. В дальнейшем обозначение базовых терминов и их отрицаний (что в данном случае соответствует дополнениям соответствующих множеств) мы будем называть литералами.

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

Следующим шагом после уточнения терминологии при анализе E-структур является вывод следствий. Для любой системы логического вывода необходимы по крайней мере два компонента: 1) формальные правила, с помощью которых в этой системе можно записывать исходные посылки на языке математики и 2) правила логического вывода, с помощью которых из произвольно заданных посылок можно получить следствия. Тем самым мы как бы представляем каждую конкретную E-структуру аксиоматической системой, в которой посылки играют роль аксиом.

Но получение всех возможных следствий не является завершающим этапом анализа. Нам еще предстоит освоить методы, которые позволяют определить, является ли наша система корректной и содержит ли она неопределенности. Методы решения этих и других задач мы рассмотрим в следующих разделах, а сейчас перейдем к правилам вывода. При определении этих правил мы будем использовать некоторые законы алгебры множеств и, в частности, те законы, которые устанавливают системные свойства отношения включения (в предыдущем разделе им присвоены номера 12a и 12b). Здесь мы полностью отходим от методики Л. Кэрролла. Сходство заключается лишь в том, что в своей методике Л. Кэрролл также использовал неявно некоторые законы алгебры множеств.

Пусть X, Y и Z – некоторые базовые термины (литералы) E-структуры.

Определение 8. Правилами вывода E-структуры являются следующие:

Правило С (контрапозиции): из XY следует  ;

Правило T (транзитивности): из XY и YZ следует XZ.

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

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

C1: S (следует из C по правилу контрапозиции);

C2:  (следует из TR по правилу контрапозиции);

C3: RS (следует из  по правилу контрапозиции).

Здесь надо только учесть, что мы при выводе следствий по правилу контрапозиции используем иногда и закон двойного отрицания. Так, если мы из первой посылки получили по правилу C следствие  , то из равенства = S мы получаем S  .

Можно теперь перевести наши следствия с математического языка на обычный. Например, S  переводится как «Все разумные люди не являются малыми детьми». Но продолжим вывод следствий – у нас в запасе еще есть правило транзитивности. Из всех посылок и полученных следствий выберем пары суждений, у которых левая часть первого суждения полностью совпадает с правой частью другого суждения. Получим такие пары:

(C ,  ); (TR, RS); (  ,  ); (RS; S ).

Из них по правилу T получим еще четыре следствия:

C4: C ; C5: TS;

C6:  ; C7: R .

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

C8: C ;

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

Самыми интересными, по-видимому, являются следствия, полученные на последнем этапе процедуры вывода. Если переведем их на обычный язык, то получим следующие суждения: «Все малые дети не укрощают крокодилов» и «Все, кто укрощает крокодилов, не являются малыми детьми». Задача решена, но хотелось бы, чтобы инструменты для ее решения были бы проще. В качестве этих инструментов можно использовать такие математические структуры как графы и частично упорядоченные множества, о которых идет речь в следующем разделе.

4. Графы и частично упорядоченные множества

Обе структуры, указанные в названии раздела, объединяет то, что они являются частными случаями бинарных отношений. А как понимается математическое отношение? Наглядно любое отношение можно представить в виде таблицы с произвольным числом строк и колонок. Более строгое определение отношения будет приведено далее. Если таблица содержит только две колонки, то такая таблица представляет бинарное отношение.

Пусть задано множество каких-то объектов и из этих объектов по какому-то определенному принципу формируются пары. Например, дано некоторое множество людей, а пары в нем выбираются по такому принципу: первый элемент пары – некий человек, а второй - один из его родителей. При этом один и тот же человек может присутствовать в двух и более парах, например, когда один и тот же человек имеет двоих, троих или более детей. Например, три пары в этом отношении (Иван, Мария), (Дарья, Мария), (Глеб, Мария) означают, что Иван, Дарья и Глеб – дети Марии. В качестве математического примера бинарного отношения можно привести пары, составленные из некоторого множества чисел, при этом первое число в каждой паре меньше второго. Это пример бинарного отношения "меньше". Другой пример: задана некоторая система множеств, а бинарное отношение в этой системе формируется из пар множеств по принципу: первое множество включено во второе множество – это пример бинарного отношения "включение множеств".

4.1. Графы

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

Рассмотрим пример. Пусть задано множество вершин

V = {a, b, c, d, e},

из которого сформировано некоторое множество пар

E = {(a, b), (a, c), (b, d), (c, a), (c, e)}.

Множество пар E, сформированное из множества V вершин, является примером бинарного отношения. Преобразуем это бинарное отношение в схему. Для этого изобразим на листе бумаги все его вершины произвольным образом и соединим эти вершины линиями со стрелками так, чтобы каждая стрелка выходила из первого элемента пары и входила во второй элемент пары (см. рисунок 8). При этом, если окажется, что некоторая пара вершин соединяется стрелкой в одну и в другую сторону, то мы вместо линий со стрелками нарисуем линию без стрелок (для нашего примера это пары (a, c) и (c, a)). С учетом этого дугами в графе являются соединительные линии со стрелками в одну сторону, а ребрами – соединения без стрелок или со стрелками, направленными в обе стороны. Можно считать, что каждое ребро содержат пару разнонаправленных дуг.

Рис.8 Каждая дуга графа представлена начальной и конечной вершинами. Граф, у которого все связи представлены только ребрами, называется неориентированным графом (или просто графом). Граф, у которого отсутствуют ребра (т.е. все связи имеют только одно направление), называется ориентированным графом, а граф, у которого имеются и ребра, и дуги — смешанным.

Если задан граф G, то выражение G(x), где x — произвольная вершина графа, используется для обозначения множества смежных с ней вершин, т.е. вершин, в которые направлена дуга из x. Например, для графа G на рисунке 8 справедливы следующие равенства:

G(a) = {b, c}; G(b) = {d}; G(c) = {a, e}; G(d) = G(e) = .

Если мы, используя изображение произвольного графа, будем двигаться от вершины к вершине в соответствии с направлением дуг (при этом по ребру можно передвигаться в любую сторону), то последовательность вершин, отмечаемых по мере такого "обхода", называется путем в данном графе. Например для графа G на рисунке 8 существуют следующие пути: (a, b, d); (c, e); (a, c, a, b) и т.д. Пути можно записывать, используя стрелки, например, abd. При этом возможны графы, у которых имеются самопересекающиеся пути, т.е. некоторые вершины и дуги могут в некоторых путях повторяться.

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

Например, в графе на рисунке 8 имеется один цикл, обусловленный тем, что в нем имеется ребро (a, c). Поэтому цикл можно представить в виде пути (a, c, a). Если в этот граф добавить еще одну дугу (d, a) , то в этом случае появится еще одни цикл (d, a, b, d). По сути, цикл – это путь без начала и конца, поскольку, "путешествуя" по циклу, мы можем крутиться в нем бесконечное число раз.

Одним из основных в теории графов является понятие достижимости. Вершина y графа G называется достижимой из вершины x, если в G существует путь из вершины x в вершину y. Часто бывает необходимо определить для каждой вершины графа G множество всех достижимых из нее вершин. Например, для вершины a в графе на рисунке 8 достижимыми являются все вершины этого графа (в том числе и сама вершина a), в то время как из вершины b достижима только одна вершина – d, а для вершины e в данном графе нет вообще достижимых вершин.

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

4.2. Частично упорядоченные множества

Частично упорядоченное множество – один из типов бинарного отношения. Отношение частичного порядка является одним из фундаментальных общематематических понятий и широко используется в теоретической математике, в системах логического вывода и во многих других приложениях. Оно является обобщением таких широко известных бинарных отношений как "меньше или равно" () для чисел и "включено или равно" () для множеств. Обозначение "" часто используется не только для обозначения отношения "меньше или равно" для чисел, но и для обозначения произвольного отношения частичного порядка. Формально отношение частичного порядка определяется как заданное на множестве X бинарное отношение со следующими свойствами:

1) рефлексивности: aa для любого aX;

2) транзитивности: если ab и bc, то ac;

3) антисимметричности: из ab и ba следует a=b,

где a, b и c – произвольные элементы частично упорядоченного множества X.

Среди всех отношений частичного порядка наиболее простым в структурном отношении является линейный порядок, когда для любой пары разных элементов (a, b) множества определено либо ab, либо ba. Примерами линейного порядка являются множества чисел, упорядоченных по величине, и множества слов, расположенных в лексикографическом порядке. Их можно по заданному порядку сформировать в виде одной непрерывной последовательности. Например, 2

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