7. Свойства бинарных отношений: рефлексивность, антирефлексивность, симметричность, антисимметричность, транзитивность, связность.

Рассмотрим бинарное отношение р заданное на множестве А:

1. Рефлексивным называется отношение р такое, что . В матрице рефлексивного отношения на главное диагонали должны располагаться «1».

   

2. Антирефлексивным называется отношение р такое, что . В матрице антирефлексивного отношения на главной диагонали должны располагаться «0».

3. Симметричным называется отношение р такое, что . В матрице симметричного отношения элементы должны быть симметричны относительно главной диагонали.

4. Антисимметричным называется отношение р такое, что => х=у. В матрице антисимметричного отношения не должно быть симметричных относительно главное диагонали «1».

5. Транзитивным называется отношение р такое, что => (x,z) p. В матрице транзитивного отношения нули не должны заменяться единицами.

   

6. Связным называется отношение р такое, что => (x,y) p или (у,х) р. В матрице симметричного отношения не должно быть симметричных относительно главной диагонали «0».

8. Замыкания отношений. Транзитивное замыкание, рефлексивное транзитивное замыкание. Теоремы о транзитивном и рефлексивном транзитивном замыкании.

Пусть р и p’ отношения на множестве А. Отношение р’ называется замыканием р относительно свойства С, если:

1. р’ обладает свойством С, т.е. С(р’)

2. р’ является надмножеством р:р с р’

3. Р’ является наименьшим: С(р’’) и р с р’’ => р’ c р’’ (любое р’’, обладающее свойством С и содержащее в себе р, содержит в себе также и р’)

Пусть р⁺ - объединение положительных степеней р, а р^* - объединение неотрицательных степеней р, т.е. р⁺= и р^*= . Тогда р⁺ - транзитивное замыкание р, а р^* - рефлексивно-транзитивное замыкание р.

9. Операции над бинарными отношениями, заданными в матричной форме.

Рассмотрим два конечных множества А={а₁,а_2,…,а_m}, B={b₁,b₂,…,b_n} и бинарное отношение

Р с А . Определим матрицу [P]=(p_ij) размера m n, бинарного отношения Р по следующему правилу: p_ij=1, если (a_i,b_j) P. : p_ij=0, если (a_i,b_j) P.

Заметим, что любая матрица, состоящая из нулей и единиц, является матрицей некоторого бинарного отношения.

Для матричной формы задания:

1. Объединение отношений. v .

2. Пересечение отношений. .

3. Обратное отношение. Транспонирование: C_ij=a_ij.

4. Композиция отношений. С_ij= .

5. Дополнение. C_ij=a_ij.

10. Алгоритм определения матрицы транзитивного замыкания бинарного отношения.

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, StdCtrls;

type

TForm1 = class(TForm)

Button1: TButton;

Edit1: TEdit;

StringGrid1: TStringGrid;

StringGrid2: TStringGrid;

Button2: TButton;

procedure Button1Click(Sender: TObject);

procedure Button2Click(Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1.Button1Click(Sender: TObject);

var h:integer;

begin

h:=strtoint(Edit1.Text);

h:=h+1;

StringGrid1.Colcount:=h;

StringGrid1.Rowcount:=h;

StringGrid2.Colcount:=h;

StringGrid2.Rowcount:=h;

end;

procedure TForm1.Button2Click(Sender: TObject);

var a:array[1..100,1..100] of integer ;

b:array[1..100,1..100] of integer ;

c:array[1..100,1..100] of integer ;

h,i,j,k,z:integer;

begin

z:=0;

h:=strtoint(Edit1.text);

For i:=1 to h do begin

For j:=1 to h do begin

a[i,j]:= strtoint(StringGrid1.Cells[i,j]);

end;

end;

For i:=1 to h do begin

For j:=1 to h do begin

c[i,j]:=a[i,j];

b[i,j]:=a[i,j];

end;

end;

while z=0 do begin

For i:=1 to h do begin

For j:=1 to h do begin

For k:=1 to h do begin

If (a[i,k]*b[k,j])=1 then begin b[i,j]:=1; break; end;

end;

If c[i,j]>=b[i,j] then z:=1 else z:=0;

end;

end;

For i:=1 to h do begin

For j:=1 to h do begin

If (c[i,j]=0) and (b[i,j]=1) then c[i,j]:=b[i,j];

end;

end;

end;

For i:=1 to h do begin

For j:=1 to h do begin

StringGrid2.Cells[i,j]:=inttostr(c[i,j]);

end;

end;

end;

end.