35. Аксиомы исчисления предикатов:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

Правила логического вывода:

1. Правило заключения (Modus Ponens – MP)

Если и являются выводимыми формулами, то   — выводимая формула.

2. Правило обобщения (правило -введения)

где   содержит свободное вхождение переменной  , а   их не содержит.

3. Правило введения квантора существования (правило -введения)

где   содержит свободное вхождение переменной  , а   их не содержит.

36.Графы. Типы задач теории графов.

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

Типы задач:Примеры известных задач, которые способствовали развитию теории графов.

1)Задача о Кёнигсбергских мостах(Эйлер 1736г.)

Можно ли обойти все 7 мостов пройдя по каждому 1 раз, вернувшись в начальную точку маршрута (любую) не переплывая реки? (Нет, так как граф должен быть связным, каждая его вершина должна быть инцидентна четному числу ребер; а мы имеем связный граф, но инцидентный нечетному кол-ву ребер.)

2)Задача о 3 домах и 3 колодцах.

Необходимо от каждого дома к каждому колодку проложить тропу таким образом чтобы тропы не пересекались.(невозможно)

3)Задача о 4 красках. (Правильная раскраска графа.) Эта задача является одной из наиболее известных проблем теории графов, которая оставалась неразрешимой на протяжении длительного времени. Возникла она в связи с раскраской географических карт и состоит в след.:

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

Известно что для такой раскраски достаточно 5 красок. (теорема о 5 красках). Известно также что для такой раскраски гарантировано недостаточно 3 красок. Вопрос о 4 красках был положительно разрешен в 1976 году. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств, впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок.

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

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