Logisk ækvivalens - Logical equivalence

I logik og matematik siges udsagn og at være logisk ækvivalente, hvis de kan bevises fra hinanden under et sæt aksiomer eller har den samme sandhedsværdi i hver model . Den logiske ækvivalens og er undertiden udtrykkes som , , , eller , afhængigt af notationen der anvendes. Imidlertid bruges disse symboler også til materiel ækvivalens , så korrekt fortolkning vil afhænge af sammenhængen. Logisk ækvivalens er forskellig fra materiel ækvivalens, skønt de to begreber er iboende forbundet. ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p \ equiv q}$${\ displaystyle p :: q}$${\ displaystyle {\ textsf {E}} pq}$${\ displaystyle p \ iff q}$

Logiske ækvivalenser

I logik findes der mange almindelige logiske ækvivalenser og er ofte opført som love eller egenskaber. Følgende tabeller illustrerer nogle af disse.

Generelle logiske ækvivalenser

Ækvivalens	Navn
${\ displaystyle p \ wedge \ top \ equiv p}$ ${\ displaystyle p \ vee \ bot \ equiv p}$	Identitetslove
${\ displaystyle p \ vee \ top \ equiv \ top}$ ${\ displaystyle p \ wedge \ bot \ equiv \ bot}$	Dominanslove
${\ displaystyle p \ vee p \ equiv p}$ ${\ displaystyle p \ wedge p \ equiv p}$	Idempotent eller tautologi love
${\ displaystyle \ neg (\ neg p) \ equiv p}$	Dobbelt negation lov
${\ displaystyle p \ vee q \ equiv q \ vee p}$ ${\ displaystyle p \ wedge q \ equiv q \ wedge p}$	Kommutative love
${\ displaystyle (p \ vee q) \ vee r \ equiv p \ vee (q \ vee r)}$ ${\ displaystyle (p \ wedge q) \ wedge r \ equiv p \ wedge (q \ wedge r)}$	Associerende love
${\ displaystyle p \ vee (q \ wedge r) \ equiv (p \ vee q) \ wedge (p \ vee r)}$ ${\ displaystyle p \ wedge (q \ vee r) \ equiv (p \ wedge q) \ vee (p \ wedge r)}$	Distributive love
${\ displaystyle \ neg (p \ wedge q) \ equiv \ neg p \ vee \ neg q}$ ${\ displaystyle \ neg (p \ vee q) \ equiv \ neg p \ wedge \ neg q}$	De Morgans love
${\ displaystyle p \ vee (p \ wedge q) \ equiv p}$ ${\ displaystyle p \ wedge (p \ vee q) \ equiv p}$	Absorptionslove
${\ displaystyle p \ vee \ neg p \ equiv \ top}$ ${\ displaystyle p \ wedge \ neg p \ equiv \ bot}$	Negationslove

Logiske ækvivalenser, der involverer betingede udsagn

1. ${\ displaystyle p \ antyder q \ equiv \ neg p \ vee q}$
2. ${\ displaystyle p \ antyder q \ equiv \ neg q \ antyder \ neg p}$
3. ${\ displaystyle p \ vee q \ equiv \ neg p \ implicerer q}$
4. ${\ displaystyle p \ wedge q \ equiv \ neg (p \ implicerer \ neg q)}$
5. ${\ displaystyle \ neg (p \ implicerer q) \ equiv p \ wedge \ neg q}$
6. ${\ displaystyle (p \ implicerer q) \ wedge (p \ implicerer r) \ equiv p \ implicerer (q \ wedge r)}$
7. ${\ displaystyle (p \ implicerer q) \ vee (p \ implicerer r) \ equiv p \ implicerer (q \ vee r)}$
8. ${\ displaystyle (p \ implicerer r) \ wedge (q \ implicerer r) \ equiv (p \ vee q) \ implicerer r}$
9. ${\ displaystyle (p \ implicerer r) \ vee (q \ implicerer r) \ equiv (p \ wedge q) \ implicerer r}$

Logiske ækvivalenser, der involverer biconditionals

1. ${\ displaystyle p \ iff q \ equiv (p \ impliserer q) \ wedge (q \ implicerer p)}$
2. ${\ displaystyle p \ iff q \ equiv \ neg p \ iff \ neg q}$
3. ${\ displaystyle p \ iff q \ equiv (p \ wedge q) \ vee (\ neg p \ wedge \ neg q)}$
4. ${\ displaystyle \ neg (p \ iff q) \ equiv p \ iff \ neg q}$

Eksempler

I logik

Følgende udsagn er logisk ækvivalente:

1. Hvis Lisa er i Danmark , så er hun i Europa (en formularerklæring ).${\ displaystyle d \ implicerer e}$
2. Hvis Lisa ikke er i Europa, er hun ikke i Danmark (en formularerklæring ).${\ displaystyle \ neg e \ implicerer \ neg d}$

Syntaktisk kan (1) og (2) afledes fra hinanden via reglerne for kontraposition og dobbelt negation . Semantisk er (1) og (2) sande i nøjagtigt de samme modeller (fortolkninger, værdiansættelser); nemlig dem, hvor enten Lisa er i Danmark, er falske eller Lisa er i Europa, er sandt.

(Bemærk, at i dette eksempel antages klassisk logik . Nogle ikke-klassiske logikker anser ikke (1) og (2) for at være logisk ækvivalente.)

I matematik

I matematik siges to udsagn og er ofte logisk ækvivalente, hvis de kan bevises fra hinanden med et sæt aksiomer og forudsætninger. For eksempel kan udsagnet " kan deles med 6" betragtes som ækvivalent med udsagnet " kan deles med 2 og 3", da man kan bevise førstnævnte fra sidstnævnte (og omvendt) ved hjælp af en vis viden fra grundlæggende talteori . ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle n}$${\ displaystyle n}$

Forhold til materiel ækvivalens

Logisk ækvivalens er forskellig fra materiel ækvivalens. Formler og er logisk ækvivalente, hvis og kun hvis erklæringen om deres materielle ækvivalens ( ) er en tautologi. ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p \ iff q}$

Den materielle ækvivalens af og (ofte skrevet som ) er i sig selv en anden erklæring på det samme objektsprog som og . Denne erklæring udtrykker ideen "' hvis og kun hvis '". Især sandhedsværdien af kan skifte fra en model til en anden. ${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p \ leftrightarrow q}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p}$${\ displaystyle q}$${\ displaystyle p \ leftrightarrow q}$

På den anden side er påstanden om, at to formler er logisk ækvivalente, en erklæring i metasprog , der udtrykker et forhold mellem to udsagn og . Påstandene er logisk ækvivalente, hvis de i hver model har samme sandhedsværdi. ${\ displaystyle p}$${\ displaystyle q}$

Se også

• Entailment
• Equisatisfiability
• Hvis og kun hvis
• Logisk biconditional
• Logisk lighed
• ≡ den IFF symbol (U + 2261 identiske med )
• ∷ den a er at b som c er at d symbol (U + 2237 DEL )
• Bic den dobbeltslagede tobetingede (U + 21D4 VENSTRE HØJRE DOBBEL PIL )
• ↔ den tovejs pil (U + 2194 VENSTRE PIL HØJRE )

Referencer