Dziś wpis o trochę innej tematyce. Ale mam nadzieję, że to nie zniechęci Cię do lektury mojego bloga!

Mam wrażenie, że matematyka przez wielu informatyków jest traktowana jako zło konieczne, które trzeba zaliczyć na studiach. Moim zdaniem nie jest to prawda. Matematyka przydaje się, a jej znajomość naprawdę pomaga w pracy każdego programisty. W takich momentach przypomina się ten obrazek:

Oryginalny obrazek możesz znaleźć tutaj. Oczywiście maszyna Turinga jest konceptem z pogranicza matematyki i informatyki, ale moim zdaniem pokazuje jeden, bardzo ważny fakt. Wiele osób nie widzi sensu w nauce skomplikowanej teorii. Zadowalają się umiejętnością programowania. Moim zdaniem jest to krótkowzroczne – bo rzeczywiście szybko znajdziesz zatrudnienie, ale z dużym prawdopodobieństwem nie zrobisz wielkiej kariery. Może nawet będziesz pracował w działce AI (artificial intelligence – sztucznej inteligencji), ale bez dogłębnej znajomości matematyki będziesz odtwarzał znane schematy i będzie Ci bardzo trudno wymyślić coś nowego (potencjalnie wartego grube pieniądze).

Chciałbym, żeby ten wpis rozpoczął dłuższą serię artykułów matematycznych. Chciałbym dojść do tematyki związanej z teorią Galois i wprowadzić apart matematyczny, żebyś był w stanie zrozumieć zagadnienie krzywych eliptycznych.

Jednocześnie piszę ten wpis, aby pokazać licealistom, że matematyka w liceum jest bardzo fajna, ale na studiach jest jeszcze fajniejsza. Trzeba powiedzieć wprost, że nieco inna, ale mimo to jest dużo fajniejsza.

Jeszcze do niedawna, w ramach mojej pracy przekonywałem licealistów, że studiowanie informatyki i/lub matematyki jest naprawdę bardzo przyjemne. A przede wszystkim bardzo perspektywiczne (badania wskazują, że bardzo duża część absolwentów znajduje satysfakcjonującą pracę w zawodzie). I mimo, że już teraz nie pracuję na uczelni, to i tak chciałbym przekonać przynajmniej kilka osób, że warto zaznajomić się z wyższą matematyką.

Logika i rachunek zdań

Za moich czasów (rok 2005) w pierwszej klasie liceum matematyka zaczynała się od logiki. Bardzo słusznie, rachunek zdań bardzo ułatwia wyrażanie myśli. Bez logiki matematyka byłaby dużo trudniejsza. Z tego co pamiętam, na studiach wszyscy wykładowcy zakładali, że znamy logikę i nikt nam jej nie przypominał.

Zdanie

Wszystko powinniśmy zacząć od zdania. Oczywiście, wszystko można zdefiniować bardzo formalnie. Ale zacznijmy od wprowadzenia intuicji. Zdania będziemy oznaczali małymi literami alfabetu łacińskiego (, , , …) lub greckiego (, , , …). Zdania takie są proste (nie zawierają zbyt wielu informacji) i zasadniczo można obiektywnie przypisać im jedną z dwóch wartości: prawdę lub fałsz. Zdania w matematyce mogą składać się z wielu zdań, które są połączone ze sobą spójnikami. Czyli trochę jak w gramatyce – są zdania pojedyncze, które połączone spójnikami mogą tworzyć zdania złożone. Przykładem takiego prostego zdania w matematyce może być:

• Liczba jest liczbą parzystą
• Zbiór jest zbiorem pustym

Za zdanie (w kontekście rachunku zdań, logiki i matematyki) nie możemy uznać:

• Jaś lubi liczby parzyste
• Liczba być może jest parzysta

Wartościowanie zdań

Przyjmijmy teraz, że jest zdaniem prostym. A jest funkcją, która jako argument przyjmuje zdanie, a jej wartością jest (gdy zdanie jest fałszywe) albo (gdy zadanie jest prawdziwe). Możemy więc zapisać to matematycznie:

   

Możemy teraz zdefiniować spójniki logiczne i zdefiniować wartościowanie zdań złożonych.

Koniunkcja

Koniunkcja to matematyczne określenie relacji dwóch zdań połączonych spójnikiem i (oraz). Matematycznie ten spójnik zapisuje się jako znak . Za pomocą tabelki logicznej, możemy wyznaczyć wartościowanie zdania w zależności od wartościowania zdań i :

1	1	1
1	0	0
0	1	0
0	0	0

Tak więc oba zdania połączone spójnikiem oraz muszą być prawdziwe, aby całe zdanie było prawdziwe.

Alternatywa

W alternatywie spójnikiem jest lub. Matematycznie oznacza się go znaczkiem . Dla alternatywy tabelka będzie wyglądała trochę inaczej:

1	1	1
1	0	1
0	1	1
0	0	0

Mówiąc inaczej, alternatywa dwóch zdań jest prawdziwa, gdy przynajmniej jedno zdanie połączone spójnikiem lub jest prawdziwe.

Negacja

Każde zdanie możemy zaprzeczyć używając partykuły nie. Matematycznie możemy to zapisać za pomocą znaczka (w niektórych podręcznikach można spotkać zapis ). Operacja (trochę trudno mówić o spójniku) negacji też ma swoją tabelkę:

1	0
0	1

Implikacja

Implikacja określa wynikanie jednego zdania z jakiegoś innego zdania. Na przykład:

   

Matematycznie możemy to zapisać:

   

Implikacja jest bardzo często używana w trakcie przeprowadzaniu dowodów matematycznych. Niektóre twierdzenia matematyczne są wyrażone jako implikacje (z założenia wynika teza). Matematyczna implikacja ma jednak inne znaczenie od implikacji używanej w mowie potocznej.

1	1	1
1	0	0
0	1	1
0	0	1

Tak naprawdę wystarczy zapamiętać, że implikacja jest fałszywa tylko w przypadku, gdy poprzednik implikacji (czyli zdanie stojące po lewej stronie znaku ) jest prawdziwy, a następnik (czyli zdanie stojące po prawej stronie znaku ) jest fałszywy. Ma to takie filozoficzne znaczenie, że z prawdy nie możemy wywnioskować fałszu. Zwróć uwagę na jeszcze jeden fakt: z fałszu możemy wywnioskować cokolwiek.

Równoważność

Jeszcze jeden spójnik, który określa równoważność zdań. Oznaczamy go za pomocą symbolu i czytamy: wtedy i tylko wtedy, gdy. Tutaj intuicyjne rozumowanie nie powinno Cię zawieść.

1	1	1
1	0	0
0	1	0
0	0	1

Zdanie są sobie równoważne, gdy oba mają takie samo wartościowanie logiczne. Równoważność można również zdefiniować w następujący sposób:

   

Możemy to rozumieć następująco:

zdania i są sobie równoważne wtedy i tylko wtedy, gdy ze zdania wynika zadanie oraz ze zdania wynika zdanie .

Tautologie

Zdanie jest przykładem tautologii: czyli zdania, które jest prawdziwe niezależnie od wartościowania zdań i . W szkole badanie, czy zadane zdanie złożone jest tautologią odbywa się przy użyciu tabelek. Na przykład:

0	0	1	1	1	1	1
0	1	0	1	0	0	1
1	0	0	0	1	0	1
1	1	1	1	1	1	1

Widzimy w tabelce, że całe zdanie jest prawdziwe zawsze – niezależnie od prawdziwości (bądź nieprawdziwości) zdań i .

Innym przykładem tautologii jest zdanie

   

Jest jeszcze jedna tautologia, która bywa nazywana prawem de Morgana:

   

Dowód, że te zdania są rzeczywiście tautologiami, pozostawiam Tobie, mój dzielny Czytelniku.

A teraz przez chwilę zadumajmy się nad tymi trzema tautologiami. Jeżeli głębiej się nad tym wszystkim zastanowimy, to każde zdanie logiczne można opisać tylko przy użyciu alternatywy i negacji. To znaczy, że całą logikę można wyrazić w zdaniach logicznych zawierających tylko spójnik lub oraz zaprzeczenie.

Możemy definiować jeszcze inne spójniki logiczne, które mają dużo sensu w informatyce. Przykładem może być XOR (exclusive or), NOR oraz NAND. Tutaj pozwoliłem sobie na lekkie uproszczenie, bo to są nazwy bramek logicznych. A bramki logiczne, to są najmniejsze części składowe dowolnego układu elektronicznego. Możemy sobie wyobrazić, że procesor w każdym komputerze składa się z ogromnej liczby bramek logicznych. Okazuje się, że układ cyfrowy może składać się tylko i wyłącznie z bramki NAND (operator logiczny odpowiadający tej bramce logicznej nazywa się dysjunkcją). Zaprzeczenie i alternatywę możemy wyrazić za pomocą dysjunkcji, której tabelka wartościowań wygląda następująco:

1	1	0
1	0	1
0	1	1
0	0	1

Zwróć uwagę, że jest to negacja koniunkcji. Czy widzisz, w jaki sposób można zdefiniować negację i alternatywę, przy użyciu dysjunkcji?

Teoria zbiorów

Podstawą wszytkich działów matematycznych jest teoria zbiorów (w polskiej literaturze określa się ją też jako teoria mnogości). Wszystkie pojęcia możemy wyrazić w języku zbiorów. Myślę, że w następnym wpisie z serii matematycznej uda mi się zdefiniować funkcję w języku zbiorów. O zbiorach jako takich można mówić bardzo wiele. Zdaję sobie sprawę, że ten wpis zrobił się już strasznie długi, więc dziś skupię się tylko na podstawach.

Zbiór jest przykładem pojęcia pierwotnego. Czyli cytująć polską wikipedię:

Terminem pojęcia pierwotnego określa się pojęcia, które uznawane są za fundamentalne, a zarazem trudne do opisania językiem teorii

To trochę jak z definicją konia w staropolskiej encyklopedii: koń jaki jest, każdy widzi.

Zbiór może być skończony (mieć skończenie wiele elementów) lub nieskończony (mieć nieskończenie wiele elementów, przykład: zbiór liczb naturalnych).

Warto dodać, że jest tylko jeden zbiór, który nie zawiera żadnego elementu, taki zbiór nazywamy zbiorem pustym i oznaczamy symbolem .

Fakt, że element należy do zbioru (zwyczajowo zbiory oznacza się wielkimi literami alfabetu łacińskiego) zapisujemy:

   

Oczywiście możemy również podkreślić, że element nie należy do zbioru :

   

Przejdźmy teraz do relacji pomiędzy zbiorami.

Zawieranie

Zbiór jest podzbiorem zbioru (albo inaczej jest nadzbiorem zbioru ) wtedy i tylko wtedy, gdy każdy element zbioru jest również elementem zbioru . Taką relację pomiędzy zbiorami oznaczamy symbolem inkluzji: :

   

Możemy to również zapisać przy użyciu kwantyfikatora dla każdego:

   

Słownie możemy to przeczytać:

Zbiór jest podzbiorem zbioru wtedy i tylko wtedy, gdy dla każdego elementu zachodzi implikacja, że jeżeli należy do zbioru , to należy do zbioru

O sytuacji odwrotnej – czyli o sytuacji, gdy nie jest podzbiorem – mówi się na tyle często, że istnieje osobny symbol na relację nie bycia podzbiorem:

   

Czyli zbiór nie jest podzbiorem , wtedy i tylko wtedy gdy istnieje element w zbiorze , który nie jest elementem zbioru . Można to wyrazić używając języka logiki:

   

Zapis odczytujemy:

istnieje taki, że zachodzi

Symbol nazywamy kwantyfikatorem istnieje.

Równość

Definicja równości zbiorów mówi, że zbiory i są sobie równe wtedy i tylko wtedy, gdy mają takie same elementy. Możemy to zapisać używając kwantyfikatora dla każdego:

   

Korzystając z powyższej definicji można udowodnić następujące własności dla dowolnych zbiorów , i

1. 
2. 
3. 
4. 
5. 

Szczególne przypadki zawierania

Warto w tym momencie wspomnieć o jeszcze dwóch specjalnych symbolach:

1. – oznacza zawieranie, które dopuszcza równość dwóch zbiorów
2. – oznacza zawieranie, ale wyklucza równość zbiorów. Możemy to przeczytać jako: jest właściwym podzbiorem – co oznacza, że istnieje przynajmniej jeden taki element zbioru , który nie jest elementem zbioru

Suma zbiorów

Sumę zbiorów oznacza się symbolem i definiuje się następująco dla dowolnych zbiorów i :

   

Najlepiej to obrazuje ilustracja:

 

Iloczyn zbiorów

Iloczyn zbiorów (inaczej przecięcie lub część wspólną) oznaczamy symbolem i definiuje się dla dowolnych zbiorów i :

   

Można to łatwo zdefiniować na ilustracji:

 

Różnica zbiorów

Kolejnym działaniem na zbiorach, o którym chciałbym napisać jest różnica zbiorów, którą oznacza kreską ukośną , albo po prostu zwyczajnie minusem . Dla dowolnych zbiorów i definiujemy ją:

   

Co również można łatwo zilustrować na diagramie:

 

Iloczyn kartezjański

Cały artykuł chciałbym zakończyć definicją iloczynu kartezjańskiego dowolnych zbiorów i :

   

Możemy tę definicję odczytać:

Iloczyn kartezjański dwóch zbiorów i to jest zbiór par, z których pierwszy element należy do zbioru a drugi do zbioru .

Gdy mamy zbiory oraz . To wtedy:

   

Kolejny wpis, w którym będę wykorzystywał iloczyn kartezjański już wkrótce.

Literatura

Zainteresowanych odsyłam do strony internetowej Ważniak oraz do książki pani Heleny Rasiowej o tytule Wstęp do matematyki współczesnej.