Velformet formel - Well-formed formula

I matematisk logik er propositionelogik og predikatlogik en velformet formel , forkortet WFF eller wff , ofte simpelthen formel , en endelig sekvens af symboler fra et givet alfabet, der er en del af et formelt sprog . Et formelt sprog kan identificeres med sæt formler på sproget.

En formel er et syntaktisk objekt, der kan tildeles en semantisk betydning ved hjælp af en fortolkning. To vigtige anvendelser af formler er i propositionelogik og predikatlogik.

Introduktion

En vigtig anvendelse af formler er i propositionelogik og predikatlogik såsom førsteordenslogik . I disse sammenhænge er en formel en streng af symboler φ, som det giver mening at spørge "er φ sandt?", Når alle gratis variabler i φ er blevet instantificeret. I formel logik kan bevis repræsenteres af sekvenser med formler med bestemte egenskaber, og den endelige formel i sekvensen er det, der er bevist.

Selvom udtrykket "formel" kan bruges til skriftlige mærker (for eksempel på et stykke papir eller tavle), forstås det mere præcist som rækkefølgen af ​​symboler, der udtrykkes, hvor mærkerne er en symbolsk forekomst af formlen. Således kan den samme formel skrives mere end én gang, og en formel kan i princippet være så lang, at den slet ikke kan skrives i det fysiske univers.

Formler i sig selv er syntaktiske objekter. De får betydning ved fortolkninger. For eksempel i en propositionsformel kan hver propositionsvariabel fortolkes som en konkret proposition, så den overordnede formel udtrykker et forhold mellem disse propositioner. En formel behøver ikke at fortolkes, men skal kun betragtes som en formel.

Propositionel beregning

Formlerne for propositionel beregning , også kaldet propositionelle formler , er udtryk som . Deres definition begynder med det vilkårlige valg af et sæt V af propositionelle variabler . Alfabetet består af bogstaverne i V sammen med symbolerne for propositional connectives og parenteser "(" og ")", som alle antages at være i V . Formlerne vil være visse udtryk (dvs. symbolstrenge) over dette alfabet. ${\ displaystyle (A \ land (B \ lor C))}$

Formlerne defineres induktivt som følger:

• Hver propositionsvariabel er alene en formel.
• Hvis φ er en formel, er ¬φ en formel.
• Hvis φ og ψ er formler, og • er en hvilken som helst binær forbindelse, er (φ • ψ) en formel. Her kan • være (men er ikke begrænset til) de sædvanlige operatorer ∨, ∧, → eller ↔.

Denne definition kan også skrives som en formel grammatik i Backus – Naur-form , forudsat at variabelsættet er endeligt:

<alpha set> ::= p | q | r | s | t | u | ... (the arbitrary finite set of propositional variables)
<form> ::= <alpha set> | ¬<form> | (<form>∧<form>) | (<form>∨<form>) | (<form>→<form>) | (<form>↔<form>)

Ved hjælp af denne grammatik, rækkefølgen af ​​symboler

((( p → q ) ∧ ( r → s )) ∨ (¬ q ∧ ¬ s ))

er en formel, fordi den er grammatisk korrekt. Sekvensen af ​​symboler

(( p → q ) → ( qq )) p ))

er ikke en formel, fordi den ikke er i overensstemmelse med grammatikken.

En kompleks formel kan være vanskelig at læse på grund af for eksempel spredning af parenteser. For at afhjælpe dette sidste fænomen antages forrangsregler (beslægtet med den standard matematiske rækkefølge ) blandt operatørerne, hvilket gør nogle operatører mere bindende end andre. For eksempel antager vi forrang (fra mest binding til mindst binding) 1. ¬ 2. → 3. ∧ 4. ∨. Derefter formlen

((( p → q ) ∧ ( r → s )) ∨ (¬ q ∧ ¬ s ))

kan forkortes som

p → q ∧ r → s ∨ ¬ q ∧ ¬ s

Dette er dog kun en konvention, der bruges til at forenkle den skriftlige repræsentation af en formel. Hvis forresten for eksempel blev antaget at være venstre-højre-associerende i følgende rækkefølge: 1. ¬ 2. ∧ 3. ∨ 4. →, ville den samme formel ovenfor (uden parentes) blive omskrevet som

( p → ( q ∧ r )) → ( s ∨ ((¬ q ) ∧ (¬ s )))

Prædikatlogik

Definitionen af ​​en formel i første ordens logik er i forhold til underskriften af den aktuelle teori. Denne signatur specificerer de konstante symboler, prædikatforbrydelser symboler og funktionssymboler af teorien ved hånden, sammen med arities af funktionen og prædikatforbrydelser symboler. ${\ displaystyle {\ mathcal {QS}}}$

Definitionen af ​​en formel findes i flere dele. For det første sæt af termer er defineret rekursivt. Termer, uformelt, er udtryk, der repræsenterer objekter fra diskursens domæne .

1. Enhver variabel er et udtryk.
2. Ethvert konstant symbol fra signaturen er et udtryk
3. et udtryk for formen f ( t ₁ ,…, t _n ), hvor f er et n -ary funktionssymbol, og t ₁ ,…, t _n er udtryk, er igen et udtryk.

Det næste trin er at definere atomformlerne .

1. Hvis t ₁ og t ₂ er vilkår derefter t ₁ = t ₂ er et atomart formel
2. Hvis R er en n -foldig prædikat symbol, og t ₁ , ..., t _n er udtryk, og derefter R ( t ₁ , ..., t _n ) er et atomart formel

Endelig er sættet med formler defineret til at være det mindste sæt, der indeholder sættet med atomformler, således at følgende gælder:

1. ${\ displaystyle \ neg \ phi}$ er en formel hvornår er en formel ${\ displaystyle \ phi}$
2. ${\ displaystyle (\ phi \ land \ psi)}$ og er formler, hvornår og er formler; ${\ displaystyle (\ phi \ lor \ psi)}$${\ displaystyle \ phi}$${\ displaystyle \ psi}$
3. ${\ displaystyle \ eksisterer x \, \ phi}$ er en formel, når er en variabel, og er en formel; ${\ displaystyle x}$${\ displaystyle \ phi}$
4. ${\ displaystyle \ forall x \, \ phi}$ er en formel når er en variabel og er en formel (alternativt kunne defineres som en forkortelse for ). ${\ displaystyle x}$${\ displaystyle \ phi}$${\ displaystyle \ forall x \, \ phi}$${\ displaystyle \ neg \ eksisterer x \, \ neg \ phi}$

Hvis en formel ikke har nogen forekomster af eller for en variabel , kaldes den kvantificeringsfri . En eksistentiel formel er en formel, der starter med en sekvens af eksistentiel kvantificering efterfulgt af en kvantificeringsfri formel. ${\ displaystyle \ eksisterer x}$${\ displaystyle \ forall x}$${\ displaystyle x}$

Atomiske og åbne formler

En atomformel er en formel, der ikke indeholder nogen logiske forbindelser eller kvantificeringsmidler , eller tilsvarende en formel, der ikke har nogen strenge underformler. Den nøjagtige form for atomformler afhænger af det formelle system, der overvejes; for propositionelogik er atomformlerne for eksempel de propositionelle variabler . For predikatlogik er atomerne predikatsymboler sammen med deres argumenter, hvor hvert argument er et udtryk .

Ifølge en eller anden terminologi dannes en åben formel ved at kombinere atomformler, der kun bruger logiske forbindelser, med undtagelse af kvantificeringsmidler. Dette må ikke forveksles med en formel, der ikke er lukket.

Lukkede formler

En lukket formel , også formalet formel eller sætning , er en formel, hvor der er ingen frie forekomster af enhver variabel . Hvis A er en formel for en første ordens sprog hvori variablerne v ₁ , ..., v _n har fri forekomster, så A Forud v ₁ ⋯ v _n er en lukning af A . ${\ displaystyle \ forall}$${\ displaystyle \ forall}$

Egenskaber, der gælder for formler

• En formel A på et sprog er gyldig, hvis den gælder for enhver fortolkning af . ${\ displaystyle {\ mathcal {Q}}}$${\ displaystyle {\ mathcal {Q}}}$
• En formel A på et sprog er tilfredsstillende, hvis det er sandt for en eller anden fortolkning af . ${\ displaystyle {\ mathcal {Q}}}$${\ displaystyle {\ mathcal {Q}}}$
• En formel A af sproget i aritmetiske er afgørbart hvis den repræsenterer en beslutningsrepræsentation sæt , dvs. hvis der er en effektiv metode som, givet en substitution af de frie variabler i A , siger, at enten den resulterende forekomst af A er bevislig eller dens negation er .

Anvendelse af terminologien

I tidligere værker om matematisk logik (f.eks. Af Church ) henviste formler til enhver symbolstreng og blandt disse strenge var velformede formler strengene, der fulgte formationsreglerne for (korrekte) formler.

Flere forfattere siger simpelthen formel. Moderne kutymer (især i forbindelse med datalogi med matematisk software som model brikker , automatiserede sætningen provers , interaktive sætningen provers ) tendens til at beholde af begrebet formel kun den algebraiske koncept og til at forlade spørgsmålet om veludformning , dvs. den konkrete strengrepræsentation af formler (ved hjælp af dette eller det andet symbol til tilslutnings- og kvantificeringsmidler, ved hjælp af denne eller den anden parentesekonvention , ved hjælp af polsk eller infix- notation osv.) som et rent notationsproblem.

Mens udtrykket velformet formel stadig er i brug, bruger disse forfattere ikke nødvendigvis det i modsætning til den gamle betydning af formlen , som ikke længere er almindelig i matematisk logik.

Udtrykket "velformede formler" (WFF) sneg sig også ind i populærkulturen. WFF er en del af en esoterisk ordspil brugt i navnet på det akademiske spil " WFF 'N PROOF : The Game of Modern Logic", af Layman Allen, udviklet mens han var på Yale Law School (han var senere professor ved University of Michigan ). Pakken af ​​spil er designet til at lære børnene om symbolsk logik (i polsk notation ). Dets navn er et ekko af whiffenpoof , et nonsensord, der blev brugt som jubel ved Yale University, der blev populært i The Whiffenpoof Song og The Whiffenpoofs .

Se også

• Jordudtryk

Bemærkninger

Referencer

• Allen, Layman E. (1965), "Mod autotelic Learning of Mathematical Logic by the WFF 'N PROOF Games", Mathematical Learning: Report of a Conference Sponsored by the Committee on Intellective Processes Research of the Social Science Research Council , Monographs of the Society for Research in Child Development, 30 (1): 29–41
• Boolos, George ; Burgess, John; Jeffrey, Richard (2002), Computability and Logic (4. udgave), Cambridge University Press , ISBN   978-0-521-00758-0
• Ehrenberg, Rachel (forår 2002). "Han er positivt logisk" . Michigan i dag . University of Michigan. Arkiveret fra originalen den 2009-02-08 . Hentet 2007-08-19 .
• Enderton, Herbert (2001), En matematisk introduktion til logik (2. udgave), Boston, MA: Academic Press , ISBN   978-0-12-238452-3
• Gamut, LTF (1990), Logik, sprog og betydning, bind 1: Introduktion til logik , University Of Chicago Press, ISBN   0-226-28085-3
• Hodges, Wilfrid (2001), "Classical Logic I: First-Order Logic", i Goble, Lou (red.), The Blackwell Guide to Philosophical Logic , Blackwell, ISBN   978-0-631-20692-7
• Hofstadter, Douglas , Gödel, Escher, Bach: En evig gylden fletning , Penguin Books , ISBN   978-0-14-005579-5
• Kleene, Stephen Cole (2002) [1967], Matematisk logik , New York: Dover Publications , ISBN   978-0-486-42533-7 , MR   1950307
• Rautenberg, Wolfgang (2010), En kort introduktion til matematisk logik (3. udgave), New York : Springer Science + Business Media , doi : 10.1007 / 978-1-4419-1221-3 , ISBN   978-1-4419-1220-6

eksterne links

• Velformet formel til First Order Predicate Logic - inkluderer en kort Java- quiz.
• Velformet formel på ProvenMath