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.
Utsagnlogiske utrykk, P vs NP
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
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?
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?
[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?