Przejdź do zawartości

Język zdaniowy

Z Wikipedii, wolnej encyklopedii

Język zdaniowy – trójka gdzie:

jest zbiorem nieskończonym,
zbiorem rozłącznym z

Elementy zbioru są nazywane zmiennymi zdaniowymi, elementy zbioru spójnikami języka a jego sygnaturą.

Skończone ciągi elementów zbioru są nazywane napisami języka

Najmniejszy (w sensie inkluzji) spośród zbiorów napisów zbiór spełniający warunki:

(jednoelementowe napisy złożone ze zmiennych są w
(1)
(2)

nazywany jest zbiorem formuł języka i oznaczany symbolem

O zbiorach spełniających warunki (1) i (2) mówi się, że są domknięte na budowę formuł języka .

Innymi słowy zbiór jest najmniejszym zbiorem napisów domkniętym na budowę formuł języka

Przykład

[edytuj | edytuj kod]

Niech

gdzie

i niech

Wówczas jest formułą języka ale i nie są.

Język arytmetyki Peana

[edytuj | edytuj kod]

Język termów arytmetyki Peana

[edytuj | edytuj kod]

Niech

Język

nazywa się językiem termów arytmetyki Peana. Formuły tego języka nazywa się termami arytmetyki Peana. Zbiór wszystkich termów arytmetyki Peana oznaczany będzie

Dla wygody czasem zamiast pisze się zamiast pisze się i zamiast pisze się

Definiujemy indukcyjnie ciąg numerałów:

Język formuł arytmetyki PA

[edytuj | edytuj kod]

Formułami atomowymi arytmetyki Peana nazywamy napisy postaci oraz gdzie

Zwyczajowo zamiast pisze się zamiast pisze się

Zbiór formuł atomowych języka PA, oznaczymy

Przykład:
formułami atomowymi języka PA są
(Zero jest najmniejsze)
(Aksjomaty dla dodawania)
(Aksjomaty dla mnożenia)
(Przemienność dodawania i mnożenia)
(Łączność dodawania i mnożenia)
(2+3=5)
(2*3=6)

Formułami arytmetyki Peana nazywamy formuły języka

gdzie

oraz gdzie jest wzbogaceniem sygnatury do zbioru dla którego

Zamiast pisać pisze się zazwyczaj zamiast zaś pisać pisze się zazwyczaj

Przykład:
formułami języka PA są

Lemat (o kształcie formuł)

[edytuj | edytuj kod]

Niech będzie językiem zdaniowym.

Wówczas dla każdej formuły tego języka zachodzi jeden z warunków

(3)
dla pewnego oraz
(4)

Dla dowodu tego lematu należy rozważyć zbiór formuł spełniających warunki (3) i (4) powyżej, a następnie pokazać, że jest on domknięty na budowę formuł.

Lemat (o jednoznaczności budowy)

[edytuj | edytuj kod]

Niech będzie językiem zdaniowym, niech będą formułami i niech będą takie, że

Wówczas oraz

Podformuły

[edytuj | edytuj kod]

Lematy o kształcie formuł i jednoznaczności budowy pozwalają na indukcyjne zdefiniowanie pojęcia podformuły danej formuły oraz podstawienia w formule innej formuły w miejsce zmiennej:

Zbiorem podformuł formuły nazywamy zbiór zdefiniowany następująco:

Zmiennymi formuły nazywamy elementy zbioru

Przykład

[edytuj | edytuj kod]

Podstawienie w formule

[edytuj | edytuj kod]

Podstawieniem w formule formuły w miejsce zmiennej nazywamy formułę:

Zachodzi Jeśli to

Przykład

[edytuj | edytuj kod]

Jednoczesne podstawienie kilku formuł

[edytuj | edytuj kod]

W wielu wypadkach przydaje się umiejętność jednoczesnego podstawienia kilku formuł w miejsce kilku zmiennych:

Podstawieniem w formule formuł w miejsce zmiennych nazywamy formułę:

Wynik podstawienia nie zależy od kolejności:

dla dowolnej permutacji zbioru

Jeśli i to:

Przykład

[edytuj | edytuj kod]

Algebra formuł

[edytuj | edytuj kod]

Język zdaniowy wyznacza dość ważną algebrę sygnatury

Algebrą formuł języka nazywamy algebrę sygnatury tego języka której uniwersum jest i w której

Algebra języka jest algebrą wolną z jako zbiorem wolnych generatorów w klasie algebr jej sygnatury:

Dla dowolnej algebry sygnatury języka oraz dowolnego odwzorowania istnieje jedyny homomorfizm rozszerzający
W przypadku, gdy język jest ustalony w danym kontekście homomorfizm ten oznaczamy po prostu symbolem

Zauważmy, że gdzie dane jest wzorem:

Co więcej, jeśli oraz to:

Niech będzie zbiorem formuł języka Wówczas

Reguła podstawiania

[edytuj | edytuj kod]

Regułą podstawiania w języku jest reguła:

W przypadku, gdy język jest ustalony, indeks górny jest pomijany.

Zobacz też

[edytuj | edytuj kod]

Bibliografia

[edytuj | edytuj kod]
  • Pogorzelski Witold, Elementarny słownik logiki formalnej, wyd. Filii UW, Białystok 1992.
  • Pogorzelski Witold, Klasyczny rachunek zdań, Warszawa 1975.
  • Hunter Geoffrey, Metalogika, Warszawa, PWN 1982.
  • Shoenfield Joseph R., Mathematical Logic, Addison-Wesley, 1967.