Logika i teoria mnogości – Wykład 1

1

Logika klasyczna to nauka, która ustala reguły badania prawdziwości

stwierdzeń oraz reguły dowodzenia twierdzeń.

Rachunek zdań

Def.1. Podstawowe pojęcie to zdanie, czyli stwierdzenie, które ma jednoznacznie

określoną wartość logiczną: jest albo prawdziwe albo fałszywe.

Stosujemy wartościowanie – czyli przypisanie wartości logicznej zdaniu p:

w(p) = 1 gdy p jest zdaniem prawdziwym, w(p) = 0 gdy p jest zdaniem fałszywym.

W klasycznym rachunku zdań innych możliwości nie ma.

Ze zdań prostych tworzymy zdania złożone przy użyciu spójników logicznych

(funktorów). Najbardziej znane funktory:

 (~) negacja (jednoargumentowy),

dwuargumentowe:

 - koniunkcja,  - alternatywa,  - implikacja,  -

równoważność.

Def.2. Zdanie logiczne nazywamy tautologią, jeśli jest zawsze prawdziwe,

niezależnie od wartości logicznych zmiennych zdaniowych (zdań składowych) w

nim występujących.

Def.3. Zdania logiczne Φ i Ψ są równoważne, jeśli zdanie Φ

 Ψ jest tautologią.

Ważniejsze prawa rachunku zdań

•

p

p

¬¬

⇔

(prawo podwójnego przeczenia)

•

p

p

¬

∨

(prawo wyłączonego środka)

•

)

(

p

p

¬

∧

¬

(prawo sprzeczności)

•

)

(

)

(

)

(

)

(

q

p

q

p

q

p

q

p

¬

∧

¬

⇔

∨

¬

¬

∨

¬

⇔

∧

¬

(prawa de Morgana)

•

łączność alternatywy i łączność koniunkcji

•

przemienność alternatywy oraz koniunkcji

•

)

(

)

(

)

(

r

q

r

p

r

q

p

∧

∨

∧

⇔

∧

∨

(rozdzielność koniunkcji względem

alternatywy)

•

)

(

)

(

)

(

r

q

r

p

r

q

p

∨

∧

∨

⇔

∨

∧

( rozdzielność alternatywy względem

koniunkcji)

•

[

]

)

(

)

(

)

(

r

p

r

q

q

p

⇒

⇒

⇒

∧

⇒

( prawo przechodniości implikacji)

•

))

(

)

((

)

(

p

q

q

p

q

p

⇒

∧

⇒

⇔

⇔

(prawo eliminacji równoważności)

Logika i teoria mnogości – Wykład 1

2

Powyższe prawa są wykorzystywane przy dowodzeniu twierdzeń.

W matematyce często spotykamy twierdzenia postaci:

q

p

⇒

.

Def.4. Jeśli prawdziwa jest implikacja:

q

p

⇒

, to zdanie q nazywamy warunkiem

koniecznym zdania p, zaś zdanie p nazywamy warunkiem wystarczającym zdania q.

Funkcje zdaniowe

Def.5. Funkcja zdaniowa jednej zmiennej, to wyrażenie

∅

≠

∈

X

x

x),

(

ϕ

, które

staje się zdaniem (prawdziwym lub fałszywym), gdy za zmienną x wstawimy

elementy zbioru X. Zbiór X nazywamy zakresem zmienności funkcji φ. Mówimy, że

x

0

X spełnia funkcję zdaniową

)

(x

ϕ

, jeśli

)

(

0

x

ϕ

jest zdaniem prawdziwym. Zbiór

elementów spełniających funkcję zdaniową oznaczamy

)

(

:

{

)}

(

:

{

x

X

x

x

X

x

ϕ

ϕ

∈

=

∈

jest zdaniem prawdziwym}.

Kwantyfikatory

Niech

)

(x

ϕ

będzie funkcją zdaniową zmiennej x

X, zakładamy, że X.

Def.6. Kwantyfikator ogólny (uniwersalny) jest oznaczany symbolem

.

Napis

)

(

)

(

x

X

x

ϕ

∈

∀

- czytamy: dla każdego x należącego do X zachodzi

)

(x

ϕ

.

Uwaga:

)

(

)

(

x

X

x

ϕ

∈

∀



)}

(

:

{

x

X

x

ϕ

∈

= X.

Def.7. Kwantyfikator szczegółowy (egzystencjalny) jest oznaczany symbolem

.

Napis

)

(

)

(

x

X

x

ϕ

∈

∃

- czytamy: istnieje x ze zbioru X spełniający formułę

)

(x

ϕ

.

Uwaga:

)

(

)

(

x

X

x

ϕ

∈

∃



∅

≠

∈

)}

(

:

{

x

X

x

ϕ

.

Uwaga: Kwantyfikator

 () jest uogólnieniem spójnika koniunkcji, zaś

kwantyfikator

 () jest uogólnieniem spójnika alternatywy.

Def. 8. Zakresem kwantyfikatora nazywamy zakres zmiennej funkcji zdaniowej,

której on dotyczy. Mówimy, że kwantyfikatory

)

(

X

x

∈

∀

i

)

(

X

x

∈

∃

wiążą zmienną

x. Zmienną x w wyrażeniu nazywamy związaną, jeśli wiąże ją jakiś kwantyfikator.

Zmienną, która nie jest związana, nazywamy zmienną wolną.

Logika i teoria mnogości – Wykład 1

3

Często zdarza się, że wybieramy zmienne tylko z pewnego podzbioru zakresu

kwantyfikatora. W takiej sytuacji wygodnie jest korzystać z kwantyfikatorów

ograniczonych (zrelatywizowanych).

Def.9. Niech

)

(x

ϕ

będzie funkcją zdaniową zmiennej x

X i niech AX.

Kwantyfikatory ograniczone do zbioru A definiujemy następująco:

•

))

(

(

)

(

)

(

x

A

x

x

x

A

x

ϕ

ϕ

⇒

∈

∀

⇔

∈

∀

•

))

(

(

)

(

)

(

x

A

x

x

x

A

x

ϕ

ϕ

∧

∈

∃

⇔

∈

∃

.

Prawa rachunku kwantyfikatorów

Def.10. Zdanie (zapisane z użyciem kwantyfikatorów) nazywamy prawem rachunku

kwantyfikatorów, gdy jest prawdziwe dla dowolnej interpretacji występujących w

nim symboli funkcji zdaniowych.

Tw. 1. Niech

)

(

),

(

x

x

ψ

ϕ

- funkcje zdaniowe o zakresie zmiennej x

X≠Ø. Wtedy:

1.

),

(

)

(

x

x

x

x

ϕ

ϕ

∃

⇒

∀

2.

))

(

(

)

(

)

(

))

(

(

)

(

)

(

x

x

x

x

x

x

x

x

ϕ

ϕ

ϕ

ϕ

¬

∀

⇔

∃

¬

¬

∃

⇔

∀

¬

prawa de Morgana

3.

)

(

)

(

))

(

)

(

(

x

x

x

x

x

x

x

ψ

ϕ

ψ

ϕ

∀

∧

∀

⇔

∧

∀

rozdzielność kwantyfikatora ogólnego

względem koniunkcji

4.

)

(

)

(

))

(

)

(

(

x

x

x

x

x

x

x

ψ

ϕ

ψ

ϕ

∃

∨

∃

⇔

∨

∃

rozdzielność kwantyfikatora

szczególnego względem alternatywy

5.

)

(

)

(

))

(

)

(

(

x

x

x

x

x

x

x

ψ

ϕ

ψ

ϕ

∃

∧

∃

⇒

∧

∃

6.

))

(

)

(

(

))

(

)

(

x

x

x

x

x

x

x

ψ

ϕ

ψ

ϕ

∨

∀

⇒

∀

∨

∀

Uwaga: Dla kwantyfikatorów ograniczonych zachodzą te same prawa.

Przykład:

)

(

))

(

:

(

)

(

))

(

:

(

x

x

x

x

x

x

α

ϕ

α

ϕ

¬

∃

⇔

∀

¬

Logika i teoria mnogości – Wykład 1

4

Prawa włączania i wyłączania kwantyfikatorów

Tw. 2. Niech

)

(x

ϕ

- dowolna funkcja zdaniowa o zakresie zmiennej x

X i niech -

zdanie, zaś oznacza wybrany spójnik logiczny

⇒

∨

∧

,

,

. Wtedy:

1.

)

(

)

)

(

(

x

x

x

x

ϕ

β

ϕ

β

∀

◊

⇔

◊

∀

,

2.

)

(

)

)

(

(

x

x

x

x

ϕ

β

ϕ

β

∃

◊

⇔

◊

∃

.

Prawa przestawiania kwantyfikatorów

Tw. 3. Niech

)

,

(

y

x

ϕ

będzie dowolną funkcją zdaniową o zakresie zmiennych x

X,

y

Y. Wtedy:

1.

)

,

(

)

,

(

y

x

x

y

y

x

y

x

ϕ

ϕ

∀

∀

⇔

∀

∀

przemienność kwantyfikatorów ogólnych

2.

)

,

(

)

,

(

y

x

x

y

y

x

y

x

ϕ

ϕ

∃

∃

⇔

∃

∃

przemienność kwantyfikatorów szczegółowych

3.

)

,

(

)

,

(

y

x

x

y

y

x

y

x

ϕ

ϕ

∃

∀

⇒

∀

∃

.