Transitiv lukning

Transitiv lukning i mængdeteori  er en operation på binære relationer . Den transitive lukning af en binær relation R på en mængde X er den mindste transitive relation på en mængde X, der inkluderer R.

For eksempel, hvis X er et sæt mennesker (både levende og døde), og R er en "er en forælder"-relation, så er den transitive lukning af R en "er en forfader"-relation. Hvis X er mængden af ​​lufthavne, og xRy svarer til "der er en flyvning fra x til y", og den transitive lukning af R er lig med P, så svarer xPy til "du kan flyve fra x til y med fly " (selv om du nogle gange skal flyve med transfers)

Eksempel

Lad mængde A være følgende sæt af dele og strukturer:

A = {Bolt, møtrik, motor, bil, hjul, aksel}

desuden kan nogle af delene og strukturerne bruges til samling af andre strukturer. Forholdet mellem detaljer er beskrevet af relationen R("direkte brugt i") og består af følgende tuples:

Tabel 1. Relation R.
Transitiv lukning består af tupler (tilføjede tupler er markeret med fed skrift):

Tabel 2. Den transitive lukning af relationen R.

Den åbenlyse betydning af lukningen R er at beskrive inkorporeringen af ​​dele i hinanden, ikke kun direkte, men gennem deres brug i mellemdele, for eksempel bruges en bolt i en bil, da den bruges i en motor, og en motor bruges i en bil.