Z Skrypty dla studentów Ekonofizyki UPGOW
(→Algebra zbiorów, czyli działania na zbiorach) |
|||
(Nie pokazano 3 wersji pomiędzy niniejszymi.) | |||
Linia 8: | Linia 8: | ||
Logika zajmuje się badaniem zdań twierdzących i takimi zdaniami będziemy się teraz zajmować. Logika nie zajmuje się zdaniami np. pytającymi, którym nie można przyporządkować wartości logiczne (np. Jutro będzie padał deszcz.). Dla skrócenia zapisu jako zdanie będziemy rozumieli zdanie twierdzące, któremu można przypisać jedną z dwóch wartości logicznych. | Logika zajmuje się badaniem zdań twierdzących i takimi zdaniami będziemy się teraz zajmować. Logika nie zajmuje się zdaniami np. pytającymi, którym nie można przyporządkować wartości logiczne (np. Jutro będzie padał deszcz.). Dla skrócenia zapisu jako zdanie będziemy rozumieli zdanie twierdzące, któremu można przypisać jedną z dwóch wartości logicznych. | ||
- | Zdania mogą być proste albo złożone. Zdanie jest proste | + | Zdania mogą być proste albo złożone. Zdanie jest proste, gdy nie zawiera spójników logicznych. Zdanie jest złożone, gdy zawiera spójniki logiczne. |
{|class="wikitable" style="text-align: center;" | {|class="wikitable" style="text-align: center;" | ||
+ | |+Przykładowe spójniki logiczne | ||
|- | |- | ||
|Spójnik | |Spójnik | ||
Linia 18: | Linia 19: | ||
|...lub... | |...lub... | ||
|alternatywa, suma | |alternatywa, suma | ||
- | |''' | + | |'''<math>\lor</math>''' |
|- | |- | ||
|...i... | |...i... | ||
|koniunkcja, iloczyn | |koniunkcja, iloczyn | ||
- | |''' | + | |'''<math>\land</math>''' |
|- | |- | ||
|jeżeli...to... | |jeżeli...to... | ||
Linia 37: | Linia 38: | ||
|- | |- | ||
|} | |} | ||
- | Zauważmy, że argumentem negacji jest jedno zdanie | + | Zauważmy, że argumentem negacji jest jedno zdanie, natomiast pozostałe cztery spójniki łączą dwa zdania. Prawdziwość zdania złożonego zależy od: |
* wartości logicznej zdań prostych tworzących zdanie złożone, | * wartości logicznej zdań prostych tworzących zdanie złożone, | ||
* użytego spójnika. | * użytego spójnika. | ||
- | W przypadku zdania złożonego utworzonego z dwóch zdań | + | W przypadku zdania złożonego utworzonego z dwóch zdań '''<math>p</math>''' i '''<math>q</math>''' mamy cztery możliwości (po dwie 0 lub 1) wartości logicznych. Są one podane w poniższej tabeli, dla pięciu spójników. |
- | {| class="wikitable" style="text-align: center;" | + | {| class="wikitable" style="text-align: center;" |
|- | |- | ||
| <math>p</math> || <math>q</math> || <math>p \lor q </math> || <math> p \land q </math> || <math> p \Rightarrow q </math> || <math>p \Leftrightarrow q </math> || <math>\sim p </math> | | <math>p</math> || <math>q</math> || <math>p \lor q </math> || <math> p \land q </math> || <math> p \Rightarrow q </math> || <math>p \Leftrightarrow q </math> || <math>\sim p </math> | ||
Linia 55: | Linia 56: | ||
Wnioski z powyższej tabeli są następujące: | Wnioski z powyższej tabeli są następujące: | ||
- | * alternatywa dwóch zdań | + | * alternatywa dwóch zdań jest prawdziwa jeżeli chociaż jedno z nich jest prawdziwe, |
- | * koniunkcja dwóch zdań | + | * koniunkcja dwóch zdań jest prawdziwa jedynie wtedy gdy oba zdania są prawdziwe, |
- | * implikacja jest fałszywa jedynie wtedy gdy poprzednik (zdanie ''' | + | * implikacja jest fałszywa jedynie wtedy gdy poprzednik (zdanie '''<math>p</math>''') jest prawdziwy, a następnik (zdanie '''<math>q</math>''') jest fałszywy, |
- | * równoważność jest prawdziwa gdy wartość logiczna obu zdań | + | * równoważność jest prawdziwa gdy wartość logiczna obu zdań jest taka sama. |
- | Dla niektórych | + | Dla niektórych układów spójników łączących zdania otrzymujemy formuły które są prawdziwe '''''zawsze''''', czyli niezależnie od wartości logicznych zdań składowych. Takie wyrażenia nazywamy prawami rachunku zdań lub tautologiami. |
- | Poniżej przedstawiono przykłady tautologii (''' | + | Poniżej przedstawiono przykłady tautologii ('''<math>p</math>''', '''<math>q</math>''', '''<math>r</math>''' oznaczają zdania): |
* prawo podwójnego przeczenia: | * prawo podwójnego przeczenia: | ||
- | + | :<math>\sim (\sim p) \Leftrightarrow p</math> | |
- | :<math> | + | * prawo przemienności alternatywy: |
- | * prawo przemienności | + | :<math>(p \lor q) \Leftrightarrow (q \lor p)</math> |
- | + | ||
- | :<math>( | + | |
* prawo przemienności koniunkcji: | * prawo przemienności koniunkcji: | ||
- | + | :<math>(p \land q) \Leftrightarrow (q \land p)</math> | |
- | :<math>( | + | * prawo łączności alternatywy: |
- | * prawo łączności | + | :<math> p \lor (q \lor r) \Leftrightarrow (p \lor q) \lor r</math> |
- | + | ||
- | :<math> | + | |
* prawo łączności koniunkcji: | * prawo łączności koniunkcji: | ||
- | + | :<math> p \land (q \land r) \Leftrightarrow (p \land q) \land r</math> | |
- | :<math> | + | * prawo rozdzielności alternatywy względem koniunkcji: |
- | * prawo rozdzielności | + | :<math> p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)</math> |
- | + | ||
- | :<math> | + | |
* prawo rozdzielności koniunkcji względem alternatywy: | * prawo rozdzielności koniunkcji względem alternatywy: | ||
- | + | :<math> p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)</math> | |
- | :<math> | + | |
* I-sze prawo de Morgana: | * I-sze prawo de Morgana: | ||
- | + | :<math>\sim(p \land q ) \Leftrightarrow (\sim p) \lor (\sim q),</math> | |
- | :<math> | + | |
czyli zaprzeczenie koniunkcji jest równoważne alternatywie zaprzeczeń. | czyli zaprzeczenie koniunkcji jest równoważne alternatywie zaprzeczeń. | ||
* II-gie prawo de Morgana: | * II-gie prawo de Morgana: | ||
+ | :<math>\sim(p \lor q ) \Leftrightarrow (\sim p) \land (\sim q),</math> czyli zaprzeczenie alternatywy jest równoważne koniunkcji zaprzeczeń. | ||
+ | * prawo transpozycji: | ||
+ | :<math>p \Rightarrow q \Leftrightarrow (\sim q) \Rightarrow (\sim p).</math> | ||
<br> | <br> | ||
- | + | Prawdziwość praw rachunku zdań można sprawdzić m.in. metodą zero-jedynkową. W metodzie tej sprawdza się tautologię dla wszystkich układów wartości logicznych zdań składowych. | |
- | + | ||
- | Prawdziwość praw rachunku zdań można sprawdzić m.in. metodą zero-jedynkową. W metodzie tej sprawdza się tautologię dla wszystkich | + | W poniższych dwóch przykładach sprawdzimy: |
- | I-sze prawo de Morgana | + | * I-sze prawo de Morgana |
{| class="wikitable" style="text-align: center;" | {| class="wikitable" style="text-align: center;" | ||
|- | |- | ||
- | |<math>p</math> || <math>q</math> || <math>\sim p</math> || <math>\sim q</math> || <math>p \land q </math> || <math>\sim (p \land q)</math> || <math>\sim p \lor \sim q</math> | + | |<math>p</math> || <math>q</math> || <math>\sim p</math> || <math>\sim q</math> || <math>p \land q </math> || <math>\sim (p \land q)</math> || <math>(\sim p) \lor (\sim q)</math> |
|- | |- | ||
|1 || 1 || 0 || 0 || 1 || 0 || 0 | |1 || 1 || 0 || 0 || 1 || 0 || 0 | ||
Linia 107: | Linia 103: | ||
|0 || 0 || 1 || 1 || 0 || 1 || 1 | |0 || 0 || 1 || 1 || 0 || 1 || 1 | ||
|} | |} | ||
- | + | * oraz prawo rozdzielności koniunkcji względem alternatywy | |
{| class="wikitable" style="text-align: center;" | {| class="wikitable" style="text-align: center;" | ||
|- | |- | ||
Linia 129: | Linia 125: | ||
|- | |- | ||
|} | |} | ||
- | Jak widzimy odpowiednie kolumny w dwóch powyższych tabelach są identyczne co stanowi dowód tych tautologii, ponieważ równoważność jest prawdziwa | + | Jak widzimy odpowiednie kolumny w dwóch powyższych tabelach są identyczne co stanowi dowód tych tautologii, ponieważ równoważność jest prawdziwa, gdy wartości logiczne obu jej stron są takie same. |
== Funkcja zdaniowa == | == Funkcja zdaniowa == | ||
- | Funkcja zdaniowa zmiennej <math>x</math> <math> | + | Funkcja zdaniowa zmiennej <math>x \in X</math> (<math>x</math> należy do zbioru <math> X</math>) to wyrażenie w którym występuje zmienna <math>x</math> i które staje się zdaniem gdy w miejsce zmiennej <math>x</math> wstawimy element ze zbioru <math>X</math>. |
- | + | <!-- | |
+ | O prawdziwości (bądź nieprawdziwości) wartości logicznej zdania, otrzymanego z funkcji zdaniowej wnioskujemy przez wstawienie w miejsce zmiennej <math>x</math> elementu ze zbioru <math>X</math> | ||
+ | --> | ||
Przykłady funkcji zdaniowych: | Przykłady funkcji zdaniowych: | ||
* Dnia <math>x</math> w Katowicach padał deszcz. Ta funkcja zdaniowa staje się zdaniem (takim jakim zajmuje się logika), gdy za <math>x</math> wstawimy datę i wtedy można takiemu zdaniu nadać wartość logiczną. | * Dnia <math>x</math> w Katowicach padał deszcz. Ta funkcja zdaniowa staje się zdaniem (takim jakim zajmuje się logika), gdy za <math>x</math> wstawimy datę i wtedy można takiemu zdaniu nadać wartość logiczną. | ||
- | * <math> x < 5, x \textstyle \in R</math>. Ta funkcja zdaniowa jest prawdziwa np. dla <math>x = 3</math>, a jest fałszywa np. dla <math>x = 17,2</math>. I oczywiście po wstawieniu za <math>x</math> dowolnej liczby rzeczywistej od razu możemy określić wartość logiczną zdania powstałego z funkcji zdaniowej. | + | * <math> x < 5, x \textstyle \in \mathbb{R}</math>. Ta funkcja zdaniowa jest prawdziwa np. dla <math>x = 3</math>, a jest fałszywa np. dla <math>x = 17,2</math>. I oczywiście po wstawieniu za <math>x</math> dowolnej liczby rzeczywistej od razu możemy określić wartość logiczną zdania powstałego z funkcji zdaniowej. |
== Kwantyfikatory == | == Kwantyfikatory == | ||
W logice i matematyce stosuje się dwa rodzaje kwantyfikatorów: | W logice i matematyce stosuje się dwa rodzaje kwantyfikatorów: | ||
- | |||
<br> | <br> | ||
- | + | ||
- | <math>\bigvee_{x \in X} P(x)</math> czytamy jako: istnieje <math>x</math> należące do zbioru <math>X</math> takie, że spełniony jest warunek <math>P(x)</math> (lub ... że zachodzi warunek <math>P(x))</math>, | + | * <math>\textstyle \bigvee</math> - kwantyfikator szczegółowy będący odpowiednikiem ''istnieje''. |
+ | |||
+ | <math>\bigvee_{x \in \mathbb{X}} P(x)</math> czytamy jako: istnieje <math>x</math> należące do zbioru <math>\mathbb{X}</math> takie, że spełniony jest warunek <math>P(x)</math> (lub ... że zachodzi warunek <math>P(x))</math>, | ||
+ | |||
<math>\bigvee_{W(x)} P(x)</math> czytamy jako: istnieje <math>x</math> spełniające warunek <math>W(x)</math> takie, że zachodzi <math>P(x)</math>. | <math>\bigvee_{W(x)} P(x)</math> czytamy jako: istnieje <math>x</math> spełniające warunek <math>W(x)</math> takie, że zachodzi <math>P(x)</math>. | ||
- | + | ||
<br> | <br> | ||
- | + | ||
- | <math>\bigwedge_{x \in X} P(x)</math> czytamy jako: dla każdego <math>x</math> należącego do zbioru <math>X</math> spełniony jest warunek <math>P(x)</math> (lub ... zachodzi warunek <math>P(x)</math>), | + | * <math>\bigwedge</math> - kwantyfikator ogólny odpowiadający ''dla każdego''. |
+ | |||
+ | <math>\bigwedge_{x \in \mathbb{X}} P(x)</math> czytamy jako: dla każdego <math>x</math> należącego do zbioru <math>\mathbb{X}</math> spełniony jest warunek <math>P(x)</math> (lub ... zachodzi warunek <math>P(x)</math>), | ||
+ | |||
<math>\bigwedge_{W(x)} P(x)</math> czytamy jako: dla każdego <math>x</math> spełniającego warunek <math>W(x)</math> zachodzi <math>P(x)</math>. | <math>\bigwedge_{W(x)} P(x)</math> czytamy jako: dla każdego <math>x</math> spełniającego warunek <math>W(x)</math> zachodzi <math>P(x)</math>. | ||
- | Kwantyfikatory przekształcają funkcje zdaniowe w zdania, przy czym | + | <br> |
+ | |||
+ | Kwantyfikatory przekształcają funkcje zdaniowe w zdania, przy czym kwantyfikator szczegółowy, jak i kwantyfikator ogólny mogą przekształcić funkcję zdaniową w zdanie prawdziwe jak i fałszywe. Prawdziwość zdania zależy zarówno od rodzaju kwantyfikatora, jak i postaci funkcji zdaniowej. Ilustrują to poniższe 4 przykłady: | ||
+ | |||
+ | * <math>\bigwedge_{x \in \mathbb{R}} x ^ 2 + 1 > 0</math>, <br> kwantyfikator ogólny przekształcił funkcję zdaniową w zdanie prawdziwe, | ||
+ | * <math>\bigwedge_{x \in \mathbb{N}} x < 7</math>, <br> kwantyfikator ogólny przekształcił funkcję zdaniową w zdanie fałszywe, | ||
+ | * <math>\bigvee_{x \in \mathbb{R}} x\textstyle ^ 2 = 0</math>,<br> kwantyfikator szczegółowy przekształcił funkcję zdaniową w zdanie prawdziwe, | ||
+ | * <math>\bigvee_{x \in \mathbb{R}} x \textstyle ^ 2 < -1</math>,<br> kwantyfikator szczegółowy przekształcił funkcję zdaniową w zdanie fałszywe, | ||
+ | |||
+ | W rachunku kwantyfikatorów mamy, podobnie jak w rachunku zdań, prawa czyli tautologie. Tutaj ograniczymy się do podania dwóch praw de Morgana dla kwantyfikatorów wraz z przykładami. Pierwsze z nich ma postać | ||
+ | : <math>\sim \bigg( \bigwedge_{x \in \mathbb{X}} P(x) \bigg) \iff \bigg( \bigvee_{x \in \mathbb{X}} \sim P(x) \bigg).</math> | ||
+ | |||
+ | Możemy powiedzieć, że "nieprawda, że wszystkie liczby naturalne <math>n</math> są podzielne przez 3" co jest równoważne temu, że "istnieje taka liczba naturalna <math>n</math>, która nie jest podzielna przez 3". | ||
- | + | A drugie | |
- | + | : <math>\sim \bigg( \bigvee_{x \in \mathbb{X}} Q(x) \bigg) \iff \bigg( \bigwedge_{x \in \mathbb{X}} \sim Q(x) \bigg).</math> | |
- | + | ||
- | + | ||
- | + | Możemy powiedzieć, że "nieprawda, że istnieje liczba rzeczywista <math>x</math> której kwadrat jest równy -1" co jest równoważne temu, że "kwadraty wszystkich liczb rzeczywistych są różne od -1". | |
== Algebra zbiorów, czyli działania na zbiorach == | == Algebra zbiorów, czyli działania na zbiorach == | ||
Linia 168: | Linia 181: | ||
Zbiór możemy określić w jeden z dwóch następujących sposobów: | Zbiór możemy określić w jeden z dwóch następujących sposobów: | ||
* wymienienie jego elementów, oczywiście jedynie wtedy gdy liczba elementów zbioru jest skończona. Np. <math> A = \{a_{1}, a_{2},...,a_{n}\}</math>, zbiór ''n-elementowy'', | * wymienienie jego elementów, oczywiście jedynie wtedy gdy liczba elementów zbioru jest skończona. Np. <math> A = \{a_{1}, a_{2},...,a_{n}\}</math>, zbiór ''n-elementowy'', | ||
- | * podanie warunku, który muszą spełniać elementy należące do zbioru. Warunkiem tym może być funkcja zdaniowa. Np. <math>A = \{x: f(x)\}</math>, do zbioru A należą te elementy <math>x</math>, które spełniają warunek <math>f(x)</math>. Np. <math> B = \{n \in N: n\leq20\}</math>, do zbioru <math>B</math> należą liczby naturalne mniejsze lub równe 20. Oczywiście zbiór <math>B</math> moglibyśmy określić także w inny sposób, po prostu wymieniając jego elementy <math> A = \{x: 1,2,3,...,20\}. </math> | + | * podanie warunku, który muszą spełniać elementy należące do zbioru. Warunkiem tym może być funkcja zdaniowa. Np. <math>A = \{x: f(x)\}</math>, do zbioru <math>A</math> należą te elementy <math>x</math>, które spełniają warunek <math>f(x)</math>. Np. <math> B = \{n \in \mathbb{N}: n\leq20\}</math>, do zbioru <math>B</math> należą liczby naturalne mniejsze lub równe 20. Oczywiście zbiór <math>B</math> moglibyśmy określić także w inny sposób, po prostu wymieniając jego elementy <math> A = \{x: x \in \{1,2,3,...,20\}\}</math>, lub prościej <math>A = \{1,2,3,...,20\}. </math> |
Jak się dalej okaże ważnym zbiorem jest zbiór pusty <math>\oslash</math> do którego nie należy ani jeden element. | Jak się dalej okaże ważnym zbiorem jest zbiór pusty <math>\oslash</math> do którego nie należy ani jeden element. | ||
Podstawowe działania na zbiorach to: | Podstawowe działania na zbiorach to: | ||
* suma zbiorów | * suma zbiorów | ||
- | + | :<math>A \cup B = \{x: x \in A \lor x \in B\},</math> | |
- | :<math>A \cup B = \{x: x \in A \lor x \in B\}</math | + | czyli element <math>x</math> należy do sumy zbiorów <math>A</math> i <math>B</math>, jeżeli należy do jednego z nich, przy czym może również należeć do obu zbiorów. |
- | + | * iloczyn (przekrój) zbiorów | |
- | * iloczyn zbiorów | + | :<math> A \cap B = \{x: x \in A \land x \in B\}.</math> |
- | + | <br> czyli element <math>x</math> należy do iloczynu zbiorów <math>A</math> i <math>B</math> wtedy i tylko wtedy, gdy należy równocześnie do zbiorów <math>A</math> i <math>B</math>. | |
- | :<math> A \cap B = \{x: x \in A \land x \in B\}</math> | + | |
- | <br> czyli element <math>x</math> | + | |
* różnica zbiorów | * różnica zbiorów | ||
- | + | :<math> A \setminus B = \{x: x \in A \land x \notin B\}.</math> | |
- | :<math> A \setminus B = \{x: x \in A \land x \notin B\}</math> | + | czyli element <math>x</math> należy do różnicy zbiorów <math>A</math> i <math>B</math> wtedy i tylko wtedy, gdy należy do zbioru <math>A</math> i nie należy do zbioru <math>B.</math> |
- | + | * dopełnienie zbioru <math>A</math> do zbioru <math>X</math> | |
- | + | ||
- | + | ||
- | + | ||
- | + | ||
- | * | + | |
:<math> A' = X \setminus A,</math> | :<math> A' = X \setminus A,</math> | ||
- | + | czyli zbiory <math>A</math> i <math>A'</math> są zbiorami rozłącznymi, tzn. nie posiadają elementów wspólnych, a ich suma jest zbiorem <math>X</math>. Zbiory rozłączne pojawią się na zajęciach ze statystyki gdy będzie omawiane prawdopodobieństwo zajścia zdarzenia i zdarzenia przeciwnego. Pojęcie dopełnienia zbioru wprowadza się gdy zbiór <math>A</math> zawiera się z zbiorze <math>X</math> (relacja zawierania jest przedstawiona poniżej). | |
- | + | ||
+ | |||
+ | Bardzo ważną relacją pomiędzy zbiorami (relacja w zbiorze zbiorów) jest zawieranie się zbiorów | ||
+ | :<math> A \subset B \Leftrightarrow \bigwedge_{x} (x \in A \Rightarrow x \in B),</math> | ||
+ | tzn. jeżeli element <math>x</math> należy do zbioru <math>A</math> to jednocześnie należy do zbioru <math>B</math>. Relacja zawierania się zbiorów pozwala zdefiniować równość dwóch zbiorów, która zachodzi wtedy gdy zbiór <math>A</math> zawiera się w zbiorze <math>B</math> i jednocześnie zbiór <math>B</math> zawiera się w zbiorze <math>A</math>. | ||
+ | :<math> A = B \Leftrightarrow A \subset B \land B \subset A.</math> | ||
+ | Można podać szereg praw rachunku zbiorów, a niektóre z nich są odpowiednikiem wcześniej omawianych praw rachunku zdań. Do najważniejszych praw rachunku zbiorów należą: | ||
* prawa przemienności sumy i iloczynu zbiorów | * prawa przemienności sumy i iloczynu zbiorów | ||
- | + | :<math> A \cup B = B \cup A</math>, | |
- | :<math> A \cup B = B \cup A, | + | :<math> A \cap B = B \cap A</math>. |
* prawa łączności sumy i iloczynu zbiorów | * prawa łączności sumy i iloczynu zbiorów | ||
- | + | :<math> A \cup (B \cup C) = (A \cup B) \cup C</math>, | |
- | :<math> A \cup (B \cup C) = (A \cup B) \cup C, | + | :<math>A \cap (B \cap C) = (A \cap B) \cap C</math>. |
* prawa rozdzielczości | * prawa rozdzielczości | ||
- | + | :<math> A \cap (B \cup C) = (A \cap B) \cup (A \cap C)</math>, | |
- | :<math> A \cap (B \cup C) = (A \cap B) \cup (A \cap C), | + | :<math>A \cup (B \cap C) = (A \cup B) \cap (A \cup C)</math>. |
- | * prawa de Morgana | + | * prawa de Morgana |
- | + | ||
:<math> (A \cup B)' = A' \cap B'</math> | :<math> (A \cup B)' = A' \cap B'</math> | ||
dopełnienie sumy jest równe iloczynowi dopełnień, | dopełnienie sumy jest równe iloczynowi dopełnień, | ||
- | |||
:<math>(A \cap B)' = A' \cup B' </math> | :<math>(A \cap B)' = A' \cup B' </math> | ||
dopełnienie iloczynu jest równe sumie dopełnień, | dopełnienie iloczynu jest równe sumie dopełnień, | ||
- | * | + | * oraz |
- | + | :<math> A \cup A = A</math> | |
- | :<math> A \cup A = A | + | :<math>A \cap A = A</math> |
+ | :<math>A \cup \oslash = A</math> | ||
+ | :<math>A \cap \oslash = \oslash</math> | ||
===Iloczyn kartezjański zbiorów=== | ===Iloczyn kartezjański zbiorów=== | ||
- | + | Zanim omówimy iloczyn kartezjański zbiorów wprowadzimy pojęcie pary uporządkowanej <math>(x,y)</math> dwóch elementów, przy czym <math>x \in X</math> i <math>y \in Y</math>. Pierwszy element pary uporządkowanej <math>x</math> nazywamy poprzednikiem, a drugi <math>y</math> następnikiem. Dwie pary uporządkowane są sobie równe wtedy i tylko wtedy gdy ich poprzedniki i ich następniki są sobie równe | |
- | :<math>(x_{1},y_{1}) = (x_{2},y_{2}) \Leftrightarrow (x_{1} = x_{2} \land y_{1} = y_{2})</math> | + | :<math>(x_{1},y_{1}) = (x_{2},y_{2}) \Leftrightarrow (x_{1} = x_{2} \land y_{1} = y_{2}).</math> |
- | Iloczyn kartezjański <math>X \times Y</math> zbiorów <math>X</math> i <math>Y</math> | + | Iloczyn kartezjański <math>X \times Y</math> zbiorów <math>X</math> i <math>Y</math> |
+ | jest zbiorem wszystkich par uporządkowanych <math>(x, y)</math> takich, że <math>x \in X</math> i <math>y \in Y</math> | ||
:<math>X \times Y = \{(x,y): x \in X \land y \in Y\}. </math> | :<math>X \times Y = \{(x,y): x \in X \land y \in Y\}. </math> | ||
Linia 227: | Linia 239: | ||
Iloczyn kartezjański zbiorów | Iloczyn kartezjański zbiorów | ||
- | <math>X = \{1,2,3\} | + | <math>X = \{1,2,3\} \quad \text{ i } \quad Y = \{4,7\}</math> |
zawiera 6 par uporządkowanych | zawiera 6 par uporządkowanych | ||
- | <math>X \times Y = \{(1,4),(1,7),(2,4),(2,7),(3,4),(3,7)\}</math> | + | <math>X \times Y = \{(1,4),(1,7),(2,4),(2,7),(3,4),(3,7)\}.</math> |
Można tworzyć iloczyn kartezjański zbioru ze sobą, tzn. <math>X \times X</math>. Dla zbioru <math>X</math> z poprzedniego przykładu <math>X \times X</math> zawiera 9 par uporządkowanych | Można tworzyć iloczyn kartezjański zbioru ze sobą, tzn. <math>X \times X</math>. Dla zbioru <math>X</math> z poprzedniego przykładu <math>X \times X</math> zawiera 9 par uporządkowanych | ||
Linia 241: | Linia 253: | ||
== Relacje == | == Relacje == | ||
- | Relacją <math>\mathbf R</math> określoną na zbiorach <math>X</math> i <math>Y</math> nazywamy podzbiór <math>\mathbf R</math> iloczynu kartezjańskiego <math>X \times Y</math> tych zbiorów. Czyli elementy <math>x</math> i <math>y</math> spełniają relację <math>\mathbf R</math> wtedy i tylko wtedy,jeżeli para uporządkowana <math>(x,y)</math> należy do pewnego podzbioru <math>\mathbf R</math> iloczynu kartezjańskiego <math>X \times Y</math> <math> {x} \mathbf R y \Leftrightarrow (x,y) \in \mathbf R </math> | + | Relacją <math>\mathbf R</math> określoną na zbiorach <math>X</math> i <math>Y</math> nazywamy podzbiór <math>\mathbf R</math> iloczynu kartezjańskiego <math>X \times Y</math> tych zbiorów. Czyli elementy <math>x</math> i <math>y</math> spełniają relację <math>\mathbf R</math> wtedy i tylko wtedy, jeżeli para uporządkowana <math>(x,y)</math> należy do pewnego podzbioru <math>\mathbf R</math> iloczynu kartezjańskiego <math>X \times Y</math> |
+ | :<math> {x} \mathbf R y \Leftrightarrow (x,y) \in \mathbf R </math> | ||
+ | W powyższym wzorze pierwsze <math>\mathbf R</math> oznacza relację zachodzącą pomiędzy elementami <math>x</math> i <math>y</math>, natomiast drugie <math>\mathbf R</math> jest podzbiorem iloczynu kartezjańskiego zbiorów <math>X</math> i <math>Y</math>. Jeżeli <math>Y=X</math> to wtedy relacja <math>\mathbf R</math> jest określona w zbiorze <math>X</math>. | ||
- | Przykład | + | '''Przykład 1''' |
+ | |||
+ | Ze zbioru par uporządkowanych <math>X \times X</math> (zbiór <math>X</math> jest zbiorem z poprzedniego przykładu) wybrać tylko te dla których poprzednik jest mniejszy od następnika. Jak widać są trzy takie pary: (1,2), (1,3) oraz (2,3). | ||
+ | |||
+ | '''Przykład 2''' | ||
+ | |||
+ | Niech <math>X=\{1,4,5\},</math> a <math>Y=\{2,4\}</math>. Określamy następującą relację: | ||
+ | <math>\mathbf{R}=\{(x,y) \in X\times Y: x+y \, \, \text{jest liczbą parzystą}\}</math> | ||
+ | |||
+ | Zbiór będący iloczynem kartezjańskim zbiorów <math>X</math> i <math>Y</math> zawiera następujące pary uporządkowane | ||
+ | :<math>X \times Y=\{(1,2), (1,4), (4,2), (4,4), (5,2), (5,4)\}.</math> | ||
+ | Natomiast relacja <math>\mathbf{R}</math> zawiera dwie pary uporządkowane | ||
+ | :<math>\mathbf{R}=\{(4,2), (4,4)\}.</math> | ||
== Funkcja jako szczególny przypadek relacji == | == Funkcja jako szczególny przypadek relacji == | ||
Linia 249: | Linia 275: | ||
Funkcja określona na zbiorze <math> X \neq \oslash </math> o wartościach w zbiorze <math> Y \neq \oslash </math> to relacja <math> f \in X \times Y </math> spełniająca poniższe dwa warunki: | Funkcja określona na zbiorze <math> X \neq \oslash </math> o wartościach w zbiorze <math> Y \neq \oslash </math> to relacja <math> f \in X \times Y </math> spełniająca poniższe dwa warunki: | ||
- | * jest prawostronnie jednoznaczna: <math>\bigwedge_{x \in X} \bigwedge_{y_1, y_2 \in Y} (x,y_1) \in f \land (x,y_2) \in f \Rightarrow y_1 = y_2 </math> | + | * jest prawostronnie jednoznaczna: <math>\bigwedge_{x \in X} \bigwedge_{y_1, y_2 \in Y} \left[\ (x,y_1) \in f \ \land \ (x,y_2) \in f\ \right] \ \ \Rightarrow \ \ y_1 = y_2, </math> |
+ | |||
+ | * jej dziedziną jest zbiór <math> X </math>: <math>\bigwedge_{x \in X} \bigvee_{y \in Y} \ (x,y) \in f </math> | ||
- | + | Przy czym dziedziną relacji jest zbiór wszystkich elementów należących do zbioru <math>X</math>, które są w relacji z przynajmniej jednym elementem ze zbioru <math>Y</math>. | |
- | Relacja <math> f </math>, czyli funkcja <math> f </math> przyporządkowuje każdemu elementowi zbioru <math> X </math> (tzn. każdemu elementowi dziedziny funkcji) dokładnie jeden element <math> y \in Y </math> (element należący do zbioru wartości funkcji). Jest to prawostronna jednoznaczność. Zauważmy, że nie jest wymagana lewostronna jednoznaczność, czyli różnym wartościom <math> x \in X </math> mogą być przyporządkowane takie same wartości <math> y \in Y </math>. | + | Warunek prawostronnej jednoznaczności relacji stwierdza, że każdemu elementowi <math>x \in X</math> odpowiada co najwyżej jeden element <math>y \in Y</math> (mogą istnieć elementy <math>x</math> nie wchodzące w relację z żadnym <math>y</math>). Drugi warunek w definicji funkcji (odnoszący się do dziedziny relacji) oznacza, że każdemu elementowi <math>x \in X</math> odpowiada co najmniej jeden element <math>y \in Y</math>.Obydwa warunki łącznie stwierdzają, że każdemu elementowi <math>x \in X</math> odpowiada dokładnie jeden element <math>y \in Y</math>. |
+ | Relacja <math> f </math>, czyli funkcja <math> f </math> przyporządkowuje każdemu elementowi zbioru <math> X </math> (tzn. każdemu elementowi dziedziny funkcji) dokładnie jeden element <math> y \in Y </math> (element należący do zbioru wartości funkcji). | ||
+ | <!-- | ||
+ | Jest to prawostronna jednoznaczność. Zauważmy, że nie jest wymagana lewostronna jednoznaczność, czyli różnym wartościom <math> x \in X </math> mogą być przyporządkowane takie same wartości <math> y \in Y </math>. | ||
+ | --> | ||
== Zadania == | == Zadania == | ||
<ol> | <ol> | ||
# Zaznacz na rysunku zbiory | # Zaznacz na rysunku zbiory | ||
- | ##<math>\{(x, y) \in \ | + | ##<math>\{(x, y) \in \mathbb{R}: (x+y<2) \land (x<3)\} </math> |
- | ##<math>\{(x, y) \in \ | + | ##<math>\{(x, y) \in \mathbb{R}: (x^2+y^2=1) \land (2x=y) \}</math> |
- | #Dane są zbiory <math> | + | <!-- |
+ | #Dane są zbiory <math>X = \{n \in \mathbb{N}: 1 \le n \le 30\}</math>, <math>A = \{n \in \mathbb{N}: n = 2k\} </math>, <math>B = \{n \in \mathbb{N}: n \in \{1, 2, \ldots, 10\}\} </math>, <math>C = \{n \in \mathbb{N}: 6 \le n \le 15\} </math> | ||
#:Pokaż, że | #:Pokaż, że | ||
- | ##<math> (A \ | + | ##<math> (A \cap B)' = A' \cup B' </math> |
- | ##<math> (A \ | + | ##<math> (A \cup B)' = A' \cap B' </math> |
- | ##<math> (A \ | + | ##<math> (A \cup B) \cap B' = A \setminus B </math> |
- | ##<math> A \setminus B = (A' \ | + | ##<math> A \setminus B = (A' \cup B') </math> |
- | ##<math> (A \ | + | ##<math> (A \cup B) \setminus C = (A \setminus C) \cup (B \setminus C)</math> |
- | ##<math> A \setminus (B \setminus C) = (A \setminus B) \ | + | ##<math> A \setminus (B \setminus C) = (A \setminus B) \cup (A \cap C)</math> |
- | # Które z wyrażeń są, a które nie są prawami rachunku | + | --> |
- | ## <math> \sim(p \lor q) \Leftrightarrow (\sim p \land \sim q)</math> | + | # Które z wyrażeń są, a które nie są prawami rachunku zdań |
- | ## <math> (p \Rightarrow q) \Leftrightarrow (\sim p \Rightarrow \sim q) </math> | + | ## <math> \sim(p \lor q) \Leftrightarrow (\sim p) \land (\sim q)</math> |
- | ## <math> (p \land q) \Leftrightarrow \sim ( | + | ## <math> (p \Rightarrow q) \Leftrightarrow (\sim p) \Rightarrow (\sim q) </math> |
- | + | ## <math> (p \land q) \Leftrightarrow \sim ((\sim p) \lor (\sim q)) </math> | |
- | ## <math> (p \Leftrightarrow q) \Leftrightarrow (\sim p \Leftrightarrow \sim q) </math> | + | ## <math> (p \Leftrightarrow q) \Leftrightarrow ((\sim p) \Leftrightarrow (\sim q)) </math> |
- | ## <math> \sim(p \lor q) \Leftrightarrow (\sim p \lor \sim q) </math> | + | ## <math> \sim(p \lor q) \Leftrightarrow (\sim p) \lor (\sim q) </math> |
- | ## <math> \sim(p \lor q) \Leftrightarrow (\sim p \land \sim q) </math> | + | ## <math> \sim(p \lor q) \Leftrightarrow (\sim p) \land (\sim q) </math> |
# <math> X=\{1, 2, 3, 4\}, Y=\{3, 4, 5\} </math> | # <math> X=\{1, 2, 3, 4\}, Y=\{3, 4, 5\} </math> | ||
#: | #: | ||
Linia 282: | Linia 315: | ||
#: Wypisz pary uporządkowane, które są elementami następujących zbiorów: | #: Wypisz pary uporządkowane, które są elementami następujących zbiorów: | ||
#: | #: | ||
- | ## <math> \{x,y: x<y \} </math> | + | ## <math> \{(x,y): x<y \} </math> |
- | ## <math> \{x,y: x \ge y \} </math> | + | ## <math> \{(x,y): x \ge y \} </math> |
- | ## <math> \{x,y: x+y=6 \} </math> | + | ## <math> \{(x,y): x+y=6 \} </math> |
- | #Określ wartość logiczną | + | #Określ wartość logiczną wyrażeń (0 oznacza wartość logiczną fałsz, a 1 to wartość logiczna prawda) |
##<math> 0 \land (1 \lor 0) </math> | ##<math> 0 \land (1 \lor 0) </math> | ||
##<math> (0 \land 1 \lor 0) \land 1 </math> | ##<math> (0 \land 1 \lor 0) \land 1 </math> |
Aktualna wersja na dzień 08:53, 31 mar 2015
Celem tego krótkiego wykładu z logiki jest przypomnienie, bądź podanie, podstaw rachunku zdań i działań na zbiorach. Wprowadzimy także funkcję zdaniową, kwantyfikatory i relacje. A zakończymy zdefiniowaniem funkcji, która jest podstawowym pojęciem używanym w matematyce.
Spis treści |
Rachunek zdań
Każda nauka jest zbiorem zdań, które zwykle są ze sobą powiązane. Pomiędzy zdaniami zachodzą związki. Większość z tych zdań to zdania twierdzące, czyli takie którym można przyporządkować jedną z dwóch wartości logicznych:
- 1 - prawda,
- 0 - fałsz.
Logika zajmuje się badaniem zdań twierdzących i takimi zdaniami będziemy się teraz zajmować. Logika nie zajmuje się zdaniami np. pytającymi, którym nie można przyporządkować wartości logiczne (np. Jutro będzie padał deszcz.). Dla skrócenia zapisu jako zdanie będziemy rozumieli zdanie twierdzące, któremu można przypisać jedną z dwóch wartości logicznych.
Zdania mogą być proste albo złożone. Zdanie jest proste, gdy nie zawiera spójników logicznych. Zdanie jest złożone, gdy zawiera spójniki logiczne.
Spójnik | Nazwa | Symbol |
...lub... | alternatywa, suma | \(\lor\) |
...i... | koniunkcja, iloczyn | \(\land\) |
jeżeli...to... | implikacja, wynikanie | \(\Rightarrow\) |
wtedy i tylko wtedy | równoważność | \(\Leftrightarrow\) |
nieprawda, że | negacja, zaprzeczenie | \(\sim\) |
Zauważmy, że argumentem negacji jest jedno zdanie, natomiast pozostałe cztery spójniki łączą dwa zdania. Prawdziwość zdania złożonego zależy od:
- wartości logicznej zdań prostych tworzących zdanie złożone,
- użytego spójnika.
W przypadku zdania złożonego utworzonego z dwóch zdań \(p\) i \(q\) mamy cztery możliwości (po dwie 0 lub 1) wartości logicznych. Są one podane w poniższej tabeli, dla pięciu spójników.
\(p\) | \(q\) | \(p \lor q \) | \( p \land q \) | \( p \Rightarrow q \) | \(p \Leftrightarrow q \) | \(\sim p \) |
1 | 1 | 1 | 1 | 1 | 1 | 0 |
1 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 0 | 1 | 0 | 1 |
0 | 0 | 0 | 0 | 1 | 1 | 1 |
Wnioski z powyższej tabeli są następujące:
- alternatywa dwóch zdań jest prawdziwa jeżeli chociaż jedno z nich jest prawdziwe,
- koniunkcja dwóch zdań jest prawdziwa jedynie wtedy gdy oba zdania są prawdziwe,
- implikacja jest fałszywa jedynie wtedy gdy poprzednik (zdanie \(p\)) jest prawdziwy, a następnik (zdanie \(q\)) jest fałszywy,
- równoważność jest prawdziwa gdy wartość logiczna obu zdań jest taka sama.
Dla niektórych układów spójników łączących zdania otrzymujemy formuły które są prawdziwe zawsze, czyli niezależnie od wartości logicznych zdań składowych. Takie wyrażenia nazywamy prawami rachunku zdań lub tautologiami.
Poniżej przedstawiono przykłady tautologii (\(p\), \(q\), \(r\) oznaczają zdania):
- prawo podwójnego przeczenia:
\[\sim (\sim p) \Leftrightarrow p\]
- prawo przemienności alternatywy:
\[(p \lor q) \Leftrightarrow (q \lor p)\]
- prawo przemienności koniunkcji:
\[(p \land q) \Leftrightarrow (q \land p)\]
- prawo łączności alternatywy:
\[ p \lor (q \lor r) \Leftrightarrow (p \lor q) \lor r\]
- prawo łączności koniunkcji:
\[ p \land (q \land r) \Leftrightarrow (p \land q) \land r\]
- prawo rozdzielności alternatywy względem koniunkcji:
\[ p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)\]
- prawo rozdzielności koniunkcji względem alternatywy:
\[ p \land (q \lor r) \Leftrightarrow (p \land q) \lor (p \land r)\]
- I-sze prawo de Morgana:
\[\sim(p \land q ) \Leftrightarrow (\sim p) \lor (\sim q),\] czyli zaprzeczenie koniunkcji jest równoważne alternatywie zaprzeczeń.
- II-gie prawo de Morgana:
\[\sim(p \lor q ) \Leftrightarrow (\sim p) \land (\sim q),\] czyli zaprzeczenie alternatywy jest równoważne koniunkcji zaprzeczeń.
- prawo transpozycji:
\[p \Rightarrow q \Leftrightarrow (\sim q) \Rightarrow (\sim p).\]
Prawdziwość praw rachunku zdań można sprawdzić m.in. metodą zero-jedynkową. W metodzie tej sprawdza się tautologię dla wszystkich układów wartości logicznych zdań składowych.
W poniższych dwóch przykładach sprawdzimy:
- I-sze prawo de Morgana
\(p\) | \(q\) | \(\sim p\) | \(\sim q\) | \(p \land q \) | \(\sim (p \land q)\) | \((\sim p) \lor (\sim q)\) |
1 | 1 | 0 | 0 | 1 | 0 | 0 |
1 | 0 | 0 | 1 | 0 | 1 | 1 |
0 | 1 | 1 | 0 | 0 | 1 | 1 |
0 | 0 | 1 | 1 | 0 | 1 | 1 |
- oraz prawo rozdzielności koniunkcji względem alternatywy
\(p\) | \(q\) | \(r\) | \(q \lor r\) | \(p \land (q \lor r)\) | \(p \land q\) | \(p \land r\) | \((p \land q) \lor (p \land r)\) |
1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Jak widzimy odpowiednie kolumny w dwóch powyższych tabelach są identyczne co stanowi dowód tych tautologii, ponieważ równoważność jest prawdziwa, gdy wartości logiczne obu jej stron są takie same.
Funkcja zdaniowa
Funkcja zdaniowa zmiennej \(x \in X\) (\(x\) należy do zbioru \( X\)) to wyrażenie w którym występuje zmienna \(x\) i które staje się zdaniem gdy w miejsce zmiennej \(x\) wstawimy element ze zbioru \(X\). Przykłady funkcji zdaniowych:
- Dnia \(x\) w Katowicach padał deszcz. Ta funkcja zdaniowa staje się zdaniem (takim jakim zajmuje się logika), gdy za \(x\) wstawimy datę i wtedy można takiemu zdaniu nadać wartość logiczną.
- \( x < 5, x \textstyle \in \mathbb{R}\). Ta funkcja zdaniowa jest prawdziwa np. dla \(x = 3\), a jest fałszywa np. dla \(x = 17,2\). I oczywiście po wstawieniu za \(x\) dowolnej liczby rzeczywistej od razu możemy określić wartość logiczną zdania powstałego z funkcji zdaniowej.
Kwantyfikatory
W logice i matematyce stosuje się dwa rodzaje kwantyfikatorów:
- \(\textstyle \bigvee\) - kwantyfikator szczegółowy będący odpowiednikiem istnieje.
\(\bigvee_{x \in \mathbb{X}} P(x)\) czytamy jako: istnieje \(x\) należące do zbioru \(\mathbb{X}\) takie, że spełniony jest warunek \(P(x)\) (lub ... że zachodzi warunek \(P(x))\),
\(\bigvee_{W(x)} P(x)\) czytamy jako: istnieje \(x\) spełniające warunek \(W(x)\) takie, że zachodzi \(P(x)\).
- \(\bigwedge\) - kwantyfikator ogólny odpowiadający dla każdego.
\(\bigwedge_{x \in \mathbb{X}} P(x)\) czytamy jako: dla każdego \(x\) należącego do zbioru \(\mathbb{X}\) spełniony jest warunek \(P(x)\) (lub ... zachodzi warunek \(P(x)\)),
\(\bigwedge_{W(x)} P(x)\) czytamy jako: dla każdego \(x\) spełniającego warunek \(W(x)\) zachodzi \(P(x)\).
Kwantyfikatory przekształcają funkcje zdaniowe w zdania, przy czym kwantyfikator szczegółowy, jak i kwantyfikator ogólny mogą przekształcić funkcję zdaniową w zdanie prawdziwe jak i fałszywe. Prawdziwość zdania zależy zarówno od rodzaju kwantyfikatora, jak i postaci funkcji zdaniowej. Ilustrują to poniższe 4 przykłady:
- \(\bigwedge_{x \in \mathbb{R}} x ^ 2 + 1 > 0\),
kwantyfikator ogólny przekształcił funkcję zdaniową w zdanie prawdziwe, - \(\bigwedge_{x \in \mathbb{N}} x < 7\),
kwantyfikator ogólny przekształcił funkcję zdaniową w zdanie fałszywe, - \(\bigvee_{x \in \mathbb{R}} x\textstyle ^ 2 = 0\),
kwantyfikator szczegółowy przekształcił funkcję zdaniową w zdanie prawdziwe, - \(\bigvee_{x \in \mathbb{R}} x \textstyle ^ 2 < -1\),
kwantyfikator szczegółowy przekształcił funkcję zdaniową w zdanie fałszywe,
W rachunku kwantyfikatorów mamy, podobnie jak w rachunku zdań, prawa czyli tautologie. Tutaj ograniczymy się do podania dwóch praw de Morgana dla kwantyfikatorów wraz z przykładami. Pierwsze z nich ma postać
- \(\sim \bigg( \bigwedge_{x \in \mathbb{X}} P(x) \bigg) \iff \bigg( \bigvee_{x \in \mathbb{X}} \sim P(x) \bigg).\)
Możemy powiedzieć, że "nieprawda, że wszystkie liczby naturalne \(n\) są podzielne przez 3" co jest równoważne temu, że "istnieje taka liczba naturalna \(n\), która nie jest podzielna przez 3".
A drugie
- \(\sim \bigg( \bigvee_{x \in \mathbb{X}} Q(x) \bigg) \iff \bigg( \bigwedge_{x \in \mathbb{X}} \sim Q(x) \bigg).\)
Możemy powiedzieć, że "nieprawda, że istnieje liczba rzeczywista \(x\) której kwadrat jest równy -1" co jest równoważne temu, że "kwadraty wszystkich liczb rzeczywistych są różne od -1".
Algebra zbiorów, czyli działania na zbiorach
Zbiór jest pojęciem pierwotnym, czyli pojęciem którego nie definiujemy. Podobnie pojęciem pierwotnym jest punkt. Element \(\it{a}\) należy do zbioru \(A\) co zapisujemy jako \(\it{a} \in A \), bądź nie należy do zbioru \(A\) co zapisujemy jako \(\it{a} \notin A \). Zbiór możemy określić w jeden z dwóch następujących sposobów:
- wymienienie jego elementów, oczywiście jedynie wtedy gdy liczba elementów zbioru jest skończona. Np. \( A = \{a_{1}, a_{2},...,a_{n}\}\), zbiór n-elementowy,
- podanie warunku, który muszą spełniać elementy należące do zbioru. Warunkiem tym może być funkcja zdaniowa. Np. \(A = \{x: f(x)\}\), do zbioru \(A\) należą te elementy \(x\), które spełniają warunek \(f(x)\). Np. \( B = \{n \in \mathbb{N}: n\leq20\}\), do zbioru \(B\) należą liczby naturalne mniejsze lub równe 20. Oczywiście zbiór \(B\) moglibyśmy określić także w inny sposób, po prostu wymieniając jego elementy \( A = \{x: x \in \{1,2,3,...,20\}\}\), lub prościej \(A = \{1,2,3,...,20\}. \)
Jak się dalej okaże ważnym zbiorem jest zbiór pusty \(\oslash\) do którego nie należy ani jeden element.
Podstawowe działania na zbiorach to:
- suma zbiorów
\[A \cup B = \{x: x \in A \lor x \in B\},\] czyli element \(x\) należy do sumy zbiorów \(A\) i \(B\), jeżeli należy do jednego z nich, przy czym może również należeć do obu zbiorów.
- iloczyn (przekrój) zbiorów
\[ A \cap B = \{x: x \in A \land x \in B\}.\]
czyli element \(x\) należy do iloczynu zbiorów \(A\) i \(B\) wtedy i tylko wtedy, gdy należy równocześnie do zbiorów \(A\) i \(B\).
- różnica zbiorów
\[ A \setminus B = \{x: x \in A \land x \notin B\}.\] czyli element \(x\) należy do różnicy zbiorów \(A\) i \(B\) wtedy i tylko wtedy, gdy należy do zbioru \(A\) i nie należy do zbioru \(B.\)
- dopełnienie zbioru \(A\) do zbioru \(X\)
\[ A' = X \setminus A,\] czyli zbiory \(A\) i \(A'\) są zbiorami rozłącznymi, tzn. nie posiadają elementów wspólnych, a ich suma jest zbiorem \(X\). Zbiory rozłączne pojawią się na zajęciach ze statystyki gdy będzie omawiane prawdopodobieństwo zajścia zdarzenia i zdarzenia przeciwnego. Pojęcie dopełnienia zbioru wprowadza się gdy zbiór \(A\) zawiera się z zbiorze \(X\) (relacja zawierania jest przedstawiona poniżej).
Bardzo ważną relacją pomiędzy zbiorami (relacja w zbiorze zbiorów) jest zawieranie się zbiorów \[ A \subset B \Leftrightarrow \bigwedge_{x} (x \in A \Rightarrow x \in B),\] tzn. jeżeli element \(x\) należy do zbioru \(A\) to jednocześnie należy do zbioru \(B\). Relacja zawierania się zbiorów pozwala zdefiniować równość dwóch zbiorów, która zachodzi wtedy gdy zbiór \(A\) zawiera się w zbiorze \(B\) i jednocześnie zbiór \(B\) zawiera się w zbiorze \(A\). \[ A = B \Leftrightarrow A \subset B \land B \subset A.\] Można podać szereg praw rachunku zbiorów, a niektóre z nich są odpowiednikiem wcześniej omawianych praw rachunku zdań. Do najważniejszych praw rachunku zbiorów należą:
- prawa przemienności sumy i iloczynu zbiorów
\[ A \cup B = B \cup A\], \[ A \cap B = B \cap A\].
- prawa łączności sumy i iloczynu zbiorów
\[ A \cup (B \cup C) = (A \cup B) \cup C\], \[A \cap (B \cap C) = (A \cap B) \cap C\].
- prawa rozdzielczości
\[ A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\], \[A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\].
- prawa de Morgana
\[ (A \cup B)' = A' \cap B'\] dopełnienie sumy jest równe iloczynowi dopełnień, \[(A \cap B)' = A' \cup B' \] dopełnienie iloczynu jest równe sumie dopełnień,
- oraz
\[ A \cup A = A\] \[A \cap A = A\] \[A \cup \oslash = A\] \[A \cap \oslash = \oslash\]
Iloczyn kartezjański zbiorów
Zanim omówimy iloczyn kartezjański zbiorów wprowadzimy pojęcie pary uporządkowanej \((x,y)\) dwóch elementów, przy czym \(x \in X\) i \(y \in Y\). Pierwszy element pary uporządkowanej \(x\) nazywamy poprzednikiem, a drugi \(y\) następnikiem. Dwie pary uporządkowane są sobie równe wtedy i tylko wtedy gdy ich poprzedniki i ich następniki są sobie równe
\[(x_{1},y_{1}) = (x_{2},y_{2}) \Leftrightarrow (x_{1} = x_{2} \land y_{1} = y_{2}).\]
Iloczyn kartezjański \(X \times Y\) zbiorów \(X\) i \(Y\) jest zbiorem wszystkich par uporządkowanych \((x, y)\) takich, że \(x \in X\) i \(y \in Y\)
\[X \times Y = \{(x,y): x \in X \land y \in Y\}. \]
Przykład
Iloczyn kartezjański zbiorów
\(X = \{1,2,3\} \quad \text{ i } \quad Y = \{4,7\}\)
zawiera 6 par uporządkowanych
\(X \times Y = \{(1,4),(1,7),(2,4),(2,7),(3,4),(3,7)\}.\)
Można tworzyć iloczyn kartezjański zbioru ze sobą, tzn. \(X \times X\). Dla zbioru \(X\) z poprzedniego przykładu \(X \times X\) zawiera 9 par uporządkowanych
\(X \times X = \{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3),(3,1),(3,2),(3,3)\}\),
przy czym zgodnie z podaną wyżej definicją, pary uporządkowane \((1,3)\) i \((3,1)\) nie są sobie równe.
Relacje
Relacją \(\mathbf R\) określoną na zbiorach \(X\) i \(Y\) nazywamy podzbiór \(\mathbf R\) iloczynu kartezjańskiego \(X \times Y\) tych zbiorów. Czyli elementy \(x\) i \(y\) spełniają relację \(\mathbf R\) wtedy i tylko wtedy, jeżeli para uporządkowana \((x,y)\) należy do pewnego podzbioru \(\mathbf R\) iloczynu kartezjańskiego \(X \times Y\) \[ {x} \mathbf R y \Leftrightarrow (x,y) \in \mathbf R \] W powyższym wzorze pierwsze \(\mathbf R\) oznacza relację zachodzącą pomiędzy elementami \(x\) i \(y\), natomiast drugie \(\mathbf R\) jest podzbiorem iloczynu kartezjańskiego zbiorów \(X\) i \(Y\). Jeżeli \(Y=X\) to wtedy relacja \(\mathbf R\) jest określona w zbiorze \(X\).
Przykład 1
Ze zbioru par uporządkowanych \(X \times X\) (zbiór \(X\) jest zbiorem z poprzedniego przykładu) wybrać tylko te dla których poprzednik jest mniejszy od następnika. Jak widać są trzy takie pary: (1,2), (1,3) oraz (2,3).
Przykład 2
Niech \(X=\{1,4,5\},\) a \(Y=\{2,4\}\). Określamy następującą relację: \(\mathbf{R}=\{(x,y) \in X\times Y: x+y \, \, \text{jest liczbą parzystą}\}\)
Zbiór będący iloczynem kartezjańskim zbiorów \(X\) i \(Y\) zawiera następujące pary uporządkowane \[X \times Y=\{(1,2), (1,4), (4,2), (4,4), (5,2), (5,4)\}.\] Natomiast relacja \(\mathbf{R}\) zawiera dwie pary uporządkowane \[\mathbf{R}=\{(4,2), (4,4)\}.\]
Funkcja jako szczególny przypadek relacji
Funkcja określona na zbiorze \( X \neq \oslash \) o wartościach w zbiorze \( Y \neq \oslash \) to relacja \( f \in X \times Y \) spełniająca poniższe dwa warunki:
- jest prawostronnie jednoznaczna: \(\bigwedge_{x \in X} \bigwedge_{y_1, y_2 \in Y} \left[\ (x,y_1) \in f \ \land \ (x,y_2) \in f\ \right] \ \ \Rightarrow \ \ y_1 = y_2, \)
- jej dziedziną jest zbiór \( X \): \(\bigwedge_{x \in X} \bigvee_{y \in Y} \ (x,y) \in f \)
Przy czym dziedziną relacji jest zbiór wszystkich elementów należących do zbioru \(X\), które są w relacji z przynajmniej jednym elementem ze zbioru \(Y\).
Warunek prawostronnej jednoznaczności relacji stwierdza, że każdemu elementowi \(x \in X\) odpowiada co najwyżej jeden element \(y \in Y\) (mogą istnieć elementy \(x\) nie wchodzące w relację z żadnym \(y\)). Drugi warunek w definicji funkcji (odnoszący się do dziedziny relacji) oznacza, że każdemu elementowi \(x \in X\) odpowiada co najmniej jeden element \(y \in Y\).Obydwa warunki łącznie stwierdzają, że każdemu elementowi \(x \in X\) odpowiada dokładnie jeden element \(y \in Y\). Relacja \( f \), czyli funkcja \( f \) przyporządkowuje każdemu elementowi zbioru \( X \) (tzn. każdemu elementowi dziedziny funkcji) dokładnie jeden element \( y \in Y \) (element należący do zbioru wartości funkcji).
Zadania
- Zaznacz na rysunku zbiory
- \(\{(x, y) \in \mathbb{R}: (x+y<2) \land (x<3)\} \)
- \(\{(x, y) \in \mathbb{R}: (x^2+y^2=1) \land (2x=y) \}\)
- Które z wyrażeń są, a które nie są prawami rachunku zdań
- \( \sim(p \lor q) \Leftrightarrow (\sim p) \land (\sim q)\)
- \( (p \Rightarrow q) \Leftrightarrow (\sim p) \Rightarrow (\sim q) \)
- \( (p \land q) \Leftrightarrow \sim ((\sim p) \lor (\sim q)) \)
- \( (p \Leftrightarrow q) \Leftrightarrow ((\sim p) \Leftrightarrow (\sim q)) \)
- \( \sim(p \lor q) \Leftrightarrow (\sim p) \lor (\sim q) \)
- \( \sim(p \lor q) \Leftrightarrow (\sim p) \land (\sim q) \)
- \( X=\{1, 2, 3, 4\}, Y=\{3, 4, 5\} \)
- Podaj wszystkie elementy iloczynu kartezjańskiego \( X \times Y \).
- Wypisz pary uporządkowane, które są elementami następujących zbiorów:
- \( \{(x,y): x<y \} \)
- \( \{(x,y): x \ge y \} \)
- \( \{(x,y): x+y=6 \} \)
- Określ wartość logiczną wyrażeń (0 oznacza wartość logiczną fałsz, a 1 to wartość logiczna prawda)
- \( 0 \land (1 \lor 0) \)
- \( (0 \land 1 \lor 0) \land 1 \)
- \( 1 \lor (1 \land 1) \)
- \( [(0 \Rightarrow \sim 0) \land 0] \Leftrightarrow(0 \Rightarrow 1) \)
- \( (1 \Rightarrow 0) \land 0 \)
- \( (1 \lor 0) \land (0 \Rightarrow \sim 0) \land (0 \Leftrightarrow 1)\)
- Uzupełnij tabelę negacji.
p | ~p |
? | 1 |
0 | ? |