Egzistencijalni kvantifikator i konjunkcija

PostPoslato: Subota, 10. Oktobar 2020, 21:28
od drmm
Pozdrav,

Imam jedan problem. Naime poznato je da implikacija
[dispmath](\exists x)(P(x))\land(\exists x)(Q(x))\;\Longrightarrow\;(\exists x)(P(x)\land Q(x))[/dispmath] u opštem slučaju ne važi, ali se to dokazuje pretežno davanjem kontraprimera. Zanima me da li postoji 'formalan' generalizovan dokaz koji pokazuje da ova implikacija nije tačna. Više puta sam dosta dugo razmišljao o ovom problemu (ili problemima koji u osnovi sadrže ovu implikaciju) ali nisam uspeo da dodjem do nekog napretka. Zaista nemam ni ideju koji bi prvi korak bio. Hvala unapred na odgovorima.

Re: Egzistencijalni kvantifikator i konjunkcija

PostPoslato: Nedelja, 25. Oktobar 2020, 11:57
od ubavic
Davanje kontraprimera je sasvim validan dokaz da navedena formula nije tautologija. Formalno, to se radi uz pomoć modela.
E sad, ti pitaš za "'formalan' generalizovan dokaz", pa mi se čini da ciljaš na dokaze u formalnim sistemima, kao što je na primer prirodna dedukcija. U tom slučaju ne možemo ništa više reći. Predikatska logika je konzistentna pa svaka njena teorema mora biti tačna pri proizvoljnoj interpretaciji. Međutim, kao što i sam znaš, postoje kontraprimeri (tj. kontramodeli) za navedenu formulu, ali i kontraprimeri za negaciju te formule. Tako da se formula [inlmath](\exists x)(P(x))\land(\exists x)(Q(x))\;\Longrightarrow\;(\exists x)(P(x)\land Q(x))[/inlmath] ne može dokazati kao ni njena negacija.

Re: Egzistencijalni kvantifikator i konjunkcija

PostPoslato: Nedelja, 25. Oktobar 2020, 13:34
od drmm
@ubavic Hvala puno na odgovoru!