Курсова роботаз дисципліни дискретнийаналіз
Доведення теоретико-математичних тотожностей і тверджень
/>Зміст
алгоритмпрограма множина графи
1. Доведення рівностей методомматематичної індукції
2. Розробка алгоритму та написанняпрограми обчислення множин
2.1. Теоретичні відомості
2.2. Проект обчислення
2.3. Організація структури програми
2.4. Вихідний текст програми
2.5.Опис процедур
2.5.1. Опис процедури SYS
2.5.1.1. Постановка задачі
2.5.1.2. Математична модель
2.5.1.3. Алгоритм рішення задачі
2.5.1.4. Блок-схема
2.5.2 Опис процедури OBED
2.5.3 Опис процедури PERET
2.5.4 Опис процедури RIZ
2.6. Результат
3. Доведення теоретико-математичнихтотожностей і тверджень
4. Побудува таблиці істинностівисловлень
4.1. Теоретичні відомості
4.2. Рішення
5. Побудова диз’юнктивної нормальноїформи (ДНФ)
5.1. Теоретичні відомості
5.2. Рішення
6. Побудова досконалої диз’юнктивноїнормальної форми (ДДНФ)
6.1. Теоретичні відомості
6.2.Рішення
7. Розробка алгоритму та написанняпрограми знаходження множини елементарних циклів у графі
7.1. Теоретичні відомості
/>7.2. Алгоритм рішення задачі
7.3. Блок-схема програми
7.4. Вихідний текст програми
7.5. Результат роботи програми
Список літератури
1.Доведеннярівностей методом математичної індукції
Теоретичнівідомості
ТЕОРЕМА. Нехайвластивість Р вірна для п =1 і нехай з істинності Р для п= к випливає його істинність для п = к+1. Тоді властивість Рвірна для кожного />. ТЕОРЕМА. Нехай множина /> має такі властивості.
1. /> .
2. Для кожного/>, якщо />, то />.
Тоді />.ТЕОРЕМА (Зворотний метод математичноїіндукції). Нехай властивість р(n)виконується для n=1. з того,що вона вірна для кожного /> випливає, що р(n)вірна для n. Значить р(n) вірна длябудь-якого натурального n.
Зауваження. У загальному випадкуіндуктивний процес не зобов'язаний починатися з 1. Базисом індукції може бутибудь-як ціле число a.ТЕОРЕМА. Нехай властивість р(n) виконується для n= a. З цього для кожного /> випливає істинність для k+1. Значить р(n)істинно для будь-якого цілого />.
Завдання1: Довести, що для будь-якого/>
/> (1)
Розв‘язок:
1. Базиси індукції. Перевіримо рівність для п =1. Лівачастина =/>, права частина = />. Тобто базис індукціївиконується.
2. Індуктивне припущення. Вважаємо рівність (1)вірною для п = к, тобто припустимо, що:
/> (2)
3. Індуктивний перехід. Доведемо рівність (1) для п=к+1,тобто доведемо, що: />, звідси /> =/>
Такимчином на підставі методу математичної індукції рівність (1) вірна для кожного п.
2. Розробка алгоритму та написанняпрограми обчислення множин
2.1. Теоретичнівідомості
Множина – це будь-якапевна сукупність об'єктів. Об‘єкти з яких складається множина, називаються йогоелементами.
Множина, що не міститьелементів, називається порожньою.
Множини,як об’єкти, можуть бути елементами інших множин. Множини, елементи яких ємножини, іноді називають сімейством.
Сукупністьоб'єктів, які не є множиною, називають класом.
Звичайнов конкретних міркуваннях елементи всіх множин беруться з деякого одного,достатньо широкої множини U яке називається універсальною множиною.
Щобзадати множину, потрібно вказати, які елементи йому належать. Це можна зробитирізними способами:
— перерахункомелементів: М={a1,a2,…,ak};
— характеристичнимпредикатом: М={x| P(x)};
— породжуючоюпроцедурою: M={x | x= f}.
Розглянемомножини Y всіх множин, що не містять себе як елементу: />
Якщо множина Y існує, то ми повинні відповісти на наступнепитання: Y/> Y? Хай Y/> Y, тоді Y/>Y. Хай Y/> Y, тоді Y/> Y. Виходитьнеусувна логічна суперечність, яка відома як парадокс Рассела. Ось три способиуникнути цього конкретного парадоксу.
1. Обмежити використання характеристичні предикати вигляду: />, де А – відома, явноіснуюча множина (універсум). Звичайно при цьому використовується позначення />. Для Y універсум невказаний, а тому Y множиною не може бути.
2. Територія типів. Об‘єкти мають типи 0, множина елементів типу 0мають тип 1, множина елементів типу 0 та 1 – типу 2 і т. д. Y не має типу ітому не може юути множиною.
3. Явназаборона приналежності множини самої собі: /> - неприпустимий предикат.Відповідна аксіома називається аксіомою регулярності.
Множина Аміститься у множині В якщо кожний елемент А є елементом В:
/>
Вцьому видатку А називається підмножиною В, В – над множиною А. З означенням />
Двімножини рівні, якщо вони є підмножинами один одного:
/>
Кажуть,що кінцева множина А має потужність к, якщо вона рівнопотужна відрізку 1… к
Операціїнад множинамиНазва операції Математичне представлення операції Об‘єднання
/> Перетин
/>/>/> Різність
/> Симетрична різність
/>
/> Заперечення
/>
Властивостіоперації над множинами
Назва властивості
Варіант №1
Варіант №2
Іденпотентність
/>
/>
Комутативність
/>
/>
Асоціативність
/>
/>
Дистрибутивність
/>
/>
Поглинання
/>
/>
Властивість нуля
/>
/>
Властивість одиниці
/>/>
/>
Інволюнтивність
/> Закон де Моргана
/>
/> Властивість доповнення
/>
/> Властивість для різності
/>
Завдання2.1
Розробитиалгоритм та написати програму обчислення множини: />
Проектування рішення задачі
Проект рішення задачіпредставляється в формі принципової блок-схеми.
/> /> /> /> />
Обчислення: />
Вхід: А
Вихід: М1 /> /> /> /> /> /> /> /> /> /> />
Обчислення:/>= M4
Вхід: M1, M3
Вихід: M4
Мал.1.Принциповаблок-схема обчислення множин
Примітка:При розробці алгоритму даної задачі ми вводимомножини А, В, Dвже в упорядкованому вигляді, але ми нижче приводимо опис методу впорядкуваннямножин методом простого включення.2.3. Організація структури прграми
Дляобчислення операцій /> використовуютьметод, який базується на методі злиття. Він пропонує, що вихідні множиниповинні бути відсортованими. Тому в програмі для сортування вихідних масивівбудемо користуватись процедурою SYS (сортування методом простого виключення).
Представимоструктуру програми у вигляді наступної блок-схеми (для програми обраномодульний принцип організації програми):
/> /> /> /> /> />
Процедура RIZ
Мал.2.Принципова блок-схемапрограми
У програмі вирішення даної задачі мивикористовуємо наступні процедури:
1. SYS- призначена для сортування цілих додаткових чисел;
2. ОBED- призначена для організації виконання операційоб’єднання двох відсортуваних множин;
3. PERET- призначена для організації виконання операційперетину двох відсортуваних множин;
4. RIZ- призначена для організації виконання операційрізниці двох відсортуваних множин.
2.5.Описпроцедур
2.5.1. Описпроцедури SYS.
2.5.1.1.Постановка задачі.
Заданапослідовність чисел A = {aі, а2, а3, …, аn}.
Необхідноупорядкувати її елементи по зростанню, тобто створити послідовність чисел В={/>}, такий, щоб />, />.
Задачу вирішимометодом простого виключення.
2.5.1.2.Математична модель
Як математичнумодель представимо логічну схему роботи методом простого включення. Описуємосуть методу.
Побудуємо таблицюз 3 стовбців:
1-й стовбецьпредначений для вказування ітерацій методу.
2-й —длянесортованої послідовності (А).
3-й —длявідсортованої послідовності (В).
На першому кроці ітерацій 1-йелемент з А вставляється в В, потім цей елемент видаляється з А. Далі накожному кроці ітерацій 1-й елемент з поточної невідсортованої послідовності Авставляється в відповідне йому місце відсортованої послідовності В; потім вінудаляєть з послідовності А. Покажемо роботу методу простого виключення наприкладі:
А=/>.
і
Невідсортований список,
(А)
Відсортований список,
(В) 7, 2, 21, 17, 6, 1, 13, 5, 8. 1 2, 21, 17, 6, 1, 13, 5, 8. 7 2 21, 17, 6, 1, 13, 5, 8. 2, 7 3 17, 6, 1, 13, 5, 8. 2, 7, 21 4 6, 1, 13, 5, 8. 2, 7, 17, 21 5 1, 13, 5, 8. 2, 6, 7, 17, 21 6 13, 5, 8. 1, 2, 6, 7, 17, 21 7 5, 8. 1, 2, 6, 7,13, 17, 21 8 8. 1, 2, 5, 6, 7,13, 17, 21 9 1, 2, 5, 6, 7, 8, 13, 17, 21
2.5.1.3. Алгоритм рішення задачі.
Алгоритмпроцедури SYS.
Алгоритм призначений для впорядкування чисел методом простоговиключення.
Вхід: А- масив невідсортуваних даних;
n- кількість елементів масиву.
Вихід: В- масив відсортуваних даних.
Трудоємністьалгоритма />.
Крок 1: Визначити перші два елемента масиваВ.
Крок 2: Організувати цикл по />, />.
Крок 3: Провірити умови /> Якщо умова виконується, то/>.
Перехід на крок6.
Крок 4: Організувати цикл по />, де /> (для індексації рештиелементів масива В).
Крок 5: Провірити умови />. Якщо вона виконується, тоелементи масива В зміщуються на один розряд вправо з /> до />. Присвоїти />.
Крок 6: Завершення циклу по />.
Крок 7:Кінець.
2.5.1.4. Блок-схема.
/>
так
ні
так
Мал.3.Блок-схема процедури SYS.
2.5.2. Опис процедури OBED.
2.5.2.1. Постановказадачі.
Задані дві множини A={а/>, а/>,.., а/>}, В={b/>,b/>,..,b/>}.
Потрібно отримати множину С=А />В.
2.5.2.2. Математична модель
Об’єднання визначаєтьсянаступним чином />.
2.5.2.3. Алгоритм рішення задачі.
Алгоритм вирішення задачібазується на методі злиття двох множин. Приведемо загальний опис вирішенняалгоритму задачі.
/>
1
2
3
4
Блок 1: використовуємо Procedure SYS, яка описана в лабораторній pоботі №1.
Блок 2,3: не відсортовані масиви; відсортовані масиви.
Блок 4: алгоритм OBED
Алгоритм OBED:
Призначений для об’єднаннядвох відсортованих множин А і В з використанням методу злиття.
Крок1. Присвоїти />, j=1,/>;
Крок2. Перевірити умову />: якщо так, то: к=к+1, с/>=/> ,і=і+1;
Крок3. Перевірити умову />; якщо так, то перехід на крок2;
інакше: записати в кінці масиву Селементи масиву В,
які залишились нерозглянуті; кінець.
Якщо/> , то перехід на крок 4;
Крок4. Перевірити />; якщо так, то: к=к+1, с/>=b/>,j=j+1
Крок5. Перевірити умову j/>; якщотак, то перехід на крок 2;
інакше: записати в кінці масива С елементи А, які залишились нерозглянуті;кінець.
Крок 6. />, к=к+1; с/>=/>,і=і+1, J=j+1 ;
Крок 7. Провірити умову: />оr/> (Чи існують іще нерозглянуті елементи множини А чиВ); якщо так, то перехід на крок 2. Інакше: якщо і>n і jкінець.якщоі m, тозаписати в кінці масиву С елементи А, які залишились ерозглянуті.Kiнець
2.5.2.4. Блок-схема.
/>
Мал.3. Блок-схемапроцедури OBED
2.5.3. Опис процедури PERET
2.5.3.1. Постановка задачі.
Задані дві множини: A={а/>, а/>,.., а/>}
В={b/>,b/>,..,b/>}, якіупорядковані.
Потрібно отримати множину С=А ÇB
2.5.3.2. Математична модель
Перетин визначається наступнимчином С=А ÇВ={С, С/>А і С/>В}
2.5.3.4. Алгоритмвирішеннязадачі
Алгоритм вирішення задачібазується на методі злиття двох множин, тому ми можемо допустити, не порушуючизагальності, що множини А і В вже відсортували. Задається у відсортованомувигляді. Приведемо загальний опис вирішення алгоритму задачі.
На кожному кроці основного циклуможлива одна з трьох ситуацій: поточний елемент множини А менше, чи більше, чидорівнює поточному елементу множини В.
· у першому випадку поточнийелемент множини А не належить перетинанню, він пропускається і відбуваєтьсяпросування в цій множині;
· у другому випадку теж самевиконується з множиною ;
· у третьому випадкузнайдені співпадаючі елементи, один екземпляр елементу додається в результат івідбувається просування відразу в обох множинах.
Алгоритм перетину:
Призначений для перетину двохвідсортованих множин А і В з використанням методу злиття.
Крок 0. Ініціалізація: задання множин А і В:
А={а/>},/>/>/>;
В={b/>},/>;
Присвоїти />, j=1/>
Крок 1. Перевірити />.Якщо так, то: і=і+1. Перехід на Крок4.
Крок 3. Перевірити />, якщотак, то: j=j+1. Перехід на Крок 4.
Крок 4. Виконати Крок2 і Крок3 при ( /> )оr (/> ) .
Крок 5. Кінець.
Блок-схема.
/>
Мал.3. Блок-схемапроцедури PERET
2.5.4. Опис процедури RIZ.
2.5.4.1. Постановка задачі
Задані дві множини A={а/>, а/>,.., а/>} і В={b/>,b/>,..,b/>}, якіупорядковані.
Потрібно отримати множину С=А \B.
2.5.4.2. Математична модель
Різниця визначається наступнимчином С=А \В={с, сÎА і сÏВ}
2.5.4.3. Алгоритмвирішення задачі
Алгоритм вирішення задачібазується на методі злиття двох множин, тому ми можемо допустити не порушуючизагальності, що множини А і В вже відсортували. Приведемо загальний описвирішення алгоритму задачі.
На кожному кроці основного циклуможлива одна з трьох ситуацій: поточний елемент множини А менше, чи більше, чидорівнює поточному елементу множини В.
· у першому випадку поточнийелемент множини А записується в результат С і розглядається наступний елементмножини А;
· у другому випадку поточнийелемент множини А не належить різниці і розглядається наступний елемент множиниВ;
· у третьому випадкупоточний елемент А не належить результату і розглядаються наступні елементимножин А і В.
Після закінчення основного циклуті елементи множини А, які не були розглянуті, записуються в кінець списку Сбез перевірки.
АЛГОРИТМ RIZ. Призначений для знаходження різниці двохвідсортованих множин А і В з використанням методу злиття.
Крок 0. Задання множин А і В: А={а/>},/>/>/>; В={b/>},/>;
Присвоїти />, />,/>.
Крок 1. Перевірити />.Якщо так, то: />, />, />. Перехід на Крок3.
Крок 2. Перевірити />.Якщо так, то: />, />, перехід на Крок 3. Інакше: />.
Крок3. Виконати Крок1 іКрок2 поки ( /> )оr (/> ) .
Крок 4. Визначити: якщо залишились нерозглянуті елементимножини А, то записати їх без перевірки в кінець списку С.
Крок5.Кінець.
Приведемо загальний опис вирішеннязадачі./>
Ввід А =/>, B = />
А, В – невідсортовані множини
1
/>
Виклик SYS (а, А,n)
Вихід А- відсортовані 2
/>
3/> /> /> /> /> /> /> />
Виклик RIZNICA(A,B,m,n,D)
SYS (B).
Вихід D = A\B
4
/> /> /> /> /> /> /> />
5 />
SYS – procedure для відсортування масиву
RIZNICA-procedure для обчислення С = А \ В
2.5.4.5. Блок-схема
/>
Мал.3. Блок-схемапроцедури RIZ
2.6.Результат
Текстпрограми:
Program proga;
type ar=array [1..50] of integer;
Var A,B,C,D,BK1,BK2,Bk3,Bk4,Bk5,Bk6,M,U:ar;
i,j,k,nk1,nk2,nk3,nk4,nk5,nk6,nm,na,nb,nc,nd:integer;
Procedure OBED(Var pa:ar;Var pb:ar;Var pc:ar;Varpn1, pn2,pk:integer);{вхід:A,B;вихідC}{програма для об’єднаннямножин}
var
i,j,k,l:integer;
begin
i:=1;j:=1;k:=0;
repeat
if pA[i]
begin k:=k+1;pC[k]:=pA[i];i:=i+1; end;
if pA[i]>pB[j] then
begin k:=k+1;pC[k]:=pb[j];j:=j+1; end;
if pA[i]=pB[j] then
begin k:=k+1;pC[k]:=pA[i];i:=i+1;j:=j+1; end;
until (i>pn1) or (j>pn2);
if (i>pn1)and(j
for l:=j to pn2 do
begin k:=k+1; pC[k]:=pB[l];end;
if (ipn2)then
for L:=i to pn1 do
begin k:=k+1;pC[k]:=pA[l];end;
write(' A={'); for i:=1 to pn1 do write(pa[i]:3);writeln('}');
write(' B={'); for i:=1 to pn2 do write(pB[i]:3);writeln('}');
write(' C={'); for i:=1 to k do write(pC[i]:3);write('}');
pk:=k;
readln;
end;
Procedure RIZ(Var pa:ar;Var pb:ar;Var pc:ar;Var pn1,pn2,pk:integer); {вхід:A,B;вихідC}{програма для обчисленнярізниці множин}
{const n=5;m=6;}
var
i,j,k,l:integer;
begin
i:=1;j:=1; k:=0;
repeat
if pa[i]
else begin if pa[i]=pb[j] then
begin i:=i+1; j:=j+1; end
else j:=j+1; end;
until (i>pn1)or(j>pn2);
if (ipn2) then
begin for l:=i to pn1 do
begin k:=k+1; pc[k]:=pa[l]; end;
end;
if k=0 then
begin
write(' A={'); for i:=1 to pn1 do write(pa[i]:3);writeln('}');
write(' B={'); for i:=1 to pn2 do write(pb[i]:3);writeln('}');
write(' C={'); for i:=1 to k do write(pc[i]:3);writeln('}');
end
else
begin
write(' A={'); for i:=1 to pn1 do write(pa[i]:3);writeln('}');
write(' B={'); for i:=1 to pn2 do write(pb[i]:3);writeln('}');
write(' C={'); for i:=1 to k do write(pc[i]:3);writeln('}');
end;
pk:=k;
readln;
readln;
end; Procedure PERET(Var pa:ar;Var pb:ar;Varpc:ar;Var pn1, pn2,pk:integer); {вхід:A,B;вихідC}{програма для перетинумножин}
{const n=10; m=7;}
var
i,j,k,l:integer;
begin
i:=1;j:=1;k:=0;
repeat
if pA[i]
if pA[i]>pB[j] then j:=j+1;
if pA[i]=pB[j] then
begin k:=k+1; pC[k]:=pA[i]; i:=i+1;j:=j+1;end;
until (i>pn1) or (j>pn2);
if k = 0 then
begin
write(' A={'); for i:=1 to pn1 do write(pa[i]:3);writeln('}');
write(' B={'); for i:=1 to pn2 do write(pB[i]:3);writeln('}');
write(' C={'); for i:=1 to k do write(pC[i]:3);write('}');
end
else
begin
write(' A={'); for i:=1 to pn1 do write(pa[i]:3);writeln('}');
write(' B={'); for i:=1 to pn2 do write(pB[i]:3);writeln('}');
write(' C={'); for i:=1 to k do write(pC[i]:3);write('}');
end;
writeln;
pk:=k;
readln;
end;
Begin {тілопрограми}
k:=15;
For i:=1 to k do U[i]:=i;
Write('Задайте множину A таiiграницю');
write(' na=');REadln (na);
For i:=1 to na do begin write ('A[',i,']= '); Readln(a[i]); end;
Write('Задайте множину В таiiграницю');
write(' nb='); Readln (nb);
For i:=1 to nb do begin write ('B[',i,']= '); Readln(b[i]); end;
Write('Задайте множину С таiiграницю');
write(' nc='); Readln (nc);
For i:=1 to nc do begin write ('C[',i,']= '); Readln(C[i]); end;
Write('Задайте множинуD таiiграницю');
write(' nd='); Readln (nd);
For i:=1 to nd do begin write ('D[',i,']= '); Readln(D[i]); end;
peret(A,B,bk1,na,nb,nk1);
riz(U,bk1,bk2,k,nk1,nk2);
riz(U,C,bk3,k,nc,nk3);
riz(U,D,bk4,k,nD,nk4);
peret(bk3,bk4,bk5,nk3,nk4,nk5);
riz(U,bk5,bk6,k,nk5,nk6);
obed(bk2,bk6,M,nk2,nk6,nm);
end.
Результати:
Вхідні данні:
A={2,3,5,8}, na=4
B={1,2,5,11}, nb=4
C={12,14,15}, nc=3
D={3,9,10,11,12}, nd=5
Отриманіданні:
М1= {2,5}
М2= {1,3,4,6,7,8,9,10,11,12,13,14,15}
М3= {1,2,3,4,5,6,7,8,9,10,11,13}
М4={1,2,4,5,6,7,8,13,14,15}
М5= {1,2,4,5,6,7,8,13}
М6={3,9,10,11,12,14,15}
3 Доведеннятеоретико-математичних тотожностей і тверджень
Завдання:Довеститотожність: />;
Доведення:
1) />
2) />
3) />;
4.Побудова таблиці істинності висловлень
4.1. Теоретичні відомості
Під висловленнямрозуміють пропозицію людської мови, про яку можна сказати, істинна вона абохибна. Пізніше стане ясно, чому тут говориться не про визначення, а про поняттявисловлення. А надалі в нас з'явиться можливість дати точне визначеннявисловлення. Висловлення позначаються великими буквами латинського алфавіту,можливо з індексами: /> . Якщовисловлення А є істинним то пишуть А=1, інакше пишуть А=0.
Задається діязаперечення за допомогою таблиці істинності:
/>
/> 1 1
Кон’юнкція задається за допомогоютаблиці істинності:
/>
/>
/> 1 1 1 1 1
Диз'юнкціязадається за допомогоютаблиці істинності:
/>
/>
/> 1 1 1 1 1 1 1
Еквівалентністьзадається таблицеюістинності:
/>
/>
/> 1 1 1 1 1 1
Задається імплікаціятаблицею істинності:
/>
/>
/> 1 1 1 1 1 1 1
4.2.Побудовання таблиці істинності висловлень
Завдання: Побудуйте таблиці істинностідля висловлювання />;
Відзначимо, відповідно допріоритетів виконання операцій />,кроки, за якими буде побудована таблиця істинності висловлень:
/> />
/> B D E f1 f2 f3 f4 f5 f6 f7 f8 f9 f10 f11 f12 F 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
Розв‘язок:/>/>/>/>/>/>/>
5.Побудова диз'юнктивноїнормальної форми (ДНФ)
5.1. Теоретичні відомості
Визначення. Нехай F –висловлення і />.
/>
Визначення. /> утому і тільки в тому випадку, коли />.
Визначення. Кон’юнкція логічних зміннихабо їх заперечень називається елементарною кон’юнкцією. Загальний вигляделементарної кон’юнкції
/>.Визначення. Висловлення називається диз'юнктивноюнормальною формою, якщо воно є диз'юнкцією елементарних кон’юнкцій. загальний вигляд ДНФ/>,де кожна />, у свою чергу, єелементарною кон’юнкцією.
Теорема. Будь-яке висловленнярівносильне диз'юнктивній нормальній формі (говорять ще так: “Будь-яке висловлення зводиться доДНФ”).
Основнілогічні тотожності:
1) /> – ідемпотентністьдиз'юнкції;
2) /> – ідемпотентністькон’юнкції;
3) /> – комутативністьдиз'юнкції;
4) /> – комутативністькон’юнкції;
5) /> – асоціативністьдиз'юнкції;
6) /> – асоціативністькон’юнкції;
7) /> – дистрибутивністькон’юнкції щодо диз'юнкції;
8) /> – дистрибутивністьдиз'юнкції щодо кон’юнкції.
9) /> – перший законМоргана.
10) /> – другий законМоргана.
11) /> – закон подвійногозаперечення.
12) /> – закон протиріччя.
13) /> – закон виключеннятретіх.
14) />.
15) />.
16) />.
Тотожності,що містять константи:
17) />.
18) />.
19) />.
20) />.
21) />.
22) />.
23) />.
24) />.
25) />.
26) />.
5.2.Завдання:
Звести до ДНФтаке висловлювання. />
Розв‘язок:F=/>
/>
/>
6. Побудова досконалої диз'юнктивної нормальної форми (ДДНФ)
6.1. Теоретичнівідомості
Визначення. Нехай /> – деяка множиналогічних змінних. Елементарна кон’юнкція, в яку входять усі логічні змінні,називається повною елементарною кон’юнкцією щодо множини />.
Визначення. Нехай /> є повною елементарноюкон’юнкцією щодо множини />. Тоді /> містить у таблиціістинності лише одну одиницю, причому на наборі />.І навпаки, якщо в таблиці істинності висловлення /> єлише одна одиниця на наборі />, то /> є повною елементарноюкон’юнкцією, причому
Визначення. Нехай /> – висловлення.Позначимо через /> множину всіхнаборів />, на яких />. /> називається множиноюістинності висловлення />. Можназаписати, що />.
Теорема. Якщо />, то />.
Визначення. Диз'юнктивна нормальна форманазивається досконалою (ДДНФ), якщо всі складові її елементарноїкон’юнкції є повними.
Теорема. Нехай /> – висловлення, що неє тотожно хибним, тобто />, тоді
/>
6.2.Завдання:
Звести до ДНФ такевисловлювання. />;
Розв‘язок:
X
Y
Z
W
/>
/>
/>
/>
/>
/>
/>
/> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
X
Y
Z
W
/>
/>
/>
/> 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 /> />
7. Графи
7.1. Теоретичнівідомості
Матрицяінциденцій для орієнтованого графа:
/> 1, якщо вершина vi інцидентна ребру ej і є його кінцем
H[i,j]= 2, якщо вершина vi і ребро не інцидентні ej
-1,якщо вершина vi інцидентна ребру ej і є його початком
Задан ориентированний граф у графиічноїескойформі.Побудовати
Нехай, v1 i v2 – вершини, e = (v1,v2) – ребро, що їх з’єднує. Тоді вершина v1 i ребро е – інцидентні,ребро e i вершина v2 також інцидентні.
Завдання: Побудовати таблицу иіцидентности данного графа
Розв‘язок: таблицуиіцидентности данного графа.
V1
V2
V3
V4
V5
V6
V7
V8
e1 -1 1
e2 1 -1
e3 1 -1
e4 -1 1
e5 -1 1
e6 -1 1
e7 1 -1
e7
e6
e5
e4
e3
e1
e2 />/>/>/>/>/>/>/>/>/>/>/>/>/>/>
Списоквикористаної літератури
1. С.Гудман,С.Хидемниеми «Введение в разработку и анализ алгоритмов». Изд. «Мир», М.1984.
2. Г. Кортман и др.«Алгоритм. Построение и анализ», М., С.-П, К., 2005.
3. Н. Культин, «Turbo Pascal в задачах и примерах», Москва, 2004.
4. Г. Майерс«Надежность програмного обеспечения», Изд. «Мир», М.1980.
5. А.И.Марченко «Программированиена языке Turbo Pascal 7.0. Базовый курс», М., 2004.
6. Ю.В. Нікольський, В.В. Пасічник,Ю.М. Щербина “Дискретна математика”, Київ, 2007.
7. В.С.Новиков, Н.И. Парфилова, А.Н. Пылькин «Алгоритмизация и программирование наТурбо Паскале. Учебное пособие для вузов», М., 2005.
8. Г.Рапаков «Программирование на языке Pascal», М., 2004.
9. Р.Г.Тадевосян, С.М. Арапов «Інформатика та комп’ютерна техніка», 21, 23, Вінниця,ВДАУ, 2004.
10. Р.Г.Тадевосян, В.А. Лужецький «Комп’ютер», Вінниця, 2003.
11. Р.Г.Тадевосян, В.А. Лужецький «Windows», Вінниця, 2003.