• Artykuły
  • Forum
  • Ciekawostki
  • Encyklopedia
  • Algebra Boole'a



    Podstrony: 1 [2] [3] [4] [5]
    Przeczytaj także...
    Moc zbioru – własność zbioru, która opisuje jego liczebność. Nieformalnie, moc zbioru jest tym większa im większy jest zbiór. Pojęcie mocy zbioru opiera się na pojęciu równoliczności dwóch zbiorów – zbiory A i B są równoliczne, gdy każdy element zbioru A można połączyć w parę z dokładnie jednym elementem zbioru B, innymi słowy istnieje bijekcja (funkcja różnowartościowa i "na") między zbiorami A i B. Zbiory równoliczne mają tę samą moc. Moce zbiorów są konkretnymi obiektami matematycznymi, nazywanymi liczbami kardynalnymi.Diagram Hassego – graf skierowany przedstawiający częściowy porządek w zbiorze, w odpowiedni sposób przedstawiony graficznie.
    Diagram Hassego dla algebry Boole’a podzbiorów zbioru trójelementowego

    Algebra Boole’a – pewien typ struktury algebraicznej, rodzaj algebry ogólnej stosowany 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.

    Rachunek zdań – dział logiki matematycznej badający związki między zmiennymi zdaniowymi (zdaniami) lub funkcjami zdaniowymi, utworzonymi za pomocą funktorów zdaniotwórczych (spójników zdaniowych) ze zdań lub prostszych funkcji zdaniowych. Rachunek zdań określa sposoby stosowania funktorów zdaniotwórczych w poprawnym wnioskowaniu.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:

    Typowymi przykładami algebr Boole’a są: rodzina wszystkich podzbiorów ustalonego zbioru wraz z działaniami na zbiorach jako operacjami algebry oraz dwuelementowa algebra wartości logicznych {0, 1} z działaniami koniunkcji, alternatywy i negacji.

    Definicja[ | edytuj kod]

    Algebra Boole’a – struktura algebraiczna w której i działaniami dwuargumentowymi, jest operacją jednoargumentową, a 0 i 1 są wyróżnionymi różnymi elementami zbioru spełniająca następujące warunki dla wszystkich

    Podzbiór – pewna „część” danego zbioru, czyli dla danego zbioru, nazywanego nadzbiorem, zbiór składający się z pewnej liczby jego elementów, np. żadnego, jednego, wszystkich. Pierwszy przypadek nazywa się podzbiorem pustym, drugi – podzbiorem jednoelementowym lub singletonem, trzeci – podzbiorem niewłaściwym.Andrzej Stanisław Mostowski (ur. 1 listopada 1913 we Lwowie, zm. 22 sierpnia 1975 w Vancouver, Kanada) – polski matematyk zajmujący się głównie podstawami matematyki, przedstawiciel warszawskiej szkoły matematycznej.

    Oznaczenia[ | edytuj kod]

    Istnieją co najmniej trzy różne, szeroko rozpowszechnione tradycje oznaczeń w teorii algebr Boole’a. W definicji sformułowanej powyżej użyto symboli ale w częstym użyciu są również oraz Symbole oznaczające operacje dwuczłonowe algebry Boole’a są prawie zawsze wprowadzane przez wybór jednej z par albo W oznaczeniach operacji jednoargumentowej algebry istnieje mniejsza konsekwencja i można się spotkać zarówno z symbolami jak i

    Roman Sikorski (ur. 11 lipca 1920 w Mszczonowie, zm. 12 września 1983 w Warszawie) – polski matematyk, profesor Uniwersytetu Warszawskiego i Instytutu Matematycznego PAN, członek rzeczywisty PAN (od 1964), autor prac z logiki matematycznej, algebr Boole’a, topologii, funkcji rzeczywistych, analizy funkcjonalnej (teoria wyznacznikowa dla pewnego typu operatorów liniowych ograniczonych na przestrzeniach Banacha), oryginalne ujęcie teorii dystrybucji. Kazimierz Kuratowski (ur. 2 lutego 1896 w Warszawie, zm. 18 czerwca 1980 w Warszawie), polski matematyk, jeden z czołowych przedstawicieli warszawskiej szkoły matematycznej.

    System oznaczeń przedstawiony powyżej (i dalej przyjmowany w tym artykule) jest używany, między innymi, w podręczniku Heleny Rasiowej.

    W badaniach teoriomnogościowych aspektów algebr Boole’a przeważa tradycja używania oznaczeń . Ten sam system został też wybrany za wiodący przez redaktorów monografii Handbook of Boolean Algebras.

    Stanford Encyclopedia of Philosophy (SEP) jest ogólnie dostępną encyklopedią internetową filozofii opracowaną przez Stanford University. Każde hasło jest opracowane przez eksperta z danej dziedziny. Są wśród nich profesorzy z 65 ośrodków akademickich z całego świata. Autorzy zgodzili się na publikację on-line, ale zachowali prawa autorskie do poszczególnych artykułów. SEP ma 1260 haseł (stan na 20 stycznia 2011). Mimo, że jest to encyklopedia internetowa, zachowano standardy typowe dla tradycyjnych akademickich opracowań, aby zapewnić jakość publikacji (autorzy-specjaliści, recenzje wewnętrzne).Algebra ogólna – obiekt matematyczny będący przedmiotem badań algebry uniwersalnej. Czasami algebra uniwersalna nazywana jest algebrą ogólną, wówczas rozważane w niej obiekty nazywa się zwykle algebrami abstrakcyjnymi lub po prostu algebrami.

    Z kolei symbole zgodne z oznaczeniami w teorii krat są częściej używane w kontekstach algebraicznych (i teoriokratowych).

    Spotykane są też inne kombinacje tychże symboli lub wręcz inne symbole (na przykład & w miejsce lub zamiast ). W elektronice i informatyce często stosuje się OR, AND oraz NOT w miejsce oraz W języku C oraz w językach nim inspirowanych używa się odpowiednio symboli: |, &, !.

    Kres (kraniec) dolny (również łac. infimum) oraz kres (kraniec) górny (także łac. supremum) – w matematyce pojęcia oznaczające odpowiednio: największe z ograniczeń dolnych oraz najmniejsze z ograniczeń górnych danego zbioru, o ile takie istnieją.Homomorfizm – funkcja odwzorowująca jedną algebrę ogólną (czyli strukturę algebraiczną taką jak grupa, pierścień czy przestrzeń wektorowa) w drugą, zachowująca przy tym odpowiadające sobie operacje. Jest to podstawowe narzędzie w badaniu i porównywaniu algebr.

    Minimalna aksjomatyzacja[ | edytuj kod]

    Powyższa (tradycyjna) definicja algebry Boole’a nie jest minimalna, np. nie jest konieczne wprowadzanie w niej symboli 0 i 1. Mogą one być konsekwencją aksjomatyki, a nie niezbędną dla niej definicją. 0 można zastąpić przez a 1 przez Dzięki prawom de Morgana można też z aksjomatyki wyeliminować działanie lub (W istocie wszystkie działania można tak naprawdę zastąpić jednym – dysjunkcją (NAND) lub binegacją (NOR).)

    Monadyczna algebra Boole’a – algebra Boole’a z dodatkowym działaniem jednoargumentowym ∃ {displaystyle exists } , które spełnia pewne warunki naśladujące własności kwantyfikatora egzystencjalnego.Topologia (gr. tópos – miejsce, okolica; lógos – słowo, nauka) – jeden z najważniejszych kierunków w matematyce współczesnej. Obiektem jej badań są te własności figur geometrycznych i brył, które nie ulegają zmianie nawet po radykalnym zdeformowaniu tych figur (a więc np. położenie i sąsiedztwo). Własności takie nazywa się własnościami topologicznymi figury.

    Istnieją równoważne, ale oszczędniejsze definicje algebry Boole’a. Przykładowy układ niezależnych aksjomatów to:

  • jest przemienne
  • jest łączne
  • aksjomat Huntingtona:
  • Inny taki układ to:

    Prawo podwójnej negacji albo prawo podwójnego zaprzeczenia – reguła rachunku zdań, która stwierdza, że zaprzeczenie negacji zdania jest tym samym zdaniem (bardziej formalnie: jest równoważne ze zdaniem wyjściowym).Ideał – w teorii porządków częściowych, teorii mnogości i pokrewnych dziedzinach matematyki pojęcie dualne do pojęcia filtru.
  • jest przemienne
  • jest łączne
  • aksjomat Robbinsa:
  • Istnieją też systemy z jednym aksjomatem.

    Elektronika cyfrowa to dziedzina elektroniki zajmująca się układami cyfrowymi, sygnałami cyfrowymi i cyfrowym przetwarzaniem sygnałów.Relacja równoważności – zwrotna, symetryczna i przechodnia relacja dwuargumentowa określona na pewnym zbiorze utożsamiająca ze sobą w pewien sposób jego elementy, co ustanawia podział tego zbioru na rozłączne podzbiory według tej relacji. Podobnie każdy podział zbioru niesie ze sobą informację o pewnej relacji równoważności.

    Przykłady[ | edytuj kod]

    Najprostsza algebra Boole’a ma tylko dwa elementy, 0 i 1, a operacje tej algebry są zdefiniowane przez następujące tabele działań:

    Algebra ta stanowi podstawę elektroniki cyfrowej.

    Jeśli jest ciałem podzbiorów zbioru to jest algebrą Boole’a (gdzie oznacza operację dopełnienia).

    Dopełnienie zbioru – intuicyjnie, zbiór wszystkich elementów (pewnego ustalonego nadzbioru), które do danego zbioru nie należą. W niektórych pozycjach można spotkać się również z alternatywną nazwą uzupełnienie zbioru.Struktura matematyczna (także model, system semantyczny, model semantyczny, dziedzina, struktura pierwszego rzędu) - w matematyce zbiór obiektów matematycznych połączonych w pewien system.

    Niech będzie zbiorem zdań w rachunku zdań. Niech będzie relacją dwuargumentową na zbiorze określoną jako:

    Teoria mnogości lub inaczej: teoria zbiorów – dział matematyki, a zarazem logiki matematycznej zapoczątkowany przez niemieckiego matematyka Georga Cantora pod koniec XIX wieku. Teoria początkowo wzbudzała wiele kontrowersji, jednak wraz z postępem matematyki zaczęła ona pełnić rolę fundamentu, na którym opiera się większość matematycznych rozważań.Aksjomat wyboru (ozn. AC od ang. Axiom of Choice) – jeden z aksjomatów teorii mnogości mówiący o możliwości skonstruowania zbioru (nazywanego selektorem) zawierającego dokładnie po jednym elemencie z każdego zbioru należącego do rodziny niepustych zbiorów rozłącznych.
    wtedy i tylko wtedy, gdy jest tautologią rachunku zdań.

    Można sprawdzić, że jest relacją równoważności na zbiorze Na zbiorze wszystkich klas abstrakcji relacji można wprowadzić operacje przez następujące formuły:

    Porządek zupełny – własność porządków częściowych postulująca istnienie kresów. W literaturze matematycznej istnieje kilka definicji tego pojęcia różniących się szczegółami technicznymi zależnymi od kontekstu matematycznego.Logika matematyczna – dział matematyki, który wyodrębnił się jako samodzielna dziedzina na przełomie XIX i XX wieku, wraz z dążeniem do dogłębnego zbadania podstaw matematyki. Koncentruje się ona na analizowaniu zasad rozumowania oraz pojęć z nim związanych z wykorzystaniem sformalizowanych oraz uściślonych metod i narzędzi matematyki.

    W ten sposób otrzymuje się poprawnie zdefiniowane operacje na zbiorze (tzn. wynik nie zależy od wyboru reprezentantów klas abstrakcji), a jest algebrą Boole’a. Algebra ta jest nazywana algebrą Lindenbauma-Tarskiego.

    Funkcja „na” a. surjekcja pisane też czasami jako suriekcja – funkcja przyjmująca jako swoje wartości wszystkie elementy przeciwdziedziny, tj. której obraz jest równy przeciwdziedzinie.Library of Congress Control Number (LCCN) – numer nadawany elementom skatalogowanym przez Bibliotekę Kongresu wykorzystywany przez amerykańskie biblioteki do wyszukiwania rekordów bibliograficznych w bazach danych i zamawiania kart katalogowych w Bibliotece Kongresu lub u innych komercyjnych dostawców.

    Algebry Lindenbauma-Tarskiego rozważa się również dla języków pierwszego rzędu. Niech będzie zbiorem zdań w ustalonym alfabecie i niech będzie niesprzeczną teorią w tym samym języku. Relację dwuargumentową na zbiorze można wprowadzić przez określenie

    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 qEdward Vermilye Huntington (ur. 26 kwietnia 1874 w Clinton, zm. 25 listopada 1952 Cambridge) – amerykański matematyk.
    wtedy i tylko wtedy, gdy

    Wówczas jest relacją równoważności na zbiorze Podobnie jak wcześniej:

    Łańcuch – cięgno składające się z pewnej liczby podobnych do siebie ogniw złączonych ze sobą tak, że tworzą całość, umożliwiając jednocześnie dużą zmienność kształtu.Aksjomaty Zermela-Fraenkla, aksjomatyka Zermela-Fraenkla, w skrócie: aksjomaty(ka) ZF – powszechnie przyjmowany układ aksjomatów teorii mnogości zaproponowany przez Ernsta Zermela w 1904 roku i później uzupełniony przez Abrahama Fraenkla.

    Można pokazać, że jest algebrą Boole’a.

    Monografia – praca naukowa omawiająca jakieś zagadnienie w sposób wyczerpujący. Zebranie i omówienie wszystkich dostępnych informacji dotyczących bezpośrednio danego zagadnienia.Paul Joseph Cohen (ur. 2 kwietnia 1934 w Long Branch, w stanie New Jersey, w USA; zm. 23 marca 2007, Stanford, Kalifornia) − amerykański matematyk, od 1964 prof. Stanford University.


    Podstrony: 1 [2] [3] [4] [5]




    Warto wiedzieć że... beta

    Zbiór skończony − zbiór o skończonej liczbie elementów. Nieujemną liczbę naturalną określającą ilość elementów zbioru skończonego nazywa się mocą zbioru. Zbiór skończony ma moc skończoną. Najmniejszym zbiorem skończonym jest zbiór pusty  Ø.
    George Boole (IPA: [buːl], ur. 2 listopada 1815 r. Lincoln, Anglia, zm. 8 grudnia 1864 r. w Ballintemple (hrabstwo Cork), Irlandia) – angielski matematyk, filozof i logik.
    Inwolucja – w matematyce funkcja, która ma funkcję odwrotną równą jej samej. Równoważnie jest to taka funkcja, która złożona sama ze sobą jest tożsamością.
    Funkcja kardynalna – funkcja której wartościami są liczby kardynalne. Zwykle tej nazwy używa się gdy, dodatkowo, wartości funkcji są nieskończonymi liczbami kardynalnymi. Często funkcje te są klasami.
    Algebra – jeden z najstarszych działów matematyki, powstały już w starożytności. Zajmuje się on algebrami ogólnymi i relacjami. Algebra elementarna zajmuje się takimi działaniami jak dodawanie i mnożenie; wprowadza pojęcie zmiennej i wielomianu razem z jego rozkładem na czynniki (faktoryzacją) i znajdowaniem ich pierwiastków, choć algebra jest działem bardziej ogólnym (patrz podział algebry).
    Helena Rasiowa (ur. 20 czerwca 1917 w Wiedniu, zm. 9 sierpnia 1994 w Warszawie) – polska matematyk, profesor Uniwersytetu Warszawskiego i Polskiej Akademii Nauk; zajmowała się logiką, algebrą (w tym algebrami Boole’a), teorią mnogości oraz informatyką teoretyczną. Autorka książki Wstęp do matematyki współczesnej, omawiającej zagadnienia z zakresu podstaw logiki i teorii mnogości.
    Dana Stewart Scott (ur. 11 października 1932 r.) informatyk, logik, filozof. W 1976 roku wraz z Michaelem Rabinem otrzymał nagrodę Turinga za pracę Finite Automata and Their Decision Problem, w której do teorii automatów wprowadzono maszyny niedeterministyczne.

    Reklama

    Czas generowania strony: 0.086 sek.