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