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

Вопрос 24.

Дать определение вывода из гипотез.

Пусть Ф₁,…,Ф_n – некоторые формулы исчисления высказываний наз. далее гипотезами. Выводом из этих гипотез называют всякую конечную посл-ть ф-л Y_1, Y_2,…, Y_k, в которой каждая ф-ла Y_i<=k либо 1) является одной из гипотез, либо 2) выводима в ИВ |– Y_i, либо 3) получается из 2-х предшествующих ей ф-л с помощью правил modas ponens (правило заключения). С выводом из гипотез мы сталкиваемся в таких известных типах док-ва как док-во от противного и док-во по индукции.

Примеры:

Ф₁=(А®А) ®(В®С)

Ф₂=В

Y₁: А®А

Y₂: (А®А) ®(В®С)

Y₃: В®С

Y₄: В

Y₅: С

Если ф-ла Y выводится из гипотез Ф₁,…,Ф_n, будем обозначать: Ф₁,…,Ф_n |– Y.

Теорема дедукции:

Если из гипотез Ф₁,…,Ф_k-1, Ф_k |– Y, можно уменьшить в Ф₁,…,Ф_k-1 |– Ф_k ® Y

Пример применения теоремы дедукции.

Докажем, что, если |– (Ф®Y)®((Y®C)®(Ф®C)) – правило силлогизма

Вопрос25.

Критерий выводимости

(|–_ИВ Ф)ÛФº1 при обычной булевой интерпретации логических связок.

Сравнительно не сложно доказать утверждение: если ф-ла выводима в ИВ, то она является тавтологией: (|–_ИВ Ф)ÞФº1. Докажем его:

1) Тавтологичность всех аксиом проверяется непосредственно; 2) Остается доказать, что и правила вывода сохраняют тавтологичность формул. Покажем это для подстановки: Пусть Y(А₁,…) º1. Докажем, что и результат подстановки S_Ф^A1Yº1. Это следует из того, что ф-ла Ф, появившаяся в формуле Y вместо переменной А₁ на всяком наборе значений своих переменных принимает значение либо 0, либо 1. А ф-ла Y, будучи тавтологией, примет значение 1 в обоих случаях. Рассмотрим теперь правило modas ponens:

Пусть теперь Фº1 и Ф®Yº1. Нужно проверить, что и Yº1. Предположим противное, т.е. существует a₁, a₂,…,a_n   Y(a₁, a₂,…,a_n)=0. Но тогда (Ф®Y)(a₁, a₂,…,a_n)= Ф(a₁,…,a_n) (=1)® Y(a₁,…,a_n) (=0)=0, что противоречит условию (Ф®Yº1). Значит Yº1, и рассматриваемое утверждение доказано.

Замечание: Обратное утверждение также верно, но доказывается существенно сложнее.

Примеры применения критерия выводимости.

АÚùА             A®B

А	ùА	АÚùА		A	B	A®B
0 1	1 0	1 1		0 0 1 1	0 1 0 1	1 1 0 1

|– АÚùА         |-/–A®B

Вопрос 26.

Дать определение разрешимого и непротиворечивого исчислений.

ИВ разрешимо в том смысле, что существует алгоритм, по произвольной формуле этого исчисления определяющей выводима она или нет. Важным классом ФИ явл. непротиворечивые исчисления. Формальное исчисление наз. непротиворечивым, если в нем выводима не всякая формула. Для «логических» исчислений, в которых наряду со всякой Ф можно построить ùФ, под непротиворечивостью понимают невозможность одновременного док-ва |–Ф и |–ùФ ни для какой ф-лы Ф исчислений.

ИВ непротиворечиво в обоих смыслах. Докажем его непротивороечивость во 2-м смысле. Пусть для некоторой формы Ф известно, что она выводима: |–ФÛФº1; |–ФÛùФº0; |–ФÛùФ¹1; |–ФÛ|-/–ùФ.

Критерий выводимости

(|–_ИВ Ф)ÛФº1 при обычной булевой интерпретации логических связок.

Вопросы 27,28.

Дать определение предиката, привести пример.

Пусть U¹Æ - не пусто. n-местным предикатом на U наз. всякую ф-ию f(x₁,…,x_n)=y, где x₁,…,x_nÎU, а yÎ{0;1} (0 – ложь, 1 – истина).

Пример.

1) P₁(x)=”x – простое число”     U=N.

2) Q(x,y)=”x<y”     U=N, Z, R

Дать определение множества истинности предиката.

Пусть P(x₁,…,x_n) – некоторый предикат. Его множеством истинности наз. мн-во T_P, которое устроено след. образом: T_P={(U₁,…,U_n)| U₁,…,U_nÎU, P(U₁,…,U_n)=1}. Из данных предикатов можно строить другие, более сложные с помощью ряда соотв. операций: булевы операции (Ù, Ú, ®, ù ). Очевидно, как преобразуются мн-ва истинности данных предикатов под действием этих операций:

T_PÙQ=T_PÇT_Q; T_PÚQ=T_PÈT_Q; T_ùP=U-T_P=T_P; T_P®Q=U-(T_P-T_Q)=T_ùPÚQ=(U-T_P)ÈT_Q.

Дать определение истинности предиката «сущ» х Р и «любое» х Р.