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 AX.
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
ϕ
ϕ
∃
∀
⇒
∀
∃
.