Matematické Fórum

hroch · 02. 01. 2011 14:25

Mám problém s dokazováním těcthto výroků

1)
Dokažte bez použití věty o úplnosti výrokové logiky .
Dokazatelný(A -> B) -> [(C -> D) -> ((A nebo C) ->(B nebo D))]

2)
Dokažte bez použití věty o úplnosti predikátové logiky
Dokazatelný (Existuje z)(P(z) -> (Všechna x)P(x))

Byl bych vdečný za jakýkoliv návod, já jsem pokoušel pomocí axiomů ale k ničemu jsem nedostal.

Wotton · 15. 02. 2011 16:47

Bohužel si nenapsal v čem se to má dokazovat, ... použiju na to HK (s větou o dedukci):

$A,C,(A\rightarrow B),(C\rightarrow D)&\vdash(A\rightarrow (B\vee D))\rightarrow((C\rightarrow (B\vee D))\rightarrow((A\vee C)\rightarrow(B\vee D)))\\ A,C,(A\rightarrow B),(C\rightarrow D)&\vdash(A\rightarrow (B\rightarrow(B\vee D)))\rightarrow((A\rightarrow B)\rightarrow(A\rightarrow(B\vee D)))\\ A,C,(A\rightarrow B),(C\rightarrow D)&\vdash(C\rightarrow (D\rightarrow(B\vee D)))\rightarrow((C\rightarrow D)\rightarrow(C\rightarrow(B\vee D)))\\ A,C,(A\rightarrow B),(C\rightarrow D)&\vdash B\rightarrow(B\vee D)\\ A,C,(A\rightarrow B),(C\rightarrow D)&\vdash D\rightarrow(B\vee D)\\ A,C,(A\rightarrow B),(C\rightarrow D)&\vdash A\rightarrow B\\ A,C,(A\rightarrow B),(C\rightarrow D)&\vdash C\rightarrow D\\ C,(A\rightarrow B),(C\rightarrow D)&\vdash A\rightarrow(B\rightarrow(B\vee D))\\ (A\rightarrow B),(C\rightarrow D)&\vdash C\rightarrow(D\rightarrow(B\vee D))\\ (A\rightarrow B),(C\rightarrow D)&\vdash(A\rightarrow B)\rightarrow(A\rightarrow(B\vee D))\\ (A\rightarrow B),(C\rightarrow D)&\vdash(C\rightarrow D)\rightarrow(C\rightarrow(B\vee D))\\ (A\rightarrow B),(C\rightarrow D)&\vdash A\rightarrow(B\vee D)\\ (A\rightarrow B),(C\rightarrow D)&\vdash C\rightarrow(B\vee D)\\ (A\rightarrow B),(C\rightarrow D)&\vdash(C\rightarrow (B\vee D))\rightarrow((A\vee C)\rightarrow(B\vee D))\\ (A\rightarrow B),(C\rightarrow D)&\vdash(A\vee C)\rightarrow(B\vee D)\\ (A\rightarrow B)&\vdash(C\rightarrow D)\rightarrow((A\vee C)\rightarrow(B\vee D))\\ &\vdash(A\rightarrow B)\rightarrow((C\rightarrow D)\rightarrow((A\vee C)\rightarrow(B\vee D)))$
Přičemž prvních 7 řádků jdou axiomy. 8 a 9 odvozen pomocí věty o dedukci, 10-15 jsou pdvozany pomocí Modus ponens, 16 a 17 pomocí věty o dedukci.

Ve druhém případě budu považovat $P(x)\rightarrow P(x)$ za dokázané.
$&\vdash (P(x)\rightarrow\forall xP(x))\rightarrow\exists z(P(z)\rightarrow\forall xP(x))\\ &\vdash P(x)\rightarrow P(x)\\ &\vdash P(x)\rightarrow\forall xP(x)\\ &\vdash\exists z(P(z)\rightarrow\forall xP(x))$
Přičemž první řádek je axiom, třetí je odvozen generalizací a čtvrtý pomocí modus ponens.

Matematické Fórum

#1 02. 01. 2011 14:25

důkaz ve výrokové a predikátové logice

#2 15. 02. 2011 16:47

Re: důkaz ve výrokové a predikátové logice

Zápatí