Skończone zbiory wyrażeń

Df. I. Powiemy, że wyrażenie E jest elementem wyrażenia F jeśli F ma kształt ∗ Z I, przy czym zachodzi związek {IZE}.

Df. II. Wyrażenie kształtu ∗ EE E oznaczać będziemy krótko ι'E. Widzimy natychmiast, że ι'E posiada zawsze dokładnie jeden element E. Wprowadzanie osobnej definicji pojęcia zbioru jest zbędne, gdyż w sensie przyjętej definicji każde wyrażenie stanowi pewien ściśle określony i skończony zbiór wyrażeń. Tak np. wyrażenia:

0, ∗00, ∗ ∗000, ∗ ∗00∗00 są zbiorami pustymi, bo nie posiadają żadnych elementów, wyrażenia zaś:

∗0∗00, ∗0 ∗0∗00, ∗0∗0∗ ∗0 ∗000 przedstawiają kolejno zbiory złożone z 1, 2, 3 elementów. Można się łatwo przekonać, że wszystkie elementy pewnego, odpowiednio zbudowanego wyrażenia mogą tworzyć zupełnie dowolny, z góry dany skończony zbiór [3]

Pojęcia: identyczności, sumy i iloczynu zbiorów wprowadzamy w ogólnie przyjęty sposób:

Df. III. Wyrażenia E, F nazywać będziemy równymi klasowo (symbolicznie: =CL EF) jeśli każdy element wyrażenia E jest elementem wyrażenia F i na odwrót.

Df. IV. Wyrażenie G nazywać będziemy sumą wyrażeń E, F jeśli:
1. każdy element E jest elementem G,
2. każdy element F jest elementem G,
3. każdy element G jest elementem E lub elementem F .

Df. V. Wyrażenie G nazywać będziemy iloczynem wyrażeń E, F jeśli:
1. wszystkie elementy wspólne wyrażeń E,F są elementami G,
2. każdy element G jesł elementem E oraz elementem F.

Na oznaczenie sumy i iloczynu wyrażeń E, F używać będziemy symboli ∪ EFG, ∩ EFG, które czytamy kolejno: G jest sumą wyrażeń E, F; G jest iloczynem wyrażeń E, F.

Przy pomocy wprowadzonych pojęć uzyskujemy bez istotnych trudności pełną algebrę klas skończonych, która stanowi jednak tylko fragment ogólnej algebry klas. W szczególności nie możemy w obrębie klas skończonych określić pojęcia dopełnienia danego zbioru. Tutaj zajmiemy się jednym tylko twierdzeniem algebry klas skończonych, gdyż z innych nie będziemy korzystać w dalszym ciągu.

Tw. Dla dowolnych wyrażeń E, F istnieje wyrażenie G spełniające związek ∪ EFG. Dowód: Jeżeli = E 0(względnie = F 0), wyrażenie E (wzgl. F) jest zbiorem pustym, mamy zatem w ∪ EFF (wzgl. ∪ E F E). Wystarczy zatem zająć się wypadkiem, gdy E, F są wyrażeniami złożonymi. Mamy wtedy: = EZ 1 I 1 = E ∗ Z 2 I 2 Oznaczamy przez Z wyrażenie ∗ I 1 I 2. Na mocy twierdzenia, które udowodniłem w "Podstawach semantyki" (Lem. 1, str. 74) istnieją wyrażenia ∗J 1 J 2 spełniające związki: =CL E ∗ Z 1 J 1 = CL E ∗ Z 2 J 2. Widzimy natychmiast, że szukanym zbiorem G jest wyrażenie ∗ Z ∗J 1 J 2 jeśli ∼ = J 1 Z, a wyrażenie ∗Z J 2 jeśli = J 1 Z.

Z twierdzenia naszego wynika również oczywiście istnienie sumy trzech, czterech i większej ilości wyrażeń. Sumy powyższe zapisywać będziemy w postaci: ∪DEF,G,CDEF,G, itd.