Z Skrypty dla studentów Ekonofizyki UPGOW

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 1 Rachunek zdań 2 Funkcja zdaniowa 3 Kwantyfikatory 4 Algebra zbiorów, czyli działania na zbiorach 4.1 Iloczyn kartezjański zbiorów 5 Relacje 6 Funkcja jako szczególny przypadek relacji 7 Zadania

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.

Przykładowe 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