9cm Algebra Boola Jest to struktura algebraiczna \definition

spełniająca następujące aksjomaty

- Przemienność:

a+b=b+a⁢ oraz   a⋅b=b⋅a

- Rozdzielność:

a⋅b+c=a⋅b+a⋅c, oraz  a+b⋅c=a+b⋅a+c

- Elementy neutralne:

a+0=a⁢ oraz ⁢a⋅1=a

- Istnienie elementu komplementarnego:

a+a¯=1⁢ and ⁢a⋅a¯=0

*) Czasem negacja jest dodana do sygnatury algebry Boola.

1. <+-> Algebra zbiorów: P(X)=(2X,∪,∩,-,∅,X);

2. <+-> Rachunek zdań

   ({zdanialogiczne},∨,∧,¬,⊥,⊤)

3. <+-> Binarna algebra Boola B2=({0,1},+,⋅,0,1) to jest najmniejsza, ale najważniejsza algebra Boola w zastosowaniu.

   xyx+yx⋅y0000011010101111⁢⁢x¬⁢x0110

   Przykłady zastosowań:

   • projektowanie układów scalonych;

   • rachunek zdań.

Łączność (ang. Associative law):

⁢x+y+z=x+y+z⁢ oraz ⁢x⋅y⋅z=x⋅y⋅z

Idempotence:

⁢⁢x+x=x⁢⁢o⁢r⁢a⁢z⁢⁢x⋅x=x⁢d⁢u⁢a⁢l

Działania z 0 i 1:

⁢x+1=1⁢⁢o⁢r⁢a⁢z⁢⁢x⋅0=0⁢d⁢u⁢a⁢l

Pochłanienie (ang. Absorption laws):

⁢y⋅x+x=x⁢⁢o⁢r⁢a⁢z⁢⁢y+x⋅x=x⁢d⁢u⁢a⁢l

Inwolocja (ang. Involution laws):

⁢x¯¯=x

Prawa DeMorgana (ang. DeMorgan's laws):

¬⁡x+y

=¬x⋅¬yoraz¬(x⋅y)=¬x+¬y(dual)

Prawa konsensusu (ang. Consensus laws):

	x+y⋅x¯+z⋅y+z	=x+y⋅x¯+z⁢ oraz
	x⋅y+x¯⋅z+y⋅z	=x⋅b+x¯⋅z

Zasada dualności:

Każda algebraiczna równość pozostaje prawdziwa jeśli zamieniamy operatory + na ⋅, ⋅ na +, 0 na 1 oraz 1 na 0.

• <+-> usuwanie alternatyw regułą pochłaniania (t.j. p∧p∨q≡p):

  f

  =

  α1⁢α4⁢α2∨α3

• <+-> sprowadzanie funkcji f z postaci CNF (koniunkcja alternatyw) do postaci DNF (alternatywa koniunkcji)

  f

  =

  α1⁢α4⁢α2∨α1⁢α4⁢α3

• <+-> Każdy składnik jest reduktem! Zatem mamy 2 redukty: R1=A1,A2,A4 i R2=A1,A3,A4

• <+-> Atrybut jest ważniejszy jeśli częściej występuje w klauzulach;

• <+-> Selekcja: W każdym kroku wybierzmy atrybut, który najczęściej występuje w funkcji rozróżnialności;

• <+-> Usuwanie: Usuwamy z tej funkcji te klauzule, które zawierają wybrany atrybut;

• <+-> Powtarzamy Selekcja i Usuwanie dopóty, póki funkcja rozróżnialności zawiera jeszcze jakąś klazulę.

Heurystyka Johnsona

1. Znaleźć atrybut, który występuje najczęściej w macierzy rozróżnialności;

2. Usuwnąć wszystkie pola zawierające wybrany atrybut;

3. Powtarzamy kroki 1 i 2 dopóki wszystkie pola macierzy są puste.

• W macierzy nierozróznialności z poprzedniego przykładu

  a1 - występuje 23 razy a2 - występuje 23 razy

  a3 - występuje 18 razy a4 - występuje 16 razy

• Jeśli wybieramy a1, to po usunięciu pól zawierających a1 zostało 9 niepustych pól macierzy nierozróżnialności. Wśród nich:

  a2 - występuje 7 razy a3 - występuje 7 razy a4 - występuje 6 razy

• Jeśli wybieramy tym razem a2 to zostały 2 niepuste pola i wśród nich a4 jest zdecydowanym faworytem.

• Możemy dostać w ten sposób redukt: R1=a1,a2,a4.

• Niech X=u,v∈U2:d⁢e⁢c⁢u≠d⁢e⁢c⁢v;

• Niech Sai=u,v∈X:ai⁢u≠ai⁢v;

• Niech C*⊂A będzie minimalnym reduktem, lecz C=a1,…,ak będzie reduktem znalezionym przez heurystykę Johnsona;

• Załóżmy, że heurystyka Johnsona musi płacić 1zł za każdym razem, gdy dodała ai do C.

• Rozłóżmy ten koszt tym elementom, które zostały po raz pierwszy pokryte przez zbiór Sai

• Niech cx = koszt ponoszony przez x. Jeśli x jest pokryty po raz pierwszy przez ai, to

  cx=1Sai-Sa1∪…∪Sai-1

• Heurystyka Johnsona ponosi łączny koszt =C. Mamy

  C=∑x∈Xcx≤∑a∈C*∑x∈Sacx

• Gdybyśmy pokazali, że dla dowolnego altrybutu a∈A

  ∑x∈Sacx≤H⁢Sa

  gdzie H⁢n=∑i=1n1i, wówczas możemy oszacować dalej:

  	C	≤∑a∈CA*∑x∈Sacx≤|C*|⋅H(max{|Sa:a∈A|})
  		≤|C*|⋅H(|X|)≤|C*|⋅ln(|X|+1)

 Lemat:

Dla dowolnego altrybutu a∈A

Dowód:

• Niech ui=Sa-Sa1∪…∪Sai-1, mamy:

  u0=Sa≥…≥ui-1≥ui≥…≥uk=0;

  gdzie k jest najmniejszym indeksem t., że Sa=Sa1∪…∪Sak

• Zatem

  	∑x∈Sacx	=∑i=0kui-1-ui⋅1Sai-Sa1∪…∪Sai-1
  		≤∑i=0k(ui-1-ui)⋅1ui-1≤∑i=0k(H(ui-1)-H(ui))=H(|Sa|)

• ILP (Integer Linear Program)

• Symulowane wyżarzanie (simulated annealing)

• Algorytmy genetyczne

• SAT solver

• ???

Dana jest funkcja f:0,1n→0,1 zapisana w postaci CNF za pomocą zmiennych x1,…,xn

1. Utwórz nowe zmienne y1,…,y2⁢n odpowiadające literałom x1,x1¯,…,xn,xn¯;

2. Dla każdej zmiennej xi, utwórzmy nierówność y2⁢i-1+y2⁢i≤1

3. Zamień każdą klausulę ωi=li1∨…∨lini na nierówność yi1+…+yini≥1;

4. Utwórzmy układ nierówności z poprzednich punktów:

   Ay≥b

5. Zagadnienie programowania liniowego liczb całkowitych (ILP) jest definiowane jako problem szukania

   min⁡∑i=1nyi⁢⁢ przy ograniczeniu:  ⁢Ay≥b.

Dla danego zbioru atrybutów A definiujemy język deskryptorów jako trójkę

gdzie

• D jest zbiorem deskryptorów

  D={(a=v):a∈A and v∈Vala};

• {∨,∧,¬} jest zbiorem standardowych operatorów logicznych;

• F jest zbiorem formuł logicznych zbudowanych na deskryptorach z D.

• Dla każdego zbioru atrybutów B⊆A oznaczamy:

  D|B={(a=v):a∈B and v∈Vala}, czyli zbiór deskryptorów obciętych do B.

  FB zbiór formuł zbudowanych na DB.

Semantyka:

Niech S=U,A będzie tablicą informacyjną. Każda formuła ϕ∈F, jest (semantycznie) skojarzona ze zbiorem ϕS zawierającym obiekty spełniające ϕ.

Formalnie możemy indukcyjnie definiować semantykę jak następująco:

Każda formuła ϕ może być charakteryzowana przez:

• l⁢e⁢n⁢g⁢t⁢h⁢ϕ= liczba deskryptorów w ϕ;

• s⁢u⁢p⁢p⁢o⁢r⁢t⁢ϕ=ϕS= liczba obiektów spełniających formułę

Definicja reguł decyzyjnych Niech S=U,A∪d⁢e⁢c będzie tablicą decyzyjną. Regułą decyzyjną dla S nazywamy formuły postaci:

gdzie ϕ∈FA i δ∈Fd⁢e⁢c.

Formułę ϕ nazywamy poprzednikiem (lub założeniem) reguły r, a δ nazywamy następnikiem (lub tezą) reguły r.

Oznaczamy poprzednik i następnik reguły r przez p⁢r⁢e⁢v⁢r oraz c⁢o⁢n⁢s⁢r.

Reguły atomowa: Są to reguły postaci:

Każda reguła decyzyjna r postaci (5.5) może być charakteryzowana następującymi cechami:

Mówimy, że reguła r jest niesprzeczna z A jeśli

Minimalne niesprzeczne reguły: Niech S=U,A∪d⁢e⁢c będzie daną tablicą decyzyjną. Niesprzeczną regułę

nazywamy minimalną niesprzeczną regułą decyzyjną jeśli usunięcie któregokolwiek z deskryptorów spowoduje, że reguła przestaje być niesprzezcna z S.

Klasyfikatory regułowe dzialają w trzech fazach:

1. Faza treningu: Generuje pewien zbiór reguł R⁢U⁢L⁢E⁢S⁢A z danej tablicy decyzyjnej A.

2. Faza selekcji reguł: Szuka w R⁢U⁢L⁢E⁢S⁢A tych reguł, które są wspierane przez obiekt x. Oznaczamy zbiór tych reguł przez M⁢a⁢t⁢c⁢h⁢R⁢u⁢l⁢e⁢s⁢A,x.

3. Faza klasyfikacji: wyznacza klasędecyzyjną dla x za pomocą reguł z M⁢a⁢t⁢c⁢h⁢R⁢u⁢l⁢e⁢s⁢A,x według następującego schematu:

   1. Jeśli M⁢a⁢t⁢c⁢h⁢R⁢u⁢l⁢e⁢s⁢A,x jest pusty: odpowiedź dla x jest `⁢`⁢N⁢I⁢E⁢W⁢I⁢E⁢M′′, tzn. nie mamy podstaw, aby klasyfikować obiekt x do którejkolwiek z klas;

   2. Jeśli M⁢a⁢t⁢c⁢h⁢R⁢u⁢l⁢e⁢s⁢A,x zawiera tylko obiekty z k-tej klasy: wówczas d⁢e⁢c⁢x=k;

   3. Jeśli M⁢a⁢t⁢c⁢h⁢R⁢u⁢l⁢e⁢s⁢A,x zawiera reguły dla różnych klas decyzyjnych: wówczas decyzja dla x określimy za pomocą pewnego, ustalonego schematu głosowania między regułami z M⁢a⁢t⁢c⁢h⁢R⁢u⁢l⁢e⁢s⁢A,x.

Reguły:

Reguły:

• (a1=dobra)∧(a3=nie)⟹dec=strata

• (a1=dobra)∧(a2=super)∧(a4=nie)⟹dec=strata