Материал: 1944

Внимание! Если размещение файла нарушает Ваши авторские права, то обязательно сообщите нам

Путь	(цикл),			Достаточные условия

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

Операции над графами

Название

Обозначение

Определение

операции

Дополнение

x V V;x X

G (V, X)

G(V, X)

Объединение

G (V , X

) G

, X

)

G(V, X):V V1

V2,

графов

X X1

(V1 V2

)

Пересечение

G1(V1, X1) G2

(V2, X2)

G(V, X):V V1

V2,

графов

X X1

Сумма по

G (V , X

) G

, X

)

G(V, X):V V1

V2,

модулю

(V1 V2

)

X X1

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

Название

Способ задания

П р и м е р

V 1,2,3,4

x, y R "x y"

Аналити-

Бинарное отношение R на

ческий

множестве

V vi ,i 1,n

109

Матрица			a		a	...	a
смежности				11	12			1n			vi			1		2		3			4
графа			a21		a22 ...		a2n
			a21		a22 ...		a2n				1			0		1		1			1
											1			0		1		1			1
G(V, X)			...		... ...			...
G(V, X)			...		... ...			...			2			0		0		1			1
V v ,...,v											2			0		0		1			1
	n		an1		an2 ...		ann
			an1		an2 ...		ann
1				1,	если (v		,v		) X;		3			0		0		0			1
				1,	если (v		,v		) X;		3			0		0		0			1
		aij				i		j			4			0		0		0			0
		aij			если (v		,v		) X		4			0		0		0			0
				0,	если (v		,v		) X
						i		j

Матрица			a		a	...	a
инцидент-				11	12			1m
ности			a21		a22 ...		a2m
ности			a21		a22 ...		a2m						x1		x2		x3		x4		x5	x6

орграфа			...		... ...		...
орграфа			...		... ...		...				1		1		0		0		1		0	1
G(V, X)											1		1		0		0		1		0	1
			an1		an2 ...		anm
			an1		an2 ...		anm				2		-1		1		0		0		1	0
V v1,...,vn				1, если xj		исходит изvi;					2		-1		1		0		0		1	0
V v1,...,vn				1, если xj		исходит изvi;
X x1,...,xm											3		0		-1		1		0		0	-1
X x1,...,xm		aij		1,если xj заходит в vi						;
		aij			если xj						4	0			0		-1		-1	-1		0
				0,
				0,

				не инцидентна vi

110

Раздел 21. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ

Операции над высказываниями

Высказыванием Р называется предложение, к которому возможно применить понятия истинно И или ложно Л.

П р и м е р. «2+3=5» – И; « Москва – столица Казахстана» – Л.

Название

Определение

Таблица

операции и

истинности

обозначение

Отрицание

Высказывание Р (или Р )

( )

истинно Р ложно

связка «не»

Конъюнкция

Р Q

Высказывание Р Q истинно

( или &)

истинны оба высказывания

связка «и»

Дизъюнкция

Р Q

Высказывание Р Q ложно

( )

связка

ложны оба высказывания

«или»

Импликация

Р Q

Высказывание Р Q ложно

( )

связка

Р истинно, а Q – ложно

«если …, то…»

Эквиваленция

Высказывание Р ~ Q истинно

Р ~ Q

(~ или )

связка

истинности высказываний Р и Q

«тогда и только

совпадают

тогда»

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

101

Булевы функции

Булева функция f(X1, X2,…,Xn) – n-местная функция, аргументы и значения которой принадлежат множеству {0, 1}.

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

Дополнительно

вводятся операции:

Х1 | Х2=Х1 Х2 –

штрих

Шеффера и Х1 Х2 =

стрелка Пирса.

Х1

Х2

X1 X2

Х1 | Х2

Х1 Х2

Основные законы математической логики

Название

Закон относительно

операции конъюнкции

операции дизъюнкции

Тавтология

х х х

Коммутативность

х у у х

Ассоциативность

(х у) z x (y z)

Дистрибутив-

x (y z) (x y) (x z)

х (у z) (x y) (x z)

ность

Законы де

х y x y

x y x y

Моргана

Законы

x (x y) x

поглощения

Операции с 0 и 1

х 1 х; х 0 0

х 1 1; х 0 х

Закон

дополнитель-

ности

Закон склеивания

(y x) (y

) y

(y x) (y

) y

Закон

x (x y) x y

ортогонализации

Закон

у х y

импликации

Инверсия

x x

102

П р и м е р. Доказать с помощью таблиц истинности справедливость формул де Моргана x y x y.

	x			y					x y
	x			y					x y		x y		x		y		x y
	0			0				0		1		1		1		1
	0			1				1		0		1		0		0
	1			0				1		0		0		1		0
	1			1				1		0		0		0		0
		Закон		справедлив, так как совпадают столбцы истинности для
формул					и				.
формул			x y		и	x	y		.

Формы представления булевых функций

х,если 1

Пусть

x0 x,

x1 x, 0,1 . х

– литера.

x, если

Совершенные формы

Формула

Совершенная конъюнктивная

нормальная форма (СКНФ)–

f (x1, x2

,...,xn )

конъюнкция конституент нуля

по всем наборам

i 1

( 1, 2,..., n)

на которых

f ( 1, 2,..., n) 0

Совершенная дизъюнктивная

нормальная форма (СДНФ) –

f (x1, x2

,...,xn )

дизъюнкция конституент

по всем наборам i 1

( 1, 2,..., n)

единицы

на которых

f ( 1, 2,..., n) 1

П р и м е р

f (x, y)

Элементарные

x y

конъюнкции

дизъюнкции

x0 y0

y1 x1 y0 x

x1 y

x0 y1

x1 y1 x0 y0

СДНФ:

f (x, y)

СКНФ:

f (x, y) (x

) (

y) (

103

Источник: https://studfile.net/preview/16408001/

Смотрите также:



ЦЕНОВАЯ ПОЛИТИКА ПРЕДПРИЯТИЯ НА ПРИМЕРЕ ООО «ДНС РИТЕЙЛ»
_archivetempпротивовоспалительные
- Обратный порядок следования фаз 4
- Сопротивление изоляции 25
!_Лабораторные_работы_1_сем_ОУТС
!Контрольная работа (задание)
!Фармакология препаратов для терапии заболеваний дыхательных путей
.Юридический позитивизм как теория права.