Счетные и несчетные множества

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

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

Формирование предложений в естественном языке указывает на то, что высказывания могут объединяться с помощью связывающих союзов. С математической точки зрения эти союзы реализуют операции над высказываниями. В математической логике рассматривают только такие операции над высказываниями, для которых истинность результирующего высказывания можно определить исходя из истинности исходных независимо от смысла этих высказываний, т.е. независимо от того, что именно утверждают эти высказывания. Вообще говоря, под операцией на множестве A понимают любое отображение ϕ: An → A, которое любому упорядоченному набору из n элементов множества A (кортежу) ставит в соот- ветствие элемент того же множества. Натуральный показатель n называют арностью этой операции. Ясно, что множество всех операций на заданном множестве бесконечно, даже если само множество конечно. Однако на практике ограничиваются операциями небольшой арности: унарными (n = 1), бинарными (n = 2), тернарными (n = 3). Кроме того, практические важные операции обладают определенными свойствами (например, свойство коммутативности для бинарных операций). Ассоциация ” операция — функция“ наталкивает на мысль о введении нульарных операций (функций без аргументов). С точки зрения математики нульарная операция — это постоянная функция или, иными словами, некоторый фиксированный элемент множества A. В качестве таких элементов выступают, например, число 0 или 1, т.е. элементы, чем-то выделяющиеся с точки зрения других операций. Выделим пять операций над высказываниями: 1) дизъюнкция (соответствует союзу ” или“); 2) конъюнкция (соответствует союзу ” и“); 3) импликация (соответствует фразе типа ” если..., то ”); 4) эквиваленция (соответствует фразе типа ”... тогда и только тогда, когда...); 5) отрицание (соответствует союзу ” не“). Первые четыре из этих операций бинарные, последняя унарная. Относительно указанных операций можно сказать лишь, что они формируют новое высказывание. При этом, зная, истинны или ложны исходные высказывания, можно сказать, является ли истинным вновь Ì Ã Ò Ó Ô Í -12 Ì Ã Ò Ó Ô Í -12 Ì Ã Ò Ó Ó Ò Ã Ì 21- Í Ô Ó Ò Ã Ì 21- Í Ô Ó Ò Ã Ì Ì Ã Ò Ó Ì Ã Ò Ó Ì Ã Ò Ó Ô Í - 1 2 Ô Í - 1 2 Ô Í - 1 2 Ô Í - 1 2 Ì Ã Ò Ó Ì Ã Ò Ó Ì Ã Ò Ó Ô Í - 1 2 Ô Í - 1 2 Ô Í - 1 2 Ô Í - 1 2 1. АЛГЕБРА ВЫСКАЗЫВАНИЙ 4 образованное высказывание. Введенные пять операций мы будем называть логическими или пропозициональными. Для символической записи высказываний и операций над ними необходимо ввести некоторый набор символов и сформулировать правила записи с помощью этих символов. Набор символов (алфавит) в сочетании с набором правил записи представляет собой некоторый язык — язык алгебры высказываний. Вообще говоря, алфавит позволяет из заданного набора символов со- ставлять цепочки символов (слова, фразы). Множество всех цепочек символов разделяется на две группы: правильные и неправильные. Правильные цепочки можно назвать словами, их множество и называется языком. На практике язык можно определить как множество цепочек, удовлетворяющих некоторым требованиям, которые в конечном счете сводятся к тому, является ли данная цепочка интепре- тируемой с точки зрения выполнения операций или нет. Но часто язык определяют, указывая правила, по которым из уже построенных слов можно строить новые. Набор таких правил называется грамматикой. Хотя любой математический язык проще любого естественно- го, многие закономерности у них схожи. Так слова русского языка собираются из отдельных частей с помощью некоторых правил. Описание языка с помощью грамматики в математи- ке приводит к особому типу определения, так называемому индуктивному определению. При таком определении сначала задаются первичные, элементарные слова (это база индукции), а затем указываются правила, по которым из уже построенных слов формируются новые (шаг индукции). Алфавит языка алгебры высказываний составляют множество пропозициональных пе- ременных, множество функциональных символов (символов операций, или логических свя- зок) ∨, ∧, →, ∼, и множество служебных символов (две круглые скобки). Формулы языка вводятся индуктивно. База индукции: пропозициональные переменные представляют собой формулы. Шаг индукции: если X и Y — формулы, то формулами являются (X ∨ Y), (X ∧ Y), (X → Y), (X ∼ Y), X. Договоримся о следующих обозначениях. Будем обозначать: пропозициональные перемен- ные — строчными латинскими буквами конца алфавита (x, y, z и т.д.); какие-либо формулы — прописными латинскими буквами конца алфавита (X, Y, Z и т.д.). Для сокращения коли- чества скобок в формулах с целью улучшить их читаемость договоримся о дополнительных правилах. Это правило приоритета операций. Вместо, например ((X∆ Y)∆ Z), как положено по определению, будем писать X∆ Y ∆ Z, имея в виду, что операции выполняются слева направо, причем сначала отрицание, затем дизъюнкция и конъюнкция, а потом ипликация и эквивален- ция. Соглашение не относится к самому языку и служит лишь для удобства: в любой момент сокращенную запись формулы однозначным образом можно преобразовать в полную запись со всеми нужными скобками. В математический язык эти правила вводить нет смысла, поскольку они ничего не добавляют к математической сути вопроса. В наших рассуждениях будут встречаться формулы, которые относятся к введенному языку, но, кроме того, придется использовать и дополнительные обозначения и символику, чтобы рас- суждать не в рамках языка, а о самом языке и его формулах. Так, обозначения переменных — это элемент языка алгебры высказываний, а обозначения формул или соглашение о приоритете уже выходят за рамки языка. В этом случае говорят о расширении рассматриваемого языка или о метаязыке. На практике язык и метаязык тесно переплетаются и трудно разделимы. Рассмотрим какую-либо формулу, например (x → y) → z. Об истинности этой формулы можно судить, если известно, истинны ли элементарные высказывания x, y, z. Например, если x и z ложны, а y истинна, то x→ y является истинной, а (x→ y)→ z ложной. Приписав истинной формуле значение 1, а ложной — 0, мы получаем функцию, которая по значениям истинности пропозициональных переменных (элементарных высказываний) определяет значение истинно- сти всей формулы. Эта функция есть отображение вида h: {0, 1} n → {0, 1} (и аргументы, и функция принимают значения 0 и 1). Она называется истинностной функцией формулы. Позже мы увидим, что любая двузначная (булева) функция от n аргументов есть истинностная функция некоторой пропозициональной формулы с n переменными. Замечание. Отметим различия понятий ” формула“ и ” функция“. Первое понятие связано с языком, на котором описываются свойства математических объектов. Формула имеет не- который набор переменных, если заданы значения этих переменных, то формула также имеет некоторое значение. В этом смысле формулу можно рассматривать как запись некоего правила, которое заданным значениям переменных ставит в соответствие новое значение. Это похоже на понятие функции, но функция (отображение) есть реальный математический объект, а не запись о нем в некотором языке. Кроме того, исходные значения, по которым отображение формирует значение, должны быть упорядочены. Одна и та же формула задает разные функ- ции. Так, формула x − t определяет и функцию f(x, t), и функцию f(t, x), а также, например, функцию f(x, y, t). Чтобы с формулой связать некоторую функцию n аргументов, необходи- мо установить связь между аргументами функции и переменными формулы. Это в языках программирования реализуется формальными переменными: f(x, t) = x − t. Понятие истинностной функции позволяет и введенные логические операции рассматри- вать совершенно формально — как формульную запись некоторых истинностных функций тбл.1.1 (табл. 1.1). В дальнейшем через |X| мы будем обозначать истинностную функцию формулы X.

Тавтологии и эквивалентность формул Тавтологии. Формулы выполнимые и опровержимые. Теорема о правиле modus ponens: если X и X → Y — тавтологии, то и Y — тавтология. Подстановка. Эквивалентность фор- мул алгебры высказываний. Теорема о заменах. Следствие 1: если X — тавтология, то и S(z1, z2,..., zn|Y1, Y2,..., Yn|X) — тавтология. Следствие 2: инвариантность эквивалент- ности относительно логических операций. Способы получения эквивалентных формул: на основе свойств логических операций; на основе взаимосвязей операций; на основе двойствен- ности. Среди формул алгебры высказываний выделяют: – тождественно истинные, или тавтологии, истинные при любой истинности пе- ременных; – выполнимые, имеющие значение 1 хотя бы для одного набора значений пропозициональ- ных переменных; – опровержимые, имеющие значение 0 хотя бы для одного набора значений пропозицио- нальных переменных. – тождественно ложные, или противоречия, ложные при любой истинности пере- менных. Эти четыре понятия связаны между собой. Формула, не являющаяся опровержимой, есть тавтология. Такие формулы описывают универсальные логические законы. Именно с исполь- зованием тавтологий проводится любое математическое доказательство. Формула, не являю- щаяся выполнимой, тождественно ложна, т.е. представляет собой противоречие. Для тавтологий (противоречий) истинностная функция есть константа 1 (0). Для вы- полнимых формул истинностная функция не равна постоянной 0, а для опровержимых — постоянной 0.

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

Граф

Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).

Рис. 2.15

Петля это дуга, начальная и конечная вершина которой совпадают.

Простой граф граф без кратных ребер и петель.

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

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