04.pdf

1.3.WYNIKANIESYNTAKTYCZNEAWYNIKANIE

SEMANTYCZNE

1.3.1. Pełność rachunku zdań

(DEF.modeluzbioruzdań) M jest modelemzbioruzdań Σ ,cozapi-

sujemy:

=Σ

wtedyitylkowtedy,gdykażdezdaniezezbioru Σ jestprawdziwew

M ;czyligdydlakażdego α :

jeżeli α ∈ Σ ,to M| = α .

Ozbiorze Σ mówimy,żejest spełniony w M .

TWIERDZENIE14.(UOGÓLNIONETWIERDZENIEOPEŁNO-

ŚCI).

Zbiórzdań Σ jestniesprzecznywtedyitylkowtedy,gdyjestspeł-

nionywjakimśmodelu.

DOWÓD

Nadowodzonetwierdzenieskładająsiędwietezy.

(A) Jeżeli Σ mamodel,tojestniesprzeczne

(B) Jeżeli Σ jestniesprzeczne,tomamodel.

Rozpocznijmy od dowodu tezy (A). Pokażmy wpierw, że każde

zdaniemającedowódz Σ jestprawdziwewmodelu Σ .

Załóżmy, że Σ ma model. Niech więc dla pewnego M , M| =Σ .

Pokażemy,żekażdezdanie α ,któremadowódz Σ jestprawdziwew

modelu M ;czyli,żedlakażdego α :jeżeli Σ α ,to M| = α .Niech α

będziedowolnymzdaniemmającymdowódz Σ .Niech α 0 ,α 1 ,...,α n (=

) będzie dowodem tego zdania ze zbioru Σ . Dowiedziemy, że dla

każdego i, 0 ≤ i ≤ n , M| = α i .Wszczególności dla i = n dostaniemy,

że α n (= α ) jestprawdziwew M .Dowodzićbędziemyprzezindukcję

podługościdowodu.

1. KLASYCZNALOGIKAZDAŃ

Zdeﬁnicjidowoduwiadomo,że α 0 jestbądźtautologią,bądźele-

mentemzbioru Σ .Gdy α 0 jesttautologią,toztwierdzeniaopełności

otrzymujemy,że α 0 jestprawdziwew M .Gdy α 0 należydo Σ ,tojest

prawdziwew M zzałożeniadowodu.

ZAŁOŻENIEINDUKCYJNE:Niech M| = α i ,i ≤ k<n .

Pokażemy,że

α k +1 .

Gdy α k +1 jest tautologią lub elementem zbioru Σ , to postępu-

jemyjakwwypadku α 0 .Niechwięc α k +1 będzieuzyskaneprzezza-

stosowanie reguły odrywaniadozdań α l ,α m (= α l ⇒ α k +1 ) ; l,m ≤ k .

Z założenia indukcyjnego α l , α m są prawdziwe w modelu M , czyli

α l ,α l ⇒ α k +1 .Zdeﬁnicjiprawdziwościwmodeluzdańopostaci

implikacji M| = α l ⇒ α k +1 , jeżeli M| = α l lub M| = α k +1 .Ponieważ

α l ,więc M| = α k +1 ,czyliże α k +1 jestprawdziwewmodelu M .

Pokazaliśmy więc,żekażdezdaniemającedowódzezdańpraw-

dziwychw M jestprawdziwew M .Gdyby Σ byłosprzeczne,toz Σ

miałoby dowód zdanie p 0 ∧¬ p 0 . Zdanieto zaś niejest prawdziwew

żadnym modelu, a więc nie jest prawdziwe w modelu M .Ponieważ

wszystkiezdaniamającedowódz Σ sąprawdziwew M ,zatemzdanie

p 0 ∧¬ p 0 niemadowoduz Σ ,więc Σ niejestsprzecznymzbioremzdań.

Abydowieśćtezy(B)załóżmy,że Σ jestniesprzecznymzbiorem

zdań.Pokażemy,że Σ mamodel.NapodstawielematuLindenbauma

stwierdzamy, że istnieje niesprzeczny maksymalny zbiór Γ zawiera-

jący Σ .Niech M będziezbiorem wszystkich liter zdaniowych, które

sąelementami Γ .Dowiedziemy,żedlakażdego α :

(C)

Γ wtedyitylkowtedy,gdy M| = α 58 .

Dowód przeprowadzamy przez indukcję po długości zdania. W do-

wodziekorzystaćbędziemyztwierdzenia13.Jeżeli α jestliterązda-

niową,to(C)zachodzinapodstawieokreśleniamodelu M .

α ∈

58 Dla samej dowodzonej tezy wystarczyłoby tylko tyle, że jeżeli

α ∈

Γ to

. Dowodzimy jednak więcej, czyli również tego, że jeżeli

,to

α ∈

Γ . Ta teza, a raczej teza jej równoważna: jeżeli

α ∈

Γ ,to

M |

jest

bowiemwykorzystywanadlaprzeprowadzeniainteresującegonasdowodu.

1.3. WYNIKANIE SYNTAKTYCZNEAWYNIKANIE SEMANTYCZNE

ZAŁOŻENIEINDUKCYJNE:Niech(C)zachodzidla β i γ .

Pokażemy,że(C)zachodzidlazdańzłożonychzbudowanychzezdań

β i γ .

( ¬ ). Załóżmy, że ¬ β ∈ Γ .Ponieważ Γ jest zbiorem maksymalnym

niesprzecznym,więc β nienależydo Γ .Zgodniezzałożenieminduk-

cyjnymniezachodzi M| = β ,azatemzachodzi M| = ¬ β .

Załóżmy,że ¬ β nienależydo Γ .Zmaksymalności Γ otrzymujemy,

że β ∈ Γ .Zzałożeniaindukcyjnego M| = β .Zatemniezachodzi M| =

¬ β .

( ⇒ ).Załóżmy,że β ⇒ γ ∈ Γ .Zatembądź ¬ β ∈ Γ ,bądź γ ∈ Γ ,awięc

bądźniezachodzi M| = β ,bądźzachodzi M| = γ .Napodstawietego

zaśstwierdzamy,że M| = β ⇒ γ .

Załóżmy,żezachodzi M| = β ⇒ γ .Azatem bądźzachodzi M| =

γ , bądź nie zachodzi M| = β . Korzystamy z założenia indukcyjnego

i dostajemy, że bądź γ należy do Γ ,bądź β nie należy do Γ .Na

podstawietwierdzenia13otrzymujemywięc,że β ⇒ γ należydo Γ .

Dowody dlapozostałych spójników jako przebiegające wanalo-

gicznysposóbpomijamy.

Dowiedliśmy,że M| =Γ .Ponieważ Σ ⊆ Γ ,więc M| =Σ .

1.3.2. Wynikanie semantyczne

Dotychczas mówiliśmy o rzeczywistym stosunku wynikania nie

precyzująctego,czymjesttenstosunek.Zdeﬁniowanewynikanierze-

czywistebędziemyokreślaćjakowynikaniesemantyczne.

(DEF. | = )Zdanie α wynikasemantyczniez Σ (jestnastępstwemzdań

z Σ ,zdaniaz Σ sąracjami α ) ,cozapisujemy:

α ,

wtedyitylkowtedy,gdydlakażdegomodelu M :

jeżeli M| =Σ ,to M| = α ,

czyliwkażdymmodelu,wktórymprawdziwesąwszystkiezdaniaz

1. KLASYCZNALOGIKAZDAŃ

Σ ,prawdziwejestrównieżzdanie α 59 .

Wnioskiemzuogólnionegotwierdzeniaopełnościjest,że

TWIERDZENIE15.

α wtedyitylkowtedy, gdy Σ α ,

czyli α wynikasemantyczniezezbioru Σ wtedyitylkowtedy,gdy

wynikaztegozbiorusyntaktycznie.

DOWÓD

Dowód będzieskładałsię zdwóchczęści. Wpierwudowodnimy,

że:

(A) jeżeli Σ | = α ,to Σ α ,

anastępnie,że:

(B) jeżeli Σ α ,to Σ | = α .

Obu zdań (A) i (B) dowodzić będziemy niewprost, czyli poka-

żemy,żezałożeniezdaniasprzecznegozezdaniemdowodzonympro-

wadzidosprzeczności.Jakwiemyzrachunkuzdańzdaniemsprzecz-

nymzezdaniem: α ⇒ β jestzdanie: α ∧¬ β . Taksamoprzyjmujemy

na poziomie rozumowania intuicyjnego. W wypadku (A) założymy

więc,że Σ | = α inieprawda,że Σ α ;zaśwwypadku(B),że Σ α i

nieprawda,że Σ | = α .Wobuwypadkachpokażemy,żeotrzymujemy

sprzeczność.

(A) Niech Σ | = α iniechniezachodzi Σ α .Ztego,żeniezachodzi

59 Deﬁnicjęwynikaniasemantycznegopodał(używałonterminu:wynikanielo-

giczne)K.Ajdukiewicz[1934].DeﬁnicjasformułowanaprzezA.Tarskiego[1935]

–dziśpowszechnieprzyjęta,równieżwniniejszejksiążce–jestogólniejszawtym

sensie, że pozwala mówić o wynikaniu z nieskończonej klasy zdań. Podobną do

niej deﬁnicję podał w pierwszej połowie XIX w. B. Bolzano. Pierwsze w histo-

rii logiki próby określenia wynikania pochodzą od logików XIII–XV w., którzy

mówiąo„konsekwencjiformalnej”(odróżniającjąodkonsekwencjimaterialnej).

AlbertSaksończykkonsekwencjęformalnąokreślajakotakąformęwnioskowania,

że każde wnioskowanie o tej formie od prawdziwych przesłanek nie prowadzi do

fałszywego wniosku. Wcześniejsze podobne określenie znajdujemy np. u Dunsa

Szkota.

α napodstawietwierdzenia10mamy,żezbiór Σ ∪{¬ α } jestnie-

sprzeczny. Na podstawie uogólnionego twierdzenia o pełności zbiór

1.3. WYNIKANIE SYNTAKTYCZNEAWYNIKANIE SEMANTYCZNE

α ,więczgodniezdeﬁnicjąwynikaniasemantycznegoistniejemo-

del M taki,żewszystkiezdaniaz Σ sąprawdziwe,a α niejestpraw-

dziwew M .Zatemzgodniezwłasnościamimodelumamy,że M| = ¬ α ,

czyli M jestmodelemzbioruzdań Σ ∪{¬ α } .Napodstawieuogólnio-

negotwierdzeniaopełnościzbiór Σ ∪{¬ α } jestniesprzeczny. Zatem

zgodnie z lematem Lindenbauma istnieje maksymalny niesprzeczny

nadzbiórtegozbioru.Niech Γ będzietymmaksymalnymniesprzecz-

nymnadzbiorem. α nienależydo Γ ,zczegonapodstawiewłasności

zbioru maksymalnego niesprzecznego mamy, że nie zachodzi Γ α .

Ponieważ Σ ⊆ Γ więc napodstawietwierdzenia owłasnościach ope-

racjikonsekwencji[przypomnijmy:jeżeli Σ ⊆ Σ 1 ,to Cn (Σ) ⊆ Cn (Σ 1 ) ;

czyli: gdy Σ ⊆ Σ 1 , to jeżeli Σ α ,to Σ 1 α ] również nie zachodzi

α ,cojestwbrewzałożeniu.Zatemjeżeli Σ α ,to Σ | = α .

Twierdzeniepowyższepozwaladlajęzykaklasycznejlogikizdań

(czylidlajęzyka,któregowyrażeniazbudowanesątylkoznieanalizo-

walnychwwewnętrznejstrukturzezdańprostychiklasycznychspój-

ników prawdziwościowych) zastąpić pojęcie wynikania semantycz-

negoprzezpojęciewynikaniasyntaktycznego.Umożliwiaonoopusz-

czenie dowodu, że jakiejś zdanie wynika semantycznie, jeżeli tylko

pokazanejest,żezdanietowynikasyntaktycznie.Wszystkiepowyżej

formułowane twierdzenia o własnościach wynikania syntaktycznego

mogą zostać przeformułowane na twierdzenia o własnościach wyni-

kania semantycznego. W praktycznym stosowaniu logiki nie istnieje

więc potrzeba odróżniania pomiędzy wynikaniem syntaktycznym a

semantycznym.Jesttosytuacjaanalogiczna doznanejzarytmetyki

szkolnej,gdzienieodróżniamynp.pomiędzyrzeczywistymiloczynem

liczbaliczbąwyrachowanązgodniezregułamipisemnegomnożenia.

Wdalszychrozważaniachwzakresielogikizdańwszędzietam,gdzie

odróżnienietoniejestważne,będziemymówilipoprostuowynikaniu

(logicznym).

tenmamodel.Wmodelutymprawdziwesąwszystkiezdaniaz Σ ,a

zdanie α jestfałszywe,więczgodniezdeﬁnicjąwynikaniasemantycz-

negoniezachodzi Σ | = α , co przeczy założeniu. Zatem jeżeli Σ | = α ,

to Σ α .

(B) Niech Σ α iniechniezachodzi Σ | = α .Ponieważniezachodzi

Plik z chomika:

Inne pliki z tego folderu:

Inne foldery tego chomika: