4053

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

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

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

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

Русский

2012-11-12

185 KB

106 чел.

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

Бинарное отношение 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.


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


 

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

25934. Измерительные трансформаторы тока и напряжения. Назначение. Конструктивное исполнение. Принцип действия. Условия выбора 26 KB
  Измерительные трансформаторы тока и напряжения. Трансформатор напряжения трансформатор предназначеный для преобразования высокого напряжения в низкое в цепях РЗиА. Применение трансформатора напряжения позволяет изолировать логические цепи защиты и цепи измерения от цепи высокого напряжения. Виды трансформаторов напряжения Заземляемый трансформатор напряжения однофазный трансформатор напряжения один конец первичной обмотки которого должен быть наглухо заземлен или трехфазный трансформатор напряжения нейтраль первичной обмотки которого...
25935. Разрядники: назначение, конструкция, принцип действия. Вентильные и трубчатые разрядники. Нелинейные ограничители перенапряжения (ОПН): назначение, конструкция, принцип действия. Условия выбора 52.5 KB
  Нелинейные ограничители перенапряжения ОПН: назначение конструкция принцип действия. В результате пробоя в трубке возникает интенсивная газогенерация и через выхлопное отверстие образуется продольное дутье достаточное для погашения дуги . ОПН Ограничитель перенапряжения нелинейный ОПН это разрядник без искровых промежутков. Активная часть ОПН состоит из последовательного набора варисторов.
25936. Устройство защитного отключения (УЗО). Назначение, схема подключения 53 KB
  Устройство защитного отключения УЗО. Устройство защитного отключения УЗО; более точное название: Устройство защитного отключения управляемое дифференциальным остаточным током сокр. УЗО−Д механический коммутационный аппарат или совокупность элементов которые при достижении превышении дифференциальным током заданного значения при определённых условиях эксплуатации должны вызвать размыкание контактов. Основная задача УЗО защита человека от поражения электрическим током и от возникновения пожара вызванного утечкой тока через...
25937. Конструкция и принцип действия воздушных выключателей. Достоинства и недостатки. Условия выбора. Сравнение с другими высоковольтными выключателями 27.5 KB
  Воздушные выключатели обладают высокими техническими характеристиками. Сетевые выключатели на напряжение 6кВ и выше применяемыев электрических сетях и предназначенные для пропуска и коммутации тока в нормальных условиях работы цепи и в условиях КЗ. Генераторные выключатели на напряжение 624 кВ предназначенные для пропуска и коммутации токов в нормальных условиях а также в пусковых режимах и при КЗ. Выключатели для электротермических установок с напряжениями 6220 кВ предназначенные для работы как в нормальных так и в аварийных режимах 4.
25938. Конструкция и принцип действия элегазовых выключателей. Достоинства и недостатки. Условия выбора. Сравнение с другими высоковольтными выключателями 23 KB
  В элегазовых выключателях гашение дуги происходит так же как и в воздушных выключателях при интенсивнои охлаждении дуги потоком газа. В элегазовых дугогасительных устройствах в отличие о воздушных при гашении дуги истечение газа через сопло происходит не в атмосферу а в замкнутый объем камеры заполненный элегазом при небольшом избыточном давлении. По способу гашения дуги в элегазе различают следующие ДУ: с системой продольного дутья в которую предварительно сжатый воздух поступает из резервуара с относительно высоким давлением элегаза ДУ...
25939. Выключатели нагрузки. Назначение, конструктивное исполнение и принцип действия выключателей нагрузки. Условия выбора 21 KB
  Выключатели нагрузки. Назначение конструктивное исполнение и принцип действия выключателей нагрузки. Выключатели нагрузки используются для оперативного соединения и разъединения цепи. Выключатель нагрузки обеспечивает двухкратное включение нормированного для него тока включения на короткое замыкание без повреждений препятствующих его дальнейшей работе в нормальном и эксплуатационном режиме.
25940. Расчет деревянных, металлических, железобетонных перекрытий 1.07 MB
  Орел 2011 Расчет деревянного перекрытия Подобрать сечение деревянной балки для перекрытия жилого дома.Предварительно принимаем собственный вес одного метра балки qnбалки=025кН м;f=1.1 qбалки= qnбалки f=0.Собираем нагрузку на погонный метр балки с учетом её собственного веса: qn=qnперекрытияlгр qnбалки=18140275=277кН м; q= qперекрытияlгр qбалки=234120275=3083кН м.
25941. СБОРНО-МОНОЛИТНЫЕ КОНСТРУКЦИИ 26.5 KB
  СБОРНОМОНОЛИТНЫЕ КОНСТРУКЦИИ конструкции состоящие из заранее изготовленных на заводах отд. Наибольшее распространение получили сборномонолитные конструкции со сборными элементами из железобетона см. Железобетонные конструкции . арматуру конструкции и иногда используются в качестве формы опалубки для монолитного бетона; их целесообразно делать предвари тсльно напряженными.
25942. Здания и сооружения из монолитного железобетона 31 KB
  Монолитные конструкции несущего остова здания представляют собой неразрезные элементы наружных и внутренних несущих стен колонн ригелей и перекрытий жестко связанных между собой в пространственную систему работающую под нагрузкой как единое целое. Здания из монолитного железобетона разделяются на монолитные и сборномонолитные и выполняются по следующим конструктивным схемам: монолитные несущие и ограждающие конструкции; монолитный каркас колонны и перекрытия наружные и внутренние стены сборные или каменных материалов; монолитные...