Доведення теоретико-математичних тотожностей і тверджень
=b
,j=j+1
Крок 5.
Перевірити
умову j
;
якщо так, то
перехід на крок
2;
інакше: записати в кінці масива С елементи А, які залишились нерозглянуті; кінець.
Крок 6.
,к=к+1;
с=
,і=і+1,
J=j+1
;
Крок 7. Провірити
умову:
оr
(Чи існують
іще нерозглянуті
елементи множини
А чи В);якщо так,
то перехід на
крок 2. Інакше
: якщо і>n
і j<m,
то записати
в кінці масиву
С елементи В,
які не були
розглянені;
кінець.якщо
і <n i 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. Кінець.
Приведемо загальний опис вирішення задачі.
1
2
3
4
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;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 Доведення теоретико-математичних тотожностей і тверджень
Завдання:
Довести
тотожність:
;
Доведення:
;
4.Побудова таблиці істинності висловлень
4.1. Теоретичні відомості
Під висловленням
розуміють
пропозицію
людської мови,
про яку можна
сказати, істинна
вона або хибна.
Пізніше стане
ясно, чому тут
говориться
не про визначення,
а про поняття
висловлення.
А надалі в нас
з'явиться можливість
дати точне
визначення
висловлення.
Висловлення
позначаються
великими буквами
латинського
алфавіту, можливо
з індексами:
. Якщо висловлення
А є істинним
то пишуть А=1,
інакше пишуть
А=0.
Задається дія заперечення за допомогою таблиці істинності:
|
|
|
| 0 | 1 |
| 1 | 0 |
Кон’юнкція задається за допомогою таблиці істинності:
|
|
|
|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Диз'юнкція задається за допомогою таблиці істинності:
|
|
|
|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Еквівалентність задається таблицею істинності:
|
|
|
|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Задається імплікація таблицею істинності:
|
|
|
|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
4.2. Побудовання таблиці істинності висловлень
Завдання:
Побудуйте
таблиці істинності
для висловлювання
;
Відзначимо,
відповідно
до пріоритетів
виконання
операцій
,
кроки, за якими
буде побудована
таблиця істинності
висловлень:
| B | D | E | f1 | f2 | f3 | f4 | f5 | f6 | f7 | f8 | f9 | f10 | f11 | f12 | F |
| 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 |
Розв‘язок:
5. Побудова диз'юнктивної нормальної форми (ДНФ)
5.1. Теоретичні відомості
Визначення.
Нехай F –
висловлення
і
.
Визначення.
у тому і тільки
в тому випадку,
коли
.
Визначення. Кон’юнкція логічних змінних або їх заперечень називається елементарною кон’юнкцією. Загальний вигляд елементарної кон’юнкції
.
Визначення. Висловлення називається диз'юнктивною нормальною формою, якщо воно є диз'юнкцією елементарних кон’юнкцій. загальний вигляд ДНФ
,
де кожна
,
у свою чергу,
є елементарною
кон’юнкцією.
Теорема. Будь-яке висловлення рівносильне диз'юнктивній нормальній формі (говорять ще так: “Будь-яке висловлення зводиться до ДНФ”).
Основні логічні тотожності:
1)
–
ідемпотентність
диз'юнкції;
2)
–
ідемпотентність
кон’юнкції;
3)
–
комутативність
диз'юнкції;
4)
–
комутативність
кон’юнкції;
5)
–
асоціативність
диз'юнкції;
6)
–
асоціативність
кон’юнкції;
7)
–
дистрибутивність
кон’юнкції
щодо диз'юнкції;
8)
–
дистрибутивність
диз'юнкції щодо
кон’юнкції.
9)
–
перший закон
Моргана.
10)
