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

• 4. Důkaz sporem.

• existuje E tak, že E(R) = R+ a jakoukoliv relaci R, tj. i E(Rs) Rs+ pro dostatečně velká s

• dle lemmatu, Rs+ b1,b2 |(b1,b2)

• Nastávají dva případy:

• (a) každá klauzule z obsahuje atom tvaru

• b1ai, b2ai nebo b1b2+ c (bb c

• Nechť b1b2 amam+d ,

• kde m  libovolné i a d libovolné c