Matematyka.pl

Które z poniższych formuł zdaniowych są tautologiami rachunku predykatów?

a) \(\displaystyle{ \exists x \exists y: f \Rightarrow \forall x \exists y: f}\).
b) \(\displaystyle{ \neg \exists x : \neg f \Rightarrow \forall x : f}\).
c) \(\displaystyle{ \exists x : \neg f \Rightarrow \neg \forall x : f}\).
d)\(\displaystyle{ \forall x \exists y (f \wedge g) \Leftrightarrow \exists y \forall x : (f \wedge g)}\).

Jak to zrobić? Może mi ktoś pomóc?

Zrozumieć, co znaczą te znaczki.

Np. b) i c) to prosty wniosek z praw de Morgana.

Natomiast w a) i d) nietrudno podać kontrprzykłady.

JK

No dobra to spróbuję podać kontrprzykład do a):
Jeśli prawdą jest, że istnieje \(\displaystyle{ x \in \RR}\) i \(\displaystyle{ y \in \RR}\), że \(\displaystyle{ x=y^2}\) (na przykład \(\displaystyle{ x=4,y=2)}\), to nie jest prawdą, że dla każdego \(\displaystyle{ x \in \RR}\), istnieje \(\displaystyle{ y \in \RR}\), że \(\displaystyle{ x=y^2}\) (na przykład \(\displaystyle{ x=-4}\), wówczas nie istnieje taki \(\displaystyle{ y}\)).

Dobrze?

A jak uzasadnić to b) i c) z praw de Morgana?

Możesz pokazać ten przykład b) jak zrobić z praw de Morgana, bo za bardzo nie wiem. Nie bardzo rozumiem schemat tego dowodu.

max123321 pisze: 25 mar 2025, o 13:43 No dobra to spróbuję podać kontrprzykład do a):
Jeśli prawdą jest, że istnieje \(\displaystyle{ x \in \RR}\) i \(\displaystyle{ y \in \RR}\), że \(\displaystyle{ x=y^2}\) (na przykład \(\displaystyle{ x=4,y=2)}\), to nie jest prawdą, że dla każdego \(\displaystyle{ x \in \RR}\), istnieje \(\displaystyle{ y \in \RR}\), że \(\displaystyle{ x=y^2}\) (na przykład \(\displaystyle{ x=-4}\), wówczas nie istnieje taki \(\displaystyle{ y}\)).

To jest dobry kontrprzykład źle sprzedany.

Kontrprzykładem jest formuła \(\displaystyle{ f(x,y)=(x=y^2)}\). Ale jest nim nie dlatego, że jeśli prawdą jest \(\displaystyle{ \exists x \exists y: f}\), to nie jest prawdą, że \(\displaystyle{ \forall x \exists y: f}\), tylko dlatego, że prawdą jest \(\displaystyle{ \exists x \exists y: f}\) i nie jest prawdą, że \(\displaystyle{ \forall x \exists y: f}\).

Różnica pomiędzy "jeśli..., to" oraz "i" jest bardzo istotna.

max123321 pisze: 25 mar 2025, o 14:15 Możesz pokazać ten przykład b) jak zrobić z praw de Morgana, bo za bardzo nie wiem. Nie bardzo rozumiem schemat tego dowodu.

A znasz prawa de Morgana dla kwantyfikatorów?

JK

No tak, racja, tam pomieszałem.

Tak, znam te prawa de Morgana:
\(\displaystyle{ \neg (\forall x: p(x)) \Leftrightarrow (\exists x: \neg p(x))}\)
\(\displaystyle{ \neg (\exists x: p(x)) \Leftrightarrow (\forall x: \neg p(x))}\),

gdzie \(\displaystyle{ p}\) to dowolne zdanie, zależne od \(\displaystyle{ x}\).

No dobra, ale jak się teraz zabrać za uzasadnienie b)?

Chociaż jak tak teraz myślę to może, można zrobić tak:
Wziąć \(\displaystyle{ p= \neg f}\) bo wówczas \(\displaystyle{ \neg p =f}\). Teraz w prawie de Morgana tym drugim mamy równoważność, więc tym bardziej zachodzi implikacja po podstawieniu tego \(\displaystyle{ p=\neg f}\) z lewa na prawo.

O to chodzi?

Tak.

JK