1. Elementy logiki matematycznej, rachunek zdań, funkcje zdaniowe,
metody dowodzenia, rachunek predykatów

Logika matematyczna, dział matematyki zajmujący się badaniem własności wnioskowania
(dowodzenia) matematycznego oraz modeli teorii matematycznych. Początki logiki

matematycznej sięgają drugiej połowy XIX w. (G.Boole, Ch.Peirce, G.Peano), ale jej
uformowanie się i rozwój przypadają na wiek XX (G.Frege, D.Hilbert, B.Russell).

Najciekawsze odkrycia w logice matematycznej poczynili K.Gödel i A.Tarski w latach 30 XX
wieku. Oprócz logiki ogólnej (obejmującej także logikę intuicjonistyczną, logiki modalne i

in.) wyodrębnia się w logice matematycznej następujące działy:

●

teorię modeli, badającą związki między zbiorami zdań (formuł) a ich modelami,

a także podającą konstrukcje modeli o specjalnych własnościach (A.Tarski, R.Vaught,
T.Skolem);

●

teorię rekursji, badającą efektywność konstrukcji matematycznych i logicznych oraz
rozstrzygalność teorii; teoria ta bazuje na pojęciu funkcji obliczalnej (rekurencyjnej)

wprowadzonym przez K. Gödla i niezależnie przez A. Turinga;

●

teorię dowodu, badającą strukturę dowodów matematycznych i zagadnienia

konstruktywności w matematyce (D.Hilbert, J.Herbrand, L.E.J.Brouwer, G.Gentzen).

Logika zdań, rachunek zdań

Zdanie logiczne jest to wypowiedź, w której orzeka się coś o czymś, czyli w terminach

tradycyjnej gramatyki jest to zdanie oznajmujące.

W logice dwuwartościowej (klasycznej) zakłada się, że każde poprawnie zbudowane zdanie

jest albo prawdziwe albo fałszywe jest to tak zwana zasada sprzeczności.

„Prawdę” bądź „fałsz” nazywamy wartością logiczną (stałą logiczną) zdania i oznaczamy

odpowiednio przez P lub 1 oraz F lub 0.

Logika zdań bada prawdziwość zdań złożonych zależnie od wartości logicznych zdań

składowych. Przy czym rozpatruje się tylko złożenia ekstensjonalne, czyli takie których
prawdziwość zależy wyłącznie od wartości logicznych zdań składowych i łączących ich

spójników zdaniowych.

Zmienna zdaniowa (najczęściej oznaczana p, q, r …) jest literą reprezentującą dowolne

zdanie lub inaczej zmienna zdaniowa wskazuje wolne miejsce, które może zostać wypełnione
przez dowolne wyrażenie należące do kategorii zdań.

Wartościowaniem nazywamy funkcję, która każdej zmiennej zdaniowej przyporządkowuje
wartość logiczną 0 lub 1. Funkcję taką można uogólnić na zbiór wszystkich formuł rachunku

zdań.

Tautologią nazywamy formułę, która przy dowolnym wartościowaniu przybiera wartość

logiczną 1.

Wartość logiczna wyrażenia zdaniowego może być wyznaczona za pomocą wartości

logicznych klasycznych funktorów zdaniowych.

Funktorem zdaniowym n-argumentowym (spójnikiem zdaniowym) nazywamy funkcję, która

każdemu układowi (p

1

,p

2

,…,p

n

), gdzie p

i

jest prawdą bądź fałszem, przyporządkowuje

wartość logiczną 0 lub 1.

Istnieje

n

2

2

n-argumentowych funktorów zdaniowych.

Dla n=1 istnieją cztery funktory, nazywamy je funktorami jednoargumentowymi:

A

0

A

1

A

2

A

3

0

0

0

1

1

1

0

1

0

1

Dla n=2 jest szesnaście funktorów, które nazywamy funktorami dwuargumentowymi:

B

0

B

1

B

2

B

3

B

4

B

5

B

6

B

7

B

8

B

9

B

10

B

11

B

12

B

13

B

14

B

15

00 0

0

0

0

0

0

0

0

1

1

1

1

1

1

1

1

01 0

0

0

0

1

1

1

1

0

0

0

0

1

1

1

1

10 0

0

1

1

0

0

1

1

0

0

1

1

0

0

1

1

11 0

1

0

1

0

1

0

1

0

1

0

1

0

1

0

1

Tylko niektóre funktory są używane w systemach logicznych jako odpowiadające spójnikom

zdaniowym występującym w dalszych wnioskowaniach.

I tak funktor jednoargumentowy

A

2

nazywa się negacją (nie) i oznaczamy go „

∼

” lub „

¬

”,

oraz funktory dwuargumentowe:

B

1

nazywa się

koniunkcją

(i, funkcją AND) i oznacza „

∧

”,

B

7

nazywa się

alternatywą

(lub, funkcją OR) i oznacza „

∨

”,

B

9

nazywa się r

ównoważnością

(wtedy i tylko wtedy) i oznacza „

⇔

”,

B

13

nazywa się implikacją (jeżeli … to …) i oznacza „

⇒

”,

B

8

nazywa się strzałką Peirce’a (funktorem jednoczesnego zaprzeczenia) i oznacza „

↓

”,

B

14

nazywa się dysjunkcją (funkcją NAND, funktorem Sheffera, kreską Sheffera) i oznacza

„



”.

Funktory te porządkuje się następująco:

¬

,

∧

,

∨

,

⇒

,

⇔

.

Podstawowe prawa logiki zdań

1. Prawa łączności

(p

∧

q)

∧

r = p

∧

(q

∧

r)

(p

∨

q)

∨

r = p

∨

(q

∨

r)

2. Prawa przemienności

p

∧

q = q

∧

p

p

∨

q = q

∨

p

3. Prawa rozdzielności

(p

∧

q)

∨

r = (p

∨

r)

∧

(q

∨

r)

(p

∨

q)

∧

r = (p

∧

r)

∨

(q

∧

r)

4. Prawa absorpcji (pochłaniania)

p

∧

(p

∨

q) = p

p

∨

(p

∧

q) = p

5. Prawo idempotentności

p

∧

p = p

p

∨

p = p

6. Prawo wyłączonego środka (tertium non datur)

p

∧¬

p = F

p

∨¬

p = P

7. Prawa de Morgana

¬

(p

∧

q) =

¬

p

∨¬

q

¬

(p

∨

q) =

¬

p

∧¬

q

8. Wzory dla P i F

p

∧

P = p

p

∨

F = p

p

∧

F = F

p

∨

P = P

¬

P = F

¬

F = P

9. Podwójne przeczenie (inwolutywność)

¬

(

¬

p) = p

10. Wyrażanie funktorów przez pozostałe

p

⇒

q =

¬

p

∨

q

p

⇔

q = (p

∧

q)

∨

(

¬

p

∧¬

q)

Metody dowodzenia twierdzeń

1. Dowód bezpośredni „wprost”

Przez implikację - metoda ta polega na założeniu, że zdanie

p jest prawdą i pokazaniu, że wówczas również zdanie q jest prawdziwe:

p

⇒

q.

Przez równoważność - metoda ta polega na założeniu, że zdanie p jest prawdą i pokazaniu, że

wówczas również zdanie q jest prawdziwe oraz na założeniu, że zdanie q jest prawdą
i pokazaniu, że wówczas również zdanie p jest prawdą:

p

⇔

q.

2. Dowód „nie wprost”

Metoda dowodu „nie wprost” opiera się na tautologii rachunku zdań, zwanej prawem
kontrapozycji:

( p

⇒

q )

⇔

(

¬

q

⇒

¬

p ).

Stosując tę metodę zakładamy, że q jest fałszem i pokazujemy, że p jest również fałszem.

KWADRAT LOGICZNY

Dla każdej implikacji prostej p

⇒

q

implikację q

⇒

p nazywamy implikacją odwrotną,

implikację

¬

q

⇒

¬

p nazywamy implikacją przeciwstawną,

implikację

¬

p

⇒

¬

q nazywamy implikacją przeciwną.

Na podstawie prawa kontrapozycji widać, że implikacje prosta i przeciwstawna są
równoważne oraz implikacje odwrotna i przeciwna są

równoważne.

Zależności te przedstawia kwadrat logiczny:

Przy tej samej przekątnej są umieszczone implikacje
równoważne, natomiast do udowodnienia wszystkich spośród

tych implikacji, wystarczy udowodnić dowolną parę tych
implikacji umieszczonych na jednym boku kwadratu.

∼

q

⇒∼

p

∼

p

⇒∼

q

p

⇒

q

q

⇒

p

3. Dowód „przez zaprzeczenie” (ad absurdum)

Metoda dowodu przez zaprzeczenie, zwanego też dowodem przez sprowadzeniem do

sprzeczności, opiera się na równoważności:

( p

⇒

q )

⇔

¬

(p

∧

¬

q ).

Stosując to podejście zakładamy, że p jest prawdą a q fałszem i pokazujemy, że prowadzi to
do sprzeczności, to znaczy, że p i nie prawda, że q jest fałszem.

4. Zasada indukcji matematycznej

Niech p(n) będzie zdaniem, które dla każdego naturalnego n może być zdaniem prawdziwym
lub fałszywym. Aby udowodnić, że zdanie p(n) jest prawdziwe dla wszystkich liczb

naturalnych n, gdzie n

≥

n

0

, wystarczy pokazać, że

(i)

zdanie p(n

0

) jest prawdziwe,

(ii)

dla każdego k

≥

n

0

, p(k)

⇒

p(k+1), tzn. zdanie p(k+1) jest prawdziwe jeżeli

tylko zdanie p(k) jest prawdziwe.

5. Dowód konstruktywny

Dowód pewnego twierdzenia o istnieniu obiektu określa się jako konstruktywny, jeżeli podaje
on gotowy algorytm do wyznaczenia poszukiwanego obiektu, o którego istnieniu mówi dane

twierdzenie.

Przykładem takiego dowodu jest podanie algorytmu na istnienie naturalnej sześciennej

funkcji sklejanej, gdzie podaje się wzory pozwalające obliczyć współczynniki takiej funkcji z
układu równań liniowych, co jest elementarnym zadaniem algebraicznym.

AUTOMATYCZNE DOWODZENIE TWIERDZEŃ

Jest to dziedzina wiedzy, której celem jest konstruowanie programów komputerowych

umożliwiających dowodzenie twierdzeń w teoriach, w których zostały sformułowane.

Ponieważ klasyczny rachunek zdań jest rozstrzygalny, więc teoretycznie istnieje algorytm

pozwalający dla dowolnej formuły rachunku zdań w skończonej liczbie kroków rozstrzygnąć,
czy jest ona twierdzeniem tego rachunku.

Wyniki rozważań dotyczących złożoności obliczeniowej wydają się przekreślać możliwość
uzyskania algorytmu, który rozpoznawałby zbiór twierdzeń rachunku zdań zużywając do tego

liczbę kroków wyrażoną zależnością wielomianową od długości formuły.

Nie przekreśla to jednak możliwości konstruowania skutecznych w zastosowaniach

algorytmów, które dotyczą tylko formuł o skończonej długości. Przykładem jest dowód
„problemu czterech barw”.

Rachunek predykatów

Logika predykatów wraz z logiką zdań stanowi całość logiki formalnej.

Logika predykatów dostarcza praw wnioskowania odwołujących się do wewnętrznej budowy
zdań, w której wyróżnia się predykaty (odpowiednik orzeczenia w gramatyce), argumenty

predykatów (odpowiednik podmiotu w gramatyce) oraz wyrażenia zwane kwantyfikatorami
(wskazujące czy predykat odnosi się do wszystkich czy do niektórych argumentów).

W związku z tym logika predykatów często nazywana jest logiką kwantyfikatorów.

UWAGA

Zamiast słowa „logika” mówi się też „teoria” lub „rachunek”.

WYRAŻENIA LOGIKI PREDYKATÓW

Formuła atomowa (forma elementarna) jest to najprostsze zdanie w języku predykatów,

składa się jedynie z predykatu wraz z odpowiednią liczbą argumentów. Dla zmiennych
x

1

, x

2

, ..., x

n

wyrażenie P(x

1

, x

2

, ..., x

n

) jest n-argumentową formułą atomową.

Przykładowo formułami atomowymi są wyrażenia:

jednoargumentowe – „x jest liczbą pierwszą”,

dwuargumentowe - „x dzieli y”.

Formuła atomowa przekształca się w wyrażenie o większym stopniu złożoności, gdy zostanie

poprzedzona kwantyfikatorem

ogólnym

∀

„dla każdego” lub

egzystencjalnym

∃

„dla pewnego”.

Zmienną x określamy jako związaną w pewnym wyrażeniu, jeśli jest zmienną kwantyfikatora

∀

x lub

∃

x, w przeciwnym wypadku jest to zmienna wolna.

Wyrażenie logiki predykatów nazywamy formą zamkniętą, jeżeli nie zawiera żadnych

zmiennych wolnych.

Tautologie logiki predykatów

1.

∼∀

x P(x) =

∃

x

∼

P(x)

∼∃

x P(x) =

∀

x

∼

P(x)

2.

∀

x P(x) =

∼∃

x

∼

P(x)

∃

x P(x) =

∼∀

x

∼

P(x)

3.

∀

x

∀

y P(x,y) =

∀

y

∀

x P(x,y)

4.

∃

x

∃

y P(x,y) =

∃

y

∃

x P(x,y)

5.

∀

x P(x)

∧

∀

x Q(x) =

∀

x [P(x)

∧

Q(x)]

6.

∃

x P(x)

∨

∃

x Q(x) =

∃

x [P(x)

∨

Q(x)]

7.

∀

x P(x)

∨

∀

x Q(x)

⇒

∀

x [P(x)

∨

Q(x)]

8.

∃

x [P(x)

∧

Q(x)]

⇒

∃

x P(x)

∧

∃

x Q(x)

9.

∀

x [P(x)

⇒

Q(x)]

⇒

[

∀

x P(x)

⇒

∀

x Q(x)]

10.

∀

x [P(x)

⇔

Q(x)]

⇒

[

∀

x P(x)

⇔

∀

x Q(x)]

11.

∃

x

∀

y P(x,y)

⇒

∀

y

∃

x P(x,y)

Logika predykatów pierwszego rzędu stanowi system formalny, w którym zmienne zdaniowe

mogą być związane kwantyfikatorami, natomiast w logikach predykatów wyższych rzędów
kwantyfikatorami mogą być związane również zmienne predykatywne.

Każda teoria sformułowana w ramach logiki pierwszego rzędu nazywana jest teorią
elementarną.