Всё сдал! - помощь студентам онлайн Всё сдал! - помощь студентам онлайн

Реальная база готовых
студенческих работ

Узнайте стоимость индивидуальной работы!

Вы нашли то, что искали?

Вы нашли то, что искали?

Да, спасибо!

0%

Нет, пока не нашел

0%

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

это быстро и бесплатно

Получите скидку

Оформите заказ сейчас и получите скидку 100 руб.!


Доведення теоретико-математичних тотожностей і тверджень

Тип Реферат
Предмет Информатика и программирование
Просмотров
1065
Размер файла
163 б
Поделиться

Ознакомительный фрагмент работы:

Доведення теоретико-математичних тотожностей і тверджень

Курсова робота

з дисципліни дискретний аналіз

Доведення теоретико-математичних тотожностей і тверджень


Зміст

алгоритм програма множина графи

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існує, то ми повинні відповісти на наступне питання: YY ? Хай YY, тоді YY. Хай YY, тоді YY. Виходить неусувна логічна суперечність, яка відома як парадокс Рассела. Ось три способи уникнути цього конкретного парадоксу.

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-й елемент з поточної невідсортованої послідовності А вставляється в відповідне йому місце відсортованої послідовності В; потім він удаляєть з послідовності А. Покажемо роботу методу простого виключення на прикладі:

А=.

і

Невідсортований список,

(А)

Відсортований список,

(В)

07, 2, 21, 17, 6, 1, 13, 5, 8.
12, 21, 17, 6, 1, 13, 5, 8.7
221, 17, 6, 1, 13, 5, 8.2, 7
317, 6, 1, 13, 5, 8.2, 7, 21
46, 1, 13, 5, 8.2, 7, 17, 21
51, 13, 5, 8.2, 6, 7, 17, 21
613, 5, 8.1, 2, 6, 7, 17, 21
75, 8.1, 2, 6, 7,13, 17, 21
88.1, 2, 5, 6, 7,13, 17, 21
91, 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:використовуємо ProcedureSYS ,яка описана в лабораторній 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, то записати в кінці масиву С елементи В, які не були розглянені; кінець.якщо і <nij >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 = AB


4

5

SYS – procedure для відсортування масиву

RIZNICA- procedure для обчислення С = А В

2.5.4.5. Блок-схема


Мал.3. Блок-схема процедури RIZ

2.6. Результат

Текст програми:

Programproga;

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;Var pn1, pn2,pk:integer);{вхід:A,B; вихід C}{програма для об’єднання множин}

var

i,j,k,l:integer;

begin

i:=1;j:=1;k:=0;

repeat

if pA[i]<pB[j] then

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<pn2) then

for l:=j to pn2 do

begin k:=k+1; pC[k]:=pB[l];end;

if (i<pn1) and (j>pn2)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]<pb[j] then begin k:=k+1; pC[K]:=pa[i]; i:=i+1; end

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 (i<pn1)and(j>pn2) 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;Var pc: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]<pB[j] then i:=i+1;

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.

Задається дія заперечення за допомогою таблиці істинності:

01
10

Кон’юнкція задається за допомогою таблиці істинності:

000
010
100
111

Диз'юнкція задається за допомогою таблиці істинності:

000
011
101
111

Еквівалентність задається таблицею істинності:

001
010
100
111

Задається імплікація таблицею істинності:

001
011
100
111

4.2.Побудовання таблиці істинності висловлень

Завдання:Побудуйте таблиці істинності для висловлювання ;

Відзначимо, відповідно до пріоритетів виконання операцій , кроки, за якими буде побудована таблиця істинності висловлень:

BDEf1f2f3f4f5f6f7f8f9f10f11f12F
0001000010010011
0010000010010011
0101000110010011
0110000010100111
1001001001010000
1010000010010011
1101111110010001
1110110001101111

Розв‘язок:


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.Завдання:

Звести до ДНФ таке висловлювання. ;

Розв‘язок:

XYZW
000011100111
000111111000
001100011010
011100011010
111001111000
110001111000
100011101001
111101111000
XYZW
00001011
00011000
00110111
01110011
11101111
11001101
10001011
11111111


7. Графи

7.1. Теоретичні відомості

Матриця інциденцій для орієнтованого графа:

1, якщо вершина vi інцидентна ребру ej і є його кінцем

H[i,j]= 2, якщо вершина vi і ребро не інцидентні ej

-1, якщо вершина vi інцидентна ребруej і є йогопочатком

Задан ориентированний граф у графиічноїеской формі.Побудовати

Нехай, v1 iv2 – вершини, e = (v1,v2) – ребро, що їх з’єднує. Тоді вершина v1 iребро е – інцидентні, ребро eiвершина v2 також інцидентні.

Завдання:Побудовати таблицу иіцидентности данного графа

Розв‘язок: таблицу иіцидентности данного графа.

V1V2V3V4V5V6V7V8
e10-1001000
e21000-1000
e30010-1000
e400-100001
e5000-10001
e6000-10010
e700010-100
e7
e6
e5
e4
e3
e1
e2

Список використаної літератури

1. С.Гудман, С.Хидемниеми «Введение в разработку и анализ алгоритмов». Изд. «Мир», М.1984.

2. Г. Кортман и др. «Алгоритм. Построение и анализ», М., С.-П, К., 2005.

3. Н. Культин, «TurboPascal в задачах и примерах», Москва, 2004.

4. Г. Майерс «Надежность програмного обеспечения», Изд. «Мир», М.1980.

5. А.И. Марченко «Программирование на языке TurboPascal 7.0. Базовый курс», М., 2004.

6. Ю.В. Нікольський, В.В. Пасічник, Ю.М. Щербина “Дискретна математика”, Київ, 2007.

7. В.С. Новиков, Н.И. Парфилова, А.Н. Пылькин «Алгоритмизация и программирование на Турбо Паскале. Учебное пособие для вузов», М., 2005.

8. Г. Рапаков «Программирование на языке Pascal», М., 2004.

9. Р.Г. Тадевосян, С.М. Арапов «Інформатика та комп’ютерна техніка», 21, 23, Вінниця, ВДАУ, 2004.

10. Р.Г. Тадевосян, В.А. Лужецький «Комп’ютер», Вінниця, 2003.

11. Р.Г. Тадевосян, В.А. Лужецький «Windows», Вінниця, 2003.


Нет нужной работы в каталоге?

Сделайте индивидуальный заказ на нашем сервисе. Там эксперты помогают с учебой без посредников Разместите задание – сайт бесплатно отправит его исполнителя, и они предложат цены.

Цены ниже, чем в агентствах и у конкурентов

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

Бесплатные доработки и консультации

Исполнитель внесет нужные правки в работу по вашему требованию без доплат. Корректировки в максимально короткие сроки

Гарантируем возврат

Если работа вас не устроит – мы вернем 100% суммы заказа

Техподдержка 7 дней в неделю

Наши менеджеры всегда на связи и оперативно решат любую проблему

Строгий отбор экспертов

К работе допускаются только проверенные специалисты с высшим образованием. Проверяем диплом на оценки «хорошо» и «отлично»

1 000 +
Новых работ ежедневно
computer

Требуются доработки?
Они включены в стоимость работы

Работы выполняют эксперты в своём деле. Они ценят свою репутацию, поэтому результат выполненной работы гарантирован

avatar
Математика
История
Экономика
icon
159599
рейтинг
icon
3275
работ сдано
icon
1404
отзывов
avatar
Математика
Физика
История
icon
156450
рейтинг
icon
6068
работ сдано
icon
2737
отзывов
avatar
Химия
Экономика
Биология
icon
105734
рейтинг
icon
2110
работ сдано
icon
1318
отзывов
avatar
Высшая математика
Информатика
Геодезия
icon
62710
рейтинг
icon
1046
работ сдано
icon
598
отзывов
Отзывы студентов о нашей работе
63 457 оценок star star star star star
среднее 4.9 из 5
Филиал государственного бюджетного образовательного учреждения высшего образования Московской област
Спасибо Елизавете за оперативность. Так как это было важно для нас! Замечаний особых не бы...
star star star star star
РУТ
Огромное спасибо за уважительное отношение к заказчикам, быстроту и качество работы
star star star star star
ТГПУ
спасибо за помощь, работа сделана в срок и без замечаний, в полном объеме!
star star star star star

Последние размещённые задания

Ежедневно эксперты готовы работать над 1000 заданиями. Контролируйте процесс написания работы в режиме онлайн

решить 6 практических

Решение задач, Спортивные сооружения

Срок сдачи к 17 дек.

только что

Задание в microsoft project

Лабораторная, Программирование

Срок сдачи к 14 дек.

только что

Решить две задачи №13 и №23

Решение задач, Теоретические основы электротехники

Срок сдачи к 15 дек.

только что

Решить 4задачи

Решение задач, Прикладная механика

Срок сдачи к 31 дек.

только что

Выполнить 2 задачи

Контрольная, Конституционное право

Срок сдачи к 12 дек.

2 минуты назад

6 заданий

Контрольная, Ветеринарная вирусология и иммунология

Срок сдачи к 6 дек.

4 минуты назад

Требуется разобрать ст. 135 Налогового кодекса по составу напогового...

Решение задач, Налоговое право

Срок сдачи к 5 дек.

4 минуты назад

ТЭД, теории кислот и оснований

Решение задач, Химия

Срок сдачи к 5 дек.

5 минут назад

Решить задание в эксель

Решение задач, Эконометрика

Срок сдачи к 6 дек.

5 минут назад

Нужно проходить тесты на сайте

Тест дистанционно, Детская психология

Срок сдачи к 31 янв.

6 минут назад

Решить 7 лабораторных

Решение задач, визуализация данных в экономике

Срок сдачи к 6 дек.

7 минут назад

Вариационные ряды

Другое, Статистика

Срок сдачи к 9 дек.

8 минут назад

Школьный кабинет химии и его роль в химико-образовательном процессе

Курсовая, Методика преподавания химии

Срок сдачи к 26 дек.

8 минут назад

Вариант 9

Решение задач, Теоретическая механика

Срок сдачи к 7 дек.

8 минут назад

9 задач по тех меху ,к 16:20

Решение задач, Техническая механика

Срок сдачи к 5 дек.

9 минут назад
9 минут назад
10 минут назад
planes planes
Закажи индивидуальную работу за 1 минуту!

Размещенные на сайт контрольные, курсовые и иные категории работ (далее — Работы) и их содержимое предназначены исключительно для ознакомления, без целей коммерческого использования. Все права в отношении Работ и их содержимого принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие в связи с использованием Работ и их содержимого.

«Всё сдал!» — безопасный онлайн-сервис с проверенными экспертами

Используя «Свежую базу РГСР», вы принимаете пользовательское соглашение
и политику обработки персональных данных
Сайт работает по московскому времени:

Вход
Регистрация или
Не нашли, что искали?

Заполните форму и узнайте цену на индивидуальную работу!

Файлы (при наличии)

    это быстро и бесплатно