URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Bramka logiczna - element konstrukcyjny maszyn i mechanizmów (dziś zazwyczaj: układ scalony, choć podobne funkcje można zrealizować
Bramka logiczna - element konstrukcyjny maszyn i mechanizmów (dziś zazwyczaj: układ scalony, choć podobne funkcje można zrealizować
również za pomocą innych rozwiązań technicznych, np. hydrauliki czy pneumatyki), realizujący fizycznie pewną prostą funkcję logiczną, której
również za pomocą innych rozwiązań technicznych, np. hydrauliki czy pneumatyki), realizujący fizycznie pewną prostą funkcję logiczną, której
argumenty (zmienne logiczne) oraz sama funkcja mogą przybierać jedną z dwóch wartości, np. 0 lub 1 (zob. algebra Boole'a).
argumenty (zmienne logiczne) oraz sama funkcja mogą przybierać jedną z dwóch wartości, np. 0 lub 1 (zob. algebra Boole'a).
Podstawowymi elementami logicznymi, stosowanymi powszechnie w budowie układów logicznych, są elementy realizujące funkcje logiczne:
Podstawowymi elementami logicznymi, stosowanymi powszechnie w budowie układów logicznych, są elementy realizujące funkcje logiczne:
sumy (alternatywy), iloczynu (koniunkcji) i negacji. Są to odpowiednio bramki OR, AND i NOT. Za pomocą dwóch takich bramek (np. OR i
sumy (alternatywy), iloczynu (koniunkcji) i negacji. Są to odpowiednio bramki OR, AND i NOT. Za pomocą dwóch takich bramek (np. OR i
NOT lub AND i NOT) można zbudować układ, realizujący dowolną funkcję logiczną.
NOT lub AND i NOT) można zbudować układ, realizujący dowolną funkcję logiczną.
Bramki NAND (negacja koniunkcji), oraz NOR (negacja sumy logicznej) nazywa się funkcjonalnie pełnymi ponieważ przy ich użyciu (tzn.
Bramki NAND (negacja koniunkcji), oraz NOR (negacja sumy logicznej) nazywa się funkcjonalnie pełnymi ponieważ przy ich użyciu (tzn.
samych NAND lub samych NOR) można zbudować układ realizujący dowolną funkcję logiczną.
samych NAND lub samych NOR) można zbudować układ realizujący dowolną funkcję logiczną.
Dowolną bramkę logiczną można też skonstruować za pomocą pary bramek, np. za pomocą OR i NOT lub AND i NOT. Układy takie
Dowolną bramkę logiczną można też skonstruować za pomocą pary bramek, np. za pomocą OR i NOT lub AND i NOT. Układy takie
nazywamy układami zupełnymi.
nazywamy układami zupełnymi.
Bramkę logiczną XOR często wykorzystujemy w układach arytmetyki takich jak sumatory czy subtraktory.
Bramkę logiczną XOR często wykorzystujemy w układach arytmetyki takich jak sumatory czy subtraktory.
Bramka NOT - układ cyfrowy, bramka logiczna wykonująca logiczną negację [~].
Bramka NOT - układ cyfrowy, bramka logiczna wykonująca logiczną negację [~].
p ~p
p ~p
1 0
1 0
0 1
0 1
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Bramka AND - koniunkcja to zdanie złożone mające postać p i q , gdzie p, q są zdaniami. W rachunku zdań koniunkcję zapisuje się
Bramka AND - koniunkcja to zdanie złożone mające postać p i q , gdzie p, q są zdaniami. W rachunku zdań koniunkcję zapisuje się
symbolicznie jako:
symbolicznie jako:
Przez koniunkcję rozumie się też zdanie mające postać p(1) i ... i p(n). Koniunkcję można zdefiniować precyzyjniej jako dwuargumentowe
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 q
działanie określone w zbiorze zdań, które zdaniom p, q przyporządkowuje zdanie p i q
Działanie to pozostaje w ścisłym związku z działaniem przekroju zbiorów (patrz algebra zbiorów). Dlatego zdanie utworzone z innych zdań za
Działanie to pozostaje w ścisłym związku z działaniem przekroju zbiorów (patrz algebra zbiorów). Dlatego zdanie utworzone z innych zdań za
pomocą koniunkcji jest też nazywane iloczynem logicznym. Koniunkcję zdań uznaje się za prawdziwą wtedy i tylko wtedy, gdy oba zdania p,
pomocą koniunkcji jest też nazywane iloczynem logicznym. Koniunkcję zdań uznaje się za prawdziwą wtedy i tylko wtedy, gdy oba zdania p,
q są prawdziwe.
q są prawdziwe.
Uproszczony schemat bramki logicznej AND - iloczynu bitowego Symbol koniunkcji jako bramki logicznej:
Uproszczony schemat bramki logicznej AND - iloczynu bitowego Symbol koniunkcji jako bramki logicznej:
Tablica prawdy (1 oznacza zdanie prawdziwe 0 zaś zdanie fałszywe):
Tablica prawdy (1 oznacza zdanie prawdziwe 0 zaś zdanie fałszywe):
0 0 0
0 0 0
0 1 0
0 1 0
1 0 0
1 0 0
1 1 1
1 1 1
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Koniunkcja jest operacją dwuargumentową i charakteryzuje się następującymi cechami:
Koniunkcja jest operacją dwuargumentową i charakteryzuje się następującymi cechami:
- przemienność
- przemienność
- łączność
- łączność
Bramka NAND (funktor Sheffera, kreska Sheffera, dysjunkcja)  dwuargumentowa funkcja boolowska (funktor logiczny) realizująca
Bramka NAND (funktor Sheffera, kreska Sheffera, dysjunkcja)  dwuargumentowa funkcja boolowska (funktor logiczny) realizująca
zaprzeczoną koniunkcję (NOT AND) - jest fałszywa wtedy i tylko wtedy, gdy oba składniki są prawdziwe. Często przedstawiana jest
zaprzeczoną koniunkcję (NOT AND) - jest fałszywa wtedy i tylko wtedy, gdy oba składniki są prawdziwe. Często przedstawiana jest
symbolicznie jako , a w poręczniejszej notacji jako pionowa kreska "|", który oznacza logiczną negację koniunkcji dwóch argumentów. Jego
symbolicznie jako , a w poręczniejszej notacji jako pionowa kreska "|", który oznacza logiczną negację koniunkcji dwóch argumentów. Jego
znaczenie przedstawia poniższa tablica prawdy:
znaczenie przedstawia poniższa tablica prawdy:
A B A*B[neg]
A B A*B[neg]
0 0 1
0 0 1
0 1 1
0 1 1
1 0 1
1 0 1
1 1 0
1 1 0
Przy pomocy funktora NAND można zdefiniować wszystkie pozostałe funktory klasycznego rachunku zdań ((łac. p aut q). Jest to twierdzenie
Przy pomocy funktora NAND można zdefiniować wszystkie pozostałe funktory klasycznego rachunku zdań ((łac. p aut q). Jest to twierdzenie
amerykańskiego logika polskiego pochodzenia Henry Sheffera, które opublikował w 1913 roku w artykule 'A Set of Five Independent
amerykańskiego logika polskiego pochodzenia Henry Sheffera, które opublikował w 1913 roku w artykule 'A Set of Five Independent
Postulates for Boolean Algebras, with Application to Logical Constants'. Wcześniej na identyczny pomysł wpadł amerykański filozof Charles
Postulates for Boolean Algebras, with Application to Logical Constants'. Wcześniej na identyczny pomysł wpadł amerykański filozof Charles
Peirce (artykuł 'A Boolean Algebra with One Constant' z 1880 roku), lecz jego pomysł nie został dostrzeżony.
Peirce (artykuł 'A Boolean Algebra with One Constant' z 1880 roku), lecz jego pomysł nie został dostrzeżony.
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Inne funktory logiczne definiowane są w sposób następujący:
Inne funktory logiczne definiowane są w sposób następujący:
Realizacją operacji NAND w elektronice jest bramka logiczna NAND. Oznaczana jest symbolem:
Realizacją operacji NAND w elektronice jest bramka logiczna NAND. Oznaczana jest symbolem:
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Bramka OR - Alternatywa (suma logiczna) - w logice to:
Bramka OR - Alternatywa (suma logiczna) - w logice to:
Działanie dwuargumentowe określone w dowolnym zbiorze zdań bądz
w zbiorze funkcji zdaniowych, które zdaniom (funkcjom zdaniowym) p i
Działanie dwuargumentowe określone w dowolnym zbiorze zdań bądz
w zbiorze funkcji zdaniowych, które zdaniom (funkcjom zdaniowym) p i
q przypisuje zdanie (funkcję zdaniową) prawdziwe wtedy i tylko wtedy gdy prawdziwe jest przynajmniej jedno ze zdań (funkcji) p i q
q przypisuje zdanie (funkcję zdaniową) prawdziwe wtedy i tylko wtedy gdy prawdziwe jest przynajmniej jedno ze zdań (funkcji) p i q
Dwuargumentowy spójnik zdaniowy, oznaczany (łac. p vel q) o znaczeniu odpowiadającemu wyżej zdefiniowanemu działaniu określonemu w
Dwuargumentowy spójnik zdaniowy, oznaczany (łac. p vel q) o znaczeniu odpowiadającemu wyżej zdefiniowanemu działaniu określonemu w
zbiorze . Od poprzedniej definicji różni się tym, że jest definiowany na poziomie syntaktycznym, dzięki czemu unika się określania jego
zbiorze . Od poprzedniej definicji różni się tym, że jest definiowany na poziomie syntaktycznym, dzięki czemu unika się określania jego
dziedziny.
dziedziny.
Zdanie logiczne postaci , gdzie p i q są zdaniami.
Zdanie logiczne postaci , gdzie p i q są zdaniami.
Potoczne znaczenie słowa alternatywa jako dwóch wykluczających się możliwości odpowiada matematycznemu pojęciu alternatywy
Potoczne znaczenie słowa alternatywa jako dwóch wykluczających się możliwości odpowiada matematycznemu pojęciu alternatywy
wykluczającej, a nie klasycznej alternatywy przedstawianej w tym artykule.
wykluczającej, a nie klasycznej alternatywy przedstawianej w tym artykule.
Alternatywa pozostaje w ścisłym związku z dodawaniem zbiorów (patrz algebra zbiorów). Dlatego zdanie utworzone z innych zdań przy użyciu
Alternatywa pozostaje w ścisłym związku z dodawaniem zbiorów (patrz algebra zbiorów). Dlatego zdanie utworzone z innych zdań przy użyciu
alternatywy jest też nazywane sumą logiczną. Alternatywa jest prawdziwa, jeżeli którekolwiek z jej zdań składowych jest prawdziwe. W
alternatywy jest też nazywane sumą logiczną. Alternatywa jest prawdziwa, jeżeli którekolwiek z jej zdań składowych jest prawdziwe. W
przeciwnym razie alternatywa zdań jest fałszywa.
przeciwnym razie alternatywa zdań jest fałszywa.
Symbol alternatywy jako bramki logicznej:
Symbol alternatywy jako bramki logicznej:
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Bramka NOR - (funktor Pierce'a, binegacja)  dwuargumentowa funkcja boolowska (funktor logiczny) realizująca zaprzeczoną sumę logiczną
Bramka NOR - (funktor Pierce'a, binegacja)  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. Często przedstawiana pionowa kreska "|" przechodząca przez
(NOT OR) - jest prawdziwa wtedy i tylko wtedy, gdy oba składniki są fałszywe. Często przedstawiana pionowa kreska "|" przechodząca przez
symbol alternatywy "v" dwóch argumentów, co oznacza jej logiczną negację. Jego znaczenie przedstawia poniższa tablica prawdy:
symbol alternatywy "v" dwóch argumentów, co oznacza jej logiczną negację. Jego znaczenie przedstawia poniższa tablica prawdy:
A B A nor B
A B A nor B
0 0 1
0 0 1
0 1 0
0 1 0
1 0 0
1 0 0
1 1 0
1 1 0
NOR jest równoważna negacji sumy logicznej
NOR jest równoważna negacji sumy logicznej
a NOR b = NOT (a OR b)
a NOR b = NOT (a OR b)
NOR jest również równoważna iloczynowi negacji logicznych
NOR jest również równoważna iloczynowi negacji logicznych
a NOR b = (NOT a) AND (NOT b)
a NOR b = (NOT a) AND (NOT b)
Symbol zaprzeczenia alternatywy jako bramki logicznej:
Symbol zaprzeczenia alternatywy jako bramki logicznej:
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Za pomocą funkcji NOR możemy zdefiniować negację:
Za pomocą funkcji NOR możemy zdefiniować negację:
NOT a = a NOR a
NOT a = a NOR a
alternatywę:
alternatywę:
a OR b = NOT ( a NOR b) = ( a NOR b) NOR ( a NOR b )
a OR b = NOT ( a NOR b) = ( a NOR b) NOR ( a NOR b )
koniunkcję:
koniunkcję:
a AND b = NOT (( NOT a ) OR ( NOT b )) = ( NOT a ) NOR ( NOT b ) = ( a NOR a ) NOR ( b NOR b )
a AND b = NOT (( NOT a ) OR ( NOT b )) = ( NOT a ) NOR ( NOT b ) = ( a NOR a ) NOR ( b NOR b )
czyli dowolną funkcję logiczną. Dlatego też ta funkcja jest ważna (podobnie jak NAND).
czyli dowolną funkcję logiczną. Dlatego też ta funkcja jest ważna (podobnie jak NAND).
Bramka XOR - Alternatywa wykluczająca (alternatywa rozłączna, różnica symetryczna, suma modulo 2, kontrawalencja, XOR, exclusive or,
Bramka XOR - Alternatywa wykluczająca (alternatywa rozłączna, różnica symetryczna, suma modulo 2, kontrawalencja, XOR, exclusive or,
EOR) to logiczny funktor zdaniotwórczy (dwuargumentowa funkcja boolowska) .
EOR) to logiczny funktor zdaniotwórczy (dwuargumentowa funkcja boolowska) .
Różnica symetryczna zdań jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jedno ze zdań p,q jest prawdziwe:
Różnica symetryczna zdań jest prawdziwa wtedy i tylko wtedy, gdy dokładnie jedno ze zdań p,q jest prawdziwe:
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Ta bramka realizuje funkcję logiczną zwaną EXCLUSIVE-OR (WYA

CZNIE LUB - ALBO).
Ta bramka realizuje funkcję logiczną zwaną EXCLUSIVE-OR (WYA

CZNIE LUB - ALBO).
Funkcja XOR przyjmuje wartość 1 tylko wtedy, gdy argument p lub q jest równy 1.
Funkcja XOR przyjmuje wartość 1 tylko wtedy, gdy argument p lub q jest równy 1.
Innym oznaczeniem jest p V q
Innym oznaczeniem jest p V q
Tablica prawdy alternatywy wykluczającej:
Tablica prawdy alternatywy wykluczającej:
p q pVq
p q pVq
0 0 0
0 0 0
0 1 1
0 1 1
1 0 1
1 0 1
1 1 0
1 1 0
Funkcję bramki XOR można realizować również w poniższy sposób:
Funkcję bramki XOR można realizować również w poniższy sposób:
A
C
B
Przy użyciu funkcji XOR dla więcej niż dwóch argumentów wynik jest prawdziwy gdy nieparzysta liczba argumentów jest prawdą.
Przy użyciu funkcji XOR dla więcej niż dwóch argumentów wynik jest prawdziwy gdy nieparzysta liczba argumentów jest prawdą.
Operacja XOR jest przemienna:
Operacja XOR jest przemienna:
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Operacja XOR jest łączna:
Operacja XOR jest łączna:
Istnieje element neutralny; jest nim 0:
Istnieje element neutralny; jest nim 0:
Dla każdego elementu istnieje element odwrotny; jest nim ten sam element:
Dla każdego elementu istnieje element odwrotny; jest nim ten sam element:
Bramka XNOR - bramka logiczna realizująca funkcję negacji alternatywy wykluczającej (tzw. Bramka Równoważności).
Bramka XNOR - bramka logiczna realizująca funkcję negacji alternatywy wykluczającej (tzw. Bramka Równoważności).
Bramka ta neguje wynik bramki XOR czyli zwraca fałsz (0), jeśli dokładnie jedno z wejść: A lub B jest prawdą (1), a w przeciwnym wypadku
Bramka ta neguje wynik bramki XOR czyli zwraca fałsz (0), jeśli dokładnie jedno z wejść: A lub B jest prawdą (1), a w przeciwnym wypadku
zwraca prawdę. Innymi słowy bramka XNOR dopuszcza pojawienie się dwóch takich samych sygnałów na wejściu.
zwraca prawdę. Innymi słowy bramka XNOR dopuszcza pojawienie się dwóch takich samych sygnałów na wejściu.
Tablica prawdy XNOR
Tablica prawdy XNOR
A B Q
A B Q
0 0 1
0 0 1
0 1 0
0 1 0
1 0 0
1 0 0
1 1 1
1 1 1
URZ
DZENIA TECHNIKI KOMPUTEROWEJ
BRAMKI LOGICZNE, PODSTAWOWE DZIAA
ANIA LOGICZNE.
Tablice prawdy podstawowych bramek logicznych.
Tablice prawdy podstawowych bramek logicznych.