Решение

Вид материала

Решение

Содержание 1.3 Математическая логика 1.4 Логика высказываний Пропозициональные формулы Теорема корректности. Теорема полноты. Способы задания графов Маршруты, циклы, связности. Свойства деревьев. Планарные графы. Парное сочетание (паросочетание) двудольных графов Теорема Холла (без доказательства)

Подобный материал:

• Найти частное решение линейного однородного дифференциального уравнения. Решение, 6.09kb.
• «Алгоритмизация и решение физических задач на эвм», 391.8kb.
• Навык 4 Думайте в духе «Выиграл выиграл», 91.19kb.
• Решение, 1036.71kb.
• Решение линейных уравнений Цель урока, 126.51kb.
• Совет депутатов г. Протвино решение от 25. 07. 2011 №241/38, 380.05kb.
• Решение страсбург, 1314.79kb.
• Герция Виталия Михайловича, Садоводческого некоммерческого партнерства «Речник» иОрлова, 141.35kb.
• Первая Вторая половина ХIХ начало ХХ вв. Право и жизнь в адыгском обществе, 3427.05kb.
• Республика мордовия рузаевский муниципальный район совет депутатов городского поселения, 19.08kb.

1.3 Математическая логика


Основная идея математической логики – формализация знаний и рассуждений. Известно, что наиболее легко формализуемые знания – математические. Таким образом, математическая логика, по-существу, – наука о математике, или метаматематика. Центральным понятием математической логики является ``математическое доказательство''. Действительно, ``доказательные'' (иначе говоря, дедуктивные) рассуждения

– единственный вид признаваемых в математике рассуждений. Рассуждения в математической логике изучаются с точки зрения формы, а не смысла. По-существу, рассуждения моделируются чисто ``механическим'' процессом переписывания текста ( формул). Такой процесс называют выводом. Говорят

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

Формальная система определена, если:

1. Задан алфавит (множество символов, используемых для построения формул).
   
2. Определено, какие именно строки считать формулами (остальные строки считаются просто бессмысленными).
   
3. Выделено множество формул, называемых аксиомами. Это – стартовые точки в выводах.
   
4. Задано множество правил вывода, которые позволяют из некоторой формулы (или множества формул) получать новую формулу.
   

1.4 Логика высказываний


Для понятия ``высказывание'' иногда используют термин ``пропозиция'', что является калькой с английского. Мы этот термин не используем, но говорим ``пропозициональный'' в смысле относящийся к логике высказываний. Центральными понятиями данной части являются пропозициональные формулы и пропозициональный вывод.

Объектный язык и метаязык

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

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

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

Пропозициональные формулы

Пропозициональная сигнатура – это множество символов, называемых атомами. Символы ¬ (отрицание), & (конъюнкция),  (дизъюнкция) и  (импликация) называются пропозициональными связками; ¬ – унарная связка, а другие – бинарные.

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

Чтобы определить понятие пропозициональной формулы, нам требуется следующее вспомогательное определение.

Определение. Множество X строк замкнуто относительно правил построения (для логики высказываний), если

каждый атом принадлежит X,

для любой строки F, если F принадлежит X, то ¬F тоже принадлежит,

для любых строк F, G и любой бинарной связки , если F и G принадлежат X, то также принадлежит (F  G).

Определение. (Формула). Строка F называется пропозициональной формулой, если F принадлежит всем множествам, которые замкнуты относительно правил построения.

Нормальные формы

Определение. (Эквивалентность). Формула F эквивалентна формуле G, если F^I = G^I для любой интерпретации I.

Корректность и полнота логики высказываний

Теорема корректности. Если существует вывод F из , тогда  логически влечёт F.

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

Полнота логики высказываний (для другого множества правил вывода) была установлена Емилем Постом в 1921 году.


1.5 Графы

Графом (G) будем называть тройку объектов (V, X, )

V – множество n вершин.

X – конечное множество ребер.

- функция инцидентности, которая каждому элементу множества X ставит в соответствие пару элементов из множества V.


задана на множестве X.

Если в значении функции инцидентности допускается перестановка вершин, то граф называется неориентированным. В противном случае граф называется ориентированным (Орграф).

V_j – начало ребра

V_k – его конец

x_i) = (V_j, V_k) – ребро инцидентно в вершине Vj и в вершине Vk.

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

Если на ребре x_i0

(x₀) = (V_j0, V_j0),

то ребро называется петлей.

Способы задания графов

1. Аналитический
   

Если вершине не инцидентно никакое ребро, то эта вершина называется изолированной.

Выписываются все ребра и пишутся напротив две пары вершин, которым они инцидентны.

В конце выписываются все изолированные вершины.

2. Геометрический
   

Каждая вершина графа задается точкой. А ребра, инцидентные паре вершин – кривой.

Желательно рисовать кривые без пересечения. Если пересечения существуют, то их надо отличать от вершин.

3. С помощью матрицы инцидентности
   

A(m*n)

m = [V] – число вершин

n = [X}- число ребер

а) Неориентированные графы

A_ij = {0, если V_i не инцидентно x_j, 1, если V_i инцидентно x_j)

б) Орграфы

A_ij = {0, если V_i не инцидентно x_j, -1, если V_i - начало x_j, 1, если V_i - конец x_j)

Для петель нужны дополнительные предположения.

Матрица смежности (задается одинаково для всех графов)

B(m*m) m = [V]

Bij равно числу ребер, инцидентных паре вершин (oi, oj)

Если граф не ориентирован, то матрица симметрична.

Граф, в котором нет кратных ребер и петель, называется простым.

Простой граф называется полным, если любой паре его вершин инцидентно одно ребро.

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

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

Маршруты, циклы, связности.

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

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

Маршрут, в котором нет повторяющихся ребер, называется цепью.

Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью.

Если в простой цепи первая и последняя вершины совпадают, то она называется циклом.

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

Эти части называются компонентами связности.

Ребро называется циклическим, если оно входит хотя бы в один цикл графа. В противном случае ребро называется ациклическим.

Утверждение.

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

Связный граф, у которого все ребра ациклические, называется деревом.

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

Свойства деревьев.

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

Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

Планарные графы.

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

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

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


Любой граф можно изобразить в трехмерном пространстве без пересечения ребер.

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

Граф будет планарным, если существует его укладка на сфере.

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

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

Парное сочетание (паросочетание) двудольных графов

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

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

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

Паросочетание называется совершенным (из множества v в множество w), если число ребер в нем совпадает с числом вершин в подмножестве c.

Для любого подмножества S через ф(S) обозначим те вершины из множества w, которые соединяются ребрами с вершинами подмножества S.

Теорема Холла (без доказательства)

Для того, чтобы в двудольном графе существовало совершенное паросочетание, необходимо и достаточно, чтобы для любого подмножества S из множества V выполнялось условие [S] <= [ф(S)].

Венгерский алгоритм нахождения максимального паросочетания.

Дан двудольный граф. Все определения для графа справедливы.

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




2. Задачи

Задача 1

В штучном отделе магазина посетители обычно покупают или один торт, или одну коробку конфет, или один торт и одну коробку конфет. В один из дней было продано 57 тортов и 36 коробок конфет. Сколько было покупателей, если 12 человек купили и торт и коробку конфет?