Quinova metoda minimizacije

Boolova algebra

• Boolova algebra je dedukativna matematika, definirana z:
  • množico elementov
  • množico operatorjev
  • množico aksiomov ali postulatov

Osnovne definicije

• Če je S množica in sta x in y elementa, velja:
  • x ∈ S (element x pripada množici S)
  • y ∉ S (element y ne pripada množici S)
• Množico opišemo z naštevanjem elementov v oklepajih:
  • A = {1, 2, 3, 4}

Osnovne definicije (nad.)

• Binarni operator glede na množico S, je pravilo, ki vsakemu paru elementov iz S enolično priredi element iz S.

Postulati - splošno

• Postulati so osnovne predpostavke za matematične sisteme.
• Postulatov ni mogoče dokazati.

Postulati - splošno (nad.)

• Zaprtost
• Zakon asociativnosti
• Zakon komutativnosti
• Element enote
• Inverzni element
• Zakon distributivnosti

Zaprtost

• Množica S je zaprta glede na binarni operator, če velja za vsak par elementov iz S.

Zakon asociativnosti

• (x * y) * z = x * (y * z) za vse x, y, z ∈ S.

Zakon komutativnosti

• x * y = y * x za vse pare elementov x, y ∈ S.

Nevtralni element

• Množica S ima nevtralni element e ∈ S za binarno operacijo *, če za vsak x ∈ S velja e * x = x * e = x.

Inverzni element

• Element x ∈ S ima inverzni element y ∈ S glede na binarno operacijo *, če velja x * y = y * x = e, kjer je e nevtralni element v množici S.

Zakon distributivnosti

• Če sta * in · binarna operatorja nad množico S, potem velja zakon distributivnosti, če za vse x, y, z ∈ S velja x * (y · z) = (x * y) · z in x · (y * z) = (x · y) * z.

Aksiomi Boolove algebre

• Osnove Boolove algebre je postavil George Bool leta 1854.
• Leta 1938 je C. E. Shannon uvedel dvovrednostno algebro, imenovano preklopna algebra.
• Boolova algebra je algebraična struktura, definirana nad elementi množice X in s konjunkcijo in disjunkcijo.

Postulati

• Zaprtost.
• Nevtralni element.
• Komutativnost.
• Distributivnost.
• Število elementov.

Postulati (nad.)

• Distributivnost.
• Inverzni element.
• Število elementov.

Pravila

• Idempotenca
• Absorbcija
• Asociativnost

Pravila (nad.)

• De Morganov izrek

Primeri dokazov

• Primeri dokazov o aksiomih in pravilih Boolove algebre z uporabo aksiomov in pravil.

Dualnost

• Postulati so sestavljeni iz dveh delov (originalnega in dualnega).
• Dualnost dosežemo z zamenjavo logičnih vrednosti (0 z 1 in obratno) ter zamenjavo operatorjev konjunkcije in disjunkcije.
• Dualni operator je definiran glede na vseh vhodnih spremenljivk.

Dualnost (nad.)

• Postulati in pravila iz dualnosti.

Preklopne funkcije

• Preklopne spremenljivke – neodvisne spremenljivke kot elementi X₁ ,X₂,...,Xn∈{0,1}.
• Preklopna funkcija – odvisna spremenljivka v odvisnosti od vhodnih spremenljivk, f (x₁,x₂,...,xₙ). Enačba v obliki f (x₁, x₂,x₃) = x₁x₂ ∨ x₃.

Logični simboli

• Konjunkcija, disjunkcija, negacija.

Primer logične sheme

• Logične sheme za primer logičnih funkcij.

Pravilnostna tabela

• Leva stran predstavlja vse možne vhodne vektorje.
• Desna stran prikazuje vrednost funkcije pri vhodih.

Pravilnostna tabela (nad.)

• Leva stran predstavlja vse možne vhodne vektorje
• Desna stran predstavlja vrednost preklopne funkcije.

Mintermi in makstermi

• Pojave mintermov in makstermov.
• Vrste sprememb
• Število mintermov je 2^n.

Mintermi in maks. (nad.)

• Splošna enačba minterma m = x₁w₁₁ x₂w₂₁ ... x₂w₂₋₁
• Splošna enačba maksterma M = ẋ₁v₁₁ ẋ₂v₂₁ ... ẋ₂v₂₋₁

(Ostali podnaslovi in točke so enaki kot prej. Nadaljujemo z vsebino.)