http://www-users.mat.umk.pl/~pjedrzej/matwyz.html

1

Formy zdaniowe

Forma zdaniowa ϕ(x) określona w zbiorze X to wyrażenie, które

jest zdaniem, jeśli za x wstawimy dowolny element zbioru X.

Zbiór X nazywamy zakresem formy zdaniowej ϕ(x).

2

Przykłady.

• ϕ(x) = „ x

2

< 1” , gdzie x ∈ R,

ϕ(x) jest zdaniem:

– prawdziwym dla x ∈ (−1, 1),

– fałszywym dla x ∈ (−∞, −1] ∪ [1, +∞);

• ϕ(x) = „ x

2

> 0”, gdzie x ∈ R,

ϕ(x) jest zdaniem prawdziwym dla wszystkich x ∈ R;

3

• ϕ(n) = „ n | 6” (n dzieli 6), gdzie n ∈ N

1

,

ϕ(n) jest zdaniem:

– prawdziwym dla n = 1, 2, 3, 6

– fałszywym dla pozostałych n;

• ϕ(n) = „ n = n + 1” , gdzie n ∈ Z,

ϕ(n) jest zdaniem fałszywym dla każdego n ∈ Z.

4

Uwaga.

Forma zdaniowa określona w zbiorze X pozwala każ-

demu elementowi tego zbioru przyporządkować zdanie. Możemy

więc ją nazwać funkcją zdaniową.

Pytanie.

Co jest dziedziną, a co zbiorem wartości tej funkcji?

5

Kwantyfikatory

Jeśli ϕ(x) jest formą zdaniową określoną w zbiorze X, to możemy

rozważyć następujące dwa zdania.

1. Zdanie

„Dla każdego x ∈ X (zachodzi) ϕ(x)”,

które zapisujemy symbolicznie

∀

x∈X

ϕ(x).

6

2. Zdanie

„Istnieje x ∈ X takie, że ϕ(x)”,

które zapisujemy

∃

x∈X

ϕ(x).

Zdanie

∃

x∈X

ϕ(x) jest prawdziwe dokładnie wtedy, gdy ϕ(x) jest

zdaniem prawdziwym dla co najmniej jednego x ∈ X.

7

Przykłady:

• ∀

x∈R

x

2

< 1 – zdanie fałszywe,

∃

x∈R

x

2

< 1 – zdanie prawdziwe,

• ∀

x∈R

x

2

> 0 – zdanie prawdziwe,

∃

x∈R

x

2

> 0 – zdanie prawdziwe,

8

• ∀

n∈N

1

n | 6 – zdanie fałszywe,

∃

n∈N

1

n | 6 – zdanie prawdziwe,

• ∀

n∈Z

n = n + 1 – zdanie fałszywe,

∃

n∈Z

n = n + 1 – zdanie fałszywe.

9

Zauważmy, że:

– jeśli ϕ(x) jest zdaniem prawdziwym dla wszystkich x ∈ X, to

zdania

∀

x∈X

ϕ(x) i ∃

x∈X

ϕ(x) są prawdziwe,

– jeśli ϕ(x) jest zdaniem fałszywym dla wszystkich x ∈ X, to

zdania

∀

x∈X

ϕ(x) i ∃

x∈X

ϕ(x) są fałszywe,

– jeśli ϕ(x) jest zdaniem prawdziwym dla pewnych elementów

zbioru X, a fałszywym dla innych elementów tego zbioru, to

zdanie

∀

x∈X

ϕ(x) jest fałszywe, a zdanie ∃

x∈X

ϕ(x) jest prawdzi-

we.

10

Symbol „

∀” nazywamy kwantyfikatorem ogólnym, a symbol „ ∃”

nazywamy kwantyfikatorem szczegółowym.

∀

– for

A

ll

∃

–

E

xists

Jeśli zakres formy zdaniowej (zbiór X) jest jasno określony, to

zamiast

∀

x∈X

ϕ(x) i ∃

x∈X

ϕ(x) możemy pisać: ∀

x

ϕ(x), ∃

x

ϕ(x).

11

W matematyce elementarnej popularne są polskie symbole kwan-

tyfikatorów:

V

– kwantyfikator ogólny (zamiast

∀),

W

– kwantyfikator szczegółowy (zamiast

∃).

Kwantyfikatory te są uogólnieniami spójników logicznych, gdyż

w przypadku zbioru skończonego X mamy:

^

x∈{x

1

,...,x

n

}

ϕ(x) ⇔ ϕ(x

1

)

∧ . . . ∧ ϕ(x

n

),

_

x∈{x

1

,...,x

n

}

ϕ(x) ⇔ ϕ(x

1

)

∨ . . . ∨ ϕ(x

n

).

12

Formy zdaniowe wielu zmiennych

Możemy rozważać formy zdaniowe większej liczby zmiennych, np.

ϕ(x, y, z), gdzie x ∈ X, y ∈ Y , z ∈ Z lub ϕ(x, y), gdzie x, y ∈ X.

Przykłady:

• „ x < y”, gdzie x, y ∈ N;

• „ x · y = 0”, gdzie x ∈ Z, y ∈ R;

• „ A ∈ k”, gdzie A ∈ zbiór punktów, k ∈ zbiór prostych;

• „Punkt A leży między punktami B i C”.

13

Rozważmy formę zdaniową ϕ(x, y) zmiennych x, y ∈ X.

Zdanie

∀

x∈X

∀

y∈X

ϕ(x, y)

oznacza, że dla każdego x ∈ X zachodzi to, że dla każdego y ∈ X

zachodzi ϕ(x, y). Prościej:

„dla dowolnych x, y ∈ X zachodzi ϕ(x, y)”,

co zapisujemy używając jednego symbolu kwantyfikatora:

∀

x,y∈X

ϕ(x, y).

14

Zdanie

∃

x∈X

∃

y∈X

ϕ(x, y)

oznacza, że istnieje x ∈ X, dla którego istnieje y ∈ X taki, że

zachodzi ϕ(x, y). Prościej:

„istnieją x, y ∈ X takie, że ϕ(x, y)”,

co też zapisujemy używając jednego symbolu kwantyfikatora:

∃

x,y∈X

ϕ(x, y).

15

Niech teraz ϕ(x

1

, . . . , x

n

) będzie formą zdaniową zmiennych x

1

,

. . ., x

n

, gdzie x

1

∈ X

1

, . . ., x

n

∈ X

n

.

Zdanie

„Dla dowolnych x

1

∈ X

1

, . . ., x

n

∈ X

n

(zachodzi) ϕ(x

1

, . . . , x

n

)”

zapisujemy

∀

x

1

∈X

1

,...,x

n

∈X

n

ϕ(x

1

, . . . , x

n

).

Zdanie

„Istnieją x

1

∈ X

1

, . . ., x

n

∈ X

n

takie, że ϕ(x

1

, . . . , x

n

)”,

zapisujemy

∃

x

1

∈X

1

,...,x

n

∈X

n

ϕ(x

1

, . . . , x

n

).

16

Przykład.

Które z następujących zdań są prawdziwe, a które

fałszywe:

∀

x,y∈Z

x < y,

∀

x,y∈R

x · y = y · x,

∃

x∈N

∃

y∈Z

x < y?

17

Niech ϕ(x, y) będzie formą zdaniową zmiennych x ∈ X, y ∈ Y .

Zdanie

∃

x∈X

∀

y∈Y

ϕ(x, y)

oznacza, że istnieje x ∈ X takie, że ϕ(x, y) zachodzi dla każdego

y ∈ Y .

Zdanie

∀

x∈X

∃

y∈Y

ϕ(x, y)

oznacza, że dla każdego x ∈ X istnieje takie y ∈ Y , że zachodzi

ϕ(x, y).

To nie jest to samo!

18

Przykład.

Które z następujących zdań są prawdziwe, a które

fałszywe:

∀

x∈Z

∃

y∈Z

x < y,

∃

x∈Z

∀

y∈Z

x < y,

∃

x∈Z

∀

y∈Z

x · y = 0?

19

Ćwiczenie. Utwórz kilka ciekawych zdań z użyciem kwantyfika-

torów

∀, ∃ i form zdaniowych:

x < y,

x 6 y, x · y = 0, x · y = 1,

gdzie x, y przebiegają zbiory: N, N

1

, Z, Q, R.

Określ prawdziwość utworzonych zdań.

20

Przykłady użycia kwantyfikatorów

• a ∈ Z, a jest liczbą parzystą:

∃

k∈Z

a = 2k.

• a, b ∈ Z, a jest podzielne przez b:

∃

k∈Z

a = k · b.

• p ∈ N

1

, p jest liczbą pierwszą:

(p 6= 1) ∧ ∀

a∈N

1

(a | p ⇒ a = 1 ∨ a = p).

21

• b ∈ R, A ⊂ R, b jest ograniczeniem z góry zbioru A:

∀

a∈A

a 6 b.

• Między dowolnymi dwiema różnymi liczbami rzeczywistymi

istnieje liczba wymierna:

∀

x∈R

∀

y∈R

(x 6= y ⇒ ∃

w∈Q

((x < w ∧ w < y) ∨ (y < w ∧ w < x))).

• Od pewnego miejsca wszystkie wyrazy ciągu (x

n

) są dodat-

nie:

∃

N

∀

n>N

x

n

> 0.

• Zasada indukcji matematycznej:

(T (0) ∧ ∀

n∈N

(T (n) ⇒ T (n + 1))) ⇒ ∀

n∈N

T (n).

22

Prawa rachunku kwantyfikatorów

Prawo rachunku kwantyfikatorów to wyrażenie utworzone po-

prawnie z symboli kwantyfikatorów, funkcji zdaniowych i spój-

ników logicznych, które jest zdaniem prawdziwym dla dowolnej

funkcji zdaniowej i dowolnych wartości zmiennych.

Prawa de Morgana dla kwantyfikatorów:

∼ (∀

x∈X

ϕ(x)) ⇔ ∃

x∈X

(

∼ ϕ(x)),

∼ (∃

x∈X

ϕ(x)) ⇔ ∀

x∈X

(

∼ ϕ(x)).

23

Przykład. Liczba b nie jest ograniczeniem z góry zbioru A:

∼ (∀

a∈A

a 6 b) ⇔ ∃

a∈A

∼ (a 6 b) ⇔ ∃

a∈A

a > b.

Inne prawa rachunku kwantyfikatorów:

(

∀

x∈X

ϕ(x)) ⇒ (∃

x∈X

ϕ(x)),

(

∃

x∈X

∀

y∈Y

ϕ(x, y)) ⇒ (∀

y∈Y

∃

x∈X

ϕ(x, y)).

24

Metody dowodzenia twierdzeń

Metoda dowodu „nie wprost” jest oparta na tautologii

(p ⇒ q) ⇔ (∼ q ⇒∼ p).

Zadanie. Dane są liczby całkowite a i b. Wykaż, że jeśli a · b jest

liczbą parzystą, to a jest parzyste lub b jest parzyste.

25

Metoda dowodu „przez sprzeczność” jest oparta na tautologii

(p ⇒ q) ⇔∼ (p∧ ∼ q).

Zadanie. Dane są liczby rzeczywiste x, y. Wykaż, że jeżeli x

2

+

y

2

< 1, to x + y <

√

2.

26