Podstawy logiki i teorii zbiorów

Zbiór wzorów, definicji i najczęściej poruszanych problemów ze Zbiór-ki.
Awatar użytkownika
miki999
Użytkownik
Użytkownik
Posty: 8691
Rejestracja: 28 lis 2007, o 18:10
Płeć: Mężczyzna
Lokalizacja: Gdańsk
Podziękował: 36 razy
Pomógł: 1001 razy

Podstawy logiki i teorii zbiorów

Post autor: miki999 »

Podstawowe informacje na temat logiki oraz zbiorów

W dziale Zbiory. Teoria mnogości niejednokrotnie pojawiają się tematy dotyczące podstawowych zagadnień z zakresu logiki oraz zbiorów. Autor wątku często zostaje odesłany do wyszukiwarki albo do innego tematu. Mam nadzieję, że potencjalny czytelnik znajdzie tutaj podstawowe informacje oraz przykładowe zadania z tej tematyki, które pozwolą rozwiać posiadane wątpliwości.
Temat dopiero się rozwija i z pewnością będzie z czasem uzupełniany o nowe informacje i zadania.




1. Podstawy logiki
1. 1. Co to jest zdanie?
1. 2. Spójniki i tabele logiczne
1. 3. Tautologie i kontrtautologie
1. 4. Formy zdaniowe i kwantyfikatory

2. Zbiory
2. 1. Podstawowe informacje


Co to jest zdanie?
W matematyce za zdanie przyjmuje się wyłącznie stwierdzenie, któremu można przypisać wartość logiczną: \(\displaystyle{ 1}\)- zdaniu prawdziwemu, \(\displaystyle{ 0}\)- fałszywemu.
Przykład:
- Trójkąt jest figurą geometryczną. -zdanie logiczne, prawdziwe
- Warszawa jest stolicą Polski.- zdanie logiczne, prawdziwe
- \(\displaystyle{ 2<3}\)- zdanie logiczne, prawdziwe
- Istnieje największa liczba naturalna.- zdanie logiczne, fałszywe
- Idź do sklepu.- zdanie nielogiczne
- W pięciokąt można wpisać okrąg.- zdanie nielogiczne, ponieważ nie wiadomo o jakim pięciokącie jest mowa, więc nie można jednoznacznie określić wartości logicznej.

Na ogół do oznaczania zdań używa się małych liter: \(\displaystyle{ p, q, r, s, t, x, y, z}\) itp.


Spójniki i tabele logiczne
Negacja: oznaczana jest symbolem \(\displaystyle{ " \neg "}\) (czasami \(\displaystyle{ " \sim "}\)). Zmienia ona wartość logiczną następującego po nim zdania na przeciwną. \(\displaystyle{ " \neg p "}\) czytamy jako "nieprawda, że \(\displaystyle{ p}\)" lub krócej "nie \(\displaystyle{ p"}\).
Przykład:
\(\displaystyle{ p\equiv \text{ "W każdy ośmiokąt można wpisać okrąg."},\ \neg p \equiv " \text{Nieprawda, że w każdy ośmiokąt można wpisać okrąg."}}\)


Alternatywa: symbol- \(\displaystyle{ " \vee "}\). Zdanie \(\displaystyle{ r\equiv p \vee q}\) jest prawdziwe, gdy co najmniej 1 ze zdań, między którymi występuje \(\displaystyle{ " \vee "}\) jest prawdziwe. \(\displaystyle{ "p \vee q"}\) czytamy "\(\displaystyle{ p}\) lub \(\displaystyle{ q}\)".

Przykład: \(\displaystyle{ p \equiv \text{"8 jest liczbą parzystą."}\ q \equiv}\) "\(\displaystyle{ 2<8}\)"

Zdanie \(\displaystyle{ p\vee q}\) wygląda tak: "\(\displaystyle{ 8}\) jest liczbą parzystą lub \(\displaystyle{ 2<8}\)."


Koniunkcja: Symbol- \(\displaystyle{ \wedge}\)("i"). Zdanie \(\displaystyle{ r=p \wedge q}\) jest prawdziwe wyłącznie wtedy, gdy zarówno \(\displaystyle{ p}\), jak i \(\displaystyle{ q}\) są prawdziwe.

Przykład:
\(\displaystyle{ p\equiv \text{"Istnieje największa liczba naturalna."},\ q\equiv \text{"Istnieje co najwyżej 5 liczb rzeczywistych."},\\ \\ p \wedge q \equiv\text{"Istnieje największa liczba naturalna i istnieje co najwyżej 5 liczb rzeczywistych".}}\)


Implikacja: symbol- \(\displaystyle{ " \Rightarrow "}\) ("to"). Zdanie \(\displaystyle{ r\equiv p \Rightarrow q}\) jest fałszywe wyłącznie, gdy \(\displaystyle{ p}\) jest prawdziwe, a \(\displaystyle{ q}\) fałszywe.

Przykład: \(\displaystyle{ p \equiv \text{ "Trójkąt jest prostokątny."}}\),

\(\displaystyle{ q\equiv "\text{suma kwadratów długości przyprostokątnych jest równa kwadratowi długości przeciwprostokątnej."}}\),

\(\displaystyle{ p \Rightarrow q \equiv " \text{Jeżeli trójkąt jest prostokątny, to suma kwadratów długości przyprostokątnych jest równa kwadratowi} \\ \text{długości przeciwprostokątnej."}}\)


Równoważność: symbol- \(\displaystyle{ " \Leftrightarrow "}\). \(\displaystyle{ r\equiv p \Leftrightarrow q}\) jest prawdziwe, gdy \(\displaystyle{ p}\) i \(\displaystyle{ q}\) mają tę samą wartość logiczną.
Przykład: Rozpatrujemy liczbę ze zbioru liczb rzeczywistych. \(\displaystyle{ p\equiv "x=1",\ q\equiv "x^2=1",\ p \Leftrightarrow q \equiv "x=1}\) wtedy i tylko wtedy, gdy \(\displaystyle{ x^2=1"}\).


Czasami również mówi się o alternatywie wykluczającej oznaczanej jako "\(\displaystyle{ \veebar}\)" ("albo"). Ma podobne znaczenie do zwykłej alternatywy, z tą różnicą, że wyklucza przypadek, gdy oba zdania są prawdziwe.


Dla lepszego zobrazowania można używać tabelek logicznych reprezentujących wartość logiczną dla poszczególnych elementów tego zdania.


Dla podanych przed chwilą działań prezentują się one tak:
\(\displaystyle{ \begin{tabular}{|c|c|}\hline
p & \neg p \\ \hline
0 & 1 \\ \hline
1 & 0 \\ \hline
\end{tabular} \quad \quad
\begin{tabular}{|c|c|c|}\hline
p & q & p \vee q \\ \hline
0 & 0 & 0 \\ \hline
0 & 1 & 1 \\ \hline
1 & 0 & 1 \\ \hline
1 & 1 & 1 \\ \hline
\end{tabular}\quad \quad
\begin{tabular}{|c|c|c|}\hline
p & q & p \wedge q \\ \hline
0 & 0 & 0 \\ \hline
0 & 1 & 0 \\ \hline
1 & 0 & 0 \\ \hline
1 & 1 & 1 \\ \hline
\end{tabular}\quad \quad
\begin{tabular}{|c|c|c|}\hline
p & q & p \Rightarrow q \\ \hline
0 & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
1 & 0 & 0 \\ \hline
1 & 1 & 1 \\ \hline
\end{tabular}\quad \quad
\begin{tabular}{|c|c|c|}\hline
p & q & p \Leftrightarrow q \\ \hline
0 & 0 & 1 \\ \hline
0 & 1 & 0 \\ \hline
1 & 0 & 0 \\ \hline
1 & 1 & 1 \\ \hline
\end{tabular}\quad \quad
\begin{tabular}{|c|c|c|}\hline
p & q & p \veebar q \\ \hline
0 & 0 & 0 \\ \hline
0 & 1 & 1 \\ \hline
1 & 0 & 1 \\ \hline
1 & 1 & 0 \\ \hline
\end{tabular}\\}\)


Zdania mogą być o wiele bardziej złożone i może występować więcej zdań, np.: \(\displaystyle{ (p \vee q )\Rightarrow \neg ( r \Rightarrow s)}\) itp. Oczywiście wtedy tabelki są dużo bardziej rozbudowane.

Zad. 1. Zrobić tabelkę logiczną dla zdania: \(\displaystyle{ (p \Rightarrow q )\vee \neg (q \Rightarrow \neg p)}\).

\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|c|}\hline
p & q & \neg p & p \Rightarrow q & q \Rightarrow \neg p & \neg (q \Rightarrow \neg p) & (p \Rightarrow q ) \vee \neg (q \Rightarrow \neg p) \\ \hline
0 & 0 & 1 & 1 & 1 & 0 & 1 \\ \hline
0 & 1 & 1 & 1 & 1 & 0 & 1\\ \hline
1 & 0 & 0 & 0 & 1 & 0 & 0\\ \hline
1 & 1 & 0 & 1 & 0 & 1 & 1 \\ \hline
\end{tabular}}\)


Zad. 2. Zrobić tabelkę zdania \(\displaystyle{ (p \Rightarrow r )\vee (r \Rightarrow q)}\)

\(\displaystyle{ \begin{tabular}{|c|c|c|c|c|c|}\hline
p & q & r & p \Rightarrow r & r \Rightarrow q & (p \Rightarrow r )\vee (r \Rightarrow q) \\ \hline
0 & 0 & 0 & 1 & 1 & 1 \\ \hline
0 & 0 & 1 & 1 & 0 & 1 \\ \hline
0 & 1 & 0 & 1 & 1 & 1 \\ \hline
0 & 1 & 1 & 1 & 1 & 1 \\ \hline
1 & 0 & 0 & 0 & 1 & 1 \\ \hline
1 & 0 & 1 & 1 & 0 & 1 \\ \hline
1 & 1 & 0 & 0 & 1 & 1 \\ \hline
1 & 1 & 1 & 1 & 1 & 1 \\ \hline
\end{tabular}}\)


Zad. 3. Ocenić wartość logiczną zdań:
a) \(\displaystyle{ 2|6 \Rightarrow 2>3}\) (zapis \(\displaystyle{ a|b}\) oznacza "a dzieli b")

\(\displaystyle{ 2|6}\)- zdanie jest prawdziwe (\(\displaystyle{ 6}\) jest podzielne przez \(\displaystyle{ 2}\)),
\(\displaystyle{ 2>3}\)- zdanie jest fałszywe
Zatem mamy sytuację \(\displaystyle{ 1 \Rightarrow 0}\). Patrzymy do tabelki dla implikacji i dajemy odp.

Odp.: Zdanie jest fałszywe.

b) \(\displaystyle{ (3|12 \wedge 4|12) \Rightarrow \sqrt{2} <1}\)

\(\displaystyle{ 3|12}\)- prawda
\(\displaystyle{ 4|12}\)- prawda
\(\displaystyle{ (3|12 \wedge 4|12}\)- (patrzymy na tabelkę: \(\displaystyle{ 1 \wedge 1}\))- prawda
\(\displaystyle{ \sqrt{2} <1}\)- fałsz
\(\displaystyle{ (3|12 \wedge 4|12) \Rightarrow \sqrt{2} <1}\)- (patrzymy na tabelkę \(\displaystyle{ 1 \Rightarrow 0}\))- fałsz

Odp.: Zdanie jest fałszywe.

c) \(\displaystyle{ [(2|3 \vee 8+5<17 \vee 11<9) \Rightarrow \pi<3] \vee 2>0}\)

Sprawdzanie wszystkich składowych zdania nie jest konieczne. Wystarczy zauważyć, że zdanie składa się z 2 głównych części:
1) \(\displaystyle{ (2|3 \vee 8+5<17 \vee 11<9) \Rightarrow \pi<3}\)
2) \(\displaystyle{ 2>0}\)
połączonych spójnikiem "lub". Druga część jest prawdziwa. Patrzymy na tabelkę spójnika \(\displaystyle{ \vee}\) i dochodzimy do wniosku, że bez względu na wartość logiczną 1. części całość i tak jest prawdziwa.

Odp.: Zdanie jest prawdziwe.

Tautologie i kontrtautologie
Tautologią nazywamy zdanie, które bez względu na wartość logiczną zdań zawierającyc zawsze przybiera wartość logiczną \(\displaystyle{ 1}\). W celu sprawdzenia czy dane zdanie nią jest, sporządzamy tabelkę taką jak w zadaniach powyżej. Gdy na końcu wychodzą same jedynki, to zdanie jest tautologią. Aby zaoszczędzić czasu możemy też postępować w niestandardowy sposób (patrz zad. 4. c) )
Zad. 4. Sprawdź czy poniższe zdania są tautologiami:
a) \(\displaystyle{ (p \Rightarrow r )\vee (r \Rightarrow q)}\) -tabelka znajduje się w zad. 2.

Odp.: Tak, jest.

b) \(\displaystyle{ p \vee \neg p}\)

\(\displaystyle{ \begin{tabular}{|c|c|c|}\hline
p & \neg p & p \vee \neg p\\ \hline
0 & 1 & 1 \\ \hline
1 & 0 & 1 \\ \hline
\end{tabular}}\)


Odp: Tak, jest.

c) \(\displaystyle{ p \vee [( \neg p \wedge q) \vee ( \neg p \wedge \neg q)]}\)
Krok 1. Zauważmy, że zdanie nie jest tautologią, gdy dla co najmniej jednej kombinacji nie wychodzi \(\displaystyle{ 1}\). Nasze wyrażenie składa się z dwóch głównych członów połączonych spójnikiem lub: \(\displaystyle{ p}\) oraz \(\displaystyle{ ( \neg p \wedge q) \vee ( \neg p \wedge \neg q)}\). Patrzymy na tabelkę spójnika lub i widzimy, że aby otrzymać na końcu fałsz, oba człony muszą być fałszywe. Zatem \(\displaystyle{ p=0}\) oraz \(\displaystyle{ ( \neg p \wedge q) \vee ( \neg p \wedge \neg q)=0}\).
Krok 2. Sprawdzamy kiedy 2. część jest fałszem. Składa się ona również z dwóch głównych elementów: \(\displaystyle{ ( \neg p \wedge q)}\) oraz \(\displaystyle{ ( \neg p \wedge \neg q)=0}\) połączonych tym samym spójnikiem co poprzednio. Ustaliliśmy, że \(\displaystyle{ p=0}\), czyli \(\displaystyle{ \neg p =1}\), a zatem aby 1. nawias był fałszem, to musi być \(\displaystyle{ q=0}\), ale w drugiej części mamy identyczną sytuację, tylko że \(\displaystyle{ q}\) jest zanegowane i w analogiczny sposób możemy wnioskować, że musi być \(\displaystyle{ q=1}\).
Krok 3. Zwróćmy uwagę, że otrzymaliśmy sprzeczność, bo doszliśmy do tego, że musi jednocześnie zachodzić: \(\displaystyle{ q=0}\) oraz \(\displaystyle{ q=1}\), a to jest niemożliwe.
Krok 4. Wniosek: zdanie nie może być fałszywe, zatem jest tautologią.

d) \(\displaystyle{ (p \wedge \neg p)\Rightarrow ([(p \vee q )\Rightarrow \neg ( r \Rightarrow s)] \Rightarrow \{p \vee [( p \Rightarrow r) \wedge ( p \wedge \neg s)]\})}\)

Wydaje się to kosmiczne, ale w rzeczywistości jest banalne. Mamy 2 człony: \(\displaystyle{ (p \wedge \neg p)}\) oraz 2. bardzo rozbudowany. Łatwo sprawdzić, że \(\displaystyle{ (p \wedge \neg p)}\) jest zdaniem zawsze fałszywym. Patrzymy na tabelkę i widzimy, że czymkolwiek by następnik implikacji nie był, to przy fałszywym poprzedniku zdanie jest zawsze prawdziwe. Wniosek: zdanie jest tautologią.


Kontrtautologią nazywamy przeciwieństwo tautologii, czyli zdanie, które zawsze jest fałszywe.
Przykład: \(\displaystyle{ p \wedge \neg p}\)


Ważniejsze prawa rachunku zdań

Przedstawione zostaną tutaj ważniejsze tautologie.

1) prawo tożsamości

\(\displaystyle{ p \Rightarrow p\,\!}\)
2) prawo podwójnego przeczenia

\(\displaystyle{ p \Leftrightarrow \lnot\lnot p\,\!}\)
3) prawo przemienności koniunkcji

\(\displaystyle{ (p \land q) \Leftrightarrow (q \land p)\,\!}\)
4) prawo przemienności alternatywy

\(\displaystyle{ (p \lor q) \Leftrightarrow (q \lor p)\,\!}\)

5) prawo łączności koniunkcji

\(\displaystyle{ [(p \land q) \land r] \Leftrightarrow [p \land (q \land r)]\,\!}\)
6) prawo łączności alternatywy

\(\displaystyle{ [(p \lor q) \lor r] \Leftrightarrow [p \lor (q \lor r)]\,\!}\)

7) prawo idempotentności koniunkcji

\(\displaystyle{ p \Leftrightarrow (p \land p)\,\!}\)

8) prawo idempotentności alternatywy

\(\displaystyle{ p \Leftrightarrow (p \lor p)\,\!}\)
9) prawo rozdzielności koniunkcji względem alternatywy

\(\displaystyle{ [p \land (q \lor r)] \Leftrightarrow [(p \land q) \lor (p \land r)] \,\!}\)
10) prawo rozdzielności alternatywy względem koniunkcji

\(\displaystyle{ [p \lor (q \land r)] \Leftrightarrow [(p \lor q) \land (p \lor r)]\,\!}\)

11) prawo wyłączonego środka

\(\displaystyle{ p \lor \lnot p\,\!}\)

12) pierwsze prawo De Morgana

\(\displaystyle{ \lnot (p \land q) \Leftrightarrow (\lnot p \lor \lnot q)\,\!}\)

13) drugie prawo De Morgana

\(\displaystyle{ \lnot (p \lor q) \Leftrightarrow (\lnot p \land \lnot q)\,\!}\)

14) prawo Claviusa

\(\displaystyle{ (\lnot p \Rightarrow p) \Rightarrow p\,\!}\)

15) prawo eliminacji implikacji

\(\displaystyle{ (p \Rightarrow q) \Leftrightarrow (\lnot p \lor q)\,\!}\)

16) prawo zaprzeczenia implikacji

\(\displaystyle{ \lnot (p \Rightarrow q) \Leftrightarrow (p \land \lnot q)\,\!}\)


Większość z tych praw jest dosyć intuicyjna. Niektóre z nich są niezwykle istotne i będziemy się do nich odwoływać w dalszym tekście.


Formy zdaniowe i kwantyfikatory
Za formę zdaniową \(\displaystyle{ \varphi(x)}\) uważać będziemy wyrażenie, które po wstawieniu pod \(\displaystyle{ x}\) jakiegokolwiek elementu \(\displaystyle{ x \in X}\) stanie się zdaniem.
W takim wypadku \(\displaystyle{ X}\) nazywamy zakresem formy zdaniowej.

Przykład:
\(\displaystyle{ \varphi(x)= |x|<5 \text{, gdzie } x \in \mathbb{R}}\).
\(\displaystyle{ \varphi(x)}\) jest zdaniem prawdziwym dla \(\displaystyle{ x \in (-5;5)}\) oraz fałszywym dla \(\displaystyle{ x \in (- \infty ;5 \rangle \cup \langle 5; \infty )}\).

Oczywiście forma może dotyczyć większej ilości zmiennych oznaczana jako \(\displaystyle{ \varphi(x, y), \varphi(x_1, x_2, ... , x_n)}\).

Kwantyfikatory

Posiadając formę zdaniową z podanym zakresem, możemy stworzyć następujące zdania:

1) Dla dowolnego (każdego) \(\displaystyle{ x \in X \varphi(x)}\)
2) Istnieje takie \(\displaystyle{ x \in X,\ \text{że}\ \varphi(x)}\)

Zaznaczone fragment poprzedzające zdania, to kwantyfikatory. W skróconym zapisie wygląda tak:
1) \(\displaystyle{ \forall x \in X \varphi(x)}\)
z ang. "for All"
2) \(\displaystyle{ \exists x \in X \varphi(x)}\)
z ang. "Exists"

Czasem fragment \(\displaystyle{ x \in X}\) jest zapisywany pod kwantyfikatorem. Stosuje się też zamiast \(\displaystyle{ \forall-\ \bigwedge,\ i\ \exists-\ \bigvee}\).

Forma zdaniowa poprzedzona kwantyfikatorem, staje się zdaniem i ma określoną wartość logiczną. Zdanie 1) jest prawdziwe, gdy każdy element ze zbioru \(\displaystyle{ X}\) spełnia formę zdaniową \(\displaystyle{ \varphi(x)}\), natomiast drugie- gdy co najmniej jeden.

Przykłady:
- \(\displaystyle{ \forall x \in \mathbb{R}\ x^2\geqslant 0}\)- zdanie prawdziwe, ponieważ prawdą jest, że kwadrat dowolnej liczby jest nieujemny.
- \(\displaystyle{ \exists x \in \mathbb{N}\ n+5<2}\)- zdanie fałszywe, ponieważ nie istnieje l. naturalna, która powiększona o \(\displaystyle{ 5}\) jest mniejsza od \(\displaystyle{ 2}\).
- \(\displaystyle{ \forall x \in \mathbb{Z}\ x> 0}\)- zdanie fałszywe, podajemy kontrprzykład, np. \(\displaystyle{ x=-5}\).
- \(\displaystyle{ \exists x \in \mathbb{Z}\ x> 0}\)- prawda, istnieje dodatnia l. całkowita, np. \(\displaystyle{ x=7}\).


Zad. 5. Sprawdź prawdziwość stwierdzenia: \(\displaystyle{ \forall x \in X \varphi (x) \Rightarrow \exists x \in X \varphi (x)}\) (dla \(\displaystyle{ X \neq \emptyset}\)).

Zdanie w oczywisty sposób jest spełnione. Wynika to z tego, że skoro dana formuła jest spełniana dla wszystkich elementów z \(\displaystyle{ X}\), to skoro \(\displaystyle{ X}\) jest niepustym zbiorem, to musi istnieć co najmniej jeden element, dla którego podana formuła zdaniowa jest prawdziwa.

Zad. 6. Zapisz zdania przy użyciu kwantyfikatorów:

a) Każda liczba naturalna jest mniejsza od \(\displaystyle{ 2}\).
\(\displaystyle{ \forall n \in \mathbb{N}\ n<2}\)

b) Kwadrat dowolnej liczby rzeczywistej jest liczbą rzeczywistą.
\(\displaystyle{ \forall x ( x \in \mathbb{R}\ \Rightarrow x^2 \in \mathbb{R}\ )}\)

c) Istnieje największa liczba naturalna.
\(\displaystyle{ \exists n \in \mathbb{N}\ \forall k \in \mathbb{N}\ (n\neq k \Rightarrow n>k)}\)

Podstawowe informacje
Na razie odsyłam do tematu viewtopic.php?t=18549.


Wszelkie uwagi i propozycje proszę kierować na pw

Podziękowania
dla osób, które przyczyniły się do poprawy jakości tego tematu:
- mat_61

Osobom chcącym w większym stopniu zgłębić temat polecam:
- "Wstęp do matematyki", J. Kraszewski
- "Wykłady ze wstępu do matematyki", W. Guzicki, P. Zakrzewski
- "Wstęp do teorii mnogości i topologii", K. Kuratowski
ODPOWIEDZ