1
1
LOGIKA
KLASYCZNY RACHUNEK ZDAŃ
Podstawowymi elementami języka rachunku zdań są:
zmienne zdaniowe : p, q, r...
operatory logiczne (funktory prawdziwościowe):
- negacja
- koniunkcja
- alternatywa (zwykła)
- implikacja
- równoważność
nawiasy ( ), [ ], { },...
Ad.1 zmienne reprezentują zdania w sensie logicznym, tzn. zdania, którym przysługują wartości logiczne:
prawdy i fałszu. Prawdziwość zdania oznaczamy przez T lub 1, zaś fałszywe przez F lub 0. Omawiany
rachunek zdań nazywamy klasycznym, gdyż zakłada się, że, zdanie przyjmuje jedynie jedną z dwu
wymienionych wartości logicznych. Powstały inne rachunki zdań, w których nie przyjmuje się tego
założenia. Nazywamy je ogólnie wielowartościowymi rachunkami zdań.
Ad. 2 .Za pomocą operatorów logicznych budujemy zdania złożone ze zdań prostych. Wartość logiczna
takich zdań złożonych zależy jedynie od wartości logicznych zdań składowych.. Stąd też dla danych
zdań : p i q wartości logiczne zdań złożonych:
p, p
q, p
q, p
q, p
q będą całkowicie
wyznaczone za pomocą wartości. Mamy więc:
p
p
1
0
0
1
Czyt. „nieprawda, że”
p q
p
q
p q
p
q
p q
p
q
p q
p
q
1 1
1 0
0 1
0 0
1
0
0
0
1 1
1 0
0 1
0 0
1
1
1
0
1 1
1 0
0 1
0 0
1
0
1
1
1 1
1 0
0 1
0 0
1
0
0
1
2
2
czyt. „i” czyt. „lub” czyt. „jeżeli, to” czyt. „wtw”
Ad. 3. Nawiasy, jako znaki pomocnicze, zmieniają naturalną kolejność operacji logicznych, tzn.
najmocniejsza jest negacja, później koniunkcja, alternatywa, implikacja i równoważność. Przykładowo:
p
q
p oraz ( p
q )
p
Def. Matrycą logiczną zdania złożonego, zbudowanego ze zdań prostych p, q, r ..., nazywamy tablica
podającą wartości logiczne tego zdania tego zdania złożonego, w zależności od wartości logicznych zdań
prostych.
Wn. Wartość logiczną zdania złożonego możemy obliczyć, wyznaczając po kolei wartości logiczne zdań
prostszych.
Ex. 1
Zapisz poniższe zdanie za pomocą symboliki logicznej, używając zmiennych zdaniowych: p, q, r, ... oraz
operatorów logicznych:
,
,
,
,
i podaj jego matrycę.„ Jeśli pada deszcz, to nie świeci słońce i
na niebie są chmury”. Niech
p =” pada deszcz”;
q = „ świeci słońce”;
r = „na niebie są chmury”
Tak więc mamy zdanie: p
q
r
Budujemy matrycę tego zdania:
p q r
q
q
r p
q
r
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
0
0
1
1
0
0
1
1
0
0
1
0
0
0
1
0
0
0
1
0
1
1
1
1
Kolumna 4 zawiera wartości logiczne dla całego zdania złożonego. Zdanie złożone jest prawdziwe bądź
to gdy nie pada deszcz, bądź to gdy pada deszcz lecz świeci słońce i na niebie są chmury. W
pozostałych przypadkach jest fałszywe.
3
3
Def 2. Zdania złożone, które są zawsze prawdziwe, niezależnie od wartości logicznych zmiennych
zdaniowych w nich występujących nazywamy tautologiami (prawami logiki); te zaś, które są zawsze
fałszywe nazywamy kontrtautologiami lub też wewnętrznie sprzecznymi.
Ex. 2.
Zdanie „p
p” jest tautologią, gdyż matryca przyjmuje zawsze wartość logiczną 1, zaś zdanie:
„p
p” zaś jest kontrtautologią, gdyż matryca przyjmuje zawsze wartość 0.
P
p
p
p
p p
p
1
0
1
1
1
0
0
1
0
0
Ex. 3.
Zbuduj matryce logiczną dla zdania złożonego P o postaci (p
q)
[ (p
q)
(p
q)] i wskaż
czy jest ono tautologią, czy kontrtautologią.
p q
q
p
q P
q p
q
(p
q)
(p
q) P
1 1
1 0
0 1
0 0
0
1
0
1
1
0
1
1
1
1
0
1
1
0
0
0
1
0
1
0
1
1
1
0
Ponieważ w ostatniej kolumnie w ostatnim wierszu pojawiło się 0 zatem zdanie P nie jest tautologią. Nie
jest tez ono kontrtautologia, gdyż nie wystąpiły w ostatniej kolumnie same zera.
Tautologie do których często odwołujemy się w procesach dowodzenia , posiadają zwykle
specjalne nazwy, nawiązujące do ich strukturalnych własności. Do tych najbardziej znanych zaliczają się
[(p
q)
p]
q modus ponendo ponens
[(p
q)
q ]
p modus tollendo tollens
(p
q)
p
q prawa de Morgana
(p
q )
p
q
p
(
p
q) prawo Dunsa Szkota
(p
p)
p prawo redukcji do absurdu
[(p
q )
r]
[p
(q
r)] prawo eksportacji
[p
(q
r)]
[(p
q )
r] prawo importacji
[(p
q)
(q
r)]
(p
r) prawo sylogizmu warunkowego
IDEA DEDUKCJI
4
4
Termin dedukcja wiążę się na ogół z wyprowadzaniem jednych zdań z drugich. Dedukcja daje
się sprowadzić do wyprowadzania jednych zdań z drugich, za pomocą małych kroków tzw. Reguł
wyprowadzania, co do których każdy jest w stanie się zgodzić, że są poprawne. Pozostaje tylko
zgodzić się, co do tego, które reguły są poprawne na mocy samej oczywistości. Omówimy dwa ujęcia
systemu klasycznego rachunku zdań, w których to ujęciach będziemy mieli do czynienia z procesem
dedukcji. Ujęcia te pozwalają o każdym zdaniu klasycznego rachunku zdań rozstrzygnąć, czy jest ono
tautologią, czy też nie. W jednym z tych ujęć zwanym założeniowym systemem rachunku zdań będziemy
mieli do czynienia z tzw. założeniowymi dowodami wprost i nie wprost, w drugim zaś będziemy mieli do
czynienia ze zwykłymi dowodami wprost i nie wprost. Obydwa ujęcia dają wyobrażenia o tym, co to
znaczy dowód (w sensie matematycznym) oraz na czym polega proces dowodzenia.
A. Założeniowy system klasycznego rachunku zdań.
Dowód założeniowy jest najbliższy temu co nazywamy dedukcją w potocznym tego słowa
znaczeniu, niekiedy zwaną dedukcja naturalną. Żadne ze zdań nie jest w tym ujęciu wyróżnione, a w
procesie dedukcji główną rolę odgrywają reguły. Zakres stosowania tej metody jest jednak dość
ograniczony, gdyż odnosi się jedynie do tych systemów, czy teorii, dla których obowiązuje tzw.
twierdzenie o dedukcji. W dowodach założeniowych mamy do czynienia z dwoma typami reguł, z tak
zwn. (1) Regułą tworzenia założeniowych dowodów wprost i nie wprost (RDZ) oraz z (2) Regułami
pierwotnymi ( przyjętymi na mocy oczywistości) oraz wtórnymi ( przyjętymi poprzez udowodnienie)
dołączania nowych wierszy do dowodu (RDNW).
RDZ : jeśli istnieje założeniowy dowód wprost zdania
P* =„ P1
(P2
( P3
...
( Pn-1
Pn )...))”
dla n
1 to zdanie to jest tezą tego rachunku( tautologia klasycznego rachunku zdań )
(2) RDNW:
P
Q P
(a) RO(reguła odrywania): P (b) DK (reguła dołączania koniunkcji) : Q
Q P
Q
P
Q P
Q
OK. (reguła opuszczania koniunkcji): P Q
P Q
DA (reguła dołącznia alternatywy: P
Q P
Q
P
Q P
Q
OA (reguła opuszczania alternatywy):
P
Q
Q P
P
Q
5
5
DE ( dołączania równoważności): Q
P
P
Q
P
Q P
Q
(g) OE (opuszczania równoważności): P
Q Q
P
Założeniowy dowód wprost zdania P* tworzymy w następujący sposób:
Założeniowy dowód wprost zdania P
*
tworzymy w następujący sposób:
1. W n-1 początkowych wierszach dowodu wypisujemy kolejno zdania, P
1
, ..., P
n-1
jako założenia
dowodu.
2. Do dowodu można dołączyć jako nowe wiersze:
(a) tezy wcześniej udowodnione;
(b) wyrażenia uzyskane na podstawie dotychczasowych wierszy według RDNW .
3. Dowód jest zakończony jeśli w ostatnim wierszu występuje wyrażenie P
n
Ex.4 P
1
P
2
P
3
P
n
Zbuduj dowód założeniowy zdania P
*
=”(p
q)
[(q
r)
(p
r )]
1. p
q
2. q
r zał. dow.
3. p
4. q RO 1 i 2
5. r RO 2 i 4
Ex. 5 P1 P2 P3 Pn
Zbuduj dowód założeniowy zdania P*=”[p
q
r]
[p
(q
r)]”
1. p
q
r
2. p zał. dow.
3. q
4. p
q DK 2 i 3
5. r RO 1 i 4
6
6
Założeniowe dowody nie wprost tworzymy podobnie jak założeniowe dowody wprost, z tym ,że
dodatkowo w n- tym wierszu dowodu wpisujemy zdanie sprzeczne ze zdaniem Pn, tzn. gdy zdanie Pn
nie posiada negacji lub posiada parzysta ich liczbę wpisujemy
. Dowód jest zakończony po otrzymaniu
w nim dwóch wierszy sprzecznych.
Ex. 6
P1 Pn
Zbuduj dowód założeniowy nie wprost zdania P*=”[(p
q)
q ]
p”
1. ( p
q)
q zał. dow.
2. p zał. dow. nwp.
3. p
q
q OK. 1
5. q RO 3 i 2
sprzeczność wierszy 4 i 5
P1 Pn
Ex.7.
Zbuduj dowód założeniowy nie wprost zdania P*=”[(p
r)
(q
r)
(p
q )]
r”
1. (p
r)
(q)
(p
q ) zał. dow.
2.
r zał. dow. nwp.
3. p
r
4. q
r OK. 1
5. p
q
q MTT. (reguła wtórna z modus tollendo tolens)
9. p OA 5 i 8
10. r RO 3 i 9
sprzeczność wierszy 2 i 10
Zadanie:
Zbuduj dowód założeniowy nie wprost zdania P*=”[(p
q )
r]
[(p
r)
q ] „
Uwaga! Udowodnić najpierw implikacje w obydwie strony, a później zwykły dowód wprost.
7
7
AKSJOMATYCZNE UJĘCIE RACHUNKU ZDAŃ
Aksjomatyzacja logiki zdań nie jest zabiegiem koniecznym dla rozstrzygnięcia czy zdanie tego rachunku
jest tautologią czy też nie. Do tego celu wystarczają metoda matrycowa albo założeniowa. Powstało
jednak wiele aksjomatyzacji rachunku zdań, gdyż okazały się one dogodnym obiektem badań,
posiadającym specyficzne własności, a ponadto takie ujęcie logiki zdań daje pewne korzyści
dydaktyczne. Do elementów systemu aksjomatycznego zdań należą:
Aksjomaty, czyli zdania będące tautologiami tego rachunku.
Reguły pierwotne, które pozwalają przejść od jednych tautologii do innych.
Definicje, które pozwalają zastąpić terminy wtórne, a więc nie występujące w aksjomatach terminami
pierwotnymi, występującymi w aksjomatach.
Istnieje wiele aksjomatyzacji rachunku zdań różniących się ilością aksjomatów jak i ich doborem.
Jednym z najbardziej znanych aksjomatyzacji systemu klasycznego rachunku zdań jest system (
implikacyjno-negacyjny) polskiego logika J. Łukasiewicza.
SYSTEM AKSJOMATYCZNY ŁUKASIEWICZA
Aksjomaty
A1. (p
q)
[(q
r)
(p
r)]
A2. (
p
p)
p
A3. p
(
p
q)
Reguły pierwotne:
RP (reguła podstawiania): Jeżeli zdanie P jest tautologią, zawierającą zmienną zdaniową v, to po
podstawieniu zdania E za każde wystąpienie zmiennej v w P otrzymujemy zdanie P*, które także jest
tautologią.
RO: Jeżeli zdanie złożone P* =”P
Q” jest tautologią i P jest tautologią, to Q jest też tautologią
Definicje:
D1. P
Q =
P
Q
D2. P
Q =
(P
Q)
D3. P
Q = (P
Q)
(Q
P)
Tak sformułowane definicje są regułami zastępowania (RZ) w tezach systemu zdań zawierających
terminy pierwotne, przez zdania zawierające terminy zdefiniowane i odwrotnie.
Dowód prowadzimy podobnie jak dowód założeniowy, z tym, że punktem wyjścia dowodu
zamiast założeń przyjmujemy aksjomaty a zamiast reguł dołączania nowych wierszy do dowodu
stosujemy reguły pierwotne (RP i RO) oraz (RZ)
Ex.8 Niech P = „p
p”. Zbuduj dowód zdania P na gruncie aksjomatyki Łukasiewicza dla klasycznego
rachunku zdań.
8
8
1. (p
q)
[(q
r)
(p
r)] A1.
2 .[p
(
p
p)]
[((
p
p)
r)
(p
r)] RP 1 (q/
p
p)
[p
(
p
p)]
[((
p
p)
p)
(p
p)] RP 2 (r/p)
p
(
p
q) A3
p
(
p
p) RP 4 (q/p)
((
p
p)
p)
(p
p) RO 3 i 5
(
p
p)
p A2
p
p RO 6 i 7
EX. 9 Niech P = „p
p”. Zbuduj dowód zdania P na gruncie aksjomatyki Łukasiewicza dla
klasycznego rachunku zdań.
1. p
p Teza udow.
2. p
p
p
p RP 1 (p/ p
p)
3. (
p
p)
p
p RZ D1 i 2
4. p
p Teza udow.
5.
p
p RP 4 (p/
p)
6. p
p RO 3 i 5
Metoda założeniowa a aksjomatyzacja klasycznego rachunku zdań.
a) Zarówno metoda założeniowa jak i aksjomatyczna daje wyobrażenie o tym, czym jest dowód w
sensie matematycznym
b) każde zdanie dowodu w dowodzie aksjomatycznym jest tezą systemu, tymczasem w dowodzie
założeniowym nie są tezami systemu;
c) w systemie aksjomatycznym siła inferencyjna zawarta jest w aksjomatach, w systemie założeniowym
w regułach;
d) metoda aksjomatyczna ma charakter bardziej uniwersalny, metoda założeniowa ma zastosowanie na
gruncie tych systemów, dla których obowiązuje twierdzenie o dedukcji.
e) metoda aksjomatyczna jest na ogół trudniejsza niż założeniowa- nie wiadomo z góry jakie powinny
być początkowe wiersze dowodu;
DEFINICJA DOWODU
Dowodem D zdania B w oparciu o zbiór zdań X przyjętych jako założenia nazywamy ciąg zdań, takich,
że D={D
1
, D
2
, ..., D
n
}spełniających następujące warunki:
a) B= D
n
(ostatnie zdanie tego ciągu jest identyczne z B);
b) każde zdanie D
k
ciągu D, gdzie (1
k
n ) albo należy do X albo jest tautologią, albo jest
wyprowadzone z wcześniejszych zdań ciągu za pomocą reguł wnioskowania.
9
9
NOTACJA BEZNAWIASOWA ŁUKASIEWICZA
Beznawiasowa notacja Łukasiewicza zwana też notacja polską, polega na tym, że każdy funktor
prawdziwościowy zarówno jednoargumentowy jak i dwuargumentowy poprzedza swe argumenty,
zamiast, jak w przypadku dwuargumentowych, znajdować się między nimi. Argumenty zaś wypisuje się
od lewa do prawa. Strukturalne własności zdania złożonego są zachowane bez używania nawiasów.
Przy tym dla oznaczenia operatorów logicznych stosuje się duże litery alfabetu. I tak, dla oznaczenia
negacji( N), dla koniunkcji (K), dla alternatywy (A), dla implikacji (C), dla równoważności (E).
Ex10 . (a) Niech zdanie P=”
(p
p). Przedstaw go w notacji beznawiasowej.
Ustalamy najpierw kolejność symboli w zdaniu P, zaczynając od funktorów
1 3 2 4 5
P=”
( p
p), a zatem wypisując te elementy zdania w zaznaczonej kolejności otrzymujemy zdanie
P’=”NKpNp” identyczne z P.
4 3 5 2 6 7 1 8 9
P=”[( p
q)
q]
p, a zatem otrzymujemy postępując jak wyżej zdanie P’
P’=”CKCpqNqNp” identyczne z P.
Ex11.
a) Przedstaw zdanie złożone P podane w symbolice beznawiasowej w postaci strukturalnej, gdzie
P=”CKApqrKCprCqr”.
1 a1 a2
4 d1 d2 5 e1 e2 6 f1 f2
P=”C K A p q r K C p r C q r
2 b1 b2 3 c1 c2
Zdanie P’= [(p
q)
r ]
[(p
r)
(q
r)]
(b) Niech zdanie P=”CKKCprCqrApqr”
1 a1 a2
3 c1 c2 4 d1 d2
P=” C K K C p r C q r A p q r
10
10
2 b1 b2
Zdanie P’= [(p
r)
(q
r)
(p
q)]
r
Notacja polska ma duże zastosowanie przy translacji wyrażeń arytmetycznych na język wewnętrzny
maszyny, przy równoczesnym wykorzystaniu stosowej organizacji pamięci komputera.
Zadanie: Przedstaw aksjomaty Łukasiewicza dla klasycznego rachunku zdań w postaci notacji polskiej.
LOGIKA WIELOWARTOŚCIOWA
1
,
1
2
,...,
1
2
,
1
1
,
0
n
n
n
n
U podstaw klasycznego rachunku zdań legło założenie o dwuwartościowości wszystkich zdań w
sensie logicznym. Uwolnienie się od tego założenia prowadzi do rachunków zdań wielowartościowych. I
tak np. J. Łukasiewicz wprowadzając trzecią wartość logiczną zbudował trójwartościowy rachunek
zdań Ł3. Podobnie jak on a niezależnie od niego postą pił E. Post. Jeśli przyjąć, że n oznacza ilość
dopuszczalnych wartości logicznych, w systemie wielowartościowym, to system taki ma następujące
wartości:
Dla n = 3 mamy następujące wartości logiczne: 0, ˝, 1
Dla n = 4 mamy zaś: 0, 1/3, 2/3,1
Główna inspiracją zbudowania przez Łukasiewicza logiki trójwartościowej były rozważania dotyczące
determinizmu. Zdania, które dotyczyły przyszłości mogły przyjmować jedną z trzech wartości
logicznych. I tak:
0 - przyjmują te zdania, dla których istnieje obecnie przyczyna wykluczająca ich zajście;
1- przyjmują te zdania, dla których istnieje obecnie przyczyna powodująca ich zajście
1/2 -przyjmują te zdania, dla których nie istnieje obecnie przyczyna powodująca ich zajście, ani też
przyczyna wykluczająca ich zajście.
Ex.12 Weźmy przykład zdań dotyczących przyszłości i oceńmy je pod względem wartości logicznych.
Niech
p = ”Ziemia będzie kulista”;
q = ” Ziemia będzie nieruchoma”
r = „Ludzie w 2100 r. pobudują osiedla na Marsie”
a) zdanie „p” jest prawdziwe, gdyż istnieje obecnie przyczyna powodująca zajście zdarzenia, że Ziemia
jest kulista
b) zdanie „q” jest fałszywe, gdyż istnieje obecnie przyczyna wykluczająca zajście zdarzenia że Ziemia
jest nieruchoma”
11
11
c) r jest niezdeterminowane, czyli posiada wartość 1/2, gdyż nie istnieje obecnie przyczyna powodująca
zajście zdarzenia budowania osiedli przez ludzi na Marsie, ani też przyczyna wykluczająca zajście
takiego zdarzenia.
Podstawową sprawą pozostaje zbudowanie matryc dla zdań złożonych w Ł3. Oczywiście tabelki
charakteryzujące klasyczne operatory są tutaj niewystarczające. Jednakże Łukasiewicz podając takie
charakterystyki zachował dotychczasowe „zdrowe” intuicje logiczne jakie tkwiły w L, chodzi tu głównie
o implikację, która o ile poprzednik posiada wartość logiczna mniejszą lub równą następnikowi o tyle
całe przyjmuje wartość 1.
Oto główne warunki dla matryc Ł3
Np.=1-p
Apq = max{p, q}
Kpq = min{p, q}
jeśli p
q, to Cpq=1
jeśli p>q, to Cpq=1-p+q
Na tej podstawie możemy zbudować matryce dla zdań złożonych w Ł3
1) dla negacji
p Np
1 0
½ ½
0
1
2) dla koniunkcji (Kpq)
q p 1
½
0
1
1
½
0
½
½
½
0
0
0
0
0
3) dla alternatywy (Apq)
q p 1
½
0
1
1
1
1
½
1
½
½
0
1
½
0
4) dla implikacji ( Cpq)
q p 1
½
0
12
12
1
1
1
1
½
½
1
1
0
0
½
1
Ex. 13 Zbuduj matrycę dla Epq wiedząc, że Epq=KCpqCqp. Najpierw zbudujemy dwie matryce dla P
= Cpq i Q = Cqp, a następnie dla KPQ
p q P Q KPQ
1 1 1 1 1
1 0 0 1 0
0 1 1 0 0
0 0 1 1 1
1 ½ ½ 1 ½
½ 1 1 ½ ½
0 ½ 1 ½ ½
½ 0 ½ 1 ½
Wyniki z powyższej matrycy można więc zebrać, i przedstawić podobnie jak dla pozostałych
operatorów logicznych dla Ł3.
q p 1
½
0
1
1
½
0
½
½
1
½
0
0
½
1
Rachunek zdań Ł3 można budować metoda matrycową podobnie jak w przypadku L, czyli
klasycznego rachunku. Zdanie jest tautologia Ł3 gdy przyjmuje wartość 1 (prawdę) . W innych
rachunkach wielowartościowych, ze względu na trudności w interpretacji nowych wartości logicznych
nie mówi się o prawdzie, lecz tzw. wartości wyróżnionej. Dokonano też aksjomatyzacji tego rachunku.
Ex14. Sprawdź, czy zdanie P=” p
p „oraz zdanie Q =”
(p
p)” są tautologiami Ł3.
Ex3. Sprawdź, czy zdanie P=” p
p „oraz zdanie Q =”
(p
p)” są tautologiami Ł3.
a) P= ApNp
p Np ApNp
1 0 1
13
13
0 1 1
½ ½ ½
b) Q= NKpNp
p Np KpNp NKpNp
1 0 0 1
0 1 0 1
½ ½ ½ ½
Logika trójwartościowa Łukasiewicza jest zawarta w logice klasycznej, tzn., że każda tautologia
Ł3 jest tautologią L, lecz nie odwrotnie. Z powyższych matryc widać, że ważne prawa klasycznego
rachunku zdań jak tzw. prawo wyłączonego środka i tzw. prawo niesprzeczności, posiadające przy tym
ciekawe i zgodne z intuicjami interpretacje, a także długie tradycje w logice nie są tautologiami Ł3.
Szczególnie dużą klasę problemów, dla których systemy wielowartościowe znajdują
zastosowanie stanowią problemy przyrodoznawstwa. Rozumowania bowiem dotyczące mikroświata
prowadzone przy użyciu logiki klasycznej, okazują się rodzić sprzeczności na gruncie tych teorii, które
go dotyczą. . Zauważono bowiem, że własności algebraiczne operatorów fizyki kwantowej mają
charakter inny niż narzuca logika klasyczna. W tym celu m in. została zbudowana przez G. Birkhoffa i
J. von Neumana tzw. logika kwantowa. Ciekawe są również analogie między logikami
wielowartościowymi a tzw. logikami rozmytymi, znajdujące zastosowania w komputerowych systemach
ekspertowych.
ANALIZA ROZUMOWAŃ
We wszystkich niemal rozumowaniach matematycznych i nie tylko opieramy się bezpośrednio
lub pośrednio na prawach rachunku zdań. Spośród rozumowań do najważniejszych należą
wnioskowanie i dowodzenie. W praktyce mamy często do czynienia z wnioskowaniami i dowodami
poprawnymi i niepoprawnymi. Jeżeli rozumowanie - wnioskowanie bądź dowód spełniają warunki,
które powinien spełniać wnioskowanie lub dowód wnioskowanie, to rozumowanie takie nazywamy
14
14
poprawnym, w przeciwnym przypadku nazywamy go niepoprawnym. Przeprowadzane dotąd
rozumowania miały charakter formalny, jednakże i faktycznie przeprowadzane rozumowania, mające
charakter nieformalny, można poddać formalizacji.
Ex. 15 Mamy następujące rozumowanie: „Jeżeli będę się uczył lub jestem geniuszem, to zdam egzamin.
Jeżeli zdam egzamin, to będę mógł uczęszczać na następne wykłady. Zatem, jeżeli nie zostanę
dopuszczany do następnych wykładów, to nie jestem geniuszem.”
Niech
p= ”będę się uczył”
q = „jestem geniuszem”
r =” zdam egzamin”
s =”zostanę dopuszczony do następnych wykładów”
Przesłanki:
P1= ” Jeżeli będę się uczył lub jestem geniuszem, to zdam egzamin”
P2 = „ Jeżeli zdam egzamin, to będę mógł uczęszczać na następne wykłady”
Wniosek:
W= „ jeżeli nie zostanę dopuszczany do następnych wykładów, to nie jestem geniuszem.”
METODA MATRYCOWA
P1= ”p
q
r”
P2 = „r
s”
W =”
s
q”
Jeżeli zdanie Q=„ P1
P2
... Pn
W ” jest tautologią, to wnioskowanie jest formalnie poprawne,
tzn. w niosek wynika logicznie z przesłanek, w przeciwnym przypadku jest formalnie niepoprawne.
Sprawdzimy metodą matrycową skróconą , czy zdanie Q jest tautologią.
1 0 0
1 1 1 0
(p
q
r)
(r
s)
(
s
q)
0 0 0 0 0 0 11
1
0
1
15
15
Sprzeczność w wartościowaniu. Zdanie q=0 w pierwszym wystąpieniu, a w drugim wystąpieniu q= 1.
DOWÓD ZAŁOŻENIOWY
WPROST
1. p
q
r
2. r
s zał.
3.
s
4. (r
s)
(
s
r ) prawo transpozycji
5.
s
r RO 4 i 2
6.
r RO 5 i 3
7. (p
q
r)
[
r
( p
q )] prawo transpozycji
8.
r
( p
q ) RO 7 i 1
9.
( p
q ) RO 8 i 6
10.
( p
q )
(
p
q) prawo de Morgana
11.
( p
q )
(
p
q) OE 10
12.
p
q RO 11 i 9
13.
q OK. 12
NIE WPROST
1. p
q
r
2. r
s zał.
3.
s
4 q zdnwp.
5. p
q DA 4
6. r RO 1 i 5
7. s RO 2 i 7
sprzeczność wierszy 7 i 3
EX 16. Wiemy, że jeśli program komputerowy działa poprawnie, to zaczyna i zakończy swoje działanie.
Wiemy też, że nasz program rozpoczął swoje działanie i nie działał poprawnie. Wnioskujemy stąd, że
program nie zakończył działania.
Niech
p = „ program rozpoczął działanie”
q = „program zakończył działanie”
r = „ program nie działa poprawnie”
P1= „
r
p
q”
P2 =” p
r
W= „
q „
DOWÓD ZAŁOŻENIOWY (WPROST)
1 „
r
p
q
16
16
2. p
r zał..
3. p
q
q prawo opuszczania koniunkcji
4. (
r
p
q)
(p
q
q)
(
r
q) prawo syl. warunkowego
5. (
r
p
q)
(p
q
q) DK 1 i 3
6.
r
q RO 4 i 5
7. r OK. 2
8.
q ? ? ? 6 i 7
Wniosek:
a) źle prowadzony dowód
b) brak dowodu
Sprawdźmy, metodą matrycową, czy zdanie Q=„(
r
p
q)
( p
r)
q” jest tautologią.
1 1 0
Q=”(
r
p
q)
( p
r)
q”
1 1 1 1 1 1
Brak sprzeczności w wartościowaniu, a zatem zdanie Q nie jest tautologią. W związku z tym zdanie
q
= „program nie zakończył działania” nie posiada dowodu z założeń
P1= „
r
p
q” i P2 =” p
r”. Oznacza to więc, że program może zacząć działanie i zakończyć
działanie i nie działać poprawnie z jakiegoś innego powodu.
Ex 17.
Na podstawie prawa (p
q)
[ (q
r)
(p
r)], reguł podstawiania i odrywania oraz
następujących twierdzeń arytmetyki
Tw. 1(x * y >0)
{[(x > 0)
(y > 0)]
[( x < 0)
(y < 0)]}
Tw.2{[(x > 0)
(y > 0)]
[( x < 0)
(y < 0)]}
(
x + y
=
x
+
y
)
udowodnić twierdzenie (x * y >0 )
(
x + y
=
x
+
y
)
1.( p
q)
[ (q
r)
(p
r)]
2. p
q Tw1 RP p / (x * y >0) ;
3. q
r. Tw2 q / {[(x > 0)
(y > 0)]
[( x < 0)
(y<0)]}
r /
x + y
=
x
+
y
4. (q
r)
(p
r) RO 1 i 2
5. p
r RO 3 i 4
5’. (x * y >0 )
(
x + y
=
x
+
y
)
Ex 18. Udowodnij twierdzenie:
(x + y >0)
{(x * y >0)
[(x > 0)
(y > 0)]}
17
17
Założenia:
(x + y >0)
[( x < 0)
(y < 0)]
(x * y >0)
[(x > 0)
(y > 0)]
[( x < 0)
(y < 0)]
Niech
p =” x + y >0”
q =”( x < 0)
(y < 0)”
r = „x * y >0”
s = „(x > 0)
(y > 0)”
TEZA: p
(r
s)
DOWÓD:
p
q
r
q
s zał.
(r
q
s)
[
s
(r
q)] prawo rach. zdań
s
(r
q) RO 3 i 2
q
(r
s) RP 4 s/ q ; q/ s
(p
q)
{[(
q
(r
s )]
[p
(r
s)]} syll. hipoteczny
[(
q
(r
s )]
[p
(r
s)] RO 6 i 2
p
(r
s) RO 7 i 5
8’.(x + y >0)
{(x * y >0)
[(x > 0)
(y > 0)]}
RACHUNEK KWANTYFIKATORÓW (I - RZĘDU)
Rachunek zdań nie stanowi całego języka stosowanego w rozumowaniach matematycznych.
Dopiero język rachunku zdań i język rachunku kwantyfikatorów pozwala na wyrażanie myśli dowolnych
teorii matematycznych i sprawdzanie ich sprawdzanie ich prawdziwości za pomocą formalnego
postępowania dowodowego.
Język rachunku kwantyfikatorów I rzędu
stałe nazwowe: a, b, c, ...
zmienne nazwowe : x, y, z,...
predykaty: F,. G, ..., S,..
operatory logiczne :
,
,
,
,
kwantyfikatory: Ex, Ax
znaki pomocnicze: ( ), [ ], { },...
18
18
Ad 1. Stałe nazwowe pełnią taką sama rolę w omawianym języku jak nazwy jednostkowe w języku
naturalnym, tzn. oznaczają one indywidua. W matematyce stałymi są np. nazwy liczb
Np. a = 5; b = żona Jana Kowalskiego
Ad. 2 zmienne nazwowe są zmiennymi, za które można podstawiać nazwy przedmiotów, ale ze ściśle
określonego zbioru D zwanego dziedziną dyskursu. Dzięki zmiennym w odróżnieniu od języka
naturalnego można budować tzw. funkcje zdaniowe, które nie są zdaniami oznajmującymi, a zatem nie
są też zdaniami w sensie logicznym. Dopiero wstawiając za zmienne określone nazwy otrzymujemy z
nich zdania w sensie logicznym: np.
a) x jest większe od 10
b) x jest mniejsze od y
c) x jest podzielne przez 2
d) x jest żoną y
Funkcjami zdaniowymi nie są takie wyrażenia, jak: x + y, czy x2 - z, gdyż po podstawieniu nie sa
zdaniami lecz nazwami.
Ad 3. Predykaty oznaczają własności albo relacje. Np. F= „być liczba naturalną”, R=” jest większe
niż” itp. Zamiast pisać :Maria jest żoną Andrzeja - można zapisać R(a, b), zamiast pisać : x jest liczba
naturalną, można napisać N(x). Argumentami predykatu są stałe nazwowe lub zmienne nazwowe.
Predykaty występują więc ze swoimi argumentami np. P(x), Q(x, y), czy S(x, y, z). Predykaty można
dzielić w zależności od ilości jego argumentów na jedno, dwu, trzy i więcej argumentowe. Np. F= „być
liczba naturalną”, R=” jest większe niż” itp. Zamiast pisać: Maria jest żoną Andrzeja - można zapisać
R(a, b), zamiast pisać: x jest liczba naturalną, można napisać N(x). W matematyce stałymi
predykatowymi są np. symbole relacji: >, <, >=, <=, identyczności: =, czy różności:
.
Ad 4. Operatory logiczne pełnia analogiczna role jak w rachunku zdań, tzn. łączą zdania z predykatami
np. [ (1= 0)
(2
3 )]
[
(2 > 7)
(2 + 5 = 7)] a także funkcje zdaniowe. np ( jeśli P(x, y)
oznacza x > y, a R(x, y) oznacza x
y a S( x, y) oznacza x < y, to wypowiedź: ( x >y )
(x
y)
(x < y) można zapisać : P(x, y)
R(x, y)
S(x, y)
Ad 5. Zwroty takie, jak: „dla każdego x” oraz „dla pewnego x”, „ dla niektórych x” lub „ istnieje takie
x, że” odgrywają w języku matematyki zasadniczą rolę i łącznie z operatorami logicznymi, stałymi i
zmiennymi pozwalają już na wypowiadanie każdej myśli matematycznej. Są one nazywane
kwantyfikatorami. Pierwsze z tych wyrażeń nazywamy kwantyfikatorem ogólnym lub dużym, natomiast
pozostałe nazywamy szczegółowym lub egzystencjalnej albo małym. Kwantyfikator mały symbolizowany
jest przez Ex, duży Ax, duży. Często alternatywnie używa się innych symboli
Kwantyfikatory wiążą zmienne. Wyrażenia znajdujące się w nawiasie występującym
bezpośrednio po kwantyfikatorze nazywamy zasięgiem. Np. w wyrażeniu Ay [x + x = x + y], zasięgiem
kwantyfikatora jest wyrażenie: x + x = x + y, natomiast w wyrażeniu: Ax Ay (x >y)
(x
y)
zasięgiem kwantyfikatora Ay jest wyrażenie x >y a zasięgiem kwantyfikatora Ax jest wyrażenie Ay (x
>y). Zamiast pisać Ax Ay piszemy często Axy. Mówimy, że zmienna występująca w wyrażeniu przy
symbolu kwantyfikatora jest przez ten kwantyfikator związana, w przeciwnym przypadku jest zmienną
wolna.
19
19
Ex 19. Wskazać zakresy kwantyfikatora w następujących zdaniach predykatywne. Wyróżnić zmienne
wolne i związane. Kreski nad zmiennymi wskazują, że zmienna w danym wystąpieniu jest zmienną
związaną
(a) Ax[Ey [((x + y)
2
< z)
( u + x < v)]
( y +x = u)]
(b) Ay[Ex [((x + y)
2
< z)
( u + x < v)]
( z +x = u)]
Zasięgiem kwantyfikatora Ax jest wyrażenie Ey [((x + y)2 < z)
( u + x < v)]
( y +x = u)], zaś
zasięgiem kwantyfikatora Ey jest wyrażenie [((x + y)2 < z)
( u + x < v)]. Zmienne związane są u
góry podkreślone.
Zasięgiem kwantyfikatora ogólnego A jest wyrażenie Ex [((x + y)2 < z)
( u + x < v)]
( z +x = u)], zaś zasięgiem kwantyfikatora szczegółowego E jest wyrażenie [((x + y)2 < z)
( z + x < v)].
Jeżeli wszystkie zmienne występujące w funkcji zdaniowej zostaną w każdym swym wystąpieniu
związane kwantyfikatorami, to funkcja staje się zdaniem. Np. funkcja zdaniowa (x + y = y + x)
staje się zdaniem Ax Ay (x + y = y + x), gdyż zarówno zmienna x i y w każdym swym wystąpieniu
zostały związane kwantyfikatorami.
Ex 20. Które z poniższych wyrażeń są zdaniami, a które tylko funkcjami zdaniowymi?.
P(x, y, z)
Ax P(x, y, z)
E x Ax P(x, y, z)
Ax Ey Az P (x, y, z)
Ponieważ tylko w przypadku d) wszystkie zmienne zostały związane, zatem tylko w tym przypadku
wyrażenie jest zdaniem.
PRAWA RACHUNKU KWANTYFIKATORÓW
W rachunku zdań rozpatrywane były takie zdania złożone, które przy dowolnym podstawieniu
wartości logicznych za zdania składowe przyjmowały wartość 1 , czyli prawdę. Takie wypowiedzi są
nazywane tautologiami rachunku zdań. Przez analogię z rachunkiem zdań wypowiedzi ( formuły)
rachunku kwantyfikatorów, które są prawdziwe w każdej dziedzinie przy dowolnej interpretacji
predykatów, które w nim występują, tzn. przy dowolnym rozumieniu symboli F, G, P, R, Q itd. jako
wyrażeń odnoszących się do pewnych własności lub relacji z danej dziedziny.
I Prawa rozdzielności kwantyfikatorów
20
20
Ex [P (x)
Q(x)]
Ex P (x)
Ex Q(x)
Ax [P (x)
Q(x)]
Ax P (x)
Ax Q(x)
II Prawa de Morgana dla kwantyfikatorów
1.
Ex P(x)
Ax
P(x)
2.
Ax P(x)
Ex
P(x)
III. Prawa zastępowania kwantyfikatorów
Ax P(x)
Ex
P(x)
Ex P(x)
Ax
P(x)
IV. Prawa przestawiania kwantyfikatorów
Ax Ay R(x, y)
Ay Ax R(x, y)
Ex Ey R(x, y)
Ey Ex R(x, y)
ExAy R(x, y)
Ay Ex R(x, y)
V. Inne prawa
Ax P(x)
P(a) schemat podstawiania
P(a)
E(x) P(x) prawo abstrahowania od konkretności
METODA ZAŁOŻENIOWA DOWODZENIA TEZ RACHUNKU KWANTYFIKATORÓW
Rachunek kwantyfikatorów otrzymujemy dołączając do reguł pierwotnych założeniowego
systemu rachunku zdań - w odpowiednio rozszerzonej postaci i wzbogacamy je o reguły pierwotne dla
kwantyfikatorów. To rozszerzenie polega na tym, że termin zdanie rozumiemy obecnie jako termin
oznaczający dowolną funkcję zdaniową lub zdanie rachunku kwantyfikatorów.
Reguły pierwotne dla kwantyfikatorów:
Ax P(x)
OA: reguła opuszczania kwantyfikatora ogólnego
P(x)
Np. z założenia Ax (x = x) wyprowadzamy wyrażenie x = x
P(x)
Ax P(x) DA: reguła dołączania kwantyfikatora ogólnego ( zmienna x nie może być
zmienną wolną w założeniach dowodu)
21
21
Np. z założenia x > 2 wyprowadzamy wyrażenie x >2
x=2, ale nie można wyprowadzić z niego
wyrażenia Ax (x > 2
x = 2), gdyż zmienna x jest wolna w założeniu .
Ex P(x)
P(a) OE1: reguła opuszczania kwantyfikatora szczegółowego ( stosując tę regułę
kilkakrotnie wprowadzamy nową stałą różną od stałych systemu i od uprzednio
wprowadzonych w tym dowodzie za pomocą tej reguły)
Ex R( x, y)
R(a
y
, y) OE2: ( stała musi być zrelatywizowana do zmiennej wolnej y będącej w zasięgu
kwantyfikatora)
Np. mamy dwa założenia 1) Ex (x =2) i 2) Ex (x = 4). Z 1) można wyprowadzić zdanie 3) a =2 , lecz
z 2) nie można już wyprowadzić zdania 4) a = 4
Np. z założenia 1) Ex ( x > y) ( dla dowolnej liczby y istnieje większa od niej liczba) nie można
wyprowadzić wyrażenia 2) a > y ( pewna liczba jest większa od dowolnej liczby y) ale można
wyprowadzić 3) a
y
>y ( od dowolnej liczby x jest większa pewna liczba ay)
P ( a) P(x) P(y)
Ex P(x) ; Ex P(x) ; Ex P(x) DE: (dołączania kwantyfikatora szczegółowego)
Np. jeżeli mamy założenie 1) a= 5, to można wyprowadzić za pomocą tej reguły zdanie
2) Ex (x = 5) ( stąd, że dowolny lub pewien określony przedmiot ma własność P wynika, żde istnieje
przedmiot posiadający tę własność )
DOWODY ZAŁOŻENIOWE
Ex. 21. Zbudować dowód założeniowy poniższego twierdzenia
Ex Ay R(x, y)
Ay Ex R(x, y)
1. Ex Ay R(x, y) zał.
2. Ay R(a, y) OE 1
3. R(a, y) OA 2
4. Ex(x, y) DE 3
22
22
5. Ay Ex(x, y) DA 4
Ex 22. Zbudować dowód założeniowy poniższego twierdzenia
P(x)
Ex Q(x)
Ex [P(x)
Q(x)]
1. Ex P(x)
Ex Q(x) zał.
2. Ex P(x) OK. 1
3. Ex Q(x)
4. P(a) OE 2
5. Q(b) OE 3
6. P(a)
Q(b) DK 5 i 6
Urywa się dowód - niemożliwość zastosowania reguły DE
Ex. 23. Zbudować dowód założeniowy poniższego twierdzenia
Ay Ex R(x, y)
ExAy R(x, y)
1. Ay Ex R(x, y) zał.
2. Ex R(x, y) OA 1
3. R(a
y
,y) OE 2
4. Ay R(a
y
, y) DA 3
Urywa się dowód - niemożliwość zastosowania DE
Ex. 24
Udowodnij metodą założeniową, że zdanie Q=„Ex [ F(x)
G(x) ]
[Ex F(x)
Ex G(x)]” jest
tautologią rachunku kwantyfikatorów.
1.Ex [ F(x)
G(x) ] zał.
2. F(a)
G(a) OE 1
3. F(a)
4. G(a) OK. 2
5. Ex F(x) DE 3 i 4
6. Ex G(x)
7. Ex F(x)
Ex G(x) DK 5 i 6
Ex. 25
Udowodnij metodą założeniową, że zdanie Q = „Ex[ F(x)
G(x) ]
[Ex F(x)
Ex G(x)]” jest
tautologią rachunku kwantyfikatorów.
23
23
Ex[ F(x)
G(x)] zał.
Ex F(x)
F(a)
G(a) OE 1
F(b) OE 2
?
Niech F(x) będzie x < 0 i a G(x) będzie x2 < 0 wtedy otrzymujemy:
Q*= „Ex[(x < 0)
(x2 < 0)]
[Ex (x < 0)
Ex (x2 < 0)]
Ex. 26 Udowodnij metodą założeniową, że zdanie Q = „AxAy[ R(x, y)
S(x, y)]
[ExEy R(x, y)
ExEy S(x, y )]” jest tezą rachunku kwantyfikatorów.
1. AxAy [R(x, y)
S(x, y)] zał.
2. ExEy R(x, y)
3. R(a, b)
S(a, b) OA 1
4. R(a, b) OE 2
5. S(a, b) RO 3 i 4
6. ExEy S(x, y) DE 5
Ex. 27 Udowodnij metodą założeniową, że zdanie Ax P(x)
Ax Q(x)
Ax [P(x)
Q(x)] jest tezą
rachunku kwantyfikatorów.
Dowód założeniowy tzw. rozgałęziony (wiersze z podwójną numeracją)
1. Ax P(x)
Ax Q(x) zał.
1.1 Ax P(x) zał dod.
1.2. P (x) OA 1.1
1.3 P(x)
Q(x) DA 1.2
1.4 Ax [P(x)
Q(x)] DA 1.3
Ax P(x)
Ax [P(x)
Q(x)] 1.1
1.4
2.1 Ax Q(x) zał dod.
2.2 Q(x) OA 2.1
2.3 P(x)
Q(x)] DA 2.2
2.4 Ax [P(x)
Q(x)] DA 2.3
3. Ax Q(x)
Ax [P(x)
Q(x)] 2.1
2.4
4. {Ax P(x)
Ax [P(x)
Q(x)]}
{Ax Q(x)
Ax [P(x)
Q(x)]}
. {Ax P(x)
Ax Q(x)}
Ax
[P(x)
Q(x)] Prawo dyl konst. pr.{(p
r)
.(q
r)
(p
q)
r}
5. {Ax P(x)
Ax [P(x)
Q(x)]}
{Ax Q(x)
Ax [P(x)
Q(x)]}
. {Ax P(x)
Ax}
DK 1, 2, 3
6. Ax [P(x)
Q(x)] RO 4i 5
Ex. 27 Zapisz następujące wypowiedzi w języku kwantyfikatorów
24
24
Każdy matematyk jest muzykalny
Niektórzy matematycy są muzykalni.
Żaden matematyk nie jest muzykalny
Niektórzy matematycy nie są muzykalni
Tylko matematycy są muzykalni
Każdy matematyk jest uczniem pewnego matematyka
Pewien matematyk nie ma uczniów wśród matematyków.
Niech F= „być matematykiem”, G =”być muzykalnym”. D =zbiór ludzi a
x należy do D. R= ” być uczniem”
Ad. 1 Ax [F(x)
G(x)]
Ad. 2 Ex [F(x)
G(x)]
Ad. 3 Ax [F(x)
G(x)]
Ad. 4 Ex [F(x)
G(x)]
Ad. 5 Ax [G(x)
F(x)]
Ad. 6 Ax [F(x)
Ey (F(y)
R(x,y))]
Ad 7. Ex[F(x)
Ey (F(y)
R(y,x))]
Ex. 28 Zapisz następujące wypowiedzi w języku kwantyfikatorów
Istnieje ktoś kto ma przyjaciela
Każdy jest czyimś przyjacielem.
Każdy jest przyjacielem wszystkich
Nikt nie jest niczyim przyjacielem
Zaimki osobowe: „ktoś”, „nikt” , „wszyscy” są synonimami wyrażeń „ pewien człowiek”, „żaden
człowiek” i „ wszyscy ludzie”. Niech P=” być człowiekiem”, a R=” być przyjacielem”. D = zbiór
indywiduów a zmienne z, y należą do D.
Ad. 1 Ex[P(x)
Ey (P(y)
R(x,y))]
Ad. 2 Ax [P(x)
Ey (P(y)
R(x,y))]
Ad 3. Ax[P(x)
Ay (P(y)
R(x,y))]
Ad 4. Ax[P(x)
Ey (P(y)
R(x,y))]
Ex 29. Niech
y
x
y,
x
y,
x
będą funkcjami zdaniowymi określonymi dla liczb naturalnych. Za
ich pomocą , korzystając ze znanych operacji arytmetycznych, takich jak x+y, x * y, symboli dla liczb
oraz symboli logicznych, zapisać następujące funkcje
x jest liczba parzystą
x nie jest liczba parzysta
x nie jest liczba pierwszą
Nie istnieje największa liczba naturalna
Nie istnieje największa liczba pierwsza
25
25
Każda liczba przy dzieleniu przez 2 daje resztę zero lub 1
Pomiędzy liczbami n i 2n istnieje co najmniej jedna liczba pierwsza (Tw. Czebyszewa)
Każda liczba nieparzysta większa od 3 rozkłada się na sumę dwu liczb pierwszych
( hipoteza Goldbacha)
Ad 1. Ey x=2* y
Ad 2.
Ey x= 2 *y
Ad 3. EyEz [(
(y = x)
(y=1))
x=y*z]
Ad 4.
Ex Ay (x
y) co jest równoważne Ax Ey (x < y)
Ad 5. AxEt [AyAz x = y * z
y = 1
y = x]
[Ay A z ( t = y * z
y = 1
y = t)
x < t]
Ad 6. AxAyAz[(x =2*y +z
z < 2)
(z = 1
z = 0)]
Ad 7 An [ Ex(AyAz x = y * z
y = 1
y = x)
n)
*
2
x
x
(n
]
Ad 8 Ax[(x>3
Ey (x=2* y)
Ez(AwAt z = w * t
w = 1
w = z)
Ev(AwAt z = w * t
w =
1
w = v)
x=z+v] lub równoważnie
Ax(2*x+1>3)
Ez Ev (AwAt ((z = w * t
w = 1
w = z)
(z = w * t
w = 1
w = v))
x=z+v]
ZBIORY - PODSTAWOWE POJĘCIA
Zbiorami i relacjami zajmuje się nauka zwana teorią mnogości. Jednakże pojęcie zbioru można
wprowadzić także na gruncie rachunku kwantyfikatorów. Możemy mówić o dwóch koncepcjach
zbioru a) logicznej G. Fregego oraz matematycznej - Cantora i innych. Pojęcie zbioru ujętego logicznie
będzie się przedstawiało krótko mówiąc jako własność elementów, albo inaczej obiektów spełniających
pewną funkcję zdaniową.
Niech „{x: P(x)}” lub „
P(x)"
xˆ
oznacza zbiór tych x, że P(x) . Symbol „{: }” oznacza operator
abstrakcji, który tworzy nazwę zbioru z predykatu. Sens symbolu „
” ustala tzw. prawo eliminacji: y
{x: P(x)}
P(y). W myśl tego prawa przedmiot y jest elementem zbioru tych x, które maja własność
P wtw. gdy przedmiot y ma własność P. Na oznaczenie zbiorów używamy najczęściej symboli A, B, C
.... .Wyrażenie „x
A” czytamy „x jest elementem zbioru A” lub „x należy do zbioru A”. Zamiast
wyrażenia „
x
A” piszemy „x
A” „ x nie należy do A”.
1. Zbiór uniwersalny
V={ x: x = x}x
V
x = x nazywamy zbiorem pełnym (należą do niego wszystkie te przedmioty, które
spełniają funkcje zdaniową x = x) . Ponieważ powyższą definicję można zapisać następująco:
x
V
x = x a tezą jest „Ax (x = x)”, zatem tezą jest też
Ax (x = x)
Ax
V stwierdzającą, że każdy przedmiot należy do zbioru pełnego
26
26
2. Zbiór pusty
={x: x
x} nazywamy zbiorem pustym (należą do niego wszystkie te przedmioty, które spełniają
funkcję zdaniową x
x. Ponieważ powyższą definicję można zapisać następująco: x
: x
x
a tezą jest „
Ex (x
x)”, zatem tezą jest też
Ex (x
x)
Ex x
stwierdzającą, że żaden
przedmiot nie należy do zbioru pustego
Ex. 30. Niech zbiór pełny V będzie zbiorem liczb naturalnych. Przy użyciu funkcji zdaniowych
z= x*y, x/y i kwantyfikatorów zapisać funkcje zdaniowe jednej zmiennej wyznaczające zbiory
liczb parzystych - A
liczb nieparzystych - B
liczb pierwszych - C
zbiór jednoelementowy złożony z 3 - D
a) x
A
Ey (x=2* y)
b) x
B
Ay [Ez (y =2* z)
(x/y)]
c) x
C
AyAz [ x = y * z
y =x
y =1]
d) x
D
Ay[ x = y
y =3]
Ex. 32. Elementami zbiorów mogą być również zbiory. Jeżeli A jest dowolnym zbiorem, to {A}
symbolizuje zbiór jednostkowy, którego elementem jest zbiór A., co zapisujemy A
{A}.
A
{A}, tak samo jak a
{a}. Ponadto porządek elementów w zbiorach nie odgrywa żadnej roli,
zatem{a, b}={b, a}
Wśród podanych niżej zbiorów A,. B, C, D wskaż
a) zbiór o najmniejszej liczbie elementów
b) zbiór o największej liczbie elementów
c) zbiory identyczne
d) zbiory mające dokładnie jeden element wspólny
e) zbiory nie mające żadnego elementu wspólnego
A={1, 2, 3,. 4, 5}
B={2, {1, 4}, {3, 5, 6}}
C={{1, 2, 3, 4, 5}}
D={3, {2}, {{5}}}
E={{3-1}, 3, {{3+2}}}
OPERACJE NA ZBIORACH I ICH GEOMETRYCZNE INTERPRETACJE
1. Sumą A
B nazywamy taki zbiór złożony z tych elementów, które należą do zbioru A lub do B
x
(A
B)
x
A
x
B
A B
27
27
2. Iloczynem ( przekrojem) A
B nazywamy taki zbiór złożony z tyc elementów, które należą do A i
należą do B
x
(A
B)
x
A
x
B
V
a
3. Różnicą A – B nazywamy taki zbiór złożony z tych elemntów, które należą do A, a nie należą do B
x
(A – B)
x
A
x
B
V
3. Dopełnieniem zbioru A nazywamy taki zbiór A’ złożony z tych wszystkich elemntów, które nie
należą do zbioru A
x
A’
x
A
a zatem A’=V-A
V
5. Dwa zbiory A i B są równe wtw. , gdy każdy elemnt który należy do zbioru A należy takżę do B i
na odwrót
x
A
x
B
6. Między zbiorami A i B zachodzi relacja zawierania się ( inkluzji) A
B wtw. gdy każdy elemnt który
należy do zbioru A należy także do B
x
A
x
B
V
Ex. 33. Obliczyć A
B, A
B, A-B, B-A dla następujących zbiorów
A={a, b, c}, B={c, d}
A={{a, b}, c}, B={c, d}
A B
A
B
A
A B
B
A
28
28
A={{a, {a}}, a}, B={a, {a}}
A={a, {a}, {b}}, B={{a}, {b}}
TWIERDZENIA RACHUNKU ZBIORÓW
Opierając się na wprowadzonych definicjach (sumy, iloczynu, różnicy, dopełnienia , zawierania ) oraz na
prawach rachunku zdań można udowodnić odpowiednie twierdzenia dotyczące zbiorów.
Aksjomat ekstensjonalności dla zbiorów
Ax(x
A
x
B)
A=B
Aksjomat ten stwierdza, że zbiory złożone z tych samych elementów są identyczne
DOWODY TWIERDZEŃ
Założeniowe
1. A=B
Ax (x
A
x
B)
1. A=B zał.
2. . x
A
x
A taut. p
p
3. x
A
x
B Ex I 1 i 2
4. Ax (x
A
x
B) DAk 3
Reguła ekstensjonalności:
Ex.I:
V1= V2
P
P(V1// V2)
Reguła ExI : Jeżeli żadna zmienna wolna wyrażenia V1 nie jest związana w wyrażeniu P na miejscu
zastąpienia; żadna zmienna wolna wyrażenia V2 nie staje się związana na miejscu zastąpienia w
wyrażeniu stanowiącym wynik zastąpienia
2. A=B
A
B
B
A
A=B zał.
A=B
Ax (x
A
x
B) Tw. Udow.
Ax (x
A
x
B) RO 1 i 2
Ax (x
A
x
B)
Ax [(x
A
x
B)
(x
B
x
A)]
taut. (p
q )
(p
q)
(q
p)
29
29
5. Ax [(x
A
x
B)
(x
B
x
A)] RO 4 i 3
6. Ax (x
A
x
B)
Ax (x
B
x
A) Prwo rozkła. Kw. Ogóln. na konjuncję
7. A
B
B
A Def. zaw i 6
3. A
B
A
B=A
A
B zał.
Ax (x
A
x
B) Def zaw.i 1
Ax(x
A
x
B
x
A) taut. (p
q)
(p
q
p)
Ax(x
A
B
x
A) Def Ilocz. Zbiorów i 3
A
B =A RO Aks. Ekstens. i 4
Ex 34. Podać dowody praw de Morgana dla zbiorów i podać ich interpretację graficzną
( A
B)’= ‘A
’B
(A
B)’= A’
B’
PRAWA ALGEBRY ZBIORÓW
Prawa algebry zbiorów są zbudowane ze zmiennych reprezentujących nazwy zbiorów, stałych:
,
, -, V,
,
, = oraz operatorów logicznych. Nie występuje w nich symbol
1. A
A prawo zwrotności zawierania się zbiorów
2. A
B
B
C
A
C prawo przechodniości zawierania się zbiorów
3. A
B= B
A prawa przemienności iloczynu
4. A
B= B
A prawa sumy zbiorów
5. A
B = (A’
B’)’ prawo zastępowania sumy zbiorów iloczynem
6. A
B = (A’
B’)’ ’ prawo zastępowania iloczynu zbiorów sumą
7. A’’= A dopełnienie dopełnienia zbioru A jest równe zbiorowi A
8. A
A’ =V suma zbioru A i jego dopełnienia jest równa zbiorowi uniwersalnemu
A zbiór pusty jest zawarty w dowolnym zbiorze
10. A
V każdy zbiór jest zawarty w zbiorze uniwersalnym
11. A
B
C
D
A
C
B
D Prawo dodawania inkluzji stronami
Ex. 35. Operacja A
B=(A-B)
(B-A) nazywa się różnicą symetryczną
podać interpretację graficzną
wykazać, że A
A=
wykazać, że (A
B)
C = A
(B
C)
wykazać, że jeżeli A
B=
, to A
B= A
B
30
30
RELACJE
Zbiory jednoelementowe i dwuelementowe
Def 1.
Zbiór jednolementowy utworzony z przedmiotu x, to taki zbiór , którego jedynym elementem jest
przedmiot x; oznaczamy go przez {x} i definiujemy:
y
{x}
y=x
Zbiór utworzony z elementów x, y, to taki zbiór którego jedynymi elementami są przedmioty x, y i
tylko te; oznaczamy go przez {x, y} i definiujemy:
z
{x,y}
z = x
z=y
Z definicji tej wynika następująca teza:
{x,y}={y,x}
Def 2. Za pomocą pojęć rachunku zbiorów można zdefiniować pojęcie pary uporządkowanej o
pierwszym elemencie x i drugim elemencie y, która będziemy oznaczać za pomocą symbolu
x, y
x, y
={{x}, {x,y}}
Na podstawie tej definicji można udowodnić twierdzenie:
x, y
=
z, u
x =z
y =u
x, y
z, u
x
z
y
u
x, y
y, z
Def. 3 Relacja dwuczłonowa R jest to zbiór par uporządkowanych; relacja n- członowa R jest zbiorem
n- elementowych układów uporządkowanych. Na oznaczenie relacji wprowadzamy następujące
symbole:
x, y
R
xRy
x1,..., xn
R
R(x1,..., xn)
Def. 4 Zbiór D(R) nazywa się dziedziną relacji R Dp(R) nazywa się przeciwdziedziną relacji
Zbiór C(R) nazywa się polem relacji R. Zbiory te określone są następująco:
a) x
D(R)
EyxRy
b) y
Dp(R)
Ex xRy
c) C(R)=D(R)
Dp(R)
Dla relacji n-członowej określa się pojęcie 1-ej, 2-ej,...n-ej dziedziny
C(R)=D1(R)
...
Dn(R)
WYKRESY RELACJI
Iloczyn ( produkt) kartezjański dwóch zbiorów
31
31
Def.
x, y
A
B
x
A
y
B
Zbiór A
B nazywa się iloczynem kartezjańskim zbiorów A i B. Jest to zbiór par uporządkowanych,
których pierwsze elementy należą do zbioru A, a drugie należą do B.
Relacja R o polu X
Zbiór R złożony z pewnych par uporządkowanych
x, y
, gdzie x i y należą do X nazywamy relacją
dwuczłonową R o polu X , tzn. podzbiór produktu kartezjańskiego R
X
X co zapisujemy
x, y
R.
Ta definicja jest w istocie definicją geometryczną. Na ogół rozumie się przez nią związek a nie zbiór.
Sam zbiór par nazywa się wtedy wykresem relacji R.
Ex. 36. Niech X={1, 2, 3, 4, 5, 6}. Produkt kartezjański Z= X
X składa się z 36 par. Rozpatrzmy
podzbiór R produktu Z złożony z następujących par uporządkowanych:
1,1
,
1,2
,
1,3
,
1,4
,
1,5
,
1,6
,
2,2
,
2,4
,
2,6
,
3,3
,
3,6
4,4
,
5,5
,
6,6
Jaka relacja zachodzi pomiędzy x i y?. Widać, że R jest relacja podzielności y przez x.
x, y
R
x/y
X 1 2 3 4 5 6
Wykres relacji podzielności R
Ex 37. Niech będzie relacja R w zbiorze A={1, 2, 3} określoną przez
..Narysuj wykres relacji R
3
0
.
1
2
Wykres relacji R jest grafem skierowanym z pętlami
OPERACJE ALGEBRAICZNE NA RELACJACH
Niech R i S będą dwoma relacjami w zbiorze X.
32
32
1. Sumą relacji R i S nazywa się relację T taką, która zachodzi między elementami x i y wtedy i tylko
wtedy, gdy między nimi zachodzi relacja R lub S co zapisujemy:
x R
Sy
xRy
xSy
2. Różnicą relacji R i S nazywamy relację Q taką, że która zachodzi między elementami x i y wtedy i
tylko wtedy, gdy między nimi zachodzi relacja R, a nie zachodzi relacja S, co zapisujemy
x R-S y
xRy
xSy
3. Iloczynem relacji R i S nazywamy relację Q taką, że która zachodzi między elementami x iy
wtedy i tylko wtedy, gdy zachodzi między nimi zarówno relacja R jak i S, co zapisujemy:
xR
Sy
xRy
xSy
4. Iloczynem względnym relacji R i S nazywamy relację Q taką, że , która zachodzi między
elemntami x i y wtedy i tylko wtedy, gdy istnieje takie z, że między x i z zachodzi relacja R, a między z i
y zachodzi relacja S, co zapisujemy:
x R | S y
E z (xRz
zSy)
5. Negacją relacji (dopełnieniem) R nazywamy relację R’ taką, która zachodzi między elementami x i
y wtedy i tylko wtedy, gdy nie zachodzi między nimi relacja R, co zapisujemy:
xR’y
xRy
6. Konwersem relacji 6. R nazywamy relację R
-1
taką, która zachodzi między elementami x i y wtedy i
tylko wtedy, gdy zachodzi między y a x relacja R, co zapisujemy
x R
-1
y
yRx
Ex 37. Udowodnić, że dla każdych x, y
X
xR
Sy
(xRy
xSy)
xR
Sy
(xRy
xSy)
xR’y
(xRy)
Dowód 1.
xR
Sy
x, y
R
S
x, y
R
x, y
S
xRy
xSy
WŁASNOŚCI FORMALNE RELACJI
1. Relacje zwrotne w zbiorze X oznaczamy symbolem refl(X) i definiujemy
R
refl(X)
Ax
X (xRx)
2. Relacje symetryczne w zbiorze X oznaczamy symbolem sym(X) i definiujemy
R
sym(X)
Axy
X (xRy
yRx)
3. Relacje asymetryczne w zbiorze X oznaczamy symbolem as(X) i definiujemy
33
33
R
as(X)
Axy
X (xRy
yRx)
4. Relacje antysymetryczne w zbiorze X oznaczamy symbolem ants(X) i definiujemy
R
ants(X)
Axy
X (xRy
yRx
x = y)
5. Relacje przechodnie w zbiorze X oznaczamy symbolem trans(X) i definiujemy
R
trans(X)
Axyz
X (xRy
yRz
xRz)
Axyz
X (xRy
yRz
xRz)
6.Relacje spójne w zbiorze X oznaczamy symbolem con(X) i definiujemy
R
con(X)
Axy
X (xRy
yRx)
RELACJA RÓWNOWAŻNOŚCI
Def. Relację R określoną w zbiorze X nazywamy relacją równoważności, jeżeli jest ona zwrotna,
symetryczna i przechodnia w zbiorze X i oznaczamy symbolem
.
Ex 38. Niech R będzie relacją „=” określoną w zbiorze X liczb rzeczywistych.
Dla każdych x, y, z
X zachodzi
x = x,
x =y
y = x
x =y
y = z
x = z
Relacja „=” jest relacją „
”.
Tw.1 (Zasada abstrakcji). Jeżeli w zbiorze X określona jest relacja równoważności „
”, to podzbiory:
[x], [y],... (zwane klasami abstrakcji relacji równoważności), określone następująco:z
[x]
z
x
spełniają następujące warunki:
każda klasa jest niepusta
suma wszystkich klas daje zbiór X
każde dwie klasy są albo rozłączne albo identyczne
dwie klasy są identyczne [x]=[y] wtedy i tylko wtedy, gdy x
y
Niech w zbiorze X określona będzie relacja „
”. Weźmy dowolne x
X. Tworzymy podzbiór [x] zbioru
X zwany klasa abstrakcji elementu x, złożony ze wszystkich tych elementów y
X, które są równoważne
x.
1. Wobec zwrotności „
” x
[x]
2. Wobec tego, że każdy element zbioru X tworzy klasę abstrakcji, zatem
[x]
[y]
...=X
3. Jeżeli x
y, to [x]=[y], gdyż z
[x]. wtw. gdy z
x, wobec przechodniości relacji „
”
z
y, czyli z
[y]. A zatem [x]
[y]. Podobnie z
[y] wtw gdy. z
y wobec przechodniości relacji „
”
z
x, czyli z
[x]. A zatem [y]
[x]. A zatem [x]=[y]
4. Jeżeli x
y, to [x]
[y] =
. Załóżmy[x]
[y]
. Istnieje takie z, że z
[x] i. z
[y]. Stąd z z
x i z
y, a wobec przechodniości relacji „
” x
y. A zatem jeżeli x
y,
34
34
to [x]
[y] =
.
Zasada abstrakcji ma dla matematyki wielkie znaczenie, gdyż pozwala z elementów jakiegoś zbioru
przedmiotów, w którym jest określona relacja równoważności, tworzyć nowe obiekty - klasy abstrakcji
tej relacji - klasy abstrakcji tej relacji, utożsamiając wszystkie przedmioty równoważne.
RELACJE PORZĄDKUJĄCE
Def. . Relację R określoną w zbiorze X nazywamy relacją porządkującą, jeżeli jest ona zwrotna,
antysymetryczna i przechodnia w zbiorze X
Ex.39. Niech relacja R oznacza relacje podzielności (x|y) ( x jest dzielnikiem y) w zbiorze X liczb
naturalnych.
x|x
jeżeli x|y i y|x, to x=y
jeżeli x|y i y|z, to x|z
Ex. 40 .Niech X będzie zbiorem podzbiorów ustalonego zbioru A={1, 2, 3}. Relacja R niech będzie
relacja inkluzji „
” czyli zawierania się podzbiorów. Narysuj graf tej relacji.
Podzbiory: {1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3},
{1, 2, 3}
{1, 2} {1, 3} {2, 3}
{1} {2} {3}
Graf relacji inkluzji zbioru X podzbiorów zbioru A={1, 2, 3}
Def. Relację R porządku w zbiorze X nazywamy relacją liniowego porządku, jeżeli spełnia własbość
spójności.
Ex. 40 Relacją liniowo porządkującą jest relacja „
” oraz relacja”
”. Nie jest nią natomiast relacja
„>” ani też relacja „<”, które są tylko relacjami częściowego porządku, gdyż nie śą spójne. Innym
ważnym przykładem relacji liniowego porządku jest tak zwane uporządkowanie leksykograficzne
"
"
przez
oznaczamy
i
.
35
35
Ex 41. Dla następujących relacji w zbiorze A={0, 1, 2, 3} określ, które z własności refl, sym, trans as
spełniają następujące relacje
x, y
R1, jeśli x +y=3
x, y
R2, jeśli x -y jest liczbą parzystą
x, y
R3, jeśli x
y
x, y
R3, jeśli max{x, y}=3
Narysuj wykres każdej z tych relacji. Nie rysuj strzałek, jeśli relacja jest symetryczna.
FUNKCJE
Pojęcie funkcji, aczkolwiek było od dość dawna używane przez matematyków doczekało się
stosunkowo dość późno precyzacji za sprawą G. Peano w terminach teorii relacji.
Def 1. Funkcją f określona na zbiorze X (zwanego dziedziną funkcji), o wartościach należących do
zbioru Y (zwanego przeciwdziedziną), nazywamy relację R, która każdemu elementowi dziedziny,
przyporządkowuje jeden i tylko jeden przedmiot przeciwdziedziny, co oznaczamy f: X
Y, a czytamy
zazwyczaj funkcja f odwzorowuje zbiór X w zbiór Y, co można opisać poniższym diagramem:.
x . f(x)
Funkcje określamy dwoma sposobami:
a) postać algebraiczna
podając zbiór X na którym jest określona i regułę lub wzór f(x) dla każdego x
X.
b) postać graficzna
podając podzbiór U par uporządkowanych
x, y
iloczynu kartezjańskiego X
Y takich, że
y = f(x)
x, y
f.
Rodzaje funkcji
1. Funkcja różnowartościowa
Funkcja f: X
Y jest funkcja różnowartościową, jeśli różnym elementom zbioru X funkcja
przyporządkowuje różne wartości w zbiorze Y.
2. Funkcja „na”
36
36
Funkcja f: X
Y jest funkcją przekształcającą zbiór X na Y, jeśli dla każdego y
Y, istnieje takie x,
że y = f(x), tzn. każdy element przeciwdziedziny jest wartościa funkcji dla jakiegoś argumentu.
3. Funkcja jako przekształcenie wzajemnie jednoznaczne:
Funkcję f: X
Y nazywamy przekształceniem wzajemnie jednoznacznym wtw. gdy jest
różnowartościowa i przekształca zbiór X na Y.
Ex 42. Określ rodzaj funkcji
a) b) c) d)
a) funkcja „na”
b) funkcja różnowartościowa
c) przekształcenie wzajemnie jednoznaczne
d) przekształcenie nie jest funkcją
Ex. 43. Niech X={1, 2, 3, 4, 5} i weźmy następujące funkcje ze zbioru X w zbiór X
f(n) = 6-n
g(n) = max{3, n}
h(x)= max{1, n-1}
- zapisz każdą z tych funkcji jako zbiór par uporządkowanych, tzn. wypisz elementy ich wykresów
- naszkicuj wykres każdej z tych funkcji
- które z tych funkcji są jednocześnie różnowartościowe i „na”
Operacje na funkcjach
1. Superpozycja
Niech będą dane funkcje f: X
Y i g: Y
Z. Dla każdego elementu x
X istnieje wówczas
dokładnie jeden element z
Z, taki że z =g(f(x)). Funkcje f i g wyznaczają więc nową funkcję h: X
Z
określoną w następujący sposób: h(x) = g(f(x)) dla każdego x
X. Funkcję h nazywamy superpozycją
lub złożeniem funkcji f i g i oznaczamy symbolem g
f. Z definicji mamy: (g
f)(x) = g(f(x))
f g
37
37
g
f
Ex. 44. Niech f(x)= x
2
a g(x) = x+1. Niżej podane funkcje wyraź za pomocą funkcji f i g
a)
h(x)= x
2
+1 h(x)=( g
f) (x)
b) h(x)= (x
+1)
2
h(x)=( f
g) (x)
c) h(x)= x
+2 h(x)=( g
g) (x) = g
2
(x)
d) h(x)= x
4
h(x)=( f
f ) (x) = f
2
(x)
e) h(x)= (x
2
+1)
2
h(x)= f
( f
g ) (x)
f) h(x)= (x
+2)
2
h(x)= f
( g
g ) (x)
2. Odwracanie funkcji
Funkcję g: Y
X nazywamy funkcją odwrotną do funkcji f: X
Y jeżeli y = f(x)(zbiór argumentów
funkcji g jest zbiorem wartości funkcji f) a x= g(y) (zbiór argumentów funkcji f jest zbiorem wartości
funkcji g) i dla każdego x
X zachodzi równość g(f(x)) = x. Funkcję g oznaczamy symbolem f
-1
.
Funkcje, które posiadają funkcje odwrotne nazywamy funkcjami odwracalnymi.
f
f
–1
38
38
Ex 45. Znajdź funkcje odwrotne następujących funkcji, przedstawiając je w podobnej formie np. f(x) =
2x f
–1
(x) =
x
2
1
a) f(x)= 2x – 3
b) f(x)= 3 - 5x
c)
3
1
)
(
x
x
f
d)
x
x
f
7
2
3
)
(
e)
x
x
f
1
10
8
)
(
Funkcja identycznościowa
Funkcję f : X
X przekształcającą każdy x
X na samego siebie nazywamy funkcja identycznościową
i oznaczamy I.
I(x) = x
Funkcja stała
Funkcję f : X
Y nazywamy funkcją stała, jeśli istnieje element y0
Y taki, że f(x)= y0 dla wszystkich
x
X.
Funkcja charakterystyczna
Weźmy zbiór X i jego podzbiór A. Funkcję określoną na zbiorze X, która przyjmuje wartość 1 dla
elementów x
A i wartość 0 dla x
A, nazywamy funkcja charakterystyczna zbioru A i oznaczamy
A.
1 dla x
A
A =
0 dla x
A
Ex. 46. Dla n
Z (zbiór liczb całkowitych) niech
]
1
)
1
[(
2
1
)
(
n
n
f
funkcja f jest funkcja
charakterystyczna pewnego podzbioru zbioru Z. Jaki to podzbiór?
Liczby parzyste dodatnie, gdyż f(n)= 1 dla n - parzystych i 0 dla nieparzystych
MOCE ZBIORÓW. ZBIORY NIESKOŃCZONE
39
39
Badania nad mocami zbiorów są jednym z podstawowych działów teorii mnogości. Terminem
pierwotnym jaki zostaje tu użyty jest termin równoliczność zbiorów, który to termin po raz pierwszy
został sprecyzowany przez G. Cantora twórcę matematycznej koncepcji zbiorów.
Def. 1. Zbiory X i Y nazywamy równolicznymi, jeśli istnieje funkcja różnowartościowa
f: X
Y przekształcająca zbiór X na Y. Funkcja f ustala równoliczność zbiorów X i Y. Jeżeli zbiory X
i Y są równoliczne, to piszemy X~Y.
Ex. 47. Jeżeli X={1, 2, 3, 4} a zbiór Y={2, 4, 6, 8}, to zbiory te są równoliczne, gdyż istnieje funkcja
różnowartościowa f określona następująco f(x)=2x, która przekształca zbiór X na Y.
Własności równoliczności
X ~ X
X~ Y
Y~ X
X~ Y
Y~ Z
X~ Z
Zachodzi 1. gdyż istnieje Ix(x)=x, która przekształca X na X
Zachodzi 2. gdyż jeśli istnieje f przekształcająca X na Y , to istnieje f -1: Y
X, przekształcająca Y na
X
Zachodzi 3., gdyż jeśli istnieje f: X
Y przekształcająca X na Y oraz jeśli istnieje g: Y
Z, to istnieje
f
g: X
Z, które przekształca X na Z
Określenie mocy zbioru
Każdemu zbiorowi X przyporządkowana jest pewna własność zwana mocą zbioru lub liczba
kardynalną, która nie zmienia się jeśli elementy zbioru X zastąpi się wzajemnie jednoznacznie przez
inne elementy, a także wtedy gdy zmieni się uporządkowanie elementów zbioru X.. Liczbę kardynalną
zbioru X oznaczamy przez X .
Zachodzą następujące zależności
( X = Y )
X~ Y
Jeżeli zbiór X jest zbiorem n -elementowym, to X = n
Ex 48. Niech X={1, 4, 6, 9}; X = 4. Jeśli X jest zbiorem pustym, to jego mocą jest liczba kardynalna
n = 0
Zbiory skończone, nieskończone i przeliczalne
Def. 1. X jest zbiorem skończonym wtw, gdy E n
N X = n
Def 2. X jest zbiorem nieskończonym wtw, gdy
E n
N X = n
40
40
Def. 3 Jeżeli N jest zbiorem liczb naturalnym, to
N
=
0
(alef zero)
Def. 4. Zbiorami przeliczalnymi nazywamy zbiory skończone lub nieskończone równoliczne ze zbiorem
N.
Ex. 49. Niech X będzie zbiorem liczb naturalnych parzystych, a Y zbiorem liczb naturalnych
nieparzystych. Jakiej mocy są zbiory X i Y.
Istnieje f: N
X, określone wzorem f(n)=2n, które przekształca N na X. Zatem jeżeli N~X, to
N
= X .
Skoro
N
=
0
, X =
0
Istnieje g: N
Y, określone wzorem f(n)=2n-1, które przekształca N na Y. Zatem jeżeli N~Y, to
N
= Y . Skoro
N
=
0
, Y =
0
Ex. 50. Wykazać, że jest zbiory X i Y są mocy
0
, to X
Y też jest mocy
0
.
Niech f: N
X i g: N
Y przekształca zbiór N odpowiednio na X i Y. Mamy zatem pary
f(1), g (1)
,
f(1), g (2)
,
f(1), g (3)
,....
f(1), g (n)
,...
f(2), g (1)
,
f(2), g (2)
,
f(2), g (3)
,....
f(2), g (n)
,...
f(3), g (1)
,
f(3), g (2)
,
f(3), g (3)
,....
f(3), g (n)
,...
............................................................................................
f(m), g (1)
,
f(m), g (2)
,
f(m), g (3)
,....
f(m), g (n)
,...
.................................................................................................
Ustawiając pary w odpowiednim porządku można ustalić funkcję h: N
X
Y
Która przekształca zbiór N na iloczyn kartezjański zbiorów X i Y.
h(1)=
f(1), g (1)
pierwsza przekątna
h(2)=
f(1), g (2)
h(3)=
f(2), g (1)
druga przekątna
h(4)=
f(3), g (1)
h(5)=
f(2), g (2)
trzecia przekątna
h(6)=
f(1), g (3)
.............................
Zatem Iloczyn kartezjański X i Y jest mocy
0
, co zapisujemy
Y
X
=
0
Def.1 Niech
oznacza zbiór liczb rzeczywistych.. Zbiory o mocy
c
nazywa się zbiorami o mocy
continuum.
Udowodnimy, że zbiór o mocy continuum jest nieprzeliczalny. W tym celu wystarczy udowodnić, że
zbiór liczb rzeczywistych
posiada moc różną od
0
tzn.
0
c
. Dowód taki pochodzi od Cantora i
nazywa się dowodem przekątniowym. Jest on dowodem nie wprost.
41
41
Dowód.
1. Załóżmy, że
=
0
Niech
składa się z wszystkich liczb rzeczywistych uporządkowanych w różnowartościowy
nieskończony ciąg: r
1
, r
2
, r
3
,...
Dla każdej liczby rzeczywistej istnieje jej rozwinięcie na ułamek dziesiętny nieskończony, wyrazy ciągu
można przedstawić następująco:
r
1
= c
1
, c
11
c
12
...
r
2
= c
2
, c
21
c
22
...
........................
r
n
= c
n
, c
n1
c
n2
...
.......................
gdzie c
n
jest częścią całkowitą, a c
n1
c
n2
, ... kolejnymi cyframi rozwinięcia dziesiętnego liczby rn.
Budujemy tabelę, która przyporządkowuje każdej liczbie naturalnej liczbę rzeczywistą.
1
2
3
4
.
n
.
c1, c11 c12 .................
c2,c21c22.......................
c3,c31c32 c33.................
c4,c41c42 c43 c44...........
.......................................cn,
cn1 cn2.............. cnn
..................................
1. Określmy liczbę r następująco: r = 0,d1 d2..., gdzie dla każdego n
1
0, gdy cnn
0
dn=
1, gdy cnn = 0
1.
a) Z założenia liczba r jest liczba rzeczywista, a więc należy do ciągu wszystkich liczb rzeczywistych
zebranych w tabeli.
b) Z drugiej strony liczba r różni się od każdej liczby rzeczywistej ciągu zebranego w tabeli, gdyż różni
się od niej przynajmniej na jednej pozycji nieskończonego rozwinięcia dziesiętnego liczby rn. Wystąpiła
sprzeczność a zatem
N
i
0
c
.
Nierówności między liczbami kardynalnymi. Twierdzenie Cantora-Bernsteina
Niech X = n i Y =m. Przyjmujemy, że liczba kardynalna n jest nie większa od liczby kardynalnej m,
jeżeli zbiór X jest równoliczny z podzbiorem zbioru Y. Wówczas
42
42
Każdy zbiór mocy n jest równoliczny z pewnym podzbiorem zbioru mocy m, co zapisujemy n
m
Jeżeli n
m i n
m to mówimy, że liczba kardynalna n jest mniejsza od liczby m i piszemy n
m
Ex 51. Zbiór N wszystkich liczb naturalnych jest równoliczny z podzbiorem zbioru
, czyli ze zbiorem
N
. Ponieważ zbiór
jak to ustalono jest nieprzeliczalny, zatem
N
a stąd mamy
0
c
Tw. Cantora-Bernsteina
1). Dla dowolnych liczb kardynalnych n i m zachodzi:
Jeżeli n
m i m
n, to n = m
Dla dowolnych zbiorów X, Y, Z zachodzi:
a) Jeżeli X
Y
Z, to X
Y
Z
b) Jeżeli X
Y
Z i X = Z , to X = Y = Z
Zbiór potęgowy. Twierdzenie Cantora
Niech f: X
{0, 1} będzie funkcją charakterystyczna zbioru X. Niech {0, 1}X oznacza zbiór
wszystkich takich funkcji, które nazywamy funkcjami charakterystycznymi podzbiorów zbioru X.
1. Dla każdego zbioru X zbiór wszystkich podzbiorów zbioru X jest równoliczny ze zbiorem{0, 1}
X
. Zbiór wszystkich podzbiorów zbioru X będziemy oznaczać symbolem 2X i nazywać zbiorem
potęgowym zbioru X. (należy pokazać, że istnieje funkcja g, która ustala równoliczność rodziny
wszystkich podzbiorów zbioru X i zbioru {0, 1}
X
)
2. Zbiór wszystkich podzbiorów zbioru N jest mocy c, więc
N
2 = c
Tw. Cantora
Dla każdego Zbioru X zachodzi:
X <
X
2
Wniosek:
1. Twierdzenie Cantora pozwala konstruować zbiory coraz wyższych mocy. Wychodząc np. ze
zbioru N wszystkich liczb naturalnych konstruujemy zbiory: N, 2
N
,
,...
2
,
2
2
2
2
N
N
, przy czym z Tw.
Cantora i 2. mamy:
43
43
0
=
N
<
N
2 <
N
N
2
2
2
2
2
< ...
2. Nie istnieje zbiór wszystkich zbiorów.
Gdyby bowiem istniał zbiór wszystkich zbiorów A, to rodzina 2A wszystkich podzbiorów A byłaby
sama podzbiorem A.
FUNKCJE OBLICZALNE
Funkcje obliczalne zwane też funkcjami rekurencyjnymi stanowią bardzo ważny dział logiki,
pozwalają one na precyzyjne sformułowanie wielu zagadnień dotyczących algorytmów. Okazuje się
bowiem, że za pomocą tego pojęcia można zdefiniować pojęcie efektywnej procedury rozstrzygania,
czy też obliczania. Intuicyjna treść pojęcia funkcji obliczalnej wyjaśnia się nieraz za pomocą
następującego sformułowania: Funkcja jest obliczalna, gdy istnieje efektywna metoda, za pomocą
której można obliczyć jej wartość dla dowolnego ciągu jej argumentów. W latach trzydziestych
udało się sprecyzować określenie pojęcia funkcji obliczalnej; podano też kilka równoważnych definicji
tego pojęcia.
Zamk(X,K)
Najmniejszy zbiór, zawierający zbiór X i zamknięty ze względu na zbiór operacji K.
Zbiór funkcji obliczalnych określa się często posługując się pojęciem najmniejszego zbioru,
zawierającego określone funkcje wyjściowe i zamkniętego na określone operacje.
Def 1. Zbiór X jest zamknięty ze względu na funkcję f , gdy dla każdego x f(x)
X
Ex1. Niech funkcja S będzie określona w następujący sposób S(n)=n+1 dla każdego n
N Zbiór liczb
naturalnych N, jest zamknięty na funkcję następnika, gdyż następnik liczby naturalnej też jest liczba
naturalną.
Def. 2. Zbiór X jest zamknięty ze względu na zbiór funkcji K co oznaczamy Zamk(X,K) wtedy i tylko
wtedy, gdy jest zamknięty ze względu na każdą funkcję należącą do K
Def. 3. Najmniejszy zbiór zawierający zbiór X i zamknięty ze względu na zbiór operacji (funkcji) K jest
to iloczyn wszystkich zbiorów, które zawierają zbiór X i są zamknięte ze ze względu na zbiór operacji
(funkcji)
Ex 51. Posługując się tym pojęciem można zdefiniować wiele zbiorów np. zbiór liczb naturalnych, zbiór
tautologii rachunku zdań itp.
Zbiór N liczb naturalnych, jest to najmniejszy zbiór zawierający zbiór X={0} i zamknięty ze względu na
funkcję S następnika
Zbiór tez (tautologii) aksjomatycznego systemu rachunku zdań Łukasiewicza Ł3, jest to najmniejszy
zbiór, do którego należą trzy aksjomaty i zamknięty ze względu na operację (reguły) odrywania,
podstawiania i zastępowania członów definicji
44
44
Definicja Funkcji obliczalnych
Funkcje obliczalne należą do takiego zbioru funkcji, których zarówno dziedziną jak i przeciwdziedziną
jest zbiór liczb naturalnych.
Zbiór X funkcji wyjściowych
Z(x), czyli jednoargumentowa funkcja stała, przyjmująca 0 dla dowolnego x
N
S(x)= x+1, czyli funkcji następnika
n
i
I
(x
1
,..., x
n
)= x
i
, czyli n-argumentowej funkcji identycznościowej
Ex. 52. Podaj wartości dla wyżej podanych funkcji, dla argumentów będących kolejnymi liczbami
naturalnymi
a) Z(1)=0, Z(2)=0,..., Z(10)=0, ...
b) S(0)=1, S(1)=2,...,S(10)=11, ...
c)
1
1
I (x)=x,
2
1
I ( x
1
, x
2
)= x
2
,
3
2
I ( x
1
, x
2,
x
3
)= x
3
, ...
Zbiór operacji K określania nowych funkcji
a) Składania funkcji wyrażonej wzorem
f (x
1
, . . .,x
n
)=g(h
1
(x
1
, . . .,x
n
),..., h
m
(x
1
, . . .,x
n
))
Mając kreślone funkcje g i h
i
, gdzie 1
i
m można określić nowa funkcję f będącą ich złożeniem.
Gdy n=1 i m=1wtedy mamy :
f (x)= g(h(x))
b) Rekursji prostej wyrażonej wzorami :
f (x
1
, . . .,x
n
,0)= g(x
1
, . . .,x
n
)
f (x
1
, . . .,x
n
,y+1) = h(x
1
, . . .,x
n,
y, f (x
1
, . . .,x
n
,y )
Mając kreślone funkcje g i h, można określić nowa funkcję f. Gdy n=1 wzory te przybierają postać:
f (0)=k, gdzie k
N
f (y+1)=h(y, f (y))
6) Operacja minimum efektywnego wyrażona wzorem:
f (x
1
, . . .,x
n
) =
y[g (x
1
, . . .,x
n
, y)=0] , gdy dla każdego x
1
, . . .,x
n
istnieje takie y gdzie
y oznacza
najmniejsze takie y
N, że funkcja g określona wzorem g(x
1
, . . .,x
n
, y)=0, pod warunkiem, że dla
każdego x1,..., xn istnieje takie y , że g(x
1
, . . .,x
n
, y)=0
Mając kreśloną funkcję g można określić nową funkcję f. Gdy n=1 mamy wtedy:
f(x)=
y[g(x,y)=0]. Określenie funkcji f polega na obliczeniu dla danego x kolejno wartości
g (x, 0), g (x, 1), g (x, 2),... tak długo aż natrafimy na pierwsze takie n.
N, że g (x, n)=0. To znalezione
n będzie wartością funkcji f.
45
45
Def 4. Zbiór funkcji obliczalnych jest to najmniejszy zbiór zawierający zbiór X funkcji określonych
wzorami 1-3 i zamkniętych ze względu na zbiór operacji K określonych wzorami 4-5.
Wniosek: Jeżeli funkcja f jest obliczalna, to jest ona otrzymana z funkcji 1-3 w skończonej ilości
operacji 4-6, tzn. istnieje skończony ciąg funkcji, którego ostatnim wyrazem jest funkcja f i którego
każdy wyraz bądź jest jedna z funkcji 1-3, bądź jest uzyskany z wcześniejszych od niego wyrazów tego
ciągu za pomocą jakiejś z operacji 4-6
Ex 53. Przykłady funkcji obliczalnych
a) f(x) = n , gdzie x
N a n jest stałą i n
N
Funkcję f można uzyskać z funkcji Z(x)=0 poprzez n-krotne składanie z funkcją następnika
f(x) =S(S(S...S(Z(x)))) = n
n razy
b) funkcja f(x, y)=x + y
Funkcję f można określić wychodząc od funkcji identycznościowej I i funkcji następnika S za pomocą
rekursji prostej, tzn.
f(x,0)= x+0= x=I(x)
f(x, y+1)=S(x+y)=S(f(x,y))
c) funkcja f(x, y)=x * y
Funkcję f można określić wychodząc od funkcji stałej Z, takiej, że f(x,0)=Z(x) i funkcji obliczalnej g(x,
y, z)= z+x za pomocą rekursji prostej, tzn.
f(x,0)=x*0=0=Z(x)
f(x, y+1)= (x*y)+x =g(x, f(x,y))
d) ) funkcja f(x)=[ x ], gdzie [x] oznacza cześć całkowitą z x.
Funkcję f można określić za pomocą operacji minimum efektywnego dla funkcji g określonej wzorem
g(x, y)= 0 (y+1)2>x
1 (y+1)2
x
a zatem f(x) =
y [ (y+1)2>x]=
y [g(x, y)=0]
Według tego określenia f(1) = [ 1 ]=1, f(2) = [ 2 ]=1,..., f(5) = [ 5 ]=2
Jest to operacja minimum, gdyż dla każdego x istnieje takie y, że (y+1)2>x. Tak np. dla x=1
g(1,y) =0 dla y=1, 2, 3, 4, ... jednakże minimalnym jest y=1, a zatem f(1) =1
Funkcja g jest zaś obliczalna z funkcji Z i S za pomocą rekursji prostej, gdyż
46
46
g(x, 0)=1=S(Z(x))
g(x, y+1)=Z(S(Zx))=Z(g(x, y), y)
Twierdzenie.
Zbiór funkcji obliczalnych jest zbiorem przeliczalnym o mocy
0
Dowód.
W definicji zbioru funkcji obliczalnych wychodzimy z przeliczalnego zbioru funkcji
(1) Z, S oraz
n
i
I . Ta ostatnia dla różnych n posiada przeliczalny zbiór układów zmiennych x1,..., xn a
więc mamy także przeliczalny ciąg funkcji
n
i
I . Oznaczmy zbiór (1) przez X0. Dołączmy do X0
wszystkie funkcje zdefiniowane przez a) złożenie, b) rekursję, c) minimum efektywne zastosowane do
zbioru funkcji X0 i oznaczmy je przez X1. Ogólne do zbioru Xi złożonego z funkcji dołączamy za
pomocą omówionych operacji nowe funkcje i tworzymy zbiór Xi+1. Powstaje ciąg X0
X1
X2. . .
zbiorów przeliczalnych. Każda funkcja obliczalna należy do jednego ze zbiorów Xi. Elementy zbiorów
X0 ,X1, X2... ustawiamy w ciągi:
X0=
...}
,
,
{
0
2
0
1
0
0
f
f
f
X1=
...}
,
,
{
1
2
1
1
1
0
f
f
f
X2=
...}
,
,
{
2
2
2
1
2
0
f
f
f
...............................
Licząc elementy na przekątnych ustawiamy je w ciąg:
,...
,
,
,
1
1
1
0
0
1
0
0
f
f
f
f
przypisując im kolejne liczby
naturalne. A zatem zbiór funkcji obliczalnych jest przeliczalny.
Uwaga: Można udowodnić, że moc zbioru wszystkich funkcji wielu zmiennych, o argumentach i
wartościach będących liczbami naturalnymi jest równa c .
Podanie konkretnego przykładu funkcji nieobliczalnej jest jednak bardzo trudne, gdyż większość
funkcji, z którymi spotykamy się w praktyce, to funkcje obliczalne.
Funkcje obliczalne mają szerokie zastosowanie w teorii maszyn cyfrowych. Komputery w swojej pracy
nie wykonują nic innego, jak operacje składania, schemat rekursji prostej i schemat minimum
efektywnego. Dla każdej funkcji obliczalnej istnieje urządzenie czy to mechaniczne lub elektroniczne (np.
arytmometr), o bardzo dużej pamięci do zapisywania wyników pośrednich, obliczy wartość funkcji dla
dowolnych argumentów. Wielkość pamięci która maszyna musi zużyć jest dla danego argumentu
skończona, choć nie daje się z góry oszacować, podobnie czas liczenia również nie daje się z góry
oszacować, choć jest skończony.
Teza Turinga
Funkcjami obliczalnymi są dokładnie te funkcje, dla których istnieje maszyna cyfrowa mająca
skończoną ilość stanów wewnętrznych i nieskończoną pamięć, zdolna w skończonym, choć z góry nie
dającym się oszacować czasie, obliczyć wartość funkcji dla zadanego argumentu i zatrzymać się po
wykonaniu obliczenia.
47
47
Teza Churcha
Każde zagadnienie dla którego istnieje efektywny sposób rozwiązania, daje się wyrazić w
odpowiednim tłumaczeniu za pomocą funkcji obliczalnych.
Ex 54. Zastosowanie funkcji obliczalnych w zagadnieniu gry w szachy:
Na 64 polach szachownicy znajduje się pewna ilość figur nie więcej niż 32, a nie mniej niż 2.
Każdemu ustawieniu figur można przyporządkować numer będący liczba naturalna. Ponumerujmy pola
liczbami 0d 1 do 64, figury zaś:
Białe : 1- pionek, 2- wieża, 3- skoczek, 4-goniec, 5-hetman, 6- król
Czarne: 7- pionek, 8- wieża, 9- skoczek, 10-goniec, 11-hetman, 12- król
Jeżeli na polu o numerze i nie stoi figura, to piszemy ci=0
Jeżeli na polu o numerze i stoi figura o numerze c, to piszemy ci= c. Piszemy ponadto c0=0, jeżeli ruch
maja białe , a c0=1 jeżeli ruch maja czarne. Niech q=13 będzie zasada numeracji
Pi=( c64 c63 c62... c1 c0)13 i=1, 2, ...n...
Niech
P1=(8 7 10 11 12 10 9 8 7 7 7 7 7 7 7 7 0 ...0 1 1 1 1 1 1 1 1 2 3 4 5 6 4 3 2 0)13
będzie początkowym ustawieniem, zaś
Pn=(1 0 0 0 7 0 4 0 0 0 2 0 0 0 0 12 0 6 0 0 2 0)
13
n - tym ustawieniem zapisanym w systemie 13-
nastkowym.
Można udowodnić, że funkcja f określona następująco:
1 jeżeli x jest numerem pozycji wygrywającej dla białych
2 jeżeli x jest numerem pozycji wygrywającej dla czarnych
f(x)= 3 jeżeli x jest numerem pozycji remisowej
0 jeżeli x nie jest numerem pozycji dopuszczalnej do gry w szachy
nie jest funkcją obliczalną. Wartość funkcji f dla liczby x przedstawionej przez Pn=1. Nie potrafimy
jednak obliczyć wartości funkcji f dla liczby x przedstawionej zapisem P1
Algebry Boole’a
1. Definicja Algebr Boole’a
48
48
Def.1 Algebrą Boole’a nazywamy zbiór X co najmniej dwóch elementów, jeżeli spełnione są
następujące warunki:
a) w zbiorze X istnieją dwa elementy wyróżnione, które oznaczamy przez 0 i 1
b) w zbiorze X określone są trzy operacje A
B, A
B, A” zwane odpowiednio sumą boole’owską,
iloczynem boole’owskim i dopełnieniem, które nie wyprowadzają poza zbiór X, tzn. dla każdych
elementów A i B należących do X również A
B, A
B, A” należą do X
c) na elementach zbioru X określona jest relacja równoważności oznaczona przez „=” spełniająca
następujący warunek: dla każdych elementów A, B, C należących do X, jeżeli A=B, to również
A’=B’, A
C =B
C, A
C =B
C
d) operacje wymienione w b) spełniają następujące aksjomaty
A1. A
B =B
A przemienność
B1. A
B =B
A
A2. A
(B
C)= (A
B)
(A
C) rozdzielność
B2. A
(B
C) = (A
B)
(A
C)
A3. A
0=A
B3. A
1=A
A4. A
A’=1
B4. A
A’=0 własności stałych
2. Przykłady Algebr Boole’a
a) Algebrą Boole’a jest algebra zbiorów
Niech Z={1, 2, 3},a X będzie zbiorem podzbiorów zbioru Z. Załóżmy, że
{1, 2, 3}=1; {1, 2}=e
1
; {1, 3}=e
2
; {2, 3}=e
3
; {1}=e
4
; {2}=e
5
; {3}=e
6
; {0}=0
Czyli X={{1, 2, 3}, {1, 2}, {1, 3}, {2, 3}, {1}, {2}, {3}, {0}}={1, e
1
,e
2
,e
3
,e
4
e
5
,e
6
,0}
Sprawdźmy, czy spełnione są aksjomaty algebry Boole’a dotyczące stałych 0, 1
Za A przyjmujemy pierwszy element, tzn. A={1,2,3}
A3. A
=A
1
0={1, 2, 3}
{0}={1, 2, 3}= e
1
B3. A
A’=0
1
(1
)’={1,2, 3}
{0}={0}=0
A4. A
A’=1
1
(1
)’ ={1,2, 3}
{0}={1,2, 3}=1
B4. A
1=A
1
1 ={1,2, 3}
{1,2, 3}={1,2, 3}= 1
49
49
b) Algebrą Boole’a jest też rachunek zdań
Niech X będzie zbiorem wszystkich formuł rachunku zdań, zawierających 0, 1 i zmienne p
1
, p
2,. . .,
zamkniętych ze względy na operacje :
,
. Zbiór X ma następującą postać:
X={0, 1, p
1,.
p
2, . . .,
p
1,. . .,
p
1
p
2, . . .,
p
1
p
2 ,. . .
}
Niech
„1” - oznacza symbol zdania prawdziwego
„0” - oznacza symbol zdania fałszywego
„
” - oznacza operację dopełnienia „ ’ ”,
„
”- oznacza operację iloczyn boole’owski „
”
„
”- oznacza operację sumy boole’owskiej „
”
„
” - oznacza relację równoważności
Sprawdźmy czy przy danej interpretackji spełnione są aksjomaty dla stałych Boole’a
A3. A
0=A
p
0
p
B3. A
A’=0
p
p
0
A4. A
A’=1
p
p
1
B4. A
1=A
p
1
p
c) Algebrą Boole’a jest algebra sieci kontaktowych
Niech X będzie zbiorem wszystkich możliwych dwubiegunowych sieci kontaktów, z których każdy
może być zamknięty, bądź otwarty. Elementami wyróżnionymi zbioru X będą:
0 - sieć składająca się z jednego, ciągle otwartego, kontaktu
1 -sieć składająca się z jednego, ciągle zamkniętego, kontaktu
operacje algebry boole’owskiej interpretujemy następująco:
„
” – mnożenie sieci
„
” – sumowanie sieci
„ ’ ” - negacja sieci
1. Jeżeli A i B są sieciami należącymi do X, to ich A
B jest siecią otrzymaną przez równoległe
połączenie sieci:
A
50
50
B
2. Jeżeli A i B są sieciami należącymi do X, to ich A
B jest siecią otrzymaną przez szeregowe
połączenie sieci:
A B
N
3. Negacja sieci polega na zmianie kontaktów z zamkniętych na otwarte, a z otwartych na zamknięte
oraz wszystkie połączenia równoległe na połączenia szeregowe, a szeregowe na równoległe
Negacją sieci:
A
B
Będzie sieć:
A B
Sprawdźmy aksjomaty dla stałych
A3. A
0=A
A
0
Sieć A
0 składa się z dwóch kontaktów A oraz 0 połączonych równolegle. Ponieważ kontakt 0 jest
stale otwarty więc działanie sieci zależy jedynie od kontaktu A. Sieć A
0 oraz A są więc równoważne
A
A
51
51
=
0
B3. A
A’=0
Sieć A
A’ składa się z sieci A oraz negacji A połączonych szeregowo
Jeżeli sieć A jest otwarta, to sieć A’ jest zamknięta i na odwrót. Za każdym razem suma sięci jest
jednak otwarta co odpowiada sieci zawsze otwarte 0
A A’ 0
=
Podobnie sprawdzamy aksjomaty:
A4. A
A’=1
B4. A
1=A
3. Twierdzenia algebry Boole’a
Tw1. W każdej algebrze Boole’a istnieje tylko jeden wyrózniony element 0 i jeden wyróżniony element
1.
Dowód ( niewprost): Załóżmy że twierdzenie nie jest prawdziwe, a więc istnieją dwa różne elementy 0 i
0* oraz 1 i 1*, takie że 0
0* i 1
1* spełniające aksjomaty algebry Boole’a dla wszystkich A. W
aksjomacie A3 A
0=A za A podstawmy najpierw 0*.
Mamy wówczas:
0*
0 = 0*
Ponieważ A3 jest on spełniony dla 0* otrzymujemy A
0*=A W aksjomacie A3 A
0*=A za A
podstawmy teraz 0.
Mamy wówczas:
0
0* = 0
Wobec przemienności operacji sumy algebraicznej „
” otrzymujemy:
0*
0=0
0*
0 = 0*
co jest sprzeczne z założeniem, że 0
0*. Analogicznie postępujemy dla 1 i 1*.
Tw. 2 Dla każdego elementu A dowolnej algebry Boole’a istnieje dokładnie jeden element B taki, że
A
B=1 i A
B=0
Dowód (niewprost): Załóżmy że element A ma dwa uzupełnienia A’ i A* :
1. A*= A*
0 A3
2. A*
0=A*
(A
A’) B4
3. A*
(A
A’)=(A*
A)
(A*
A’) A2
52
52
4. A*
A)
(A*
A’)= (A
A*)
(A*
A’) A1
5. (A
A*)
(A*
A’)=1
(A*
A’) A4
6. 1
(A*
A’)= 1
(A’
A*) A1
7. 1
(A’
A*)= (A
A’)
(A’
A*) A4
8. (A
A’)
(A’
A*) =(A’
A)
(A’
A*) A1
9. (A’
A)
(A’
A*)=A’
(A
A*) A2
10. A’
(A
A*)=A’
0 B4
11. A’
0=A’ A3
A*=A’ co jest sprzeczne z założeniem.
Tw. 3 Dla każdego elementu A algebry Boole’a A’’=A
Dowód:
1. A
A’=1 A4
2. A
A’=0 B4
4. A’
A=1 A1
5. A’
A=0 B1
6. A jest dopełnieniem A’
7. A’’=A Tw2.
Wyszukiwarka
Podobne podstrony:
Logika, KLASYCZNY RACHUNEK ZDAŃ
moduł 3 Klasyczny rachunek zdań, LOGIKA 2006
03 Klasyczny rachunek zdań świat fcji prawdziwościowychid 4395
03 Klasyczny rachunek zdań, świat fcji prawdziwościowych
1 Klasyczny Rachunek Zdań
Klasyczny rachunek zdań Adekwatność
Klasyczny rachunek zdań metoda 0 1
logika prawa rachunku zdań IOQCAYPZQONTXEX3IGUQQTLW3NNHKROP6XDFUQY
Modul 3 Klasyczny rachunek zdan
Klasyczny rachunek zdań Dedukcja naturalna
03 Klasyczny rachunek zdań świat fcji prawdziwościowychid 4395
więcej podobnych podstron