PODSTAWY LOGIKI I TEORII MNOGOŚCI

Pojęcia pierwotne logiki i teorii mnogości

I. zbiór

II. zdanie

III.wartość logiczna zdania

w(p)=1 zdanie jest prawdziwe

w(p)=0 zdanie p jest fałszywe

IV. x჎X

Aksjomaty logiki i teorii mnogości

A1 Istnieje pewien zbiór

A2 Istnieje pewne zdanie

A3 Dla dowolnych zdań
,
istnieją zdania
,
,
,
,
, których wartość logiczna zależy jedynie od wartości logicznych
i
w następujący sposób:

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

Z powyższego wynika istnienie zdania prawdziwego oraz istnienie zdania fałszywego.

Alternatywa wykluczająca - spójnik Ⴥ, w informatyce XOR

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

Kreska Sheffera - spójnik Ⴝ, w informatyce NAND

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

Interpretacja implikacji

Warunek wystarczający:
jest warunkiem wystarczającym na zajście

Warunek konieczny:
jest warunkiem koniecznym na zajście

Definicja Symbole
nazywamy funktorami zdaniotwórczymi

Definicja Litery symbolizujące zdania nazywać będziemy zmiennymi zdaniowymi, zaś wyrażenie utworzone ze zmiennych zdaniowych, funktorów zdaniotwórczych i ewentualnie nawiasów nazywamy schematami zdań

Definicja Schematy zdań, które stają się zdaniami prawdziwymi niezależnie od wartości logicznych tworzących je zdań nazywamy tautologiami

Zasada ekstensjonalności:

Jeśli S₁(p) jest dowolnym schematem rachunku zdań, S₂(p) jest schematem który powstaje z S₁(p) przez zastąpienie wszystkich lub niektórych symboli p symbolem q to schematy:

są prawdami rachunku zdań

Logiczna konsekwencja

ၢ nazywamy logiczną konsekwencją ciągu ၡ₁,…,ၡ_n jeśli przy każdym układzie wartości logicznych przyporządkowanym zmiennym zdaniowym występującym w ၡ₁,…,ၡ_n, ၢ, jeśli zdania ၡ₁,…,ၡ_n są zdaniami prawdziwymi, to ၢ też jest zdaniem prawdziwym.

Metody dowodzenia:

Dowód wprost:

Dowód nie wprost:

Dowód nie wprost przez sprowadzenie do sprzeczności:

Jeśli
to sprzeczność.

Dowód „w próżni”

,
- zdanie fałszywe

Dowód trywialny

,
- zdanie prawdziwe

Dowód konstruktywny - wskazuje obiekt

Dowód niekonstruktywny

Reguły wnioskowania:

Przykłady tautologii

Rachunek zbiorów:

A4 Dla dowolnych zbiorów A, B istnieje zbiór dla którego prawdziwe jest

zdanie x჎A ლ x჎B , czyli w(x჎A ლ x჎B)=1

Zbiór ten nazywamy sumą zbiorów A i B. Oznaczamy A჈B

Umowa: ~(x჎X) Ⴚ x჏X

A5 Dla dowolnych zbiorów A i B istnieje zbiór dla którego prawdziwe jest zdanie x჎A i x჏B. Zbiór ten nazywamy różnicą zbiorów A i B i oznaczamy A\B

Definicja Niech X będzie zbiorem, którego istnienie wynika z aksjomatu A1; na mocy aksjomatu A5 istnieje zbiór X\X. Zbiór ten nazywamy zbiorem pustym i oznaczamy symbolem ჆.

Uwaga w(x჎჆)=0

Definicja Powiemy, że zbiory A i B są równe jeśli w(x჎Aმx჎B)=1. Piszemy A=B.

Twierdzenie Niech A będzie dowolnym zbiorem. Wówczas A\A=჆.

Definicja Powiemy, że zbiór A zawarty jest w zbiorze B (A jest podzbiorem B) jeśli w(x჎Aპx჎B)=1. Piszemy wtedy A჌B.

Twierdzenie Niech A i B będą dowolnymi zbiorami. Wówczas:

1. ჆჌A

2. A჌A

3. A=B მ A჌B კ B჌A

Definicja Niech A i B będą dowolnymi zbiorami. Zbiór A\ (A\B) nazywamy iloczynem zbiorów A i B i oznaczamy AჇB.

Twierdzenie Dla dowolnych zbiorów A i B ich iloczyn AჇB={x: x჎A კ x჎B}

Prawa algebry zbiorów:

Niech A, B, C, X będą dowolnymi zbiorami:

1. AჇ( B჈C ) = ( AჇB) ჈ (AჇC)

2. A჈ (BჇC) = (A჈B) Ⴧ (A჈C)

3. X\(A჈B) = (X\A) Ⴧ (X\B)

4. X\(AჇB) = (X\A) ჈ (X\B)

5. AჇB჌A i AჇB჌B

6. A჌A჈B i B჌A჈B

7. Niech A჌X i B჌X. Wówczas AჇB=XმA=X კ B=X

Definicja Niech A჌X. Zbiór X\A nazywamy dopełnieniem zbioru A (do zbioru X) X\A oznaczamy A'

Uwaga. Jeśli we własnościach od I do VII założymy, że A჌X i B჌X to własności III oraz IV można zapisać w postaci;

(A჈B)' = A' Ⴧ B'

(AჇB)' = A' ჈ B'

Tak sformułowane własności III oraz IV noszą nazwę praw de Morgana dla rachunku zbiorów

Definicja Jeśli w(a჎A)=1 to mówimy, że a jest elementem zbioru A.

Definicja Niech X będzie dowolnym zbiorem. Wyrażenie ၪ(x) zawierające zmienną x, które staje się zdaniem (prawdziwym lub fałszywym) gdy w miejsce zmiennej x wstawimy dowolny element zbioru X nazywamy funkcją zdaniową, której zakresem zmienności jest zbiór X.

A6 Dla dowolnej funkcji zdaniowej ၪ(x) której zakresem zmienności jest zbiór X, istnieje zbiór tych elementów ze zbioru X dla których ၪ(x) jest zdaniem prawdziwym: {x჎X: w(ၪ(x))=1}. Zbiór ten zapisujemy w postaci {x჎X: ၪ(x) } i mówimy o nim jako o zbiorze tych elementów x჎X, które spełniają funkcję zdaniową ၪ(x).

Twierdzenie: Niech ၡ(x) i ၢ(x) będą funkcjami zdaniowymi o zakresie X. Wówczas:

1. {x჎X: ၡ(x) კ ၢ(x) } = {x჎X: ၡ(x) }Ⴧ {x჎X: ၢ(x) }

2. {x჎X: ၡ(x) ლ ၢ(x) } = {x჎X: ၡ(x) }჈ {x჎X: ၢ(x) }

3. {x჎X: ၡ(x) კ ~ၢ(x) } = {x჎X: ၡ(x) }\ {x჎X: ၢ(x) }

4. X \ {x჎X: ၡ(x) } = {x჎X: ~ၡ(x) }

Rachunek kwantyfikatorów:

Niech ၡ(x) będzie funkcją zdaniową, której zakresem zmienności jest zbiór X. Wówczas:

oznacza, że { x჎X: ၪ(x)} = X

oznacza, że { x჎X: ၪ(x)} Ⴙ჆

Prawa de Morgana dla rachunku kwantyfikatorów

Niech ၡ(x) będzie funkcją zdaniową, której zakresem zmienności jest zbiór X. Wówczas:

1. ~(
   ) მ
   

2. ~(
   ) მ
   

Prawa rozdzielności kwantyfikatorów względem funktorów zdaniotwórczych:

1. 
   მ (
   კ
   )

2. 
   მ (
   ლ
   )

3. 
   პ (
   კ
   )

4. (
   ლ
   ) პ
   

5. 
   პ [
   პ
   ]

6. 
   პ [
   პ
   ]

Przyjmijmy teraz, że S jest zdaniem lub funkcją zdaniową o zakresie zmienności zawartym w zbiorze X, która nie zależy w sposób efektywny od zmiennej x

2. 
   მ S ლ
   

3. 
   მ S კ
   

4. 
   მ S ლ
   

5. 
   მ S კ
   

Uwaga:
პ

Kwantyfikatory o zakresie ograniczonym:

Zapis
oznacza
.

Zapis
oznacza
.

A7 Dla dowolnego zbioru X istnieje zbiór złożony ze wszystkich jego podzbiorów. Zbiór ten oznaczamy 2^X i nazywamy zbiorem potęgowym zbioru X. A჎2^X oznacza, że A჌X.

Iloczyn kartezjański:

Niech AႹ჆, BႹ჆, a჎A i b჎B. Parą uporządkowaną o poprzedniku a i następniku b nazywamy zbiór { {a}, {a, b} } i piszemy (a,b).

A8 Niech AႹ჆ i BႹ჆. Istnieje wówczas zbiór złożony ze wszystkich par uporządkowanych o poprzednikach ze zbioru A i następnikach ze zbioru B. Symbolicznie piszemy AႴB

AႴB = { (a,b): a჎A კ b჎B }

Twierdzenie Niech ၪ(x,y) będzie funkcją zdaniową której zakresem zmienności jest zbiór XႴY. Wówczas:

I.

II.

III.

Relacje:

Definicja Każdy podzbiór iloczynu kartezjańskiego XႴY nazywamy relacją w zbiorze XႴY. W przypadku, gdy X=Y o zbiorze ၲ჌XႴX mówimy, że jest relacją w zbiorze X.

Uwaga Zamiast pisać, że dla x჎X i y჎Y, (x,y)჎ ၲ piszemy xၲy.

Definicja Relację ၲ჌ XႴX nazywamy relacją:

zwrotną jeśli
xၲx

przeciwzwrotną jeśli
~( xၲx )

symetryczną jeśli

( xၲy პ yၲx )

antysymetryczną jeśli

[( xၲy კ yၲx ) პ x=y ]

przechodnią jeśli


[( xၲy კ yၲz ) პ xၲz ]

równoważności jeśli jest zwrotna, symetryczna i przechodnia.

Oznaczenie: Relację równoważności będziemy oznaczać ~.

Definicja Niech x჎X oraz (X,~). Zbiór [x]={t჎X: x~t} nazywamy klasą abstrakcji.

Twierdzenie Niech (X,~). Wówczas:

(*)
[t]=[z] albo [t]Ⴧ[z]=჆

Definicja Relację
჌DႴP spełniająca warunek:

x
y კ
( x
z პ z=y )

nazywamy funkcją, której dziedziną jest zbiór D, a zbiorem wartości zbiór P. Piszemy
: D Ⴎ P.

Zamiast pisać x
y bądź (x,y)჎
, piszemy y =
(x).

Umawiamy się też warunek (*) zapisywać w postaci:

(**)

y =
(x)

Definicja: Niech
: D Ⴎ P oraz ჆ႹK჌D. Zdefiniujmy funkcję
: K Ⴎ P następująco:

=
. Funkcję taką nazywamy obcięciem funkcji
do zbioru K.

Definicja: Niech
: D Ⴎ P. Wykresem funkcji
nazywamy zbiór

W={ (x,y)჎ DႴP: y =
}

Definicja: Niech
: D Ⴎ P oraz A჌D i B჌P. Zbiór
nazywamy obrazem zbioru A przy odwzorowaniu
.

Zbiór:
nazywamy przeciwobrazem zbioru B przy odwzorowaniu
.

Definicja: Niech
: D Ⴎ P. Funkcję
nazywamy:

1. różnowartościową jeśli
   

2. odwzorowaniem „na” jeśli
   
   

3. odwzorowaniem wzajemnie jednoznacznym D na P jeśli jest różnowartościowa i „na”.

Rozważmy funkcję A:XႮ2^X. Jest to funkcja, która elementom zbioru X przyporządkowuje podzbiory zbioru X. W przypadku takich funkcji zamiast pisać A(x) piszemy A_x.

Definicja: Zbiór
nazywamy indeksowaną rodziną podzbiorów zbioru X.

Definicja: Niech
będzie indeksowaną rodziną podzbiorów pewnego ustalonego zbioru X. Zbiór
nazywamy sumą uogólnioną rodziny
. Zaś zbiór
nazywamy iloczynem uogólnionym rodziny
.

Twierdzenie Jeśli (X,~), to
.

Równoliczność zbiorów:

Definicja: Powiemy, że zbiór A jest równoliczny ze zbiorem B jeśli istnieje funkcja
odwzorowująca wzajemnie jednoznacznie A na B
: A
B.

Piszemy wtedy A~B. Przyjmujemy, że ∅ ~ ∅.

Twierdzenie: Dla dowolnych zbiorów A, B, C mamy:

1. A ~ A

2. A ~ B ⇒ B ~ A

3. ( A ~ B ∧ B ~ C ) ⇒ ( A ~ C )

Oznaczenie: Niech n∈N P(n)={1, 2, … , n}

Definicja: Zbiór A nazywamy skończonym jeśli

Uwaga: Fakt, że zbiór A jest skończony i niepusty zapisujemy

Definicja: Zbiór A nazywamy przeliczalnym jeśli jest on pusty lub skończony, lub równoliczny ze zbiorem N liczb naturalnych. Piszemy
.

Definicja: Zbiór A nazywamy nieprzeliczalnym gdy nie jest on przeliczalny.

Własności zbiorów przeliczalnych

Twierdzenie: Na to by zbiór A≠∅ był przeliczalny potrzeba i wystarcza by A był zbiorem wyrazów pewnego ciągu (niekoniecznie różnowartościowego).

Twierdzenie: Każdy podzbiór zbioru przeliczalnego jest zbiorem przeliczalnym. Każdy nadzbiór zbioru nieprzeliczalnego jest nieprzeliczalny.

Twierdzenie: Dla dowolnych zbiorów przeliczalnych A i B przeliczalnymi są również zbiory A∩B, A\B, A∪B.

Twierdzenie: Iloczyn kartezjański zbiorów przeliczalnych jest zbiorem przeliczalnym.

Twierdzenie: Suma przeliczalnej ilości zbiorów przeliczalnych jest zbiorem przeliczalnym.

Twierdzenie: Dla dowolnej funkcji obraz zbioru przeliczalnego jest zbiorem przeliczalnym.

Twierdzenie Cantora: Przedział <0,1> jest nieprzeliczalny

Algebry Boole'a

Definicja: Algebra Boole'a jest to zbiór B≠∅ z dwoma działaniami dwuargumentowymi ∧ i ∨, działaniem jednoargumentowym ` oraz różnymi elementami 0 i 1, spełniającymi następujące prawa:

1.B.

a)

x∨y = y∨x

}

prawa przemienności

b)

x∧y = y∧x

2.B.

a)

(x∨y)∨z = x∨(y∨z)

}

prawa łączności

b)

(x∧y)∧z = x∧ (y∧z)

3.B.

a)

x∨(y∧z) = (x∨y) ∧(x∨z)

}

prawa rozdzielności

b)

x∧(y∨z) = (x∧y) ∨ (x∧z)

4.B.

a)

x∨0 = x

}

prawa identyczności

b)

x∧1 = x

5.B.

a)

x∨x' = 1

}

prawa dopełnienia

b)

x∧x' = 0

Działanie ∨ nazywamy sumą, ∧ iloczynem, a działanie ` dopełnieniem.

Zasada dualności:

Jeśli zamienimy we wzorze prawdziwym we wszystkich algebrach Boole'a ∧ z ∨ oraz 1 i 0 to otrzymany wzór będzie prawdziwy we wszystkich algebrach Boole'a.

Twierdzenie: Następujące własności zachodzą w każdej algebrze Boole'a:

6.B.

a)

x∨x = x

}

prawa idempotentności

b)

x∧x = x

7.B.

a)

x∨1 = 1

}

następne prawa identyczności

b)

x∧0 = 0

8.B.

a)

(x∧y)∨x = x

}

prawa pochłaniania

b)

(x∨y)∧x = x

9.B.

a)

(x∨y)' = x'∧y'

}

prawa de Morgana

b)

(x∧y)' = x'∨y'

Definicja: W algebrze Boole'a definiuje się relację ≤ wzorem:

x≤y ⇔ x∨y=y

Uwaga: x < y oznacza, że x ≤ y oraz x≠y

x ≥ y oznacza, że y ≤ x

x > y oznacza, że y < x

Wniosek: W algebrze Boole'a relację ≤ zdefiniowaną za pomocą działania ∨ można zdefiniować za pomocą działania ∧ ponieważ zachodzi

x∨y = y ⇔ x∧y = x

Twierdzenie W algebrze Boole'a

1. x ≤ x

2. jeśli x ≤ y i y ≤ z to x ≤ z

3. jeśli x ≤ y i y ≤ x to x = y

4. jeśli x < y i y < z, to x < z

5. x∧y ≤ x ≤ x∨y

6. 0 ≤ x ≤ 1

Definicja: Atomem w algebrze Boole'a nazywamy niezerowy element a, który nie może być przedstawiony w postaci a = b∨c, gdzie a≠b i a≠c.

Twierdzenie: Niezerowy element x z algebry Boole'a jest atomem wtedy i tylko wtedy, gdy nie istnieje element y taki, że 0<y<x.

Twierdzenie: Jeśli B jest skończoną algebrą Boole'a, to każdy niezerowy element z B może być przedstawiony w postaci sumy różnych atomów. Ponadto sposób przestawienia jest jednoznaczny z dokładnością do kolejności atomów.

Twierdzenie: Każda skończona algebra Boole'a mająca n atomów jest izomorficzna z algebrą Boole'a P(S) wszystkich podzbiorów n-elementowego zbioru S.

Definicja: Funkcją boolowską n-argumentową nazywamy funkcję f: Bⁿ→B, gdzie Bⁿ =B×B×…×B (n czynników B), jest zbiorem ciągów zerojedynkowych długości n. Zbiór wszystkich n-argumentowych funkcji Boooleowskich oznaczamy symbolem BOO(n).

Definicja: Wyrażenie booleowskie jest to ciąg symboli wśród których występują stałe 0 i 1, pewne zmienne oraz działania booleowskie.

---