KIF42

Zbadaj, czy podane niżej relacje są izomorficzne:

(a) relacja bycia matką, relacja bycia ojcem; fb) relacja bycia matką, relacja bycia dzieckiem;

(c)    relacja bycia córką, relacja bycia synem;

(d)    relacja bycia żoną, relacja bycia mężem;

(c) relacja bycia młodszym, relacja bycia starszym.

243. Relacja R odwzorowuje homomorficznie relację S na relacji T zawsze i tylko, gdy: (1) R jest relacją jednoznaczną.

(2) D(R)=P(S). (3) m=P(n oraz

(⁴) A^xAy/\^vA*l<^x>y>^eJi*<^v’^z>^eJi-

->{<*,»> 6 Sm<y, *>er)].

Na przykład, relacja, która przyporządkowuje każdemu człowiekowi liczbę przeżytych przezeń lat odwzorowuje hornomor-ficznie relację starszeństwa między ludźmi na relacji większości między liczbami (ograniczonej do pewnego ich podzbioru).

Wskaż relację, która odwzorowuje homomorficznie na relacji większości między liczbami relację:

(a)    bycia wyższym,

(b)    bycia cięższym,

(c)    posiadania większej objętości.

244.    Niech o,, Of, Oj. a_t, a_h będą dowolnymi (różnymi) przedmiotami. Wskaż relację R, która odwzorowuje homomor-ficznic relację S na relacji I, gdy:

«3>. <^fl2- ^a«M.

245.    Niech R, S będą relacjami określonymi w zbiorze liczb całkowitych przez następujące wzory:

<x,y>eS»|xJ~|y|.

<x,y>6 Raymx*.

Wskaż relację T, na której relacja R odwzorowuje homomor-Geznic relację S.

246. Przyporządkujmy wyrażenia reprezentujące zbiory wyrażeniom rachunku zdań (zawierającym jako jedyne terminy stale symbole a, v, wedle następującej zasady, jeśli W jest wyrażeniem rachunku zdań, to W* powstaje z W przez konsekwentne zastąpienie zmiennych p, q, r, ... zmiennymi

A. B, C.....zaś stałych a , v, ~ - odpowiednio — stałymi

n, \j, Na przykład:

W    W*

pvq    A\jB

~(pAg)    (/inS)'

(p v q) a

Zachodzą następujące zależności:

(ł) Jeśli IPjs W_x jest prawem rachunku zdań. to jest prawem rachunku zbiorów.

(2)    Jeśli Pj jest prawem rachunku zdań. to W* <= W* jest prawem rachunku zbiorów.

(3)    Jeśli Jf' jest prawem rachunku zdań, to JF* = 1 jest prawem rachunku zbiorów.

Zależności te pozwalają otrzymywać prawa rachunku zbiorów z praw rachunku zdań; na przykład, z praw dc Morgana dla zdań:

~(>A?)«=(~/>V~0),    q) = (~p*~q)

— prawa dc Morgana dla zbiorów:

(AnB)'=(A'\jB'),    (AvB)'=(A‘nB').

Z jakich tautologii rachunku zdań otrzymujemy następujące prawa rachunku zbiorów:

(a)    AvA~A    (d) (AnA')'ml

(b)    AnA~A    (c) (.A’)'~A

(c)    AuA’-l    (OAcA