ZAGADNIENIA NA ROZMOWE KWALIFIKACYJNĄ –UNIWERSYTET ŚLĄSKI KATOWICE

RACHUNEK ZDAŃ I KWANTYFIKATORÓW

Wartościowaniem nazywamy funkcję, która każdej zmiennej zdaniowej przyporządkowuje wartość logiczną 0 (fałsz) lub 1 ( prawda). Funkcję taką w naturalny sposób można rozszerzyć na zbiór wszystkich formuł rachunku zdań.

Tautologią nazywamy formułę, która przy dowolnym wartościowaniu przybiera wartość logiczną 1.

Funktorem zdaniowym n- argumentowym (spójnikiem zdaniowym) nazywamy funkcję, która każdemu układowi ⟨x₁,…,x_n⟩, gdzie x_i jest bądź fałszem, bądź prawdą, przyporządkowuje wartość logiczną 0 lub 1. Mamy więc cztery funktory jednoargumentowe:

prawdziwość zdań	zaprzeczenie ∼p nie p	alternatywa p ∨ q p lub q	koniunkcja p ∧ q p i q	implikacja p ⇒ q jeśli p, to q	równoważność p ⇔ q p równoważne q
p	q
1 1 0 0	1 0 1 0	0 0 1 1	1 1 0 0	1 0 0 0	1 0 1 1

Prawa rachunku zdań
Nazwa
Zdanie
Zaprzeczenie zdania
Alternatywa zdań
Koniunkcja zdań
Implikacja zdań
Równoważność zdań
Przemienność alternatywy
Przemienność koniunkcji
Łączność alternatywy
Łączność koniunkcji
Rozdzielność alternatywy względem koniunkcji
Rozdzielność koniunkcji względem alternatywy
Prawa de Morgana

Kwantyfikatory i ich zaprzeczenie
Kwantyfikator
Nazwa
Ogólny
Szczegółowy

Niektóre prawa logiki
Nazwa prawa
Wyłączonego środka
Sprzeczności
Podwójnego przeczenia
Zaprzeczenia implikacji
Kontrapozycji
Sylogizmu
Odrywania
Pochłaniania
Prawo Claviusa
Prawo Dunsa-Scotusa
Prawo Pierce’a
Prawo de Morgana

ALGEBRA ZBIORÓW

Jeśli a jest elementem zbioru A , to piszemy a ∈ A.

Rachunek zbiorów
Nazwa
Zbiór
Dopełnienie zbioru
Suma zbiorów
Iloczyn zbiorów (część wspólna)
Zawieranie zbiorów
Równość zbiorów
Przemienność dodawania
Przemienność mnożenia
Łączność dodawania
Łączność mnożenia
Rozdzielność dodawania względem mnożenia
Rozdzielność mnożenia względem dodawania
Prawa de Morgana

Najważniejsze działania na zbiorach
Działanie
Suma zbiorów
Iloczyn zbiorów
Różnica zbiorów
Dopełnienie zbioru A do Ω
Różnica symetryczna
Iloczyn kartezjański

RELACJE

• Zwrotna – dla każdego x zachodzi xRx

• Relacja identyczności x = y, gdyż x = x;

• Relacja podzielności w zbiorze liczb całkowitych, gdyż x| x;

• Relacja ≤ w zbiorze liczb rzeczywistych, gdyż x ≤ x;

• Przeciwzwrotna – dla każdego x zachodzi ∼(xRx)

• Relacja < w zbiorze liczb rzeczywistych, gdyż nieprawdą jest, że x < x;

• Relacja bycia ojcem w zbiorze ludzi;

• Symetryczna –dla każdego x, y zachodzi xRy ⇒ yRx

• Relacja identyczności x = y, gdyż x = y  pociąga y = x;

• Relacja równoległości prostych na płaszczyźnie;

• Przeciw-symetryczna – dla każdego x, y zachodzi xRy ⇒ ∼(yRx)

• Relacja < w zbiorze liczb rzeczywistych, gdyż nieprawdą jest, że może zachodzić równocześnie x < y i y < x;

• Każda relacja przeciwzwrotna i przechodnia;

• Antysymetryczna – dla każdego x, y zachodzi (xRy∧yRx) ⇒ x = y

• Relacja ≤ w zbiorze liczb rzeczywistych;

• Relacja inkluzji ⊂ w dowolnej rodzinie zbiorów;

• Relacja podzielności | w zbiorze liczb naturalnych;

• Przechodnia – dla każdego x, y, z zachodzi (xRy∧yRz) ⇒ xRz

• Relacja ≤ w zbiorze liczb rzeczywistych;

• Relacja podzielności | w zbiorze liczb naturalnych;

• Równoważności – relacja zwrotna, symetryczna i przechodnia

• Relacja równoległości prostych na płaszczyźnie;

• Relacja równości liczb całkowitych

• Quasi- porządkująca– relacja zwrotna i przechodnia

• W zbiorze liczb całkowitych Z relacja taka, żekRl,gdy istnieje takie a ∈ Z, że ka = l;

• Częściowo porządkująca– relacja quasi-porządkująca i asymetryczna

• W zbiorze wszystkich funkcji rzeczywistych relacja ≤ dana wzorem f ≤ gwtedy, gdy dla każdego x,  f(x) ≤ g(x);

• Relacja zawierania ⊆ w dowolnej rodzinie zbiorów;

• Liniowo porządkująca– relacja częściowo porządkująca i taka, że dla każdego x, y : xRy ∨ yRx

• Relacja ≤ w zbiorze liczb rzeczywistych;

• Zbiór liniowo uporządkowany nazywamy łańcuchem;

• Dobrze porządkująca– relacja liniowo porządkująca i taka, że dla każdego niepustego A ⊂ Xw zbiorze liniowo uporządkowanym (A,  R|A)^a istnieje element pierwszy

• Zbiór liczb naturalnych jest dobrze uporządkowany przez relację ≤

• Funkcja– relacja f taka, że dla każdego x ∈ X istnieje dokładnie jeden y ∈ Y taki, że xfy

• Dziedzinę i przeciwdziedzinę definiuje się jak dla relacji;

FUNKCJE

Relację R ⊂ X × Y nazywamy funkcją, jeśli spełnia ona warunek

$$\bigwedge_{x \in X}^{}{\bigwedge_{y \in Y}^{}{\bigwedge_{z \in Y}^{}{\left( \left\langle x,y \right\rangle \in R \land \left\langle \text{x.z} \right\rangle \in R \Rightarrow y = z \right).}}}$$

Zamiast pisać ⟨x,y⟩ ∈ f piszemy f(x)=y.

Dziedziną (zbiorem argumentów) funkcji nazywamy zbiór Df określony warunkiem

$$x \in Df \Leftrightarrow \bigvee_{y}^{}{\left( \left\langle x,y \right\rangle \in f \right),\ \ czyli}\ \ x \in Df \Leftrightarrow \bigvee_{y}^{}{\left( f\left( x \right) = y \right).}\ $$

Przeciwdziedziną (zbiorem wartości) funkcji f nazywamy zbiór Wf określony warunkiem

$$y \in Wf \Leftrightarrow \bigvee_{x}^{}{\left( \left\langle x,y \right\rangle \in f \right),\ \ czyli}\ \ y \in Wf \Leftrightarrow \bigvee_{x}^{}{\left( f\left( x \right) = y \right).}$$

Przekształceniem (odwzorowaniem zbioru X w zbiór Y nazywamy funkcją f taką, że Df = X i Wf ⊂ Y.

Fakt, że f jest takim odwzorowaniem oznaczmy przez f : X → Y, a zbiór wszystkich takich odwzorowań oznaczamy przez ^XY.

Jeśli dana jest funkcja f ⊂ X × Y, to jest ona przekształceniem zbioru Df w zbiór Y.

Jeśli Df = X, to mówimy, że f jest funkcją całkowitą na X. Jeśli zaś Df ⊂ X,to mówimy o f, że jest funkcją częściowo określoną w X. tak więc każda funkcja jest funkcją częściową, każda funkcja częściowa jest całkowicie określona na swojej dziedzinie. Zbiór wszystkich funkcji częściowych określonych na X o wartościach Y oznaczamy ^XY. Mamy więc: $f \in_{\overset{\check{}}{}}^{X}{Y \Leftrightarrow \bigvee_{X_{1} \in X}^{}{f \in_{}^{X_{1}}\text{Y.}}}$

Dla danych przekształceń f : X → Y,  g : Y → Z definiujemy przekształcenie g ∘ f : X → Z za pomocą wzoru $\left\langle x,z \right\rangle \in g \circ f \Leftrightarrow \bigvee_{y}^{}{\left( \left\langle x,y \right\rangle \in f \land \left\langle y,z \right\rangle \in g \right) \Leftrightarrow \bigvee_{y}^{}{\left\lbrack y = f\left( x \right) \land g\left( y \right) \right\rbrack.}}$

Przekształcenie g ∘ f nazywamy złożeniem funkcji (superpozycją ) przekształceń f i g . Działanie superpozycji jest łączne, tzn. h ∘ (g∘f) = (h∘g) ∘ f. natomiast nie jest ono przemienne.

Jeśli zbior X zawarty jest w Df, to obraz zbioru X jest zbiorem wartości funkcji f dla elementów zbioru X, czyli $f*X = \{ y:\bigvee_{x \in X}^{}{f\left( x \right) = y\}.}$

Jeśli f odwzorowuje zbiór X w zbiór Y, to f⁻¹ * Z, dla Z ⊂ Y, definiujemy jako {x:f(x)∈Z}. Zbiór f⁻¹ * Z nazywamy przeciw-obrazem Z przy odwzorowaniu f.

Odwzorowaniem różnowartościowym (funkcją różnowartościową) nazywamy odwzorowanie spełniające warunek $\bigwedge_{x}^{}{\bigwedge_{y}^{}{\lbrack f\left( x \right) = f(y) \Rightarrow x = y\ \ albo\ \ \bigwedge_{x}^{}{\bigwedge_{y}^{}{\left\lbrack x \neq y \Rightarrow f\left( x \right) \neq f\left( y \right) \right\rbrack.}}}}$

Piszemy wtedy f : XY.

Odwzorowaniem „na” nazywamy odwzorowanie f : X → Y spełniające warunek Wf = Y. Innymi słowy $\bigwedge_{y \in Y}^{}{\bigvee_{x \in X}^{}{\ \left( f\left( x \right) = y \right).}}$

Piszemy wtedy $f:X\overset{\rightarrow}{\text{na}}\text{Y.}$

Odwzorowanie różnowartościowe i „na” nazywamy wzajemnie jednoznacznym. Piszemy wtedy f : X_naY. jeśli f jest funkcją różnowartościową , to relacja f⁻¹ jest także funkcją. Nazywamy ją funkcją odwrotną . Jeśli f : X_naY, to f⁻¹ : Y_naX.

LICZBY NATURALNE, INDUKCJA MATEMATYCZNA I REKURENCJA

N- zbiór liczb naturalnych, tzn. całkowitych i dodatnich

Zasada indukcji matematycznej (zupełnej) mówi, że jeżeli

1. Pewna liczba naturalna n₀ ma własność W,

2. Z tego, że dowolna liczba naturalna k ≥ n₀ ma własność W, wynika, że liczba k + 1 ma własność W,

To każda liczba naturalna n ≥ n₀ ma własność W.

Funkcje rekurencyjne

Niech f : A₁ × …×A_n→𝒩. Jeśli A_i⊂𝒩 dla i ≤ n, to mówimy,że f jest określona na liczbach naturalnych . w szczególności , jeśli A₁ = A₂ = …=A_n=𝒩, to mówimy, że f jest określona na całym zbiorze liczb naturalnych.

Mówimy, że zbiór funkcji F jest zamknięty ze względu na n-argumentową operację ϑ jeśli z faktu, że f_i ∈ F dla i ≤ nwynika, że ϑ(f₁,…,f_n) ∈ F.

Niech teraz f będzie dowolną n + 1 argumentową funkcją. Funkcję g(x₁, …, x_n) określoną w następujący sposób:

g(x₁,…,x_n) = najmniejsze x takie,  ze f(x, x₁,…,x_n) = 0 oznaczamy przez (μx)[f(x, x₁,…,x_n)=0]. Tak więc została zdefiniowana pewna operacja Nan funkcjach zwana operacją minimum.

Jeżeli funkcja f jest, taka, że $\bigwedge_{x_{1}}^{}{\ldots\bigwedge_{x_{n}}^{}{\bigvee_{x}^{}{f\left( {x,x}_{1},\ldots,x_{n} \right) = 0,}}}$ to o operacji minimum zastosowanej do funkcji f mówimy, że jest efektywna. Operację minimum ograniczoną jedynie do funkcji mających powyższą własność nazywamy operacją minimum efektywnego.

Pewną modyfikacją operacji minimum jest operacja minimum ograniczonego, która funkcji f(x, x₁,…,x_n) przyporządkowuje funkcję g= (μx≤y)[f(x, x₁,…,x_n)=0] określona w następujący sposób:

$$g\left( y,\ x_{1},\ldots,x_{n} \right) = \left\{ \begin{matrix} \left( \text{μx} \right)\left\lbrack f\left( {x,x}_{1},\ldots,x_{n} \right) = 0 \land x \leq y \right\rbrack,\ \ \ \ \ \ \ \ \ \ \ \ jesli\ takie\ x\ istnieje \\ 0,\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ w\ przeciwnym\ wypadku \\ \end{matrix} \right.\ $$

Inną operacją określona na tej samej klasie funkcji jest operacja zwana definiowaniem przez indukcję. Często zwana też rekursją prostą.

Zbiór funkcji pierwotnie rekurencyjnych jest to najmniejszy zbiór funkcji , który zawiera funkcje

S(x) = x + 1 − nastepnika; I(x) = x − identycznosciowa;  I₂(x,y) = y − rzutowania; 0(x) = 0 − zerowa i jest zamknięty ze względu na operację rekursji prostej i superpozycji.

Zbior funkcji rekurencyjnych(obliczeniowych) określamy jako najmniejszy zbiór zawierający te same funkcje wyjściowe, tj. funkcje S(x),  I(x), I₂(x,y), 0(x) oraz zamknięty ze względu na operacje superpozycji , rekursji prostej i minimum efektywnego.

Zbiór funkcji częściowo rekurencyjnych jest to najmniejszy zbiór zawierający operacje S(x),  I(x), I₂(x,y), 0(x) oraz zamknięty ze względu na superpozycji, rekursji prostej i minimum.

Relację R o polu 𝒩 nazywamy pierwotnie rekurencyjną(względnie obliczalną), jeśli istnieje funkcja f pierwotnie rekurencyjna (obliczalna) taka, że R(m₁,…,m_n) ⇔ (m₁,…,m_n) = 0 .

W szczególności zbiór A ⊂ 𝒩 nazywamy pierwotnie rekurencyjnym(obliczalnym), jeśli istnieje taka funkcja f pierwotnie rekurencyjna (obliczalna), że m ∈ A ⇔ f(m) = 0.

Zbiór A ⊂ N jest natomiast zbiorem rekurencyjnie przeliczalnym, jeśli istnieje taka funkcja obliczalna f, że f * 𝒩=A.

RÓWNOLICZNOŚĆ ZBIORÓW

Mówimy, że zbiory A i B są równoliczne (symbolicznie A ∼ B), gdy istnieje bijekcja A → B.

Dla dowolnych zbiorów A, B, C mamy

(zwrotność) A ∼ A

(symetryczność) A ∼ B ⇒ B ∼ A

(przechodniość) A ∼ B ∧ B ∼ C ⇒ A ∼ C.

ZBIORY PRZELICZALNE I NIEPRZELICZALNE

Zbiór przeliczalny

Zbiór A ≠ 0 jest przeliczalny wtedy i tylko wtedy, gdy jest on zbiorem wyrazów pewnego ciągu

nieskończonego, czyli wtedy i tylko wtedy, gdy istnieje funkcja f przekształcająca zbiór wszystkich

liczb naturalnych na zbiór A

Zbiór przeliczalny zatem to zbiór skończony lub równoliczny ze zbiorem wszystkich liczb naturalnych.

Zbiory przeliczalne nieskończone są równej mocy. Moc zbiorów przeliczalnych nieskończonych oznaczamy

symbolem ℵ0 (czytaj: alef zero).

Przykłady zbiorów przeliczalnych:

- podzbiór zbioru przeliczalngo jest zbiorem przeliczalnym,

- suma dowolnej skończonej ilości zbiorów przeliczalnych jest zbiorem przeliczalnym,

- produkt kartezjański zbiorów przeliczalnych jest zbiorem przeliczalnym,

- zbiór wszystkich liczb całkowitych jest zbiotem przeliczalnym,

- zbiór wszystkich liczb wymiernych jest zbiotem przeliczalnym,

- zbiór wszystkich ciągów skończonych o wyrazach należących do ustalonego zbioru przeliczalnego jest zbiorem

przeliczalnym,

- zbiór wszystkich wielomianów jednej zmiennej o współczynnikach wymiernych jest przeliczalny,

- zbiór wszystkich liczb algebraicznych jest przeliczalny.

Zbiór nieprzeliczalny

Zbiór nieprzeliczalny to zbiór, który nie jest przeliczalny.

Zbiór liczb rzeczywistych przedziału <0, 1> jest zbiorem nieprzeliczalnym,

gdyż nie istnieje ciąg o wyrazach z przedziału <0, 1>, taki że każda liczba

rzeczywista z tego przedziału jest wyrazem ciągu.

Jeżeli zbiór A jest nieprzeliczalny i A ⊂ B,

to B jest również zbiorem nieprzeliczalnym. Z twierdzenia tego wynika, że

zbiór wszystkich liczb rzeczywistych jest nieprzeliczalny.

Moc zbioru wszystkich liczb rzeczywistych nazywamy continuum i oznaczamy

symbolicznie ℭ.

Zbiór wszystkich liczb niewymiernych jest zbiorem nieprzeliczalnym

Zbiór wszystkich liczb przestępnych jest nieprzeliczalny.

ZBIORY UPORZĄDKOWANE

Uploaded by freeXtreme