Boolova formula

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Boolova ali logična formula je izraz, ki ga dobimo z naslednjimi pravili:

  1. Logični konstanti T in F sta logični formuli.
  2. Vsaka logična spremenljivka p je logična formula.
  3. Če je p logična formula, je tudi negacija(\lnot p) logična formula.
  4. Če sta p in q logični formuli, je tudi konjunkcija (p \land q) logična formula.
  5. Če sta p in q logični formuli, je tudi disjunkcija (p \lor q) logična formula.
  6. Če sta p in q logični formuli, je tudi implikacija (p \Rightarrow q) logična formula.
  7. Če sta p in q logični formuli, je tudi ekvivalenca (p \Leftrightarrow q) logična formula.
  8. le izrazi, oblikovani s pravili 1 - 7 so logične formule.


Vsebina

Sintaktična ekvivalenca

Logične formule lahko transformiramo v (sintaktično) ekvivalentne formule, tako da uporabljamo pravila. Npr. namesto (p \land q) lahko pišemo (q \land p), namesto ((p \land q) \land r) pa (p \land (q \land r)). Z uporabo pravil, lahko izrazimo vsako logično formulo le z operacijami negacija, konjunkcija in disjunkcija.

Vsako logično formulo lahko zapišemo v konjunktivni normalni obliki.

Valuacija

Vsaki logični formuli priredimo vrednost, tako da jo valuiramo. V splošnem je njena vrednost odvisna od vredsnoti logičnih spremenljivk.

  1. v(T) = 1 in v(F) = 0.
  2. v(\lnot p) = 1 - v(p)
  3. v(p \land q) = v(p) v(q)
  4. v(p \lor q) = v(p) + v(q) - v(p)v(q).
  5. v(p \Rightarrow q) = max{(1- v(p)),v(q)}
  1. v(p \Leftrightarrow q) = 1 - v(p) - v(q) + 2 v(p)v(q)


Dualna formula

Vsaki logični formuli F lahko priredimo njeno dualno formulo D(F), tako da v njej zamenjamo logični konstanti, konjunkcijo z disjunkcijo, ...

Glej tudi

Osebna orodja