Diskretka

Diskretka.doc20.02.2014

141

Формула ( x1) A1(1)(x2) ( x1)не(А

2(2)(x2,x3)) — приведенная;

Формула не( x2) A1(1)(x2) → А2(1)(x1) — неприведенная.

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

множествасвободныхисвязанныхпеременныхэтиформулсовпадают.

улан зывается приведеннойформой

Такаяприведеннаяформ

даннойформулы.

Влогикевысказываниймыввелидвенормальныеформы

— дизъюнктивную

нормальнуюформуиконъюнктивнормальформу. ную

нормальнаяформа

Влогикепредтакжеимеетсякатов

,целькоторой

— упрощение

процедуры доказательств.

нормальной,

Приведеннназываетсяформула

еслионсодержитасимволов

кванторовилисимволыекванторовстоятвпереди..(логсимволыческие

предикатовст бластиятдейсткаждогов)ияантора.

Длялюбойприведеннойформул

ысуществуетравносильнаяейнормальнаяформула

тойжедлиныпод(длинойформулыбудемпониматьобщеечисловходящихнеесимволов

предикатов,логичессимволовкиханторов)олов.

нормальнойформой

Нормальнаяформуланазывается

даннойформулы.

Алгоритмпреобразовформулнормальнуюформуния

1Исключ. логичесвязки↔→тьпомкиефощьюрмул

F↔G=(F→G) (G→F),

F→G=не F G.

2. Использоватьзакон

ненеF=F, законыдеМоргана:

не( F G)не=

F неG,не( F G)не= F неG,

законы

,

,

( x)F (x)

≡ ( x)(F (x))

( x)F (x)

≡ ( x)(F (x))

чтобыпрознакотрицанияестивну

трьформулы.

3Переим. связапенр,еслиоватьменныеэтообходимо.

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

самоеначалоформулыдляприведенияеекнормальнойформе.На,приведеммер

формулу ( x)P(x) → ( x)Q(x) кнормальнойформе:

( x)P(x) → ( x)Q(x) =

( x)Q(x)

(( x)P(x))

Q(x))

= ( x)(P(x))

( x)=Q(x) ( x)(P(x)

( x)P(x) → ( x)Q(x) — это

След,новатеформулырмальнаяформа

( x)(

Q(x)).

P(x)

Исчислениепредикатов

теопепорядкаийвого

Исчислениепредикатовназываютеще

.

Висчисленпредикатов,такжекаксчислении

разрешимости.

выск,нпервомазыванийпо

важностиместестоитпроблема

Новисчислениивысказыванийпроблемаразрешимсостояларешениив просасти

явлданнаяяетсяисложфутождественнокцияаяистинной,выполнимойили

тождественноложной.

Тепжеворь

просследуетпоставитьиначе.Принимлиданнфункциязначениеет1

при:

а)любыхпредметныхпеременныхилюбыхпредикатах,

б)нанекотмнпожествередметныхомпеременныхилюбыхпредикатах,

в)принекотозначенияхпредметныхпеременныхлюбыхпредик

атах,

Diskretka.doc20.02.2014

142

г)явлонаяетсяитождественноложной,..невып? лнимой

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

эффективнспособадляраспобщезначимостигознаванияфункций.

Поэтомувисчислениипредикатуказываетсянекоторая

совокупностьформул,

которназываютсяе

аксиомами исоставляют

аксиоматическуютеорию

,иуказывается

конечноемн жествотношениймеждуформулами,составляющее

правилавывода

.

Аксиоматичетеопрвыводаияавиласоставляютк

исчисленияпредикатов

.

Символамиисчисленисчисленияпредикатовилиалфавпредикатовтомявляются

символыпредметныхпеременных,символыпредикатов,логическсимволыотр( цание

имплик),символыкванторов,циятакжескобкизапятая.

Сформулаксиомыисчпрследикату мния

овиправилавыводаисчисления

предикатов.

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

.

Пусть A, B и C - любыеформулы.

Аксиома1

.

A →( B→C).

Аксиома2

. (A→(B→C))→((A→B)→C))(A.

Аксиома 3.

(неB→ неA)→((

неB→A)→B).

Аксиома4

.

( хi) A(х i)→

A(хj),гдеформула

A(х i) несодпержитеменной

хj.

Аксиома5

.

A(х i)→( хj) A(х j),гдеформула

A(х i) несодпержитеменной

хj.

Правилавыводаисчисленияпредикатов.

(1)Пусть

(А(х)→В)

и В несодпержитеменной

х,тогда

Этопрасвязыванияилокванторомсуществования.

((( x)A(x)→В)

(2)Пусть

В→А(х)

и В несодпержитеменной

х, тогда

Этопрасвязыванияилокванторобщн. омсти

(В→((

x)A(x)))

В можнозаменитьдругойпер

(3)Связаннуюпеременнуюформулы

еменной,не

являющейсясвободной

В. Этоправилопереименованиясвязаннойпеременной.

Следоиэквиваленцияание

Q2

Q1 , если

Высказывформательная

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

импликация Q1 →Q2 обращаетсявистинноевысказываниеприлюбыхнаборах

нияпринятообозначение

значений

переменных,входящихнее.Дляоперациилогическогоследова

Q1 Q2 .

Q1(x1, х2 , …, хn) и

Q2 (x1 ,х

2 , …, хn),аихмножества

Пустьданыпредикаты

истинноссоответиственно

T(Q1 )

и

T(Q2 ).

Поскольку

Q Q ,

тоесли

1

2

(x1 , x2 ,..., xn ) T (Q1 ), т.е.

Q1 ис,тдолжнаиннабытьистинна

Q2 ,

т.е. (x1 , x2 ,..., xn ) T (Q2 ).

Посколькутаксвойстводолжноебытьлюбогоэлементаиз

T(Q1 ),

этоопреде

ление

подмножества.Итак,

T(Q1 ) T(Q2 ).

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

формы Q1

и Q2 назовем равносильными,есприлюбомнаборезначенийпеременных,

ности:

входящихних,вы

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

Q Q .

Очевидно,чтоесли

Q Q , a

Q Q

то Q Q .

Тогда T(Q1) = T(Q2).т.е.

1

2

1

2

2

1

1

2

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

Пример.

R.

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

тельныхчисел

x2 − 5x + 6

= 0 их

2

- 5х+не6являются=равносильными0 .

x − 2

Diskretka.doc20.02.2014

143

3x + 8

= 0 иЗх+являются8 =равносильными0 .

x 2 +1

ln (х - 1) + ln (х+ и1) = 2

ln (х 2 - 1)неявляются= 2равносиль

ными.

2

x + 3 = x −1 и+х3

= (х - 1 )

н е являютсяравносильными.

4 − 8x

≥ 0

и(4

- 8х)(2х >не+являютсяравносильными0 .

2 + x

4 − 8x

> 0

и(4

- 8х)(2х являются>+0равносильными.

2 + x

x 2 − x 4

≥ 0

и 1 − x2

≥ 0 неявля

ютсяравносильными.

Вматематикенарушениецептождчкипреобразоваственных

нийпрешении

уравненийилинеравенстввлечетзасобойпо

терюимеющихсяилиприобретение

посткор,т.е.изнейонних

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

Можно

доказать,что

отношениеравносильности

высказывательныхформ

обладаетизвессвойствами,нымиименно,оно

рефлективно и симметрично.

Втом

случае,кодинаковыегдаперемен

ныевкаждойизисследуемыхфопр знимаютачения

изод ногомн,ожестватношени

еравносибудетоблаьнисвойствомкжедатьсти

транзитивности.

равносильнымпреобразованием

Q1 ее

Тогданазовем

высказывательнойформы

заменунаравносильнуюформу

Q2 . Дверавносиль

высказывательныеформы

одинаковымнабопереомен

ных,длякоторы

хустановленодинаковыйпорядок,

определяютодинтотже

предикат.

Этисвойствапредикатаиспользуютсяешенииуравне

нинеравенствй,которые

тожеявляютсянекоторымивысказывательнымиформами.Так,решениелюбогоуравнения

илинеравпредусматнства

риваетустановлмножегоистинествание

ности,.е.множества

истинноспредисоотвеемутствующего

ката.Впроцепоимножестваистинностисека

производятзамеодногопредикатаудругим,равноданному,сцельюильнымупро

щения

имеющихсявысказывательных

форм.

Пример.

2х - 13х + 2 - (6х

2 - 4х+ 5

- 6х 2) =х0= <х18=т.е.множество>3,<=>6истинн сти

каждогоизэтихуравненсостоизодногочи3йтсла.

Рассмотримпримеры,длякоторыхобластьюопределенияяв

ляетсямножество

действительныхчисел:

D = Е.

Пример.

- 3) = 0 (Q1 ) их

- 3 = 0 (Q2) —

Длядвухысказывательныхформ

— уравненийх(

- 2)(х

изх - 3следует=,что0х(

- 2)(х

- 3)т.е.верназапись= 0,

Q2

Q1. Однакоизх(

- 2)(х

- 3) = 0

неследуетх

- 3 Например= 0,х.=являе2

тсякорнемпервогоуравнения,новторого.

Пример.

Изуравнениях(

- 5)(х - 2)следует=неравенство0 х>как0,орниуравнения

—

числа25

— удовлетворяюттакжеинеравенству.

Пример.

2

+

можетследо5 > 0

ватьизлюбой

Тождественно-истинноевысказываниех

высказывательнойформы

Q, имеющейнепустоемножистиннствости

х.

T(Q) R , т.е.

форма Q→ (х 2 + 5 > 0) истинприлюбыхзначениях

Отношения следования и равносильности длявысказывательныхформ,вообще

говоря,зависятоттогом

ножества,накоторомонорассматривается.

Diskretka.doc20.02.2014

144

Пример.

D = {2, 0, 4, 5, 7,

Высказывформх>следует9изнеравтельная8х<<нствасли12,

D(Q) = N . Действительно,при

9, 10,нонесл11,еслидует13},

D = {2, 0, 4, 5, 7, 9, 10, 11}

T(Q1) = {9, 10, 11}, a T(Q2 ) = {9, 10, 11, 13} ивыполняется

T(Q ) T(Q ),

т.е.форма

Q1 →

Q2 истинна.

1

2

(D(Q) = N), T(Q1 ) = {8, 9, 10, 11}, a T(Q2 ) = {9, 10, 1 1 , 12, 13, 14 ...},

Вовто

ромслучае

отношение

T(Q1 ) с T(Q2 ) невыполняется,поскольку

8 T(Q ).

2

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

Прзаключениявило(

modus ponens) —

пр,анавитомуло,которгичное

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

F → G(x)

Правилообобщения

( -введения,

ug-правило)

R2 :

, где

G(x)

F → xG(x)

содержитсвободныевхождения

х,тогдакак

F несодержитсвободных

x.

Правило -введения (eg-правило)

R3

:

G(x) → F

xG(x) → F

Нарушениеэтихребмопривестижетванийкложнымвыво

дам,полученнымиз

истинныхвысказываний.

Пример.

Р(х)

: «натуральное х делитсяна15

», Q(x): «х

делитсяна5

Даныпредикаты

».

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

Q(x) истиннодлюбыхя

х N.Приме

нимдлянегоправило

обобщения.Имеем

Р(х)→

x Q(x): «Если х делитсяна15

,токаждоечисло

х делитсяна

5»По. ложноеучилиутверждение,таккакправило

Р(х) ,предикатам.

-введенияприменимок0

-местным,а

некодноместным,как

Можнодоказатеоремыделатьновыминыеправвывода.Так,лапоправилмимо

-

и -введенияможноввестиправилауда

лениякванторов.

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

xF(x), напримСущ« ер

ствуютстуденты,

работающиепоспециальности»Из.предметно

гомножествавсех

студентвыберемтак, ого

окоторомдействи

тельноизвестно,чтоонрабпспециальноститает,длянеговведем

константу а. Поэтому xF(x)→ F(a). Этотакназываемоеправило

-удаления,

или es-

правило (правило выбора).

xF(x) к

Правило -удаления снимаеткванторобщности,осуществляяпереходот

произвольнымформулам

F(a), F(y) идр.сучетомтого,чтоэтипеременныесвотбодны

х

в Fx.

Пример.

ИзвысказыванияКаждый«

студентколвлкомпьютеаджаеет

ром»будсле,довать

чток нкретныйстудентМаксимовтожевладеетком,пьютерроизввыбранольмноый

некоторыйсту

дент у

владееткомпьютером,ивсякийстудент

z тожевладееткомпьютером.

Приэтомнеобходпомн,ч имоть

топредметныепеременные

у и z недолжныбыть

связанными.

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

или

us-npaвилом.

Примеры.

1. «Всем Мталлы)(

— плавятсяП)(Цинк.

(Ц)

— металл.Зна

чит,цинкплавится».

Формализациявлогикепредикатовприметвид:

x(M(x)→П(х))

x(Ц (x)→

Diskretka.doc20.02.2014

145

М(х))├

x(Ц (x)→М(х))

.Снятиеквантораобщности:

(М(х)→

П(х))

(Ц(х)→

П(х))

; тогданаосновантранзимпликацииимеемтивности

(Ц(х)→М(х)),(х)→(

П(х))├Ц(х)→

П(х) .

Вывод x(Ц (x)→П(х))

— обобщениепо

R2 — верен.

2. «Всестуденты(

С)проходятпрактику(

П)Некоторые. студен

тыработаютвфирме

(Ф),значи т,некоторыеработающиевфир

ме — проходятпрактику»Формализация.

приметвид:

x(C(x)→П(х))

х(С(х)

Ф(х))├

х(Ф(х)

П(х)) .Уберем

кванторыпоправилам

us и es. Имеем (С(

a)→П(

а))

(С( a) Ф(а))

(Са)(→

П(а )) Са()

Ф( a) П(а)

Ф(а).

Вывод:

х(П(х)

Ф(х))

,т.е.существуютстуденты,которыепроходятпрактикув

фирме.

Свотношенйстваклассификациия

жество U.

Рассмотримнепустоемно

Пустьданаодноместнаявысказывательнаяфо

рма

Ф спеременной,котораяприз ачениямаетз

U, проявляясвой

ствонекоторыхобъектов

изнегоисоответствуянекоторомупре

дикату Q. Множествоистинности

T(Q) таких

объектовявляетсяподмножеством

U какуниверсальногомножества.

Пример.

Ux

= {5, 6, 7, 8, 9, 10, 11, 12, 13, 14 ...}.

Пустьдано

Высказывательнойформе

«5х<<12»

соответствуетподмножество

T1 (Q) = {5, 6, 7, 8, 9, 10, 11}

( T ( Q 1 ) U1).

Измножества

U2

= {1, 3, 5, 7, 9, 11, 13, 15}тажевысказывательнаяформ

авыделяет

множествоистинн сти

Т2 ( Q) =

{5, 7, 9, 11},

из U3 = {5, 6, 7, 8, 9, 10, 11} - T3 (Q) = U3 ,

из U4

= = {12, 13, 14, 15} рассматривысказформавыдеаемаявтельная

ляетпустое

подмножествоистинности

T4 (Q) = .

U единственноесвойство,

Этавысказ

ывательнаяформавырмножествежает

характерноедлярассматрпрназадаимножествеемогокатаном

U, т.е.одноместный

предикат Q (вдан

номслучае

«5х << 12

»)задаетсвойстводанмно.Тогдагожества

множествоэлементов,

обладающихтакимсвойством

Q,

будемназывать

объемом этого

свойства.

Еслинамножестве

U заданпредикат,выражающийнекотороесвойство

Р,

то

множество U можноразбитьнадваподмножества

Т(Р)

и U\T(P).

Такоеразбиениена

непересекающиесяподмыножества

называем классификацией множества U пооснованию

Р.

Пример.

Т(Р) =

{5, 6, 7, 8, 9, 10, 11} множествоистинн сти

Так,впредыдущпримерем

предиката Р:

«5 < х<

12» измножества

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}.

U\T(P) = {1, 2, 3, 4, 12, 13, 14, 15}.

Пустьнамножестве

U заданоещеодносв йство

Q.

Тогдавсемножество

U,

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

логическихоперацийтакуюклассифзаписывают: кациюде

Замечание.

Этоаналогичноразложебулевфупндвумокциииюперейс(.менным

P(x) Q(x) 1

подразд. 4стой.разницейчто7), каждоеслагаемоедолжноиметьвид

,таккак

Diskretka.doc20.02.2014

146

Так,впредыдущпримерем

Т(Р) =

{5,

6, 7, 8,

9, 10, 11} множествоистинн сти

предиката Р: «5 < х<

12» измножества

U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}.

U\T(P) = {1, 2, 3, 4, 12, 13, 14, 15}.

Q выражает носвоейство

— «бытьнечетным

Пустьвнашемприпредикатере

числом»Тогдаэти. двсвойствадновреклассифицируютмножествоенно

U

на

подмножества:

Т(Р)

∩ T(Q) = {5, 7, 9, 11},выполнено

Р(х)·

Q(x);

T (P)∩

P(x)

T (Q) = {6, 8, 10},выполнено

Q(x);

T (P)∩T (Q) = {1, 3, 13, 15},выполнено

P(x) Q(x),

T (P)∩T (Q) = {2, 4, 12, 14},выполнено

P(x) Q(x).

Уточпоотношение«ятиеим»спом нятияпредищью«

кат»Во.всех

n-местных

предикатах (n >уста2) некоавливаются

торые отношения междупеременными.

Примеры.

«х — друг у» выделяетизвсегомн

х и

1.Высказывформательная

жествалюдейпары

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

«х┴у

ниемдружбы.

2.Высказывформательная

» выделяетизмноже

ствапар,напримерямых

плос,тепары,косторыетивязаныот

ношениемперпендикулярности.

3.Высказывформательная

«х2 +у

2 + z2

= 16»выделяетизвсегомнтроекжества

координатте,которыесвязаныотношением«

точкаскоординатами

(х; у; z)

лежитна

сферецентрвначалекооимрадиусомдинат

R = 4».

Отрицаниявисчислениипредикатов

Вразговречидляпорнойстротрицаниябычноенияпередсказуемымставятчастицу

не.

Пример,

1а «Студент х учитсянафакультетепрограммирова

ния»имеетотрицание

16 «Студент х неучитсянафакультетепро

граммирования».

?Новсегдалипостакимроеннобразотрицаистим?е ниено

Утверждения 2а

«Всевыпускникиколледжейпродолжилиоб

разованиевузе

»и

2б

«Всевыпускникиколледжейнепродолжи

лиобразованиевуз

е»неявляютсяотрицанием

друга,таккакониобаложны.

За «Некотвыпускникиорыелледжейпро

должилиобразование

Парыутверждений

вузе»и

36 «Некотвыпускникиорыел

леджейнепродолжилиобразованиевузе

»тожене

служатотри

цаниемдруга,

таккакониобаистинны.

Втортретьяи парыутверждотличаютсяпетемрвыхний,чтодержат

квантсловавсе«»ирныенекот« »Апри. пострые

роенииотрицанийдляпредложений,

содержащихкванторы,приввотрицаниямдения

не передсказуемымнесрабатыв

ает.

Можновоспользодр,унгиверсальным,приемоматьсяпостроенияотрицаний

неверно,что...

предложе,содержащихква,добавивнийторыобщееотрицание

Тогдаво

втоприНеверноом« ,чтоеревсевыпускникиколледжейпродолжилиобразованиевузе»

совпадаетпосмыслуутверждениемНекоторые« выпускникикол

леджейнепродолжили

образованиевузе»Таким. образом,отри

цаниемпредложения

2а служит 36, аотрицанием

За служит 26.

Симвобщеетрицпринятоелическиза помосывать

щьюлиобчертыощей,

либоотрицаниясамогоквантора.

Diskretka.doc20.02.2014

147

x(Φ(x))

x

x

x

x

Дляотрицанияпредложения

возможнызаписи

(Φ(

)),или

(Φ(

)),или

( x(

(x))):

x(Φ(x)) x(

(x));

Φ

Φ

Этиравносильностиявляютсяобоснованиемметодапо

строенияотрицаний

высказыва,содержащихкванторы.Дляпостроенияий

отрицания

высказываний,

содержащихквантор

( | ),достаточнозаменитьегонадругойквантор

( | ) ивзять

отрицаниевыражения,накотороеэтотквабыл«торавешен».

Длямногоместныхкванторовтакжеприменяетсяэтоправило:осуществляется

последоватпеотрицаниярельсквантосыйслнапваедлного,стоящеезажение

квантором,самзаменяютнадвойственный.

x y z(R(x, y, z))

Например,дляформулы

постр:оимицание

x y z(R(x, y, z)) x(

y z(R(x, y, z)) x y(

z(R(x, y, z))) x y z(

(x, y, z))).В

R

подразд. была4.показана8 булевд

войственностьконъюнкциидизъюнкции.Поэтомудля

сложныхвысказыван,состоящизпростых,разий

деленныхоперациямиконъюнкции

( ) заменитьна

дизъюнкции,

отрицание строитсяследующимобразом:нужновсекванторы

( ),инаоборот;всвязкие

и ( )

заменитьна

или ( ), инаоб;ивзятьотрицаниерот

утверждения.

Контрольныевопросы

1Что.называетсяпредикатом?Приведитепримерыпредикатов.

2Какой. предикатназывается

азрешимым,тождественноистинным.Тождественно

ложным?

3Перечислите. операции,котм рыежносуществитьнадпреди.Какатами

применяюпредиквалгебре?Чтакоемножествосятыистиннпредиката? сти

4Из.чегосостоиталфавитлогикипреди?Чтотакоатов

еквантор?

5Что.называетсяформулойлогикипредикатов?

6Сформулируйте. основныеправилапостроформул. ния

Diskretka.doc20.02.2014

148

Литература

1.

Акритас.Основыкомбинаторнойалгебрысприложениями.

– М.Мир: , 1994

2.

АлексанП.С.Вветеордмровнижествбщуютопологию.М.На:

ука,

1977. - 367с.

3.

Архангельск..Канторовскаятеормножеств.иМ.Изд:й

-воМоск.ун

-та, 1988,

112с

4.

АляевЮ..Тюр, С.Ф.дискретнматемиматематическаяатикалогика.

- М.:

Финансыстатистика, 2006.

- 368с.

5.

АсановМ.О.Баранский, В.А.Расин, В.

. Дискрмате:графытн,матроиды,яика

алгоритмы.

- Ижевск:НИЦРегулярная« ихаотди»,намикаческая2001.

6.

Ахо.Ульман, Дж.Теориясинтаксическогоанал,переводакомпиляцииза.М.:

Мир, 1978 -

с.

7.

Ахо.Хопкрофт, Дж.Ульман, Дж.Построениеанализвычислительных

алгор.М.м:,и1979ртмов.

-

с.

8.

БасакерР.Саати, Т.Конечнграфисети. ые

– М.Наука: , 1974.

11.

БеловВ..Воробьев, Е.М.Шаталов, .Е.Теорияграфов.

– М.Высш: .Школа, 1976

12.

БелоусовА.И.Ткачев, С..Дискрматематика. тная

– М.Изд:

-воМГТУим.Н.Э.

Баумана, 2006.

– 744с.

13.

БержК.Теорияграфовееприме.Изд. н.Литос.ение, 1962р

14.

БочаровВ.А.О

сновылогики.М.Логос: , 1994.

-296с.

15.

ВладимировД.А.Булевыалгебры.М.Наука: , 1989.

- 318с.

16.

ГаврилС.П.СапоженкоА..Сборникв задачисматематикеретной.

– М.:

Наука, 1978.

17.

ГаврилС.П.СапоженкоА..Задачив упражнениядискретнойматемат

ике. –

М.Физматлит:

, 2006. – 416с.

18.

ГалушкинаЮ.И.МарьямовА.Н.Конспектлекцийподискретнойматематике

упражиконтрольнымиработамиений.М.Айрис: ПРЕСС, 2007

– 175с.

19.

ГанчевИ.Чимев, К.Стоянов, Й.Математическийфольклор..Знание: , 1987.

20.

ГиндикинС.Г.

Алгебралогикивзадачах.М.Наука: ; 1972.

21.

ГорбатовВ.А.

Фундаментальосновыдискретматем.М.Наука:н;ойыетики

Физматлит, 2000.

22.

ГорбатовВ.А.Основыдискретнойматематики.М.Высшая: школа, 1986.

- 311с.

23.

ГэриМ.Джонсон, .Вычислительны

емашинытруднорешаемыезадачи.М.:

Мир, 1982

Diskretka.doc20.02.2014

149

29.

ЕршовА. П.Введениетеоретическоепрограммирование.М.Наука: , 1977

30.

ЕршовД.Л.Палютин, .А.Математическая" логика".

-

Спб.Лань: , 2004.

31.

А..ЗыковОсн" теграфоввырии",МНаука, 1987.

32.

ИвановБ.Н.

Дискрматематика.Алготнаяпрограммы.итмыПолный

курс. - М.:

ФИЗМАТЛИТ, 2007.

– 408с.

33.

ИвинА..Строгиймирлогики.

– М.Педагогика: , 1988.

– 154с.

34.

КапитоноваЮ.В.Кривой, С.Л. др.

Лекцииподискретнойматематике.

- СПб.:

БХВ-Петербург, 2004.

– 624с.

35.

КанцедалС.А.Д

искретнаяматематика.

- М.ИД: ФО«

РУМ»

- ИФРА-М. 2007.

36.

КаргаполовМ.И.Мерзляк, Ю.И.Оснтегрупповы.рииМ.Наука: , 1977.

- 239

с.

комбинат:Учебноепос рикае

– М.Из: д-воМГСУ, 2010.

1977

42.

КозловаЕ.Г.Сказкиподсказки.

– М.Мирос: , 1994.

43.

КорменТ.Лейзерсон, Ч.Ривест, .

Алгор:построениеанализтмы

. — М.:

МЦНМО, 2001.

44.

КристофН.Теорграфов.Алгоритмическийдесяпод

ход.М.Мир: , 1978.

– 432с.

45.

КонП.Универсальнаяалгеб,Ми, 1968

46.

КорменТ.Лейзерсон, Ч.Ривест, .

Алгор:построениеанализтмы

. — М.:

МЦНМО, 2001.