Ответы на экзаменационные вопросы № 1-31 по курсу "Дискретная математика" (Определение взаимно однозначного соответствия между двумя множествами. Определение транспортной сети, разреза в ней и его пропускной способности. Теорема Форда-Фолкерсона), страница 9

Кванторами наз. символы ", $. Кванторы можно навешивать на предикаты, в результате чего появляются новые предикаты, число аргументов которых на 1 меньше, чем у исходных. $x P(x,y)=Q(y). Кванторы являются операциями родственными Ú, Ù, именно, квантор всеобщности "x явл. бесконечным аналогом конъюнкции Ù, а квантор существования $x~Ú. Точнее, справедливы «формулы»:

"xP(x,y₀)=P(U₁,y₀)ÙP(U₂,y₀)Ù…ÙP(U_n,y₀)Ù…

Причем беск. Ù счит. истинной, когда истинны все ее члены. Аналогично:

$xP(x,y₀)=P(U₁,y₀)ÚP(U₂,y₀)Ú…ÚP(U_n,y₀)Ú…

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

Ф-лы выражающие один квантор через другой:

AÙB=ù(ùAÚùB)

AÚB=ù(ùAÙùB)

Доказать теорему о вынесении кванторов из-под отрицания.

Правила вынесения кванторов из-под отрицания:

ù"xP(x,…)=$xùP(x,…)

ù($xP(x,…))="xùP(x,…)

Док-во:

b=lim_x®af(x)Û"e>0 $d>0 "x [xÎO_d^·(a)Þf(x)ÎO_e(b)]

b¹ lim_x®af(x)Ûù"e>0 $d>0…Û$e>0 ù$d>0…Û$e>0 "d>0 $x ù[xÎO_d^·(a)Þf(x)ÎO_e(b)]Û…$x[xÎO_d^·(a)Þf(x)ÎO_e(b)]

Пример: ù(A®B)=ù(ùAÚB)=ù ùAÙùB=AÙùB

Вопрос 29.

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

f(A₁,A₂,…) – тавтология

f(A₁,A₂,…)º1, т.е. эта ф-ия принимает значение 1 для любого набора ее переменных A₁,A₂,…Î{0,1}

A®A AÚùA  AÙB®AÚB

Общезначимые ф-лы (предикатные ф-лы) явл. аналогом булевых повторений в том смысле, что и они «универсально-истинные» в силу своего строения. Предикатными будем называть ф-лы типа: "xP(x)Ú$yQ(y,x); "x($yQ(x,y)®Q(x,x)) и т.д., т.е. ф-лы, полученные из предикатных символов x,y,… с помощью булевых связок и кванторов. Сама по себе такая ф-ла не является ни истинной, ни ложной. Такие ф-лы принимают истинные значения в рез-те их интерпретации.

Интерпретацией предикатной ф-лы наз. след. процедуру:

1) Выбирается некоторое мн-во U¹Æ; 2) Предикатным символом P,Q,…, входящим в интерпр. ф-лу, ставятся в соответствие предикаты P^~,Q^~,… на множестве U, зависящие от соответствующего числа аргументов; 3) Свободным переменным x,y,… данной ф-лы (т.е. не вход. в область действия квантора по этой переменной) придаются значения u_xÎU, u_yÎU,…

После выбора произв. интерпретации для данной ф-лы, эта формула становится истинной или ложной.

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

Вопросы 30,31.

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

Транспортные сети – это модели, предназначенные для описания таких реальных структур, как железная дорога, газо- и нефтепроводы. Транспортной сетью наз. всякий связный ориентированный граф, всем дугам которого приписаны положительные числа с_ij, называемые пропускными способностями, при этом две вершины графа выделены и называются полюсами (входным – S и выходным – T), из которых в полюс S не входит ни одна дуга, а из полюса T ни одна дуга не выходит.

Потоком в данной сети наз. всякая система неотрицательных чисел a_ij (a_ij – поток в дуге, исходящий из вершины i и входящий в вершину j), удовлетворяющая двум условиям: 1) "i,j a_ij£c_ij; 2) "i (¹S,T) å_ja_ji=å_ka_ik, где первая сумма складывается из потоков во всех дугах входящих в вершину i, а вторая – из потоков во всех дугах из этой вершины исходящих. Таким образом равенства 2 изображают условия сохранения вещества во всех вершинах сети, кроме полюсов.

Величиной потока называют å_ia_Si.

В силу сохранения вещества имеем å_ia_Si=å_ja_jT. Это равенство можно существенно обобщить, именно разобьем множество всех вершин сети на два подмн-ва N_S и N_T.

Будем считать, что S принадлежит N_S, а T принадлежит N_T. Общее кол-во вещества, пересекающего границу между N_S и N_T равно сумме потоков в дугах, пересекающих эту границу из N_S в N_T, минус сумма потоков в дугах, пересекающих ту же границу в обратном направлении. Из условий сохранения вещества следует, что для любого фиксированного потока в данной сети и для любого разбиения сети на N_S и N_T, указанная величина является постоянной и равной величине данного потока.