Czułość funkcji logicznych (I)

Najpierw jednak spróbujmy wyjaśnić, dlaczego poważni specjaliści chcieli w ogóle rozważać tak (pozornie) niepoważne zagadnienie...

Zacznijmy od dwóch powiązanych pytań:

Czy pięć mrówek może zająć pięć różnych wierzchołków sześcianu w taki sposób, by każda miała najwyżej jedną sąsiadkę (powiemy, że mrówki sąsiadują, gdy siedzą na końcach pewnej krawędzi sześcianu)?
Czy pięć mrówek może zająć pięć różnych wierzchołków sześcianu w taki sposób, by każda miała najwyżej dwie sąsiadki?

Czytelnik, który bez trudu rozprawił się z tymi zagadkami, zdziwi się zapewne, że rozwiązanie tego problemu (co prawda nie tylko dla zwykłej trójwymiarowej kostki, ale w dowolnie wielu wymiarach, o czym później), przedstawione przez Hao Huanga w lipcu 2019 roku, zostało przez społeczność informatyków-teoretyków przyjęte z niemałym entuzjazmem jako rozstrzygnięcie ważnej hipotezy, postawionej prawie 30 lat wcześniej.

Najpierw jednak spróbujmy wyjaśnić, dlaczego poważni specjaliści chcieli w ogóle rozważać tak (pozornie) niepoważne zagadnienie.

Funkcje boolowskie

W klasycznej logice rozważa się zdania, którym przypisuje się wartości logiczne "prawda" lub "fałsz", oraz operatory logiczne, z których najczęściej używane widnieją obok. Zauważmy, że używanie liczb zamiast wartości logicznych (najczęstsze jest utożsamianie prawdy z jednością, a fałszu z zerem) może znacznie uprościć zapis. Zamiast mówić: koniunkcja $p ∧q$ (czytaj " $p$ i $|q$ ") to zdanie, które jest prawdziwe, gdy oba jego człony są prawdziwe, fałszywe zaś w każdym innym przypadku, wystarczy napisać " $| p∧ q = pq$ ".

Ogólnie mówiąc, $|n$ -argumentową funkcją boolowską (lub logiczną) będziemy nazywali każdą funkcję $| n f {prawda, fałsz} {prawda,fałsz}.$ Mówiąc nie wiem, czy zdążę dziś pójść na (p)ocztę, do (s)klepu i naprawić (r)ower, ale chcę zrobić chociaż dwie z tych rzeczy, możemy zapisać funkcję logiczną opisującą, czy ten plan został wykonany:

w1(p,

Analogiczny zapis możemy zastosować do każdej funkcji boolowskiej - po prostu spośród wszystkich $n 2$ układów wartości logicznych argumentów wybieramy te, dla których nasze zdanie złożone jest prawdziwe. Czasami jednak funkcję można zapisać krócej, np. tak:

w2(p,

uwzględniając, że zbiór ${p, r,s}$ ma trzy dwuelementowe podzbiory, lub tak:

w3(p,

co nawet można dość zrozumiale wypowiedzieć: zajrzę na pocztę lub do sklepu, ale jeśli nie naprawię roweru, to pójdę i tu, i tu. (Czy dla Czytelnika jest oczywiste, że to sformułowanie jest równoważne poprzedniemu? Dla autora nie całkiem, za każdym razem musi się on chwilę zastanowić.)

Skąd jednak wiadomo, że to rzeczywiście ciągle ta sama funkcja logiczna, czyli że formuły $w1,$ i $|w3$ są faktycznie równoważne? Z pewnością można podstawić po kolei wszystkie $23 | = 8$ układów wartości zmiennych $|p,r,s$ należących do {0,1} i sprawdzić, czy dla każdej z formuł dostajemy jednakowe wyniki. Inny sposób wykorzystuje przedstawione wyżej na marginesie algebraiczne definicje operatorów logicznych. Na przykład

(¬q ¬ p) = 1 −(1− q) + (1− q)(1− p) = 1 −p + pq = (p q),

a zatem zdania $(p q)$ i $(¬q ¬p)$ są równoważne. Podobnie wyznaczymy

$(p (q ∧ r)) = 1− p+ pqr, 2 ((p q) ∧(p r)) = (1 −p + pq)(1− p + pr) = 1 +p(q + r− 2) +p (1− q− r+ qr).$

Tym razem wydaje się, że mamy różne wyniki. Zauważmy jednak, że dla

|p∈ {0,1}

zachodzi

|p2 = p,

czyli

2 1+p(q+r − 2)+p (1−q −r+qr) = 1+p(q+r − 2)+p(1− q−r+qr) = 1−p+pqr.

Zatem i tym razem mamy do czynienia z równoważnością

(p (q ∧ r)) ((p q)∧ (p r)).

Cierpliwy Czytelnik lub odpowiednio zaprogramowany komputer może wyznaczyć wielomiany odpowiadające wyrażeniom $w$ i $w$ i stwierdzić, że wszystkie one są równe $w(p,$ a to dowodzi równoważności tych wyrażeń.

Dzięki redukcjom typu $p2 = p$ każda $n$ -argumentowa funkcja boolowska może być zapisana w postaci wielomianu $n$ zmiennych, w którym nie występują wykładniki większe od 1. Różne wielomiany nie mogą definiować tej samej funkcji boolowskiej - wynika to z ogólnych własności wielomianów. Przez stopień funkcji boolowskiej, oznaczany przez $|deg( f ),$ będziemy rozumieć stopień jej wielomianu, na przykład $deg(p ∧ q) = 2,$ $|deg(p ∨q ∨ r) = 3,deg(w(p,$

Czułość funkcji boolowskich

Starając się o kredyt, pan Kowalski rzetelnie wypełnił kwestionariusz z setką pytań. Otrzymał decyzję odmowną - bankowy analityk wyjaśnił swojemu przełożonemu, że odpowiedzi na pytania 14, 58 i 83 wskazują na skłonność klienta do nadmiernych wydatków. Pan Kowalski nigdy się jednak nie dowie, że dostałby kredyt, wystarczyłoby tylko, odpowiadając na jedno z tych trzech pytań, skłamać.

Decyzja podejmowana na podstawie kwestionariusza to pewna funkcja boolowska. W rzeczywistości nie na każde pytanie można odpowiedzieć tak lub nie, ale nie jest to silne ograniczenie, bo na przykład pytanie z tysiącem dopuszczalnych odpowiedzi można w zasadzie zastąpić dziesięcioma pytaniami binarnymi. To, że zmiana pojedynczego argumentu może zmienić wartość funkcji, jest przejawem zjawiska zwanego czułością.

Niech więc $f$ będzie $|n$ -argumentową funkcją boolowską, a $|x = (x ,...,x ) 1 n$ dowolnym elementem jej dziedziny. Czułością $|s( f ,x)$ funkcji $f$ w punkcie $|x$ nazwiemy liczbę takich $y,$ że $y$ różni się od $x$ tylko na jednej współrzędnej, ale $| f(y) /= f (x).$ Czułością $|s( f )$ funkcji $f$ nazwiemy największą możliwą wartość czułości $|s( f ,x).$

Przykład 1. Aby zdać egzamin, należy poprawnie odpowiedzieć na siedem z dziesięciu pytań.

Alicja odpowiedziała poprawnie na 9 pytań i zdała. Czułość Alicji wynosi 0, gdyż zmiana jednej odpowiedzi nie może spowodować, że Alicja nie zda.
Bartek odpowiedział dobrze na 7 pytań i zdał z trudem. Gdyby udzielił innej odpowiedzi na którekolwiek z tych pytań, nie zdałby. Jego czułość to 7.
Czarek odpowiedział dobrze na 6 pytań i nie zdał, choć niewiele brakowało. Gdyby zaliczył choćby jedno z pozostałych 4 pytań, zdałby. Czułość Czarka to 4.
Dagmara odpowiedziała dobrze na 5 pytań i nie zdała. Zmiana jednej odpowiedzi nic nie daje - poprawnych odpowiedzi będzie najwyżej 6, co nie wystarcza do pozytywnego wyniku. Czułość Dagmary wynosi 0.

Czułość całej funkcji to 7 i nietrudno zobaczyć, że wpływają na nią jedynie przypadki graniczne. Ogólnie, dla egzaminu z $n$ pytaniami i progiem zdania na poziomie $m$ (oraz $|m$ bo trudno żądać, by ktoś odpowiedział na ponad 100% pytań) czułość to większa z liczb $m$ i $n | − m$

Przykład 2. Emil zaprosił na urodziny $n = m2$ gości pochodzących z $|m$ krajów (z każdego kraju dokładnie $m |$ osób). Imprezę uzna za udaną, jeśli z każdego kraju przyjdzie co najmniej jeden gość (funkcją boolowską $f$ jest tu więc koniunkcja $m$ alternatyw po $m |$ zmiennych w każdej, czyli funkcja stopnia $m$ ). Rozważmy graniczne przypadki.

"Prawie nieudana" udana impreza ma miejsce wtedy, gdy z każdego kraju ktoś jest, ale z niektórych krajów tylko pojedyncze osoby, które mogą wyjść, psując urodziny. Tych pojedynczych osób jest nie więcej niż krajów, więc czułość nie przekracza $|m.$
"Prawie udana" nieudana impreza jest zaś wtedy, gdy z jakiegoś (ale tylko jednego) kraju nikt nie przyszedł. Wtedy czekamy, aż ktoś z $|m$ zaproszonych z tego kraju gości jednak się pojawi - tu czułość wynosi $m. |$

Ostatecznie czułość całej funkcji to $s(f | ) = m$

Po wprowadzeniu powyższych pojęć możemy już powiedzieć, że problem rozstrzygnięty przez Huanga pierwotnie wcale nie dotyczył mrówek na kostce:

Twierdzenie (Hipoteza o czułości - obecnie twierdzenie Huanga). Dla każdej funkcji boolowskiej $f$ zachodzi nierówność $√ ------- |s( f)⩾ deg(f ).$

Związek funkcji boolowskich z kostkami jest dość prosty: podobnie jak zwykły sześcian możemy umieścić tak, by jego wierzchołkami były punkty $|(0,0,0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0)$ i $(1,1,1),$ i powiedzieć, że jest to dziedzina trójargumentowej funkcji boolowskiej, tak możemy uważać złożone z zer i jedynek ciągi długości $n$ za współrzędne wierzchołków $n$ -wymiarowej kostki.

Wracając na razie do geometrii, możemy sformułować następujące twierdzenie:

Twierdzenie (Huang). Jeśli ponad połowę z $2n$ wierzchołków $|n$ -wymiarowej kostki (czyli co najmniej $2n−1 + 1$ wierzchołków) zajmują mrówki, to co najmniej jedna z nich ma co najmniej $√ n-$ sąsiadek.

Dowód tego twierdzenia, wymagający jedynie znajomości podstaw algebry liniowej, w tym mnożenia macierzy, omówimy w kolejnej części artykułu, w następnym numerze. Powiemy wówczas również, jak z powyższego faktu wydedukować twierdzenie Huanga o czułości.