Liczby binarne i bramki logiczne

Zamiana liczb dziesiętnych na binarne

Za pomocą jednego bitu możemy zapisać dwie podstawowe cyfry binarne: 0 i 1, w zapisie dziesiętnym ich znaczenie jest takie samo.
Aby zapisać kolejne cyfry (2 i 3) należy skorzystać z dwóch bitów:

2 - 10
3 - 11

Wykorzystanie 3 bitów pozwoli na zapis kolejnych cyfr z systemu dziesiętnego:

4 - 100
5 - 101
6 - 110
7 - 111

Jak zamienić dowolną liczbę dziesiętną na binarną? Przykład (18 na zapis binarny):

liczba|reszta z dzielenia przez 2
    18|0
     9|1
     4|0
     2|0
     1|1

Następnie odczytujemy kolejność od dołu: 10010

Sprawdzenie:
Wartości z powyżej od dołu 1 2 4 9 18
Reszta z dzielenia przez 2 1 0 0 1 0
Potęgi dwójki malejąco 16 8 4 2 1

Spójrz teraz na dwa dolne rzędy i wykonaj następujące operacje:

(1)
\begin{equation} 1*16 + 0*8 + 0*4 + 1*2 + 0*1 = 16 + 2 = 18 \end{equation}

Można to także sprawdzić w Pythonie:

print(bin(18))

Zamiana liczby binarnej na dziesiętną

Uzyskaną liczbę binarną (10010) zamieńmy na dziesiętną.
Sposób bardziej przyzwoity i poprawny z matematycznego punktu widzenia niż przedstawiony powyżej:

(2)
\begin{equation} 1*2^4+0*2^3+0*2^2+1*2^1+0*2^0=1*2^4+1*2^1=16+2=18 \end{equation}

Dodawanie liczb binarnych

Prosty przykład:

  10=2
+ 01=1
--------
  11=3

Przykład z dwiema jedynkami w jednej kolumnie:

  001=1
+ 101=5
--------
  110=6

Dlaczego? Zaczynamy od prawej strony 1+1=10, dlatego na dole zapisujemy 0 i zapamiętujemy 1. W następnym kroku dodajemy 0+0+1 (zapamietane) co daje 1, które zapisujemy na dole. W ostatnim kroku dodajemy 0 + 1 i pod kreską zapisujemy 1.

Odejmowanie liczb binarnych

Prosty przykład:

  11=3
- 01=1
--------
  10=2

Przykład z zerem i jedynką w jednej kolumnie:

  101=5
- 011=3
--------
  010=2

Dlaczego? Zaczynamy od prawej strony 1-1=0, dlatego na dole zapisujemy 0. W następnym kroku odejmujemy 0-1, musimy zastosować metodę, którą znamy z tradycyjnego odejmowania, czyli "pożyczenie" (jeśli pożyczamy z wyższego 1 to de facto mamy 2 w zapisie dziesiętnym, 10 w zapisie binarnym) 1 z następnej kolumny, w ten sposób uzyskujemy 10-0-1 = 1 które zapisujemy na dole. W ostatnim kroku 0-0=0. Zapis 1-1 oznacza, że musimy "oddać" "pożyczoną" jedynkę.

Mnożenie liczb binarnych

   101=5
*  101=5
----------
   101
  000
+101
----------
 11001=25

Mnożymy tak jak robimy to w tradycyjnym mnożeniu. Wyniki zapisujemy poniżej. Uzyskane wyniki dodajemy.

Bramki logiczne

W elektronice (informatyce) wykorzystywane są następujące bramki logiczne:
bramki.png

Bramki na zdania

Teraz będziemy przekształcać bramki na zdania KRZ oraz tabelki prawdziwościowe.

Przykład 1

implikacja.png

Zapis zaczynamy od lewej strony, od dwóch wejść 'p' i 'q'. Pierwszy wyraz jest zanegowany (bramka not), więc:

(3)
\begin{align} \lnot p \end{align}

Drugi wyraz zostaje tak jak jest:

(4)
\begin{align} \lnot p q \end{align}

Bramka łącząca wszystko to bramka OR, więc ostatecznie:

(5)
\begin{align} \lnot p \lor q \end{align}

Ktoś spostrzegawczy mógł zauważyć, że taka formuła ma postać własnego spójnika logicznego.

Sprawdźmy jakiego.

p|q
----
0|0
0|1
1|0
1|1

Następnie negujemy pierwsze wejście (bramka NOT):

p|q|~p
---|----
0|0| 1
0|1| 1
1|0| 0
1|1| 0

W ostatnim kroku łączymy zanegowane p oraz q znakiem alternatywy:

p|q|~p|~pvq
---|--|----
0|0| 1|   1
0|1| 1|   1
1|0| 0|   0
1|1| 0|   1

Co to za funkcja/spójnik?

Przykład 2

zadanie.png

Tym razem mamy 3 wejścia. Nazwijmy je 'p','q','r'. Wejścia 'p' i 'q' połączone są bramką OR, więc:

(6)
\begin{align} p \lor q \end{align}

Wyjście bramki OR połączone jest z wejściem bramki NAND. Bramka NAND jest połączona również z wejściem 'r', co zapisujemy następująco:

(7)
\begin{align} (p \lor q) / r \end{align}

Zdania na bramki

Zakoduj swoje imię oraz pierwszą literę nazwiska za pomocą operacji XOR (https://crypto.stackexchange.com/a/19471). Prowadzącemu prześlij zakodowaną informację oraz klucz.

Wybierz dowolny aksjomat/tezę/tautologię KRZ i przedstaw go w postaci bramki logicznej. Polecam ten symulator w celu stworzenia bramki: https://logic.ly/demo. Należy użyć jak najmniejszej możliwej liczby bramek.
Przykład: mam taką formułę: ~(p^q). Jeśli ktoś w tym przypadku użyje AND i NOT zamiast NAND, nie otrzyma za to zadnie przynależnej mu części punktu. Dlaczego? Celem tego zadania jest zapoznanie się z jak największą liczbą istniejących bramek. Teoretycznie w KRZ możemy spowadzić każdą formułę do ciągów NOT i AND, ale czy o to chodzi? Dalszego istnieje więcej spójników/bramek?

Listę aksjomatów/tez znajdą Państwo w podręczniku Tadeusza Batoga, Podstawy logiki.

Pytanie które z pewnością pojawi się w Państwa głowach: jak przedstawić implikację? Powinni już to Państwo wiedzieć przeczytawszy materiały powyżej.

Jeśli prawo/przykład się powtórzy, wszystkie osoby używające tego przykładu dostaną 0 punktów. Proszę napisać nazwę prawa/aksjomatu, jeśli takowe on posiada.

Strona na licencji Creative Commons Attribution-ShareAlike 3.0. Autorzy: A. Czoska, M. Komosiński, B. Kowalczyk, A. Kupś, M. Lubawy