dr Przemysław Szczepaniak

Logika dla informatyków

wykład 1

RACHUNEK ZDAŃ

JĘZYK. Na język rachunku zdań składają się zmienne zdaniowe p 0 , p 1 , p 2 , ... , spójniki logiczne ¬, ∧, ∨, −→, ←→ oraz symbole nawiasów.

Wymienione spójniki nazywamy odpowiednio: negacją, koniunkcją, alterna-tywą, implikacją, równoważnością.

Definicja 1. (Zdanie).

- zmienne zdaniowe są zdaniami,

- jeśli ϕ, ψ są zdaniami, to ( ¬ϕ) , ( ϕ∧ψ) , ( ϕ∨ψ) , ( ϕ −→ ψ) , ( ϕ ←→ ψ) też,

- innych zdań nie ma.

Często zamiast zmiennych pi do budowy zdań używać będziemy liter p, q, r, przy czym przyjmujemy, że p = p 0, q = p 1, r = p 2. Aby zredukować liczbę nawiasów w zdaniach przyjmujemy, że spójniki ∧ oraz ∨ wiążą zdania silniej niż −→ oraz ←→, a najsilniejszym spójnikiem jest ¬. Na przykład w zdaniu (( p∧( ¬q)) −→ r) nawiasy możemy pominąć i pisać p∧¬q −→ r, ponieważ w tym przypadku możemy z wersji bez nawiasów odtworzyć zdanie z nawiasa-mi, bo negacja dotyczy tylko zdania q, koniunkcja łączy zdania p oraz ¬q, a implikacja łączy zdania p∧¬q oraz r.

Cyfry 0 i 1 to wartości logiczne, interpretowane odpowiednio jako fałsz i prawda. Na zbiorze { 0 , 1 } wprowadzamy działania and, or, imp, iff , not: x

y

and(x,y) or(x,y) imp(x,y) iff(x,y)

0

0

0

0

1

1

x

not(x)

0

1

0

1

1

0

0

1

1

0

0

1

0

0

1

0

1

1

1

1

1

1

Definicja 2. (Wartościowanie). Niech v = ( v 0 , v 1 , v 2 , v 3 , ... ) będzie ustalonym ciągiem wartości logicznych. Określamy wartościowanie ¯

v dowolnego zdania:

- ¯

v( pi) = vi,

- jeśli ϕ i ψ są zdaniami i ¯

v( ϕ) , ¯

v( ψ) są już określone, to:

- ¯

v( ¬ϕ) = not(¯

v( ϕ)) ,

- ¯

v( ϕ∧ψ) = and(¯

v( ϕ) , ¯

v( ψ)) ,

- ¯

v( ϕ∨ψ) = or(¯

v( ϕ) , ¯

v( ψ)) ,

1

- ¯

v( ϕ −→ ψ) = imp(¯

v( ϕ) , ¯

v( ψ)) ,

- ¯

v( ϕ ←→ ψ) = iff (¯

v( ϕ) , ¯

v( ψ)) .

Ciąg v ustala więc wartości logiczne najprostszych zdań, czyli zmiennych zdaniowych. Wartościowanie określa, przy danym ciągu v, wartości logiczne zdań złożonych.

PRZYKŁAD. Niech ϕ = p∧¬q −→ r oraz v = (0 , 1 , 0 , 1 , 0 , 1 , ... ). Chcemy wyznaczyć wartość ¯

v( ϕ). Obliczamy:

¯

v( ϕ) = ¯

v( p∧¬q −→ r) =

imp(¯

v( p∧¬q) , ¯

v( r)) =

imp(and(¯

v( p) , ¯

v( ¬q)) , ¯

v( r)) =

imp(and(¯

v( p) , not(¯

v( q))) , ¯

v( r)) =

imp(and(0 , not(1)) , 0) =

imp(and(0 , 0) , 0) =

imp(0 , 0) = 1.

Definicja 3. (Tautologia). Zdanie ϕ jest tautologią jeśli ¯

v( ϕ) = 1 dla dowol-

nego ciągu wartości logicznych v.

Tautologie są zatem takimi zdaniami, które są prawdziwe, niezależnie od tego

jakie wartości logiczne przyjmują zmienne zdaniowe, z których są zbudowane.

Przykładem może być zdanie p∨¬p, którego prawdziwość jest tak oczywista jak to, że jutro będzie lub nie będzie padać deszcz. Zapisem |= ϕ oznaczać będziemy, że ϕ jest tautologią.

PODSTAWOWE TAUTOLOGIE. Z niektórych tautologii będziemy często

korzystać. Przedstawiamy te podstawowe:

p∧q ←→ q∧p (przemienność),

p∨q ←→ q∨p (przemienność),

p∧( q∧r) ←→ ( p∧q) ∧r (łączność),

p∨( q∨r) ←→ ( p∨q) ∨r (łączność),

p∧( q∨r) ←→ ( p∧q) ∨( p∧r) (rozdzielność), p∨( q∧r) ←→ ( p∨q) ∧( p∨r) (rozdzielność),

¬( p∧q) ←→ ¬p∨¬q (prawo de Morgana),

¬( p∨q) ←→ ¬p∧¬q (prawo de Morgana),

( p −→ q) ∧ ( q −→ r) −→ ( p −→ r) (przechodniość implikacji), ( p −→ q) ←→ ( ¬p∨q) (eliminacja implikacji),

2

( p −→ q) ←→ ( ¬q −→ ¬p) (kontrapozycja),

( p ←→ q) ←→ ( p −→ q) ∧( q −→ p) (eliminacja równoważności), p∧( p −→ q) −→ q (reguła odrywania).

METODA ZERO-JEDYNKOWA. Jak można sprawdzić czy dane zdanie jest

tautologią? Ponieważ każde zdanie jest zbudowane ze skończeniu wielu zmien-

nych zdaniowych, wystarczy rozważyć wszystkie przypadki wartości logicz-

nych jakie te zmienne mogą przyjąć. Robimy to za pomocą tabeli. Na przy-

kład udowodnijmy prawo eliminacji implikacji:

p

q

¬p

¬p ∨ q

p −→ q

( p −→ q) ←→ ( ¬p ∨ q)

0

0

1

1

1

1

0

1

1

1

1

1

1

0

0

0

0

1

1

1

0

1

1

1

Same jedynki w ostatniej kolumnie kończą dowód. Oczywiście jeśli w ostatniej

kolumnie pojawi się choć jedno zero, to rozważane zdanie nie jest tautologią.

Aby sprawdzić tą metodą czy zdanie zbudowane na przykład z trzech zmien-

nych zdaniowych jest tautologią rozważamy aż 23 = 8 przypadków.

ZASTOSOWANIE TAUTOLOGII. Tautologie wykorzystujemy przy dowo-

dzeniu twierdzeń. Typowe twierdzenie ma postać implikacji Z −→ T , tzn.

mówi, że jeśli założenie Z jest spełnione, to teza T też. Czasem Z jest koniunkcją kilku założeń. Twierdzenie można niekiedy dowodzić wprost, tzn. z

założenia Z jakoś wywnioskować tezę T .

PRZYKŁAD. Udowodnimy, że „ jeśli n jest parzyste, to n 2 też jest parzyste dla dowolnej liczby całkowitej n”.

Ustalmy n i załóżmy, że n jest parzyste. To oznacza, że n = 2 k dla pewnej liczby całkowitej k. Zatem n 2 = 4 k 2 = 2(2 k 2), więc widzimy, że n 2 jest parzyste.

Czasem przeprowadzamy dowód oparty na prawie kontrapozycji. Takie do-

wody zaliczane są do tzw. dowodów nie wprost.

PRZYKŁAD. Udowodnimy, że „ jeśli n 2 jest parzyste, to n też dla dowolnej liczby całkowitej n”.

3

Korzystając z prawa kontrapozycji wystarczy z tego, że n nie jest parzyste wywnioskować, że n 2 też nie jest parzyste. Ustalmy zatem n i załóżmy, że n jest nieparzyste. To znaczy, że n = 2 k − 1 dla pewnej liczby całkowitej k. Zatem n 2 = 4 k 2 − 4 k + 1 = 2(2 k 2 − 2 k) + 1, więc n 2 jest też nieparzyste.

W dwóch ostatnich przykładach udowodniliśmy twierdzenie „ n jest parzyste wtedy i tylko wtedy, gdy n 2 jest parzyste dla dowolnej liczby całkowitej n”, pokazując prawdziwość implikacji w obie strony (prawo eliminacji równoważ-

ności).

Twierdzenia możemy też dowodzić nie wprost przez sprowadzanie do sprzecz-

ności. Przypuszczamy, że teza jest fałszywa, ale założenie prawdziwe. Je-

śli poprawnie wywnioskujemy stąd sprzeczność (zdanie fałszywe), będzie to

oznaczać, że przypuszczenie o fałszywości tezy było fałszywe, czyli że teza

jest prawdziwa. Tautologia ( p −→ q) ←→ ( p∧¬q −→ r∧¬r) uzasadnia po-prawność dowodów tego typu.

PRZYKŁAD. Udowodnimy, że „ jeśli a 2 = 2, to a jest niewymierne”.

Przypuśćmy, że a 2 = 2 i a jest wymierne. Zatem a = k dla pewnych liczb n

całkowitych k, n. Możemy założyć, że ułamek k jest nieskracalny (został

n

skrócony). Ponieważ 2 = a 2 = k 2 , więc 2 n 2 = k 2. Stąd k 2 jest parzyste, n 2

zatem k też jest parzyste. To znaczy, że k = 2 l dla pewnej liczby całkowitej l. Wtedy 2 n 2 = (2 l)2, czyli 2 n 2 = 4 l 2, czyli n 2 = 2 l 2. Stąd widzimy, że n 2

jest parzyste, więc n jest parzyste. Zatem ułamek k można skrócić przez 2.

n

Otrzymaliśmy więc sprzeczność, bo ułamek k jest nieskracalny.

n

4