[ Pobierz całość w formacie PDF ]
.��ZADANIA Z MPIWICZENIA 1FUNKCJE BOOLOWSKIE1.Niech Fn oznacza zbiór wszystkich n-argumentowych funkcji boolowskich.Wyznaczyć |Fn|.2.Wyznaczyć DAPK i DKPK dla funkcji f : L3 �! L zdefiniowanej przypomocy tabelki:x y z f(x, y, z)0 0 0 10 0 1 00 1 0 01 0 0 10 1 1 11 0 1 01 1 0 11 1 1 03.Niech Sn będzie zbiorem wszystkich permutacji zbioru {1, 2,., n).Niech� " Sn i niech f " Fn, wtedy definiujemy:�f(x1, x2,., xn) = f(x�(1), x�(2),., x�(n)).Dla wszystkich � " S3 wyznaczyć �f, gdzie f jest funkcją z zadania poprzed-niego.4.Funkcję boolowską f " Fn nazywamy symetryczną wtedy i tylko wte-dy gdy dla każdego � " Sn mamy �f = f.Wyznaczyć wszystkie funkcjesymetryczne w F3.5.Funkcję boolowską f " Fn nazywamy całkowicie asymetryczną jeśli zbiór{�f; � " Sn} ma n! elementów.Wyznaczyć wszystkie całkowicie antysyme-tryczne funkcje w zbiorach F2 i F3.6.Czy w zbiorze Fn istnieją funkcje, które nie są ani symetryczne ani całko-wicie antysymetryczne?1 7.Funkcję boolowską f " Fn nazywamy liniową, jeśli istnieją takie elementya0, a1,., an " {0, 1}, żef(x1, x2,., xn) = a1 �" a1x1 �".�" anxn,gdzie �" oznacza dodawanie modulo 2.Wyznaczyć wszystkie funkcje liniowew zbiorze F3.8.Ile jest funkcji liniowych w zbiorze Fn?9.Niech A = (a1, a2,., an), B = (b1, b2,., bn), gdzie ai, bi " {0, 1} dla1 i n.Będziemy pisali A z" B, jeżeli ai bi dla wszystkich i.Narysowaćgraf tego porządku w zbiorze L3.10.Funkcję f " Fn nazywamy monotoniczną jeśli(a1, a2,., an) z" (b1, b2,., bn)pociąga za sobą zawszef(a1, a2,., an) f(b1, b2,., bn).Wyznaczyć wszystkie funkcje monotoniczne w zbiorze F3.Podać przykładfunkcji, która nie jest monotoniczna.11.Niech f " Fn wtedy definiujemy f(x1, x2,., xn) = f(x1, x2,., xn),gdzie x oznacza funkcję negacji.Wyznaczyć f, f i f dla funkcji f zdefinio-wanej następująco:x y z f(x, y, z)0 0 0 10 0 1 00 1 0 01 0 0 10 1 1 11 0 1 11 1 0 01 1 1 012.Funkcję f " Fn nazywamy samodualną jeśli f = f.Wyznaczyć wszystkiesamodualne funkcje w zbiorze F3.2 13.Wyznaczyć w zbiorze F3 wszystkie funkcje, które spełniają warunek f =f.14.Czy w zbiorze F3 istnieją funkcje, które są nieliniowe, niemonotonocznei niesamodualne?15.Podać przykład funkcji f, g " F3, takich że zbiór {f, g} jest zupełny.16.Korzystając z twierdzenia Posta, wyznaczyć wszystkie funkcje f " F3 ta-kie, że zbiór {f} jest zupełny.Podbnie wyznaczyć wszystkie jednoelementowezbiory zupełne w F2.3
[ Pobierz całość w formacie PDF ]
