Равносильные формулы логики предикатов.

 

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

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

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

Закон де Моргана:

1.

2.

Закон двойного отрицания:

3.

4.

5.

6.

7.

Для произвольного высказывания (предиката, не связанного по переменной ) справедливы следующие формулы равносильности:

8.

9.

10.

11.

12.

13.

Формулы замены переменных (где и из одной предметной области):

14.

15.

 

Предваренная нормальная форма предиката

 

Формула предиката имеет нормальную форму, если она содержит только операции конъюнкции, дизъюнкции, и кванторные операции, а операция отрицания отнесена к элементарному предикату.

 

ПРИМЕР

 

Пусть дан предикат . Привести данный предикат к нормальной форме

 

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

 

ПРИМЕР

Привести предикат из предыдущего примера к предваренной нормальной форме предиката

ТЕОРИЯ ГРАФОВ

Начало теории графов как математической дисциплине было положено Леонардом Эйлером в его знаменитом решении задачи о Кенигсбергских мостах в 1736 году. План города Кенигсберга представлен на рис. 3.1. Задача о Кенигсбергских мостах сводилась к тому, чтобы построить маршрут своей воскресной прогулки так, чтобы, начиная в любой точке суши (A, B, C или D) пройти по всем мостам строго по одному разу и вернуться в исходную точку (начало маршрута).

 

A

 

 

B

Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах.

 

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

 

Основные понятия теории графов

Графом называется пара следующего вида:

, (3.1)

где - график ;

- множество вершин.

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

 

 

Рис. 3.2. Граф

Граф, представленный на рис. 3. 2, состоит из множества вершин и множество дуг

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

1. перечислением:

2. множеством образов:

,

где - образ вершины - множество вершин, в которые исходят дуги из данной вершины.

Матрицей инцидентности

Матрица инцидентности - это матрица вершин и инцидентных им дуг.

Дуга инцидентна вершине, если эта дуга исходит или заходит в данную вершину.

Вершина инцидентна дуге, если в эту вершину заходит или исходит данная дуга.

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

· , если из i-той вершины исходит j-тая дуга:

· , если в i-той вершину заходит j-тая дуга;

· , если i-тая вершина не инцидента j-той дуге;

· , если из i-той вершины исходит j-тая дуга и в нее же заходит, т.е. в i-той вершине j-тая дуга образует петлю.

Для графа, представленного на рис. 3.2 матрица инцидентности имеет вид:

 

		-1	+1			+1	-1
		+1
			-1	-1
				+1	-1
					+1	-1
							+1

 

На практике в матрице инцидентности иногда нули не проставляются для наглядности.

 

		-1	+1			+1	-1
		+1
			-1	-1
				+1	-1
					+1	-1
							+1

Свойство матрицы инцидентности – сумма элементов по столбцам равна 0 или 2.

Матрицей смежности

Смежные дуги – это дуги инцидентные одной вершине.

Смежные вершины – вершины, инцидентные одной дуге.

Матрица смежности - это матрица смежных вершин.

Матрица смежности заполняется по следующему правилу: , если из i-той вершины исходит дуга в j – тую вершину; во всех остальных случаях (для удобства и наглядности на практике в матрице смежности нули не проставляются).

Для графа, представленного на рис. 3.2 матрица смежности имеет вид:

 

 

Полустепенью захода i–той вершины называется число дуг, заходящих в данную вершину.

Полустепенью исхода i-той вершины называется число дуг, исходящих из данной вершины.

Степенью i-той вершины исхода называется сумма полустепеней захода и исхода:

(3.2)

Свойства матрицы смежности:

1. Сумма единиц по строке определяет полустепень исхода;

2. Сумма единиц по столбцу определяет полустепень захода;

3. Сумма единиц по строкам и по столбцам определяет степень вершин.

Основное свойство графа:

В любых графах число вершин с нечетной степенью четно.

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

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

Простой путь – это такой путь, в котором дуга встречается не более одного раза.

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

Контур – путь, начинающийся и заканчивающийся в одной точке.

Петля – контур длиной в одну единицу.

Графы бывают двух видов:

· ориентированный граф (орграф) - это граф, состоящий из вершин и дуг.

· неориентированный граф – это граф, состоящий из вершин и ребер. Ребро – это дуга, не имеющая направление.

Рис. 3.3. Неориентированный граф

 

В неориентированном графе путь называется цепью; контур – циклом.

Неориентированный граф также может быть задан с помощью матриц инцидентности и смежности.

Матрица инцидентности для неориентированного графа составляется по правилу:

· , если i-тая вершина инцидентна j-тому ребру;

· , если i-тая вершина не инцидента j-тому ребру;

· , если. в i-той вершине j-тое ребро образует петлю.

Для графа, представленного на рис. 3.3, матрица инцидентности имеет вид:

 

	I	II	III	IV	V	VI	VII

 

Матрица смежности для неориентированного графа составляется по правилу: , если из i-тая и j – тая вершины смежные.

Для графа, представленного на рис. 3.3, матрица смежности имеет вид:

Матрица смежности для неориентированного графа симметрична относительно главной диагонали. Степень i- той вершины равна сумме элементов по строке или по столбцу матрицы смежности.

 

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

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

 

Рис. 3.4. Смешанный мультиграф.

 

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

 

Эйлеров граф.

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

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

Эйлеровым графом называется граф, содержащий Эйлеров цикл.

 

ТЕОРЕМА: Для того чтобы связанный граф был Эйлеровым, необходимо и достаточно, чтобы степени всех вершин были четны

 

 

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

 

А

 

 

С D

 

 

B

Рис. 3.5 Граф «Кенигсбергские мосты»

 

Вершины графа (A, B, C, D) имеют степени:

(3.3)

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

 

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