Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

1

Elementy logiki

Wojciech Buszkowski

Zakład Teorii Oblicze´n

Wydział Matematyki i Informatyki

Uniwersytet im. Adama Mickiewicza

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

2

1. K R Z´

1.1. Spójniki logiczne

Zdaniem w sensie logicznym

nazywamy wyra˙zenie, które jest

prawdziwe lub fałszywe.
Prawd ˛e i fałsz nazywamy

warto´sciami logicznymi

.

Prawd ˛e oznaczamy symbolem 1, a fałsz symbolem 0.

Zmienne zdaniowe

p, q, r, s (tak˙ze z indeksami) reprezentuj ˛a

dowolne zdania.

Spójniki logiczne

(albo: funktory KRZ) słu˙z ˛a do konstrukcji zda´n

logicznie zło˙zonych. Wyró˙zniamy pi ˛e´c podstawowych spójników
logicznych.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

3

Spójnik

negacji

jest to wyra˙zenie nieprawda, ˙ze u˙zyte w kontek´scie

nieprawda, ˙ze p. Symbol: ¬, w kontek´scie: ¬p. Zdanie postaci ¬p
nazywamy negacj ˛a zdania p.
Spójnik

koniunkcji

jest to wyraz i u˙zyty w kontek´scie p i q. Symbol:

∧, w kontek´scie: p ∧ q. Zdanie postaci p ∧ q nazywamy koniunkcj ˛a
zda´n p i q.
Spójnik

alternatywy

jest to wyraz lub u˙zyty w kontek´scie p lub q.

Symbol: ∨, w kontek´scie: p ∨ q. Zdanie postaci p ∨ q nazywamy
alternatyw ˛a zda´n p i q.
Spójnik

implikacji

jest to wyra˙zenie je˙zeli ..., to u˙zyte w kontek´scie

je˙zeli p, to q. Symbol →, w kontek´scie: p → q. Zdanie postaci

p → q nazywamy implikacj ˛a o

poprzedniku

p i

nast ˛epniku

q.

Spójnik

równowa˙zno´sci

jest to wyra˙zenie wtedy i tylko wtedy, gdy

u˙zyte w kontek´scie p wtedy i tylko wtedy, gdy q. Symbol: ↔, w
kontek´scie: p ↔ q. Zdanie postaci p ↔ q nazywamy
równowa˙zno´sci ˛a zda´n p i q.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

4

Inne oznaczenia spójników logicznych: spójnik negacji ∼,
koniunkcji &, ·, alternatywy +, implikacji ⇒, równowa˙zno´sci
⇔, ≡.
Zdanie p nazywamy

argumentem

spójnika negacji w zdaniu ¬p.

Spójnik negacji jest jednoargumentowy.
Zdania p i q nazywamy

argumentami

spójnika koniunkcji w zdaniu

p ∧ q. Spójnik koniunkcji jest dwuargumentowy. Spójniki

alternatywy, implikacji i równowa˙zno´sci s ˛a te˙z dwuargumentowe.
Spójniki logiczne s ˛a

ekstensjonalne

: warto´s´c logiczna zdania

zło˙zonego za pomoc ˛a danego spójnika jest jednoznacznie
wyznaczona przez ten spójnik i warto´sci logiczne argumentów.
Negacja zdania prawdziwego jest zdaniem fałszywym. Negacja
zdania fałszywego jest zdaniem prawdziwym.
Koniunkcja dwóch zda´n jest prawdziwa wtedy i tylko wtedy, gdy oba
argumenty s ˛a prawdziwe.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

5

Alternatywa dwóch zda´n jest prawdziwa wtedy i tylko wtedy, gdy
przynajmniej jeden argument jest prawdziwy.
Implikacja dwóch zda´n (zdanie warunkowe) jest fałszywa wtedy i
tylko wtedy, gdy poprzednik jest prawdziwy, a nast ˛epnik jest
fałszywy.
Równowa˙zno´s´c dwóch zda´n jest prawdziwa wtedy i tylko wtedy, gdy
oba argumenty maj ˛a t ˛e sam ˛a warto´s´c logiczn ˛a.

¬1 = 0, ¬0 = 1
1 ∧ 1 = 1 1 ∨ 1 = 1 1 → 1 = 1 1 ↔ 1 = 1
1 ∧ 0 = 0 1 ∨ 0 = 1 1 → 0 = 0 1 ↔ 0 = 0
0 ∧ 1 = 0 0 ∨ 1 = 1 0 → 1 = 1 0 ↔ 1 = 0
0 ∧ 0 = 0 0 ∨ 0 = 0 0 → 0 = 1 0 ↔ 0 = 1

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

6

W powy˙zszych wzorach symbole spójników oznaczaj ˛a działania na
zbiorze {0, 1}, odpowiadaj ˛ace poszczególnym spójnikom. Czasem
działanie odpowiadaj ˛ace ∧ oznaczamy ∧

0

i podobnie dla pozostałych

spójników.
Tablice prawdziwo´sciowe spójników

p

¬p

1

0

0

1

p

q

p ∧ q

p ∨ q

p → q

p ↔ q

1

1

1

1

1

1

1

0

0

1

0

0

0

1

0

1

1

0

0

0

0

0

1

1

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

7

1.2. Formuły KRZ

Formuły KRZ

to wyra˙zenia poprawnie zbudowane ze zmiennych

zdaniowych za pomoc ˛a spójników logicznych. W formułach
zawieraj ˛acych kilka spójników stosujemy nawiasy, ˙zeby
jednoznacznie okre´sli´c argumenty ka˙zdego spójnika.

Przykład.

Wyra˙zenie p ∧ q ∨ r nie jest poprawnie zbudowan ˛a

formuł ˛a. Wprowadzaj ˛ac nawiasy, otrzymujemy dwie istotnie ró˙zne
formuły: (p ∧ q) ∨ r oraz p ∧ (q ∨ r).
Niektóre nawiasy mo˙zemy pomin ˛a´c, przyjmuj ˛ac priorytety (sił ˛e
wi ˛azania) spójników. Najsilniejszy jest spójnik negacji, słabsze s ˛a
spójniki koniunkcji i alternatywy (równosilne), a najsłabsze spójniki
implikacji i równowa˙zno´sci (równosilne).

p ∧ q → ¬p ∨ q przedstawia formuł ˛e (p ∧ q) → ((¬p) ∨ q).

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

8

Drzewo formuły:

p ∨ ¬q ↔ (q → p), czyli (p ∨ (¬q)) ↔ (q → p)

A

A

A

¢

¢

¢¢

↔

AA ¢¢

∨

p

¬

q

AA ¢¢

→

q

p

Notacja beznawiasowa (polska, Łukasiewicza): ↔ ∨p¬q → qp.
Piszemy funktor przed argumentami. (Czytamy drzewo gał ˛eziami od
lewej, ang. depth-first.)
Inny zapis: EApNqCqp.
Oznaczamy: ¬ : N, ∧ : K, ∨ : A, →: C, ↔: E.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

9

Definicja 1.

Niech V b ˛edzie pewnym zbiorem zmiennych

zdaniowych. Warto´sciowaniem zbioru V nazywamy dowoln ˛a
funkcj ˛e w : V 7→ {0, 1}.
Mniej formalnie: warto´sciowanie jest to przyporz ˛adkowanie
warto´sci logicznych pewnym zmiennym zdaniowym.
Ka˙zde warto´sciowanie w zbioru V jednoznacznie okre´sla warto´s´c
logiczn ˛a dowolnej formuły KRZ, której zmienne nale˙z ˛a do V.
Literami A, B, C, . . . oznaczamy dowolne formuły KRZ.

Warto´s´c

logiczn ˛a formuły A dla warto´sciowania w

oznaczamy przez w(A). T ˛e

warto´s´c mo˙zna wyznaczy´c w oparciu o nast ˛epuj ˛ace warunki
rekurencyjne:
w(¬A) = ¬

0

w(A),

w(A ∧ B) = w(A) ∧

0

w(B), w(A ∨ B) = w(A) ∨

0

w(B),

w(A → B) = w(A) →

0

w(B), w(A ↔ B) = w(A) ↔

0

w(B)

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

10

Przykład.

A = p ∨ q → p ∧ q, w(p) = 1, w(q) = 0. Obliczamy:

w(A) = w(p ∨ q) →

0

w(p ∧ q) = (w(p) ∨

0

w(q)) →

0

(w(p) ∧

0

w(q) =

= (1 ∨

0

0) →

0

(1 ∧

0

0) = 1 →

0

0 = 0

W praktyce zaczynamy od drugiego wiersza i pomijamy "

0

".

W ten sposób mo˙zemy wyznaczy´c warto´s´c logiczn ˛a dowolnego
zdania logicznie zło˙zonego, je˙zeli znane s ˛a warto´sci logiczne
wszystkich składowych zda´n logicznie prostych.

Przykład.

Zdanie: je˙zeli nieprawda, ˙ze Pozna´n le˙zy nad Wisł ˛a, to

je˙zeli Pozna´n le˙zy nad Wart ˛a, to przez Pozna´n przepływa rzeka.

p - Pozna´n le˙zy nad Wisł ˛a, q - Pozna´n le˙zy nad Wart ˛a, r - przez

Pozna´n przepływa rzeka.
Logiczny schemat zdania: A = ¬p → (q → r). Warto´sciowanie:
w(p) = 0, w(q) = w(r) = 1. Mamy
w(A) = ¬0 → (1 → 1) = 1 → 1 = 1. Zatem zdanie jest prawdziwe.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

11

Tablica prawdziwo´sciowa formuły: A = p ∨ ¬q → ¬p ∧ r.
Oznaczmy: B = p ∨ ¬q, C = ¬p ∧ r.

p q r

¬q ¬p B C

A

1 1 1

0

0

1

0

0

1 1 0

0

0

1

0

0

1 0 1

1

0

1

0

0

1 0 0

1

0

1

0

0

0 1 1

0

1

0

1

1

0 1 0

0

1

0

0

1

0 0 1

1

1

1

1

1

0 0 0

1

1

1

0

0

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

12

1.3. Tautologie KRZ, logiczna równowa˙zno´s´c i logiczne
wynikanie

Definicja 2.

Tautologi ˛a KRZ nazywamy formuł ˛e KRZ, która

przyjmuje warto´s´c logiczn ˛a 1 dla ka˙zdego wartosciowania
zmiennych wyst ˛epuj ˛acych w tej formule.
Tautologie KRZ s ˛a logicznymi schematami zda´n

logicznie

prawdziwych

, tzn. prawdziwych na mocy samej logiki, niezale˙znie

od warto´sci logicznych składowych zda´n prostych.

Przykład.

Zdanie Pozna´n le˙zy nad Wart ˛a jest prawdziwe, ale nie jest

logicznie prawdziwe. Jego schemat logiczny p nie jest tautologi ˛a.
Zdanie je˙zeli Pozna´n le˙zy nad Wart ˛a, to Pozna´n le˙zy nad Wart ˛a jest
logicznie prawdziwe. Jego schemat logiczny p → p jest tautologi ˛a.
w(p) = 1. Wtedy w(p → p) = 1 → 1 = 1.
w(p) = 0. Wtedy w(p → p) = 0 → 0 = 1.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

13

Definicja 3.

Mówimy, ˙ze formuła A jest logicznie równowa˙zna

formule B (w KRZ), je˙zeli dla ka˙zdego warto´sciowania w
(zmiennych wyst ˛epuj ˛acych w tych formułach) w(A) = w(B).

Fakt 1.

A jest logicznie równowa˙zne B wtetdy i tylko wtedy, gdy

formuła A ↔ B jest tautologi ˛a.

Dowód.

Oczywi´scie dla dowolnego warto´sciowania w:

w(A) = w(B) wtw, gdy w(A ↔ B) = 1.
St ˛ad wynika równowa˙zno´s´c warunków:
(L) dla ka˙zdego warto´sciowania w w(A) = w(B),
(P) dla ka˙zdego warto´sciowania w w(A ↔ B) = 1,
co ko´nczy dowód faktu. Q.E.D.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

14

Prawa

ł ˛aczno´sci

koniunkcji, alternatywy i równowa˙zno´sci:

(p ∧ q) ∧ r ↔ p ∧ (q ∧ r)
(p ∨ q) ∨ r ↔ p ∨ (q ∨ r)
[(p ↔ q) ↔ r] ↔ [p ↔ (q ↔ r)]
Prawa

przemienno´sci

koniunkcji, alternatywy i równowa˙zno´sci:

p ∧ q ↔ q ∧ p
p ∨ q ↔ q ∨ p

(p ↔ q) ↔ (q ↔ p)
Na mocy praw ł ˛aczno´sci mo˙zemy pomija´c nawiasy w formułach

p

1

∧ p

2

∧ · · · ∧ p

n

oraz p

1

∨ p

2

∨ · · · ∨ p

n

.

Na mocy praw ł ˛aczno´sci i przemienno´sci kolejno´s´c wyst ˛epowania
zmiennych nie wpływa na warto´s´c logiczn ˛a takich formuł.
To samo mo˙zna stwierdzi´c o formułach postaci A

1

∧ A

2

∧ · · · ∧ A

n

i

A

1

∨ A

2

∨ · · · ∨ A

n

.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

15

Prawa

idempotentno´sci

koniunkcji i alternatywy:

p ∧ p ↔ p
p ∨ p ↔ p

Prawa

rozdzielno´sci koniunkcji wzgl ˛edem alternatywy

i

alternatywy

wzgl ˛edem koniunkcji

:

p ∧ (q ∨ r) ↔ (p ∧ q) ∨ (p ∧ r)
p ∨ (q ∧ r) ↔ (p ∨ q) ∧ (p ∨ r)

Pierwsze prawo rozdzielno´sci przypomina arytmetyczne prawo
rozdzielno´sci mno˙zenia wzgl ˛edem dodawania:
a · (b + c) = a · b + a · c,
lecz drugie prawo rozdzielno´sci nie ma odpowiednika w arytmetyce.
Prawa

De Morgana

:

¬(p ∧ q) ↔ ¬p ∨ ¬q
¬(p ∨ q) ↔ ¬p ∧ ¬q

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

16

Prawo

podwójnej negacji

: ¬¬p ↔ p

Prawo

transpozycji

: (p → q) ↔ (¬q → ¬p)

Prawo

eksportacji-importacji

: [p ∧ q → r] ↔ [p → (q → r)]

Prawo

wył ˛aczonego ´srodka

: p ∨ ¬p

Prawo

sprzeczno´sci

: ¬(p ∧ ¬p).

Prawa

definiowania

jednych spójników przez inne:

(p ↔ q) ↔ (p → q) ∧ (q → p)
(p → q) ↔ ¬p ∨ q

p ∧ q ↔ ¬(¬p ∨ ¬q)
p ∨ q ↔ ¬(¬p ∧ ¬q)

Prawa

z ustalonym argumentem

:

p ∧ 1 ↔ p, p ∧ 0 ↔ 0, p ∨ 1 ↔ 1, p ∨ 0 ↔ p

(1 → p) ↔ p, (0 → p) ↔ 1, (p → 1) ↔ 1, (p → 0) ↔ ¬p

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

17

Definicja 4.

Mówimy, ˙ze warto´sciowanie w spełnia formuł ˛e A, je˙zeli

w(A) = 1. Formuł ˛e nazywamy spełnialn ˛a, je˙zeli istnieje
warto´sciowanie, które spełnia t ˛e formuł ˛e. Zbiór formuł nazywamy
spełnialnym, je˙zeli istnieje warto´sciowanie, które spełnia wszystkie
formuły z tego zbioru (tzn. spełnia ten zbiór).

Fakt 2.

Formuła A jest spełnialna wtw, gdy formuła ¬A nie jest

tautologi ˛a. Formuła A jest tautologi ˛a wtw, gdy formuła ¬A nie jest
spełnialna.

Definicja 5.

Mówimy, ˙ze formuła A logicznie wynika ze zbioru

formuł S (w KRZ), je˙zeli ka˙zde warto´sciowanie spełniaj ˛ace zbiór S
spełnia formuł ˛e A.

Fakt 3.

Formuła A logicznie wynika ze zbioru formuł S wtw, gdy

zbiór S ∪ {¬A} nie jest spełnialny.

Fakt 4.

Formuła A logicznie wynika ze zbioru {A

1

, . . . , A

n

} wtw, gdy

formuła A

1

∧ · · · ∧ A

n

→ A jest tautologi ˛a.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

18

Prawo

odrywania

: (p → q) ∧ p → q

Prawo

odrzucania

: (p → q) ∧ ¬q → ¬p

Prawo

sylogizmu hipotetycznego

: (p → q) ∧ (q → r) → (p → r)

Prawa

symplifikacji

: p ∧ q → p, p ∧ q → q

Prawa

addycji

: p → p ∨ q, q → p ∨ q

Logiczne wynikanie zapisujemy te˙z w postaci schematów
wnioskowania:

A

1

; . . . ; A

n

A

,

gdzie formuły A

1

, . . . , A

n

nazywamy

przesłankami

, a formuł ˛e A

wnioskiem

. Schemat wnioskowania nazywamy

logiczn ˛a reguł ˛a

wnioskowania

KRZ, je˙zeli wniosek logicznie wynika z przesłanek

(tzn. ze zbioru przesłanek).

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

19

Reguła

odrywania

(nazwa łaci´nska: modus ponens)

(MP)

p → q; p

q

Reguła

sylogizmu hipotetycznego

:

(SYL)

p → q; q → r

p → r

Reguła

odrzucania

:

p → q; ¬q

¬p

Reguła

wprowadzania równowa˙zno´sci

:

p → q; q → p

p ↔ q

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

20

1.4. Podstawianie w KRZ

Tautologie i logiczne reguły wnioskowania KRZ s ˛a zamkni ˛ete ze
wzgl ˛edu na podstawianie dowolnych formuł za zmienne zdaniowe.
σ = [p

1

/A

1

, . . . , p

n

/A

n

] oznacza operacj ˛e równoczesnego

podstawiania formuły A

i

za zmienn ˛a p

i

dla i = 1, . . . , n. Tak ˛a

operacj ˛e nazywamy

podstawieniem

.

Aσ oznacza wynik podstawienia σ w formule A.

Przykład.

(p → p ∨ q)[p/q, q/q ∨ r] = q → q ∨ (q ∨ r).

UWAGA: Wykonuj ˛ac podstawienie Aσ, formuł ˛e A

i

podstawiamy za

ka˙zde wyst ˛apienie zmiennej p

i

w formule A, lecz nie za te

wyst ˛apienia, które pojawiaj ˛a si ˛e w wyniku podstawiania (wyst ˛epuj ˛a
w formułach A

j

). Dlatego A[p/B, q/C] jest na ogół ró˙zne od

A[p/B][q/C].

(p → p ∨ q)[p/q][q/q ∨ r] = (q → q ∨ q)[q/q ∨ r] = q ∨ r → q ∨ r

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

21

Fakt 5.

Je˙zeli A jest tautologi ˛a KRZ, to dla ka˙zdego podstawienia σ

formuła Aσ jest tautologi ˛a KRZ.

Dowód.

Niech σ = [p

1

/A

1

, . . . , p

n

/A

n

]. Niech A b ˛edzie tautologi ˛a.

Niech w b ˛edzie dowolnym warto´sciowaniem zmiennych w Aσ.
Okre´slamy warto´sciowanie w

0

zmiennych w A:

w

0

(p

i

) = w(A

i

) dla p

i

wyst ˛epuj ˛acych w A, w

0

(q) = q dla pozostałych

zmiennych w A.
Oczywi´scie w(Aσ) = w

0

(A). Poniewa˙z A jest tautologi ˛a, wi ˛ec

w

0

(A) = 1, czyli w(Aσ) = 1. Zatem Aσ przyjmuje warto´s´c 1 dla

ka˙zdego warto´sciowania w. Q.E.D.

Przykład.

p ∨ q ↔ q ∨ p jest tautologi ˛a. Zatem tautologi ˛a jest ka˙zda

formuła postaci A ∨ B ↔ B ∨ A, poniewa˙z powstaje z poprzedniej
przez podstawienie [p/A, q/B].

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

22

Fakt 6.

Je˙zeli A logicznie wynika ze zbioru {A

1

, . . . , A

n

}, to dla

ka˙zdego podstawienia σ formuła Aσ logicznie wynika ze zbioru
{A

1

σ, . . . , A

n

σ}.

Dowód.

Zakładamy, ˙ze A logicznie wynika z {A

1

, . . . , A

n

}. Niech σ

b ˛edzie podstawieniem.
Na mocy faktu 4, formuła A

1

∧ · · · ∧ A

n

→ A jest tautologi ˛a.

Mamy: (A

1

∧ · · · ∧ A

n

→ A)σ = A

1

σ ∧ · · · ∧ A

n

σ → Aσ.

Na mocy faktu 5, A

1

σ ∧ · · · ∧ A

n

σ → Aσ jest tautologi ˛a.

Na mocy faktu 4, Aσ logicznie wynika ze zbioru {A

1

σ, . . . , A

n

σ}.

Q.E.D.

Przykład.

Skoro MP jest logiczn ˛a reguł ˛a wnioskowania, to jest ni ˛a

te˙z ka˙zdy schemat:

A → B; A

B

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

23

1.5. Postacie normalne formuł KRZ

Formuły p i ¬p, gdzie p jest dowoln ˛a zmienn ˛a zdaniow ˛a, nazywamy

literałami

; p jest literałem

pozytywnym

, a ¬p

negatywnym

. Literały

p, ¬p s ˛a

przeciwne

(jeden wzgl ˛edem drugiego).

Alternatywa elementarna

(albo: klauzula) jest to alternatywa

sko´nczenie wielu literałów, np. p ∨ ¬q ∨ r, ¬q.

Koniunkcja elementarna

jest to koniunkcja sko´nczenie wielu

literałów, np. p ∧ ¬q ∧ r, ¬q.

Formuła w koniunkcyjnej postaci normalnej

(kpn) jest to koniunkcja

sko´nczenie wielu klauzul, np. (p ∨ ¬q ∨ r) ∧ (¬p ∨ ¬r).

Formuła w alternatywnej postaci normalnej

(apn) jest to alternatywa

sko´nczenie wielu koniunkcji elementarnych, np.
(p ∧ ¬q ∧ r) ∨ (¬p ∧ ¬r).

Twierdzenie 1.

Ka˙zda formuła KRZ jest logicznie równowa˙zna

pewnej formule w kpn i pewnej formule w apn.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

24

Przykład.

A = p ∧ q ↔ q ∧ ¬r.

p q r

p ∧ q ¬r q ∧ ¬r A

apn

kpn

1 1 1

1

0

0

0

¬p ∨ ¬q ∨ ¬r

1 1 0

1

1

1

1

p ∧ q ∧ ¬r

1 0 1

0

0

0

1

p ∧ ¬q ∧ r

1 0 0

0

1

0

1

p ∧ ¬q ∧ ¬r

0 1 1

0

0

0

1

¬p ∧ q ∧ r

0 1 0

0

1

1

0

p ∨ ¬q ∨ r

0 0 1

0

0

0

1

¬p ∧ ¬q ∧ r

0 0 0

0

1

0

1

¬p ∧ ¬q ∧ ¬r

apn: (p ∧ q ∧ ¬r) ∨ (p ∧ ¬q ∧ r) ∨ (p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ q ∧ r) ∨
(¬p ∧ ¬q ∧ r) ∨ (¬p ∧ ¬q ∧ ¬r)
kpn: (¬p ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬q ∨ r)

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

25

Przypadki szczególne:
(1) w(A) = 0 dla ka˙zdego warto´sciowania w. Wtedy A jest logicznie
równowa˙zne formule p ∧ ¬p, która jest w apn.
(2) w(A) = 1 dla ka˙zdego warto´sciowania w. Wtedy A jest logicznie
równowa˙zne formule p ∨ ¬p, która jest w kpn.
Sprowadzanie do apn i kpn

metod ˛a przekształce´n

równowa˙zno´sciowych

.

Podformuły danej formuły zast ˛epujemy równowa˙znymi formułami,
stosuj ˛ac nast ˛epuj ˛ace prawa (zast ˛epujemy lew ˛a stron ˛e praw ˛a stron ˛a).
¬¬A ↔ A
(A ↔ B) ↔ (A → B) ∧ (B → A), (A → B) ↔ ¬A ∨ B
¬(A ∨ B) ↔ ¬A ∧ ¬B, ¬(A ∧ B) ↔ ¬A ∨ ¬B

A ∧ (B ∨ C) ↔ (A ∧ B) ∨ (A ∧ C), (B ∨ C) ∧ A ↔ (B ∧ A) ∨ (C ∧ A)
A ∨ (B ∧ C) ↔ (A ∨ B) ∧ (A ∨ C), (B ∧ C) ∨ A ↔ (B ∨ A) ∧ (C ∨ A)

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

26

Przykład.

Sprowadzamy formuł ˛e A = p ∨ q ↔ q ∧ ¬r do kpn.

[p ∨ q → q ∧ ¬r] ∧ [q ∧ ¬r → p ∨ q]
[¬(p ∨ q) ∨ (q ∧ ¬r)] ∧ [¬(q ∧ ¬r) ∨ (p ∨ q)]
[(¬p ∧ ¬q) ∨ (q ∧ ¬r)] ∧ [¬q ∨ r ∨ p ∨ q] (negacyjna posta´c normalna)
[(¬p ∧ ¬q) ∨ q] ∧ [(¬p ∧ ¬q) ∨ ¬r] ∧ [¬q ∨ r ∨ p ∨ q]
(¬p ∨ q) ∧ (¬q ∨ q) ∧ (¬p ∨ ¬r) ∧ (¬q ∨ ¬r) ∧ (¬q ∨ r ∨ p ∨ q)
Sprowadzamy A do apn. Powtarzamy trzy pierwsze kroki i
kontynuujemy.
{[(¬p ∧ ¬q) ∨ (q ∧ ¬r)] ∧ ¬q} ∨ {[(¬p ∧ ¬q) ∨ (q ∧ ¬r)] ∧ r} ∨
{[(¬p ∧ ¬q) ∨ (q ∧ ¬r)] ∧ p} ∨ {[(¬p ∧ ¬q) ∨ (q ∧ ¬r)] ∧ q}
(¬p ∧ ¬q ∧ ¬q) ∨ (q ∧ ¬r ∧ ¬q) ∨ (¬p ∧ ¬q ∧ r) ∨ (q ∧ ¬r ∧ r) ∨
(¬p ∧ ¬q ∧ p) ∨ (q ∧ ¬r ∧ p) ∨ (¬p ∧ ¬q ∧ q) ∨ (q ∧ ¬r ∧ q)

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

27

Twierdzenie 2.

Formuła w kpn jest tautologi ˛a KRZ wtw, gdy w

ka˙zdej składowej klauzuli wyst ˛epuje para przeciwnych literałów.

Dowód.

Twierdzenie wynika z dwóch faktów.

(1) Formuła A

1

∧ A

2

∧ · · · ∧ A

n

jest tautologi ˛a wtw, gdy ka˙zda

formuła A

i

jest tautologi ˛a.

(2) Klauzula jest tautologi ˛a wtw, gdy wyst ˛epuje w niej para
przeciwnych literałów.
(1) jest oczywiste.
(2). Je˙zeli w klauzuli wyst ˛epuj ˛a przeciwne literały, to dla ka˙zdego
warto´sciowania jeden z nich ma warto´s´c 1, czyli cała klauzula ma
warto´s´c 1. Je˙zeli w klauzuli nie wyst ˛epuj ˛a przeciwne literały, to
mo˙zna znale´z´c warto´sciowanie, dla którego wszystkie literały maj ˛a
warto´s´c 0, czyli cała klauzula ma warto´s´c 0. Q.E.D.

Przykład.

C = p ∨ ¬q ∨ r. Okre´slamy w(p) = 0, w(q) = 1, w(r) = 0.

Wtedy w(C) = 0.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

28

Twierdzenie 3.

Formuła w apn nie jest spełnialna wtw, gdy w ka˙zdej

składowej koniunkcji elementarnej wyst ˛epuje para przeciwnych
literałów.

Przykład.

A = p ∧ (q ∨ r) → (p ∧ q) ∨ r. Sprowadzamy A do kpn.

¬[p ∧ (q ∨ r)] ∨ [(p ∧ q) ∨ r]
[¬p ∨ ¬(q ∨ r)] ∨ [(p ∨ r) ∧ (q ∨ r)]
[¬p ∨ (¬q ∧ ¬r)] ∨ [(p ∨ r) ∧ (q ∨ r)]
[(¬p ∨ ¬q) ∧ (¬p ∨ ¬r)] ∨ [(p ∨ r) ∧ (q ∨ r)]
(¬p∨¬q∨ p∨r)∧(¬p∨¬q∨q∨r)∧(¬p∨¬r∨ p∨r)∧(¬p∨¬r∨q∨r)
Formuła A jest tautologi ˛a. Sprowadzamy A do apn.
¬p ∨ (¬q ∧ ¬r) ∨ (p ∧ q) ∨ r
Formuła A jest spełnialna.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

29

1.6. Formalne systemy dedukcyjne KRZ

Przedstawimy

system dedukcyjny KRZ w stylu Fregego-Hilberta

.

Niektóre tautologie KRZ przyjmujemy jako

aksjomaty

. Wszystkie

pozostałe tautologie i wszystkie logiczne reguły wnioskowania KRZ
mo˙zna wyprowadzi´c z tych aksjomatów, posługuj ˛ac si ˛e dwiema

regułami dowodzenia

: reguł ˛a odrywania i reguł ˛a podstawiania.

(MP)

A → B; A

B

, (SUB)

A

Aσ

Te reguły przyjmujemy dla wszelkich formuł A, B i ka˙zdego
podstawienia σ. Je˙zeli przesłanki tych reguł s ˛a tautologiami, to
wniosek jest tautologi ˛a.
Aksjomaty implikacji
(A1) p → (q → p) (prawo poprzednika)
(A2) [p → (q → r)] → [(p → q) → (p → r)] (prawo Fregego)

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

30

Aksjomat negacji
(A3) (¬q → ¬p) → (p → q) (odwrotne prawo transpozycji)
Aksjomaty koniunkcji
(A4) p ∧ q → p, (A5) p ∧ q → q (prawa symplifikacji)
(A6) (p → q) → [(p → r) → (p → q ∧ r)] (prawo mno˙zenia
nast ˛epników)
Aksjomaty alternatywy
(A7) p → p ∨ q, (A8) q → p ∨ q (prawa addycji)
(A9) (p → r) → [(q → r) → (p ∨ q → r)] (prawo dodawania
poprzedników)
Aksjomaty równowa˙zno´sci
(A10) (p ↔ q) → (p → q), (A11) (p ↔ q) → (q → p)
(A12) (p → q) → [(q → p) → (p ↔ q)]

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

31

Dowód formalny

mo˙zna przedstawi´c jako sko´nczony ci ˛ag formuł, w

którym ka˙zda formuła jest aksjomatem systemu lub wnioskiem z
poprzednich formuł na mocy reguł dowodzenia systemu. Ostatnia
formuła tego ci ˛agu jest dowodzonym

twierdzeniem

. Twierdzenia

systemów formalnych nazywamy te˙z

tezami

.

(T1)

p → p (prawo to˙zsamo´sci)

1. [p → (q → r)] → [(p → q) → (p → r)] (A2)
2. [p → (q → p)] → [(p → q) → (p → p)] SUB 1 [r/p]
3. p → (q → p) (A1)
4. (p → q) → (p → p) MP 2,3
5. (p → (p → p)) → (p → p) SUB 4 [q/p → p]
6. p → (p → p) SUB 3 [q/p]
7. p → p MP 5,6

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

32

(T2)

p ∧ q → q ∧ p

1. (p → q) → [(p → r) → (p → q ∧ r)] (A6)
2. (p ∧ q → q) → [(p ∧ q → p) → (p ∧ q → q ∧ p)] SUB 1
[p/p ∧ q, r/p]
3. p ∧ q → q (A5)
4. (p ∧ q → p) → (p ∧ q → q ∧ p) MP 2,3
5. p ∧ q → p (A4)
6. p ∧ q → q ∧ p MP 4,5

(T2’)

q ∧ p → p ∧ q

1. p ∧ q → q ∧ p (T2)
2. q ∧ p → p ∧ q SUB 1 [p/q, q/p]

(T2”)

p ∧ q ↔ q ∧ p. W (A12) podstaw p/p ∧ q, q/q ∧ p. Potem

zastosuj (T2), (T2’) i dwa razy MP.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

33

W

formalnych dowodach reguł

przesłanki reguły graj ˛a rol ˛e

zało˙ze´n

dowodu

.

Istotnie ograniczamy stosowanie SUB: nie wolno podstawia´c w
zało˙zeniach, ani ˙zadnych formułach, które od nich pochodz ˛a. Zatem
SUB wolno stosowa´c tylko do aksjomatów oraz ju˙z udowodnionych
tez i reguł systemu.

(SYL)

A → B; B → C

A → C

1. A → B (zało˙zenie)
2. B → C (zało˙zenie)
3. [A → (B → C)] → [(A → B) → (A → C)] (A2), SUB
4. (B → C) → [A → (B → C)] (A1), SUB
5. A → (B → C) MP 4,2
6. A → C 2× MP 3,5,1

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

34

Je˙zeli przesłanki reguły (SYL) mo˙zna udowodni´c, to i wniosek
mo˙zna udowodni´c: wystarczy skopiowa´c powy˙zszy dowód.
Tak jest dla wszelkich reguł udowodnionych w systemie. Wobec
tego, udowodnione reguły mo˙zemy stosowa´c w nast ˛epnych
dowodach jako skróty; ich stosowanie nie zmienia siły systemu.

(KOM)

A → (B → C)
B → (A → C)

(reguła komutacji)

1. A → (B → C) (zało˙zenie)
2. [A → (B → C)] → [(A → B) → (A → C)] (A2), SUB
3. (A → B) → (A → C) MP 2,1
4. B → (A → B) (A1), SUB
5. B → (A → C) SYL 4,3

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

35

(T3)

(p → q) → [(q → r) → (p → r)] (prawo sylogizmu

hipotetycznego)
1. [p → (q → r)] → [(p → q) → (p → r)] (A2)
2. (q → r) → [p → (q → r)] (A1), SUB
3. (q → r) → [(p → q) → (p → r)] SYL 2,1
4. (p → q) → [(q → r) → (p → r)] KOM 3

(T4)

¬p → (p → q) (prawo Dunsa Szkota)

1. (¬q → ¬p) → (p → q) (A3)
2. ¬p → (¬q → ¬p) (A1), SUB
3. ¬p → (p → q) SYL 2,1
Tezy tego systemu pokrywaj ˛a si ˛e z tautologiami KRZ. Reguły
dowodliwe w tym systemie pokrywaj ˛a si ˛e z logicznymi regułami
wnioskowania KRZ.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

36

Przedstawimy

system sekwencyjny

dowodzenia praw KRZ. W

takich systemach procedura poszukiwania dowodu mo˙ze by´c
całkowicie zautomatyzowana.

Sekwent:

sko´nczona lista formuł A

1

, . . . , A

n

, interpretowana jako

alternatywa A

1

∨ · · · ∨ A

n

.

Aksjomaty:

wszystkie sekwenty zawieraj ˛ace par ˛e sprzecznych

formuł A, ¬A (w dowolnej kolejno´sci).

Reguły dowodzenia:

(R ¬)

X, A, Y

X, ¬¬A, Y

(R ∧)

X, A, Y; X, B, Z

X, A ∧ B, Z

(R ¬∧)

X, ¬A, ¬B, Y

X, ¬(A ∧ B), Y

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

37

(R ∨)

X, A, B, Y

X, A ∨ B, Y

(R¬∨ )

X, ¬A, Y; X, ¬B, Y

X, ¬(A ∨ B), Y

(R →)

X, ¬A, B, Y

X, A → B, Y

(R¬ →)

X, A, Y; X, ¬B, Y

X, ¬(A → B), Y

(R ↔)

X, ¬A, B, Y; X, A, ¬B, Y

X, A ↔ B, Y

(R ¬ ↔)

X, A, B, Y; X, ¬A, ¬B, Y

X¬(A ↔ B), Y

W tych regułach litery X, Y oznaczaj ˛a dowolne konteksty, czyli
sko´nczone listy formuł (mog ˛a by´c puste).
W przypadku reguły z jedn ˛a przesłank ˛a wniosek jest logicznie
równowa˙zny tej przesłance; w przypadku reguły z dwiema
przesłankami wniosek jest logicznie równowa˙zny koniunkcji
przesłanek (listy interpretujemy jako alternatywy).

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

38

(p → q) → (¬q → ¬p)

\

\

\

¿

¿

¿

¬(p → q), ¬q → ¬p

p, ¬q → ¬p

p, ¬¬q, ¬p

p, q, ¬p

¬q, ¬q → ¬p

¬q, ¬¬q, ¬p

¬q, q, ¬p

p ∨ q → p ∧ q

\

\

\

¿

¿

¿

¬(p ∨ q), p ∧ q

A

A

A

¢

¢¢

¬p, p ∧ q

¬p, p ¬p, q

A

A

¢

¢

¬q, p ∧ q

¬q, p ¬q, q

Formuła w korzeniu drzewa jest logicznie równowa˙zna koniunkcji
wszystkich alternatyw elementarnych na li´sciach drzewa. Zatem
nasz system mo˙ze słu˙zy´c do sprowadzania formuł do kpn.
Z lewej strony: drzewo dowodu prawa (p → q) → (¬q → ¬p).
Z prawej strony: poszukiwanie dowodu formuły p ∨ q → p ∧ q
zako´nczyło si ˛e pora˙zk ˛a, poniewa˙z dwa sekwenty elementarne na
li´sciach drzewa nie s ˛a aksjomatami.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

39

2. K R P´

2.1. Wprowadzenie

Skrót: KRP
Inne nazwy: logika elementarna, logika pierwszego rz ˛edu (ang.
first-order logic, st ˛ad skrót FOL).
Rozwa˙zmy wnioskowanie:
Ka˙zdy Polak jest Europejczykiem. Jan jest Polakiem. Zatem Jan jest
Europejczykiem.
To wnioskowanie jest dedukcyjne, lecz nie mo˙zna tego stwierdzi´c na
gruncie KRZ. Schemat tego wnioskowania na gruncie KRZ to:

p; q

r

Oczywi´scie ten schemat nie jest logiczn ˛a reguł ˛a wnioskowania KRZ.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

40

Na gruncie KRP wnikamy gł ˛ebiej w struktur ˛e zda´n.
Oznaczamy:

P(x) : x jest Polakiem
Q(x) : x jest Europejczykiem

a : Jan
Otrzymujemy schemat:

∀x(P(x) → Q(x)); P(a)

Q(a)

,

który jest logiczn ˛a reguł ˛a wnioskowania KRP.
To znaczy: dla ka˙zdej prawidłowej interpretacji symboli P, Q, a,
je˙zeli przesłanki tego schematu s ˛a prawdziwe, to wniosek jest
prawdziwy.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

41

W j ˛ezyku formalnym KRP pojawiaj ˛a si ˛e nast ˛epuj ˛ace symbole.

Zmienne indywiduowe:

x, y, z (ewentualnie z indeksami).

Zmienne indywiduowe reprezentuj ˛a elementy pewnej dziedziny
obiektów, b ˛ed ˛acej niepustym zbiorem.

Stałe indywiduowe:

a, b, c (ewentualnie z indeksami).

Stałe indywiduowe oznaczaj ˛a wyró˙znione elementy dziedziny.
Innymi słowy, graj ˛a rol ˛e nazw własnych tych elementów. W j ˛ezyku
polskim nazwami własnymi s ˛a np. Warszawa, Lech Wał ˛esa. W
matematyce t ˛e rol ˛e graj ˛a symbole liczb, np. 0,1,2,. . ., π, e, symbole
wyró˙znionych zbiorów, np. N, R i inne.

Stałe logiczne:

spójniki logiczne KRZ i kwantyfikatory ∀ i ∃.

∀ nazywamy kwantyfikatorem ogólnym (generalnym, uniwersalnym,
du˙zym). Inne oznaczenie:

V

.

∃ nazywamy kwantyfikatorem szczegółowym (egzystencjalnym,
istnienia, małym). Inne oznaczenie:

W

.

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

42

Kwantyfikator zawsze wyst ˛epuje w powi ˛azaniu ze zmienn ˛a: ∀x, ∃x.
∀x czytamy: dla ka˙zdego x.
∃x czytamy: istnieje x takie, ˙ze.

Przykład.

∀x∃y(x < y) czytamy: dla ka˙zdego x istnieje y takie, ˙ze x

jest mniejsze od y.

Symbole relacyjne:

P, Q, R (ewentualnie z indeksami). Inna nazwa:

symbole predykatowe.
Przyjmujemy, ˙ze ka˙zdy symbol relacyjny ma okre´slon ˛a liczb ˛e
argumentów (argumentowo´s´c, arno´s´c), któr ˛a podajemy w deklaracji
j ˛ezyka jako górny indeks, np. P

1

- jednoargumentowy (unarny)

symbol relacyjny, Q

2

- dwuargumentowy (binarny) symbol relacyjny

itp.
Argumentami symboli relacyjnych mog ˛a by´c zmienne i stałe
indywiduowe. Symbol relacyjny razem z argumentami tworzy

formuł ˛e atomow ˛a

(atom).

Wojciech Buszkowski

Elementy logiki. Wykład kursowy.

43

Przykład.

Przykłady formuł atomowych, zbudowanych z symboli

relacyjnych P

1

, Q

1

, R

2

, zmiennych x, y i stałych indywiduowych a, b:

P(a) - czytamy: P od a. Q(x) - czytamy: Q od x. R(x, y) - czytamy:

R od x, y.
Formuła P(a) wyra˙za stwierdzenie, ˙ze a ma własno´s´c P.
Formuła R(x, y) wyra˙za stwierdzenie, ˙ze x jest w stosunku R do y.

Jednoargumentowe symbole relacyjne reprezentuj ˛a własno´sci
elementów dziedziny.
Dwuargumentowe symbole relacyjne reprezentuj ˛a stosunki
dwuczłonowe mi ˛edzy elementami dziedziny.
Symbole relacyjne o wi ˛ekszej liczbie argumentów reprezentuj ˛a
stosunki wieloczłonowe, np. R(x, y, z) : x le˙zy mi ˛edzy y i z
(dziedzina to zbiór wszystkich punktów danej prostej).