I. ELEMENTY LOGIKI I TEORII MNOGOŚCI .
1.1 Rachunek zdań
Podstawowe wiadomości teoretyczne
Zdaniami w logice matematycznej nazywamy zdania orzekające z których każde jest prawdziwe lub fałszywe. O zdaniu prawdziwym mówimy, że ma wartość logiczną "1", a o zdaniu fałszywym, że ma wartość logiczną "0".
Niech p, q, r, oznaczają zmienne zdaniowe w miejsce których można podstawić dowolne zdanie prawdziwe lub fałszywe.
Tautologia jest to formuła, która zawsze przyjmuje wartość logiczną "1", niezależnie od wartości logicznych zdań podstawionych w miejsce zmiennych zdaniowych. Do sprawdzania czy dane wyrażenia rachunku zdań są tautologią służy metoda zero‑jedynkowa (0,1), która polega na rozpatrzeniu wszystkich układów wartości logicznych zmiennych zdaniowych występujących w badanych wyrażeniach.
Korzystając ze spójników zdaniotwórczych zwanych funktorami można tworzyć zdania złożone . Wyróżniamy 6 ważnych funktorów :
1.negacja (zaprzeczenie) zdania p.
Oznaczamy symbolem ~p i czytamy :"nie prawda, że p". Wartość logiczna zdania zależy od wartości logicznej zdania p. Jeżeli p="0" (fałsz) to p="1" (prawda) ,a gdy p="1" (prawda) to p="0" (fałsz).
2.koniunkcja (iloczyn logiczny) zdania p i q.
Oznaczamy symbolem p Ù q i czytamy "p i q". Koniunkcja p Ù q jest zdaniem prawdziwym, gdy jednocześnie zdania p i q są prawdziwe.
3.alternatywa (suma logiczna) zdań p i q.
Oznaczamy symbolem p Ú q i czytamy : "p lub q". Alternatywa p Ú q jest zdaniem prawdziwym, gdy co najmniej jedno ze zdań p , q jest prawdziwe.
4.implikacja ( wynikanie ) zdań p i q .
Oznaczamy symbolem p Þ q i czytamy :"jeżeli p to q", gdzie p jest poprzednikiem, q natomiast jest następnikiem. Implikacja jest prawdziwa w każdym przypadku z wyjątkiem jednego, gdy poprzednik p="1", a jednocześnie następnik q="0".
5.równoważność zdań p i q.
Oznaczamy symbolem p Û q i czytamy: "p wtedy i tylko wtedy gdy q". Równoważność pÛq jest zdaniem prawdziwym, gdy p i q mają tę samą wartość logiczną.
6.nierównoważność zdań p i q (alternatywa wykluczająca się)
Oznaczamy symbolem p v q i czytamy "p albo q". Nierównoważność zdań jest prawdziwa, gdy p i q mają różną wartość logiczną.
Wartość logiczną wyżej wymienionych funktorów przedstawia tabela 1.
p
q
~p
pÙq
pÚq
pÞq
pÛq
0
1
tabela 1
Tautologia służy do przeprowadzania dowodów matematycznych. Polega to na uznaniu za prawdziwe pewnych zdań (wniosków), w logicznej konsekwencji prawdziwości innych zdań (przesłanek). Te elementarne ogniwa dowodów opierają się na regułach wnioskowania (dowodzenia). Każda z nich jest implikacją związaną z pewną tautologią.
Na przykład prawu przechodniości implikacji odpowiada reguła wnioskowania, którą symbolicznie zapisujemy następująco (przesłanki nad kreska, wniosek pod kreską)
pÞq , qÞr
pÞr
Jest to przykład dowodu matematycznego metodą wprost.
Innym przykładem przeprowadzania dowodu matematycznego może być metoda dowodu nie wprost. Metoda ta polega na zaprzeczeniu tezy, której prawdziwość mamy wykazać.
Jeżeli na przykład wskażemy prawdziwość dwóch implikacji (~q)Þr i (~r)Þ(~r), gdzie r jest dowolnym zdaniem to na podstawie reguły dowodzenia :
(~q)Þr, (~q)Þ(~r)
związanej z tautologią :
{[(~qÞr] Ù [(~q)Þ(~r)]}Þq możemy wnioskować o prawdziwości tezy "q". Jeżeli zdanie pÞq nazwiemy prostym, qÞp odwrotnym, (~ p)Þ(~ q) przeciwnym, a zdanie (~q)Þ(~p) przeciwstawny to możemy to ująć w tak zwany kwadrat logiczny, który przedstawiony jest na rys 1.1
Rys. 1.1
Przy wierzchołkach kwadratu położonych wzdłuż tej samej przekątnej umieszczone są twierdzenia równoważne. Z prawdziwości dowolnej pary twierdzeń umieszczonych przy końcach tego samego boku wynika prawdziwość wszystkich czterech twierdzeń. O twierdzeniach : prostym i przeciwnym oraz odpowiednio odwrotnym i przeciwstawnym mówimy, że tworzą zamknięty układ twierdzeń.
Zadania :
1.1 Określić koniunkcję za pomocą :
a) negacji i alternatywy
b) negacji i implikacji
1.2 Określić alternatywę za pomocą:
a) negacji i koniunkcji
1.3 Określić równoważność za pomocą koniunkcji, alternatywy i negacji.
1.4 Dla jakich wartości logicznych zdań p i q następujące zdania złożone są prawdziwe, a dla jakich fałszywe ?
a) (pÞq) Û (~p ...
Szeregowy2013