Boolean satisfiability problem

Üdvözlöm, Ön a Boolean satisfiability problem szó jelentését keresi. A DICTIOUS-ban nem csak a Boolean satisfiability problem szó összes szótári jelentését megtalálod, hanem megismerheted az etimológiáját, a jellemzőit és azt is, hogyan kell a Boolean satisfiability problem szót egyes és többes számban mondani. Minden, amit a Boolean satisfiability problem szóról tudni kell, itt található. A Boolean satisfiability problem szó meghatározása segít abban, hogy pontosabban és helyesebben fogalmazz, amikor beszélsz vagy írsz. ABoolean satisfiability problem és más szavak definíciójának ismerete gazdagítja a szókincsedet, és több és jobb nyelvi forráshoz juttat.

Angol

Főnév

Boolean satisfiability problem (tsz. Boolean satisfiability problems)

  1. (informatika) logikai kielégíthetőségi probléma vagy Boole-függvények kielégíthetőségének problémája

A Boolean satisfiability problem (röviden: SAT probléma) a logika és a számítástudomány egyik legfontosabb alapvető problémája. Ez volt az első ismert NP-teljes probléma, amit Stephen Cook bizonyított 1971-ben (Cook-tétel).


🧠 Alapfogalom – Mi az a SAT?

A SAT probléma azt kérdezi:

Van-e logikai változók egy olyan igaz/hamis (true/false) értékadása, amely igazságra kiértékeli a megadott logikai képletet?

📘 Formális definíció

  • Bemenet: egy logikai kifejezés, például logikai ÉS (∧), VAGY (∨), tagadás (¬) operátorokkal.
  • Kérdés: Létezik-e olyan változóbeállítás, amely igazzá teszi a képletet?


🧩 Példa

Legyen a képlet: 

(A ∨ B) ∧ (¬A ∨ C) ∧ (¬B ∨ ¬C)

Ez a képlet kielégíthető, például:

  • A = hamis
  • B = igaz
  • C = hamis


📜 Fogalmak

  • Literal: egy változó vagy annak negáltja (pl. A, ¬A)
  • Klauszula: literálok VAGY kapcsolata (pl. A ∨ ¬B ∨ C)
  • CNF (konjunktív normálforma): több klauszula ÉS kapcsolattal (pl. (A ∨ B) ∧ (¬A ∨ C))


🧮 SAT probléma típusa

  • Döntési probléma: Igaz-e, hogy létezik kielégítő értékadás?
  • NP-teljes: Ha gyors algoritmus létezne SAT megoldására, akkor minden NP-problémára is.


🔁 Variánsok

Probléma Leírás
2-SAT Minden klauszulában legfeljebb 2 literál – polinomiálisan megoldható
3-SAT Minden klauszulában 3 literál – már NP-teljes
MAX-SAT Hány klauszulát lehet maximum kielégíteni?
UNSAT A képlet nem kielégíthető (nincs igaz értékelés)


📊 Miért fontos a SAT?

A SAT egy alapprobléma, amely rengeteg más probléma formálható SAT-problémává.

SAT-ra vezethető problémák:

  • Ütemezés (pl. órarend)
  • Hardvertervezés, verifikáció
  • AI – keresési problémák
  • Játékállások elemzése (pl. Sudoku SAT-tal modellezhető)


🧠 Megoldási módszerek

🔍 1. Brute Force:

Próbálj ki minden lehetséges változóértéket.

  • Lassú:
  • Csak kis képletekhez

🧠 2. DPLL algoritmus (Davis–Putnam–Logemann–Loveland)

  • Backtracking + heurisztikák
  • Egységlevezetés (unit propagation)
  • Literál-eltávolítás (pure literal rule)

🌲 3. CDCL (Conflict-Driven Clause Learning)

  • Modern SAT solverek alapja
  • Visszaugrás (backjumping)
  • Konfliktusklauszulák tanulása


⚙️ SAT Solver példák

  • MiniSAT – kicsi és gyors
  • Z3 – Microsoft által fejlesztett SMT-solver
  • Glucose, Cadical, SAT4J


🧠 Példa SAT solver bemenet (DIMACS formátumban)

p cnf 3 3
1 -2 0
-1 3 0
-2 -3 0

Jelentése:

  • 3 változó, 3 klauszula
  • (x1 ∨ ¬x2) ∧ (¬x1 ∨ x3) ∧ (¬x2 ∨ ¬x3)


📈 Alkalmazások

  • Kriptográfia (támadási modellek)
  • Problémaellenőrzés (formal verification)
  • Logikai puzzle-k megoldása
  • Szoftverhibák automatikus keresése


🔄 Összefoglalás

Fogalom Leírás
SAT Van-e igaz értékelés egy logikai képlethez?
NP-teljes Nincs ismert hatékony algoritmus
CNF Klauszulák ÉS-ei literálok VAGY-ával
3-SAT Alap NP-teljes probléma
SAT solver Speciális program, ami megoldja a SAT-ot
Alkalmazások AI, verifikáció, kriptográfia, keresés

További információk

Enciclo
Wikious
Sapientia
Scientia
Boobota
Anandapedia
Sagapedia
Wikithot