Mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a Boolean
We study mathematical models of the structure of nilpotent subsemigroups of the semigroup $PTD(B_n)$ of partial contracting transformations of a Boolean, the semigroup $TD(B_n)$ of full contracting transformations of a Boolean, and the inverse semigroup $ISD(B_n)$ of contracting transformations of a...
Gespeichert in:
| Datum: | 2009 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | Ukrainisch Englisch |
| Veröffentlicht: |
Institute of Mathematics, NAS of Ukraine
2009
|
| Online Zugang: | https://umj.imath.kiev.ua/index.php/umj/article/view/3072 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Ukrains’kyi Matematychnyi Zhurnal |
| Завантажити файл: |  |
Institution
Ukrains’kyi Matematychnyi Zhurnal| _version_ | 1860509098727964672 |
|---|---|
| author | Selezneva, N. V. Селезньова, Н. В. |
| author_facet | Selezneva, N. V. Селезньова, Н. В. |
| author_sort | Selezneva, N. V. |
| baseUrl_str | https://umj.imath.kiev.ua/index.php/umj/oai |
| collection | OJS |
| datestamp_date | 2020-03-18T19:44:40Z |
| description | We study mathematical models of the structure of nilpotent subsemigroups of the semigroup $PTD(B_n)$ of partial contracting transformations of a Boolean, the semigroup $TD(B_n)$ of full contracting transformations of a Boolean, and the inverse semigroup $ISD(B_n)$ of contracting transformations of a Boolean. We propose a convenient graphical representation of the semigroups considered. For each of these semigroups, the uniqueness of its maximal nilpotent subsemigroup is proved. For $PTD(B_n)$ and $TD(B_n)$, the capacity of a maximal nilpotent subsemigroup is calculated. For $ISD(B_n)$, we construct estimates for the capacity of a maximal nilpotent subsemigroup and calculate this capacity for small $n$. For all indicated semigroups, we describe the structure of nilelements and maximal nilpotent subsemigroups of nilpotency degree $k$ and determine the number of elements and subsemigroups for some special cases. |
| first_indexed | 2026-03-24T02:35:42Z |
| format | Article |
| fulltext |
UDK 519.4
N. V. Selezn\ova (Ky]v. nac. un-t im. T. Íevçenka)
MATEMATYÇNE MODELGVANNQ
NIL|POTENTNYX PIDNAPIVHRUP NAPIVHRUP
STYSKUGÇYX PERETVOREN| BULEANA
In this paper, we study mathematical models of the structure of nilpotent subsemigroups of the
semigroup PTD Bn( ) of partial contracting transformations of a Boolean, the semigroup TD Bn( ) of
full contracting transformations of a Boolean, the inverse semigroup ISD Bn( ) of contracting
transformations of a Boolean. We propose a convenient graphical representation of the considered
semigroups. For each of these semigroups, the uniqueness of its maximal nilpotent subsemigroup is
proved. For PTD Bn( ) and TD Bn( ) , the capacity of maximal nilpotent subsemigroup is calculated.
For ISD Bn( ) , estimates of the capacity of maximal nilpotent subsemigroup are obtained and this
capacity is calculated for small n. For all considered semigroups, we describe the structure of nil-
elements and maximal nilpotent subsemigroups of nilpotency degree k and calculate the number of such
elements and subsemigroups for some special cases.
Rabota posvqwena matematyçeskomu modelyrovanyg struktur¥ nyl\potentn¥x podpoluhrupp
poluhrupp¥ PTD Bn( ) sΩymagwyx çastyçn¥x preobrazovanyj buleana, poluhrupp¥ TD Bn( )
sΩymagwyx poln¥x preobrazovanyj buleana, ynversnoj poluhrupp¥ ISD Bn( ) sΩymagwyx
preobrazovanyj buleana. Vvedeno udobnoe hrafyçeskoe yzobraΩenye rassmotrenn¥x polu-
hrupp; dlq kaΩdoj yz nyx dokazana edynstvennost\ maksymal\noj nyl\potentnoj podpoluhrup-
p¥, dlq PTD Bn( ) y TD Bn( ) v¥çyslena ee mownost\, dlq ISD Bn( ) postroen¥ ocenky mow-
nosty maksymal\noj nyl\potentnoj podpoluhrupp¥ y v¥çyslena ee mownost\ dlq mal¥x n.
Dlq vsex ukazann¥x poluhrupp opysana struktura nyl\πlementov y maksymal\n¥x nyl\potent-
n¥x podpoluhrupp klassa nyl\potentnosty k, najdeno kolyçestvo πlementov y podpoluhrupp
dlq nekotor¥x çastn¥x sluçaev.
1. Osnovni ponqttq. Nexaj S — napivhrupa z nul\ovym elementom 0. S nazy-
va[t\sq nil\potentnog, qkwo isnu[ take çyslo k , wo Sk = { }0 . Minimal\ne
take k nazyva[t\sq klasom nil\potentnosti napivhrupy S. MnoΩyna vsix nil\-
potentnyx pidnapivhrup S [ çastkovo vporqdkovanog za vklgçennqm, maksy-
mal\ni elementy ci[] mnoΩyny nazyvagt\sq maksymal\nymy nil\potentnymy
pidnapivhrupamy S [1, 2].
Krim zahal\nyx nil\potentnyx pidnapivhrup rozhlqdagt\ takoΩ nil\potent-
ni pidnapivhrupy fiksovanoho klasu nil\potentnosti. MnoΩyna takyx pidnapiv-
hrup takoΩ [ çastkovo vporqdkovanog, a otΩe, moΩna hovoryty pro maksy-
mal\ni nil\potentni pidnapivhrupy klasu nil\potentnosti k. Dlq podal\ßoho
vykladu nam potribni nastupni tverdΩennq [3].
TverdΩennq 1. Nexaj S — skinçenna napivhrupa. Todi nastupni tverd-
Ωennq ekvivalentni:
1) S [ nil\potentnog;
2) koΩen element a S∈ [ nil\potentnym;
3) [dynym idempotentom S [ nul\ovyj element.
ZauvaΩymo, wo tverdΩennq 1 u vypadku neskinçenno] napivhrupy ne zavΩdy
vykonu[t\sq. Rozhlqnemo, napryklad, napivhrupu T = ( , )n m{ n, m N∈ , 0 < n <
< m} ∪ 0{ } iz mnoΩennqm ( , )( , )n m k l =
( , ), ,
, .
n l m k
m k
qkwo
qkwo
=
≠
0
Lehko baçyty,
wo koΩen element napivhrupy T — nil\element klasu nil\potentnosti 2, ale
sama napivhrupa T ne [ nil\potentnog.
Vidnoßennq Hrina [4] na napivhrupi S oznaçagt\sq takym çynom:
© N. V. SELEZN|OVA, 2009
976 ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, # 7
MATEMATYÇNE MODELGVANNQ NIL|POTENTNYX PIDNAPIVHRUP … 977
aRb aS bS⇔ =1 1 , aLb S a S b⇔ =1 1 , aJb S aS S bS⇔ =1 1 1 1,
H R L= ∩ , D R L= ∨ ,
R ta L [ livog ta pravog konhruenciqmy, reßta vidnoßen\ — vidnoßennqmy
ekvivalentnosti. Nastupna diahrama vidobraΩa[ systemu vklgçen\ miΩ nymy:
.
TverdΩennq 2. Vidnoßennq Hrina na skinçennij nil\potentnij napivhrupi [
tryvial\nymy, tobto zbihagt\sq z vidnoßennqm rivnosti.
Nexaj M — skinçenna mnoΩyna. Rozhlqnemo mnoΩynu ]] peretvoren\, tobto
vidobraΩen\ M u sebe (ne obov’qzkovo vyznaçenyx na vsij mnoΩyni, tobto deqki
toçky M moΩut\ nikudy ne perexodyty). Na oderΩanij mnoΩyni peretvoren\
oznaçymo mnoΩennq takym çynom: qkwo peretvorennq f vidobraΩa[ toçku i v
toçku j, a peretvorennq g — toçku j v toçku k, to peretvorennq f g vido-
braΩa[ toçku i v toçku k. Asociatyvnist\ di] oçevydna, otΩe, ma[mo na-
pivhrupu. Taka napivhrupa nazyva[t\sq napivhrupog peretvoren\ mnoΩyny M.
Viz\memo mnoΩynu 1, ,…{ }n (tobto vsi natural\ni çysla vid 1 do n) i roz-
hlqnemo napivhrupu peretvoren\ ]] buleana (buleanom mnoΩyny nazyvagt\ mno-
Ωynu vsix ]] pidmnoΩyn, dlq mnoΩyny 1, ,…{ }n poznaçatymemo joho Bn ). Se-
red oderΩanyx peretvoren\ vydilymo napivhrupu styskagçyx peretvoren\, tob-
to takyx φ, wo A ∈dom φ fi φ( )A � A. V nij vydilymo try pidnapivhrupy: na-
pivhrupu çastkovyx peretvoren\ PTD Bn( ) , napivhrupu peretvoren\ TD Bn( )
(koΩna toçka obov’qzkovo perexodyt\ v inßu abo v sebe, tobto peretvorennq [
vyznaçenym na vsij mnoΩyni) i napivhrupu inversnyx peretvoren\ ISD Bn( ) (pid-
napivhrupa PTD Bn( ) , wo xarakteryzu[t\sq umovog in’[ktyvnosti, tobto v koΩ-
nu toçku moΩe perejty ne bil\ße odni[] toçky). Same ci try napivhrupy budemo
doslidΩuvaty v danij roboti.
Rozhlqnemo detal\niße strukturu cyx napivhrup. U napivhrupax PTD Bn( ) i
ISD Bn( ) nulem [ nide ne vyznaçene peretvorennq, u TD Bn( ) nulem [ peretvo-
rennq, qke koΩnu mnoΩynu perevodyt\ u ∅. Dali budemo vykorystovuvaty take
hrafiçne zobraΩennq elementa: elementy buleana zobraΩu[mo verßynamy hra-
fa, perexody — strilkamy, pryçomu pry provedenni strilok vraxovu[mo obme-
Ωennq dano] napivhrupy.
.
Navedenyj rysunok ilgstru[ moΩlyvi perexody dlq n = 3. (ZauvaΩymo, wo
pry vybori konkretnoho elementa z odni[] toçky vyxodyt\ ne bil\ße odni[]
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, # 7
978 N. V. SELEZN|OVA
strilky.) V zaleΩnosti vid toho, qka same napivhrupa rozhlqda[t\sq, dodagt\sq
takoΩ umovy, wo zvodqt\sq do naleΩnosti takoho elementa do dano] napivhrupy.
Tak, dlq ISD Bn( ) slid takoΩ vymahaty in’[ktyvnist\ (in’[ktyvnist\ u hrafiç-
nomu zobraΩenni polqha[ v tomu, wo v koΩnu toçku ma[ vxodyty ne bil\ße od-
ni[] strilky); dlq TD Bn( ) potribno vymahaty, wob koΩne peretvorennq bulo
vyznaçenym na vs\omu buleani, tobto wob koΩna toçka perexodyla abo v sebe,
abo v pidmnoΩynu; dlq PTD Bn( ) dodatkovyx umov nema[. OtΩe, moΩna sfor-
mulgvaty ta dovesty nastupni tverdΩennq.
TverdΩennq 3. U napivhrupax PTD Bn( ) ta ISD Bn( ) nil\elementamy [
ti i lyße ti peretvorennq, qki Ωodnu toçku (element buleana) ne perevodqt\
samu v sebe.
Dovedennq. Oçevydno, wo nil\element ne moΩe perevodyty toçku buleana
samu v sebe, tomu wo pry pidnesenni do dovil\noho stepenq cq petlq zbere-
Ωet\sq.
OtΩe, zalyßylos\ pokazaty, wo opysani elementy dijsno [ nil\elementamy.
Ce tak zavdqky tomu, wo qkwo Ωodna toçka ne perexodyt\ u sebe, to vona pe-
rexodyt\ u svog pidmnoΩynu, qka v svog çerhu takoΩ perexodyt\ u svog pid-
mnoΩynu, i tak dali, a oskil\ky lancgh pidmnoΩyn [ skinçennym, to v qkomus\
stepeni otryma[mo nide ne vyznaçene peretvorennq.
TverdΩennq 4. U napivhrupi TD Bn( ) nil\elementamy [ ti i lyße ti pe-
retvorennq, qki Ωodnu toçku (element buleana), krim toçky „poroΩnq mno-
Ωyna” (poznaça[mo ∅), ne perevodqt\ samu v sebe.
Dovedennq. Oçevydno, wo nil\element ne moΩe perevodyty toçku buleana
samu v sebe (qkwo ce ne ∅ ), oskil\ky pry pidnesenni do dovil\noho stepenq cq
petlq zbereΩet\sq.
OtΩe, zalyßylos\ pokazaty, wo opysani elementy dijsno [ nil\elementamy.
Ce tak tomu, wo qkwo Ωodna toçka ne perexodyt\ u sebe, to vona perexodyt\
u svog pidmnoΩynu, qka v svog çerhu takoΩ perexodyt\ u svog pidmnoΩynu, a
lancgh pidmnoΩyn [ skinçennym, otΩe, v qkomus\ stepeni oderΩymo perexid
toçky v ∅, i tak dlq vsix toçok peretvorennq.
U hrafiçnomu zobraΩenni verßyny zruçno rozmiwaty rivnqmy — vid nul\o-
voho do n-ho (zverxu vnyz). Todi dlq nil\elementiv strilky moΩut\ buty na-
pravleni lyße vnyz po rivnqx (z uraxuvannqm toho, wo verßyna moΩe perexody-
ty lyße u taku verßynu, qka vidpovida[ ]] pidmnoΩyni).
2. Maksymal\ni nil\potentni pidnapivhrupy.
TverdΩennq 5. U napivhrupax PTD Bn( ) , TD Bn( ) ta ISD Bn( ) maksy-
mal\na nil\potentna pidnapivhrupa [ [dynog, sklada[t\sq iz vsix nil\elemen-
tiv vidpovidno] napivhrupy i ma[ porqdok nil\potentnosti n + 1 dlq PTD Bn( )
i ISD Bn( ) ta n dlq TD Bn( ) .
Dovedennq. Ne nil\potentnyj element do maksymal\no] nil\potentno] pid-
napivhrupy naleΩaty ne moΩe.
Maksymal\na nil\potentna pidnapivhrupa v danomu vypadku [ [dynog, tomu
wo dlq vsix navedenyx napivhrup mnoΩyny nil\elementiv utvorggt\ napiv-
hrupu.
Skorysta[mosq tverdΩennqmy 3 ta 4, qki dagt\ xarakteryzacig nil\elemen-
tiv. Oçevydno, wo opysani vlastyvosti pry mnoΩenni zberihagt\sq.
Zalyßylosq vyznaçyty porqdok. U koΩnij iz rozhlqnutyx napivhrup ele-
ment, wo dorivng[ dobutku dvox nil\elementiv, ne moΩe mistyty perexodiv u
toçky perßoho rivnq, inakße perßyj spivmnoΩnyk mav by mistyty perexid u
toçku nul\ovoho rivnq, a dlq nil\elementiv ce nemoΩlyvo; toçka i -ho rivnq mo-
Ωe perexodyty v toçku (i + 2)-ho rivnq abo nyΩçe (za vynqtkom perexodu v ∅
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, #7
MATEMATYÇNE MODELGVANNQ NIL|POTENTNYX PIDNAPIVHRUP … 979
dlq TD Bn( ) za raxunok toho, wo v nil\elementiv ci[] napivhrupy [ petlq ∅P→
→ ∅).
Analohiçno dobutok tr\ox nil\elementiv ne moΩe mistyty perexodiv u toçky
perßoho ta druhoho rivniv, vodnoças toçka i -ho rivnq moΩe perexodyty v toçku
(i + 3)-ho rivnq abo nyΩçe (za vynqtkom perexodu v ∅ dlq TD Bn( ) ).
ProdovΩugçy ci mirkuvannq, perekonu[mosq, wo dobutok n nil\elementiv
ne moΩe mistyty perexodiv u toçky rivnq, menßoho za n , do toho Ω dlq
PTD Bn( ) ta ISD Bn( ) Ωodna toçka ne moΩe perejty ni na odyn riven\ (krim
toçky 1, ,…{ }n , qka moΩe perejty lyße v ∅), a dlq TD Bn( ) [dynym dozvo-
lenym perexodom [ perexid v ∅ . Dlq PTD Bn( ) ta ISD Bn( ) ce oznaça[, wo v
rezul\tati dobutku n + 1 elementiv ma[mo nide ne vyznaçene peretvorennq, tob-
to nul\ napivhrupy; dlq TD Bn( ) v rezul\tati dobutku n elementiv ma[mo pere-
xid vsix toçok v ∅, tobto nul\ napivhrupy TD Bn( ) .
Menßym stepin\ nil\potentnosti maksymal\no] nil\potentno] pidnapivhrupy
buty ne moΩe, tomu wo u PTD Bn( ) ta ISD Bn( ) isnu[ element stepenq n + 1,
ce, napryklad, lancgh 1, ,…{ }n → 1 1, ,… −{ }n → … → 1{ } → ∅, a v TD Bn( )
— element stepenq n, cej Ωe lancgh, dopovnenyj perexodamy v ∅ vsix neza-
diqnyx toçok.
TverdΩennq 6. Maksymal\na nil\potentna pidnapivhrupa PTD Bn( ) mis-
tyt\ rivno 2 2 1n n⋅ −
elementiv.
Dovedennq. Vs\oho ma[mo 2n verßyn, deqki z nyx potribno z’[dnaty rebra-
my, vraxuvavßy obmeΩennq na strukturu napivhrupy.
Dlq verßyny nul\ovoho rivnq, wo mistyt\ n elementiv, [ vs\oho 2n varian-
tiv : 2 1n − variant perexodu v inßu verßynu ta odyn variant, koly vona nikudy
ne perexodyt\.
Verßyn perßoho rivnq (tobto tyx, wo mistqt\ po (n – 1)-mu elementu 1{ , …
…, n} koΩna) vs\oho
n
1
i dlq koΩno] [ 2 11n− − variant perexodu v inßu
verßynu ta odyn variant ne perejty nikudy, vs\oho 2 1n− variantiv.
Mirkugçy analohiçno dlq verßyn k-ho rivnq, tobto tyx, wo mistqt\ n – k
elementiv (pry takij numeraci] „perßu” verßynu slid nazyvaty verßynog nu-
l\ovoho rivnq), znaxodymo toçno
n
k
verßyn, dlq koΩno] z qkyx [ 2n k− va-
riantiv. Dlq ostann\oho, n-ho, rivnq isnu[ odna verßyna, wo mistyt\ 0 elemen-
tiv (tobto ∅) i ma[ toçno 2 1n n− = variant nikudy ne perexodyty. Dlq koΩno]
verßyny perexid obyravsq nezaleΩno, otΩe, za pravylom kombinatornoho mno-
Ωennq zalyßa[t\sq peremnoΩyty oderΩani rezul\taty. Ma[mo
2 2 2 20
1
1
n n n n n n n
n
−
−
⋅ … =
( ) ( ) (nn i n
i
n n
i ni
n
i
n−
−
⋅= =
−∑
=
∑
=
)0 0
1
2 2
1
2nn−1
.
TverdΩennq dovedeno.
TverdΩennq 7. Maksymal\na nil\potentna pidnapivhrupa TD Bn( ) mis-
tyt\ toçno 2 1
0
n k
n
k
k
n − ( )
= −( )∏ elementiv.
Dovedennq analohiçne dovedenng poperedn\oho tverdΩennq, ale na koΩ-
nomu kroci neobxidno vyluçyty variant „nikudy ne perexodyt\”. Tomu na k - mu
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, # 7
980 N. V. SELEZN|OVA
rivni ma[mo
n
k
verßyn, dlq koΩno] z qkyx [ 2 1n k− − variant, i ostatoçna
formula nabyra[ vyhlqdu 2 1
0
n k
n
k
k
n −
= −( )∏ .
U vypadku napivhrupy ISD Bn( ) sytuaciq dewo skladnißa, tomu wo çerez
in’[ktyvnist\ vybir perexodiv dlq koΩno] verßyny vΩe ne [ nezaleΩnym. Dlq
toho wob vykonaty obçyslennq xoça b dlq malyx n, bulo napysano prohramu na
Delphy na osnovi alhorytmu pereboru z povernennqmy. Ale çerez dosyt\ rizkyj
rist potuΩnosti nil\potentno] pidnapivhrupy pry zrostanni n prohramnyj pid-
xid ne [ efektyvnym.
Tak, pry n =1 ma[mo 2 nil\elementy: 0 (tobto nide ne vyznaçene peretvoren-
nq) ta 1{ } → ∅. Pry n = 2 takyx elementiv 10:
Pry n = 3 takyx elementiv 540 (iz zrozumilyx pryçyn spysok ne navodyt\sq), a
pry n = 4 ]x 6687168.
Alhorytm pidraxunku elementiv [ pereborom z povernennqmy. Verßyny hra-
fa (elementy buleana) numerugt\sq vid 0 do 2 1n − , pryçomu vidtvoryty samu
pidmnoΩynu za nomerom dosyt\ prosto — ce taka pidmnoΩyna 1, ,…{ }n , do
qko] vxodqt\ ti çysla, wo vidpovidagt\ pozyciqm odynyc\ u dvijkovomu zapysi
nomera verßyny. OtΩe, moΩna ne zberihaty nabir verßyn hrafa u masyvi, wo
znaçno sprowu[ robotu prohramy.
Spoçatku stvorg[t\sq masyv dopustymyx perexodiv — ce dvovymirnyj masyv
rozmirnosti 2 2n n× . Na ( , )i j -mu misci sto]t\ 1, qkwo verßyna i moΩe pere-
jty v verßynu j, i 0, qkwo ne moΩe.
Dali cej masyv kopig[t\sq v potoçnyj masyv i zapuska[t\sq osnovnyj cykl:
heneraciq elementa po potoçnomu masyvu, joho vyvid na ekran (i dodavannq ody-
nyci do zahal\no] pidraxovano] kil\kosti), zmina potoçnoho masyvu („krok nazad”
dlq i = 1).
Heneraciq elementa po potoçnomu masyvu vidbuva[t\sq takym çynom: vyby-
ra[mo iz moΩlyvyx variantiv perexodu dlq 2 1n − verßyny (vidpovida[ mnoΩyni
1, ,…{ }n ). Dali pomiça[mo dlq vsix inßyx verßyn fakt nemoΩlyvosti perejty
tudy Ω (dlq toho, wob vykonuvalas\ in’[ktyvnist\). Povtorg[mo cg poslidov-
nist\ (vybir i in’[ktyvnist\) dlq vsix verßyn. Qkwo dlq qko]s\ verßyny varian-
tiv nema[, vona pomiça[t\sq qk taka, wo nikudy ne perexodyt\.
Krok nazad vidbuva[t\sq takym çynom: rozhlqda[mo verßynu pid nomerom i.
Qkwo vona kudys\ perexodyla, to pomiça[mo cej perexid qk vidprac\ovanyj i,
zvirqgçys\ z masyvom dopustymyx perexodiv (zhenerovanym na poçatku roboty
prohramy), pomiça[mo vsi moΩlyvi perexody v tu verßynu, kudy perexodyla i, qk
znovu dopustymi, a takoΩ prybyra[mo vsi pomitky pro vidprac\ovanist\ variantiv
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, #7
MATEMATYÇNE MODELGVANNQ NIL|POTENTNYX PIDNAPIVHRUP … 981
dlq tyx verßyn, çyj nomer menßyj za i. Qkwo Ω i-ta verßyna nikudy ne
perexodyla (ce oznaça[, wo vsi moΩlyvi varianty dlq ne] za umovy danoho vyboru
verßyn z nomeramy, bil\ßymy za i, vidprac\ovano), to robymo krok nazad dlq
verßyny z nomerom i + 1.
Prohrama zaverßu[ robotu pry neobxidnosti zrobyty krok nazad z verßyny z
nomerom 2 1n − , i ostannij element, zhenerovanyj prohramog, — nide ne vyzna-
çene vidnoßennq.
Zdavalos\ by, bil\ß oçevydnyj ßlqx zbereΩennq elementa u vyhlqdi odno-
vymirnoho masyvu robotu prohramy ne pryßvydßu[, oskil\ky vynyka[ neobxid-
nist\ u dodatkovyx perevirkax in’[ktyvnosti.
MoΩna ocinyty ßukanu potuΩnist\ zverxu ta znyzu. Ocinyty zverxu moΩna
xoça b potuΩnistg PTD Bn( ) .
Pobudu[mo inßyj variant ocinky.
Dopovnymo çastkovyj porqdok na buleani do linijnoho (napryklad, vvivßy
dodatkovo linijnyj porqdok na koΩnomu rivni). Todi ma[mo 2n toçok i rozhlq-
da[mo in’[ktyvni çastkovi peretvorennq. MnoΩennq peretvoren\ [ standartnym.
Todi ma[mo napivhrupu IS n2 ; ISD Bn( ) [ pidnapivhrupog tako] napivhrupy.
Nuli napivhrup zbihagt\sq, a otΩe, zbihagt\sq i ponqttq nil\potentnosti.
TverdΩennq 8. Dlq koΩnoho idempotenta e E ISm∈ ( ) takoho, wo def ( )e =
= k, napivhrupa ISm mistyt\ toçno k! maksymal\nyx nil\potentnyx pid-
napivhrup, wo mistqt\ e ( i takyx, wo e [ nul\ovym elementom). Vsi taki
nil\potentni pidnapivhrupy [ izomorfnymy, ]xnij stepin\ nil\potentnosti do-
rivng[ k, a potuΩnist\ dorivng[ k-mu çyslu Bela Blk .
ZauvaΩymo, wo dlq çysel Bela [5], qk pravylo, vykorystovu[t\sq poznaçen-
nq Bk , ale tut ]x poznaça[mo inakße, wob ne plutaty z buleanom.
U danomu vypadku nas cikavyt\ maksymal\na nil\potentna pidnapivhrupa z
idempotentom 0, tobto nide ne vyznaçenym peretvorennqm. Defekt takoho pe-
retvorennq u danomu vypadku dorivng[ 2n
.
OtΩe, ßukana ocinka matyme vyhlqd
Bl
2
0
2
1
1n S k
k
k
i
k in i
i
k
n= ( ) = −
−
=
∑,
!
( ) ( )
==
∑∑
kk
nn
0
2
0
2
.
Ocinyty znyzu moΩna pidraxuvavßy kil\kist\ „odnolancghovyx” nil\ele-
mentiv IS Bn( ) , tobto takyx, wo skladagt\sq z odnoho lancgha (dyv. rysunok).
.
Wob oderΩaty lancgh dovΩyny n, potribno na koΩnomu rivni vybraty odnu
iz dopustymyx toçok.
Na nul\ovomu rivni vybir odnoznaçnyj, oskil\ky na n\omu vs\oho odna toçka.
Na perßomu rivni moΩna vybraty odnu iz n toçok. Pislq takoho vyboru na
druhomu rivni moΩna vybraty odnu iz n – 1 toçky (wob moΩna bulo u ne] pere-
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, # 7
982 N. V. SELEZN|OVA
jty), na tret\omu rivni — vΩe odnu z n – 2 toçok i t.Pd. Na n -mu rivni, wo vid-
povida[ odnotoçkovym mnoΩynam, vybir znovu odnoznaçnyj — ∅. OtΩe, ma[mo
vs\oho n! lancghiv dovΩyny n.
Dali rozhlqnemo taki elementy, qki moΩna otrymaty iz lancghiv dovΩyny n,
vykreslyvßy i-j riven\ i zaminyvßy vidpovidnyj perexid çerez toçku prqmym
rebrom (po çerzi dlq vsix i vid 1 do n; dlq perßoho ta ostann\oho rivniv ce
styrannq vidpovidnoho rebra) . Oskil\ky na koΩnomu kroci my otrymu[mo odyn i
toj Ωe element i raziv (tomu wo v koΩnu toçku (i + 1)-ho rivnq moΩna pryjty
iz i toçok i-ho rivnq), ]x bude toçno
n
ii
n !
=∑ 1
+ n! (ostannij dodanok vidpovida[
vykreslenng toçky ∅). Qkwo vykreslyty rivni i ta j, to budemo maty
n
i j
!
elementiv, qkwo i, j < n + 1, ta
n
i
!
, qkwo vykresleno ∅. Vidpovidno pry vy-
kreslgvanni k rivniv ma[mo
n
j jkj j n
j j
k
t r
!
, , 111
…… ∈ …{ }
≠
∑ +
n
j jkj j n
j j
k
t r
!
, , 1 111 1
… −… ∈ …{ }
≠
−
∑
elementiv. Ostatoçno otrymu[mo
n
n
j j
n
j jkj j n
j j
kj jk
t r
!
! !
, ,
+
…
+
…… ∈ …{ }
≠
−…
∑
11 1 11 1 kk
t r
n
j j
k
n
− ∈ …{ }
≠
=
−
∑∑
1 11
1
, ,
elementiv.
Pry n = 2 ma[mo 7 elementiv, pry n = 3 — 40, pry n = 4 — 224.
3. Nil\potentnist\ klasu k. Nil\elementy klasu k u danyx napivhrupax
opysugt\sq odnakovo — ce taki nil\elementy napivhrupy, u hrafiçnomu zobra-
Ωenni qkyx maksymal\nyj lancgh ma[ dovΩynu toçno k, za vynqtkom petli na
∅ dlq TD Bn( ) (tobto z qko] b toçky my ne poçaly ruxatys\ po strilkax, nam
ne vdast\sq zrobyty bil\ße niΩ k perexodiv, i isnu[ xoça b odna toçka, z qko]
poçyna[t\sq ßlqx dovΩynog toçno k strilok).
TverdΩennq 9. U napivhrupax PTD Bn( ) ta ISD Bn( ) koΩna maksymal\na
nil\potentna pidnapivhrupa klasu k zada[ rozbyttq Bn na k pidmnoΩyn
M M k0 1, ,… − take, wo dlq bud\-qkyx i, j, j < i, A Mi∈ , isnu[ B M j∈ ta-
ke, wo A B⊂ , tobto dlq bud\-qkyx dvox klasiv i dlq bud\-qko] mnoΩyny kla-
su z bil\ßym nomerom znajdet\sq taka mnoΩyna z klasu z menßym nomerom, wo
moΩe perejty v ne]. KoΩnomu takomu rozbyttg vidpovida[ maksymal\na nil\-
potentna pidnapivhrupa klasu nil\potentnosti k.
Dovedennq. ZauvaΩymo, wo pry takyx rozbyttqx toçka 1 2, , ,…{ }n zavΩdy
naleΩyt\ do M 0 , a toçka ∅ — do M k .
Vidpovidnist\ taka: verßyny moΩut\ perexodyty lyße v nastupnu za porqd-
kom mnoΩynu, tobto qkwo a Mi∈ , to perexodyty vona moΩe lyße v toçky
Mj , j > i. Oçevydno, wo vsi elementy, pobudovani za cym pravylom (vraxovugçy
obmeΩennq napivhrupy, tobto perexid toçky lyße u svog pidmnoΩynu ta in’[k-
tyvnist\ dlq IS Bn( ) ), utvorggt\ napivhrupu.
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, #7
MATEMATYÇNE MODELGVANNQ NIL|POTENTNYX PIDNAPIVHRUP … 983
Rozbyttq za pidnapivhrupog budu[t\sq z çastkovoho porqdku, zadanoho ci[g
pidnapivhrupog. Oskil\ky pidnapivhrupa maksymal\na, to izol\ovanyx toçok ne-
ma[. Ma[mo same k mnoΩyn, tomu wo stepin\ nil\potentnosti pidnapivhrupy k.
Qkby bulo bil\ße mnoΩyn, to moΩna bulo b pobuduvaty element stepenq nil\-
potentnosti bil\ßoho niΩ k. Qkby mnoΩyn bulo menße, to stepin\ nil\potent-
nosti pidnapivhrupy buv by menßym. Spravdi, pry mnoΩenni bud\-qkyx dvox ele-
mentiv takym çynom pobudovano] napivhrupy u elementa-dobutku vΩe ne bude pe-
rexodiv u klas M1 (xoça b tomu, wo perexodiv u klas M 0 nema[ ni v odnoho
elementa pidnapivhrupy). Analohiçno pry mnoΩenni bud\-qkyx tr\ox elementiv
ne bude perexodiv ni v M1 , ni v M 2 i t.Pd.
Zalyßylos\ dovesty maksymal\nist\ pidnapivhrupy, pobudovano] za rozbyt-
tqm, u klasi nil\potentnyx pidnapivhrup stepenq nil\potentnosti k. Nexaj da-
nomu rozbyttg M M k0 1, ,… − vidpovida[ pidnapivhrupa S1 stepenq nil\potent-
nosti k i isnu[ nil\potentna pidnapivhrupa S2 stepenq nil\potentnosti k ta-
ka, wo S S1 2⊂ . Nexaj ]j vidpovida[ rozbyttq N Nk0 1, ,… − . Oskil\ky S1 —
pidnapivhrupa, to dlq bud\-qkoho i M Ni i⊆ . Zavdqky skinçennosti Bn dani
rozbyttq, a otΩe, i vidpovidni napivhrupy zbihagt\sq.
TverdΩennq 10. U napivhrupi TD Bn( ) koΩna maksymal\na nil\potentna
pidnapivhrupa klasu k zada[ rozbyttq Bn na k pidmnoΩyn M M k0 1, ,… −
take, wo dlq bud\-qkyx i, j, j < i, A Mi∈ isnu[ B M j∈ take, wo A B⊂ ,
tobto dlq bud\-qkyx dvox fiksovanyx klasiv i bud\-qko] mnoΩyny klasu z bil\-
ßym nomerom znajdet\sq taka mnoΩyna z druhoho klasu (z menßym nomerom),
qka moΩe perejty v ne]; do toho Ω mnoΩyna M k−1 skladalasq ne lyße z ∅.
KoΩnomu takomu rozbyttg vidpovida[ maksymal\na nil\potentna pidnapiv-
hrupa klasu nil\potentnosti k.
Dovedennq analohiçne dovedenng tverdΩennq 9. Vidminnist\ polqha[ v tomu,
wo krim perexodiv miΩ klasamy koΩna toçka moΩe perejty v ∅. Same z cym
pov’qzano vymohu, wob ostannij klas mistyv we xoça b odnu toçku, inakße fak-
tyçno oderΩymo nil\potentnu pidnapivhrupu stepenq nil\potentnosti k – 1.
4. Maksymal\ni nil\potentni pidnapivhrupy malyx stepeniv. Qk pokaza-
no u poperedn\omu punkti, koΩnij maksymal\nij nil\potentnij pidnapivhrupi
doslidΩuvanyx napivhrup vidpovida[ rozbyttq buleana special\noho vyhlqdu. V
zahal\nomu vypadku zadaça pidraxunku kil\kosti takyx rozbyttiv, a takoΩ po-
tuΩnosti vidpovidnyx pidnapivhrup [ dosyt\ skladnog, ale dlq deqkyx çastko-
vyx vypadkiv moΩna navesty taki rezul\taty.
Najprostißym [ vypadok k = 2, tobto nil\potentni pidnapivhrupy z 0-mno-
Ωennqm. U c\omu vypadku dlq PTD Bn( ) ta ISD Bn( ) moΩna braty dovil\ni
rozbyttq buleana na dvi mnoΩyny taki, wo verßyna 1, ,…{ }n naleΩyt\ do M 0 ,
a verßyna ∅ — do M1 . Vs\oho takyx rozbyttiv (a vidpovidno i maksymal\nyx
nil\potentnyx pidnapivhrup) bude 22 2n −
(koΩna toçka buleana, krim dvox
fiksovanyx vywe, perexodyt\ nezaleΩno v odnu iz mnoΩyn). Zrozumilo, wo
potuΩnist\ vidpovidno] pidnapivhrupy zaleΩyt\ vid rozbyttq, pryçomu ne til\ky
vid potuΩnostej vidpovidnyx pidmnoΩyn, a i vid toho, qki konkretno toçky
potrapyly u koΩnu iz mnoΩyn danoho rozbyttq.
Dlq TD Bn( ) mirkuvannq taki sami, ale odyn variant (toj, koly M1 skla-
da[t\sq lyße z ∅) neobxidno vidkynuty. Takym çynom, ma[mo 2 12 2n − − pidna-
pivhrupu.
Dlq prykladu rozpyßemo taki rozbyttq i vidpovidni elementy pry n = 2:
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, # 7
984 N. V. SELEZN|OVA
PTD Bn( ) :
TD Bn( ) :
ISD Bn( ) :
Vypadok k = 3 takoΩ [ prostym: mnoΩyna M 0 mistyt\ mnoΩynu 1, ,…{ }n ,
mnoΩyna M 2 mistyt\ ∅, a qkwo ma[mo TD Bn( ) , to mnoΩyna M 2 mistyt\
we xoça b odnu toçku. Todi na mnoΩynu M1 obmeΩen\ nema[. Vidpovidno dlq
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, #7
MATEMATYÇNE MODELGVANNQ NIL|POTENTNYX PIDNAPIVHRUP … 985
PTD Bn( ) i ISD Bn( ) ma[mo po 32 2n −
nil\potentnyx pidnapivhrup klasu nil\-
potentnosti 3, dlq TD Bn( ) — 32 2n − – 22 2n −
(vidkyda[mo ti pidnapivhrupy, wo
vidpovidagt\ takym rozbyttqm, v qkyx M 2 sklada[t\sq lyße z ∅).
Dlq bil\ßyx k sytuaciq uskladng[t\sq — potribno vidslidkovuvaty vyko-
nannq osnovno] umovy na klasy rozbyttq, tobto moΩlyvist\ perexodu v toçku,
wo naleΩyt\ klasu z bil\ßym nomerom.
U vypadku k = n + 1 dlq napivhrup PTD Bn( ) i ISD Bn( ) sytuaciq znovu
sprowu[t\sq — tut take rozbyttq [dyne, a same, rozbyttq za rivnqmy. Dlq k = n
i TD Bn( ) sytuaciq cilkom analohiçna, rozbyttq vidbuva[t\sq za rivnqmy, a do
M k−1 naleΩyt\ i peredostannij riven\, i ∅. U cyx vypadkax oderΩu[mo maksy-
mal\nu nil\potentnu pidnapivhrupu vidpovidno] napivhrupy.
1. Klyfford A., Preston H. Alhebrayçeskaq teoryq poluhrupp. – M.: Myr, 1972. – T 1. –
283Ps.
2. Selezn\ova N. V. Zv’qzok miΩ nil\potentnistg v BN i acykliçnymy hrafamy // Dvanadcqta
miΩnar. nauk. konf. im. akad. M. Kravçuka (15 – 17 travnq 2008 r.). – Ky]v, 2008. – Ç. 1. –
S.P783.
3. Ganyushkin O., Mazorchuk V. On classification of maximal nilpotent subsemigroups. – 2005. –
16 p. – Preprint # 37, Uppsala Univ.
4. Lalleman Û. Poluhrupp¥ y kombynatorn¥e pryloΩenyq. – M.: Myr, 1985. – 440 s.
5. Ganyushkin O., Mazorchuk V. Combinatorics of nilpotents in ISn // Ann. Combinat. – 2004. – 8.
– P. 161 – 175.
OderΩano 26.08.08,
pislq doopracgvannq — 03.04.09
ISSN 1027-3190. Ukr. mat. Ωurn., 2009, t. 61, # 7
|
| id | umjimathkievua-article-3072 |
| institution | Ukrains’kyi Matematychnyi Zhurnal |
| keywords_txt_mv | keywords |
| language | Ukrainian English |
| last_indexed | 2026-03-24T02:35:42Z |
| publishDate | 2009 |
| publisher | Institute of Mathematics, NAS of Ukraine |
| record_format | ojs |
| resource_txt_mv | umjimathkievua/1c/26b57f44bf5252774eb2536204ad141c.pdf |
| spelling | umjimathkievua-article-30722020-03-18T19:44:40Z Mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a Boolean Математичне моделювання нільпотентних піднапівгруп напівгруп стискуючих перетворень Булеана Selezneva, N. V. Селезньова, Н. В. We study mathematical models of the structure of nilpotent subsemigroups of the semigroup $PTD(B_n)$ of partial contracting transformations of a Boolean, the semigroup $TD(B_n)$ of full contracting transformations of a Boolean, and the inverse semigroup $ISD(B_n)$ of contracting transformations of a Boolean. We propose a convenient graphical representation of the semigroups considered. For each of these semigroups, the uniqueness of its maximal nilpotent subsemigroup is proved. For $PTD(B_n)$ and $TD(B_n)$, the capacity of a maximal nilpotent subsemigroup is calculated. For $ISD(B_n)$, we construct estimates for the capacity of a maximal nilpotent subsemigroup and calculate this capacity for small $n$. For all indicated semigroups, we describe the structure of nilelements and maximal nilpotent subsemigroups of nilpotency degree $k$ and determine the number of elements and subsemigroups for some special cases. Работа посвящена математическому моделированию структуры нильпотентных подполугрупп полугруппы $PTD(B_n)$ сжимающих частичных преобразований булеана, полугруппы $TD(B_n)$ сжимающих полных преобразований булеана, инверсной полугруппы $ISD(B_n)$ сжимающих преобразований булеана. Введено удобное графическое изображение рассмотренных полугрупп; для каждой из них доказана единственность максимальной нильпотентной подполугруппы, для $PTD(B_n)$ и $TD(B_n)$ вычислена ее мощность, для $ISD(B_n)$ построены оценки мощности максимальной нильпотентной подполугруппы и вычислена ее мощность для малых $n$. Для всех указанных полугрупп описана структура нильэлементов и максимальных нильпотентных подполугрупп класса нильпотентности $k$, найдено количество элементов и подполугрупп для некоторых частных случаев. Institute of Mathematics, NAS of Ukraine 2009-07-25 Article Article application/pdf https://umj.imath.kiev.ua/index.php/umj/article/view/3072 Ukrains’kyi Matematychnyi Zhurnal; Vol. 61 No. 7 (2009); 976-985 Український математичний журнал; Том 61 № 7 (2009); 976-985 1027-3190 uk en https://umj.imath.kiev.ua/index.php/umj/article/view/3072/2893 https://umj.imath.kiev.ua/index.php/umj/article/view/3072/2894 Copyright (c) 2009 Selezneva N. V. |
| spellingShingle | Selezneva, N. V. Селезньова, Н. В. Mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a Boolean |
| title | Mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a Boolean |
| title_alt | Математичне моделювання нільпотентних піднапівгруп напівгруп стискуючих перетворень Булеана |
| title_full | Mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a Boolean |
| title_fullStr | Mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a Boolean |
| title_full_unstemmed | Mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a Boolean |
| title_short | Mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a Boolean |
| title_sort | mathematical modeling of nilpotent subsemigroups of semigroups of contracting transformations of a boolean |
| url | https://umj.imath.kiev.ua/index.php/umj/article/view/3072 |
| work_keys_str_mv | AT seleznevanv mathematicalmodelingofnilpotentsubsemigroupsofsemigroupsofcontractingtransformationsofaboolean AT seleznʹovanv mathematicalmodelingofnilpotentsubsemigroupsofsemigroupsofcontractingtransformationsofaboolean AT seleznevanv matematičnemodelûvannânílʹpotentnihpídnapívgrupnapívgrupstiskuûčihperetvorenʹbuleana AT seleznʹovanv matematičnemodelûvannânílʹpotentnihpídnapívgrupnapívgrupstiskuûčihperetvorenʹbuleana |