Fråga om satslogik

Jag läste på lite och det är faktiskt inte så svårt.

1. ∀x(M(x)⇒O(x))
2. M(a)
--------
3. M(a)⇒O(a) (Universal instantiation, 1,2)
4. O(a) (Implication 2,3)

Inte riktigt. Vi ville dra slutsatsen "Kalle är ond" och inte "Det finns någon som är ond". Den förstnämnda kan vi skriva O(a) där a är kalle, medan det sistnämnda blir ∃xO(x).

Däremot kan vi ju även dra denna slutsats.

Existensintroduktion ser ut så här:

P(a) -> ∃xP(x)

Eftersom vi i mitt bevis hade dragit slutsatsen O(a) kan vi alltså mha existensintroduktion dra slutsatsen ∃xO(x)

Det verkar korrekt. Det här med "Universal instantiation" var något nytt som jag aldrig hört talas om förut. Det verkar som att det här med predikatlogik är ganska komplext.

Det är rätt komplext, och jag gjorde ett litet fel i beviset. Jag glömde att UI kräver två rader för motiveringen. Det är fixat nu.



I grunden handlar logik om att tillämpa alla regler man får lära sig, men det viktigaste är nog att du ALDRIG får använda sunt förnuft. ALLA steg du gör måste motiveras med en regel.

När man börjar med logik så försöker man attackera med sunt förnuft men det tar en inte långt.

Är det samma sak i predikatlogiken som i satslogiken att man skriver premisserna ovanför strecket och drar slutsatserna under strecket. Det kanske är så att man inte använder streck i predikatlogik? Jag är lite osäker eftersom det inte används något streck när Modus tollens förklaras för predikatlogik i länken nedan:

http://sv.wikipedia.org/wiki/Modus_tollens

Dem använder kanske symbolen som består av tre punkter istället?

Nja, det där är ju enbart en notationsteknikalitet. Det finns lite olika system för hur man skriver, även om reglerna är samma. Personligen använder jag alltid sådana streck oavsett. När jag använder subbevis använder jag lodräta linjer. Ungefär så här ser det ut:

http://www.personal.psu.edu/dxb277/m...hy/page_07.htm

Observera att ⊃ är samma sak som → eller ⇒.

Ska man lära sig logik så är det nog lämpligt att göra som i den här tråden och syssla både med satslogik och predikatlogik. Det är lättare att förstå när man kan jämföra dem med varandra.

Jag har funderat lite på hur man ska tackla följande problem i satslogik och predikatlogik:

Avgör om påståendet är sant?

För alla x gäller x>1=>x^2>1

Om vi endast pratar reella tal, vilket jag antar att du gör eftersom du använder dig av >, så stämmer påståendet. Det vet jag eftersom för x = 1 så är x^2 = 1 och potensfunktionerna (som x -> x^2 tillhör) är strängt växande, dvs x > y => x^2 > y^2.

Din lösning är vad jag kan se helt korrekt och det är en sådan typ av lösning jag skulle gjort om jag fått uppgiften på en matematik tenta. Men sen jag börjat sätta mig in i logik så har jag börjat intressera mig för hur man gör om man måste hålla sig till logikens strikta formella regelsystem.

Nja, jag skulle nog säga att det bästa är att möjligtvis nämna predikatlogik i förbifarten, men att börja ordentligt med satslogik. I princip är tänken exakt lika, men med predikatlogiken får man många fler verktyg.
Nu börjar det hela bli rätt avancerat.

För det första är ditt påstående inte ordentligt specificerat. Du har glömt att nämna att x ska vara ett tal. Vi kan också fundera på vilken typ av tal vi menar. Exempel är naturliga tal, heltal, rationella tal och reella tal. De komplexa talen är inte relevanta eftersom > inte är definierat för dem. Vi skulle kunna välja de reella talen, men då blir förmodligen bevisen rätt krångliga. Vi nöjer oss med de naturliga talen och formulerar ditt påstående på följande sätt:

∀x[(Nx and (x>1) ⇒ (x²>1)]

Sen börjar det dryga. Vi börjar med att titta på definitionen av potenser för naturliga tal, och nu förstår du nog varför jag inte valde reella. S är successorfunktionen som i princip betyder "nästa tal". I praktiken är S(n)=n+1.

x^S(y)=x*(x^y)
x^0=1

Det verkar som att vi även måste titta på definitionen av multiplikation också.

x*S(y)=x+x*y
x*0=0

Addition måste vi också ha.

x+S(y)=S(x+y)
x+0=x

Vi kan ta ett exempel:
4+2=4+S(1)=S(4+1)=S(4+S(0))=S(S(4+0))=S(S(4))


Det kan även vara värt att nämna hur de naturliga talen är definierade. De definieras med Peanos axiom.

1. N0 Noll är ett naturligt tal
2. ∀xNx(x=x) Lika med är reflexiv
3. ∀xNx∀yNy(x=y ⇒ y=x) Lika med är symmetrisk
4. ∀xNx∀yNy∀zNz(x=y and y=z ⇒ x=z) Lika med är transitiv
5. ∀xNx∀y(x=y ⇒ Ny) De naturliga talen är stängda under lika med
6. ∀xNx(NS(x)) Om x är ett tal så är S(x) ett tal
7. ∀xNx(~S(x)=0) Det finns inget tal sådant att S(x)=0, dvs 0 är det minsta talet
8. ∀xNx∀yNy(S(x)=S(y) ⇒ x=y) S är en injektiv funktion, dvs om x och y är olika så är S(x) och S(y) också olika.
9. Om [0∈M and (∀xNx(x∈M ⇒ S(x)∈M))] så innehåller M alla (naturliga) tal.



Sen ska vi ju definiera olikheter också. Det kan vi göra på följande sätt.

∀xNx∀yNy(x≤y ⇔ ∃zNz(x+z=y))

På liknande sätt kan vi definiera strikt olikhet:

∀xNx∀yNy(x<y ⇔ ∃zNz(x+S(z)=y))




Nu tror jag att du har allt du behöver för att visa att ∀x[(Nx and (x>1) ⇒ (x²>1)]

Jag tänkte att jag skulle spåna lite på ett bevis här. Vi slarvar lite och struntar i att tala om att x är ett tal och liknande petitesser. Jag påminner om definitionen av <:
∀x∀y(x<y ⇔ ∃z(x+S(z)=y))

Jag vänder även på olikheterna.


∀x[(1<x) ⇒ (1<x²)]
Anta 1<a (Introduktion av a)
∃b(1+S(b)=a) (Definition av <)
Anta c=a² (Intro c)
c=a*a (Def av potens)
c=(1+S(b))*(1+S(b)) (Insättning)
c=(S(1+b))*(S(1+b)) (Def av +)
c=(S(S(0)+b)*(S(S(0)+b)) (Def av +)
c=(S(S(0+b))*(S(S(0+b)) (Def av +)
c=(S(S(b))*(S(S(b)) (Def av +)
Anta b=0 (Om detta stämmer för b=0 stämmer det även för b>0, men jag fuskar och visar inte det)
c=S(S(0))+S(S(0))*S(0) (Def av *)
1=S(0) (Påminner om def av 1)
Anta d=S(S(0))*S(0) (Observera 2 mindre än c)
1+S(d)=c (Def av en massa och nu fuskar jag som fan)
1<c (Def av <)
1<a*a (Insättning)


Ungefär så tror jag att beviset skulle kunna se ut, men jag medger att jag är ute på djupt vatten här, och det finns förmodligen några saker jag har missat förutom de jag struntat i.

Jag ser att problemet är mycket komplicerat för predikatlogik. Hade inte kunnat drömma om att det skulle vara så svårt. Men hur löser man problemet i satslogik? Som jag ser det så kan man inte lösa uppgiften i satslogik. Stämmer det?