4053

Отношения и их свойства

Лабораторная работа

Информатика, кибернетика и программирование

Отношения и их свойства Бинарное отношение R на конечном множестве Требования на множество – те же, что и раньше (в нем не должно встречаться повторяющихся элементов, кроме того, оно должно быть упорядочено по возрастанию)....

Русский

2012-11-12

185 KB

129 чел.

Отношения и их свойства

Бинарное отношение R на конечном множестве A: RÍ A2 – задано списком упорядоченных пар вида (a,b), где a,bÎ A. Требования на множество – те же, что и раньше (в нем не должно встречаться повторяющихся элементов, кроме того, оно должно быть упорядочено по возрастанию). Программа должна определять свойства заданного отношения: рефлексивность, симметричность, антисимметричность, транзитивность (по материалам главы 1, п.1.3). Проверку свойств выполнять по матрице бинарного отношения, сопровождая необходимыми пояснениями.

Работа программы должна происходить следующим образом:

1. На вход подается множество A из n элементов и список упорядоченных пар, задающий отношение R (мощность множества, элементы и парывводятся с клавиатуры).

2. Результаты выводятся на экран (с необходимыми пояснениями) в следующем виде:

а) матрица бинарного отношения размера n´ n;
б) список свойств данного отношения.

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

3. После вывода результатов предусмотреть возможность изменения заданного бинарного отношения либо выхода из программы.

Это изменение может быть реализовано различными способами. Например, вывести на экран список пар (с номерами) и по команде пользователя изменить что-либо в этом списке (удалить какую-то пару, добавить новую, изменить имеющуюся), после чего повторить вычисления, выбрав соответствующий пункт меню. Другой способ – выполнять редактирование непосредственно самой матрицы отношения, после чего также повторить вычисления. Возможным вариантом является автоматический пересчет – проверка свойств отношения – после изменения любого элемента матрицы.

Дополнительно: предусмотреть не только изменение отношения, но и ввод нового множества (размер нового множества может тоже быть другим).


Решение.

Проверять свойства бинарного отношения будем оперируя с матрицей этого отношения. Матрицу будем хранить как двумерный массив.

Алгоритм проверки на рефлексивность.

Проверяем элементы главной диагонали. Если они все равны 1, то отношение рефлексивно, иначе – не рефлексивно.

Алгоритм проверки на симметричность.

Если элементы матрицы бинарного отношения симметричны относительно главной диагонали, то и само отношение является симметричным.

Алгоритм проверки на антисимметричность.

Находим матрицу пересечения данного бинарного отношения с обратным ему отношением (обратное задаётся путём транспонирования матрицы). Если в полученной матрице все элементы вне главной диагонали равны нулю, то исходное отношение обладает свойством антисимметричности.

Алгоритм проверки на транзитивность.

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

Для проверки на транзитивность:

  1.  находим матрицу , где – матрица нашего бинарного отношения;
  2.  если для каждой строки матрицы и соответствующей строки матрицы выполняется , то исходное отношение транзитивно.

Под записью в пункте b понимается, .


Исходный код на Borland Pascal 7.

program lab2;

uses

 Crt;

const

 Nmax = 15; { Макс. количество элементов множества A }

type

 T = Char; { Тип элементов множества A }

 TPair = Record

   a, b: T;

 end;

 TSet = Array[1..Nmax] of T;

 TMatrix = Array[1..Nmax, 1..Nmax] of Byte;

{ Сортировка выбором по неубыванию }

procedure Sort(var A: TSet; const N: Integer);

var

 i, j, k: Integer;

 tmp: T;

begin

 for i := 1 to N - 1 do begin

   k := i;

   for j := i + 1 to N do

     if A[j] < A[k] then k := j;

   tmp := A[i];

   A[i] := A[k];

   A[k] := tmp;

 end;

end;

{ Возвращает индекс элемента x в A. Если такого элемента нет, то возвращает -1 }

function Search(const x: T; const A: TSet; const N: Integer): Integer;

var

 i: Integer;

begin

 for i := 1 to N do

   if x = A[i] then begin

     Search := i;

     Exit;

   end;

 Search := -1;

end;

{ Проверка на рефлексивность }

function Reflex(const M: TMatrix; const N: Integer): Boolean;

var

 i: Integer;

begin

 Reflex := False;

 for i := 1 to N do

   if M[i, i] = 0 then Exit;

 Reflex := True;

end;

{ Проверка на симметричность }

function Symmetry(const M: TMatrix; const N: Integer): Boolean;

var

 i, j: Integer;

begin

 Symmetry := False;

 for i := 1 to N - 1 do

   for j := i + 1 to N do

     if M[i, j] <> M[j, i] then Exit;

 Symmetry := True;

end;

{ Проверка на антисимметричность }

function Antisymmetry(const M: TMatrix; const N: Integer): Boolean;

var

 i, j: Integer;

begin

 Antisymmetry := False;

 for i := 1 to N do

   for j := 1 to N do

     if (i <> j) and (M[i, j] * M[j, i] <> 0) then Exit;

 Antisymmetry := True;

end;

{ Проверка на транзитивность }

function Transit(const M: TMatrix; const N: Integer): Boolean;

var

 i, j, k: Integer;

 S: TMatrix;

begin

 Transit := False;

 for i := 1 to N do

   for j := 1 to N do begin

     S[i, j] := 0;

     for k := 1 to N do

       S[i, j] := S[i, j] or M[i, k] and M[k, j];

   end;

 for i := 1 to N do

   for j := 1 to N do

      if M[i, j] < S[i, j] then Exit;

 Transit := True;

end;

{ Вывод списка клавиш управления }

procedure Keys;

begin

 ClrScr;

 WriteLn('Выберите действие.');

 WriteLn;

 WriteLn('1 - показать список элементов множества A');

 WriteLn('2 - показать список пар бинарного отношения');

 WriteLn('3 - показать матрицу бинарного отношения');

 WriteLn('4 - показать свойства бинарного отношения');

 WriteLn('5 - измененть одну пару бинарного отношения');

 WriteLn('6 - удалить одну пару бинарного отношения');

 WriteLn('7 - добавить новую пару бинарного отношения');

 WriteLn('0 - очистить экран');

 WriteLn('Esc - завершить работу');

 WriteLn

end;

var

 i, j, N, k, z: Integer;

 x, y: T;  

 A: TSet;  

 M: TMatrix;

 P: Array[1..Nmax] of TPair;

 F: Boolean;

 v: Char;

begin

 ClrScr;

 WriteLn('Введите множество A (набор элементов через пробел)');

 N := 0;

 while not SeekEoLn do begin

   Inc(N);

   Read(A[N]);

 end;

 Sort(A, N);

 F := False;

 i := 1;

 while i < N do begin

   if A[i] = A[i + 1] then begin

     F := True;

     Dec(N);

     for j := i to N do

       A[j] := A[j + 1];

   end

   else

     Inc(i);

 end;

 if F then WriteLn('Повторяющиеся элементы были удалены.');

 for i := 1 to Nmax do

   for j := 1 to Nmax do

      M[i, j] := 0;

 WriteLn;

 WriteLn('Введите список пар. Каждую пару в новой строке, элементы пары - через пробел.');

 WriteLn('Для завершения ввода, вместо ввода пары нажмите Enter.');

 Reset(Input);

 k := 0;

 while not SeekEoLn do begin

   Read(x);

   if SeekEoLn then Reset(Input);

   ReadLn(y);

   if (Search(x, A, N) = -1) or (Search(y, A, N) = -1) then begin

      WriteLn('Элементы должны быть из множества A. Эта пара будет пропущена.');

      Continue;

   end;

   F := False;

   for i := 1 to k do

     if (P[i].a = x) and (P[i].b = y) then begin

        WriteLn('Эта пара уже была. Пропущено.');

        F := True;

        Break;

     end;

   if F then Continue;

   M[Search(x, A, N), Search(y, A, N)] := 1;

   Inc(k);

   P[k].a := x;

   P[k].b := y;

 end;

 Keys;

 repeat

   v := ReadKey;

   case v of

   '1':

     begin

       WriteLn('Элементы множества A:');

       for i := 1 to N do

         Write(A[i], ' ');

       WriteLn;

     end;

   '2':

     begin

       WriteLn('Список пар бинарного отношения:');

       for i := 1 to k do

         WriteLn(i, '. (', P[i].a, ', ', P[i].b, ')');

     end;

   '3':

     begin

       WriteLn('Матрица бинарного отношения:');

       Write('    ');

       for i := 1 to N do

         Write(A[i]:3, ' ');

       WriteLn;

       for i := 1 to N do

       begin

         Write(A[i]:3, ' ');

         for j := 1 to N do

           Write(M[i, j]:3, ' ');

         WriteLn;

       end;

     end;

   '4':

     begin

       WriteLn('Введённое отношение');

       if Symmetry(M, N)     then  WriteLn('- симметрично')     else WriteLn('- не симметрично ');

       if Antisymmetry(M, N) then  WriteLn('- антисимметрично') else WriteLn('- не антисимметрично');

       if Reflex(M, N)       then  WriteLn('- рефлексивно')     else WriteLn('- не рефлексивно');

       if Transit(M, N)      then  WriteLn('- транзитивно')     else WriteLn('- не транзитивно');

     end;

   '5':

     begin

       WriteLn('Введите номер пары, которую хотите изменить.');

       {$I-}

       ReadLn(z);

       {$I+}

       while IOResult <> 0 do begin

         WriteLn('Введено неверно. Введите заново.');

         {$I-}

         ReadLn(z);

         {$I+}

       end;

       if (z > k) or (z < 1) then

         WriteLn('Нет такой пары.')

       else begin

         WriteLn('Введите новое значение пары (два элемента через пробел).');

         Reset(Input);

         Read(x);

         if SeekEoLn then Reset(Input);

         ReadLn(y);

         if (Search(x, A, N) = -1) or (Search(y, A, N) = -1) then

           WriteLn('Значения должны быть из множества A. Изменение не произведено.')

         else begin

           F := False;

           for i := 1 to k do

             if (P[i].a = x) and (P[i].b = y) then begin

               WriteLn('Эта пара уже была. Пропущено.');

               F := True;

               Break;

             end;

           if not F then begin

             M[Search(P[z].a, A, N), Search(P[z].b, A, N)] := 0;

             P[z].a := x;

             P[z].b := y;

             M[Search(x, A, N), Search(y, A, N)] := 1;

             WriteLn('Изменено.');

           end;

         end;

       end;

     end;

   '6':

     begin

       WriteLn('Введите номер пары для удаления');

       {$I-}

       ReadLn(z);

       {$I+}

       while IOResult <> 0 do begin

         WriteLn('Введено неверно. Введите заново.');

         {$I-}

         ReadLn(z);

         {$I+}

       end;

       if (z > k) or (z < 1) then

         WriteLn('Нет такой пары')

       else begin

         M[Search(P[z].a, A, N), Search(P[z].b, A, N)] := 0; { Удаляем пару из матрицы }

         Dec(k);

         for i := z to k do  { Удаляем пару из списка P }

           P[i] := P[i + 1];

         WriteLn('Удалено.');

       end;

     end;

   '7':

     begin

       WriteLn('Введите пару (два элемента через пробел)');

       Reset(Input);

       Read(x);

       if SeekEoLn then Reset(Input);

       ReadLn(y);

       if (Search(x, A, N) = -1) or (Search(y, A, N) = -1) then

         WriteLn('Значения должны быть из множества A. Добавление не произведено.')

       else begin

         F := False;

         for i := 1 to k do

           if (P[i].a = x) and (P[i].b = y) then begin

             WriteLn('Эта пара уже есть. Пропущено.');

             F := True;

             Break;

           end;

         if not F then begin

           Inc(k);

           P[k].a := x;

           P[k].b := y;;

           M[Search(P[k].a, A, N), Search(P[k].b, A, N)] := 1;

         end;

       end;

       if not F then WriteLn('Добавлено.');

     end;

     '0': Keys;

   end;

 until v = #27;

end.


Результат работы программы.


 

А также другие работы, которые могут Вас заинтересовать

81346. Звернення стягнення на валюту та валютні цінності 24.23 KB
  У разі якщо кошти боржника в іноземній валюті розміщені на рахунках внесках або на зберіганні у банку чи іншій фінансовій установі що мають право на продаж іноземної валюти на внутрішньому валютному ринку державний виконавець зобовязує їх продати протягом семи днів іноземну валюту в сумі необхідній для погашення боргу. У разі якщо такі кошти розміщені у банку або іншій фінансовій установі які не мають права на продаж іноземної валюти на внутрішньому валютному ринку державний виконавець зобовязує їх перерахувати протягом семи днів ці...
81347. Звернення стягнення на цінні папери, ювелірні вироби та дорогоцінне каміння 30.05 KB
  Цінні папери ювелірні та інші побутові вироби із золота срібла платини і металів платинової групи дорогоцінних каменів і перлів а також лом і окремі частини таких виробів виявлені під час опису на які накладено арешт підлягають обов\'язковому вилученню і негайно передаються на зберігання установам Національного банку України. Порядок і умови зберігання та реалізації грошей у тому числі іноземної валюти цінних паперів ювелірних та інших побутових виробів із золота срібла платини і металів платинової групи дорогоцінного каміння і...
81348. Особливості звернення стягнення на будинок, квартиру, приміщення, земельну ділянку 28.33 KB
  Звернення стягнення на будинок квартиру інше приміщення земельну ділянку що є нерухомим майном провадиться у разі відсутності в боржника достатніх коштів чи рухомого майна. У разі звернення стягнення на будинок квартиру приміщення земельну ділянку державний виконавець звертається з запитом до відповідних місцевих органів виконавчої влади та органів місцевого самоврядування про належність зазначеного майна боржникові на праві власності та про його вартість а також до нотаріального органу чи не знаходиться це майно під арештом...
81349. Особливості звернення стягнення на предмет іпотеки 22.32 KB
  Звернення стягнення на предмет іпотеки і його реалізація для задоволення вимог іпотекодержателя здійснюються відповідно до умов іпотечного договору. У разі звернення стягнення на предмет іпотеки на підставі виконавчого напису нотаріуса на нотаріально посвідчених примірниках іпотечного договору та договору про іпотечний кредит чи на нотаріально посвідчених копіях цих документів або за рішенням суду орган державної виконавчої служби здійснює реалізацію предмета іпотеки в порядку установленому іпотечним договором. Відчуження предмета іпотеки...
81350. Звернення стягнення на грошові кошти боржника - юридичної особи 27.5 KB
  Готівка в національній та іноземній валюті яка знаходиться в касах або інших сховищах боржника юридичної особи підлягає невідкладному вилученню після її виявлення Державний виконавець звертає стягнення на кошти боржника юридичної особи що знаходяться в кредитних установах в тому числі в органах Державного казначейства в порядку передбаченому Законом. Якщо даних про наявність у боржника юридичної особи рахунків і вкладів у банках чи інших кредитних установах немає то державний виконавець одержує такі дані в податкових органах які...
81351. Звернення стягнення на інше майно боржника - юридичної особи 28.88 KB
  У разі відсутності в боржника юридичної особи коштів достатніх для покриття заборгованості стягнення звертається на інше майно належне боржникові юридичній особі на праві власності або закріплене за ним у тому числі на майно яке обліковується на окремому балансі філії представництва та іншого відокремленого підрозділу боржника юридичної особи за винятком майна виключеного з обороту або обмеженого в обороті незалежно від того хто фактично використовує це майно. На зазначене майно накладається арешт і воно реалізується в такій...
81352. Порядок звернення стягнення на майно при реорганізації та ліквідації боржника - юридичної особи 23.4 KB
  У разі реорганізації злиття приєднання розділення виділення перетворення боржника юридичної особи стягнення за виконавчими документами звертається на кошти та інше майно тієї юридичної особи на яку відповідно до закону покладено відповідальність за зобовязаннями боржника юридичної особи. У разі ліквідації боржника юридичної особи у тому числі внаслідок визнання боржника банкрутом виконавчий документ передається до ліквідаційної комісії або арбітражного керуючого для вирішення питання про подальший порядок виконання рішення у...
81353. Порядок звернення стягнення на зарплату та інші доходи боржника - фізичної особи. Розмір відрахувань із зарплати та інших доходів боржника 28.68 KB
  Розмір відрахувань із зарплати та інших доходів боржника Умови звернення стягнення на заробітну плату та інші доходи боржника Стягнення на заробітну плату заробіток пенсію стипендію та інші доходи боржника звертається за відсутності в боржника коштів на рахунках у банках та інших кредитних установах відсутності чи недостатності майна боржника для повного покриття належних до стягнення сум а також при виконанні рішень про стягнення періодичних платежів та стягнень на суму що не перевищує двох мінімальних розмірів заробітної плати. При...
81354. Особливості і виконання рішень про стягнення аліментів 28.71 KB
  У разі неможливості стягнення аліментів із заробітної плати чи інших доходів боржника протягом трьох місяців підряд якщо боржник не працює і не одержує доходів стягнення звертається на майно боржника. Розмір заборгованості з аліментів визначається державним виконавцем за місцем виконання рішення виходячи з фактичного заробітку доходів одержаного боржником за час протягом якого стягнення не провадилося або одержуваного ним на момент визначення заборгованості в твердій грошовій сумі або у відсотковому відношенні. Державний виконавець у...