Wrocław, 13 grudnia 2012
Wydział Informatyki i Zarządzania, rok I
Logika dla informatyków
Zadania  lista 10
1. Niech f, g, h będą symbolami funkcyjnymi, p, q  symbolami predykatów, x, y, z  zmienny-
mi indywiduowymi. Wskazać wolne i związane wystąpienia zmiennych indywiduowych w
formułach:
a) "�x �� "�y �� p(f(x, y), z) Ł� "�x �� q(x, z, h(x, y))
b) ("�x �� $� y �� q(x, z) �� p(h(x, y)) �� p(f(x, y), z)
c) "�x �� p(h(x), z) �� ($�z �� ($�y �� q(f(h(x), z) Ł�"�z �� p(z, y) �� q(x, y))
2. Zdefiniować funkcję, która dla dowolnej formuły a� rachunku kwantyfikatorów określa zbiór
wszystkich zmiennych indywiduowych, które w formule a� mają:
a) wystąpienia związane,
b) parzystą liczbę wystąpień wolnych,
c) jednocześnie wystąpienia wolne i wystąpienia związane,
d) dokładnie taką samą liczbę wystąpień wolnych jak liczbę wystąpień związanych.
3. Dana jest sygnatura Sig = języka rachunku kwantyfikatorów, w której
F =def {f0} �� {f1, g1} �� {f2, g2, h2} jest zbiorem symboli funkcyjnych,
P =def {p0} �� {p1, q1} �� {p2, q2} jest zbiorem symboli predykatów,
zaś dolny indeks wskazuje liczbę argumentów. Podać gramatykę definiującą zbiór termów i
gramatykę definiującą zbiór formuł języka o podanej sygnaturze.
4. Niech {=, Ł�, <� } będzie zbiorem symboli predykatów, oraz {+, *, /}  zbiorem symboli funk-
cyjnych określonych na liczbach naturalnych. Dla symboli tych przyjmujemy standardową
interpretacją arytmetyczną. Korzystając z tego zestawu symboli oraz z symboli stałych licz-
bowych zapisać formuły reprezentujące następujące wypowiedzi:
a) x jest liczbą podzielną przez ustaloną liczbę n > 0,
b) x jest sumą kwadratów dwu liczb naturalnych,
c) x jest liczbą pierwszą,
d) x nie jest liczbą pierwszą,
e) x jest najmniejszą wspólną wielokrotnością liczb y i z,
f) x przy dzieleniu przez 4 daje resztę 1 lub 2,
g) każda liczba przy dzieleniu przez inną liczbę daje resztę 0 lub 1,
h) każda liczba parzysta większa od 3 jest sumą dwu liczb pierwszych,
i) każde trzy liczby mają największy wspólny dzielnik,
j) nie istnieje największa liczba naturalna.
Zapisać zaprzeczenia powyższych formuł w taki sposób, aby nie zaczynały się od negacji.