Boole-függvények, Formulák

Legyen B logikai jelek egy halmaza, például B={¬, Λ, V}, B={¬, Λ, V, →, XOR} (ez utóbbia kizáró vagy-ot jelöli). A B-re épülõ Boole-formulák (vagy B-bázisú Boole-formulákat) kétféleképpen is leírjuk. V a változók halmaza, általában V={x₁, x₂, x₃, ...} vagy V={x,y,z}.

Definíció (I): Φ(B,V) a következõ jelsorozat-halmaz:

V elemei Φ(B,V) elemei,
Ha φ és ψ is Φ(B,V) elemei, akkor (¬φ), (φΛψ), (φVψ), (φ→ψ), (φXORψ) is Φ(B,V) elemei.
Φ(B,V) a fenti két tulajdonsággal rendelkezõ halmazok között a legszûkebb.

Definíció (II): Legyen T egy gyökeres sík fa, amely minden csúcsának egy vagy két gyereke van (két gyerek esetén az egyeik bal/elsõ a másik jobb/második). A csúcsok címkézve vannak a következõ módon: A levelek címkéi V-beli elemek, a nem levelek (belsõ csúcsok címkéi) logikai jelek úgy, hogy a ¬ címkét pontosan az egy gyerekû csúcsok kapják.

Definíció: Egy Boole-függvény egy f: {0,1}ⁿ → {0,1} függvény.

Definíció: Minden φ formula meghatároz egy Boole-függvényt.

Feladat: Írjunk fel egy formulát, ami a következõ Boole-függvényeket írják le. Törekedjünk arra, hogy formulánk mérete ne legyen túl nagy.

Többség(x,y,z)
Többség(x,y,z,t,s)

Feladat: Analízáljuk a kapott formula méretét ha n-változós esetre alkalmazzuk a fenti feladat megoldásainak ötleteit.

Feladat: Írjunk fel egy formulát, ami a következõ Boole-függvényeket írják le. Törekedjünk arra, hogy formulánk mérete ne legyen túl nagy.

Bit-rendezés(x,y)
Bit-rendezés(x,y,z,t)
Bit-rendezés(x₁,x₂,x₃,x₄, x₅,x₆,x₇,x₈)

Feladat: Analízáljuk a kapott formula méretét ha n-változós esetre alkalmazzuk a fenti feladat megoldásainak ötleteit.

Feladat: Legyen V egy egyszerû gráf csúcshalmaza. Minden pontpárhoz (lehetséges élhez) tartozzon egy változó. Egy változó értéke azt kódolja, hogy a csúcspár összekötött-e. A változók értékadása egy gráfot kódol. Egy gráftulajdonság egy Boole-függvénnyel írható le. Az alábbi Boole-függvényeket írjuk le minél kisebb formulával:

Összefüggõség, |V|=4.
Párosság, |V|=4.

Feladat: Írjunk fel egy formulát, ami a következõ Boole-függvényeket írják le. Törekedjünk arra, hogy formulánk mérete ne legyen túl nagy. a) B tartalmazza XOR-t, b) B={¬, Λ, V}.

Paritás(x,y)
Paritás(x,y,z,t)

Feladat: Analízáljuk a kapott formula méretét ha n-változós esetre alkalmazzuk a fenti feladat megoldásainak ötleteit.