Scan0016 (2)

24 Tautologie. Wynikanie logiczne. Systemy dowodzenia

Przykład 2.4 Rozpatrujemy fomuły A\, A2, A₃ podane w tablicy:

p	Q	> II *C3	A2 = ~ p V q	A3 = ~p
0	0	0	1	1
0	1	0	1	1
1	0	1	0	0
1	1	□	0	0

Widać, że zbiór U\ = {A\,A2} jest spelnialny, zaś U2 = {A\, A2, A₃} nie jest spelnialny. Zauważmy, że każda formuła A{ ze zbioru U2 jest spełnialna, lecz zbiór U2 nie jest jednocześnie spelnialny.

Definicja 2.4 Formułę B nazywamy konsekwencja, logiczną zbioru U, jeśli w każdym modelu U wartością B jest 1. Mówimy również, że U implikuje logicznie B lub, że B wynika logicznie z U i zapisujemy

U \= B.

Przykład 2.5 Czy {p,p => q] f= q ?

p	Q	Ai =p	A2=P=> q	B = q
0	0	0	1	0
0	1	0	1	1
1	0	1	0	0
1	1	0	0	0

Tak, zbiór {p,p => q] implikuje logicznie q.

Uwaga 2.2 Formula B w przykładzie 2.5 nie jest tautologią. Wystarczy, że ma wartość 1 w interpretacjach, które spełniają zbiór U.

Zachodzi następujące twierdzenie.

Twierdzenie 2.3 Jeśli wszystkie formuły zbioru U są tautologiami, to również formuła B jest tautologią.

2.3.1 Reguły wnioskowania

Konsekwencje logiczne zapisujemy również w postaci schematu zwanego regułą wnioskowania (dowodzenia):

A\,..., A_n ~~B    ’