Міністерство освіти та науки України
Національний університет «Львівська політехніка»
Кафедра ІСМ
Лабораторна робота № 3
з дисципліни:
«Теорія прийняття рішень»
на тему:
«Дослідження операцій з метризованими бінарними відношеннями та їх властивостей»
Виконав:
студент
групи КН-46
Рак О.Р.
Прийняла:
асистент
Заяць М. М.
Львів-2012
Мета роботи: Вивчення та практичне ознайомлення з основними алгебрами метризованих бінарних відношень та з властивостями і типами метризованих бінарних.
Варіант завдання: 20.
Тексти програм опису об’єктів
namespace Lab1
{
public abstract class Relation
{
public enum ElementaryRelation
{
Free,
Full,
Diagonal,
AntiDaigonal
};
public abstract Relation Intersection(Relation other);
public abstract Relation Union(Relation other);
public abstract Relation Distinction(Relation other);
public abstract Relation SymmetricDistinction(Relation other);
public abstract Relation Complemention();
public abstract Relation Reverse();
public abstract Relation Compose(Relation other);
public abstract Relation Restriction();
public abstract bool IsInRelation(int a, int b);
public abstract int Size { get; }
public abstract void Show();
public abstract bool IsSubRelation(Relation other);
}
}
using System;
using System.Collections.Generic;
using System.Linq;
namespace Lab1
{
public class SectionBasedRelation: Lab2.PropertiedRelation
{
private readonly int _size;
private readonly IEnumerable<int>[] _sections;
public SectionBasedRelation()
{
_size = 0;
_sections = new IEnumerable<int>[0];
}
public SectionBasedRelation(ElementaryRelation type, int size)
{
switch (type)
{
case ElementaryRelation.Free:
_sections = new IEnumerable<int>[size];
for (int i = 0; i < size; i++)
{
_sections[i] = new List<int>(size);
}
break;
case ElementaryRelation.Full:
_sections = new List<int>[size];
for (int i = 0; i < size; i++)
{
_sections[i] = new List<int>(size);
for (int j = 0; j < size; j++)
{
((List<int>) (_sections[i])).Add(j);
}
}
break;
case ElementaryRelation.Diagonal:
_sections = new IEnumerable<int>[size];
for (int i = 0; i < size; i++)
{
_sections[i] = new List<int>(size) {size - i - 1};
}
break;
case ElementaryRelation.AntiDaigonal:
_sections = new IEnumerable<int>[size];
for (int i = 0; i < size; i++)
{
_sections[i] = new List<int>(size) {i};
}
break;
}
}
public SectionBasedRelation(int size)
{
_size = size;
_sections = new IEnumerable<int>[_size];
for (int i = 0; i < _sections.Length; i++)
{
_sections[i] = new List<int>(_size);
}
}
public SectionBasedRelation(bool[,] relations)
{
_size = relations.GetLength(0);
_sections = new IEnumerable<int>[_size];
CopyArrayToMatrix(relations);
}
private void CopyArrayToMatrix(bool[,] relations)
{
for (var i = 0; i < relations.GetLength(0); i++)
{
for (var j = 0; j < relations.GetLength(1); j++)
{
if (_sections[j] ==null)
{
_sections[j] = new List<int>(_size);
}
if (relations[i, j])
{
((List<int>)_sections[j]).Add(i);
}
}
}
}
private SectionBasedRelation(IEnumerable<int>[] sections)
{
_size = sections.Length;
_sections = sections;
}
public SectionBasedRelation(Relation other)
{
_size = other.Size;
_sections = new IEnumerable<int>[other.Size];
for (int i = 0; i < other.Size; i++)
{
for (int j = 0; j < other.Size; j++)
{
if (_sections[j]==null)
{
_sections[j] = new List<int>(other.Size);
}
if (other.IsInRelation(i, j))
{
((List<int>) _sections[j]).Add(i);
}
}
}
}
private bool[,] GetRelationsMatrix(Relation other, Func<bool, bool, bool> op)
{
var matrix = new bool[Size, Size];
GetMatrixFromOperation(other, op, matrix);
return matrix;
}
private void GetMatrixFromOperation(Relation other, Func<bool, bool, bool> op, bool[,] matrix)
{
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
matrix[i, j] = op(IsInRelation(i, j), other.IsInRelation(i, j));
}
}
}
public override Relation Intersection(Relation other)
{
return new SectionBasedRelation(GetRelationsMatrix(other, (a, b) => a && b));
}
public override Relation Union(Relation other)
{
return new SectionBasedRelation(GetRelationsMatrix(other, (a, b) => a || b));
}
public override Relation Distinction(Relation other)
{
return new SectionBasedRelation(GetRelationsMatrix(other, (a, b) => a && !b));
}
public override Relation SymmetricDistinction(Relation other)
{
return new SectionBasedRelation(GetRelationsMatrix(other, (a, b) => (a || b) && !(a && b)));
}
public override Relation Complemention()
{
var sections = new List<int>[Size];
for (int i = 0; i < Size; i++)
{
sections[i] = new List<int>(Size);
for (int k = 0; k < Size; k++)
{
if (!_sections[i].Contains(k))
{
sections[i].Add(k);
}
}
}
return new SectionBasedRelation(sections);
}
public override Relation Reverse()
{
var matrix = new bool[Size, Size];
GetReversedMatrix(matrix);
return new SectionBasedRelation(matrix);
}
private void GetReversedMatrix(bool[,] matrix)
{
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
matrix[j, i] = IsInRelation(i, j);
}
}
}
public override Relation Compose(Relation other)
{
return new SectionBasedRelation(GetTransitionedMatrix(other));
}
private bool[,] GetTransitionedMatrix(Relation other)
{
var transitioned = new bool[Size, Size];
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
if (IsInRelation(i, j) && other.IsInRelation(i, j))
{
transitioned[i, j] = true;
}
else
{
transitioned[i, j] = CheckForTransition(i, j, other);
}
}
}
return transitioned;
}
private bool CheckForTransition(int i, int j, Relation other)
{
for (int k = 0; k < Size; k++)
{
if (IsInRelation(i, k) && other.IsInRelation(k, j))
{
return true;
}
}
return false;
}
public override Relation Restriction()
{
throw new NotImplementedException();
}
public override bool IsInRelation(int a, int b)
{
return _sections[b].Contains(a);
}
public override int Size
{
get { return _size; }
}
public override void Show()
{
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
Console.Write("{0,3}", IsInRelation(i, j) ? 1 : 0);
}
Console.WriteLine();
}
}
public override bool IsSubRelation(Relation other)
{
if (other.Size < this.Size)
return false;
for (int i = 0; i < other.Size; i++)
{
for (int j = 0; j < other.Size; j++)
{
if (other.IsInRelation(i, j))
{
if (!IsInRelation(i, j))
return false;
}
}
}
return true;
}
public override Relation FactorizeByEquivalence(Relation relation)
{
var sectionRelation = new SectionBasedRelation(relation);
return FactorizeByEquivalence(sectionRelation._sections.Distinct(new EnumerableComparer()));
}
private class EnumerableComparer: IEqualityComparer<IEnumerable<int>>
{
public bool Equals(IEnumerable<int> x, IEnumerable<int> y)
{
if (x.Count() != y.Count())
return false;
else
{
if (x.Any(i => !y.Contains(i)))
{
return false;
}
if (y.Any(i => !x.Contains(i)))
{
return false;
}
}
return true;
}
public int GetHashCode(IEnumerable<int> obj)
{
var res = obj.Aggregate((r, e) => e.GetHashCode());
return res;
}
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Lab1
{
public class MatrixBasedRelation: Lab2.PropertiedRelation
{
private readonly bool[,] _matrix;
#region Constructors
public MatrixBasedRelation()
{
_matrix = new bool[0,0];
}
public MatrixBasedRelation(ElementaryRelation type, int size)
{
switch (type)
{
case ElementaryRelation.Free:
_matrix = new bool[size, size];
break;
case ElementaryRelation.Full:
_matrix = new bool[size, size];
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
_matrix[i, j] = true;
}
}
break;
case ElementaryRelation.Diagonal:
_matrix = new bool[size,size];
for (int i = 0; i < size; i++)
{
_matrix[i, i] = true;
}
break;
case ElementaryRelation.AntiDaigonal:
_matrix = new bool[size,size];
for (int i = 0; i < size; i++)
{
_matrix[i, size - i - 1] = true;
}
break;
}
}
public MatrixBasedRelation(int size)
{
_matrix = new bool[size, size];
}
public MatrixBasedRelation(bool[,] relations)
{
_matrix = new bool[relations.GetLength(0), relations.GetLength(1)];
CopyArrayToMatrix(relations);
}
private void CopyArrayToMatrix(bool[,] relations)
{
for (var i = 0; i < _matrix.GetLength(0); i++)
{
for (var j = 0; j < _matrix.GetLength(1); j++)
{
_matrix[i, j] = relations[i, j];
}
}
}
public MatrixBasedRelation(Relation other)
{
_matrix = new bool[other.Size, other.Size];
for (var i = 0; i < _matrix.GetLength(0); i++)
{
for (var j = 0; j < _matrix.GetLength(1); j++)
{
_matrix[i, j] = other.IsInRelation(i, j);
}
}
}
private MatrixBasedRelation(bool[,] relations, bool isMatrixForThisOne)
{
if (isMatrixForThisOne)
{
_matrix = relations;
}
else
{
CopyArrayToMatrix(relations);
}
}
private MatrixBasedRelation(int size, IEnumerable<bool> elements)
{
_matrix = new bool[size, size];
var enumerator = elements.GetEnumerator();
for (int i = 0; i < size; i++)
{
for (int j = 0; j < size; j++)
{
enumerator.MoveNext();
_matrix[i, j] = enumerator.Current;
}
}
}
#endregion
public override int Size { get { return _matrix.GetLength(0); } }
public override bool IsInRelation(int a, int b)
{
return _matrix[a, b];
}
#region Helpers
private void CheckSizes(Relation other)
{
if (Size != other.Size)
throw new ArgumentException("Sizes of relations is not equal");
}
private Relation CheckSizesAndCreateNewRelationBasedOnOperation(Relation other, Func<bool, bool, bool> op)
{
CheckSizes(other);
var newRelationsMatrix = GetNewMatrixResultOfOperation(other, op);
return new MatrixBasedRelation(newRelationsMatrix, true);
}
private bool[,] GetReversedMatrix(bool[,] matrix)
{
var reversed = new bool[Size, Size];
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
reversed[i, j] = matrix[j, i];
}
}
return reversed;
}
private bool[,] GetNewMatrixResultOfOperation(Relation other, Func<bool, bool, bool> operation)
{
var newRelationsMatrix = new bool[Size, Size];
for (var i = 0; i < Size; i++)
{
for (var j = 0; j < Size; j++)
{
newRelationsMatrix[i, j] = operation(IsInRelation(i, j), other.IsInRelation(i, j));
}
}
return newRelationsMatrix;
}
private bool[,] GetTransitionedMatrix(bool[,] thisMatrix, Relation other)
{
var transitioned = new bool[thisMatrix.GetLength(0),thisMatrix.GetLength(1)];
for (int i = 0; i < transitioned.GetLength(0); i++)
{
for (int j = 0; j < transitioned.GetLength(1); j++)
{
if (thisMatrix[i, j] && other.IsInRelation(i, j))
{
transitioned[i, j] = true;
}
else
{
transitioned[i, j] = CheckForTransition(i, j, thisMatrix, other);
}
}
}
return transitioned;
}
private bool CheckForTransition(int i, int j, bool[,] thisMatrix, Relation other)
{
for (int k = 0; k < thisMatrix.GetLength(0); k++)
{
if (thisMatrix[i, k] && other.IsInRelation(k, j))
{
return true;
}
}
return false;
}
#endregion
public override Relation Intersection(Relation other) // ^
{
return CheckSizesAndCreateNewRelationBasedOnOperation(other, (a, b) => a && b);
}
public override Relation Union(Relation other) // u
{
return CheckSizesAndCreateNewRelationBasedOnOperation(other, (a, b) => a || b);
}
public override Relation Distinction(Relation other) // \
{
return CheckSizesAndCreateNewRelationBasedOnOperation(other, (a, b) => a && !b);
}
public override Relation SymmetricDistinction(Relation other) // xor
{
return CheckSizesAndCreateNewRelationBasedOnOperation(other, (a, b) => (a || b) && !(a && b));
}
public override Relation Complemention() // ~
{
return new MatrixBasedRelation(Size, _matrix.OfType<bool>().Select(a => !a));
}
public override Relation Reverse() // -1
{
var newMatrixArray = GetReversedMatrix(_matrix);
return new MatrixBasedRelation(newMatrixArray, true);
}
public override Relation Compose(Relation other) // o
{
CheckSizes(other);
var newMatrixArray = GetTransitionedMatrix(_matrix, other);
return new MatrixBasedRelation(newMatrixArray, true);
}
public override Relation Restriction()
{
throw new NotImplementedException();
}
public override void Show()
{
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
Console.Write("{0,3}", IsInRelation(i, j) ? 1 : 0);
}
Console.WriteLine();
}
}
public override bool IsSubRelation(Relation other)
{
if (other.Size < this.Size)
return false;
for (int i = 0; i < other.Size; i++)
{
for (int j = 0; j < other.Size; j++)
{
if (other.IsInRelation(i, j))
{
if (!IsInRelation(i, j))
return false;
}
}
}
return true;
}
public override Relation FactorizeByEquivalence(Relation relation)
{
return new SectionBasedRelation(this).FactorizeByEquivalence(relation);
}
}
}
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace Lab1.Lab2
{
public abstract class PropertiedRelation : Relation
{
public bool IsReflexive()
{
var res = true;
for (int i = 0; i < Size; i++)
{
if (!IsInRelation(i, i))
{
res = false;
break;
}
}
return res;
}
public bool IsAntiReflexive()
{
return !IsReflexive();
}
public bool IsSymmetric()
{
var res = true;
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
if (IsInRelation(i, j) && !IsInRelation(j, i))
{
res = false;
break;
}
}
}
return res;
}
public bool IsASymmetric()
{
var res = true;
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
if (IsInRelation(i, j) && IsInRelation(j, i))
{
res = false;
break;
}
}
}
return res;
}
public bool IsAntySymmetric()
{
var res = true;
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
if (IsInRelation(i, j) && IsInRelation(j, i) && (i != j))
{
res = false;
break;
}
}
}
return res;
}
public bool IsTransitive()
{
return IsSubRelation(Compose(this));
}
public bool IsEmpty()
{
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
if (IsInRelation(i, j))
{
return false;
}
}
}
return true;
}
public bool IsAcycled()
{
bool res = true;
var reversed = Reverse();
Relation temp = new MatrixBasedRelation(this);
for (int i = 0; i < Size; i++)
{
var step = temp.Intersection(reversed);
if (!((PropertiedRelation)step).IsEmpty())
{
res = false;
break;
}
temp = temp.Compose(temp);
}
return res;
}
public bool IsCohereted()
{
return
((PropertiedRelation)
Union(Reverse()).Distinction(new MatrixBasedRelation(ElementaryRelation.Diagonal, Size))).IsEqual(
(new MatrixBasedRelation(ElementaryRelation.Full, Size)).Distinction(
new MatrixBasedRelation(ElementaryRelation.Diagonal, Size)));
}
public bool IsEqual(Relation other)
{
bool res = true;
for (int i = 0; i < Size; i++)
{
for (int j = 0; j < Size; j++)
{
if (IsInRelation(i, j) != other.IsInRelation(i, j))
{
res = false;
break;
}
}
}
return res;
}
public bool IsTolerance()
{
return IsReflexive() && IsSymmetric();
}
public bool IsEquivalence()
{
return IsReflexive() && IsSymmetric() && IsTransitive();
}
public bool IsQuasi()
{
return IsReflexive() && IsTransitive();
}
public bool IsOrder()
{
return IsReflexive() && IsAntySymmetric() && IsTransitive();
}
public bool IsStrictOrder()
{
return IsASymmetric() && IsTransitive();
}
public bool IsLinearOrder()
{
return IsReflexive() && IsAntySymmetric() && IsTransitive() && IsCohereted();
}
public Relation TransitionedClosure()
{
Relation tempComposition = new MatrixBasedRelation(this);
Relation unioned = new MatrixBasedRelation(this);
for (int i = 0; i < Size - 1; i++)
{
tempComposition = tempComposition.Compose(this);
unioned = unioned.Union(tempComposition);
}
return unioned;
}
public Relation Attainability() // ~
{
return TransitionedClosure().Union(new MatrixBasedRelation(ElementaryRelation.Diagonal, Size));
}
public Relation MutuallyAttainability() // <->
{
return Attainability().Intersection(Attainability().Reverse());
}
public abstract Relation FactorizeByEquivalence(Relation r);
public Relation FactorizeByEquivalence(IEnumerable<IEnumerable<int>> D)
{
int newSize = D.Count();
var matrix = new bool[newSize,newSize];
for (int i = 0; i < newSize; i++)
{
for (int j = 0; j < newSize; j++)
{
matrix[i, j] = IsInRelation(i, j, D);
}
}
return new MatrixBasedRelation(matrix);
}
private bool IsInRelation(int i, int j, IEnumerable<IEnumerable<int>> D)
{
foreach (var i1 in D.ElementAt(i))
{
foreach (var j1 in D.ElementAt(j))
{
if (IsInRelation(i1, j1))
{
return true;
}
}
}
return false;
}
}
}