Movatterモバイル変換

[0]ホーム
URL:

Przejdź do zawartości
Wikipediawolna encyklopedia
Szukaj

Funkcja boolowska

Z Wikipedii, wolnej encyklopedii
Wikipedia:Weryfikowalność
Ten artykuł od 2012-11 wymagazweryfikowania podanych informacji.
Należy podać wiarygodne źródła w formieprzypisów bibliograficznych.
Część lub nawet wszystkie informacje w artykule mogą być nieprawdziwe. Jako pozbawione źródeł mogą zostać zakwestionowane i usunięte.
Sprawdź w źródłach:Encyklopedia PWN •Google Books • Google Scholar • Federacja Bibliotek Cyfrowych •BazHum •BazTech •RCIN • Internet Archive (texts /inlibrary)
Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się wdyskusji tego artykułu.
Po wyeliminowaniu niedoskonałości należy usunąć szablon{{Dopracować}} z tego artykułu.

Funkcja boolowska (funkcja logiczna) – dowolne odwzorowanief:X→Y,{\displaystyle f\colon X\to Y,} gdzieB={0,1}, X{\displaystyle B=\{0,1\},\ X} jest podzbioremBn,{\displaystyle B^{n},} zaśY{\displaystyle Y} jest podzbioremBm.{\displaystyle B^{m}.}

Jeżeli funkcja boolowska jest określona dla każdego elementu zbioruBn{\displaystyle B^{n}} (czyliX=Bn{\displaystyle X=B^{n}}), to nazywamy ją funkcją zupełną. Analogicznie, jeśliX{\displaystyle X} jest właściwym podzbioremBn,{\displaystyle B^{n},} to funkcja jest nazywana niezupełną lub też nie w pełni określoną.

Liczba wszystkichn{\displaystyle n}-argumentowych funkcji zupełnych jest równa:22n.{\displaystyle 2^{2^{n}}.}

Funkcja boolowska jest matematycznym modelemukładu kombinacyjnego. Układy tego typu są używane do budowy między innymimultiplekserów,mikroprocesorów, do sterowania na przykład wyświetlaczamiLED i w wielu innych urządzeniachelektronicznych.

Zapis funkcji boolowskiej

[edytuj |edytuj kod]

W opisie funkcji boolowskich używa się następujących elementów: literałów i wartości ze zbioru{0,1,−}.{\displaystyle \{0,1,-\}.} 0 i 1 są tutaj umownymi oznaczeniami dla wartości funkcji i nie należy ich wiązać zliczbami 0 (zero) i 1 (jeden); kreska oznacza, że funkcja nie jest dla danego wektora określona.

Literały

[edytuj |edytuj kod]

Literał definiuje się jako:

xe={xdlae=1x¯dlae=01dlae=−{\displaystyle x^{e}=\left\{{\begin{matrix}x&{\textrm {dla}}&e=1\\{\overline {x}}&{\textrm {dla}}&e=0\\1&{\textrm {dla}}&e=-\end{matrix}}\right.}

gdziex{\displaystyle x} jest symbolem zmiennej, natomiaste{\displaystyle e}wskaźnikiem literału. Mając dowolnen{\displaystyle n} zmiennych można przedstawić je w postaci literałów:

x1e1x2e2…xnen.{\displaystyle x_{1}^{e_{1}}x_{2}^{e_{2}}\ldots x_{n}^{e_{n}}.}

W niektórych zastosowaniach często przedstawia się funkcję (lub jej elementy) wyłącznie za pomocą wektorówwskaźników literałów:

x1e1x2e2…xnen→e1e2…en,{\displaystyle x_{1}^{e_{1}}x_{2}^{e_{2}}\ldots x_{n}^{e_{n}}\to e_{1}e_{2}\dots e_{n},}

np.

ab¯c¯de¯=a1b0c0d1e0→10010b,{\displaystyle a{\bar {b}}{\bar {c}}d{\bar {e}}=a^{1}b^{0}c^{0}d^{1}e^{0}\to 10010_{b},}
110b→x11x21x30=x1x2x3¯.{\displaystyle 110_{b}\to x_{1}^{1}x_{2}^{1}x_{3}^{0}=x_{1}x_{2}{\bar {x_{3}}}.}

W przypadku drugiej konwersji przypisanie poszczególnym bitom zmiennych jest czysto umowne.

Termy

[edytuj |edytuj kod]

Termem (wyrazem) iloczynowym/sumowym nazywamy iloczyn (np.abz¯{\displaystyle ab{\bar {z}}})/sumę (np.d¯+e¯+z+y{\displaystyle {\bar {d}}+{\bar {e}}+z+y}) w którym żadna zezmiennych nie występuje więcej niż raz. Np. jeśli funkcja ma trzy argumentya,{\displaystyle a,}b{\displaystyle b} ic,{\displaystyle c,} to termem jestabc,{\displaystyle abc,}ac{\displaystyle ac} itp.

Iloczyn nazywany jest pełnym, gdy zawierawszystkie literały; analogicznie definiuje sięsumę pełną.Miniterm jest innym określeniem dla iloczynu pełnego,maxterm dla sumy pełnej.

Jeśliminiterm (analogiczniemaxterm) zostanie przedstawiony za pomocą wektora wskaźników literałów, to wartość dwójkowa tego wektora nazywana jestindeksem dwójkowym iloczynu (sumy), natomiast wartość dziesiętnaindeksem dziesiętnym iloczynu (sumy); czasem pomija się przymiotniki „dwójkowy” i „dziesiętny”, mówiąc po prostu „indeks iloczynu (sumy)”.

Formy zapisu funkcji

[edytuj |edytuj kod]

W przykładach zakładamy, że funkcjaf{\displaystyle f} ma trzy argumenty:a,{\displaystyle a,}b{\displaystyle b} ic.{\displaystyle c.}

Opis słowny

[edytuj |edytuj kod]

Ten sposób stosowany jest w przypadku prostych funkcji, lub gdy charakteryzowane są pewne specyficzne własności funkcji. Np. „funkcja ma wartość jeden, gdy a jest różne od b, lub c jest równe b” lub „dla indeksów nieparzystych funkcja jest równa zero”.

Tablica prawdy

[edytuj |edytuj kod]

W tablicy wypisuje się wszystkie kombinacje zmiennych wejściowych oraz odpowiadające im wartości funkcji. W pierwszej kolumnie (oznaczonej #) można wpisać odpowiednieindeksy dziesiętne.

Gdy funkcja posiada niewiele jedynek (zer), wówczas do tablicy wpisuje się tylko te wiersze dla których funkcja jest równa jeden (zero).

#ABCf
00001
10011
20101
3011–
41001
51010
61101
71110

Mapa Karnaugha

[edytuj |edytuj kod]
 Osobny artykuł:metoda Karnaugha.

Jest to przekształcona tablica prawdy, przedstawiona w postaci prostokątnej tablicy, gdzieindeksy dwójkowe zostały pogrupowane tak, by spełniały własnościkodu Graya.

A\BC00011110
011–1
11001

Kanoniczna postać sumy

[edytuj |edytuj kod]

Dowolną funkcję boolowską można rozłożyć na dwa składniki w następujący sposób (jest to tak zwane twierdzenie o rozkładzie):

f(x1,x2,…,xn)=x1f(1,x2,…,xn)+x1¯f(0,x2,…,xn){\displaystyle f(x_{1},x_{2},\dots ,x_{n})=x_{1}f(1,x_{2},\dots ,x_{n})+{\overline {x_{1}}}f(0,x_{2},\dots ,x_{n})}

Postępując w ten sposób, dla wszystkichn{\displaystyle n} argumentów otrzymamy2n{\displaystyle 2^{n}} sum iloczynów minitermów i wartości funkcji ostałych argumentach, np.

f(a,b)=a¯b¯f(0,0)+a¯bf(0,1)+ab¯f(1,0)+abf(1,1).{\displaystyle f(a,b)={\overline {a}}{\overline {b}}f(0,0)+{\overline {a}}bf(0,1)+a{\overline {b}}f(1,0)+abf(1,1).}

Ponieważ iloczyn0⋅x=0,{\displaystyle 0\cdot x=0,} można zatem usunąć (nie pisać) wszystkie iloczyny w których funkcja ma wartość zero.

Np. jeśli funkcjaf(a,b){\displaystyle f(a,b)} przyjmuje wartości 1 dla a=1, b=0 dla pozostałych kombinacji zero, to jej kanoniczna postać sumy będzie miała postać:

f(a,b)=a¯b¯f(0,0)+a¯bf(0,1)+ab¯f(1,0)+abf(1,1)={\displaystyle f(a,b)={\overline {a}}{\overline {b}}f(0,0)+{\overline {a}}bf(0,1)+a{\overline {b}}f(1,0)+abf(1,1)=}
a¯b¯0+a¯b0+ab¯1+ab0=ab¯1=ab¯.{\displaystyle {\overline {a}}{\overline {b}}0+{\overline {a}}b0+a{\overline {b}}1+ab0=a{\overline {b}}1=a{\overline {b}}.}

Zatem w ostatecznej postaci funkcji pozostają jedynie teminitermy (iloczyny pełne) dla których funkcja ma wartość jeden. Często, w skróconej formie, opisuję się funkcję wyłącznie za pomocą zbioru ichindeksów dziesiętnych, np.:f(a,b)=∑[0,1,2,4,6,(3)].{\displaystyle f(a,b)=\sum [0,1,2,4,6,(3)].} Wartość w nawiasie oznacza, że dla tego indeksu funkcja ma wartość nieokreśloną.

W polskiej literaturze kanoniczna postać sumy oznaczana jest skrótemKPS, a w angielskiejSOP.

Kanoniczna postać iloczynu

[edytuj |edytuj kod]

Twierdzenie o rozkładzie ma również inną postać:

f(x1,x2,…,xn)=[x1¯+f(1,x2,…,xn)][x1+f(0,x2,…,xn)]{\displaystyle f(x_{1},x_{2},\dots ,x_{n})=[{\overline {x_{1}}}+f(1,x_{2},\dots ,x_{n})][x_{1}+f(0,x_{2},\dots ,x_{n})]}

Postać wynikowa kanonicznej postaci iloczynu zawiera iloczyn wszystkichmaxtermów (sum pełnych) dla których funkcja przyjmuje wartość zero.

W polskiej literaturze kanoniczna postać iloczynu oznaczana jest skrótemKPI, a w angielskiejPOS.

Macierzkostek

[edytuj |edytuj kod]
f={00∗1∗0010}{\displaystyle f={\begin{Bmatrix}0&0&*\\1&*&0\\0&1&0\end{Bmatrix}}}

Funkcja boolowska samodwoista

[edytuj |edytuj kod]

Funkcja boolowskaf{\displaystyle f} jest samodwoista, jeślif(x0,x1,...,xn)=¬f(x0¯,x1¯,...,xn¯){\displaystyle f(x_{0},x_{1},...,x_{n})=\neg {f({\bar {x_{0}}},{\bar {x_{1}}},...,{\bar {x_{n}}})}}

Łatwą do zapamiętania analogią do zbioru liczb rzeczywistych jestfunkcja nieparzysta.


Podsumowanie

[edytuj |edytuj kod]

Powyższe zapisy niosą z sobą nadmiar informacji. W tym przykładzie możliwa jestminimalizacja funkcjif,{\displaystyle f,} czyli sprowadzenie jej do prostszej, jakkolwiek równoważnej postaci:

f(A,B,C)=A¯+C¯.{\displaystyle f(A,B,C)={\bar {A}}+{\bar {C}}.}


Oprócz minimalizacji istnieją inne ważne zagadnienia z dziedzinysyntezy logicznej –redukcja argumentów idekompozycja funkcji boolowskich. Dzięki nim możliwe jest budowanie szybszych, tańszych i mniej zawodnychukładów cyfrowych.

Najczęściej używane funkcje boolowskie:

Zobacz też

[edytuj |edytuj kod]

Przypisy

[edytuj |edytuj kod]
Funkcje matematyczne
pojęcia podstawowe
obraz
przeciwobraz
typy (rodzaje)
ogólne
ciągi
innefunkcje jednej zmiennej
funkcje wielu zmiennych
funkcje zdefiniowane
samą przeciwdziedziną
działania algebraiczne
odmiany działań
jednoargumentowych
funkcje zdefiniowane
zbiorem wartości
zdefiniowaneporządkiem
zdefiniowanealgebraicznie
inne funkcje
pojęcia określone
głównie dla działań
jednoargumentowych
złożenie funkcji
(superpozycja)
przypadki działań
jednoargumentowych
przypadkibijekcji
struktury
definiowane funkcjami
inne powiązane
pojęcia
twierdzenia
uogólnienia

Kontrola autorytatywna (pojęcie matematyczne):
Źródło: „https://pl.wikipedia.org/w/index.php?title=Funkcja_boolowska&oldid=72922235”
Kategoria:
Ukryta kategoria:
[8]ページ先頭
©2009-2025 Movatter.jp