I førsteordens prædikatlogik bruges kvantifikatorer til at udtrykke udsagn om omfanget eller mængden af objekter i et givet domæne. De to vigtigste kvantifikatorer, der bruges i førsteordens logik, er den universelle kvantifier (∀) og den eksistentielle kvantifier (∃). Når man negerer kvantificerede udsagn, er der specifikke regler, der skal følges for at sikre den korrekte fortolkning af negationen.
For at forklare reglerne for at negere kvantifikatorer, lad os overveje den universelle kvantifier (∀). Den universelle kvantifier bruges til at udtrykke, at en sætning gælder for alle objekter i et givet domæne. For at afvise et universelt kvantificeret udsagn skal vi udtrykke, at der eksisterer mindst ét objekt, som udsagnet ikke gælder for. Dette kan gøres ved at erstatte den universelle kvantifier med den eksistentielle kvantifier og negere selve udsagnet.
Lad os for eksempel overveje udsagnet "Alle katte er pattedyr." Dette kan udtrykkes i førsteordens logik som ∀x(Kat(x) → Pattedyr(x)), hvor Kat(x) repræsenterer prædikatet "x er en kat" og Pattedyr(x) repræsenterer prædikatet "x er en pattedyr". For at negere dette udsagn erstatter vi den universelle kvantifier (∀) med den eksistentielle kvantifier (∃) og negerer selve udsagnet. Negationen af udsagnet "Alle katte er pattedyr" er derfor ∃x(Kat(x) ∧ ¬Pattedyr(x)), hvilket kan læses som "Der eksisterer et objekt x sådan, at x er en kat og x ikke er en pattedyr."
Lad os nu overveje den eksistentielle kvantifier (∃). Den eksistentielle kvantifier bruges til at udtrykke, at der eksisterer mindst ét objekt i et givet domæne, som en sætning gælder for. For at afvise et eksistentielt kvantificeret udsagn skal vi udtrykke, at udsagnet ikke gælder for noget objekt i domænet. Dette kan gøres ved at erstatte den eksistentielle kvantifier med den universelle kvantifier og negere selve udsagnet.
Lad os for eksempel overveje udsagnet "Der findes et primtal større end 10." Dette kan udtrykkes i førsteordens logik som ∃x(Primtal(x) ∧ Større(x, 10)), hvor Prime(x) repræsenterer prædikatet "x er et primtal" og Større(x, 10) repræsenterer prædikat "x er større end 10". For at negere dette udsagn erstatter vi den eksistentielle kvantifier (∃) med den universelle kvantifier (∀) og negerer selve udsagnet. Negationen af udsagnet "Der findes et primtal større end 10" er derfor ∀x(¬Primtal(x) ∨ ¬Større(x, 10)), hvilket kan læses som "For alle objekter er x ikke en primtal eller x er ikke større end 10."
Når vi negerer kvantificerede udsagn i førsteordens prædikatlogik, erstatter vi den universelle kvantifier (∀) med den eksistentielle kvantifier (∃) og negerer selve udsagnet, eller vi erstatter den eksistentielle kvantifier (∃) med den universelle kvantifier (∀) og negerer selve udsagnet. Disse regler sikrer den korrekte fortolkning af negationen og giver os mulighed for at udtrykke udsagn om fraværet eller ikke-universaliteten af visse egenskaber eller relationer i et givet domæne.
Andre seneste spørgsmål og svar vedr EITC/IS/CCTF Computational Complexity Theory Fundamentals:
- Er regulære sprog ækvivalente med Finite State Machines?
- Er PSPACE-klassen ikke lig med EXPSPACE-klassen?
- Er et algoritmisk beregneligt problem et problem, der kan beregnes af en Turing-maskine i overensstemmelse med Church-Turing-afhandlingen?
- Hvad er lukkeegenskaben for regulære sprog under sammenkædning? Hvordan kombineres endelige tilstandsmaskiner for at repræsentere foreningen af sprog, der genkendes af to maskiner?
- Kan ethvert vilkårligt problem udtrykkes som et sprog?
- Er P kompleksitetsklassen en delmængde af PSPACE-klassen?
- Har hver multi-tape Turing-maskine en tilsvarende enkelt-tape Turing-maskine?
- Hvad er output af prædikater?
- Er lambdaregning og turingmaskiner beregnelige modeller, der besvarer spørgsmålet om, hvad betyder beregnelig?
- Kan vi bevise, at Np- og P-klassen er ens ved at finde en effektiv polynomielløsning for ethvert NP-fuldt problem på en deterministisk TM?
Se flere spørgsmål og svar i EITC/IS/CCTF Computational Complexity Theory Fundamentals