Z Skrypty dla studentów Ekonofizyki UPGOW

Wersja z 11:22, 18 lis 2013

Logika

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.

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 wtedy gdy można mu {od razu} przyporządkować wartość logiczną. Zadnie złożone jest zbudowane z dwóch lub więcej zdań prostych połączonych jednym z pięciu spójników (funktorów).

Zauważmy, że argumentem negacji jest jedno zdanie proste, natomiast w pozostałe cztery spójniki łączą dwa zdania proste. Prawdziwość zdania złożonego zależy od:

• wartości logicznej zdań prostych tworzących zdanie złożone,
• użytego spójnika (funktora).

W przypadku zdania złożonego utworzonego z dwóch zdań prostych 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 funktorów.

Wnioski z powyższej tabeli są następujące:

• alternatywa dwóch zdań prostych jest prawdziwa jeżeli chociaż jedno z nich jest prawdziwe,
• koniunkcja dwóch zdań prostych jest prawdziwa jednie 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ń prostych jest taka sama.

Dla niektórych kombinacji spójników łączących zdania proste otrzymujemy formuły których wartość logiczna jest prawdziwa 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 proste):

• prawo podwójnego przeczenia:

\(\textstyle \sim (\textstyle \sim) \textstyle \it p \textstyle \Leftrightarrow \textstyle \it p\)

• prawo przemienności alterantywy:

\((\textstyle \it p \textstyle \lor \textstyle \it q) \textstyle \Leftrightarrow (\textstyle \it q\textstyle \lor \textstyle \it p)\)

• prawo przemienności koniunkcji:

\((\textstyle \it p \textstyle \land \textstyle \it q) \textstyle \Leftrightarrow (\textstyle \it q \textstyle  \land \textstyle \it p)\)

• prawo łączności alterantywy:

\([\textstyle \it p \textstyle \lor (\textstyle \it q \textstyle \lor \textstyle \it r)] \textstyle \Leftrightarrow [(\textstyle \it p \textstyle \lor \textstyle \it q) \textstyle \lor \textstyle \it r]\)

• prawo łączności koniunkcji:

\([\textstyle \it p \textstyle \land (\textstyle \it q \textstyle \land \textstyle \it r)] \textstyle \Leftrightarrow [(\textstyle \it p \textstyle \land \textstyle \it q) \textstyle \land \textstyle \it r]\)

• prawo rozdzielności alterantywy względem koniunkcji:

\([\textstyle \it p \textstyle \lor (\textstyle \it q \textstyle \land \textstyle \it r)] \textstyle \Leftrightarrow [(\textstyle \it p \textstyle \lor \textstyle \it q) \textstyle \land (\textstyle \it p \textstyle \lor \textstyle \it r)]\)

• prawo rozdzielności koniunkcji względem alternatywy:

\([\textstyle \it p \textstyle \land (\textstyle \it q \textstyle \lor \textstyle \it r)] \textstyle \Leftrightarrow [(\textstyle \it p \textstyle \land \textstyle \it q) \textstyle \lor (\textstyle \it p \textstyle \land \textstyle \it r)]\)

• I-sze prawo de Morgana:

\(\textstyle \sim(\it p \land\textstyle  \it q \textstyle ) \Leftrightarrow \textstyle  \sim \it p \textstyle  \lor \textstyle  \sim \textstyle  \it q\), czyli zaprzeczenie koniunkcji jest równoważne alternatywie zaprzeczeń,

• II-gie prawo de Morgana:

\(\textstyle \sim(\it p \lor \textstyle \it q \textstyle ) \Leftrightarrow \textstyle  \sim \it p \textstyle   \land \textstyle \sim \textstyle \it q\), czyli zaprzeczenie alternatywy jest równoważne koniunkcji zaprzeczeń.

Prawdziwość praw rachunku zdań można sprawdzić m.in. metodą zero-jedynkową. W metodzie tej sprawdza się tautologię dla wszystkich kombinacji wartości logicznych zdań prostych - 4 kombinacje dla dwóch zdań prostych tworzących tautologię, 8 kombinacji dla trzech zdań prostych, itd. W poniższych dwóch przykładach sprawdzimy:

I-sze prawo de Morgana

i prawo rozdzielności koniunkcji względem alternatywy

Jak widzimy odpowiednie kolumny w dwóch powyższych tabelach są identyczne co stanowi dowód tych tautologii, ponieważ równoważność jest prawdziwa wtedy gdy wartości logiczne obu jej stron są takie same. Można zauważyć, że niektóre z tautologii odpowiadają znanym nam prawom działania na liczbach (alternatywa to dodawanie, a koniunkcja to mnożenie).

Funkcja zdaniowa

Funkcja zdaniowa zmiennej \(x\) \(\textstyle \in X\) to wyrażenie w którym występuje zmienna \(x\) i które staje się zdaniem gdy w miejsce zmiennej \(x\) wstawimy nazwę elementu ze zbioru \(X\). Wartość logiczna funkcji zdaniowej nie jest określona, a o prawdziwości (bądź nieprawdziwości) funkcji zdaniowej możemy wnioskować dopiero po wstawieniu w miejsce zmiennej \(x\) elementu ze zbioru \(X\).

Przykłady funkcji zdaniowych:

• Dnia \(x\) była ładna pogoda. 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 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ść logiczna 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.

Poniżej przedstawiono dwa przykłady użycia kwantyfikatora szczegółowego. \(\textstyle \bigvee x \textstyle \in X P(x)\) czytamy jako: istnieje \(x\) należące do zbioru \(X\) takie, że spełniony jest warunek \(P(x)\) (lub ... że zachodzi warunek \(P(x))\), \(\textstyle \bigvee W(x) P(x)\) czytamy jako: istnieje \(x\) spełniające warunek \(W(x)\) takie, że zachodzi \(P(x)\).

• \(\textstyle \bigwedge\) - kwantyfikator ogólny odpowiadający dla każdego.

I znowu dwa przykłady użycia kwantyfikatora ogólnego. \(\textstyle \bigwedge\) x \(\textstyle \in\) \(X P(x)\) czytamy jako: dla każdego \(x\) należącego do zbioru \(X\) spełniony jest warunek \(P(x)\) (lub ... zachodzi warunek \(P(x)\)), \(\textstyle \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 zarówno kwantyfikator szczegółowy, jak i kwantyfikator ogólny mogą przekształcić funkcje zdaniową zarówno 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:

• \(\textstyle \bigwedge x \textstyle \in R x \textstyle ^ 2 + 1 > 0\),
  kwantyfikator ogólny przekształcił funkcję zdaniową w zdanie prawdziwe,
• \(\textstyle \bigwedge x \textstyle \in N x < 7\),
  kwantyfikator ogólny przekształcił funkcję zdaniową w zdanie fałszywe,
• \(\textstyle \bigvee x \textstyle \in R x\textstyle ^ 2 = 0\),
  kwantyfikator szczegółowy przekształcił funkcję zdaniową w zdanie prawdziwe,
• \(\textstyle \bigvee x \textstyle \in 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, ale nie będziemy ich tutaj omawiać.

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 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 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: 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 zbiorów

\( A \cap B = \{x: x \in A \land x \in B\}\).   

czyli element \(x\) należny do iloczynu zbiorów \(A\) i \(B\) 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\) tylko wtedy, gdy należy do zbioru \(A\) i nie należy do zbioru \(B\).

• zawieranie się zbiorów

 \( A \subset B \Leftrightarrow \bigwedge_{x} (x \in A \Rightarrow x \in B)\),

tzn. jeżeli element \(x\) należny do zbioru \(A\) to jednocześnie należy do zbioru \(B\). Operacja 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\).

• \(A'\) dopełnienie zbioru

 \(A\) \( A' = X \setminus A \quad \mathrm{je\dot{z}eli} \quad A \subset X \),

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. Można podać szereg praw rachunku zbiorów. Praw, które są zarówno odpowiednikiem znanych praw działań na liczbach, jak i 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ń

• prawa tautologii

 \( A \cup A = A,  A \cap A = A,  A \cup \oslash = A,  A \cap \oslash = \oslash\). 

Iloczyn kartezjański zbiorów

Jest to działanie na zbiorach, które ze względu na jego ważność, omówimy oddzielnie. Ale zanim to uczynimy musimy wprowadzić 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\) tworzy zbiór wszystkich par uporządkowanych \((x,y)\)

 \(X \times Y = \{(x,y): x \in X \land y \in Y\}. \)

Przykład

Iloczyn kartezjański zbiorów

\(X = \{1,2,3\} \land 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 każdy 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 zbiorze pierwsze \(\mathbf R\)oznacza realcję 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: 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.

Zadania