Příklad 1 [2 body + 1 bonusový bod]
Řešení Nejprve si uvědomme, že každou realizaci M. jazyka C je možné neformálně vnímat jako (potenciálně nekonečný) graf s množinou vrcholů M a množinou hran Rm Intuitivně, formule ipi říká, že v tomto grafu existuje právě jeden vrchol do kterého nevede žádná hrana. Formule (f2 říká, že do každého vrcholu vede nejvýše jedna hrana. Formule (p^ vynucuje, že žádný vrchol nemá přesně jednoho následníka a formule ^4 říká, že každý vrchol má nejvýše dva následníky. Konjunkci těchto formulí splňuje zejména každý binární strom, pokud tedy chceme realizaci s alespoň 6 prvky, lze uvážit realizaci M. s nosičem M — {1,2, 3,4, 5, 6, 7}, v níž RM = {(1, 2), (1, 3), (2,4), (2, 5), (3, 6), (3, 7)}.
Pro bonusové zadání stačí uvážit realizaci M. s nosičem M — No, v níž platí Rm — {(n, n+ í),(n,n + 2) | n G N je sudé číslo}.
Příklad 2 [3 body + 1 bonusový bod]
Řešení Existuje vícero správných řešení. Hodí se zavést syntaktickou zkratku empty(z) = Vít 0 z — z, která vynutí, že v libovolné realizaci M. jazyka C platí M. \= empty(z)[e] právě když e{z) — 0. Pak lze položit ip — 3z(empty(z) A(i0 y — z) A Vit(it Q y — z —> u Q x — u)). Tato formule říká, že e{x) je největší (vzhledem k inkluzi) podmnožina N disjunktní s e{y), což je právě N \ e{y).
Formuli ip lze buď zapsat pomocí formule ip a De Morganových zákonů, nebo si lze uvědomit, že sjednocení dvou množin je nejmenší množinou (vzhledem k inkluzi), která obsahuje tyto dvě množiny jako své podmnožiny. Takovouto vlastnost je možné zapsat formulí ip = b Q a — b A c Q a — c A \/u((u 0 b — b A u Q c — c) ^ uQ a — a).
1