• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Funkcja boolowska

    Przeczytaj także...
    Algebra Boole’a – algebra ogólna stosowana w matematyce, informatyce teoretycznej oraz elektronice cyfrowej. Jej nazwa pochodzi od nazwiska matematyka, filozofa i logika George’a Boole’a. Teoria algebr Boole’a jest działem matematyki na pograniczu teorii częściowego porządku, algebry, logiki matematycznej i topologii.Bramka NOR – jeden z funktorów zdaniowych rachunku zdań; dwuargumentowa funkcja boolowska (funktor logiczny) realizująca zaprzeczoną sumę logiczną (NOT OR) – jest prawdziwa wtedy i tylko wtedy, gdy oba składniki są fałszywe. Odpowiada wyrażeniu „ani … ani…”. Jego znaczenie przedstawia poniższa tablica prawdy:
    Minimalizacja funkcji boolowskich polega na znalezieniu dla danej funkcji formuły minimalnej, która jest jak najmniej skomplikowana.

    Funkcja boolowska (funkcja logiczna) – dowolne odwzorowanie gdzie jest podzbiorem zaś jest podzbiorem

    Mikroprocesor – układ cyfrowy wykonany jako pojedynczy układ scalony o wielkim stopniu integracji (LSI) zdolny do wykonywania operacji cyfrowych według dostarczonego ciągu instrukcji.Synteza logiczna polega na znalezieniu takiej konfiguracji zasobów sprzętowych (bramek logicznych), przerzutników, komórek czy też makrokomórek), która realizować będzie założony układ cyfrowy (opisany zazwyczaj za pomocą języka opisu sprzętu (HDL) lub sieci połączeń). Proces ten przebiega według pewnych wytycznych nakładanych przez projektanta. Może to być minimalizacja potrzebnych zasobów sprzętowych, minimalizacja maksymalnego czasu propagacji sygnału w układzie lub zmniejszenie mocy pobieranej przez układ.

    Jeżeli funkcja boolowska jest określona dla każdego elementu zbioru (czyli ), to nazywamy ją funkcją zupełną. Analogicznie, jeśli jest właściwym podzbiorem to funkcja jest nazywana niezupełną lub też nie w pełni określoną.

    Koniunkcja – zdanie złożone mające postać p i q , gdzie p, q są zdaniami. W rachunku zdań koniunkcję zapisuje się symbolicznie jako: p ∧ q {displaystyle p,land ,q,!} . Przez koniunkcję rozumie się też zdanie mające postać p(1) i ... i p(n). Koniunkcję można zdefiniować precyzyjniej jako dwuargumentowe działanie określone w zbiorze zdań, które zdaniom p, q przyporządkowuje zdanie p i qKod Graya, zwany również kodem refleksyjnym, jest dwójkowym kodem bezwagowym niepozycyjnym, który charakteryzuje się tym, że dwa kolejne słowa kodowe różnią się tylko stanem jednego bitu. Jest również kodem cyklicznym, bowiem ostatni i pierwszy wyraz tego kodu także spełniają w/w zasadę.

    Liczba wszystkich -argumentowych funkcji zupełnych jest równa:

    Multiplekser (w skrócie MUX) – układ kombinacyjny, najczęściej cyfrowy, służący do wyboru jednego z kilku dostępnych sygnałów wejściowych i przekazania go na wyjście.Dioda elektroluminescencyjna, dioda świecąca (ang. light-emitting diode, LED) – dioda zaliczana do półprzewodnikowych przyrządów optoelektronicznych, emitujących promieniowanie w zakresie światła widzialnego, podczerwieni i ultrafioletu.

    Funkcja boolowska jest matematycznym modelem układu kombinacyjnego. Układy tego typu są używane do budowy między innymi multiplekserów, mikroprocesorów, do sterowania na przykład wyświetlaczami LED i w wielu innych urządzeniach elektronicznych.

    Zapis funkcji boolowskiej[ | edytuj kod]

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

    Elektronika – dziedzina techniki i nauki zajmująca się obwodami elektrycznymi zawierającymi, obok elementów elektronicznych biernych, elementy aktywne takie jak lampy próżniowe, tranzystory i diody. W obwodach takich można wzmacniać słabe sygnały dzięki nieliniowym charakterystykom elementów czynnych (i ich możliwościom sterowania przepływem elektronów). Podobnie możliwość pracy urządzeń jako przełączniki pozwala na przetwarzanie sygnałów cyfrowych.Dysjunkcja, dyzjunkcja, dysjunkcja/dyzjunkcja Sheffera, funkcja Sheffera, funktor Sheffera, NAND, w terminologii Jana Łukasiewicza niewspółzachodzenie – zdanie lub funkcja zdaniowa utworzone za pomocą funktora dysjunkcji, jednego z dwuargumentowych funktorów zdaniotwórczych rachunku zdań. Symbolem funktora dysjunkcji jest przeważnie ukośna kreska /. W języku potocznym funktorowi temu odpowiada swobodnie „albo..., albo...”. Wyrażenie „p / q” odczytywać można jako „albo p, albo q” lub „bądź p, bądź q” (w znaczeniu „zachodzi najwyżej jedno z dwojga”, por.), ponieważ dysjunkcja jest negacją koniunkcji („nieprawda, że zarazem p i q”). Pojęcie dysjunkcji wprowadził w 1913 Henry Sheffer. W terminologii angielskiej disjunction to polska alternatywa, odpowiednikiem polskiej dysjunkcji (Sheffera) jest natomiast alternative denial.

    Literały[ | edytuj kod]

    Literał definiuje się jako:

    gdzie jest symbolem zmiennej, natomiast wskaźnikiem literału. Mając dowolne zmiennych można przedstawić je w postaci literałów:

    Zbiór funkcji boolowskich nazywa się systemem funkcjonalnie pełnym (bazą), jeśli dowolna funkcja boolowska może być przedstawiona za pomocą stałych 0 i 1 oraz funkcji należących do tego zbioru i argumentów funkcji.Macierz – w matematyce układ liczb, symboli lub wyrażeń zapisanych w postaci prostokątnej tablicy. Choć słowo „macierz” oznacza najczęściej macierz dwuwskaźnikową, to możliwe jest rozpatrywanie macierzy wielowskaźnikowych (zob. notacja wielowskaźnikowa). Macierze jednowskaźnikowe nazywa się często wektorami wierszowymi lub kolumnowymi, co wynika z zastosowań macierzy w algebrze liniowej. W informatyce macierze modeluje się zwykle za pomocą (najczęściej dwuwymiarowych) tablic.

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

    Układ kombinacyjny jest jednym z rodzajów układów cyfrowych. Charakteryzuje się tym, że stan wyjść zależy wyłącznie od stanu wejść; stan wyjść opisują funkcje boolowskie - w przeciwieństwie do układów sekwencyjnych, których stan wyjść zależy od stanu wejść oraz od poprzedniego stanu wyjść. W układach kombinacyjnych nie występuje sprzężenie zwrotne.Liczba – pojęcie abstrakcyjne, jedno z najczęściej używanych w matematyce. Pierwotnie liczby służyły do porównywania wielkości zbiorów przedmiotów (liczby naturalne), później także wielkości ciągłych (miary i wagi), obecnie w matematyce są rozważane jako twory abstrakcyjne, w oderwaniu od ewentualnych fizycznych zastosowań.

    np.

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

    Termy[ | edytuj kod]

    Termem (wyrazem) iloczynowym/sumowym nazywamy iloczyn (np. )/sumę (np. ) w którym żadna ze zmiennych nie występuje więcej niż raz. Np. jeśli funkcja ma trzy argumenty i to termem jest itp.

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

    Jeśli miniterm (analogicznie maxterm) zostanie przedstawiony za pomocą wektora wskaźników literałów, to wartość dwójkowa tego wektora nazywana jest indeksem dwójkowym iloczynu (sumy), natomiast wartość dziesiętna indeksem 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 kod]

    W przykładach zakładamy, że funkcja ma trzy argumenty: i

    Opis słowny[ | 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 kod]

    W tablicy wypisuje się wszystkie kombinacje zmiennych wejściowych oraz odpowiadające im wartości funkcji. W pierwszej kolumnie (oznaczonej #) można wpisać odpowiednie indeksy 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).

    Mapa Karnaugha[ | edytuj kod]

     Osobny artykuł: metoda Karnaugha.

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

    Kanoniczna postać sumy[ | 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):

    Postępując w ten sposób, dla wszystkich argumentów otrzymamy sum iloczynów minitermów i wartości funkcji o stałych argumentach, np.

    Ponieważ iloczyn można zatem usunąć (nie pisać) wszystkie iloczyny w których funkcja ma wartość zero.

    Np. jeśli funkcja przyjmuje wartości 1 dla a=1, b=0 dla pozostałych kombinacji zero, to jej kanoniczna postać sumy będzie miała postać:

    Zatem w ostatecznej postaci funkcji pozostają jedynie te minitermy (iloczyny pełne) dla których funkcja ma wartość jeden. Często, w skróconej formie, opisuję się funkcję wyłącznie za pomocą zbioru ich indeksów dziesiętnych, np.: Wartość w nawiasie oznacza, że dla tego indeksu funkcja ma wartość nieokreśloną.

    W polskiej literaturze kanoniczna postać sumy oznaczana jest skrótem KPS, a w angielskiej SOP.

    Kanoniczna postać iloczynu[ | edytuj kod]

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

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

    W polskiej literaturze kanoniczna postać iloczynu oznaczana jest skrótem KPI, a w angielskiej POS.

    | edytuj kod]

    Podsumowanie[ | edytuj kod]

    Powyższe zapisy niosą z sobą nadmiar informacji. W tym przykładzie możliwa jest minimalizacja funkcji czyli sprowadzenie jej do prostszej, jakkolwiek równoważnej postaci:

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

    Najczęściej używane funkcje boolowskie:

  • NOT
  • AND i NAND
  • OR i NOR
  • XOR
  • Zobacz też[ | edytuj kod]

  • algebra Boole’a
  • kostka boolowska
  • system funkcjonalnie pełny
  • układ cyfrowy
  • układ kombinacyjny



  • w oparciu o Wikipedię (licencja GFDL, CC-BY-SA 3.0, autorzy, historia, edycja)

    Reklama

    Czas generowania strony: 0.07 sek.