Podstawy logiki matematycznej

1

Zdanie

Oznaczenia:

∈ - należy do..
N = {1, 2, 3, 4, ...} - zbiór liczb naturalnych
Z = {..., −3, −2, −1, 0, 1, 2, 3, 4, ...} - zbiór liczb całkowitych
Q = {

w

r

: w, r ∈ Z} - zbiór liczb wymiernych

R - zbiór liczb rzeczywistych

Definicja 1 Zdaniem w logice matematycznej nazywamy każde sensowne stwierdze-
nie, które jest albo prawdziwe albo fałszywe, i które nie może być jednocześnie praw-
dziwe i fałszywe.

Rachunek zdań polega na badaniu związków logicznych między zdaniami.

Przyklad 1 Te stwierdzenia są zdaniami:

a) 2+2=4
b) 2+2=5
c) Warszawa jest stolicą Polski
d) Liczba π jest ujemna a liczba 2 dodatnia
e) x + y = x − y dla wszystkic x, y ∈ R

Przyklad 2 Te nie są:

a) To moje czy Twoje jabłko?
b) Idź po chleb.
c) Matematyka jest zabawna.
d) x − y = y − x

Zdania oznaczamy literami p, q, r, ...

Niech w(p) oznacza wartośc logiczną zdania p. Wtedy:

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

1

2

Funktory zdaniotwórcze (spójniki międzyzdaniowe)

Za pomocą funktorów tworzymy zdania złożone.

funktor

nazwa

czytamy

inne oznaczenia

∼ p

zaprzeczenie

nie p ( nieprawda, że p)

−p, p

0

, ¬p

p ∧ q

koniunkcja

p i q

·, AND, &, &&

p ∨ q

alternatywa

p lub q

+, OR, ||

p ⇒ q

implikacja

jeśli p to q (z p wynika q)

→

p ⇔ q

ekwiwalencja p wtedy i tylko wtedy gdy q (równoważne) ↔, ≡

Do zdefiniowania funktorów używamy tabelek logicznych (matryc).

p q

∼ p p ∧ q p ∨ q p ⇒ q p ⇔ q

1

1

0

1

1

1

1

1

0

0

1

0

0

0

1

1

0

1

1

0

0

0

0

0

1

1

Uwaga. Implikacja jest fałszywa tylko wtedy gdy zdanie p (poprzednik) jest prawdziwe
a zdanie q (następnik) fałszywe.

Przy pomocy funktorów i nawiasów możemy tworzyć formuły bardziej złożone:

∼ (p ∧ q)

∼ p ⇒ (q ∧ p)

(p ∨ q) ⇔ [(p ∧ (∼ p)) ∨ r]

Uwaga. Nawiasy można opuszczać przyjmując, że funktory są uporządkowane od najsil-
niejszego do najsłabszego ∼, ∧, ∨, ⇒, ⇔ . Po opuszczeniu niepotrzebnych nawiasów
ostatnie zdanie będzie wyglądać tak:

p ∨ q ⇔ (p∧ ∼ p) ∨ r.

2

3

Tautologie (prawa logiki)

Definicja 2 Tautologią nazywamy każdą formułę zdaniową która jest prawdziwa dla
wszystkich możliwych wartości logicznych zdań z których jest złożona.

Przyklad 3 Stwierdzić czy zdanie jest tautologią:

a) (∼ p ⇒ p) ⇒ p

p ∼ p ∼ p ⇒ p (∼ p ⇒ p) ⇒ p

1

0

1

1

0

1

0

1

Odp. JEST tautologią. (jest to prawo Claviusa)

b) ∼ (p ∧ q)

p q

p ∧ q ∼ (p ∧ q)

1

1

1

0

1

0

0

1

0

1

0

1

0

0

0

1

Odp. NIE jest tautologią.

3

Twierdzenie 1 Najważniejsze prawa logiki

1.

∼∼ p ⇔ p

prawo podwójnego zaprzeczenia

2.

∼ (p∧ ∼ p)

prawo sprzeczności

3.

p∨ ∼ p

prawo wyłączonego środka (tertium non datur)

4.

p ∧ q ⇔ q ∧ p

prawa przemienności 2 + 3 = 3 + 2

p ∨ q ⇔ q ∨ p

5.

p ∨ (q ∨ r) ⇔ (p ∨ q) ∨ r

prawa łączności 2 + (3 + 4) = (2 + 3) + 4

p ∧ (q ∧ r) ⇔ (p ∧ q) ∧ r

6.

p ∨ (q ∧ r) ⇔ (p ∨ q) ∧ (p ∨ r)

prawa rozdzielności

p ∧ (q ∨ r) ⇔ (p ∧ q) ∨ (p ∧ r)

2 · (3 + 4) = 2 · 3 + 2 · 4

7.

∼ (p ∨ q) ⇔ ∼ p∧ ∼ q

prawa De Morgana

∼ (p ∧ q) ⇔ ∼ p∨ ∼ q

8.

p ⇒ p

prawo tożsamości

9.

[(p ⇒ q) ∧ (q ⇒ p)] ≡ (p ⇔ q)

określenie równoważności

10. [(p ⇒ q) ∧ (q ⇒ r)] ⇒ (p ⇒ r)

przechodniość ⇒

11.

∼ (p ⇒ q) ≡ p∧ ∼ q

określenie implikacji za pomocą koniunkcji

12.

p ⇒ q ≡ ∼ p ∨ q

lub alternatywy

13.

p ⇒ q ≡ ∼ q ⇒∼ p

prawo kontrapozycji

14.

p ⇒ (p ∨ q)

wprowadzanie alternatywy

15.

(p ∧ q) ⇒ p

opuszczanie koniunkcji

Przyklad 4 Udowodnić prawo Pierce’a [((p ⇒ q) ⇒ p] ⇒ p

p q

p ⇒ q (p ⇒ q) ⇒ p [(p ⇒ q) ⇒ p] ⇒ p

1

1

1

1

1

1

0

0

1

1

0

1

1

0

1

0

0

1

0

1

4

4

Predykaty. Kwantyfikatory.

Definicja 3 Predykat (funkcja zdaniowa) jest to wyrażenie, które zawiera zmienną
przebiegającą pewien zbiór (zakres zmienności). Jeśli podstawimy za zmienną dowolną
wartoś z tego zbioru to otrzymamy zdanie.

Przyklad 5 Predykaty:

a) x + 3 = 5 dla każdego rzeczywistego x,
b) n + 5 > 10 dla 5 < n < 20,
c) 2|n dla n ∈ N.

Niech φ(x) dowolna funkcja zdaniowa, a X zakres zmienności zmiennej x.

Definicja 4 Kwantyfikator ogólny
Jeśli funkcja zdaniowa φ(x), x ∈ X jest prawdziwa DLA KAŻDEGO elementu
zakresu zmienności to piszemy:

^

x∈X

φ(x)

lub

∀

x∈X

φ(x)

lub krócej

^

x

φ(x),

∀

x

φ(x).

i czytamy: "dla każdego x należącego do X zachodzi φ(x)".

Definicja 5 Kwantyfikator szczegółowy
Jeśli funkcja zdaniowa φ(x), jest prawdziwa DLA CO NAJMNIEJ JEDNEGO
elementu zbioru X to piszemy:

_

x∈X

φ(x)

lub

∃

x∈X

φ(x)

lub krócej

_

x

φ(x),

∃

x

φ(x).

i czytamy: "istnieje x należący do X, dla którego zachodzi φ(x)".

Definicja 6 :
Jeśli funkcja zdaniowa φ(x), jest prawdziwa DLA DOKŁADNIE JEDNEGO elementu
zbioru X to piszemy:

_

x

!φ(x),

∃!

x

φ(x).

i czytamy: "istnieje dokładnie jeden x należący do X taki, że zachodzi φ(x)".

Przyklad 6

a)

^

a∈Z

a

2

> 0

b)

_

x

^

y

x + y = 0

c)

^

y

_

x

x + y = 0

5

5

Prawa działań na kwantyfikatorach

X- zakres zmienności zmiennej x

Twierdzenie 2 Prawa De Morgana

∼

³ ^

x∈X

φ(x)

´

≡

_

x∈X

¡

∼ φ(x)

¢

∼

³ _

x∈X

φ(x)

´

≡

^

x∈X

¡

∼ φ(x)

¢

φ(x), ψ(x)- formuły zdaniowe

Twierdzenie 3

^

x∈X

¡

φ(x) ∧ ψ(x)

¢

≡

^

x∈X

φ(x) ∧

^

x∈X

ψ(x)

_

x∈X

¡

φ(x) ∨ ψ(x)

¢

≡

_

x∈X

φ(x) ∨

_

x∈X

ψ(x)

Twierdzenie 4

^

x∈X

¡

φ(x) ∨ ψ(x)

¢

⇐

^

x∈X

φ(x) ∨

^

x∈X

ψ(x)

_

x∈X

¡

φ(x) ∧ ψ(x)

¢

⇒

_

x∈X

φ(x) ∧

_

x∈X

ψ(x)

Przyklad 7 Zanegować zdanie p:

p :=

^

x

(2|x ∧ x > 6)

tak, żeby nie było znaku negacji.

Rozwiązanie:
Korzystamy z praw De Morgana dla kwantyfikatorów i zdań:

∼ p ≡∼

^

x

(2|x ∧ x > 6) ≡

_

x

∼ (2|x ∧ x > 6) ≡

≡

_

x

∼ (2|x)∨ ∼ (x > 6) ≡

_

x

(2 - x) ∨ (x 6 6)

6