LOGIKA.

Zdaniem, w logice matematycznej nazywamy wyrażenie, któremu można przyporządkować jedną z dwóch wartości logicznych: prawdę lub fałsz. Przyjmujemy, że: 1 jest symbolem prawdy, a 0 symbolem fałszu.

Przykład zdań.

Łódź jest polskim miastem

2+3=8

We wszechświecie istnieją inteligentne istoty, które nie są Ziemianami.

Przykład wyrażeń, które nie są zdaniami:

Studenci są ludźmi zamożnymi.

Matematyka jest bardzo interesująca.

Będziemy używać następujących funktorów (spójników) zdaniotwórczych:

„nie” (negacja) symbol ~ (często w literaturze można spotkać symbol ¬)

„i” symbol ∧

„lub” symbol ∨

„jeżeli...to...” symbol ⇒

„wtedy i tylko wtedy, gdy” symbol ⇔

Zdanie zbudowane bez funktorów zdaniotwórczych jest zdaniem prostym. Zdanie w którym funktory takie występują nazywamy zdaniem złożonym.

NEGACJA. Jeśli mamy zdanie α, to zdanie ~α nazywamy negacją zadania α. Zależność logiczną zdania i jego negacji zapisujemy za pomocą tabelki:

α	~α
1	0
0	1

Zaprzeczeniem prawdy jest fałsz, zaprzeczeniem fałszu jest prawda.

KONIUNKCJA. Zdanie α∧β nazywamy koniunkcją zdań α i β. Zależność logiczną koniunkcji i zdań ją tworzących ilustruje następująca tabelka:

α	β	α∧β
1	1	1
1	0	0
0	1	0
0	0	0

Koniunkcja jest zdaniem prawdziwym tylko wtedy, gdy oba zdania są prawdziwe.

ALTERNATYWA. Zdanie α∨β nazywamy alternatywą zdań α i β. Zależność logiczną alternatywy i zdań ją tworzących ilustruje następująca tabelka:

α	β	α∨β
1	1	1
1	0	1
0	1	1
0	0	0

Alternatywa jest zdaniem prawdziwym tylko wtedy, gdy co najmniej jedno ze zdań ją tworzących jest prawdziwe.

IMPLIKACJA. Zdanie α⇒β nazywamy implikacją zdań α i β (czytamy: jeśli α, to β). Zależność logiczną implikacji i zdań ją tworzących ilustruje następująca tabelka:

α	β	α⇒β
1	1	1
1	0	0
0	1	1
0	0	1

Implikacja jest zdaniem fałszywym tylko wtedy, gdy z prawdy wynika fałsz.

Przykład implikacji prawdziwych.

Jeżeli 1+1=2, to 2+1=3.

Jeżeli 2 jest liczbą ujemną , to 2-2=0.

Jeżeli 2<1, to 3 jest liczbą parzystą.

RÓWNOWAŻNOŚĆ. Zdanie α⇔β nazywamy równoważnością zdań α i β (czytamy α wtedy i tylko wtedy, gdy β). Zależność logiczną równoważności zdań i zdań ją tworzących ilustruje następująca tabelka:

α	β	α⇔β
1	1	1
1	0	0
0	1	0
0	0	1

Równoważność jest zdaniem prawdziwym tylko wtedy, gdy oba zdania ją tworzące posiadają tę samą wartość logiczną.

TWIERDZENIE. Zapis α⇔β jest równoważny (α⇒β)∧(β⇒α).

TWIERDZENIE. Najważniejsze prawa rachunku zdań:

Prawa de Morgana

~(α ∧ β) ⇔ (~α ∨ ~β)

~(α ∨ β) ⇔ (~α ∧ ~β)

Prawo zaprzeczenia implikacji

~(α ⇒ β) ⇔ (α ∧ ~β)

Prawo zaprzeczenia równoważności

~(α ⇔ β) ⇔ (~(α ⇒ β) ∨ ~(β ⇒ α))

Prawo podwójnej negacji

~(~(α)) ⇔ α

Prawa przemienności

α ∧ β ⇔ β ∧ α  (koniunkcji)

α ∨ β ⇔ β ∨ α  (alternatywy)

Prawa łączności

α ∧ (β ∧ δ) ⇔ (α ∧ β) ∧ δ   (koniunkcji)

α ∨ (β ∨ δ) ⇔ (α ∨ β) ∨ δ   (alternatywy)

Prawa rozdzielności

α ∧ (β ∨ δ) ⇔ ((α ∧ β) ∨ (α ∧ δ)) (koniunkcji względem alternatywy)

α ∨ (β ∧ δ) ⇔ ((α ∨ β) ∧ (α ∨ δ)) (koniunkcji względem alternatywy)

Prawo kontrapozycji

(α ⇒ β) ⇔ (~β ⇒ ~α)

Przykładowy dowód jednego z tych praw - przemienności koniunkcji:

α	β	α∧β	β∧α	(α∧β)⇔(β∧α)
1	1	1	1	1
1	0	0	0	1
0	1	0	0	1
0	0	0	0	1

UWAGA. Prawdziwość zdania α ⇒ β wyrażamy mówiąc, że α jest warunkiem wystarczającym dla β lub, że β jest warunkiem koniecznym dla α. Stwierdzenie, że α jest warunkiem koniecznym i wystarczającym dla β, jest innym sposobem stwierdzenia, że α ⇔ β jest zdaniem prawdziwym.

KWANTYFIKATORY.

Symbol nazywamy kwantyfikatorem ogólnym i czytamy: dla każdego x ze zbioru X.

(Uwaga w zapisie międzynarodowym kwantyfikator ten ma postać: ).

Symbol nazywamy kwantyfikatorem szczegółowym (egzystencjalnym) i czytamy: istnieje element x w zbiorze X.

(Uwaga w zapisie międzynarodowym kwantyfikator ten ma postać: ).

Przykłady:

(dla każdej liczby naturalnej n, zachodzi nierówność: n+2>0)

(istnieje liczba rzeczywista x taka, że |x|<1).

TWIERDZENIE. Niech ϕ(x) będzie zmienną zdaniową (tzn. ϕ(x) staje się zdaniem logicznym, jeśli podstawimy za x pewien element zbioru X). Wówczas:

ĆWICZENIA

Przypiszmy wartość logiczną następującym zdaniom:

Każda liczba pierwsza jest nieparzysta.

Odpowiedzi:

0 - bo 2 jest liczbą pierwszą i parzystą. b) 0 - bo n=3. c) 1 - bo x=0.

Niech α, β, δ będą następującymi zdaniami:

α = „pada deszcz” β = „słońce świeci” δ = „na niebie są chmury”.

Zapisz następujące zdania za pomocą symboliki logicznej używając α, β, δ oraz funktorów logicznych.

• Pada deszcz i świeci słońce

• Jeśli pada deszcz to na niebie są chmury

• Jeśli nie pada deszcz to nie świeci słońce i na niebie są chmury.

• Słońce świeci wtedy i tylko wtedy, gdy nie pada deszcz.

• Jeśli nie ma chmur na niebie, to świeci słońce.

„Przetłumacz następujące zdania na język polski”.

• (α ∧ ~β) ⇒ δ

• ~α ⇔ (β ∨ δ)

• ~(α ∨ β) ∧ δ

Udowodnij prawdziwość zdań:

• (α ∧ α) ⇔ α

• (α ∨ β) ⇔ (~α ⇒ β)

• (α ⇒ β) ⇔ (~α ∨ β)

• α ⇒ (β ∨ ~β)

• (α ∧ ∼α) ⇒ β

ZBIORY

Zbiory oznaczać będziemy dużymi literami, a ich elementy literami małymi. Fakt, że element a należy do zbioru A zaznaczamy: a∈A; jeśli a nie należy do zbioru A, to piszemy a∉A.

Zbiór A zawiera się w zbiorze B, jeśli każdy element zbioru A należy do B, tzn.

A⊂B ⇔ (a∈A ⇒ a∈B)

Mówimy wówczas również, że A jest podzbiorem B (A⊂B) lub, że B jest nadzbiorem A (B⊃A).

Równość zbiorów definiujemy w następujący sposób:

A=B ⇔ (A⊂B ∧ B⊂A)

Zbiór pusty (tzn. zbiór, który nie zawiera żadnego elementu) oznaczamysymbolem ∅.

Dla zaznaczenia zbioru używamy niekiedy nawiasów { }. Na przykład, gdy wypisujemy wszystkie elementy danego zbioru: C={ 0,2,4,6,8} lub wskazujemy warunek który opisuje wszystkie elementy danego zbioru (zbiór elementów mających ustaloną własność): D={x∈R : |x|<1} - zbiór tych liczb rzeczywistych, których wartość bezwzględna jest mniejsza od 1 (jest to przedział (-1,1) ).

UWAGA. Zbiory rozważane w matematyce są z reguły podzbiorami pewnego ustalonego zbioru zwanego przestrzenią.

Niech będzie dana przestrzeń X i niech każdemu elementowi s∈S przyporządkowany będzie zbiór A_s⊂X. Rodzinę złożoną ze wszystkich zbiorów A_s, gdzie s∈S, oznaczać będziemy symbolem {A_s: s∈S}. Zbiór S nazywa się wtedy zbiorem wskaźników.

Ustalimy pewne stałe oznaczenia dla zbiorów:

R - zbiór liczb rzeczywistych; N - zbiór liczb naturalnych.

Działania na zbiorach.

Niech będzie dana rodzina {A_s:s∈S} zbiorów ustalonej przestrzeni.

Sumą zbiorów rodziny {A_s:s∈S} nazywamy zbiór .

Iloczynem (lub przekrojem) zbiorów rodziny {A_s:s∈S} nazywamy zbiór .

Jeśli S={1,2,...,k}, to stosujemy również oznaczenia:

A₁∪A₂∪ ... ∪A_k oraz i A₁∩A₂∩ ... ∩A_k oraz .

Jeśli S=N, to piszemy też:

A₁∪A₂∪ ... oraz i A₁∩A₂∩ ... oraz .

Różnicą zbiorów A i B nazywamy zbiór: A \ B = {x∈X: x∈A ∧ x∉B}.

Przykłady:

Niech dla i = 1,2,...

Wtedy: , , A₁\A₂= (-1, ].

TWIERDZENIE. Najważniejsze prawa rachunku zbiorów.

Prawa de Morgana

X \ (A ∪ B) = (X \ A) ∩ (X \ B)

X \ (A ∩ B) = (X \ A) ∪ (X \ B)

Prawo dopełnienia

A ⊂ B ⇔ (X \ A) ⊃ (X \ B)

Prawo podwójnego dopełnienia:

X \ (X \ A) = A

Prawa przemienności:

A ∪ B = B ∪ A

A ∩ B = B ∩ A

Prawa łączności:

A ∪ (B ∪ C) = (A ∪ B) ∪ C

A ∩ (B ∩ C) = (A ∩ B) ∩ C

Prawa rozdzielności

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

Prawo idempotentności

A ∪ A = A

A ∩ A = A

Prawa identyczności:

A ∪ ∅ = A

A ∪ X = X

A ∩ ∅ = ∅

A ∩ X = A.

Przykładowy dowód jednego z praw (przemienność sumy): A ∪ B = B ∪ A.

Aby udowodnić tę równość należy wykazać, że x∈ A ∪ B ⇔ x∈ B ∪ A.

x∈ A ∪ B ⇔ x∈A ∨ x∈B ⇔ x∈B ∨ x∈A ⇔ x∈ B ∪ A.

ILOCZYN KARTEZJAŃSKI.

Pojęcie pary uporządkowanej (a,b) można wprowadzić w ścisły sposób:

(a,b)= {{a}, {a,b}}

Mówiąc mniej precyzyjnie - para uporządkowana, to jest taka para elementów, która występuje w uporządkowanej kolejności.

Wynika stąd, że na ogół (a,b) ≠ (b,a) (np. (1,2) ≠ (2,1), ale równość zachodzi, gdy a=b).

Wykorzystując znajomość pojęcia pary uporządkowanej możemy zdefiniować trójkę uporządkowaną: (a,b,c)= ((a,b),c) itd.

Określimy obecnie równość uporządkowanych par, trójek itd.

(a,b)=(c,d) ⇔ a=c ∧ b=d

(m,n,s)=(t,r,q) ⇔ m=t ∧ n=r ∧ s=q itd.

Produktem kartezjańskim (iloczynem kartezjańskim) zbiorów A i B nazywamy zbiór

A×B = {(a,b): a∈A ∧ b∈B}.

Produktem kartezjańskim (iloczynem kartezjańskim) zbiorów A, B i C nazywamy zbiór

A×B×C = {(a,b,c): a∈A ∧ b∈B ∧ c∈C} itd.

Przykład.

Niech A={1,2}, B=R. Wtedy:

A×B={(x,y): (x=1 ∨ x=2) ∧ y∈R}

Niech będą dane zbiory A i B. Relacją ρ na zbiorze A×B nazywamy dowolny podzbiór zbioru A×B. Jeśli A=B, to mówimy, że ρ jest określona w zbiorze A. Jeśli (x,y)∈ρ, to piszemy xρy i mówimy, że x jest w relacji ρ z elementem y.

Przykład. Relacja < jest relacją w zbiorze liczb rzeczywistych i zapisujemy (zamiast ρ piszemy <) np. 1<2.

Relację ρ w zbiorze A nazywamy relacją równoważności jeśli jest ona

• zwrotna, tzn. .

• symetryczna, tzn. .

• przechodnia, tzn. .

Przykład. W zbiorze liczb rzeczywistych relacja < nie jest relacją równoważności (nie jest np. zwrotna), a relacja = jest relacją równoważności.

Niech ρ będzie relacją równoważności w zbiorze A. Wówczas dla każdego elementu a∈A możemy określić zbiór [a]_ρ={x∈A: xρa} (uwaga: jeśli wiadomo o jaką relację równoważności chodzi zamiast [a]_ρ, będziemy pisać krótko [a]), który nazywamy klasą abstrakcji, lub klasą równoważności relacji ρ w zbiorze A.

Przykład. Niech L będzie zbiorem wszystkich prostych na płaszczyźnie. Niech relacją w zbiorze L będzie relacja równoległości prostych. Wówczas dla dowolnej prostej l∈L, [l]_|| jest zbiorem wszystkich prostych równoległych do prostej l (w geometrii, tę klasę abstrakcji nazywa się niekiedy kierunkiem prostej l).

TWIERDZENIE. Niech ρ będzie relacją równoważności w zbiorze A. Dwa elementy x₁,x₂ należą do tej samej klasy abstrakcji wtedy i tylko wtedy, gdy x₁ ρ x₂.

Dowód. Niech x₁,x₂∈[z]. To ma miejsce wtedy i tylko wtedy, gdy x₁ρz i zρx₂. Ponieważ ρ jest przechodnia, więc powyższy fakt dowodzi, że x₁ ρ x₂.

Przypuśćmy teraz, że x₁ρx₂. Wtedy oczywiście x₁,x₂∈[x₁], co kończy dowód twierdzenia.

TWIERDZENIE (zasada abstrakcji). Każda relacja równoważności ρ w zbiorze A, rozbija ten zbiór na klasy abstrakcji w ten sposób, że każde dwie takie klasy są równe, lub rozłączne (tzn. nie mają wspólnych elementów) oraz każdy element zbioru A należy do co najmniej jednej klasy abstrakcji.

ĆWICZENIA

Wyznacz poniższe zbiory (tzn. wypisz ich elementy), jeśli zbiory te są niepuste i napisz ∅, jeśli zbiory te są puste.

{n∈N: n²=4}

{x∈R: x⁴=-2}

{x∈R: x²=9}∪{n∈N: |n|=2}

{x∈R: x⁴<16}∩{2,3,4,5,6,7,8}

{x∈N:}\{0}.

2. Udowodnij zależności

(A⊂C ∧ B⊂C) ⇒ A∪B⊂C

(A⊂B ∧ A⊂C) ⇒ A⊂B∩C

A∩B⊂A

A⊂A∪B

Jeśli A⊂B, to A∩B=A.

Niech A={0,1,2}, B=[0,1], C=[0,+). Znaleźć:

A×B b)B×A c)A×C d)C×B e)B×C

Które z poniższych relacji są relacjami równoważności w zbiorze liczb rzeczywistych?

relacja ρ określona wzorem: x ρ y ⇔ x+y=0.

relacja ρ określona wzorem: x ρ y ⇔ x-y =0.

relacja ρ określona wzorem: x ρ y ⇔ x-y jest liczbą wymierną.

Znajdź klasy abstrakcji tych relacji, które są relacjami równoważności.

GRAFY

Zacznijmy od przyjrzenia się przykładom grafów.

Rysunek ten przedstawia pewien schemat blokowy.

Ilustracja przemieszczania się zwierzęcia między klatkami.

Możliwe wyniki trzykrotnego rzutu monetą.

Graf skierowany G składa się z dwóch zbiorów, niepustego zbioru V(G) wierzchołków grafu G i zbioru E(G) krawędzi grafu G oraz funkcji γ:E(G)→V(G)×V(G). Jeśli e jest krawędzią grafu G i γ(e)= (p,q), to p nazywamy początkiem krawędzi e, a q końcem tej krawędzi.

Przedstawione wyżej rysunki możemy uznać za wykresy grafów skierowanych.

Jeżeli dla każdej krawędzi e, γ(e)= (p,q)=(q,p), to mówimy, że rozważamy graf (bez dodawania skierowany).

Np.

Drogą w grafie (skierowanym) nazywamy ciąg krawędzi, taki, że koniec jednej krawędzi jest początkiem następnej; dokładniej jeśli e₁,...,e_n należą do E(G), to e₁...e_n jest drogą o ile istnieją wierzchołki x₁,x₂,...,x_n,x_n+1 takie, że γ(e_i)=(x_i,x_i+1) dla i=1,2,...n. Wówczas n jest długością drogi. Droga jest zamknięta, jeśli x₁=x_n+1.

Przykłady:

Drogę zamkniętą długości co najmniej 1, z ciągiem wierzchołków x₁x₂...x_nx₁ nazywamy cyklem, jeśli wszystkie wierzchołki są różne, np.

Droga AE ED DB BA jest cyklem, a droga AE EB BC CD DB BA nie jest cyklem (bo B jest wierzchołkiem wielokrotnym.

Graf skierowany nie mający cykli nazywamy grafem acyklicznym.

Graf nazywamy spójnym, jeżeli każda para różnych wierzchołków jest połączona drogą w tym grafie.

Np.

nie jest grafem spójnym.

Drzewem nazywamy każdy acykliczny graf spójny.

Przykłady

Ćwiczenia

Narysuj dowolny graf, który nie posiada cykli.

Narysuj dowolny graf, który nie jest drzewem.

Który z poniższych grafów jest drzewem:

12

13

0

-1

1

A₁

-1/2

2

A₂

A×B

Start

s←0

t←2s

t>10

Koniec

s←s+1

A

B

C

D

O

R

OO

OR

RO

RR

OOO

OOR

ORO

ORR

ROO

ROR

RRO

RRR

A

B

C

D

O

R

OO

OR

RO

RR

OOO

OOR

ORO

ORR

ROO

ROR

RRO

RRR

A

B

C

D

E

---