Funkcje zdaniowe, kwantyfikatory – teoria
Funkcja (forma) zdaniowa zmiennej x, której zakresem zmienności jest przestrzeń X to wyraże-
nie ϕ(x), które staje się zdaniem prawdziwym lub fałszywym po podstawieniu w miejsce x
dowolnego elementu z przestrzeni X.
Zbiory
{x : ϕ(x)}
oraz
{(x
1
, . . . , x
n
) : ϕ(x
1
, . . . , x
n
)}
nazywamy wykresami funkcji zdaniowej ϕ.
Klasyfikacja form zdaniowych jednej zmiennej
Klasa P – formy zdaniowe spełnione przez wszystkie wartości zmiennej.
Klasa F – formy zdaniowe, które nie są spełnione przez żadną wartość zmiennej.
Klasa T – formy zdaniowe spełnione przez niektóre lecz nie wszystkie wartości zmiennej.
ϕ(x)
∼ ϕ(x)
P
F
F
P
T
T
ϕ(x)
ψ(x)
ϕ(x) ∧ ψ(x)
ϕ(x) ∨ ψ(x)
ϕ(x) ⇒ ψ(x)
ϕ(x) ⇔ ψ(x)
P
P
P
P
P
P
P
F
F
P
F
F
P
T
T
P
T
T
F
P
F
P
P
F
F
F
F
F
P
P
F
T
F
T
P
T
T
P
T
P
P
T
T
F
F
T
T
T
T
T
F,T
P,T
P,T
P,F,T
Kwantyfikatory
Jeśli ϕ(x) jest funkcją zdaniową zmiennej x o zakresie zmienności X 6= ∅, to
• dla każdego x należącego do X jest ϕ(x) ≡ ∀
x∈X
ϕ(x),
• istnieje x należące do X takie, że ϕ(x) ≡ ∃
x∈X
ϕ(x).
Warunek konieczny i dostateczny na to, aby zdanie ∀
x∈X
ϕ(x) było prawdziwe można zapisać
w postaci:
∀
x∈X
ϕ(x) jest zdaniem prawdziwym ⇔ {x ∈ X : ϕ(x)} = X.
Warunek konieczny i dostateczny na to, aby zdanie ∃
x∈X
ϕ(x) było prawdziwe można zapisać
w postaci:
∃
x∈X
ϕ(x) jest zdaniem prawdziwym ⇔ {x ∈ X : ϕ(x)} 6= ∅.
Prawa rachunku funkcyjnego
1. ∀
x∈X
ϕ(x) ⇒ ϕ(y), y ∈ X
2. ϕ(y) ⇒ ∃
x∈X
ϕ(x), y ∈ X
3. ∀
x∈X
ϕ(x) ⇒ ∃
x∈X
ϕ(x)
4. Prawa de Morgana
(a) ∼ ∀
x∈X
ϕ(x) ⇔ ∃
x∈X
∼ ϕ(x)
(b) ∼ ∃
x∈X
ϕ(x) ⇔ ∀
x∈X
∼ ϕ(x)
5. ∀
x∈X
[ϕ(x)∧ψ(x)] ⇔ ∀
x∈X
ϕ(x)∧∀
x∈X
ψ(x) – prawo rozdzielności kwantyfikatora ogólnego
względem koniunkcji
6. ∀
x∈X
ϕ(x) ∨ ∀
x∈X
ψ(x) ⇒ ∀
x∈X
[ϕ(x) ∨ ψ(x)]
Uwaga: Kwantyfikator ogólny nie jest rozdzielny względem alternatywy.
7. ∃
x∈X
[ϕ(x) ∨ ψ(x)] ⇔ ∃
x∈X
ϕ(x) ∨ ∃
x∈X
ψ(x) – prawo rozdzielności kwantyfikatora
szczegółowego względem alternatywy
8. ∃
x∈X
[ϕ(x) ∧ ψ(x)] ⇒ ∃
x∈X
ϕ(x) ∧ ∃
x∈X
ψ(x)
Uwaga: Kwantyfikator szczegóły nie jest rozdzielny względem koniunkcji.
9. ∀
x∈X
[ϕ(x) ⇒ ψ(x)] ⇒ [∀
x∈X
ϕ(x) ⇒ ∀
x∈X
ψ(x)] – prawo rozkładania kwantyfikatora
ogólnego
10. ∀
x∈X
[ϕ(x) ⇒ ψ(x)] ⇒ [∃
x∈X
ϕ(x) ⇒ ∃
x∈X
ψ(x)] – prawo rozkładania kwantyfikatora
szczegółowego
11. ∀
x∈X
[ϕ(x) ⇔ ψ(x)] ⇒ [∀
x∈X
ϕ(x) ⇔ ∀
x∈X
ψ(x)]
12. ∀
x∈X
[ϕ(x) ⇔ ψ(x)] ⇒ [∃
x∈X
ϕ(x) ⇔ ∃
x∈X
ψ(x)]
13. Prawa przestawiania kwantyfikatorów
(a) ∀
x∈X
∀
y∈Y
ϕ(x, y) ⇔ ∀
y∈Y
∀
x∈X
ϕ(x, y)
(b) ∃
x∈X
∃
y∈Y
ϕ(x, y) ⇔ ∃
y∈Y
∃
x∈X
ϕ(x, y)
(c) ∃
x∈X
∀
y∈Y
ϕ(x, y) ⇒ ∀
y∈Y
∃
x∈X
ϕ(x, y)
14. Prawa włączania i wyłączania kwantyfikatorów
(a) ∀
x∈X
(ϕ(x) ∨ ψ) ⇔ ∀
x∈X
ϕ(x) ∨ ψ
(b) ∃
x∈X
(ϕ(x) ∨ ψ) ⇔ ∃
x∈X
ϕ(x) ∨ ψ
(c) ∀
x∈X
(ϕ(x) ∧ ψ) ⇔ ∀
x∈X
ϕ(x) ∧ ψ
(d) ∃
x∈X
(ϕ(x) ∧ ψ) ⇔ ∃
x∈X
ϕ(x) ∧ ψ
(e) ∀
x∈X
(ϕ(x) ⇒ ψ) ⇔ ∃
x∈X
ϕ(x) ⇒ ψ
(f) ∃
x∈X
(ϕ(x) ⇒ ψ) ⇔ ∀
x∈X
ϕ(x) ⇒ ψ
(g) ∀
x∈X
(ψ ⇒ ϕ(x)) ⇔ (ψ ⇒ ∀
x∈X
ϕ(x))
(h) ∃
x∈X
(ψ ⇒ ϕ(x)) ⇔ (ψ ⇒ ∃
x∈X
ϕ(x))
Wybrane reguły rachunku kwantyfikatorów
1.
∀
x
ϕ(x)
ϕ(y)
– reguła opuszczania kwantyfikatora ogólnego
2.
ϕ(y)
∃
x
ϕ(x)
– reguła dołączania kwantyfikatora szczegółowego
3.
∀
x
[ϕ(x) ⇔ ψ(x)]
∀
x
ϕ(x) ⇔ ∀
x
ψ(x)
4.
∀
x
[ϕ(x) ⇔ ψ(x)]
∃
x
ϕ(x) ⇔ ∃
x
ψ(x)
5.
ϕ ⇒ ψ(x)
ϕ ⇒ ∀
x
ψ(x)
– reguła dołączania kwantyfikatora ogólnego
6.
ϕ(x) ⇒ ψ
∃
x
ϕ(x) ⇒ ψ
– reguła dołączania kwantyfikatora szczegółowego
7.
ϕ ⇒ ∀
x
ψ(x)
ϕ ⇒ ψ(x)
– reguła eliminacji kwantyfikatora ogólnego
8.
∃
x
ϕ(x) ⇒ ψ
ϕ(x) ⇒ ψ
– reguła eliminacji kwantyfikatora szczegółowego
Kwantyfikatory o zakresie ograniczonym przez funkcję zdaniową
Kwantyfikatory
∀
ψ(x)
ϕ(x)
oraz
∃
ψ(x)
ϕ(x)
nazywamy kwantyfikatorami o zakresie ograniczonym przez funkcję zdaniową ψ(x).
Następujące prawa pozwalają przejść do wyrażeń, które nie zawierają kwantyfikatorów o za-
kresie ograniczonym:
• ∀
ψ(x)
ϕ(x) ⇔ ∀
x
[ψ(x) ⇒ ϕ(x)]
• ∃
ψ(x)
ϕ(x) ⇔ ∃
x
[ψ(x) ∧ ϕ(x)]