Discrete 15 29

Содержание 15 Выборка. Сочетания с повторениями и без повторений.................................................................2 16 Перестановки с повторениями и без повторений. Полиномиальная формула.............................4 17 Бином Ньютона. Свойства биномиальных коэффициентов...........................................................5 18 Принцип включений и исключений..................................................................................................6 19 Задачи о распределениях. Случаи T и U...........................................................................................8 20 Задачи о распределениях. Случаи V и W.........................................................................................9 21 Обобщённый арифметический треугольник. Теорема о связи между обобщённым арифметическим треугольником порядка m и m- ичной системой счисления. Число "счастливых" автобусных билетов.......................................................................................................10 22 Свойства обобщённых коэффициентов..........................................................................................12 23 Рекуррентные соотношения. Лемма о линейной комбинации. Теорема об общем решении однородного линейного рекуррентного соотношения 2 порядка с постоянными коэффициентами. Случай действительных корней............................................................................13 24 Рекуррентные соотношения. Теорема об общем решении однородного линейного рекуррентного соотношения 2 порядка с постоянными коэффициентами. Случай комплексных корней. Однородное линейное рекуррентное соотношение k-го порядка с постоянными коэффициентами....................................................................................................................................16 25 Функции k-значной логики. Теорема о количестве функций k-значной логики, зависящих от n аргументов. Основные функции k-значной логики............................................................................19 26 Функциональная полнота. Теорема о функциональной полноте класса Поста .........................23 27 Общие принципы построения формальных теорий. Классическое исчисление высказываний L. Формулы, аксиомы, правило MP.....................................................................................................25 28 Доказательство теоремы A→A. Теорема о дедукции...................................................................27 29 Следствие теоремы о дедукции. Транзитивность импликации и правило сечения...................30

1

15 Выборка. Сочетания с повторениями и без повторений Процедуры выбора: 1 Выбор с возвращением

2 Выбор без возвращения

a i, 1 ∈A

a i, 1 ∈A

a i, 2 ∈A

a i, 2 ∈A ∖ {a i ,1 }

⋯

⋯

a i, k ∈A

a i, k ∈A ∖{a i, 1 , a i, 2 ,...,a i ,k−1 }

Запись полученная по одной из процедур выбора называется выборкой.

[a i ,1 ,a i ,2 ,... a i ,k ] Выборка

называется

неупорядоченной

выборкой

или

сочетанием

из

n

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



Ckn , n - Биномиальный коэффициент. Число сочетаний без повторений из n k элементов по k меньше числа размещений из n элементов по k в k ! раз, так как перестановка местами выбранных

k

предметов не даёт нового сочетания, а

переставить k предметов можно только k ! способами. k n

С=

A kn k!

=

n! k !n−k!

2

Сочетание с повторениями - неупорядоченная выборка, сделанная по первой процедуре выбора.

Ckn Каждому сочетанию с повторениями из n элементов по k соответствует перестановка k неразличимых точек и n−1 неразличимой между собой перегородки (количество точек, лежащих левее первой перегородки указывает на кратность a 1 , между первой и второй на кратность a 2 и так далее).

Pk , n−1=

nk−1! k n−1 =Cnk−1 =C nk −1 k ! n−1!

Ckn =C knk −1

3

16 Перестановки с повторениями и без повторений. Полиномиальная формула Перестановка без повторений - размещение без повторений из n элементов по

n . Pn=Pn =n! Перестановка с повторениями Пусть у нас имеется

n1 - элементов 1-го типа;

n2 - элементов 2-го типа, и далее; Тогда

nk - элементов k-го типа, причём элементы каждого типа неразличимы

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

Pn1, n 2, .., nk =

n1 n 2..nk ! n1 ! n2 ! ..nk !

-

перестановка

с

повторениями,

где

n1 , n2 , ..,n k - полиномиальные коэффициенты. Сначала мы считаем, что все элементы разные, но так как предметы 1-го типа неразличимы, а переставить

n1

можно n1 ! способами, то количество перестановок будет в n1 ! раз меньше общего числа перестановок. Аналогично с n2, n3, .. ,nk . Полиномиальная формула.

x 1 x 2 ..x m n =

∑

k i ∈ℕ0

k1

k 1k 2..k m=n

Pk 1, k 2, ..,k m =

k2

km

Pk1, k 2, .. ,k m  x 1 x 2 .. x m

n! k 1 ! k2 !..k m ! 4

,

17 Бином Ньютона. Свойства биномиальных коэффициентов

n

n

ax =∑ Ckn ak x n−k - формула бинома Ньютона k=0

Свойства биномиальных коэффициентов.

Сn0=Cnn =1

C1n =Cn−1 n =n n−k

Ckn =Cn−k , Cn = n

n! n! k = =Cn n−k !n−nk ! n−k ! k !

Cn0C1n ..Cnn=2n Cn0−C1n ...−1n Cnn=0 , Ckn1 =CknCk−1 n

n! n! n! n−k1n! k n!n−k1k   = = = k !n−k ! k−1!n−k1! k !n−k1! k ! n1−k! n!n1 n1! k = = =Cn1 k !n1−k! k !n1−k !

5

18 Принцип включений и исключений Пусть имеем N некоторых предметов и  1,  2, .., n - свойства предметов.

N1, 3 , 4  - количество предметов, которые обладают свойствами 1, 4 и не обладают свойством 3. Формула включений и исключений.

N1 ,  2 , .. , n =N−N 1 −..−N n N1, 2 ...Nn−1 , n −N 1,  2,  3  n

−1 N1, 2, ..,n  Доказательство: 1.

n=1 , N1 =N−N 1  , верно

2. Допустим

N1 , 2 , .. ,k =N−N 1 −..−N k N1, 2 ..−1n N1, 2, ..k  3. Докажем справедливость для n=k1

N1 , 2 , .. , k , k 1 =N k1 −N 1,  k1 −..−N k ,k 1 N1, 2, k 1  n

−1 N1, 2, ..,  k1  N1 , 2 , ..,  k , k1 =N 1 , 2 , .., k −N 1 ,  2 , .., k , k 1 

N1 , 2 , .., n =N−N1 −..−N n N 1,  2 ... N n−1 , n − −N 1,  2,  3 ..−1n N 1,  2, .., n  Формула доказана. Задачи о смещениях Перестановки с

n предметами, за которыми зафиксированы первоначальные

позиции.

6

Dn - количество перестановок предметов, когда ни один из них не стоит на первоначальной позиции.

Dn =

n!  общее количество перестановок

Dn =n!1−

−

1 C n n−1! 

...

число выборов 1−го предмета , сохраняя позицию

n n −1 Cn  число выборов n предметов , сохраняя позицию

1 1 n! n 1  −...−1 ≈ 1! 2! n! e

Dn ,k=Ckn D n−k - количество перестановок предметов, когда k из них сохраняют свою позицию.

Dn ,k=

n! 1 1 n! n n−k n−k! 1−  −...−1 ≈ k !n−k ! 1! 2! n−k ! k ! e

7

19 Задачи о распределениях. Случаи T и U Случай T. Распределение неразличимых шаров по различимым ящикам. Введём

k−1 перегородку. Левее первой - количество шаров в первом ящике,

между первой и второй - количество шаров во втором ящике, и так далее. Очевидно, что любому способу распределения ящикам, соответствует

n неразличимых шаров по

k различным

n неразличимых точек и k−1 перегородка. Количество

таких перестановок: Pn,k−1=

nk−1! k −1 =Cnk−1 n !k−1 !

T n,k=Ck−1 nk −1 В случае когда ни один из ящиков не пуст нахождению,

сколькими

способами

можно

из

T ∗ n,k  , задача сводится к

n−1 позиций выбрать

k−1

расстановок перегородок. −1 T ∗ n,k =Ckn−1

Случай U. Распределение различимых шаров по различимым ящикам. n Un,k=k×k×..×k  =k n раз

В случае, когда ни один из ящиков не пуст, количество распределений равно

U∗ n,k=

kn

1 n C k k−1 

−

общее число способов



число способоввыбора одного пустого ящика

Числа Стирлинга 2-го рода

8

2 n C k k−2  число способоввыбора двух пустых ящиков

k −1 k−1 .. −1 Ck  числоспособоввыбора n−1 пустых ящиков

20 Задачи о распределениях. Случаи V и W Cлучай V. Распределение различимых шаров по неразличимым ящикам.

U∗ n ,k - так как перестановка k ящиков местами в случае V ∗ не V n,k= k! ∗

даёт нового способа распределения, а переставить ящики можно k способами. ∗ ∗ V n , k= V n , k V n ,k−1..V∗ n, 1   нет пустых ящиков

один ящик пуст

Случай W. Распределение неразличимых шаров по неразличимым ящикам. ∗ ∗ W n,k= W n, k W n ,k−1..W∗ n ,1   нет пустых ящиков

один пустой ящик

W∗ n , k=W n−k , k

9

21 Обобщённый арифметический треугольник. Теорема о связи между обобщённым арифметическим треугольником порядка m и m- ичной системой счисления. Число "счастливых" автобусных билетов k 0

1

2

⋯

m-2

m-1

m

⋯

1

1

1

1

⋯

1

1

0

⋯

2

1

2

3

⋯

m-1

m

m-1

⋯

3

1

3

6

⋯

⋯

⋯

n

m1 ⋯ m 2

Сm n,k - арифметические коэффициенты. Сm 1,k=0,

Cm n,k =

если km−1 ; Сm 1,k=1, если k≤m−1

{

Cm n−1, kCm n−1, k−1..Cm n−1,0, если k≤m−1 Cm n−1, kCm n−1, k−1..Cm n−1, k−m1, если km−1

Теорема о связи

между обобщённым арифметическим треугольником

порядка m и m-ичной системы счисления

Сm n,k равен количеству n-разрядных чисел в m-ичной системе счисления, сумма которых равна k, причём допускаются записи, начинающиеся с 0. Доказательство: обозначим это количество за Bm n,k

{

Bm 1,k = 1, 0,

если k≤m−1 если km−1

10

Bm n, k =

{

B m n−1, kB m n−1, k−1..B m n−1,0, если k≤m−1 B m n−1, kB m n−1, k−1..B m n−1, k−m1, если km−1

Cm n,k =Bm n,k Счастливые билеты. Пусть имеется номер из одних нулей, 000000 - самая малая комбинация, 999999 самая большая комбинация.

C10 3, k , k∈{0,1, 2,.., 27} Всего способов C10 3, k

2

L - число всех счастливых билетов;

L=C10 3,02 C10 3,12 C10 3,22 ..C 10 3,132 ×2=55252

=

55252 1 ≈ - вероятность "счастливого" билета. 1000000 18

Второй способ: каждому счастливому билету можно поставить в соответствие билет с суммой цифр 27. С10 6,27=55252

11

22 Свойства обобщённых коэффициентов 1.

С2 n,k =Ckn

2.

Cm n,k =Cm n, nm−1−k , доказательство:

a 1 a2 ..an =k m−1−a 1 m−1−a 2 ..m−1−a n =nm−1−k 3.

Cm n,0Cm n,1..Cm n,nm−1=mk - общее количество различных чисел

4. Зафиксируем первые i разрядов. Пусть сумма первых i разрядов равна S . m−1i

Сm n,k =

∑ s=0

Cm i,s Cm n−i,k−s

- формула разложения по первым

разрядам. 5. Формула разложения по нулевым разрядам. n

Сm n,k =∑ Cns Cm−1 n−s, k−ns s=0

S - количество нулевых разрядов; Cns - количество способов выбора позиции для S нулей; Cm−1 n−s, k−ns - все числа уменьшили на единицу.

12

23 Рекуррентные соотношения. Лемма о линейной комбинации. Теорема об общем решении однородного линейного рекуррентного соотношения 2 порядка с постоянными коэффициентами. Случай действительных корней Рекуррентным

соотношением

k-ого

порядка

называется

соотношение,

позволяющее вычислить каждый член последовательности начиная с k+1, через k предыдущих членов этой последовательности. Решением рекуррентного соотношения называется

последовательность,

которая

при

подстановке

в

это

отношение

превращается в верное равенство. Общим решением рекуррентного соотношения k-го порядка называется решение, содержащее k произвольных постоянных, путём подбора которых можно удовлетворить любые начальные условия. Линейным

однородным

рекуррентным

соотношением

2

порядка

с

постоянными коэффициентами (ЛОРС2ППК) называется соотношение вида:

f n2=p f n1q fn , p, q−const Решения ЛОРС2ППК ищутся в виде x n :

x n2 =p x n1 q xn x 2 =pxq

x 2 −px−q=0 - характеристическое уравнение ЛОРС2ППК. Лемма о линейной комбинации решений ЛОРС2ППК. Если последовательности f n ,gn

- решения некоторого соотношения, то

hn=A fnBgn - так же решение этого соотношения. Доказательство:

13

{

fn2=p f n1q fn | ×A gn2=p gn1q gn | ×B

A fn2B gn2=A p f n1A qf nB p gn1B q gn= pA f n1Bgn1q A f nB gn=phn1qhn

Теорема об общем виде решения ЛОРС2ППК. Пусть имеем некоторое ЛОРС2ППК, составим характеристическое уравнение:

x 2 −px−q=0 В случае, если D0 , x 1 ≠x 2 , x 1, x 2 ∈ℝ :

С1 x n1 C2 x n2 - решение. Покажем, что для любых констант A ,B можно подобрать значения C1 и C 2 , чтобы:

f 0=A f 1=B

{

C1 C2 =A C1 x 1C2 x 2 =B

∣ ∣

=

1 1 =x 2−x 1 ≠0 x1 x2

В случае, если D=0 , x 1 =x 2 , x 2 ∈ℝ :

f n=x n1 C1 nC 2  2 x 1=p

14

x 21 =−q f n2=2x 1 fn1−x 21 f n=x n2 1 C1 n C2  Покажем, что для любых констант A ,B можно подобрать значения C1 и C 2 , чтобы:

f 0=A f 1=B

{

C1 =A C1 x 1C2 x 2 =B

∣ ∣

=

1 0 =x1 ≠0 x 1 x1

15

24 Рекуррентные соотношения. Теорема об общем решении однородного линейного рекуррентного соотношения 2 порядка с постоянными коэффициентами. Случай комплексных корней. Однородное линейное рекуррентное соотношение k-го порядка с постоянными коэффициентами Рекуррентным

соотношением

k-ого

порядка

называется

соотношение,

позволяющее вычислить каждый член последовательности начиная с k+1, через k предыдущих членов этой последовательности. Решением рекуррентного соотношения называется

последовательность,

которая

при

подстановке

в

это

отношение

превращается в верное равенство. Общим решением рекуррентного соотношения k-го порядка называется решение, содержащее k произвольных постоянных, путём подбора которых можно удовлетворить любые начальные условия. Линейным

однородным

рекуррентным

соотношением

2

порядка

постоянными коэффициентами (ЛОРС2ППК) называется соотношение вида:

f n2=p f n1q fn , p, q−const Решения ЛОРС2ППК ищутся в виде x n :

x n2 =p x n1 q x n

x 2 =pxq x 2 −px−q=0 - характеристическое уравнение ЛОРС2ППК. Теорема о виде общего решения ЛОРС2ППК. Пусть имеем некоторое ЛОРС2ППК, составим характеристическое уравнение:

x 2 −px−q=0 В случае, если D0 , x 1,2=rcos ±i sin 

16

с

f n=r n C1 cosC 2 sin x 1 =rcos i sin x 2 =r cos −i sin x n1 =r n cos ni sin n x n2 =r n cos n−i sin n x n1x n2 2 x n1−x n2 2i

n

=r cos n n

=r sin n

C1 r n cos nC 2 r n sin n=r n C1 cos nC 2 sin n Покажем, что ∀ A, B:∃C 1, C 2 :

f 0=A f 1=B

{

C1 =A rC1 cos r C2 sin =B

∣

=

∣

1 0 =r sin r cos  r sin 

Линейным

однородным

рекуррентным

соотношением

k-ого

порядка

постоянными коэффициентами (ЛОРСkППК) называется соотношение вида:

f nk=a 1 f nk−1a 2 f nk−2..ak fn x k −a 1 xk −1−a 2 x k −2 −..−a k=0 - характеристическое уравнение соотношения. 17

с

Теорема о виде общего решения ЛОРСkППК. Пусть имеется некоторое ЛОРСkППК, решим его характеристическое уравнение.

xn1 C1 nC 2..nm−1 Cm

1.

x 1 ∈ℝ ,

2.

x 1,2 =2cos ±i sin r n cos C1 nC 2..nm−1 Cm sin D 1nD2 ..nm−1 D m 

18

25 Функции k-значной логики. Теорема о количестве функций k-значной логики, зависящих от n аргументов. Основные функции k-значной логики Ek ={0, 1,..,k} f : Enk E k - функция k-значной логики; Pk - множество всех функций k-значной логики; - множество всех функций k-значной логики от n переменных; Pn k

x1

x2

⋯

xn

f

0

0

⋯

0

a1

0

0

⋯

1

a2

⋯

⋯

⋯

⋯

⋯

0

0

⋯

k−1

ak

⋯

⋯

⋯

⋯

⋯

k−1

k−1

⋯

k−1

ak

n

Теорема о количестве различных функций k-значной логики от n переменных. k ∣Pn k ∣=k

n

Доказательство: Каждая функция k-значной логики однозначно определяется вектором своих значений - вектором размерности k, каждая координата которого может принимать k различных значений. Тогда общее количество всевозможных векторов такого вида

будет равно

k k×k×..×k =k k

n

.

n

19

Основные функции k-значной логики. 1.

f x=C - константа;

2.

x=x1modk - отрицание Поста;

3.

~ x=k−1−xmodk - отрицание Лукасевича;

4.

x⋅ymodk - умножение по модулю k;

5.

x∧y=min {x , y} - конъюнкция;

6.

x∨y=max {x , y} - дизъюнкция;

7.

xy modk - сложение по модулю k;

8.

x−y modk - разность по модулю k;

{

x−y= x−y , если x≥y kx−y , если xy 9.

x ∸ y - усечённая разность;

10. ji  x=

{ {

11. J i x=

1, 0,

x=i - характеристическая функция I типа (рода); x≠i

k−1, x=i - характеристическая функция II типа (рода); 0, x≠i

12. V k x , y=x∨y - функция Вебба.

20

Таблица функций n переменных k-значной логики для n=2,k=3

x

y

x

~y

x⋅y

x∧y

x∨y xy x−y x ∸ y j1 x J 1  y V k x , y

0

0

1

2

0

0

0

0

0

0

0

0

1

0

1

1

1

0

0

1

1

2

0

0

0

2

0

2

1

0

0

0

2

2

1

0

0

2

0

1

0

2

2

0

0

1

1

1

1

1

0

2

1

1

2

1

1

1

1

2

0

0

1

0

2

1

2

2

0

2

1

2

0

2

0

1

2

0

2

0

0

2

0

0

2

2

2

2

0

0

0

2

1

0

1

1

1

2

0

1

1

0

0

0

2

2

0

0

2

2

2

1

0

0

0

2

0

Докажем справедливость законов де Моргана:

~x∧y=~ x∨~ y 1.

x≤y

~ x∧y=~ x=k−1−x ~ x∨~ y=k−1−x∨k−1−y=k−1−x 2.

xy ~ x∧y=~ y=k−1−y ~ x∨~ y=k−1−x∨k−1−y=k−1−y

~x∨y=~ x∧~ y 1.

x≤y x∨y=min{x ,y}=y ~ x∨y=~ y=k−1−y ~ x∧~ y=k−1−x∧k−1−y=min{k−1−x ,k−1−y}=k−1−y 21

2.

xy ~ x∨y=~ x=k−1−x ~ x∧~ y=k−1−x∧k−1−y=k−1−x

~~ x=x ~~ x=~k−1−x=k−1−k1x=x

x∧y=~~ x∨~ y

22

26 Функциональная полнота. Теорема о функциональной полноте класса Поста {¬, ∨} Теорема о представлении функций k-значной логики в первой форме. Для каждой функции k-значной логики справедлива формула:

∨

f x 1, x 2, .., xn =

 Ja x 1 ∧Ja x 2 ∧..∧Ja  xn ∧fa 1, a 2,. ., a n  1

2

n

 a1, a2, .., an

Доказательство:

f b 1, b 2, .. ,bn =0∨0∨..∨ Jb b 1 ∧Jb b1 ∧..∧Jb bn ∧fb 1, b 2, ..,b n ∨0∨..∨0= 1

2

n

=k−1∧k−1∧..∧k−1∧f b 1, b 2, ..,b n =f b1, b 2,. .,bn 

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

Pk

2.

{0,1, ..,k−1, J0 x ,J 1 x, .., Jk x,∧ , ∨}

Теорема о функциональной полноте класса Поста {¬ ,∨ } . Класс {¬ , ∨ } - функционально полный. Доказательство: 1. Построим константу

max {x ,x ,  x ,..}=k−1 При каждом фиксированном х получим полный набор констант.

23

2. Получим J i x Покажем, что 1.

J i x=1max {x }  i≠k−1

x≠i 1max {x}=1k−1=0  =k −1−i

J i x=0 2.

x=i 1max {x}=1k−2=k−1  i=k−1

J i x=k−1

3. Получим min

{

f s ,i  x= s, x=i 0, x≠i

}

f s ,i  x=s1max k−1−s, Ji  x

Покажем, что любую функцию одной переменной можно представить через f s ,i  x .

gx=max{f g0,0 x, f g1 ,1  x ,.., f gk −1 ,k−1 x} gb=max {f g0, 0 b,f g1, 1 b , ..,f gk −1 ,k−1 b}=f gb,b b=gb ~ x=max{f k−1,0 x, f k−2,0 x, .., f 0,k −1  x} x∧y=~~ x∨~ y

24

27 Общие принципы построения формальных теорий. Классическое исчисление высказываний L. Формулы, аксиомы, правило MP 1. Алфавит - множество символов; 2. Формулы

- множество правильно построенных предложений из символов

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

Правилом вывода

GA 1, A2, .. , An−1 , B

называется n-местное отношение на

множестве формул. Если A 1, A 2, .., A n−1 , B вступают в это отношение, то говорят, что

B непосредственно выводится из A 1, A 2, .., A n−1 и записывают это в виде: A 1, A 2, .. , A n−1 B Формула

G

G или A A .., A ⊢ B . 1, 2, n−1

называется

теоремой

формальной

теории,

если

существует

последовательность B1, B2, .. , Bm−1 , Bm =B , каждый член которой либо аксиома, либо получен по некоторому правилу вывода из предыдущих членов последовательности. Пишут ⊢ B . Говорят, что формула B выводима из множества гипотез Г и пишут Г ⊢ B , если существует последовательность

B1, B2, .. , Bm−1 , Bm =B , каждый член которой

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

L - классическое исчисление высказываний.

25

1. Алфавит: Bi , A ,  ,¬ , ( , ) 2. Формулу определим индуктивно 1.

Bi ,A - формулы;

2. Если A ,B - формулы, то ¬A ,A  B - формулы; 3. Других формул нет. Замечание: самые внешние круглые скобки будет опускать. 3. Введём 3 схемы аксиом 1.

A B A

2.

A BC A B A C

3.

¬A ¬B¬B  AB

Аксиомой по данной схеме аксиом называется формула, полученная из схемы аксиом подстановкой на место переменных в эту схему аксиом других формул. 4. Правило MP (Modus ponens)

A B ,A MP B

26

28 Доказательство теоремы A→A. Теорема о дедукции Теорема ⊢ A  A Доказательство:

B1 :



A B C A A A A



- по II схеме аксиом.

B1 : A  A  A A A A  AA  A B 2 : AA  A A - аксиома по I схеме



A B A AA



B 3 : A A AA  A - по MP, применённому к B1, B2 B 4 : A  A A - аксиома по I схеме

  A B A A

B5 : A  A - по MP к B 3, B 4 Теорема доказана.

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

Г, A ⊢ B⇔ Г ⊢ A B 1.

Г ⊢ A B⇒ Г, A ⊢ B A 1, .., B m−1 , A B B1, .., Bm−1 , A B, A ,B - по MP к предыдущим

2.

Г, A ⊢ B⇒ Г ⊢ A B B1, B2, .. , Bm−1 , B 27

.., A B 1, ..,A  B2, .., A  Bi−1 ,.., A Bi , .., A B Покажем, что можно сделать вставки так, что A  B - вывод из списка Г . Покажем по методу математической индукции. 1. Проверим, возможны ли вставки перед A  B1 ◦

B1 - аксиома из формул из Г

B 1  A B 1  ,B 1,  аксиомапо Г

◦

A B1  поMP к предыдущему

B1 =A , A  A Вставки 4 формулы из доказательства ⊢ A  A

2. Допустим, что все вставки до A  Bi−1 сделаны 3. Докажем, что можно сделать вставку перед формулой A  Bi

..., A B B1, B2, .. , Bi−1 ,B i ,.., B m=B ◦

Bi - аксиома или гипотеза из Г B i A B i  , Bi ,  аксиомапо Iсхеме

◦

A Bi  MP из пред.

Bi =A , A A Вставка состоит из 4 формулы из доказательства ⊢ A  A

◦

Bk =Bj Bi , B j , k , ji

...,  A Bj  Bi , .., A Bi  A B j Bi   A Bj A  Bi   аксиома поII схеме

28

A  B j A  Bi  ,  по MP к формулам



A  Bi  по MPк формулам

На основании метода математической индукции утверждаем, что

∀i

можно

сделать вставки, в том числе и для i=m . То есть можно получить вывод формулы

A  B из множества гипотез Г .

29

29 Следствие теоремы о дедукции. Транзитивность импликации и правило сечения Транзитивность импликации.

A  B,B C ⊢ A  C Доказательство: 1.

A  B - гипотеза;

2.

B C - гипотеза;

3.

A - гипотеза;

4.

B (по MP к 1 и 3)

5.

C (по MP к 2,4) A B,B C , A ⊢ C  Г

Г, A ⊢ C - применим теорему о дедукции; 6.

A  B,B C ⊢ A  C

Правило сечения.

A B C, B ⊢ A  C 1.

A B C - гипотеза;

2.

B - гипотеза;

3.

A - гипотеза;

4.

B C (по MP к 1, 3)

5.

С (по MP к 2,4) 30

AB C ,A ⊢ C  Г

6.

A B C, B ⊢ A  C по теореме о дедукции.

31