[ 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 ]