1. ordens prædikatlogik

Lige endnu et lille spørgsmål:

Definition af en tautologi:
Et sammensat udtryk, der altid er sandt, kaldes for en tautologi

Kan det sammensatte udtryk både være åbent og lukket, hvis det er en tautologi?

Udsagnslogik (eng: propositional logic) beskæftiger sig kun med lukkede udsagn. Et lukket udsagn er et udsagn (proposition) som er enten sandt eller falskt. Eksempler på lukkede udsagn er:

Månen er lavet af grøn ost.
Idag er en onsdag.

Førsteordens prædikatlogik adskiller sig fra udsagnslogik ved at tillade variable, prædikater, der udtaler sig om egenskaber ved disse variable, samt kvantifiseringer, dog kun over de variable. Notationen er bevist valgt lig funktionsnotationen, idet prædikater for specifikke værdier af den/de variable producerer et (lukket) udsagn.

Betragt f.eks. sætningen:

x > 3

her er x den frie variabel (fri betyder: ikke bundet under en kvantificering) og "> 3 " er prædikatet (egenskaben, der karakteriserer den frie variabel). Denne sætning kan repræsenteres ved symbolet p(x). Vælges f.eks. Z som domænet for x kan vi betragte sætningen p(2) som er det (falske) lukkede udsagn 2 > 3. Bemærk, det har ikke mening at spørge hvad sandhedsværdien af p(x) er. Spørgsmålet er meningsløst idet sætningen p(x) nogle gange er sand (f.eks. for x=5), andre gange falsk (f.eks. for x=2). Sandhedsværdien af p(x) er et _åbent_ spørgsmål indtil x tildeles en værdi. En anden måde at sige det på, er at åbne udsagn ikke har nogen sandhedsværdi.

Svarene på alle tre spørgsmål i #0 er derfor ja.

I prædikatlogikken indføres endvidere alkvantoren og eksistensalkvantoren til at kvantifisere en variabel over et domæne. Man siger, at den kvantifiserede variabel er bundet. En fri variabel er således en variabel, der ikke er bundet. Da kvantorerne definitionsmæssigt udtrykker sande, lukkede udsagn kan vi alternativt helt generelt definere:

Et åbent udsagn er et udsagn hvori der forekommer frie variable.

Et lukket udsagn er et udsagn hvori der ikke forekommer frie variable.

En tautologi i prædikatlogik er lidt anderledes end i udsagngslogik. En tatutologi i prædikatlogik er et udsagn, der er sandt for _alle_ mulige denotationer af de variable, konstanter i prædikater og individuelle konstanter. Udsagnet

forall(x)[P(X) \\/ non P(X)]

er således en tautologi. Det er et sammensat, lukket udsagn.

Da tautologier altid er sande, og dermed _har_ en sandhedsværdi, er de lukkede udsagn.

Hej fixer

Endnu en gang tak for et suverænt og let-forståeligt svar! :)

Nu kan jeg fortsætte rapportskrivningen, så det er bare skønt.

Nu glemte jeg det da helt.

Jeg sidder og roder med aflukning af relationer. I bogen står der følgende:

"In general, let R be a relation on a set A. R may or may not have some proporty P, such as reflexive, symmetry or transitivity. If there is a relation S with property P containing R such that S is a subset of every relation with property P containing R, then S is called the closure of R with respect to P."

Hvad menes der hermed?
Jeg har svært ved at se, hvorfor de blander en egenskab P ind i det?

Det forstår jeg godt du ikke forstår, for det er da helt håbløst beskrevet.

Der gælder helt generelt, at afslutningen (eng: closure) af et matematisk objekt, O, er det mindste objekt der indeholder O og besidder en given egenskab.

Som eksempel kan vi tage afslutningen af en mængde M i et topologisk rum. Afslutningen af M er den mindste mængde som indeholder M og er lukket.

Man kalder et objekt lukket dersom det er identisk med sin afslutning.

Lad os prøve at analysere denne knudrede sætning:

"If there is a relation S with property P containing R such that S is a subset of every relation with property P containing R,"

Ifølge denne sætning skal vi betragte _samtlige_ relationer, som indeholder R og har egenskaben P. Blandt disse skal vi udse os en som er en delmængde af dem allesammen. Denne relation, S, vil altså indeholde R og have egenskaben P. Da den er en delmængde af samtlige relationer med denne egenskab, er S den mindste relation, der indeholder R og har egenskaben P. Thi den er jo i så fald også en delmæmgde af den mindste af samtlige relationer med egenskab P og som indeholder R.

Den tekstuelle beskrivelse fra bogen er altså helt i tråd med den mere simple, generelle definition ovenfor. Man har blot omskrevet en klar definition til noget mere hemmeligt.

Bemærk, at det er ligegyldigt, om R selv har egenskaben P. Det, der kendetegner afslutningen er netop, at det er den mindste relation, der har denne egenskab og som indeholder R, uafhængigt af R's egenskaber.

I klart sprog har vi til eksempel, at den transitive afslutning af en relation R, er dèn mindste transitive relation, S, som indeholder R.

Den refleksive afslutning af en relation R er dèn mindste refleksive relation, S, som indeholder R.

"Det forstår jeg godt du ikke forstår, for det er da helt håbløst beskrevet."

Tak! Så føler jeg mig ikke helt så dum :)

"Da den er en delmængde af samtlige relationer med denne egenskab, er S den mindste relation, der indeholder R og har egenskaben P."

Hvorfor er S den mindste relation?
Kunne man ikke forestille sig, at man havde valgt en anden relation i stedet for S, som så var en mindre delmængde end S?

Jeg har prøvet at læse dit svar igennem adskillige gange, men har stadig svært ved at forstå:
"Thi den er jo i så fald også en delmængde af den mindste af samtlige relationer med egenskab P og som indeholder R."

Hvorfor følger dette ud fra den foregående sætning?

Hvad menes med "den mindste af samtlige relationer"? Den mindste af samtlige relationer, er det den relation, som indeholder færrest par?

Kan du uddybe "Man kalder et objekt lukket dersom det er identisk med sin afslutning."?
Hvad menes med "identisk med sin afslutning"? Hvis M er en mængde med afslutningen Q, skal der så gælde, at Q=M? Hvor Q så derudover besidder egenskaben P?

Du får mange tak for svaret :)

Det her er virkelig kringlet.

Forresten kender du så en præcis definition på, hvad en transitiv aflukning er?

Jeg har prøvet at søge på internettet og kigget i min diskrete matematikbog, men der står ikke en præcis definition.

Med mindste relation menes den relation, der har færrest elementer.

Det behøver ikke være par. Det er kun tilfældet hvis vi betragter binære relationer. Generelt er en relation R over mængderne M_1,...,M_k, jo en delmængde af det Cartesiske produkt M_1 X M_2 X ... X M_k. En relation over k mængder er således blot en k-tuppel.

Det er som om, du får vendt de to sætninger, i hvilke jeg argumenterer for at S er den mindste relation, på hovedet, således at du mener argumentet følger af konklusionen.

Du er vel med på, at ifølge det, der står i din bog, skal vi betragte _alle_ de relationer, der har en given egenskab, P, og som indeholder R.

Hvis R er en relation over mængderne A og B (for nu at holde os til de binære), så er R en delmængde af A X B. Vi søger nu afslutningen med egenskaben P til R.

Dertil betragter vi _alle_ relationer S over A, B der har denne egenskab og som indeholder R. D.v.s. vi betragter alle de delmængder S_i af A X B, som indeholder R og hvor (a,b) E S_i.

Blandt alle disse delmængder S_i vil der være (mindst) en som har det mindste antal elementer.

Og da vi - ifølge den engelske tekst - skal vælge en delmængde, som er en delmængde af _alle_ delmængderne S_i må vi skulle vælge den mindste delmængde, S_min. Vælger vi nemlig en større, vil den ikke være en delmængde af S_min.

Til dit sidste spørgsmål:

Ja.

Betragt f.eks. intervallet I=]0,1[ i R. Afslutningen til I er Q=[0,1], thi det er den mindste mængde i R, der indeholder I og som besidder egenskaben at være lukket. Da I != Q er I ikke lukket.

Betragtes I=[0,1] er afslutningen atter Q=[0,1], thi Q er den mindste mængde i R, der indeholder I og besidder egenskaben at være lukket. Da I = Q er I lukket.

#7
Ja. Se #5.

#9 Selvfølgelig - jeg havde læst det i #5, som om der stod afslutning begge steder.

Endnu en gang mange tak for dit svar!

Det er virkelig skønt at få en aha-oplevelse :)