Pojęcie i ogólne własności funkcji.
Definicja
Funkcją odwzorowującą zbiór X w zbiór Y nazywamy
przyporządkowanie każdemu elementowi ze zbioru X dokładnie
jednego elementu ze zbioru Y.
Przykład
Te przyporządkowania są funkcjami.
Przykład
To przyporządkowanie nie jest funkcją, bo elementowi
a " X
przyporządkowuje dwa elementy 1 i 6 ze zbioru Y.
Przykład
To przyporządkowanie nie jest funkcją, bo elementowi nie
b " X
przyporządkowuje żadnego elementu ze zbioru Y.
Funkcję najczęściej oznaczamy małymi literami
f , g,h,....
Skrócony zapis funkcji odwzorowującej zbiór X w zbiór Y może być
następujący
f :X Y, x a y = f (x)
lub
.
y = f (x) dla x " X
Zbiór X nazywamy dziedziną funkcji, zbiór Y przeciwdziedziną,
a zbiór
{ }
f (X ) = y "Y : (" y = f (x) �" Y
x"X
nazywamy zbiorem wartości funkcji f.
Pamiętajmy, aby określić funkcję musimy podać
- zbiór argumentów funkcji (X),
- zbiór, w którym funkcja przyjmuje wartości (Y),
- jak wartości funkcji zależą od argumentów.
Przykład
Wzór
y = x2 nie określa funkcji, gdyż nie wiemy do jakiego zbioru
należą jej argumentu x. Niemniej jednak w wielu przypadkach
pomijamy tę informację, jeśli mamy pewność, że ktoś, kto czyta
napisany przez nas wzór wie, ze w takim wypadku dziedzina funkcji
jest dziedziną naturalną funkcji, czyli zbiorem tych wszystkich liczb
rzeczywistych x, dla których możemy obliczyć wartość funkcji.
Uwaga:
W dalszym ciągu, jeśli nie będzie to wyraz
nie powiedziane,
będziemy rozważali funkcje rzeczywiste zmiennej rzeczywistej,
tzn. takie, dla których dziedzina i zbiór wartości są podzbiorami
zbioru liczb rzeczywistych R.
Definicja
Wykresem funkcji y = f (x), x " D nazywamy zbiór
W = {(x, y)" R � R : x " D '" y = f (x)}.
f
Definicja
Jeżeli dla funkcji f : X Y zachodzi równość , to
f ( X ) = Y
funkcje f nazywamy funkcją odwzorowującą zbiór X na zbiór Y
(w skrócie  na ). Jeśli natomiast i , to
f ( X ) �" Y f ( X ) `" Y
mówimy, że funkcja f odwzorowuje zbiór X w zbiór Y.
Przykład
Funkcja f :R R określona wzorem y = 2x odwzorowuje zbiór R
y
na zbiór R, gdyż dla dowolnej liczby y " R istnieje x = taki, że
2
y = f (x).
Innymi słowy, liczby ze zbioru liczb rzeczywistych są wartościami
naszej funkcji (oczywiście każda dla innego x).
6
4
2
0
-3 -2 -1 1 2 3
x
-2
-4
-6
y = 2x
Rys. Wykres funkcji .
Przykład
Funkcja f :R R określona wzorem y = x2 odwzorowuje zbiór R w
R, a nie jest  na ponieważ przeciwdziedziną tej funkcji jest zbiór
[0;+") = R *"{0}.
+
25
20
15
10
5
0
-4 -2 2 4
x
Rys. Wykres funkcji y = x2. �%
Definicja
Rozważmy dwie funkcje f : X Y oraz g :Y Z .
Założeniem (superpozycją) funkcji f i g nazywamy funkcję
h : X Z
określoną wzorem
h(x) = g( f (x))
dla każdego x " X .
Funkcję h oznaczamy symbolem g o f .
Przykład
3
Wez
my pod uwagę funkcję f (x) = x + 5 oraz g(x) = x.
Założenie h = g o f określona jest wzorem
3
h(x) = g( f (x)) = g(x + 5) = x + 5 dla x " R.
Uwaga:
Składanie funkcji nie jest przemienne!
Kontynuując poprzedni przykład wyznaczymy złożenie f o g.
Niech k = f o g.
Wówczas
3 3
k(x) = f ((gx)) = f ( x)= x + 5.
3 3
Bez trudu zauważamy, że x + 5`" x + 5, co potwierdza, że
składanie funkcji nie jest przemienne.
Definicja
Funkcja f :X Y nazywamy różnowartościową, jeśli różnym
argumentom przyporządkowane są różne wartości funkcji.
Przykład
Funkcja na poniższym wykresie jest różnowartościowa.
4
2
0
-3 -2 -1 1 2 3
x
-2
-4
Rys. Przykład funkcji różnowartościowej
Przykład
Funkcja, której wykres przedstawiony jest poniżej nie jest
różnowartościowa, ponieważ różnym argumentom odpowiadają te
same wartości funkcji.
25
20
15
10
5
0
-4 -2 2 4
x
Rys. Wykres funkcji, która nie jest różnowartościowa
Definicja
Funkcję id :X Y określoną wzorem id (x) = x nazywany
x x
funkcją identycznościową na zbiorze X.
Inaczej mówiąc jest to funkcja, która dowolnemu elementowi x ze
zbioru X przypisuje ten sam element x.
Funkcja identycznościowa jest bardzo pomocna przy określeniu
funkcji odwrotnej, od której, mówiąc lapidarnie, żądamy, aby
stosując funkcje odwrotną do danej każdy element zbioru X  wrócił
na swoje miejsce bez możliwości pomyłki.
Definicja
Funkcję g:Y X nazywamy funkcją odwrotną do funkcji
f :X Y , jeżeli Y = f (X ), X = g(Y ) oraz dla każdego x " X
zachodzą równości
g o f = id '" f o g = id
X Y
Innymi słowy, aby istniała funkcja odwrotna do funkcji f :X Y
musi ona być różnowartościowa i odwzorowywać zbiór X  na zbiór
Y . O takiej funkcji mówimy też czasem, że jest wzajemnie
jednoznaczna.
-1
Funkcje odwrotną do funkcji f oznaczamy zwykle symbolem f .
Definicja
Funkcję f :D R, gdzie D �" R nazywamy rosnącą, gdy dla
dowolnych x , x " D spełniony jest warunek:
1 2
jeżeli x < x , to f (x ) < f (x ).
1 2 1 2
Inaczej mówiąc, gdy wraz ze wzrostem argumentów rosną wartości
funkcji.
Definicja
Funkcję f :D R, gdzie D �" R nazywamy malejącą, gdy dla
dowolnych x , x " D spełniony jest warunek:
1 2
jeżeli x < x , to f (x ) > f (x ).
1 2 1 2
Inaczej mówiąc, gdy wraz ze wzrostem argumentów maleją wartości
funkcji.
Definicja
Funkcję f :D R, gdzie D �" R nazywamy parzystą, jeżeli
1.x'" - x " D
"D
2.x'" f (-x) = f (x)
"D
Przykład
Funkcją parzystą jest funkcja f (x) = x2 określona dla x " R.
Własność:
Wykres funkcji parzystej jest symetryczny względem osi Oy.
Wniosek 1. Aby naszkicować wykres funkcji parzystej wystarczy
narysować jej wykres dla x e" 0 a następnie znalez
ć jego
symetryczne odbicie względem osi Oy.
Definicja
Funkcję f :D R, gdzie D �" R nazywamy nieparzystą, jeżeli
1.x'" - x " D
"D
2.x'" f (-x) = - f (x)
"D
Przykład
Funkcją nieparzystą jest funkcja f (x) = 2x określona dla x " R.
Własność:
Wykres funkcji nieparzystej jest symetryczny względem początku
układu współrzędnych, czyli punktu (0,0).
Wniosek 2. Aby naszkicować wykres funkcji nieparzystej wystarczy
narysować jej wykres dla x e" 0, a następnie znalez
ć jego
symetryczne odbici względem punktu (0,0).
Definicja
Funkcję f :D R, gdzie D �" R nazywamy funkcją okresową,
jeżeli istnieje liczba T `" 0 taka, że
1.x'" x + T " D
"D
2.x'" f (x + T ) = f (x)
"D
Funkcja okresowa ma nieskończenie wiele okresów. Są to liczby
będące całkowitymi wielokrotnościami liczby T, tzn. liczby postaci
k�"T dla k " Z .
Najmniejszy dodatni okres funkcji okresowej (o ile istnieje)
nazywamy okresem podstawowym.
Uwaga:
Funkcja okresowa może nie posiadać okresu podstawowego.
Przykładem takiej funkcji jest funkcja stała f (x) = a, a " R,
dla której każda liczba rzeczywista jest okresem.
Przykład
Funkcją okresową jest funkcja f :Z R określona wzorem
ńł0, gdy x nieparzysty
�ł
f (x) =
�ł
�ł
ół1, gdy x jest parzysty
Okresem podstawowym tej funkcji jest liczba 2, gdyż, jeśli x jest
liczba parzystą to x + 2 również i wtedy f (x + 2) = f (x) =1.
Jeśli natomiast x jest liczba nieparzystą, to nieparzysta jest też liczba
x + 2 i wówczas f (x + 2) = f (x) = 0. Stąd dla dowolnego
x " Z, f (x + 2) = f (x).
PODSTAWY LOGIKI I TEORII MNOGOŚCI
Pojęcia pierwotne logiki i teorii mnogości
I. zbiór
II. zdanie
III.wartość logiczna zdania
w(p)=1 zdanie jest prawdziwe
w(p)=0 zdanie p jest fałszywe
IV. x"X
Aksjomaty logiki i teorii mnogości
A1 Istnieje pewien zbiór
A2 Istnieje pewne zdanie
A3 Dla dowolnych zdań p, q istnieją zdania p (" q, p '" q,
p �! q, p �! q, ~ p, których wartość logiczna zależy jedynie od
wartości logicznych p i q w następujący sposób:
p q p '" q p (" q p �! q p �! q
~ p
1 1 0 1 1 1 1
1 0 0 0 1 0 0
0 1 1 0 1 1 0
0 0 1 0 0 1 1
Alternatywa wykluczająca  spójnik �", w informatyce EXOR
p q p �" q
1 1 0
1 0 1
0 1 1
0 0 0
Kreska Sheffera  spójnik ćł, w informatyce NAND
p q
p q
1 1 0
1 0 1
0 1 1
0 0 1
EXNOR : ~ ( p �" q)
Interpretacja implikacji p �! q
Warunek wystarczający: p jest warunkiem wystarczającym na
zajście q
Warunek konieczny: q jest warunkiem koniecznym na zajście p
Definicja Symbole nazywamy funktorami
'",(",�!, �!, ~,�",
zdaniotwórczymi
Definicja Litery symbolizujące zdania nazywać będziemy
zmiennymi zdaniowymi, zaś wyrażenie utworzone ze zmiennych
zdaniowych, funktorów zdaniotwórczych i ewentualnie nawiasów
nazywamy schematami zdań
Definicja Schematy zdań, które stają się zdaniami prawdziwymi
niezależnie od wartości logicznych tworzących je zdań nazywamy
tautologiami
Zasada ekstensjonalności:
Jeśli S1(p) jest dowolnym schematem rachunku zdań, S2(p) jest
schematem który powstaje z S1(p) przez zastąpienie wszystkich lub
niektórych symboli p symbolem q to schematy:
(p �! q) �! [S1( p) �! S2 (q)]
(p �! q) �! [S (q) �! S ( p)]
2 1
są prawami rachunku zdań.
Logiczna konsekwencja
� nazywamy logiczną konsekwencją ciągu ą1,& ,ąn jeśli przy
każdym układzie wartości logicznych przyporządkowanym
zmiennym zdaniowym występującym w ą1,& ,ąn, �, jeśli zdania
ą1,& ,ąn są zdaniami prawdziwymi, to � też jest zdaniem
prawdziwym.
Metody dowodzenia:
Dowód wprost:
H1 '" H '" ... '" H �! C
2 n
Dowód nie wprost:
~ C �! ~ (H '" H '" .... '" H )
1 2 n
Dowód nie wprost przez sprowadzenie do sprzeczności:
Jeśli to sprzeczność.
H '" H '" .... '" H '" ~ C
1 2
Reguły wnioskowania:
P P �! Q P �! Q P
regula regula sy log izmu
P P '" Q
P �! Q Q
, , , ~ Q , Q �! R ,
P (" Q P odrywania hipotetycznego
Q P '" Q
~ P P �! R
Przykłady tautologii
1) p(" ~ p
2) p �! ~ (~ p)
3) (( p �! q) '" (q �! r)) �! ( p �! r)
4) ( p �! q) �! (~ q �!~ p)
5) ( p (" q) �! (q (" p)
6) ( p '" q) �! (q '" p)
7) (p (" (q (" r)) �! (( p (" q) (" r)
8) (p '" (q '" r)) �! (( p '" q) '" r)
9) (p (" (q '" r)) �! (( p (" q) '" ( p (" r))
10) (p '" (q (" r)) �! (( p '" q) (" ( p '" r))
11) (~ ( p '" q)) �! (~ p(" ~ q)
12) (~ ( p (" q)) �! (~ p'" ~ q)
13) ~ ( p �! q) �! ( p'" ~ q)
14) ((~ p �!~ q) '" (~ p �! q))�! p
Rachunek zbiorów:
A4 Dla dowolnych zbiorów A, B istnieje zbiór dla którego
prawdziwe jest zdanie
x"A (" x"B , czyli w(x"A (" x"B)=1
Zbiór ten nazywamy sumą zbiorów A i B. Oznaczamy A*"B
Umowa: ~(x"X) a" x "X
A5 Dla dowolnych zbiorów A i B istnieje zbiór dla którego
prawdziwe jest zdanie x"A i x "B. Zbiór ten nazywamy
różnicą zbiorów A i B i oznaczamy A\B
Definicja Niech X będzie zbiorem, którego istnienie wynika
z aksjomatu A1 (A1 Istnieje pewien zbiór); na mocy
aksjomatu A5 istnieje zbiór X\X. Zbiór ten nazywamy
zbiorem pustym i oznaczamy symbolem ".
Uwaga w(x"")=0
Definicja Powiemy, że zbiory A i B są równe jeśli
w(x"A�!x"B)=1. Piszemy A=B.
Twierdzenie Niech A będzie dowolnym zbiorem.
Wówczas A\A=".
Definicja Powiemy, że zbiór A zawarty jest w zbiorze B (A
jest podzbiorem B) jeśli w(x"A�!x"B)=1.
Piszemy wtedy A�"B.
Twierdzenie Niech A i B będą dowolnymi zbiorami.
Wówczas:
I. "�"A
II. A�"A
III. A=B �! A�"B '" B�"A
Definicja Niech A i B będą dowolnymi zbiorami.
Zbiór A\ (A\B) nazywamy iloczynem zbiorów A i B
i oznaczamy go A)"B.
Twierdzenie Dla dowolnych zbiorów A i B ich iloczyn
A)"B={x: x"A '" x"B}
Prawa algebry zbiorów:
Niech A, B, C, X będą dowolnymi zbiorami. Wówczas:
I. A)"( B*"C ) = ( A)"B) *" (A)"C)
II. A*" (B)"C) = (A*"B) )" (A*"C)
III. X\(A*"B) = (X\A) )" (X\B)
IV. X\(A)"B) = (X\A) *" (X\B)
V. A)"B�"A i A)"B�"B
VI. A�"A*"B i B�"A*"B
VII. Niech A�"X i B�"X.
Wówczas A)"B=X�!A=X '" B=X
Definicja Niech A�"X. Zbiór X\A nazywamy dopełnieniem
zbioru A (do zbioru X) X\A oznaczamy A
Uwaga. Jeśli we własnościach od I do VII założymy, że
A�"X i B�"X to własności III oraz IV można zapisać w
postaci:
(A*"B) = A )" B (A)"B) = A *" B
Tak sformułowane własności III oraz IV noszą nazwę praw
de Morgana dla rachunku zbiorów
Definicja Jeśli w(a"A)=1 to mówimy, że a jest elementem
zbioru A.
Definicja Niech X będzie dowolnym zbiorem. Wyrażenie
�(x) zawierające zmienną x, które staje się zdaniem
(prawdziwym lub fałszywym) gdy w miejsce zmiennej x
wstawimy dowolny element zbioru X nazywamy funkcją
zdaniową, której zakresem zmienności jest zbiór X.
A6 Dla dowolnej funkcji zdaniowej �(x) której zakresem
zmienności jest zbiór X, istnieje zbiór tych elementów ze
zbioru X dla których �(x) jest zdaniem prawdziwym: {x"X:
w(�(x))=1}. Zbiór ten zapisujemy w postaci {x"X: �(x) } i
mówimy o nim jako o zbiorze tych elementów x"X, które
spełniają funkcję zdaniową �(x).
Twierdzenie: Niech ą(x) i �(x) będą funkcjami
zdaniowymi o zakresie X. Wówczas:
I. {x"X: ą(x) '" �(x) } = {x"X: ą(x) })" {x"X: �(x) }
II. {x"X: ą(x) (" �(x) } = {x"X: ą(x) }*" {x"X: �(x) }
III. {x"X: ą(x) '" ~�(x) } = {x"X: ą(x) }\ {x"X: �(x) }
IV. X \ {x"X: ą(x) } = {x"X: ~ą(x) }
Rachunek kwantyfikatorów:
Niech ą(x) będzie funkcją zdaniową, której zakresem zmienności
jest zbiór X. Wówczas:
'" �(x) oznacza, że { x"X: �(x)} = X
x"X
(" �(x) oznacza, że { x"X: �(x)} `""
x"X
Prawa de Morgana dla rachunku kwantyfikatorów
Niech ą(x) będzie funkcją zdaniową, której zakresem zmienności
jest zbiór X. Wówczas:
I. ~( '" ą(x) ) �! (" ~ ą(x)
x"X x"X
II. ~( (" ą(x) ) �! '" ~ ą(x)
x"X x"X
Prawa rozdzielności kwantyfikatorów względem funktorów
zdaniotwórczych:
'"�
1. '" (ą(x) '" � (x)) �! ('"ą(x) '" x"X (x))
x"X x"X
2. (" (ą(x) (" � (x)) �! ((" ą(x) (" (" � (x))
x"X x"X x"X
3. (" (ą(x) '" � (x)) �! ((" ą(x) '" (" � (x))
x"X x"X x"X
'"ą(x)
4. (x"X (" '" � (x)) �! '" (ą(x) (" � (x))
x"X x"X
5. '"(ą(x) �! � (x))
�! [ '" ą(x) �! '" � (x)]
x"X x"X x"X
6. '"(ą(x) �! � (x))
�! [(" ą(x)�!(" � (x)]
x"X x"X x"X
Przyjmijmy teraz, że S jest zdaniem lub funkcją zdaniową o zakresie
zmienności zawartym w zbiorze X, która nie zależy w sposób
efektywny od zmiennej x
2. '" S (" ą(x) �! S (" '" ą(x)
x"X x"X
3. '" S '" ą(x)�! S '" '" ą(x)
x"X x"X
4. (" S (" ą(x) �! S ("(" ą(x)
x"X x"X
5. (" S '" ą(x) �! S '" (" ą(x)
x"X x"X
Uwaga: '" ą(x) �! (" ą(x)
x"X x"X
Kwantyfikatory o zakresie ograniczonym:
Zapis '" �(x) oznacza '"(Ś(x) �! �(x))
.
Ś( x) x"X
Zapis (" �(x) oznacza ("(Ś(x) '" �(x))
.
Ś( x) x"X
A7 Dla dowolnego zbioru X istnieje zbiór złożony ze wszystkich
jego podzbiorów. Zbiór ten oznaczamy 2X i nazywamy zbiorem
potęgowym zbioru X. A"2X oznacza, że A�"X.
Iloczyn kartezjański:
Niech A`"", B`"", a"A i b"B.
Parą uporządkowaną o poprzedniku a i następniku b nazywamy zbiór
{ {a}, {a, b} } i piszemy (a,b).
A8 Niech A`"" i B`"". Istnieje wówczas zbiór złożony ze
wszystkich par uporządkowanych o poprzednikach ze zbioru A i
następnikach ze zbioru B. Symbolicznie piszemy A�B
A�B = { (a,b): a"A '" b"B }
Twierdzenie Niech �(x,y) będzie funkcją zdaniową której zakresem
zmienności jest zbiór X�Y. Wówczas:
I. '" '"�(x, y) �! '" '" �(x, y)
x"X y"Y y"Y x"X
II. (" ("�(x, y) �! (" (" �(x, y)
x"X y"Y y"Y x"X
III. (" '"�(x, y) �! '" (" �(x, y)
x"X y"Y y"Y x"X
TABELA 1
p (x) q (x) p(x) '" q(x) p(x) (" q(x)
P P P P
P F F P
P T T P
F P F P
F F F F
F T F T
T P T P
T F F T
T T F, T T, P
p (x) q (x) p(x) �! q(x) p(x) �! q(x) ~p(x)
P P P P F
P F F F
P T T T
F P P F P
F F P P
F T P T
T P P T T
T F T T
T T T, P F, T, P
TABELA 3
p (x) (" p(x) '" p(x)
x x
P 1 1
F 0 0
T 1 0
Relacje:
Definicja Każdy podzbiór iloczynu kartezjańskiego X�Y
nazywamy relacją w zbiorze X�Y. W przypadku, gdy X=Y o zbiorze
��"X�X mówimy, że jest relacją w zbiorze X.
Uwaga Zamiast pisać, że dla x"X i y"Y, (x,y)" � piszemy x�y.
Definicja Relację ��" X�X nazywamy relacją:
Zwrotną, jeśli '" x�x
x"X
przeciwzwrotną, jeśli '" ~( x�x )
x"X
symetryczną, jeśli '" '" ( x�y �! y�x )
x"X y"X
antysymetryczną jeśli '" '" [( x�y '" y�x ) �! x=y ]
x"X y"X
spójną, jeśli '" [ x=y (" x�y (" y�x ]
x, y"X
przechodnią, jeśli '" '" '" [ ( x�y '" y�z ) �! x�z ]
x"X y"X z"X
(częściowego) porządku, jeśli jest:
" zwrotna,
" antysymetryczna,
" przechodnia
Zbiór wraz z wprowadzoną w nim relacją porządku nazywamy
zbiorem uporządkowanym
Przykład: Relacja podzielności w zbiorze liczb naturalnych,
diagram Hassego
porządku liniowego, jeśli jest
" relacją porządku,
" spójna
Twierdzenie
W każdym niepustym zbiorze liniowo uporządkowanym
i skończonym istnieje element najmniejszy (pierwszy) i element
największy(ostatni).
równoważności, jeśli jest:
" zwrotna,
" symetryczna,
" przechodnia.
Oznaczenie: Relację równoważności będziemy oznaczać ~.
Definicja Niech x"X oraz (X,~). Zbiór [x]={t"X: x~t} nazywamy
klasą abstrakcji relacji ~.
Twierdzenie Niech (X,~). Wówczas:
'" [t]=[z] albo [t])"[z]="
t,z"X
Definicja Relację f �"D�P spełniająca warunek:
(*)'" (" x f y '" '"( x f z �! z=y )
x"D y"P z"P
nazywamy funkcją, której dziedziną jest zbiór D, a zbiorem wartości
zbiór P. Piszemy f : D P.
Zamiast pisać x f y bądz
(x,y)" f , piszemy y = f (x).
Warunek (*) zapisujemy też w postaci:
(**) '" ("! y = f (x)
x"D y"P
Definicja: Niech f : D P oraz "`"K�"D. Zdefiniujmy funkcję
f : K P następująco: '" f (x)= f (x). Funkcję taką nazywamy
K K
x"K
obcięciem funkcji f do zbioru K.
Definicja: Niech f : D P. Wykresem funkcji f nazywamy zbiór
W={ (x,y)" D�P: y = f (x)}
Definicja: Niech f : D P oraz A�"D i B�"P. Zbiór
{ }
f (A) = y " P : (" y = f (x) nazywamy obrazem zbioru A przy
x"A
odwzorowaniu f .
-1
Zbiór: f (B) = {x " D : f (x) " B} nazywamy przeciwobrazem
zbioru B przy odwzorowaniu f .
Definicja: Niech f : D P. Funkcję f nazywamy:
a) różnowartościową jeśli '" x `" y �! f (x) `" f (y)
x, y"D
b) odwzorowaniem  na jeśli '" (" y = f (x)
y"P x"D
c) odwzorowaniem wzajemnie jednoznacznym D na P jeśli jest
różnowartościowa i  na .
Niech X `" ", T `" ".
Rozważmy funkcję A: T2X. Jest to funkcja, która elementom
zbioru T przyporządkowuje podzbiory zbioru X. W przypadku takich
funkcji zamiast pisać A(t) piszemy At.
{At}
Definicja: Zbiór nazywamy indeksowaną rodziną
t"T
podzbiorów zbioru X.
{At}
Definicja: Niech będzie indeksowaną rodziną
t"T
podzbiorów pewnego ustalonego zbioru X.
{
U At = x " X : (" x " At }
Zbiór nazywamy sumą uogólnioną
t"T
t"T
{At}
rodziny .
t"T
{ }
I At = x " X : '" x " At nazywamy iloczynem
Zbiór
t"T
t"T
{At}
uogólnionym rodziny .
t"T
Twierdzenie Jeśli (X,~), to U [x] = X .
x"X
Równoliczność zbiorów:
Definicja: Powiemy, że zbiór A jest równoliczny ze zbiorem B jeśli
istnieje funkcja f odwzorowująca wzajemnie jednoznacznie A na B
f : AB.
w. j.
Piszemy wtedy A~B. Przyjmujemy, że " ~ ".
Twierdzenie: Dla dowolnych zbiorów A, B, C mamy:
I. A ~ A
II. A ~ B �! B ~ A
III. ( A ~ B '" B ~ C ) �! ( A ~ C )
Oznaczenie: Niech n"N P(n)={1, 2, & , n}
Definicja: Zbiór A nazywamy skończonym jeśli (" P(n) ~ A
n"N
Uwaga: Fakt, że zbiór A jest skończony i niepusty zapisujemy
=
A < �0
Definicja: Zbiór A nazywamy przeliczalnym jeśli jest on pusty lub
skończony, lub równoliczny ze zbiorem N liczb naturalnych.
=
Piszemy A d" �0.
Definicja: Zbiór A nazywamy nieprzeliczalnym gdy nie jest on
przeliczalny.
Własności zbiorów przeliczalnych
Twierdzenie: Na to by zbiór A`"" był przeliczalny potrzeba i
wystarcza by A był zbiorem wyrazów pewnego ciągu (niekoniecznie
różnowartościowego).
Twierdzenie: Każdy podzbiór zbioru przeliczalnego jest zbiorem
przeliczalnym. Każdy nadzbiór zbioru nieprzeliczalnego jest
nieprzeliczalny.
Twierdzenie: Dla dowolnych zbiorów przeliczalnych A i B
przeliczalnymi są również zbiory A)"B, A\B, A*"B.
Twierdzenie: Iloczyn kartezjański zbiorów przeliczalnych jest
zbiorem przeliczalnym.
Twierdzenie: Suma przeliczalnej ilości zbiorów przeliczalnych jest
zbiorem przeliczalnym.
Twierdzenie: Dla dowolnej funkcji obraz zbioru przeliczalnego jest
zbiorem przeliczalnym.
Twierdzenie Cantora: Przedział <0,1> jest nieprzeliczalny
Algebry Boole a
Definicja: Algebra Boole a jest to zbiór B`"" z dwoma działaniami
dwuargumentowymi '" i (", działaniem jednoargumentowym  oraz
różnymi elementami 0 i 1, spełniającymi następujące prawa:
1.B a) } prawa przemienności
x("y
.
=
y("x
b
x'"y
)
=
y'"x
2.B a) } prawa łączności
(x("y)("z
.
=
x("(y("z)
b
(x'"y)'"z
)
= x'"
(y'"z)
3.B a) }
x("(y'"z) =
prawa rozdzielności
.
(x("y)
'"(x("z)
b
x'"(y("z) =
)
(x'"y) ("
(x'"z)
4.B a) } prawa identyczności
x("0
.
= x
b
x'"1
)
= x
5.B a) } prawa dopełnienia
x("x
.
= 1
b
x'"x
)
= 0
Działanie (" nazywamy sumą, '" iloczynem, a działanie 
dopełnieniem.
Zasada dualności:
Jeśli zamienimy we wzorze prawdziwym we wszystkich algebrach
Boole a '" z (" oraz 1 i 0 to otrzymany wzór będzie prawdziwy we
wszystkich algebrach Boole a.
Twierdzenie: Następujące własności zachodzą w każdej algebrze
Boole a:
6.B. a) }
x("x = x
prawa
b)
x'"x = x
idempotentności
7.B a) } następne prawa
x("1 = 1
.
identyczności
b)
x'"0 = 0
8.B a) } prawa pochłaniania
(x'"y)("
.
x = x
b)
(x("y)'"
x = x
9.B a) } prawa de Morgana
(x("y)
.
= x '"y
b)
(x'"y)
= x ("y
Definicja: W algebrze Boole a definiuje się relację d" wzorem:
xd"y �! x("y=y
Uwaga: x < y oznacza, że x d" y oraz x`"y
x e" y oznacza, że y d" x
x > y oznacza, że y < x
Wniosek: W algebrze Boole a relację d" zdefiniowaną za pomocą
działania (" można zdefiniować za pomocą działania '" ponieważ
zachodzi
x("y = y �! x'"y = x
Twierdzenie W algebrze Boole a
a) x d" x
b) jeśli x d" y i y d" z to x d" z
c) jeśli x d" y i y d" x to x = y
d) jeśli x < y i y < z, to x < z
e) x'"y d" x d" x("y
f) 0 d" x d" 1
Definicja: Atomem w algebrze Boole a nazywamy niezerowy
element a, który nie może być przedstawiony w postaci a = b("c,
gdzie a`"b i a`"c.
Twierdzenie: Niezerowy element x z algebry Boole a jest atomem
wtedy i tylko wtedy, gdy nie istnieje element y taki, że 0Twierdzenie: Jeśli B jest skończoną algebrą Boole a, to każdy
niezerowy element z B może być przedstawiony w postaci sumy
różnych atomów. Ponadto sposób przestawienia jest jednoznaczny z
dokładnością do kolejności atomów.
Twierdzenie: Każda skończona algebra Boole a mająca n atomów
jest izomorficzna z algebrą Boole a P(S) wszystkich podzbiorów n-
elementowego zbioru S.
Definicja: Funkcją boolowską n-argumentową nazywamy funkcję f:
BnB, gdzie Bn =B�B�& �B (n czynników B), jest zbiorem ciągów
zerojedynkowych długości n. Zbiór wszystkich n-argumentowych
funkcji Boooleowskich oznaczamy symbolem BOO(n).
Definicja: Wyrażenie booleowskie jest to ciąg symboli wśród
których występują stałe 0 i 1, pewne zmienne oraz działania
booleowskie
Sieci logiczne:
NOT AND
OR NAND
NOR EXNOR