W dzisiejszym świecie coraz częściej używamy różnorodnych samochodów i gadżetów. I nie tylko wtedy, gdy trzeba zastosować dosłownie nieludzką siłę: przenieś ładunek, podnieś go na wysokość, wykop długi i głęboki rów itp. Samochody są dziś montowane przez roboty, jedzenie jest przygotowywane przez multicookery, a elementarne obliczenia arytmetyczne są wykonywane przez kalkulatory. Coraz częściej słyszymy wyrażenie "algebra Boole'a". Być może nadszedł czas, aby zrozumieć rolę człowieka w tworzeniu robotów i zdolność maszyn do rozwiązywania nie tylko problemów matematycznych, ale także logicznych.
Logika
Przetłumaczona z greki logika to uporządkowany system myślenia, który tworzy relacje między określonymi warunkami i pozwala wyciągać wnioski na podstawie przesłanek i założeń. Dość często pytamy się nawzajem: „Czy to logiczne?” Otrzymana odpowiedź potwierdza nasze przypuszczenia lub krytykuje tok myślenia. Ale proces się nie kończy: kontynuujemy rozumowanie.
Czasami liczba warunków (wstępnych) jest tak wielka, a relacje między nimi są tak zawiłe i złożone, że ludzki mózg nie jest w stanie „przetrawić” wszystkiego na raz. Zrozumienie tego, co się dzieje, może zająć więcej niż miesiąc (tydzień, rok). Alewspółczesne życie nie daje nam takich odstępów czasowych na podejmowanie decyzji. I uciekamy się do pomocy komputerów. I tu pojawia się algebra logiki, z własnymi prawami i własnościami. Pobierając wszystkie wstępne dane, umożliwiamy komputerowi rozpoznanie wszystkich relacji, wyeliminowanie sprzeczności i znalezienie satysfakcjonującego rozwiązania.
Matematyka i logika
Słynny Gottfried Wilhelm Leibniz sformułował pojęcie „logiki matematycznej”, której problemy były zrozumiałe tylko dla wąskiego kręgu naukowców. Kierunek ten nie wzbudził szczególnego zainteresowania i do połowy XIX wieku niewiele osób wiedziało o logice matematycznej.
Wielkie zainteresowanie środowiska naukowego spowodowało spór, w którym Anglik George Boole ogłosił zamiar stworzenia gałęzi matematyki, która nie ma absolutnie żadnego praktycznego zastosowania. Jak pamiętamy z historii, w tym czasie aktywnie rozwijała się produkcja przemysłowa, powstawały wszelkiego rodzaju maszyny pomocnicze i obrabiarki, czyli wszelkie odkrycia naukowe miały nastawienie praktyczne.
Patrząc w przyszłość, powiedzmy, że algebra Boole'a jest najczęściej używaną częścią matematyki we współczesnym świecie. Więc Bull przegrał swoją kłótnię.
George Buhl
Na szczególną uwagę zasługuje sama osobowość autora. Nawet biorąc pod uwagę, że w przeszłości ludzie dorastali przed nami, nadal nie sposób nie zauważyć, że w wieku 16 lat J. Buhl uczył w wiejskiej szkole, a w wieku 20 lat otworzył własną szkołę w Lincoln. Matematyk biegle posługiwał się pięcioma językami obcymi, aw wolnym czasie czytał praceNewtona i Lagrange'a. A wszystko to dotyczy syna prostego pracownika!
W 1839 Boole po raz pierwszy przesłał swoje prace naukowe do Cambridge Mathematical Journal. Naukowiec ma 24 lata. Dzieło Boole'a tak zainteresowało członków Towarzystwa Królewskiego, że w 1844 roku otrzymał medal za wkład w rozwój analizy matematycznej. Kilka kolejnych opublikowanych prac, opisujących elementy logiki matematycznej, pozwoliło młodemu matematykowi na objęcie stanowiska profesora w Cork County College. Przypomnij sobie, że sam Buhl nie miał wykształcenia.
Pomysł
Zasadniczo algebra Boole'a jest bardzo prosta. Istnieją zdania (wyrażenia logiczne), które z punktu widzenia matematyki można określić tylko dwoma słowami: „prawda” lub „fałsz”. Na przykład wiosną kwitną drzewa - prawda, latem pada śnieg - kłamstwo. Piękno tej matematyki polega na tym, że nie ma ścisłej potrzeby używania tylko liczb. Wszelkie stwierdzenia o jednoznacznym znaczeniu są całkiem odpowiednie dla algebry osądów.
Zatem algebra logiki może być używana dosłownie wszędzie: w planowaniu i pisaniu instrukcji, analizowaniu sprzecznych informacji o zdarzeniach i określaniu sekwencji działań. Najważniejszą rzeczą jest zrozumienie, że zupełnie nie ma znaczenia, w jaki sposób ustalimy prawdziwość lub fałszywość stwierdzenia. Te „jak” i „dlaczego” należy oddzielić. Liczy się tylko stwierdzenie faktu: prawda-fałsz.
Oczywiście dla programowania ważne są funkcje algebry logiki, które są zapisywane przez odpowiednieznaki i symbole. A poznanie ich oznacza opanowanie nowego języka obcego. Nie ma rzeczy niemożliwych.
Podstawowe pojęcia i definicje
Bez wnikania w szczegóły, zajmijmy się terminologią. Tak więc algebra Boole'a zakłada:
- wypowiedzi;
- operacje logiczne;
- funkcje i prawa.
Stwierdzenia to wszelkie twierdzące wyrażenia, których nie można interpretować w sposób niejednoznaczny. Zapisywane są jako liczby (5 > 3) lub formułowane znanymi słowami (słoń jest największym ssakiem). Jednocześnie wyrażenie „żyrafa nie ma szyi” również ma prawo istnieć, tylko algebra Boole'a zdefiniuje ją jako „fałsz”.
Wszystkie instrukcje muszą być jednoznaczne, ale mogą być elementarne i złożone. Te ostatnie używają spójników logicznych. Oznacza to, że w algebrze sądów zdania złożone są tworzone przez dodanie instrukcji elementarnych za pomocą operacji logicznych.
Operacje algebry Boole'a
Pamiętamy już, że operacje w algebrze sądów są logiczne. Tak jak algebra liczb wykorzystuje arytmetykę do dodawania, odejmowania lub porównywania liczb, elementy logiki matematycznej pozwalają tworzyć złożone stwierdzenia, negować lub obliczać wynik końcowy.
Operacje logiczne dla formalizacji i uproszczenia są zapisywane za pomocą formuł znanych nam w arytmetyce. Własności algebry Boole'a umożliwiają pisanie równań i obliczanie niewiadomych. Operacje logiczne są zwykle zapisywane przy użyciu tabeli prawdy. Jego kolumnyzdefiniuj elementy obliczenia i operację, która jest na nich wykonywana, a wiersze pokazują wynik obliczenia.
Podstawowe działania logiczne
Najczęstsze operacje w algebrze Boole'a to negacja (NOT) oraz logiczne AND i OR. W ten sposób można opisać prawie wszystkie czynności w algebrze sądów. Przeanalizujmy każdą z trzech operacji bardziej szczegółowo.
Negacja (nie) dotyczy tylko jednego elementu (operandu). Dlatego operacja negacji nazywana jest jednoargumentową. Aby napisać pojęcie „nie A”, użyj następujących symboli: ¬A, A¯¯¯ lub !A. W formie tabelarycznej wygląda to tak:
Funkcja negacji charakteryzuje się następującym stwierdzeniem: jeśli A jest prawdziwe, to B jest fałszywe. Na przykład Księżyc krąży wokół Ziemi – prawda; Ziemia kręci się wokół księżyca - fałsz.
Mnożenie i dodawanie logiczne
Identyfikator logiczny AND nazywa się operacją koniunkcji. Co to znaczy? Po pierwsze, że można go zastosować do dwóch operandów, tj. I jest operacją binarną. Po drugie, tylko w przypadku prawdziwości obu argumentów (zarówno A, jak i B) samo wyrażenie jest prawdziwe. Przysłowie „Cierpliwość i praca zmiażdżą wszystko” sugeruje, że tylko oba czynniki pomogą człowiekowi poradzić sobie z trudnościami.
Symbole używane do pisania: A∧B, A⋅B lub A&&B.
Koniunkcja jest podobna do mnożenia w arytmetyce. Czasami tak mówią - mnożenie logiczne. Jeśli pomnożymy elementy tabeli wiersz po wierszu, otrzymamy wynik podobny do logicznego rozumowania.
Disjunction to logiczna operacja LUB. Ma wartość prawdygdy przynajmniej jedno ze stwierdzeń jest prawdziwe (A lub B). Jest napisane tak: A∨B, A+B lub A||B. Tabele prawdy dla tych operacji to:
Disjunction jest jak dodawanie arytmetyczne. Operacja dodawania logicznego ma tylko jedno ograniczenie: 1+1=1. Pamiętajmy jednak, że w formacie cyfrowym logika matematyczna jest ograniczona do 0 i 1 (gdzie 1 to prawda, 0 to fałsz). Na przykład stwierdzenie „w muzeum można zobaczyć arcydzieło lub spotkać ciekawego rozmówcę” oznacza, że można zobaczyć dzieła sztuki lub spotkać ciekawą osobę. Jednocześnie nie wyklucza się jednoczesnego wystąpienia obu zdarzeń.
Funkcje i prawa
Więc już wiemy, jakich operacji logicznych używa algebra Boole'a. Funkcje opisują wszystkie właściwości elementów logiki matematycznej i pozwalają uprościć złożone złożone warunki problemów. Najbardziej zrozumiałą i prostą właściwością wydaje się odrzucenie operacji pochodnych. Instrumenty pochodne to wyłączne OR, implikacja i równoważność. Ponieważ zbadaliśmy tylko podstawowe operacje, rozważymy również właściwości tylko z nich.
Łączność oznacza, że w wyrażeniach typu „i A, B i C” kolejność operandów nie ma znaczenia. Formuła jest napisana tak:
(A∧B)∧V=A∧(B∧V)=A∧B∧V, (A∨B)∨C=A∨(B∨C)=A∨B∨C.
Jak widać, jest to cecha nie tylko koniunkcji, ale także alternatywy.
Przemienność oznacza, że wynikkoniunkcja lub alternatywa nie zależy od tego, który element był brany pod uwagę jako pierwszy:
A∧B=B∧A; A∨B=B∨A.
Rozdzielczość umożliwia rozszerzanie nawiasów w złożonych wyrażeniach logicznych. Zasady są podobne do otwierania nawiasów w mnożeniu i dodawaniu w algebrze:
A∧(B∨C)=A∧B∨A∧B; A∨B∧B=(A∨B)∧(A∨B).
Własności jedynki i zera, które mogą być jednym z argumentów, są również podobne do mnożenia algebraicznego przez zero lub jeden i dodawania przez jeden:
A∧0=0, A∧1=A; A∨0=A, A∨1=1.
Idempotentność mówi nam, że jeśli w odniesieniu do dwóch równych argumentów, wynik operacji okaże się podobny, to możemy „wyrzucić” dodatkowe argumenty, które komplikują tok rozumowania. Zarówno koniunkcja, jak i alternatywa są operacjami idempotentnymi.
B∧B=B; B∨B=B.
Wchłanianie pozwala nam również uprościć równania. Absorpcja oznacza, że gdy inna operacja z tym samym elementem jest zastosowana do wyrażenia z jednym operandem, wynikiem jest operand z operacji absorbowania.
A∧B∨B=B; (A∨B)∧B=B.
Sekwencja operacji
Sekwencja operacji ma niemałe znaczenie. Właściwie, tak jak w przypadku algebry, istnieje priorytet funkcji, których używa algebra Boole'a. Formuły można uprościć tylko wtedy, gdy przestrzegane jest znaczenie operacji. Ranking od najważniejszego do najmniejszego otrzymujemy następującą sekwencję:
1. Odmowa.
2. Spójka.
3. Rozłączenie, wyłącznośćLUB.
4. Implikacja, równoważność.
Jak widać, tylko negacja i koniunkcja nie mają równego pierwszeństwa. A priorytety alternatywy i XOR są równe, podobnie jak priorytety implikacji i równoważności.
Funkcje implikacji i równoważności
Jak już powiedzieliśmy, oprócz podstawowych operacji logicznych, logika matematyczna i teoria algorytmów wykorzystują pochodne. Najczęściej używane są implikacje i równoważność.
Implikacja lub logiczna konsekwencja to instrukcja, w której jedno działanie jest warunkiem, a drugie jest konsekwencją jego realizacji. Innymi słowy, jest to zdanie z przyimkami „jeśli… to”. „Jeśli lubisz jeździć, uwielbiaj nosić sanki”. Oznacza to, że do jazdy na nartach trzeba napiąć sanki pod górę. Jeśli nie ma ochoty zjeżdżać z góry, nie trzeba nosić sań. Jest napisane tak: A→B lub A⇒B.
Równoważność zakłada, że wynikowa akcja występuje tylko wtedy, gdy oba operandy są prawdziwe. Na przykład noc zamienia się w dzień, gdy (i tylko wtedy) słońce wschodzi nad horyzontem. W języku logiki matematycznej zdanie to jest zapisane w następujący sposób: A≡B, A⇔B, A==B.
Inne prawa algebry Boole'a
Algebra sądów rozwija się, a wielu zainteresowanych naukowców sformułowało nowe prawa. Za najbardziej znane uważane są postulaty szkockiego matematyka O. de Morgana. Zauważył i zdefiniował takie własności jak bliska negacja, dopełnienie i podwójna negacja.
Zamknij negację oznacza, że nie ma negacji przed nawiasem:nie (A lub B)=nie A lub NIE B.
Kiedy argument jest zanegowany, niezależnie od jego wartości, mówi się o dopełnieniu:
B∧¬B=0; B∨¬B=1.
I wreszcie podwójna negacja sama się rekompensuje. Tych. albo negacja znika przed operandem, albo pozostaje tylko jeden.
Jak rozwiązywać testy
Logika matematyczna implikuje uproszczenie danych równań. Podobnie jak w algebrze, musisz najpierw maksymalnie uprościć warunek (pozbądź się skomplikowanych danych wejściowych i operacji na nich), a następnie zacząć szukać właściwej odpowiedzi.
Co można zrobić, aby uprościć? Konwertuj wszystkie operacje pochodne na proste. Następnie otwórz wszystkie nawiasy (lub odwrotnie, wyjmij go z nawiasów, aby skrócić ten element). Kolejnym krokiem powinno być zastosowanie własności algebry Boole'a w praktyce (absorpcja, własności zera i jedynki itp.).
Docelowo równanie powinno składać się z minimalnej liczby niewiadomych połączonych prostymi operacjami. Najłatwiejszym sposobem znalezienia rozwiązania jest uzyskanie dużej liczby bliskich negatywów. Wtedy odpowiedź pojawi się sama.
