Elégedettség

A logika és a matematika, SAT van egy metanyelvi állítmány az ingatlan logikai állítások és nyilatkozat formáját . Egy állítás akkor teljesíthető, ha van olyan hozzárendelés (értelmezés, értékelés ) azoknak a változóknak , amelyekre a teljes kifejezés igazságértéke igaz .

matematika

A matematikában különösen érdekes az (in) egyenletek és (in) egyenletrendszerek kielégíthetősége . Ezután az általános definíció átfogalmazható: "Van (legalább) egy megoldás."

Példák: A valós számok elméletében (vagyis a szokásos számrendszerben) az egyenlet megoldható, azaz ez az állítás teljesíthető. ${\ displaystyle 2x + 1 = 3x}$

Az egyenletrendszer viszont nem megoldható, mert az egyetlen megoldás az akaratra , de ez a megoldás nem elégít ki . Tehát ez az állítás nem teljesíthető. ${\ displaystyle x <0, x ^ {2} \ leq 0}$${\ displaystyle x ^ {2} \ leq 0}$${\ displaystyle x = 0}$${\ displaystyle x <0}$

logika

Propozíciós logika

A propozíciós logikában az állítások kielégítőségük alapján osztályozhatók, ezáltal a előforduló változók igazságértékeket állítanak fel állításként. A nyilatkozat egy formáját hívják ...

• akkor teljesíthető, ha a változó legalább egy hozzárendelése igaz állítást eredményez.
• egy tautológia , ha minden (!) hozzárendelése a változók termel igaz állítás.
• Egy ellentmondás , ha nem teljesíthető. Az ellentmondás tagadása mindig tautológia. Az "ellentmondás" kifejezés ellentéte azonban nem a "tautológia", hanem az "elégedettség".
• a készenléti vagy semlegesség , ha az nem tautológia, sem ellentmondás.
• hamisítható, ha legalább egy foglaltság nem képvisel modellt , vagyis hamis állítást generál.

A propozíciós képlet kielégíthetőségének eldöntésének problémáját a propozíciós logika kielégíthetőségi problémájának nevezzük . Ez a probléma fontos többek között a komplexitáselméletben .

Példák

A propozíciós változó (amely egyébként nem fordul elő) önmagában is teljesíthető, akár egy esetlegesség is. A propozíciós változó tulajdonsága, hogy igazságértéke igaz vagy hamis. ${\ displaystyle A}$

Az állítás (olvassa el: vagy sem ) tautológia, tehát teljesíthető is, mert minden igaz vagy hamis hozzárendelés igaz állítást ad. Következésképpen az állítás (az előző példa tagadása) ellentmondás, vagyis nem teljesíthető. ${\ displaystyle A \ vee \ neg A}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle A}$${\ displaystyle \ neg (A \ vee \ neg A)}$

Predikálja a logikát

A propozíciós logikához hasonlóan az elégedettség kifejezést az állítmányi logikában is használják : Az állítmányi logikai képlet akkor teljesülhet, ha létezik az állítmányok értelmezése és azoknak a változóknak a hozzárendelése, amelyekre a képlet feltételezi, hogy az igazságérték igaz ( kielégíthetőségi egyenértékűség ).

Példák

• ${\ displaystyle \ forall x (x = x)}$ "minden x esetében: x x" tautológia, mivel x mindig azonos önmagával.
• ${\ displaystyle \ forall x \ létezik y (x \ neq y)}$ "minden x-re van egy y, amelyre az alábbiak vonatkoznak: x nem egyenlő y-vel" egy esetleges esemény, mivel ez csak akkor teljesülhet, ha az objektumok halmazában egynél több objektum van, amelyek közül x-t és y-t választanak.
• ${\ displaystyle \ létezik x (x \ neq x)}$ "minden x-re a következő vonatkozik: x nem egyenlő x-szel" ellentmondás, az állítás minden objektumra hibás.

Lásd még

• Előreláthatóság
• Modellelmélet
• felbontás
• intolerancia