matematikk.net

En litteral er et utsganslogisk uttrykk på formen [tex]X[/tex], eller formen [tex]\bar{X},[/tex]der [tex]X[/tex] er en variabel.

Et utsagnslogsik uttrykk [tex]φ[/tex] er på knf (konjunktiv normalform) dersom
[tex]φ ≡ (ℓ_1^1 ∨ . . . ∨ ℓ_{k1}^1) ∧ . . . ∧ (ℓ_1^n ∨ . . . ∨ ℓ_{kn}^n)[/tex]
der [tex]ℓ_j^i[/tex] er litteraler.

Et utsagnslogsik uttrykk [tex]φ[/tex] er på dnf (disjunktiv normalform) dersom
[tex]φ ≡ (ℓ_1^1 ∧ . . . ∧ ℓ_{k1}^1) ∨ . . . ∨ (ℓ_1^n ∧ . . . ∧ ℓ_{kn}^n)[/tex]
der [tex]ℓ_j^i[/tex] er litteraler.

Det jeg lurer på er hva et litteral er? kan de representerer tallverdier? Eller hvordan kan jeg bruke disse variablene? *

Håper noen kan utdype litt her.

Slik jeg forstår det (og jeg kan ta feil!) er literaler en mild generalisering av et atomært utsagn som er den enkleste form for utsagn i teorien din (dvs. det kan ikke brytes ned til enkere utsagn). Mer nøyaktig er en literal et atomært utsagn eller negasjonen av et atomært utsagn.

Atomært utsagn i selg selv tror jeg kan være så mangt. Det avhenger av hva slags logikk ut ser på. Jeg har ikke studert dette i detalj, men jeg ser for meg noe slikt: I aksiomatisk mengdelære kan vi si at $x\in X$ er et atomært utsagn, mens $x\in X\cap Y$ ikke er det, fordi det kan brytes ned til $(x\in X) \wedge (x\in Y)$.

Hvis jeg tar feil her, håper jeg at noen irettesetter meg...

Wikilink:
http://en.wikipedia.org/wiki/Literal_%2 ... l_logic%29
http://en.wikipedia.org/wiki/Atomic_formula

PS: Hva har P vs NP med dette å gjøre?

Vi definerer kompleksitetsklassen coNP ved
[tex]A ∈ coNP ⇔ A ∈ NP[/tex] .
Et språk A er coNP-komplett dersom (i) A er i coNP og (ii) alle språk i coNP kan [tex]≤_p reduseres[/tex] til A.

vi anntar at [tex]NP \neq P[/tex] og at [tex]NP \neq coNP[/tex]

Så vil vi sjekke om et gitt utsagnlogisk utrykk er i P, P er da noe som kan testes i polinomiell tid.

gitt språket KNFSAT definert ved
KNFSAT = {φ | φ er på knf og φ er tilfredstillbar}
Hvordan kan jeg her teste om det er i P? eventuelt ikke i P?

Løst, Takk for hjelpen Espen