Dotaz na tranzitivní uzávěr (1)

• Tv.: Nechť R je schéma binární relace. Pak v AR neexistuje výraz, který pro každou relaci R počítá její tranzitivní uzávěr R+.

• Důkaz:

• 1. Nechť s= a1,a2,...,as, s 1, je množina konstant, na které neexistuje uspořádání a

• Rs =a1a2, a2a3,...,as-1as

• Pz.: Rs grafu a1  a2 as

• Pz.: je-li na definováno uspořádání , pak

• Rs(Rs Rs )(1  2)

• 2. Ukážeme, že pro libovolný výraz E(R) existuje s takové, že E(Rs) Rs+.