1. Rachunek zdań

Będziemy posługiwać się językiem, który składa się ze zdań. Interesuje nas budowa logiczna zdań, tzn. że zdaniom przyporządkowujemy wartości logiczne: prawda lub fałsz.

Funkcją zdaniową nazywamy wyrażenie, które zawiera zmienną przyjmującą wartości z pewnego niepustego zakresu, przy czym po podstawieniu zamiast zmiennej konkretnej wartości otrzymujemy zawsze zdanie prawdziwe lub fałszywe.

f(p) dla p∈X ( p należy do X)

jest funkcją zdaniową jednej zmiennej

Wyrażenie

f(p1…p n) dla pi∈Xi i=1,2….n

jest funkcją zdaniową n-zmiennych.

Zmienna w funkcji zdaniowej może przyjmować wartości, które są zdaniami, wtedy mówimy o zmiennej zdaniowej.

Jeżeli p,q są zdaniami to przy pomocy tzw. funktorów zdaniotwórczych

♦ koniunkcja ∧ („oraz”)

♦ implikacja ⇒ („implikuje”)

♦ alternatywa ∨ („lub”)

♦ równoważność ⇔ („wtedy i tylko wtedy”)

można tworzyć zdania złożone. Natomiast jeżeli p,q są zmiennymi zdaniowymi to przy pomocy funktorów zdaniotwórczych można tworzyć funkcji zdaniowe.

♦ koniunkcję p ∧ q

♦ implikację p ⇒ q

♦ alternatywę p ∨ q

♦ równoważność p ⇔ q

1

Wartości logiczne funkcji zdaniowych

♦ koniunkcję p ∧ q

p/q

1

0

1

1

0

0

0

0

♦ implikację p ⇒ q

p/q

1

0

1

1

0

0

1

1

♦ alternatywę p ∨ q

p/q

1

0

1

1

1

0

1

0

♦ równoważność p ⇔ q

p/q

1

0

1

1

0

0

0

1

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

Potwierdzenie zdania p to zdanie p.

Negacja zdania p to zdanie „nie p”.

Negację zdania p będziemy ozn. przez p’

Mówimy, że zdanie p jest warunkiem koniecznym dla zdania q, jeżeli jest prawdziwe zdanie q ⇒ p

Mówimy, że zdanie p jest warunkiem dostatecznym dla zdania q jeżeli jest prawdziwe zdanie p ⇒ q

Mówimy, że zdanie p jest warunkiem koniecznym i dostatecznym dla zdania q jeżeli jest prawdziwe zdanie p ⇔ q

Zmierzanie do zera wyrazów ciągu (an) jest warunkiem koniecznym, ale nie jest

∞

warunkiem dostatecznym, na to, by suma ∑ ak była liczbą skończoną k =1

2

Funkcja zdaniowa, która po podstawieniu w miejsce zmiennych, zdań o dowolnej wartości logicznej jest zawsze zdaniem prawdziwym nazywamy tautologią.

Przykłady tautologii:

1. Prawo transpozycji

(q’ ⇒ p’) ⇔ (p ⇒ q)

2. Prawo sylogizmu

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

3. Prawa de Morgana

(p ∧ q) ’ ⇔ (p’ ∨ q’)

(p ∨ q)’ ⇔ (p’ ∧ q’)

4. (p ⇒ q)’ ⇔ (p ∧ q’)

Sprawdzenie, czy funkcja zdaniowa jest tautologiczna dokonujemy tzw. metodą prób zerojedynkowych, która polega na zbadaniu wszystkich możliwych przypadków wartości logicznych zdań podstawianych w miejsce zmiennych.

2. Rachunek kwantyfikowany

Niech p(x) będzie funkcją zdaniową zmiennej x z pewnego niepustego zakresu X.

∃

Kwantyfikatorem szczegółowym nazywamy słowo „istnieje” ozn.

∀

Kwantyfikatorem ogólnym nazywamy słowo „dla każdego” ozn.

∃

∀

Wyrażenia

p(x) oraz

p(x) są zdaniami.

3

Zdanie, w którym kilka kwantyfikatorów poprzedza funkcję zdaniową, negujemy zamieniając kwantyfikatory szczegółowe na ogólne, a ogólne na szczegółowe i negując funkcję zdaniową. Na ogół nie zmieniamy miejsc kwantyfikatorów.

Kolejność kwantyfikatorów można zmieniać w następujących przypadkach:

∀ ∀ p( x, y) ⇔ ∀ ∀ p( x, y) x∈ X y Y

∈

y Y

∈ x∈ X

∃ ∃ p( x, y) ⇔ ∃ ∃ p( x, y) x∈ X y Y

∈

y Y

∈ x∈ X

Równoważność przy zmianie kwantyfikatora ogólnego i szczegółowego nie jest prawdziwa.

Jest słuszna implikacja.

∃ ∀ p( x, y) ⇒ ∀ ∃ p( x, y) y Y

∈ x∈ X

x∈ X y Y

∈

Niech będzie dana funkcja zdaniowa p(x) dla x∈X , w pewnych przypadkach budując

z p(x) zdanie, zawężamy zakres zmienności x, tzn. jeżeli bierzemy pod uwagę tylko te x∈X dla których jest prawdą q(x)

wtedy

∀ p( x) ⇔ (∀ ( q( x) ⇒ p( x))) q( x)

x∈ X

∃ p( x) ⇔ ( ∃ ( q( x) ∧ p( x))) q( x)

x∈ X

4

Kwantyfikatory

∀

∃

q( x)

q( x)

to tzw. kwantyfikatory o ograniczonym zakresie.

Przykład

Zdanie: nieprawda jest, że ciąg (an), gdzie an∈ℜ , dla n=1,2,3…..ma granicę g∈ℜ zapisujemy następująco

 ∀ ∃

∀

( n〉 N ⇒ a − g 〈ε

n

)



'⇔

ε〉0 N〉0 ∈

n N = ,

1

{ 2,3...}



⇔ ∃ ∀ ∃ ( n〉 N ⇒ a − g 〈ε

n

)'⇔

ε 〉0 N 〉0 ∈

n N

(p=>q)’(p ∧ q’)

⇔ ∃ ∀ ∃ ( n〉 N ∧ a − g ≥ ε

n

0 )

ε 〉0 N 〉0 ∈

n N

5