Wykład 1

1.Elementy teorii zbiorów

• rachunek zdań,

• reguły wnioskowani, prawa (równoważności) tautologie (reguła modus ponens),

• rachunek predykatów (zasada rezolucji),

• zastosowania w strukturach systemów ekspertowych,

• zbiory i działania na zbiorach, alfabet, (zastosowania - maszyna Turinga), problemy łatwe i trudne,

• asymptotyka funkcji liczbowych - zastosowania w złożoność obliczeniowej algorytmów, zasada dziel i zwyciężaj

Rachunek zdań

ZDANIA, SPÓJNIKI, FORMUŁY

Poniższe napisy nie są formułami

• p ⇒ ⇒ q

• ¬¬¬

• ten napis na pewno nie jest formułą,

• (p ⇒ ¬q))

Poniższe napisy są formułami

• (p ⇒ (r ⇒ q))

• ¬¬¬q

• (p ⇒ ¬q)

p ⇒ p ⇒ p

(p ⇒ p) ⇒ p ⇔ p ⇒ (p ⇒ p)

p	¬p
0	1
1	0

∨	0	1
0	0	1
1	1	1
∧	0	1
0	0	1
1	1	1

a ⇒ b ≡ ¬a ∨ b

⇒	0	1
0	1	1
1	0	1

1. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były wartościowane na 0

• p ⇒ (q ⇒ r)

• (p ⇒ q) ⇒ r

• (¬p ⇒ q)

2. Podaj przykład wartościowania zmiennych tak aby poniższe formuły były wartościowane na 1

• ¬(p ⇒ q)

• ¬(¬p ⇒ ¬q)

• (¬q ⇒ q) ⇒ (p ⇒ ¬q)

3. Udowodnij następujące równoważności

• 
  ,

• 
  

• 
  

• 
  

• 
  

• 
  

• 
  

• 
  

4. Sprawdź które z następujących formuł są tautologiami

• 
  

• 
  

• 
  

• 
  

5. Sprawdź:

(¬a ∨ b) ∧ (¬b ∨ c) ⇒ (¬c ∧ a) ≡ b , ((p ∨ q) ∧ ¬p) ≡ (¬p ∨ q)

(p ∨ q) ∧ ¬p) ≡ (¬p ∨ q)

Prawa

Przemienności

p ∧ q ≡ q ∧ p , p ∨ q ≡ q∨ p

Łączności

p ∧ (q ∧ r) ≡ (p ∧ q) ∧ r , p ∨ (q ∨ r) ≡ (p∨ q) ∨ r

Rozdzielności mnożenia względem dodawania

(p ∨ q) ∧ r ≡ p ∧ r ∨ q∧ r

Rozdzielności dodawania względem mnożenia

(p ∧ q) ∨ r ≡ (p ∨ r) ∧ (q∨ r)

De Morgana

¬ (p ∧ q) ≡ ¬p ∨ ¬r , ¬(p ∨ r) ≡ ¬p ∧ ¬q

Powtórzeń

p ∨p ∨p ∨…∨p ≡ p , p ∧p ∧p ∧…∧p ≡ p

((¬a ∨ b) ∨ (¬a ∨ d)) ⇒ b ∨ d ≡ a ∨ b ∨ d

((¬a ∨ (b ∨ d)) ⇒ b ∨ d ¬p ∨ ¬p ∨¬p ∨…∨ ¬p ≡ ¬p

¬(¬a ∨ (b ∨ d)) ∨ (b ∨ d) , a ⇒ b ≡ ¬b ∨ d

a ∧ ¬(b ∨ d)) ∨ (b ∨ d) , ¬(p ∨ r) ≡ ¬p ∧ ¬q

(a ∨ b ∨ d) ∧ (¬ (b ∨ d) ∨ (b ∨ d))

a ∨ b ∨ d ¬x ∨ x ≡

Wnioskowanie

Modus ponens a ⇒ b a, a ⇒ b

b

Zasada rezolucji (a ⇒ b ∧ b ⇒ b) ⇒ (b ⇒ c) ¬a ∨ b, ¬b ∨ c

¬a ∨ c

Fakty: a, b

Baza wiedzy:

R1. a ∧ c ⇒ d a

R2. a ∧ b ⇒ c R1 d g

R3. b ∧ d ⇒ g R2 c

R4. c ∧ g ⇒ h b h

h?

ZBIORY

Zbiór liczb naturalnych:1, 2, 3 , 4 , 5 , ... N = {1, 2, 3 , 4 , 5 , ...}

Zbiór liczb wmiernych:1/2, 2/3 , 4/4 , 5/6 , ... W = {1/2, 2/3 , 4/4, 5/6 , ...}

Zbiór liczb niewmiernych:√2, π, e ,... ¬ W

Zbiór liczb rzeczywistych - R

Zbiór liczb całkowitych - C

N ⊂ C ⊂ W ⊂ R ; ¬ W ⊄ C ; ¬ W ⊂ R

Suma A ∪ B = C ; C = {c ∈ A ∨ c ∈ B}

Iloczyn A ∩ B = C ; C = {c ∈ A ∧ c ∈ B}

Różnica A \ B = C ; C = {c ∈ A ∧ c ∉ B}

Różnica symetryczna

A ⊗ B = C ; C = { c ∈ A ∪ B ∧ c ∉ A ∩ B } = { c ∈ A \ B ∨ c ∈ B \ A }

Zbiór pusty A = ∅ ⇔ ¬∃ a [a ∈ A ]

Inkluzja dwóch zbiorów ( A ⊂ B ) ⇔ ∀a [ a ∈ A ⇒ b ∈ B ]

Przestrzeń ( zbiór pełny) - 1

Dopełnienie A' zbioru A przestrzeni 1

a ∈ A ⇔ a∈ 1 ∧ a ∉ A

A' = 1 \ A

N ⊂ W ; ¬(W ⊂ N ) ; W ∩¬W = ∅ ; N \ W = ∅

• {n ∈ N: 5/n} = {5, 10, 15,…}

• {4n + 3: n ∈N} = { }

Zbiór potęgowy P(S) zbioru S - zbiór wszystkich podzbiorów zbioru S.

S={a,b} ; P(S) = {∅ , {a}, {b} , {a,b}}

|S| = 2 , |P(S)| = 2ⁿ

|P(∅)| = ??? , |P({1})| = ???

• 
  ,
  

• 
  ,
  

A \ B ⊂ A ∩ B

A \ B ⊂ A ∩ B

1. 
   
   A ∩ B = ∅

A \ B = A , A ∩ B = ∅ , A ⊂ ∅

2. 
   
   A ⊆ B

A \ B = ∅ , A ∩ B = A , ∅ ⊂ A

3. A ∩ B ≠ ∅

A \ B = , ⊂ , A ∩ B =

1. Sprawdź:

A ∩ B ⊂ A ⊗ B

A ∩ B ⊂ A ∪ B

2. Niech A = {1,2,3,4,8,16}, B = {2,4,6,8,10} ` C = {1,3,7,15}. Wyznacz:

A \ C B ∪ (C ∩ B)

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

A ⊕ B ` C \ (B\A)

B ∪ C A ⊕ (B ⊕ C)

Predykaty

P(x) P(x) = [ x = 3] , P(x) = [Q(x) ∧U(x)] , [pije mleko] , [jest zielone],

P(x₁,x₂,...,x_n) P(x,y,z) = [x + y = z] , P(x,y) = [x > y] , [jest dzieckiem],

Przykłady

P(Janek,Zosia) = [Janek jest bratem Zosi] ,P(V,x,y,z) = [V = x*y*z]

∀x∈R [x + 0 = x] , ∃x∈N [x = x*x] , ¬∃x∈N [x < 0] , ∃x∈R [x < 0] ,

∀x∈zbiór kotów [x pije mleko] , ∀x∈zbiór szpaków [x jest ptakiem]

∀x∈zbiór dzieci ∃y ∈zbiór rodziców [x jest dzieckiem y]

Rachunek predykatów

∃jeden talerz ∀ student , ∀ student ∃ jeden talerz

Niech P(x) = [x = x*x] która z tez jest prawdziwa:

∃ x∈R P(x) , ∀ x∈R P(x)

∀x ∈{0,1} [x ∧ ¬x ≡ 0] , ∀x ∈{0,1} [x ∨ ¬x ≡ 0]

Sprawdzanie prawdziwości

∀x P(x) - „jeden zaprzecza wszystkiemu“

∃x P(x) - „jeden wystarcza“

¬(∀x P(x)) ⇔ ∃x [¬P(x)]

przykład ¬(∀x∈R [x < x + 1] ⇔ ∃ x∈R [x ≥ x + 1]

¬(∃y Q(y)) ⇔ ∀y [¬Q(y)]

¬(∃x ∀y [y > x]) ⇔ ∀x[¬∀y [y > x]) ⇔ ∀x∃y [¬ [y > x]] ⇔ ∀x∃y [y ≤ x]]

Niech U' = {1,2,3} , U” = {4,5,6,7}sprawdź prawdziwość:

∃x∈U' ∃y∈U” [y > x]

∀x∈U' ∀y∈U” [y > x]

∀x∈U' ∃y∈U” [y > x]

∃x∈U' ∀y∈U” [y > x]

∃!x∈R [x*6 = 0]

∀x∈R ∀y∈R ∃!z∈R [x + y = z]

∀x∈{1,2,3} P(x) ⇔ P(1) ∧ P(2) ∧ P(3) ,

(∀x P(x) ⇒ ∀x P(x)) ⇔ (∃x P(x) ⇒ ∃x Q(x))

∀x P(x) ∃x P(x) ∃x Q(x) ∀x P(x) ⇒ ∀x P(x) ∃x P(x) ⇒ ∃x Q(x)

0 0 0 1 1

0 0 1 1 1

0 1 0 1 0

0 1 1 1 1

1 0 0 1 1

1 0 1 1 1

1 1 0 1 0

1 1 1 1 1

(∀x P(x) ⇒ ∀x P(x)) ⇔ (∃x P(x) ⇒ ∃x Q(x))

( A ⇒ A ) ⇔ ( B ⇒ C )

( ¬A ∨ A ) ⇔ (¬B ∨ C )

1 ⇔ .....?????....

(∃x P(x) ⇒ ∃x P(x)) ⇒ (∀x P(x) ⇒ ∃x Q(x))

∃x P(x) ∀x P(x) ∃x Q(x) ∃x P(x) ⇒ ∃x P(x) ∀x P(x) ⇒ ∃x Q(x)

0 0 0 1 1

0 0 1 1 1

0 1 0 1 0

0 1 1 1 1

1 0 0

1 0 1

1 1 0

1 1 1

Każdy człowiek jest śmiertelny. ∀x : Cz(x) ⇒ Śm(x)

Marek jest człowiekiem. Cz(M)

Czy Marek jest śmiertelny? Śm(M)?

∀x : Cz(x) ⇒ Śm(x) ¬Cz(x) ∨ Śm(x)

Cz(M) Cz(M)

Śm(M)? ¬Śm(M)

¬Cz(x) ∨ Śm(x) , Cz(M)
¬Cz(x) ∨ Śm(x) Cz(M)

Śm(x)

Śm(x) , ¬Śm(M) Śm(x) ¬Śm(M)

€

€

Każdy człowiek jest śmiertelny. ∀x : Cz(x) ⇒ Śm(x)

Marek nie jest człowiekiem. ¬Cz(M)

Czy Marek jest śmiertelny? Śm(M)?

∀x : Cz(x) ⇒ Śm(x) ¬Cz(x) ∨ Śm(x)

¬Cz(M) ¬Cz(M)

Śm(M)? ¬Śm(M)

¬Cz(x) ∨ Śm(x) , ¬Cz(M)
¬Cz(x) ∨ Śm(x) Cz(M)

¬Cz(x) ∨Śm(x)

¬Cz(x) ∨ Śm(x) , ¬Śm(M) ¬Cz(x) ∨ Śm(x) ¬Śm(M)

€

¬Cz(x)

PROBLEM ≡ DANE + OGRANICZENIA + PYTANIE

PROBLEMY

DECYZYJNE OPTYMALIZACYJNE

PROBLEMY

TRUDNE ŁATWE

PRZYKŁADY

PROBLEM SORTOWANIA

{2, 6, 1, 7, 3, 5, 4} {1, 2, 3, 4, 5, 6 , 7}

PROBLEM PLECAKOWY

• {D} , wd ,cd ; {R} , wr ,cr ; {P} , wp , cp ; x₁, x₂ , x ₃ ∈ N_o

• x₁wd +x₂wr + x₃wp < W;

• 
  x₁cd +x₂cr + x₃cp max

PROBLEM KOMIWOJAŻERA

• N - miast, d_i,j - odległości pomiędzy miastami

• Startując z wybranego miasta, należy powrócić do niego przejeżdżając przez każde z pozostałych miast tylko jeden raz.

• Która z tras jest najkrótsza?

Problem decyzyjny: pytania są formułowane w taki sposób aby udzielana na nie odpowiedź była postaci TAK lub NIE.

Problem optymalizacyjny: pytania są formułowane w taki sposób aby udzielana na nie odpowiedź dotyczyła ekstremum pewnej funkcji celu.

Przykład

Problem sortowania

Dany jest zbiór: {7, 5, 6, 1, 3, 4 , 2, 9, 8, 10}. Zbiór ten należy uporządkować (posortować) od najmniejszego do największego elementu, tzn. {1, 2, 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10}.

Przyjmując zasadę porządkowania wg. algorytmu „bąbelkowego” złożoność obliczeniowa dana jest funkcją n²/2 - n/2,

czyli: 100/2 -10/2 = 45 porównań.

W przypadku gdy zbiór ten wstępnie podzielimy na dwa, tzn. {7, 5, 6, 1, 3} , {4 , 2, 9, 8, 10} to na wynikową złożoność obliczeniową składają się trzy składniki:

(n/2)²/2 - (n/2)/2 + (n/2)²/2 - (n/2)/2 + n

a zatem 5²/2 - 5/2 + 5²/2 - 5/2 + 10

5² - 5 + 10 = 25 - 5 + 10 = 30 porównań.

Czy dalszy podział zbioru wyjściowego na 4 lub 6 podzbiorów zmniejszyłby złożoność obliczeniową?

Jaka jest złożoność obliczeniowa algorytmu realizowanego na komputerze dwuprocesorowym?

METODY

PRZYBLIŻONE DOKŁADNE

HEURYSTYCZNE

„0” DODATKOWEJ INFOMACJI DANA DODATKOWA INFORMACJA

przeszukiwanie wszerz górska wspinaczka

przeszukiwanie w głąb algorytm gradientowy

generuj i testuj najpierw najlepszy

A*

11

1

A'

A

B

A

B

A

B

A

---