Matematyka.pl

Jak zapisać poniższe formuły korzystając z \(\displaystyle{ =, \le , +, \cdot}\), kwantyfikatorów i spójników logicznych?
Brak stałych jest dosyć dużym utrudnieniem.
Formuły dotyczą liczb naturalnych.
1. Nie istnieje największa liczba pierwsza.
2. Każda liczba nieparzysta większa od \(\displaystyle{ 3}\) jest sumą dwóch liczb pierwszych.
3. Liczby \(\displaystyle{ x}\) i \(\displaystyle{ y}\) mają takie same dzielniki pierwsze.

implicationelim pisze:Jak zapisać poniższe formuły korzystając z =, <= , +, *, kwantyfikatorów i spójników logicznych? (...)
1. Nie istnieje największa liczba pierwsza.

Dla czytelności, na początku zapiszę formułę \(\displaystyle{ p(x)}\), która jest prawdziwa wtedy i tylko wtedy gdy \(\displaystyle{ x}\) jest liczbą pierwszą:

\(\displaystyle{ \forall y,z (x = y \cdot z \Rightarrow (y = 1 \vee y = x))}\)

Teraz zdanie: nie istnieje największa liczba pierwsza to:

\(\displaystyle{ \forall x \exists t ( p(x) \Rightarrow ( p(t) \wedge x < t))}\)

(dla każdej liczby pierwszej istnieje liczba pierwsza większa od niej)

2. Każda liczba nieparzysta większa od 3 jest sumą dwóch liczb pierwszych.

To się robi tak samo, trzeba tylko wiedzieć jak zapisać, że liczba jest nieparzysta:

x jest nieparzysta wtw. \(\displaystyle{ \sim \exists t (x = 2 \cdot t)}\)

.

lukas1929 pisze:Dla czytelności, na początku zapiszę formułę \(\displaystyle{ p(x)}\), która jest prawdziwa wtedy i tylko wtedy gdy \(\displaystyle{ x}\) jest liczbą pierwszą:

\(\displaystyle{ \forall y,z (x = y \cdot z \Rightarrow (y = 1 \vee y = x))}\)

Niedobrze, użyłeś symbolu stałej \(\displaystyle{ 1}\), który jest niedopuszczalny.

lukas1929 pisze:Teraz zdanie: nie istnieje największa liczba pierwsza to:

\(\displaystyle{ \forall x \exists t ( p(x) \Rightarrow ( p(t) \wedge x < t))}\)

(dla każdej liczby pierwszej istnieje liczba pierwsza większa od niej)

Pomijając niezbyt elegancką (choć poprawną) składnię, nieco lepiej jest formalizować zdanie

"Dla każdej liczby naturalnej istnieje liczba pierwsza większa od niej."

W tym przypadku merytorycznie nie ma różnicy, ale w innych sytuacjach z podobnym poleceniem druga wersja jest bezpieczniejsza.

lukas1929 pisze:x jest nieparzysta wtw. \(\displaystyle{ \sim \exists t (x = 2 \cdot t)}\).

I znów niedozwolona stała.

JK

Faktycznie, nie zauważyłem, że w zadaniu nie dopuszczają użycia stałej.

Tą stałą również można zdefiniować:

\(\displaystyle{ jeden(x) = (\forall q (x \cdot q = q))}\)

i wtedy całe wyrażenie przyjmuje postać:

\(\displaystyle{ \forall y,z,k ((x = y \cdot z \wedge jeden(k) )\Rightarrow (y = k \vee y = x))}\)

natomiast w funkcji dla liczby nieparzystej dwa można uzyskać z jeden ponieważ symbol \(\displaystyle{ +}\) jest dopuszczalny.

.

lukas1929 pisze:\(\displaystyle{ \forall y,z,k ((x = y \cdot z \wedge jeden(k) )\Rightarrow (y = k \vee y = x)}\)

Prościej byłoby

\(\displaystyle{ \forall y,z (x = y \cdot z\Rightarrow jeden(y) \vee y = x)}\)

JK