Лекция № 12. Язык логики предикатов.

1. Предикаты.

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

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

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

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

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

Пример 1.

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

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

в) В описаниях вычислительных процедур и, в частности, в языках программирования, часто встречаются указания типа “повторять цикл до тех пор, пока переменные и не станут равными или прекратить вычисление цикла после ста повторений”. Если обозначить через счётчик повторений, то описанное здесь условие примет вид , а само указание в целом описывается выражением: “повторять, если ”.

1. Кванторы.

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

Высказывание “существует такое значение , что истинно” обозначается или . Знак называется квантором существования. Переход от предиката к выражениям вида или называется связыванием переменной , а также навешиванием квантора на переменную (или на предикат ). Переменная, на которую навешен квантор, называется связанной, несвязанная переменная называется свободной.

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

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

Пример 2.

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

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

 

1. Истинные формулы и эквивалентные соотношения.

При логической (истинностной) интерпретации формул логики возможны три основные ситуации.

1. Если в области для формулы существует такая подстановка констант вместо всех переменных, что становится истинным высказыванием, то эта формула называется выполнимой в области . Если существует область , в которой формула выполнима, то формула называется просто выполнимой. Пример выполнимой формулы - .

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

3. Если формула невыполнима в области при любых подстановках констант, то она называется тождественно ложной в области . Формула, тождественно ложная в любых множествах называется просто тождественно ложной или противоречивой. Формула является противоречивой.

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

Отметим, что если формулы и эквивалентны в соответствии с этим определением, то формула является тождественно истинной.

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

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

Аналогично доказывается истинность соотношения

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

1) Дистрибутивность квантора относительно конъюнкции:

.

2) Дистрибутивность квантора относительно дизъюнкции:

.

Если же кванторы и поменять местами, то получатся соотношения, верные только в одну сторону:

3) ,

4) .

В таких случаях говорят, что левая часть является более сильным утверждением, чем правая, поскольку она требует для своего выполнения более жёстких условий. Так, например, в соотношении 3 в левой части требуется, чтобы оба предиката были истинны для одного и того же значения , тогда как в правой части они могут быть истинны при различных значениях переменной. Пример случая, когда соотношения 3 и 4 в обратную сторону неверны: “ чётное число”, “ нечётное число”.

Пусть некоторое переменное выражение, не содержащее переменной . Тогда выполняются соотношения:

5) .

6) .

7) .

8) .

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

 

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

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

, .

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

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

 

Назад, в начало конспекта.

 

 

Лекция № 13. Комбинаторика.

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

 

1. Правила суммы и произведения.

 

Будем в дальнейшем оперировать только с множествами, содержащими конечное число элементов. На бесконечные множества все нижеприведённые правила и формулы не распространяются.

Теорема 13.1. Пусть даны непересекающиеся конечные множества . Тогда мощность объединения этих множеств равна сумме мощностей данных множеств:

.

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

Если некоторый элемент можно выбрать способами, а элемент - способами, причём любой способ выбора элемента отличается от любого способа выбора элемента , то выбор “ или ” можно сделать способами. Это правило называется правилом суммы.

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

Теорема 13.2. Число элементов в декартовом произведении множеств равно произведению мощностей этих множеств:

.

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

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

Пример 1.

а) В некоторой средней школе имеется три пятых класса, в которых обучаются соответственно 28, 31 и 26 учащихся. Требуется одного из них выбрать для участия в совете школы. Сколькими способами можно сделать выбор?

По правилу суммы получаем .

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

По правилу произведения получаем .

 

1. Размещения.

 

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

Пример 2. Куплено различных 12 книг. На полке можно поставить в ряд ровно 6 книг. Сколькими различными способами можно это сделать?

Будем считать различными не только те случаи, когда берутся разные книги, но и когда они по-разному расставлены на полке (в различном порядке). Тогда речь идёт о перестановках по 6 из 12. Получаем: .

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

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

Пример 3. Сколько различных комбинаций может получиться при одновременном бросании трёх игральных костей?

Каждая игральная кость представляет собой кубик, на гранях которого нанесено от одного до 6 очков. При каждом бросании мы будем получать наборы вида , где - количество очков, выпавших на соответствующей кости. Речь идёт о перестановках с повторениями по 3 элемента из 6. Получаем: .

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

 

1. Перестановки.

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

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

Пример 4. Сколькими различными способами можно расставить на полке 10 различных книг?

Здесь, в отличие от примера 2, значение имеет только порядок расставляемых книг. Поэтому речь идёт о перестановках из 10 элементов. Получаем: .

Рассмотрим случай, когда элементы множества повторяются по нескольку раз. Для определённости пусть 1-й элемент повторяется раз, 2-й элемент - раз и так далее. Тогда векторы длины , образованные из элементов данного множества называются перестановками из элементов с повторениями. Число таких перестановок обозначается и равно .

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

Пример 5. Сколько различных шестизначных чисел могут быть записано с помощью цифр 1, 2, 2, 2, 3, 3?

Имеется набор из шести цифр, в котором цифра 2 повторяется трижды и цифра 3 – дважды. Полученные числа будут представлять собой перестановки с повторениями из 6 элементов. Получаем: .

 

1. Сочетания. Бином Ньютона.

 

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

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

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

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

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

Пример 6.

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

Поскольку имеет значение только то, какие именно сотрудники отобраны, то речь идёт о сочетаниях без повторений по 3 элемента из 10. Получаем:

б) В цветочном магазине имеются в продаже 5 различных видов цветов. Покупателю требуется составить букет из 7 цветов. Сколькими способами можно это сделать?

Будем считать различными те букеты, которые отличаются друг от друга по подбору цветов. Поскольку цветы в букете могут повторяться, то речь идёт о сочетаниях с повторениями по 7 элементов из 5. Тогда получим .

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

.

С частными случаями применения этой формулы (для случаев и ) сталкиваются ещё в школе при изучении формул сокращённого умножения:

.

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

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

…………………..

 

Назад, в начало конспекта.

 

 

РАЗДЕЛ IV. ТЕОРИЯ ГРАФОВ.

 

Лекция № 14. Графы: основные понятия и операции.

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

 

1. Графы, их вершины, рёбра и дуги. Изображение графов.

 

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

При этом элементы множества V называются вершинами графа, а элементы множества E – ребрами.

Определение. Если вершина v является концом ребра , то говорят, что v и инцидентны.

В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями (на рисунке 1.4 при вершине 5 имеется петля). Одинаковые пары в множестве E называются кратным и (или параллельными) ребрами. Количество одинаковых пар (v, w) в E называется кратностью ребра (v, w). Например, на рисунке 1.1 все рёбра имеют кратность 1, а на рисунке 1.2 есть два ребра, соединяющих одни и те же вершины 1 и 4, следовательно, их кратность равна двум.

Множество V и набор E определяют граф с кратными ребрами – псевдограф.

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

Если в наборе E ни одна пара не встречается более одного раза, то мультиграф называется графом.

Ниже, на рисунке 1.1 изображен граф, на рисунке 1.2 мультиграф, на рисунке 1.4 – псевдограф.

Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины. На рисунке 1 изображены некоторые неориентированные графы.

Рисунок 1.

 

1.1 1.2 1.3

 

1.4 1.5

 

Замечание 1. Слово “линия”, которое мы используем, подразумевает несущественность того, какая конкретно линия используется для соединения двух вершин графа, то есть её геометрические характеристики не имеют значения.

Замечание 2. Граф можно определить, также как совокупность двух множеств и , между элементами которых установлено отношение инцидентности, при котором каждый элемент инцидентен ровно двум элементам .

Определение. Если х = { v, w } – ребро графа, то вершины v, w называются концами ребра х.

Определение. Если пары в наборе E являются упорядоченными, то граф называется ориентированным или орграфом.

Если пишут = (v, w) – дуга орграфа, то вершина v – начало, а вершина w – конец дуги х.

Определение. Вершины v, w графа G = (V, E) называются смежными, если { v,w }ÎЕ. Два ребра называются смежными, если они имеют общую вершину.

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

На рисунке 1.5 все вершины, кроме вершины 1, являются висячими. На рисунке 1.3 вершина 4 является изолированной. Если граф состоит только из таких вершин, его называют пустым. В некоторых случаях пустым называют граф, не имеющей ни одной вершины.

Рисунок 2.

2.1 2.2 2.3

a. 2.5

На рисунке 2 представлены различные типы