Prawo logiki klejenia. Podstawy algebry logiki

Lekcja z informatyki przeznaczona jest dla uczniów 10 klasy szkoły ogólnokształcącej, której program nauczania obejmuje dział „Algebra logiki”. Temat ten jest dla uczniów bardzo trudny, dlatego jako nauczyciel chciałem zainteresować ich poznawaniem praw logiki, upraszczaniem wyrażeń logicznych i zainteresowaniem rozwiązywaniem problemów logicznych. W zwykłej formie udzielanie lekcji na ten temat jest żmudne i kłopotliwe, a niektóre definicje nie zawsze są dla dzieci jasne. W związku z udostępnieniem przestrzeni informacyjnej, miałem okazję zamieścić swoje lekcje w powłoce „nauka”. Studenci, zarejestrowani w nim, mogą uczestniczyć w tym kursie w wolnym czasie i ponownie przeczytać to, co nie było jasne na lekcji. Niektórzy uczniowie, po opuszczonych lekcjach z powodu choroby, nadrabiają opuszczoną tematykę w domu lub w szkole i są zawsze gotowi na następną lekcję. Taka forma nauczania bardzo przypadła do gustu wielu dzieciom, a te prawa, które były dla nich niezrozumiałe, można teraz znacznie łatwiej i szybciej nauczyć się w formie komputerowej. Oferuję jedną z takich lekcji informatyki, która jest prowadzona integracyjnie z ICT.

Plan lekcji

1. Wyjaśnienie nowego materiału, z udziałem komputera - 25 minut.
2. Podstawowe pojęcia i definicje podane w "nauce" - 10 minut.
3. Materiał dla ciekawskich - 5 minut.
4. Praca domowa - 5 minut.

1. Wyjaśnienie nowego materiału

Prawa logiki formalnej

Najprostsze i najbardziej potrzebne prawdziwe związki między myślami wyrażają się w podstawowych prawach logiki formalnej. Są to prawa tożsamości, niesprzeczności, wyłączonego środka, racji dostatecznej.

Prawa te są fundamentalne, ponieważ w logice odgrywają szczególnie ważną rolę, są najbardziej ogólne. Pozwalają upraszczać wyrażenia logiczne oraz budować wnioski i dowody. Pierwsze trzy z powyższych praw zostały zidentyfikowane i sformułowane przez Arystotelesa, a prawo racji dostatecznej - przez G. Leibniza.

Prawo tożsamości: w procesie pewnego rozumowania każde pojęcie i sąd musi być tożsame ze sobą.

Prawo niesprzeczności: niemożliwe jest, aby jedno i to samo oko jednocześnie było i nie było nieodłączne tej samej rzeczy pod tym samym względem. Oznacza to, że nie można jednocześnie czegoś potwierdzić i zaprzeczyć.

Prawo wyłączonego środka: z dwóch sprzecznych twierdzeń jedno jest prawdziwe, drugie fałszywe, a trzecie nie jest dane.

Prawo wystarczającego powodu: Każda prawdziwa myśl musi być wystarczająco uzasadniona.

Ostatnie prawo mówi, że dowód czegoś zakłada uzasadnienie dokładnie i tylko prawdziwych myśli. Nie można udowodnić fałszywych myśli. Jest dobre łacińskie przysłowie: „Błądzić jest rzeczą wspólną dla każdego człowieka, ale tylko głupiec upiera się przy błędzie”. Nie ma formuły dla tego prawa, ponieważ ma ono tylko charakter materialny. Prawdziwe sądy, materiał faktograficzny, dane statystyczne, prawa nauki, aksjomaty, udowodnione twierdzenia mogą służyć jako argumenty potwierdzające prawdziwą myśl.

Prawa algebry zdań

Algebra zdań (algebra logiki) to dział logiki matematycznej zajmujący się badaniem operacji logicznych na zdaniach i reguł przekształcania zdań złożonych.

Podczas rozwiązywania wielu problemów logicznych często konieczne jest uproszczenie formuł uzyskanych poprzez sformalizowanie ich warunków. Upraszczanie wzorów w algebrze zdań odbywa się na podstawie przekształceń równoważnych opartych na podstawowych prawach logicznych.

Prawa algebry zdań (algebry logiki) są tautologiami.

Czasami prawa te nazywane są twierdzeniami.

W algebrze zdań prawa logiczne są wyrażone jako równość równoważnych formuł. Wśród praw szczególnie wyróżniają się te, które zawierają jedną zmienną.

Pierwsze cztery z następujących praw to podstawowe prawa algebry zdań.

Prawo tożsamości:

Każde pojęcie i osąd jest tożsame ze sobą.

Prawo tożsamości oznacza, że ​​w procesie rozumowania nie można zamienić jednej myśli na inną, jednego pojęcia na drugie. Jeśli to prawo zostanie naruszone, możliwe są błędy logiczne.

Na przykład dyskusja Słusznie mówią, że język zabierze cię do Kijowa, ale wczoraj kupiłem język wędzony, co oznacza, że ​​teraz mogę bezpiecznie jechać do Kijowa niepoprawne, ponieważ pierwsze i drugie słowo „język” oznacza różne pojęcia.

w dyskusji: Ruch jest wieczny. Chodzenie do szkoły to ruch. Dlatego chodzenie do szkoły jest na zawsze słowo „ruch” używane jest w dwóch różnych znaczeniach (pierwsze – w sensie filozoficznym – jako cecha materii, drugie – w znaczeniu potocznym – jako czynność poruszania się w przestrzeni), co prowadzi do błędnego wniosku.

Prawo niesprzeczności:

Zdanie i jego zaprzeczenie nie mogą być jednocześnie prawdziwe. To znaczy, jeśli oświadczenie A jest prawdziwe, to jego zaprzeczenie ani musi być fałszywe (i vice versa). Wtedy ich produkt zawsze będzie fałszywy.

To właśnie ta równość jest często używana podczas upraszczania złożonych wyrażeń logicznych.

Czasami prawo to jest formułowane w następujący sposób: dwa zdania, które są ze sobą sprzeczne, nie mogą być jednocześnie prawdziwe. Przykłady niezgodności z prawem niesprzeczności:

1. Na Marsie jest życie, a na Marsie nie ma życia.

2. Olya ukończyła szkołę średnią i jest w 10. klasie.

Prawo wyłączonego środka:

W tym samym momencie zdanie może być prawdziwe lub fałszywe, trzeciego nie ma. Prawda albo A, Lub ani. Przykłady realizacji prawa wyłączonego środka:

1. Liczba 12345 jest parzysta lub nieparzysta, nie ma trzeciej.

2. Firma działa ze stratą lub na progu rentowności.

3. Ten płyn może, ale nie musi, być kwasem.

Prawo wyłączonego środka nie jest prawem uznawanym przez wszystkich logików za uniwersalne prawo logiki. Prawo to stosuje się tam, gdzie wiedza dotyczy sztywnej sytuacji: „albo - albo”, „prawda-fałsz”. Tam, gdzie istnieje niepewność (na przykład w rozumowaniu o przyszłości), często nie można zastosować prawa wyłączonego środka.

Rozważ następujące stwierdzenie: Ta sugestia jest fałszywa. Nie może być prawdą, ponieważ twierdzi, że jest fałszywa. Ale nie może też być fałszywe, bo wtedy byłoby prawdziwe. To stwierdzenie nie jest ani prawdziwe, ani fałszywe, a zatem prawo wyłączonego środka jest naruszone.

Paradoks(gr. paradoxos – nieoczekiwany, dziwny) w tym przykładzie wynika z faktu, że zdanie odnosi się do siebie. Innym znanym paradoksem jest problem fryzjera: W jednym mieście fryzjer obcina włosy wszystkim mieszkańcom, z wyjątkiem tych, którzy sami obcinają włosy. Kto obcina włosy fryzjerowi? W logice, ze względu na jej formalność, nie jest możliwe uzyskanie formy takiego zdania autoreferencyjnego. To po raz kolejny potwierdza ideę, że za pomocą algebry logiki nie da się wyrazić wszystkich możliwych myśli i argumentów. Pokażmy, jak na podstawie definicji równoważności zdań można otrzymać pozostałe prawa algebry zdań.

Na przykład zdefiniujmy, co jest równoważne (równoważne) A(dwa razy nie A, czyli negacja negacji A). W tym celu zbudujemy tabelę prawdy:

Z definicji równoważności musimy znaleźć kolumnę, której wartości pasują do wartości kolumny A. To będzie kolumna A.

W ten sposób możemy sformułować podwójne prawonegacje:

Jeśli dwukrotnie zanegojemy jakieś stwierdzenie, wynikiem jest oryginalne stwierdzenie. Na przykład oświadczenie A= Matroskin- kot jest równoważne z powiedzeniem A = To nieprawda, że ​​Matroskin nie jest kotem.

Podobnie można wyprowadzić i zweryfikować następujące prawa:

Stałe właściwości:

Prawa idempotencji:

Bez względu na to, ile razy powtórzymy: Telewizor włączony lub telewizor włączony lub telewizor włączony... znaczenie zdania nie ulegnie zmianie. Podobnie z powtórzeń Na dworze ciepło, na dworze ciepło... ani jednego stopnia cieplej.

Prawa przemienności:

A v B = B v A

A i B = B i A

operandy A I W w operacjach dysjunkcji i koniunkcji mogą być zamieniane.

Prawa asocjatywności:

ZA v(B v C) = (A v B) v C;

A i (B i C) = (A i B) i C.

Jeśli wyrażenie wykorzystuje tylko operację łączenia lub tylko operację łączenia, możesz pominąć nawiasy lub ułożyć je dowolnie.

Prawa rozdzielności:

A v (B i C) = (A v B) & (A v C)

(dysjunkcja rozdzielcza
odnośnie koniunkcji)

A & (B v C) = (A & B) v (A & C)

(rozdzielność koniunkcji
odnośnie dysjunkcji)

Prawo rozdzielności koniunkcji w odniesieniu do rozdzielności jest podobne do prawa rozdzielności w algebrze, ale prawo rozdzielności w odniesieniu do koniunkcji nie ma odpowiednika, obowiązuje tylko w logice. Dlatego trzeba to udowodnić. Dowód najlepiej przeprowadzić za pomocą tabeli prawdy:

Prawa absorpcji:

A v (A i B) = A

A & (A przeciwko B) = A

Przeprowadź samodzielnie dowód praw absorpcji.

Prawa De Morgana:

Słowne sformułowania praw de Morgana:

Zasada mnemoniczna: po lewej stronie tożsamości operacja negacji stoi nad całym stwierdzeniem. Po prawej stronie wydaje się, że jest zerwana, a nad każdym z prostych zdań stoi negacja, ale jednocześnie zmienia się operacja: dysjunkcja do koniunkcji i odwrotnie.

Przykłady realizacji prawa de Morgana:

1) Oświadczenie To nieprawda, że ​​znam arabski czy chiński jest tożsamy ​​z oświadczeniem Nie znam arabskiego i nie znam chińskiego.

2) Oświadczenie To nieprawda, że ​​odrobiłem lekcję i dostałem z niej dwójkę jest tożsamy ​​z oświadczeniem Albo nie nauczyłem się lekcji, albo nie dostałem z niej piątki.

Zastąpienie operacji implikacji i równoważności

Operacje implikacji i równoważności czasami nie należą do operacji logicznych konkretnego komputera lub kompilatora z języka programowania. Jednak te operacje są niezbędne do rozwiązania wielu problemów. Istnieją zasady zastępowania tych operacji sekwencjami operacji negacji, alternatywy i koniunkcji.

Więc wymień działanie implikacje możliwe według następującej zasady:

Aby zastąpić operację równorzędność są dwie zasady:

Łatwo zweryfikować poprawność tych formuł, konstruując tablice prawdy dla prawej i lewej strony obu tożsamości.

Znajomość zasad zastępowania operacji implikacji i równoważności pomaga np. poprawnie skonstruować negację implikacji.

Rozważ następujący przykład.

Podajmy stwierdzenie:

E = To nieprawda, że ​​jeśli wygram konkurs, dostanę nagrodę.

Pozwalać A= wygram konkurs

B = Otrzymam nagrodę.

Stąd E = wygram konkurs, ale nie otrzymam nagrody.

Interesujące są również następujące zasady:

Możesz również udowodnić ich ważność za pomocą tabel prawdy.

Interesująca jest ich ekspresja w języku naturalnym.

Na przykład fraza

Jeśli Kubuś Puchatek zjadł miód, to jest pełny

jest identyczny z frazą

Jeśli Kubuś Puchatek nie jest pełny, oznacza to, że nie jadł miodu.

Ćwiczenia: pomyśl o wyrażeniach-przykładach dotyczących tych reguł.

2. Podstawowe pojęcia i definicje w dodatku 1

3. Materiał dla ciekawskich w dodatku 2

4. Praca domowa

1) Naucz się praw logiki, korzystając z kursu Algebra of Logic znajdującego się w przestrzeni informacyjnej (www.learning.9151394.ru).

2) Sprawdź dowód praw De Morgana na komputerze, konstruując tabelę prawdy.

Aplikacje

1. Podstawowe pojęcia i definicje (

Aby przekształcić funkcje, uprościć formuły otrzymane przez sformalizowanie warunków problemów logicznych, w algebrze logiki przeprowadza się przekształcenia równoważne, oparte na podstawowych prawach logicznych. Niektóre z tych praw są sformułowane i zapisane w taki sam sposób, jak podobne prawa w arytmetyce i algebrze, inne wyglądają niecodziennie.

Prawa algebry logiki są czasami nazywane twierdzenia.

W algebrze zdań prawa logiczne są wyrażone jako równość równoważnych formuł.

Ważność wszystkich praw można zweryfikować, konstruując tablice prawdy dla lewej i prawej części prawa pisanego. Po uproszczeniu wyrażenia za pomocą praw algebry logiki tablice prawdy są takie same.

Ważność niektórych praw można udowodnić za pomocą narzędzi tablic prawdy.

Obrazek 1.

Przykłady

Rysunek 3

Uprośćmy oryginalne wyrażenie, korzystając z podstawowych praw algebry logiki:

Rysunek 4

(prawo De Morgana, prawo rozdzielności dla AND, prawo idempotencji, działanie zmiennej z jej inwersją).

Z tabeli wynika, że ​​dla wszystkich zestawów wartości zmiennych $x$ i $y$ wzór na rys. 2 przyjmuje wartość $1$, czyli jest identycznie prawdziwy.

Rysunek 6

Z tabeli widać, że wyrażenie źródłowe przyjmuje takie same wartości jak wyrażenie uproszczone na odpowiednich wartościach zmiennych $x$ i $y$.

Uprośćmy wyrażenie na ryc. 5, stosując podstawowe prawa algebry logiki.

Rysunek 7

(Prawo De Morgana, prawo absorpcji, prawo rozdzielności dla I).

Rysunek 9

Z tabeli wynika, że ​​dla wszystkich zestawów wartości zmiennych $x$ i $y$ formuła na rys. 8 przyjmuje wartość $0$, czyli jest identycznie fałszywa.

Uprośćmy wyrażenie, stosując prawa algebry logiki:

Rysunek 10.

Rysunek 12.

(prawo De Mogrgana, rozdzielcze).

Zróbmy tabelę prawdy dla wyrażenia z ryc. 11:

Rysunek 13.

Z tabeli widać, że wyrażenie na ryc. 11 w niektórych przypadkach przyjmuje wartość $1$, aw niektórych - $0$, czyli jest to wykonalne.

(reguła de Morgana, usuwamy wspólny czynnik, regułę działania zmiennej z jej odwróceniem).

(powtarza się drugi czynnik, co jest możliwe przy zastosowaniu prawa idempotentu; następnie łączy się dwa pierwsze i dwa ostatnie czynniki i stosuje się prawo klejenia).

(wprowadzamy pomocniczy czynnik logiczny

Istnieje pięć praw algebry logiki:

1. Prawo pojedynczych elementów

1*X=X
0*X=0
1+X=1
0 + X = X

To prawo algebry logiki wynika bezpośrednio z powyższych wyrażeń aksjomatów algebry logiki.

Dwa górne wyrażenia mogą być przydatne przy budowaniu przełączników, ponieważ poprzez przyłożenie logicznego zera lub jedynki do jednego z wejść elementu „2I” można albo przekazać sygnał na wyjście, albo utworzyć na wyjściu potencjał zerowy.

Drugim wariantem wykorzystania tych wyrażeń jest możliwość selektywnego zerowania niektórych cyfr liczby wielocyfrowej. Dzięki bitowemu zastosowaniu operacji „AND” można albo pozostawić poprzednią wartość cyfry, albo zresetować ją, przykładając jednostkę lub potencjał zerowy do odpowiednich cyfr. Na przykład wymagane jest zresetowanie cyfr 6, 3 i 1. Następnie:

Na powyższym przykładzie wykorzystania praw algebry logiki wyraźnie widać, że aby wyzerować niezbędne cyfry w masce (niższa liczba), w miejsce odpowiednich cyfr wpisuje się zera, a w pozostałych jedynki cyfry. W oryginalnym numerze (liczba górna) zamiast 6 i 1 cyfry występują jednostki. Po wykonaniu operacji „AND” w tych miejscach pojawiają się zera. Zamiast trzeciej cyfry w oryginalnym numerze jest zero. W otrzymanej liczbie zero jest również obecne w tym miejscu. Pozostałe cyfry, wymagane przez stan problemu, nie są zmieniane.

W ten sam sposób, za pomocą prawa pojedynczych elementów, jednego z podstawowych praw algebry logiki, możemy zapisać jednostki w cyfrach, których potrzebujemy. W takim przypadku konieczne jest użycie dwóch niższych wyrażeń prawa pojedynczych elementów. Dzięki bitowemu zastosowaniu operacji „LUB” można albo pozostawić poprzednią wartość cyfry, albo zresetować ją, przykładając potencjał zerowy lub jedności do odpowiednich cyfr. Niech będzie wymagane zapisywanie jednostek w 7 i 6 bitach liczby. Następnie:

Tutaj w masce (niższy numer) napisaliśmy jedynki w siódmym i szóstym bicie. Pozostałe bity zawierają zera, a zatem nie mogą zmienić stanu początkowego pierwotnej liczby, co widzimy w wyniku liczby pod linią.

Pierwsze i ostatnie wyrażenie prawa pojedynczych elementów pozwala na użycie większej liczby wejść jako elementów logicznych o mniejszej liczbie wejść. W tym celu nieużywane wejścia w obwodzie „AND” należy podłączyć do źródła zasilania, jak pokazano na rysunku 1:

Rysunek 1. Schemat „2I-NOT” zaimplementowany na elemencie logicznym „3I-NOT”

Jednocześnie niewykorzystane wejścia w obwodzie „LUB”, zgodnie z prawem pojedynczych elementów, należy podłączyć do wspólnego przewodu obwodu, jak pokazano na rysunku 2.

Rysunek 2. Układ „NOT” zaimplementowany na elemencie „2I-NOT”.

Następujące prawa algebry logiki, wynikające z aksjomatów algebry logiki, są prawami negacji.

2. Prawa negacji

A. Prawo elementów uzupełniających

Wyrażenia tego prawa algebry logiki są szeroko stosowane w celu zminimalizowania obwodów logicznych. Jeżeli możliwe jest wydzielenie takich podwyrażeń z ogólnego wyrażenia funkcji logicznej, to można zredukować wymaganą liczbę wejść elementów układu cyfrowego, a czasem nawet sprowadzić całe wyrażenie do stałej logicznej.

Innym szeroko stosowanym prawem algebry logiki jest prawo podwójnej negacji.

B. Dwa razy nie

Prawo podwójnej negacji stosuje się zarówno do uproszczenia wyrażeń logicznych (oraz w wyniku uproszczenia i obniżenia kosztów cyfrowych układów kombinatorycznych), jak i do wyeliminowania inwersji sygnałów po takich elementach logicznych jak „2I-NOT” i „2OR- NIE". W tym przypadku prawa algebry logiki umożliwiają realizację danych układów cyfrowych przy użyciu ograniczonego zestawu elementów logicznych.

C. Prawo logiki negatywnej

Prawo logiki negatywnej obowiązuje dla dowolnej liczby zmiennych. To prawo algebry logiki pozwala realizować za pomocą elementów logicznych „LUB” i odwrotnie: realizować funkcję logiczną „LUB” za pomocą elementów logicznych „ORAZ”. Jest to szczególnie przydatne w obwodach TTL, ponieważ łatwo jest zaimplementować bramki AND, ale raczej trudno jest zaimplementować bramki OR. Dzięki prawu logiki ujemnej możliwe jest zaimplementowanie elementów „OR” na elementach logicznych „AND”. Rysunek 3 przedstawia implementację elementu logicznego „2OR” na elemencie „ ” i dwóch falownikach.

Rysunek 3. Element logiczny „2OR” zaimplementowany na elemencie „2I-NOT” i dwóch falownikach

To samo można powiedzieć o schemacie montażu „LUB”. W razie potrzeby można go przekształcić w montaż „I” za pomocą falowników na wejściu i wyjściu tego obwodu.

3. Prawa kombinacyjne

Kombinacyjne prawa algebry logiki w dużej mierze odpowiadają kombinacyjnym prawom algebry zwykłej, ale są też różnice.

A. prawo tautologii (wielokrotne powtórzenie)

X + X + X + X = X
X * X * X * X = X

To prawo algebry logicznej pozwala na użycie bramek logicznych z większą liczbą wejść jako bramek z mniejszą liczbą wejść. Na przykład można zaimplementować dwuwejściowy obwód „2I” na elemencie logicznym „3I”, jak pokazano na rysunku 4:

Rysunek 4. Schemat „2I-NOT” zaimplementowany na elemencie logicznym „3I-NOT”

lub użyj obwodu „2NAND-NOT” jako normalnego falownika, jak pokazano na rysunku 5:

Rysunek 5. Układ „NOT” zaimplementowany na elemencie logicznym „2I-NOT”

Należy jednak ostrzec, że łączenie kilku wejść zwiększa prądy wejściowe elementu logicznego i jego pojemność, co zwiększa pobór prądu przez poprzednie elementy i niekorzystnie wpływa na szybkość całego układu cyfrowego.

Aby zmniejszyć liczbę wejść w elemencie logicznym, lepiej jest użyć innego prawa algebry logiki - prawa pojedynczych elementów, jak pokazano powyżej.

Kontynuujemy rozważania nad prawami algebry logiki:

B. prawo ruchu

ZA + B + C + RE = ZA + C + B + R

C. prawo kombinowane

ZA + B + C + RE = ZA + (B + C) + re = ZA + B + (C + C)

D. prawo dystrybucji

X1(X2 + X3) = X1X2 + X1X3 X1 + X2X3 = (X1 + X2)(X1 + X3) = /udowodnijmy to rozszerzając nawiasy/ =
= X1X1 + X1X3 + X1X2 + X2X3 = X1(1 + X3 + X2) + X2X3 = X1 + X2X3

4. Zasada absorpcji (jedna zmienna pochłania inne)

X1 + X1X2X3 = X1(1 + X2X3) = X1

5. Reguła klejenia (wykonywana tylko przez jedną zmienną)

Podobnie jak w zwykłej matematyce, w algebrze logiki istnieje pierwszeństwo operacji. Odbywa się to najpierw:

1. Akcja w nawiasach
2. Operacja z jednym operandem (operacja pojedyncza) - "NOT"
3. Spójnik - „i”
4. Alternatywa - „LUB”
5. Suma modulo dwa.

Operacje tej samej rangi są wykonywane od lewej do prawej w kolejności, w jakiej zapisano wyrażenie logiczne. Algebra logiki jest liniowa i obowiązuje w niej zasada superpozycji.

Literatura:

Wraz z artykułem „Prawa algebry logiki” czytamy:

Każdy układ logiczny bez pamięci jest całkowicie opisany tablicą prawdy... Aby zaimplementować tablicę prawdy, wystarczy wziąć pod uwagę tylko te wiersze...
http://strona internetowa/digital/SintSxem.php

Dekodery (dekodery) umożliwiają konwersję jednego typu kodu binarnego na inny. Na przykład...
http://strona internetowa/digital/DC.php

Dość często twórcy sprzętu cyfrowego napotykają przeciwny problem. Chcesz przekonwertować kod linii ósemkowej lub dziesiętnej na...
http://strona internetowa/digital/coder.php

Multipleksery to urządzenia pozwalające na podłączenie kilku wejść do jednego wyjścia...
http://strona internetowa/digital/MS.php

Urządzenia nazywane są demultiplekserami ... Istotną różnicą w stosunku do multipleksera jest ...
http://strona internetowa/digital/DMS.php

Jeśli weźmiemy pod uwagę zastosowanie rachunku zdań do analizy i optymalizacji obwodów stykowo-przekaźnikowych, obwodów automatyki i innych zastosowań, oraz poznanie. że zmniejszenie liczby elementów i/lub połączeń prowadzi do wzrostu niezawodności urządzeń wykorzystujących te układy, to staje się oczywiste, że ważne jest studiowanie takich wzorów w matematyce dyskretnej, które pozwalają na optymalizację samego wzoru.

Do praw, które umożliwiają redukcję elementów i operacji zdań logicznych, należą prawa absorpcji i klejenia.

Prawo absorpcji:

dla logicznego dodania: A  (A i B) = A ;

dla mnożenia logicznego: A & (A  B) = A .

Znajomość praw logiki pozwala sprawdzić poprawność rozumowania i dowodów. W oparciu o prawa można uprościć złożone wyrażenia logiczne. Ten proces zastępowania złożonej funkcji logicznej prostszą, ale równoważną funkcją nazywa się minimalizacją funkcji.

Niektóre przekształcenia formuł logicznych są podobne do przekształceń formuł w zwykłej algebrze (ujęcie w nawias wspólnego czynnika, użycie praw przemienności i asocjacji itp.), Inne są oparte na właściwościach, których nie mają zwykłe operacje algebry (wykorzystanie prawa dystrybucji dla koniunkcji, prawa absorpcji, wiązania, prawa de Morgana itp.).

Naruszenia praw logiki prowadzą do błędów logicznych i wynikających z nich sprzeczności.

8. Reguła klejenia

; (2.11)
. (2.12) Dowód (2.11): . Dowód(2.12):

9. Prawo uogólnionego klejenie . (2.13) . (2.14) Dowody (2.13): Dowód (2.14). Otwieramy nawiasy najpierw po lewej stronie równości (2.14), a następnie po jej prawej stronie. ; .

9. Reguła De Morgana

Prawa De Morgana (zasady de Morgana) - reguły logiczne łączące pary podwójnych operatorów logicznych za pomocą logicznej negacji.

Historia i definicja

Augustus de Morgan pierwotnie zauważył, że w klasycznej logice zdań prawdziwe są następujące relacje:

nie (P i Q) = (nie P) lub (nie Q)

nie (P lub Q) = (nie P) i (nie Q)

Zwykły zapis tych praw w logice formalnej to:

w teorii mnogości:

Formuły De Morgana mają zastosowanie do dowolnej liczby argumentów. Ilustrują one głęboką wzajemną symetrię operacji AND i OR: jeśli operacja AND selektywnie reaguje na koincydencję sygnałów bezpośrednich, to operacja OR selektywnie reaguje również na koincydencję ich inwersji. Element OR jest przezroczysty dla dowolnego sygnału, element AND - dla dowolnej inwersji. Za pomocą wzorów de Morgana można łatwo przełożyć obwody logiczne z bazy NOT, AND, OR, w której człowiek jest najbardziej przyzwyczajony do myślenia i tworzenia początkowych wyrażeń logicznych, na bazy odwracające, które najefektywniej realizuje technologia zintegrowana.

10. Przebicie strzałą

Strzałka przebicia (logiczne „LUB-NIE”) sprawozdania A I B jest nowym zdaniem, które będzie prawdziwe wtedy i tylko wtedy, gdy oba zdania są fałszywe.

Znak strzałki Pierce'a to ↓

Wartości funkcji przebić strzały przedstawione w tabeli:

Logiczny element operacji przebić strzały Jest:

Strzała Pierce'a- binarna operacja logiczna, funkcja boolowska na dwóch zmiennych. Wprowadzony przez Charlesa Peirce'a w latach 1880-1881.

Strzałka przebicia, zwykle oznaczona jako ↓, jest równoważna operacji NOR i jest przedstawiona w następującej tabeli prawdy:

Zatem stwierdzenie „X ↓ Y” oznacza „ani X, ani Y”. Zmiana miejsca operandów nie zmienia wyniku operacji.

		X ↓ Y

11. Udar Schaeffera- binarna operacja logiczna, funkcja boolowska na dwóch zmiennych. Wprowadzony przez Henry'ego Schaeffera w 1913 r. (określany w niektórych źródłach jako przerywana linia Czulkowa) kreska Schaeffera, zwykle oznaczana |, jest równoważna operacji NAND i jest przedstawiona w następującej tabeli prawdy:

Zatem stwierdzenie X | Y oznacza, że ​​X i Y są niekompatybilne, tj. nie są jednocześnie prawdziwe. Zmiana miejsca operandów nie zmienia wyniku operacji. Liczba pierwsza Schaeffera, podobnie jak strzała Pierce'a, stanowi podstawę dla przestrzeni funkcji boolowskich dwóch zmiennych. Oznacza to, że używając tylko pociągnięcia Schaeffera, możesz zbudować resztę operacji. Na przykład,

-negacja

Dysjunkcja

Spójnik

Stała 1

W elektronice oznacza to, że wystarczy jeden typowy element, aby zrealizować całą różnorodność schematów konwersji sygnałów reprezentujących wartości logiczne. Z drugiej strony takie podejście zwiększa złożoność obwodów realizujących wyrażenia logiczne, a tym samym zmniejsza ich niezawodność. Przykładem jest przemysłowa seria 155.

Element 2I-NOT (2-calowy NAND), który realizuje skok Schaeffera, jest oznaczony następująco (zgodnie ze standardami ANSI):

W normach europejskich przyjęto inne oznaczenie:

12. Klawisze diodowe. Informacje ogólne. Klucz elektroniczny to urządzenie, które może znajdować się w jednym z dwóch stabilnych stanów: zamkniętym lub otwartym. Podstawą klucza elektronicznego jest nieliniowy element aktywny (dioda półprzewodnikowa, tranzystor, tyrystor itp.) działający w trybie klucza. W zależności od rodzaju zastosowanego elementu nieliniowego klucze elektroniczne dzielą się na diodę, tranzystor, tyrystor itp.

klucze diodowe. Najprostszym rodzajem przełączników elektronicznych są przełączniki diodowe. Jako elementy aktywne stosowane są w nich diody półprzewodnikowe lub elektropróżniowe.

Przy dodatnim napięciu wejściowym dioda jest otwarta i przepływa przez nią prąd

, gdzie jest rezystancją przewodzenia diody.

Napięcie wyjściowe

.

Zwykle wtedy. Przy ujemnym napięciu wejściowym prąd przepływa przez diodę

,

gdzie jest rezystancja wsteczna diody.

W tym samym czasie napięcie wyjściowe

. Z reguły i . Po zmianie biegunowości diody wykres funkcji obróci się o kąt wokół początku układu współrzędnych.

Klawisze diodowe nie pozwalają na separację elektryczną obwodów sterujących i sterowanych, co często jest wymagane w praktyce. Do przełączania (przełączania) napięć i prądów, tzw. klucze diodowe. Obwody te pozwalają, po przyłożeniu określonego napięcia sterującego, zamknąć / otworzyć obwód elektryczny, przez który przesyłany jest użyteczny sygnał (prąd, napięcie). W najprostszych układach kluczy sam sygnał wejściowy może służyć jako sterowanie.

Mówiąc o przełącznikach diodowych, nie można nie wspomnieć o specjalnej klasie diod półprzewodnikowych - diodach p-i-n. Służą tylko do przełączania sygnałów radiowych i mikrofalowych. Jest to możliwe dzięki ich unikalnej właściwości - regulowanej przewodności przy częstotliwości sygnału. Taka regulacja jest zwykle przeprowadzana albo po przyłożeniu zewnętrznego stałego napięcia polaryzacji do diody, albo bezpośrednio przez poziom sygnału (w celu ograniczenia diod p-i-n).