Skriptá

Matematicko-fyzikální fakulta UK

Predik

áto

v

á

logik

a

P

etr

©těpánek

Praha

2000

Obsah

1

Úv

o

d

3

1.1 Jazyk logiky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

1.2 Formální systém logiky prvního řádu . . . . . . . . . . . . . . . . 10

2

Výrok

o

v

á

logik

a

13

2.1 Výrokové formule . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

2.2 Sémantika výrokové logiky . . . . . . . . . . . . . . . . . . . . . . 15

2.3 Formální systém výrokové logiky . . . . . . . . . . . . . . . . . . 18

2.4 Věty o úplnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26

2.5 Standardní tvary výrokových formulí . . . . . . . . . . . . . . . . 34

2.6 Cvičení A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2.7 Cvičení B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3

Predik

áto

v

á

logik

a

45

3.1 Jazyk a jeho sémantika . . . . . . . . . . . . . . . . . . . . . . . . 45

3.2 Sémantika predikátové logiky . . . . . . . . . . . . . . . . . . . . 48

3.3 Formální systém predikátové logiky 1. řádu . . . . . . . . . . . . . 54

3.4 Prenexní tvary formulí . . . . . . . . . . . . . . . . . . . . . . . . 63

3.5 Predikátová logika s rovností . . . . . . . . . . . . . . . . . . . . . 67

3.6 Cvičení A . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

3.7 Cvičení B . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

4

Pra

vdiv

ost

a

dok

azatelnost

77

4.1 Věta o korektnosti . . . . . . . . . . . . . . . . . . . . . . . . . . 77

4.2 Věta o úplnosti . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

4.3 Věta o kompaktnosti . . . . . . . . . . . . . . . . . . . . . . . . . 93

4.4 Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96

5

T

eorie

prvního

řádu

99

5.1 Roząíření teorie o denici predikátu . . . . . . . . . . . . . . . . . 100

5.2 Roząíření teorie o funkční symboly . . . . . . . . . . . . . . . . . 101

5.3 Cvičení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108

1

2

OBSAH

Kapitola

1

Úv

o

d

Jedním z charakteristických rysů matematiky je práce s abstraktními objekty jako

jsou čísla, funkce, relace, plochy, struktury, prostory a mnoho daląích. Podobně

i (teoretická) informatika má své abstraktní objekty jazyky, automaty, funkce,

procedury, programy, třídy sloľitosti a jiné.

Matematická logika dává zkoumání takových objektů nový rozměr tím, ľe

studuje jazyk informatiky nebo matematiky, způsoby, jakými jsou abstraktní ob-

jekty denovány, jak se s nimi pracuje a zákonitosti, kterými se matematik nebo

informatik řídí, kdyľ uvaľuje o abstraktních objektech.

Matematická logika je poměrně mladá disciplina, která vznikala v 19. století

v pracích G. Boolea, B. Bolzana, G. Frege a daląích. Prodělala bouřlivý vývoj

v první polovině dvacátého století, který byl spojen se jmény, z nichľ uveďme

alespoň D. Hilberta, A. Churche, G. Peana, B. Russela, A. Tarského, A. Turinga

a který pokračuje dodnes.

Bylo by nesprávné se domnívat, ľe teprve vznikem matematické logiky dostala

matematika pevný řád a logickou výstavbu. Pojem důkazu, který rozhodujícím

způsobem ovlivnil výstavbu matematiky, patří jiľ starověké matematice. Zname-

nal vznik matematiky jako deduktivní vědy. Připomeňme jen známé Eukleidovy

knihy, kde je geometrie budována na základě několika postulátů, ze kterých jsou

postupně odvozována vąechna daląí tvrzení, věty Eukleidovy geometrie. Kaľdá

věta musí mít důkaz, který vychází z výslovně uvedených předpokladů a musí

ukázat, ľe tvrzení věty je odvozeno pouze rozumovou (logickou) úvahou. Ten,

kdo dokazuje (mlčky) předpokládá, ľe rozumí tomu, co je to (neformální) důkaz

a ľe bude schopen přesvědčit o správnosti kaľdého kroku svého odvození. Úlohu

rozhodčího ve sporných případech od starověku aľ do konce 19. století hrála kla-

sická logika, jejíľ konečnou podobu zachytil Aristoteles. Matematická logika se

ujímá své role aľ v době, kdy vrcholí snaha po přesném vyjádření základů mate-

matiky vyjasněním pojmu čísla, funkce, mnoľiny a daląích pojmů, které se dostaly

do popředí zájmu jiľ rozvinuté matematické analýzy, algebry a geometrie. Tyto

problémy jiľ klasická logika nebyla schopna adekvátně řeąit.

3

4

KAPITOLA

1.

ÚV

OD

Nový a nečekaný impuls k rozvoji matematické logiky daly paradoxy teorie

mnoľin na přelomu století. Otázku paradoxů, z nichľ jmenujme alespoň paradox

Russellův, jiľ nebylo moľné řeąit prostředky klasické logiky. První řeąení po-

dal Russell sám v rámci takzvané teorie typů. Dnes nejroząířenějąím řeąením je

axiomatická výstavba teorie mnoľin na základě predikátové logiky prvního řádu.

Matematická logika proąla od počátku století rychlým vývojem, rozvinula mnoho

účinných metod, které přispěly k vyjasnění základů matematiky a naąly uplat-

nění v různých oborech matematiky. Dokladem originálního přínosu matematické

logiky je pak i skutečnost, ľe naąla uplatnění i v moderních oborech informatiky

a v některých oborech techniky, které jeątě neexistovaly v době jejího vzniku.

Cílem tohoto textu je seznámit čtenáře se syntaxí a sémantikou predikátové

logiky, se základy jejích formálních metod a také s omezeními, které pouľití for-

málních metod nutně s sebou nese. Daląí důleľité části matematické logiky jako

jsou teorie rekurse, zabývající se studiem metod efektivní vyčíslitelnosti, teorie

modelů, která se věnuje studiu formálních teorií pomocí tříd jejích modelů, teorie

důkazů, kombinatoriká logika a lambda kalkul, neklasické logiky a daląí discipliny

matematické logiky jsou mimo zamýąlený rámec tohoto textu. K daląímu studiu

matematické logiky doporučujeme monograe ... a příručky ... .

1.1

Jazyk

logiky

Matematická logika si zaslouľí svůj přívlastek ze dvou důvodů, jednak proto,

ľe zkoumá jazyk matematiky a daląích oborů například informatiky a způsob,

jakým se v těchto oborech pracuje, jednak proto, ľe k tomuto zkoumání pouľívá

matematiky. Začneme neformální analýzou jazyků matematiky a informatiky,

abych ukázali jejich podstatné součásti, které musí logika zachytit, aby mohla k

těmto oborům něco platného říci.

1.1 Neformální jazyk matematiky Matematik pracuje s mnoľstvím růz-

ných objektů, a» to jsou čísla, body, úsečky, přímky a daląí geometrické útvary,

zobrazení nebo daląí sloľitějąí matematické struktury. Informatik pracuje napří-

klad s jazyky v různých abecedách, které jsou vlastně mnoľinami slov, s abs-

traktními automaty a stroji, které mohou takové jazyky akceptovat, transformo-

vat nebo jinak zpracovávat. Pracuje také s třídami sloľitosti, které si můľeme

představit jako mnoľiny jazyků a s daląími pojmy.

Některé objekty mají své vlastní jméno, například nula, imaginární jednotka,

prázdné slovo, identické zobrazení, zřetězení slov, které označuje jeden zcela ur-

čitý objekt. K označení těchto speciálních objektů se pouľívají ustálené symboly,

například 0

;

i;

";

id;

, kterým říkáme

konstanty

.

Pouľívají se vąak i obecná jména, která určují povahu objektu, například

číslo, bod, čtverec, ale nijak neurčují o které číslo, bod nebo čtverec se jedná.

1.1.

JAZYK

LOGIKY

5

Taková obecná jména se pouľívají i v běľném jazyce, kterým mluvíme. K ozna-

čení takových obecných jmen se pouľívají symboly, kterým říkáme proměnné.

Jde zpravidla o proměnné z konce abecedy

x;

y

;

z

;

:

:

:

často s různými indexy. Při

práci s objekty matematik, informatik nebo technik pouľívají operace, například

pracujeme-li s čísly pouľíváme operace součtu, součinu nebo rozdílu, pracujeme-li

se slovy pouľíváme zřetězení. Tyto operace mají své zvláątní označení například

+

;

;

nebo

. Operace například zřetězení je vlastně zobrazení, které dvěma

objektům (slovům) přiřazuje daląí objekt, slovo, které je jejich zřetězením. V

tomto případě je operace zřetězení funkcí na mnoľině uspořádaných dvojicí slov.

Jazyk logiky bude tedy obsahovat symboly pro operace, kterým budeme říkat

funkční symboly.

Kaľdému funkčnímu symbolu je přiřazeno přirozené číslo, které

vyjadřuje takzvanou četnost symbolu, to znamená počet argumentů, na které je

symbol aplikován. Je-li četnost symbolu rovna přirozenému číslu

n

, říkáme také,

ľe symbol je

n

-ární. Pro četnosti

n;

n

3 se poľívá vľitých názvů, symboly s

četností jedna se nazývají unární, symboly s četností dva se nazývají binární a

s četností tři se nazývají ternární. Tak funkce

S

následníka přirozeného čísla,

S

(

n

) =

n

+1 je unární, a součet a součin jsou funkce binární. V obecném případě

se setkáváme s

n

-árními funkčími symboly, které označují funkce

n

proměnných.

Je přirozené chápat konstanty, které označují určitý objekt nezávisle na jiných

objektech jako 0-ární funkce, tedy funkční symboly, které nevyľadují ľádný ar-

gument.

Matematik vyjadřuje také vztahy mezi objekty, například "číslo

x

je rovno

dvojnásobku čísla

y

"

nebo "číslo

y

je menąí neľ jedna".

Pro tyto vztahy se pouľívá

ustáleného označení = a

<

, potom výrazy

x

= 2

y

y

<

1

(1)

jsou symbolickým vyjádřením vztahů mezi čísly

x

a

y

, které jsme uvedli v úvo-

zovkách.

Povąimněme si, ľe kaľdý z výrazů (1) zastupuje holou větu českého jazyka. V

daném případě ąlo o vztah mezi dvěma čísly

x

a

y

respektive

y

a 1. Jsou moľné

i sloľitějąí vztahy například "číslo

x

leľí mezi čísly

y

a

z

"

, který určuje vztah

mezi třemi čísly. Jazyk logiky bude obsahovat symboly, které vyjadřují vztahy

mezi objekty. Budeme jim říkat predikátové symboly. Ke kaľdému predikátovému

symbolu je dáno přirozené číslo, četnost symbolu, které udává počet jeho ar-

gumentů. Tedy symboly = a

<

jsou binární, vyjadřují vztah mezi dvěma čísly.

Obecně se můľeme setkat s

n

-árními predikátovými symbolu pro

n

1. Obdobou

0-árních funkčních symbolů by mohly být "logické konstanty" označující pravdu

a nepravdu, ale nebudeme jich zde pouľívat. Povąimněme si jeątě, ľe predikátové

symboly = a

<

odpovídají slovesům českého jazyka, mají tedy schopnost tvořit

formální obdobu holých vět českého jazyka.

Jazyk logiky bude obsahovat také symboly pro logické spojky, které jsou ob-

dobou spojek v českém jazyce a dovolují spojovat jednoduąąí výrazy ve sloľitějąí.

6

KAPITOLA

1.

ÚV

OD

Je to obdoba vytváření souvětí ze dvou vět. K logickým spojkám řadíme symboly

& pro konjunkci,

_

pro disjunkci,

!

pro implikaci,

$

pro ekvivalenci a symbol

:

pro negaci.

Uľijeme-li výrazy (1), můľeme roli logických spojek ilustrovat následujícím

příkladem

:x

= 2

y

čteme "neplatí

x

= 2

y

"

x

= 2

y

&

x

<

1

čteme "

x

= 2

y

a

x

<

1"

x

= 2

y

_

x

<

1

čteme "

x

= 2

y

nebo

x

<

1"

(2)

x

= 2

y

!

x

<

1

čteme "

x

= 2

y

implikuje

x

<

1"

nebo "je-li

x

= 2

y

potom

x

<

1"

x

= 2

y

$

x

<

1

čteme "

x

= 2

y

právě kdyľ

x

<

1"

nebo "

x

= 2

y

je ekvivalentní

x

<

1"

Matematika pouľívá také formulace "pro kaľdé

x

plati

:

:

:

"

nebo "existuje

x

takové, ľe

:

:

:

".

V těchto případech mluvíme o kvantikaci proměnných. Jazyk

logiky bude proto obsahovat i symboly

8

a

9

, kterým říkáme obecný (univerzální

nebo velký) kvantikátor a existenční (nebo malý) kvantikátor.

V jazyce logiky se uplatní i pomocné symboly, které uľíváme ke zlepąení čitel-

nosti výrazů. Pomocné symboly jsou zpravidla různé druhy závorek (

;

)

;

[

;

]

;

f

;

g

atd.

Je-li

x

proměnná, potom výrazy

(

8x

)(

x

<

1)

čteme "pro kaľdé

x

platí

x

<

1"

(3)

(

9x

)(

x

= 2

y

)

čteme "existuje

x

takové, ľe

x

= 2

y

"

1.2 Symbolický jazyk Ukazuje se, ľe vąechny důleľité obraty jazyka mate-

matiky lze zachytit vhodnou volbou odpovídajících symbolů v umělém, symbo-

lickém jazyce. Matematická tvrzení jsou potom vyjádřena určitými výrazy tohoto

symbolického jazyka. Symbolické jazyky se také nazývají formální. Pro potřeby

různých matematických teorií lze sestrojit různé formální jazyky.

Předchozí analýzu shrnuje následující denice.
1.3 Jazyk 1. řádu obsahuje tyto symboly

proměnné

x;

y

;

z

;

x

1

;

x

2

;

:

:

:

;

y

1

;

y

2

;

:

:

:

kterých je neomezeně mnoho;

1.1.

JAZYK

LOGIKY

7

funkční symboly

f

;

g

;

h;

:

:

:

ke kaľdému symbolu je dáno přirozené

číslo

n

0, které vyjadřuje jeho četnost;

predikátové symboly

p;

q

;

r

;

:

:

:

ke kaľdému symbolu je dáno přirozené

číslo

n

>

0, které udává jeho četnost. Jazyk můľe (ale nemusí) obsahovat

binární predikátový symbol = k označení rovnosti. Je-li v jazyku obsaľen,

mluvíme o jazyku s rovností;

logické spojky

:;

&

;

_;

!;

$

vyjadřující negaci, konjunkci, dis-

junkci, implikaci a ekvivalenci;

kvantikátory

8;

9

univerzální a existenční;

pomocné symboly

(

;

)

;

[

;

]

;

f

;

g;

:

:

:

1.4 Speciální a logické symboly Některé symboly jsou společné vąem for-

málním jazykům, protoľe odpovídají logickým konstrukcím, budeme proto nazý-

vat logické symboly. Jsou to symboly pro proměnné, logické spojky, kvantikátory,

pomocné symboly a symbol rovnosti =, je-li v jazyku obsaľen. Zbývající symboly,

tedy symboly pro funkce a predikáty, označují speciální operace a vztahy v té,

které matematické disciplině. Budeme je nazývat speciální symboly. Je zřejmé,

ľe jazyk je určen jednoznačně výčtem svých speciálních symbolů (a tím jde-li

o jazyk s rovností nebo bez rovnosti). Například jazyk teorie mnoľin je jazyk 1.

řádu s rovností, který má jediný speciální symbol

- binární predikátový symbol

vyjadřující náleľení prvku do mnoľiny (třídy).

1.5 Termy a formule Ze symbolů jazyka se podle jistých pravidel tvoří dva

typy výrazů,

termy

, které popisují objekty, které vzniknou po provedení v termu nazna-

čených operací,

formule

, které vyjadřují různá matematická tvrzení.

Například výraz

f

(

g

(

x;

y

)

;

h

(

x

)

;

x

)

kde

x;

y

jsou proměnné a

f

;

g

;

h

jsou po řadě ternární, binární a unární

funkční symboly, je term. Výrazy (1) jsou (atomické) formule.

1.6 Jazyky vyąąích řádů Jazyky, které jsme popsali, se nazývají jazyky

1. řádu

, protoľe mají jen jeden typ proměnných, kterým říkáme proměnné pro

individua

například čísla, prvky grupy, mnoľiny a podobně. Jazyk neobsahuje

daląí typy proměnných například pro přirozená čísla, mnoľiny čísel, funkce, relace

a daląí typy objektů. Kvantikovat můľeme tedy jen proměnné pro individua.

8

KAPITOLA

1.

ÚV

OD

Tím se jazyky 1. řádu liąí od jazyků vyąąích řádů, kde například jazyk takzvané

slabé logiky 2. řádu má kromě proměnných pro individua daląí typ proměnných

pro přirozená čísla (nebo obecněji pro konečné mnoľiny individuí), které také

dovoluje kvantikovat. Jazyky 2. řádu obsahují proměnné pro mnoľiny individuí,

proměnné pro funkce a relace a dovolují kvantikovat kromě individuí i mnoľiny

individuí a funkce a relace na universu individuí. Logika, která pracuje jen s

jazyky prvního řádu, se nazývá

logika

prvního

ř

ádu

.

1.7

Výrazo

v

á

síla

jazyků

prvního

řádu

Je řada důvodů, pro které lze

logiku prvního řádu povaľovat za základní jazyk matematiky. Ve srovnání s lo-

gikami vyąąích řádů má jednoduąąí jazyk, který se neodkazuje k pojmu mnoľiny.

Protoľe jazyk teorie mnoľin je prvního řádu, můľe logika prvního řádu slouľit

jako základní teorie i pro teorii mnoľin. Vzhledem k tomu, ľe jazyk teorie mnoľin

dovoluje konstruovat vąechny matematické objekty uvnitř teorie mnoľin, logika

prvního řádu můľe prostřednictvím teorie mnoľin poslouľit jako logický základ

pro matematiku.

1.8

Příklad

Moľnosti a omezení logiky prvního řádu budeme ilustrovat na

několika příkladech z algebry a teorie mnoľin.

a) K popisu uspořádaných mnoľin vystačíme s jediným speciálním symbo-

lem

<

, binárním predikátovým symbolem pro relaci uspořádání. Pracujeme s

jazykem 1. řádu s rovností, který obsahuje jediný speciální symbol

<

. Částečné

uspořádání je charakterizováno dvěma formulemi

:

(

x

<

x

)

(

x

<

y

&

y

<

z

)

!

x

<

z

První z nich stanoví, ľe uspořádání není reexivní a druhá vyjadřuje tranzitivnost

uspořádání.

b) Ke studiu těles je moľno pouľít jazyk s rovností, který obsahuje speciální

symboly 0

;

1

;

+ a

. První dva z nich jsou konstanty označující nulu a jednotku,

druhé dva jsou binární funkční symboly, které označují operace sčítání a násobení

v tělese. V tomto jazyce lze vyjádřit obvyklé axiomy tělesa, to ponecháme čtenáři

jako cvičení. Pomocí termů můľeme také vyjádřit takzvané

přir

ozené

násobky

. Je-

li

x

proměnná, budeme termy

x;

(

x

+

x

)

;

(

x

+ (

x

+

x

))

;

:

:

:

;

(

x

+ (

x

+ (

x

+

:

:

:

(

x

+

x

)

:

:

:

)))

|

{z

}

n

v

sk

y

t

x

označovat zkratkami 1

x;

2

x;

3

x;

:

:

:

;

n

x

a budeme jim říkat

přir

ozené

násobky

x

. Uvědomme si, ľe přirozená čísla nemusí být podmnoľinou zkoumaného

tělesa a přirozený násobek imituje součin jako opakované přičítání. Výraz

p

x

,

kde

p

je nějaké přirozené číslo můľe zastupovat term značné délky. Pokud pro

nějaké nenulové přirozené číslo

p

v určitém tělese platí formule

1.1.

JAZYK

LOGIKY

9

p

1 = 0

(4)

říkáme, ľe těleso má konečnou charakteristiku. Nejmenąí nenulové číslo

p

, pro

které platí (4), je

char

akteristika

tělesa

. Pokud pro ľádné nenulové

p

neplatí (4),

říkáme, ľe těleso má charakteristiku nula. Přidáme-li k axiomům tělesa formule

p

1

6

= 0

(5)

p

pro vąechna nenulová přirozená čísla

p

, dostáváme axiomy tělesa charakteristiky

nula. Je přirozené poloľit si otázku, zda lze tělesa charakteristiky nula axiomati-

zovat také konečným počtem axiomů v logice prvního řádu. Negativní odpověď

vyplývá z následujícího tvrzení.

1.9

V

ěta

Kaľdá konečná mnoľina formulí jazyka prvního řádu, které jsou

splněny ve vąech tělesech charakteristiky nula, je splněna i ve vąech tělesech dosti

velké konečné charakteristiky.

Konečná mnoľina formulí jazyka prvního řádu tedy nemůľe rozliąit mezi tě-

lesy charakteristiky nula a tělesy některých konečných charakteristik. Tato věta

je důsledkem takzvané věty o kompaktnosti logiky prvního řádu, se kterou se

seznámíme později. Tělesa charakteristiky nula bychom mohli charakterizovat je-

dinou formulí, kdybychom překročili rámec jazyků prvního řádu, zavedli nový

typ proměnných pro přirozená čísla a dovolili jej kvantikovat. Tím by vznikl

jazyk takzvané slabé logiky druhého řádu, který algebra běľně pouľívá. Je-li

p

proměnná pro přirozená čísla, potom nekonečnou mnoľinu formulí 1. řádu (5)

p

lze nahradit jedinou formulí

(

8p

)(

p

6

= 0

!

p

1

6

= 0)

slabé logiky druhého řádu. Vyjadřovací prostředky slabé logiky druhého řádu

jsou silnějąí neľ vyjadřovací prostředky logiky prvního řádu. Z toho, co jsme

řekli o důkazu věty 1.9 pak plyne, ľe věta o kompaktnosti (pro logiku prvního

řádu) jiľ nemůľe platit pro slabou logiku druhého řádu. Zůstaneme-li u jazyka a

logiky 1. řádu, poznamenejme, ľe některé vlastnosti těles, například to, ľe těleso

je Archimedovské, nelze v tomto jazyce vyjádřit ani nekonečným počtem formulí.

Zajímavým negativním důsledkem takzvané Lövenheimovy a Skolemovy věty pro

logiku prvního řádu je i následující tvrzení

1.10

V

ěta

®ádná mnoľina formulí jazyka prvního řádu teorie těles neurčuje

těleso reálných čísel jednoznačně (aľ na izomorsmus).

Důleľitou charakteristikou tělesa reálných čísel je totiľ věta o supremu, která

mluví o mnoľině reálných čísel a reálném číslu - jejím supremu. Tato věta můľe

být vyjádřena formulí jazyka druhého řádu, který má k dispozici i proměnné

pro mnoľiny individuí, zde tedy reálných čísel. Octli bychom se tedy v logice

10

KAPITOLA

1.

ÚV

OD

druhého řádu. Uvedené výsledky se stoupající gradací ukazují na omezení daná

jazykem prvního řádu. Můľe tedy logika prvního řádu vyhovět vąem poľadav-

kům tak, aby byla spolehlivým východiskem ke studiu matematiky, informatiky

a daląích oborů? Dříve neľ odpovíme, připomeňme jiľ uvedené příklady. K po-

pisu těles charakteristiky nula chyběla jazyku prvního řádu moľnost pracovat

vedle proměnných pro individua (prvky tělesa) jeątě s proměnnými pro přirozená

čísla. Tuto moľnost nabízela slabá logika druhého řádu. V případě Archimedov-

ských těles a věty o supremu ąlo o to, ľe vedle promenných pro individua nebyla

moľnost pracovat s proměnnými pro mnoľiny individuí. Tuto moľnost nabízí aľ

logika druhého řádu. V obou případech je zřejmé, ľe silnějąí logika v sobě zahr-

nuje nějaký fragment teorie mnoľin. To nemusíme povaľovat za adekvátní řeąení.

Tyto obtíľe odpadnou, budujeme-li matematiku v teorii mnoľin, tedy v teorii

s jazykem prvního řádu. Takové řeąení je elegantnějąí, místo, abychom přimí-

chávali potřebný fragment teorie mnoľin k logice, kterou chceme ponechat co

nejprůzračnějąí, vstoupíme s celou matematikou do teorie mnoľin, která je přijí-

mána jako nejobecneąí rámec pro výstavbu matematiky a je sama teorií prvního

řádu. S teorií mnoľin můľe logika prvního řádu bez obtíľí pracovat. Vracíme se

k naąí počáteční tézi, ľe logika prvního řádu můľe být adekvátním nástrojem

ke studiu matematiky a informatiky. Tato téze je plně oprávněná, pokud bu-

dujeme matematiku a informatiku uvnitř teorie mnoľin. Tento fakt ukazuje na

specickou úlohu teorie mnoľin jak ve vztahu k matematice tak k (teoretické)

informatice. Předchozí úvaha naznačuje moľnost, redukce některých logických

systémů vyąąího řádu do logiky prvního řádu prostřednictvím teorie mnoľin.

1.2 Formální systém logiky prvního řádu
Popsali jsme jazyk prvního řádu a naznačili jsme jaké jsou jeho vyjadřovací moľ-

nosti. Ze symbolů jazyka tvoříme podle přesných syntaktických pravidel dvě dů-

leľité třídy slov termy a formule. Zatím se spokojíme s konstatováním, ľe termy

jsou výrazy, které označují určitá individua, která jsou výsledkem v termu nazna-

čených operací, a formule jsou výrazy, které symbolicky zachycují matematická

tvrzení. Některé formule vybíráme jako základní tvrzení - axiomy, abychom z

nich odvozovali daląí důsledky. Axiomy a z nich odvozené důsledky nazýváme

souhrnně věty. Kaľdá věta musí mít důkaz, který je odvozen z axiomů pouze

rozumovou (logickou) úvahou. Takové vymezení klade dvě přirozené otázky

Lze pojem důkazu denovat?

Jaká jsou logická pravidla, kterými se odvozování řídí?

1.2.

F

ORMÁLNÍ

SYSTÉM

LOGIKY

PR

VNÍHO

ŘÁDU

11

Odpověď na první otázku je snadnějąí, protoľe jsme jiľ zavedli pojem jazyka

prvního řádu, který je jazykem symbolickým a formule vyjadřující matematická

tvrzení jsou slova - konečné posloupnosti symbolů tohoto jazyka. Přirozený jazyk,

kterým budeme mluvit o důkazech, popřípadě o zkoumané axiomatice (teorii), je

odliąen a zůstává v roli takzvaného metajazyka. Metajazyk je tedy jazyk, kterým

se mluví o symbolickém jazyku, jeho konstrukcích, důkazech a zkoumané teorii.

Tímto rozliąením se vyhneme nebezpečí sémantických paradoxů, které mohou

vzniknout pouľívá-li se přirozený jazyk v obou rovinách, jako jazyk teorie a sou-

časně jako jazyk, kterým o teorii mluvíme (paradox lháře a daląí).

Zvolený přístup také zdůrazňuje nitní hledisko, předmětem studia jsou termy

a formule, tedy konečné posloupnosti symbolů, které máme alespoň v principu

plně pod kontrolou. Důkazy - jak uvidíme později - jsou posloupnosti formulí

sestavené podle přesných syntaktických pravidel: kaľdá formule důkazu je buď

axiom nebo je odvozena z některých formulí, které ji předcházejí, podle některého

odvozovacího pravidla. Nyní jiľ máme pohromadě vąechny součásti formálního

systému logiky, které lze identikovat ve vąech logikách, nejenom v predikátové

logice prvního řádu, které je věnována tato kniha.

2.1 Formální systém logiky sestává ze tří sloľek, kterými jsou

jazyk

z jehoľ symbolů vytváříme konečné posloupnosti, slova zejména termy

a formule,

axiomy

, tedy jisté formule, které přijímáme jako základní tvrzení a

odvozovací pravidla

Jsou to syntaktická pravidla, kterými se z konečného

počtu formulí mechanicky odvodí daląí formule, jejich důsledek.

2.2 Důkaz ve formálním systému je konečná posloupnost formulí, jejíľ

kaľdý člen je buď axiom nebo formule, která je odvozena z některých předchozích

formulí pomocí některého odvozovacího pravidla. Říkáme, ľe nějaká formule

A

je větou formálního systému

nebo ľe formule

A

je dokazatelná

, jestliľe existuje

důkaz, jehoľ posledním členem je formule

A

.

Uvedená denice vcelku ideálním způsobem formalizuje intuitivní pojem dů-

kazu. Odvozování vychází z axiomů a postupuje podle přesných syntaktických

pravidel, která jsou mechanicky kontrolovatelná v kaľdém kroku. To je odpoveď

na naąi první otázku.

Na rozdíl od první otázky představuje druhá mnohem hlubąí problém a má

i lozocký rozměr. V intuitivním pojetí důkazu se jednotlivé kroky odvozují z

předchozích kroků (a axiomů) jen rozumovou (logickou) úvahou. Ta je ve formál-

ním důkazu zastoupena volbou odvozovacích pravidel a axiomů logiky. Stojíme

tedy před otázkou, jaké axiomy logiky a jaká odvozovací pravidla máme zvolit. Je-

jich volbou ovlivňujeme třídu formulí, které lze ve vytvářeném formálním systému

12

KAPITOLA

1.

ÚV

OD

dokázat. Predikátová logika řeąí tuto otázku pragmaticky odkazem na sémantiku.

Axiomy logiky vybírá z univerzálně platných formulí, to znamená z formulí, které

jsou pravdivé při kaľdé interpretaci symbolů jazyka. Logika tedy nepreferuje ně-

které interpretace před jinými. Odvozovací pravidla jsou volena tak, aby byla

korektní, to znamená, aby z pravdivých formulí odvozovala formuli, která bude

opět pravdivá.

Je zřejmé, ľe mnoľina vąech univerzálně platných formulí je maximum toho,

co by měl k ní konstruovaný formální systém dokázat. Korektnost odvozovacích

pravidel a volba axiomů z mnoľiny univerzálně platných formulí zaručuje, ľe

mnoľina vět formálního systému bude podmnoľinou mnoľiny vąech univerzálně

platných formulí. Pokud se nám podaří zvolit axiomy a odvozovací pravidla tak, ľe

mnoľina vět je totoľná s mnoľinou vąech univerzálně platných formulí říkáme, ľe

takový formální systém je úplný. Úplnost je důleľitou charakteristikou formálního

systému, protoľe zaručuje, ľe pojem dokazatelnosti se kryje s pojmem univerzální

platnosti, které se také říká logická platnost. Není to ovąem věc samozřejmá.

Nyní můľeme přistoupit k výkladu predikátové logiky prvního řádu. Je účelné

rozdělit výklad do několika etap, které odpovídají uceleným částem logiky a mají

i své vľité názvy. V první etapě se budeme zabývat formálním systémem, který

popisuje vlastnosti logických spojek a který se nazývá výroková logika. V daląí

etapě přidáme axiomy a odvozovací pravidla pro kvantikátory, tím vznikne pre-

dikátová logika bez rovnosti

. Nakonec přidáme axiomy pro predikát rovnosti, který

počítáme k logickým symbolům a tak vznikne nejobsaľnějąí formální systém pre-

dikátová logika s rovností

.

V kaľdé etapě se nejprve seznámíme se sémantikou daného jazyka a budeme

přesně denovat pojmy pravdivosti formule a korektnosti odvozovacích pravidel,

na které jsme se zatím odvolávali bez bliľąího vysvětlení. Pro kaľdý formální

systém dokáľeme také větu o úplnosti.

Kapitola

2

Výrok

o

v

á

logik

a

Výroková logika zevrubně zkoumá syntax a sémantiku formulí, které vzniknou po-

mocí logických spojek. Přitom odhlíľí od daląích symbolů jazyka prvního řádu,

zejména od predikátových symbolů a kvantikátorů. Tím výroková logika při-

pomíná rozbor souvětí přirozeného jazyka, při kterém se nepouątíme do rozboru

jednotlivých vět souvětí. Ty chápeme jako nedělitelný celek, jako základní kompo-

nenty souvětí. Zavedeme proto jazyk výrokové logiky jako jednoduąąí verzi jazyka

prvního řádu, která odpovídá této situaci. Formule, které ve výrokové logice nelze

analyzovat, protoľe nejsou sestrojeny jen pomocí logických spojek budou v jazyce

zastoupeny mnoľinou takzvaných prvotních formulí, které jsou základními kom-

ponentami vąech formulí výrokové logiky. Kaľdá formule výrokové logiky vznikne

z konečného počtu prvotních formulí za pouľití logických spojek.

2.1 Výrokové formule
V této kapitole denujeme jazyk a formule výrokové logiky, probereme séman-

tiku výrokové logiky, zavedeme formální systém výrokové logiky, její axiomy a

odvozovací pravidlo modus ponens a dokáľeme některé jednoduché věty výro-

kové logiky. Z hlubąích výsledků dokáľeme větu o kompaktnosti, věty o úplnosti

výrokové logiky a věty o standardních tvarech formulí výrokové logiky.

2.1 Prvotní formule Nech»

P

je neprázdná mnoľina, jejíľ prvky mohou

být slova nějakého formálního jazyka nebo jen písmena

p;

q

;

r

;

p

1

;

p

2

;

p

3

;

:

:

:

Prvky mnoľiny

P

budeme nazývat prvotní formule.

2.2 Jazyk výrokové logiky Jazyk

L

P

výrokové logiky nad mnoľinou

P

obsahuje prvky mnoľiny

P

a dále symboly pro logické spojky

:

(negace),

&

(konjunkce),

_

(disjunkce),

!

(implikace)

a

$

(ekvivalence)

. Jazyk

L

P

jeątě obsahuje pomocné symboly (závorky). Říkáme, ľe

P

je mnoľina prvotních

formulí jazyka

L

P

.

13

14

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

2.3 Výrokové formule jazyka

L

P

denujeme pomocí následujících syntak-

tických pravidel.
(i) Kaľdá prvotní formule

p

2

P

je výroková formule.

(ii) Jsou-li výrazy

A;

B

výrokové formule, potom výrazy

:A;

(

A

&

B

)

;

(

A

_

B

)

;

(

A

!

B

)

;

(

A

$

B

)

jsou výrokové formule.

(iii) Kaľdá výroková formule vznikne konečným počtem uľití pravidel (i) a (ii).

Denice 2.3 popisuje způsob jakým se sloľitějąí výrokové formule konstruují z

formulí jiľ sestrojených. Jde o induktivní denici opírající se o konstruktivní pra-

vidla (i), (ii) a uzavírací klauzuli (iii), která zaručuje, ľe kaľdá výroková formule

je konečné slovo.

2.4 Příklad Je-li

P

=

fp;

q

;

r

;

sg

mnoľina prvotních formulí, potom

výrazy

p;

q

;

r

jsou výrokové formule podle (i)

(

p

_

q

) a (

p

&

q

)

jsou výrokové formule podle (ii)

a nakonec

((

p

_

q

)

!

(

p

&

q

))

je výroková formule podle (ii)

Vąechny formule, které jsme při konstrukci poslední z nich sestrojili, tedy

včetně jí samé, nazýváme podformulemi formule ((

p

_

q

)

!

(

p

&

q

)). Můľeme

říci, ľe podformule nějaké formule je kaľdé její podslovo, které je samo formulí.

Říkáme, ľe nějaká podformule je vlastní, je-li kratąí neľ daná formule.

Podobně bychom se přesvědčili ľe výraz

(

p

!

(

q

!

(

r

!

s

)))

je výroková formule, jejíľ vlastní podformule jsou

p;

q

;

r

;

s

(

r

!

s

) a (

q

!

(

r

!

s

))

Snadno se nahlédne, ľe výrazy

ppr

;

(

!

p

) a (

!

!

nejsou výrokové formule.
2.5 Úmluva Pomocné symboly, které pouľívíme při zápisu formulí slouľí

předevąím k lepąí čitelnosti těchto výrazů. Denice 2.3 stanoví psaní závorek

jednoznačne. Při psaní závorek si můľeme dovolit určitou volnost pokud to nebude

2.2.

SÉMANTIKA

VÝR

OK

O

VÉ

LOGIKY

15

na újmu srozumitelnosti. Je například obvyklé vynechávat krajní párové závorky,

které jsou denicí formule předepsány, ale ve skutečnosti nic neoddělují. Píąeme

například

(

p

&

q

)

_

r

místo

((

p

&

q

)

_

r

)

(

p

&

q

)

!

r

místo

((

p

&

q

)

!

r

)

V některých případech se také přijímá konvence doplňování chybějících závo-

rek při kumulaci doprava. Pak píąeme

p

1

!

p

2

!

:

:

:

!

p

n

místo (

p

1

!

(

p

2

!

:

:

:

(

p

n

1

!

p

n

)

:

:

:

))

Podobné úmluvy lze zavádět podle potřeby.

2.2 Sémantika výrokové logiky
Sémantika výrokové logiky zkoumá pravdivost výrokových formulí. Podle de-

nice 2.3 jsou výrokové formule konstruovány nad mnoľinou prvotních formulí.

Přitom prvotní formule jsou ty podformule výrokových formulí, které ve výro-

kové logice neanalyzujeme, jejich pravdivost či nepravdivost tedy musí být dána

zvnějąku zobrazením, které nazýváme pravdivostní ohodnocení. Pravdivost ostat-

ních formulí pak můľe být odvozena z pravdivosti základních podformulí a ze

sémantiky pouľitých logických spojek.

2.6 Sémantika výrokových formulí Nech»

P

je mnoľina prvotních formulí

jazyka

L

P

výrokové logiky. Mnoľina pravdivostních hodnot je dvouprvková a

sestává z hodnot 1 (true) a 0 (false).

(i) Pravdivostní ohodnocení (valuace) prvotních formulí je zobrazení

v

:

!

f

0

;

1

g

, které kaľdé prvotní formuli

p

2

P

přiřadí hodnotu 0 nebo 1.

(ii) Pravdivostní ohodnocení

v

lze jednoznačně roząířit na vąechny formule ja-

zyka

L

P

. Indukcí podle sloľitosti formule

A

denujeme roząíření

v

zobrazení

v

předpisem

v

(

A

) =

v

(

A

)

je-li

A

prvotní formule

v

(

:A

) = 0

je-li

v

(

A

) = 1

= 1

je-li

v

(

A

) = 0

v

(

A

&

B

) = 1

je-li

v

(

A

) =

v

(

B

) = 1

= 0

jinak

16

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

v

(

A

_

B

) = 0

je-li

v

(

A

) =

v

(

B

) = 0

= 1

jinak

v

(

A

!

B

) = 0

je-li

v

(

A

) = 1 a

v

(

B

) = 0

= 1

jinak

v

(

A

$

B

) = 1

je-li

v

(

A

) =

v

(

B

)

= 0

jinak

Říkáme, ľe

v

(

A

) je pravdivostní hodnota formule

A

při ohodnocení

v

.

Formule

A

je pravdivá při ohodnocení

v

, je-li

v

(

A

) = 1 jinak je nepravdivá.

2.7 Tautologie a splnitelné formule (i) Říkáme, ľe formule

A

je tauto-

logie

, je-li pravdivá při kaľdém ohodnocení prvotních formulí.

(ii) Formule je splnitelná, je-li pravdivá při nějakém ohodnocení prvotních

formulí. Ohodnocení

v

, takové ľe

v

(

A

) = 1 nazýváme modelem formule

A

.

(iii) Mnoľina formulí

T

je splnitelná

, jestliľe existuje pravdivostní ohodno-

cení

v

, takové ľe kaľdá formule

A

z mnoľiny

T

je pravdivá při ohodnocení

v

. Takové ohodnocení

v

nazýváme modelem mnoľiny formulí

T

.

(iv) Říkáme, ľe formule

A

je tautologickým důsledkem mnoľiny formulí

T

a píąeme

T

j

=

A

, je-li formule

A

pravdivá při kaľdém ohodnocení, které je

modelem mnoľiny

T

. Je-li

T

prázdná mnoľina, píąeme krátce

j

=

A

. V tomto

případě je

A

pravdivá při kaľdém ohodnocení, to znamená, ľe

A

je tautologie.

2.8 Denice 2.7 dává moľnost rozhodnout o kaľdé formuli zda je či není

tautologií. Například formule

A

_

:A

(zákon vyloučeného třetího)

:

(

A

&

:A

)

(vyloučení kontradikce)

:

(

A

&

B

)

$

(

:

A

_

:

B

)

(de Morganova pravidla)

:

(

A

_

B

)

$

(

:

A

&

:

B

)

::

A

$

A

(zákon dvojité negace)

2.9 Snadno se zjistí, ľe pro libovolné ohodnocení

v

prvotních formulí a

libovolné formule

A;

B

, je-li

v

(

A

) =

v

(

A

!

B

) = 1 potom také

v

(

B

) =

2.2.

SÉMANTIKA

VÝR

OK

O

VÉ

LOGIKY

17

1 . Jak uvidíme při studiu formálního systému výrokové logiky, tato vlastnost

implikace zaručuje korektnost odvozovacího pravidla modus ponens.

Odtud také plyne, ľe pro libovolnou mnoľinu formulí

T

, z

T

j

=

A

a

T

j

=

A

!

B

plyne

T

j

=

B

.

2.10 Věta o kompaktnosti výrokové logiky Mnoľina formulí

T

je

splnitelná, právě kdyľ je splnitelná libovolná konečná podmnoľina

T

0

T

.

Důkaz. a) Je-li

T

splnitelná, pak existuje ohodnocení

v

, které je modelem

mnoľiny

T

. Totéľ ohodnocení je pak také modelem kaľdé konečné podmnoľiny

T

0

mnoľiny

T

.

b) důkaz obrácené implikace je moľné provést matematickou indukcí, pokud

se omezíme na případ, kdy je mnoľina prvotních formulí a tedy také mnoľina

vąech formulí výrokové logiky nejvýąe spočetná. Provedeme důkaz, který pouľívá

větu o kompaktnosti součinu kompaktních topologických prostorů. Ten nepřed-

pokládá ľádné omezení mohutnosti mnoľiny prvotních formulí. Věta o kompakt-

nosti součinu topologických prostorů, která dává i jméno dokazované větě vąak

sama představuje určitou formu axiomu výběru. Poznamenejme, ľe s nespočet-

nou mnoľinou prvotních formulí bychom mnoho nedokázali, kdybychom nebyli

schopni její prvky dobře uspořádat.

Dvouprvková mnoľina

f

0

;

1

g

pravdivostních hodnot je sama kompaktním

prostorem s diskretní topologií. Je-li

P

mnoľina vąech prvotních formulí, po-

tom kartézský součin Q

p2P

f

0

;

1

g

P

exemplářů kompaktního prostoru

f

0

;

1

g

je podle věty o kompaktnosti topologického součinu také kompaktní topologický

prostor. Přitom z denice kartézského součinu souboru mnoľin vyplývá, ľe prvky

tohoto součinu jsou právě zobrazení

v

:

P

!

f

0

;

1

g

, tedy právě vąechna ohod-

nocení prvotních formulí.

Pro libovolnou formuli

A

můľeme denovat podmnoľinu

U

A

topologického

součinu předpisem

U

A

=

f

v

j

v

:

P

!

f

0

;

1

g;

v

(

A

) = 1

g

Protoľe pravdivostní hodnota

v

(

A

) závisí jen na hodnotách

v

(

p

) pro

konečně mnoho prvotních podformulí formule

A

, je

U

A

otevřená mnoľina.

Jejím doplňkem je mnoľina

U

:A

, která je ze stejného důvodu také otevřená.

Mnoľina

U

A

je tedy také uzavřená.

Podle předpokladu je kaľdá konečná podmnoľina

T

0

mnoľiny

T

splnitelná.

Je-li

T

0

=

fA

1

;

A

2

;

:

:

:

;

A

n

g

T

, pak existuje ohodnocení

v

2

U

A

1

\

U

A

2

\

:

:

:

\

U

A

n

To znamená, ľe mnoľiny

U

A

;

A

2

T

tvoří centrovaný systém obojetných

mnoľin v kompaktním prostoru Q

p2P

f

0

;

1

g

. Z kompaktnosti potom plyne, ľe

18

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

také

T

fU

A

j

A

2

T

g

6

= 0

a to znamená, ľe mnoľina

T

je také splnitelná.

2.11 Důsledek Je-li

A

formule a

T

je mnoľina formulí, potom

T

j

=

A

platí, právě kdyľ existuje konečná podmnoľina

T

0

mnoľiny

T

taková, ľe

T

0

j

=

A

.

Důkaz. Snadno se nahlédne, ľe pro libovolnou mnoľinu formulí

S

platí

S

j

=

A

, právě kdyľ mnoľina

S

0

=

S

[

f:Ag

není splnitelná. Tvrzení potom

plyne z věty o kompaktnosti.

2.3 Formální systém výrokové logiky
Jazyk výrokové logiky je denován a spolu s ním je zaveden i pojem formule.

2.12 Volba axiomů Axiomy výrokové logiky budeme vybírat z logicky plat-

ných formulí. Přirozenými kandidáty na logicky platné formule jsou tautologie.

Výrokové formule jsou sestrojeny z prvotních formulí jen pomocí logických spo-

jek, které mají jednoznačně určenou interpretaci. To znamená, ľe logická platnost

formule můľe být zaručena jen tím, ľe taková formule je pravdivá při kaľdém

ohodnocení prvotních formulí. Tak jsou denovány právě tautologie, které jsou

pravdivé bez ohledu na pravdivost či nepravdivost svých prvotních podformulí;

pravdivost tautologie je dána pouze jejím syntaktickým tvarem. Proto budeme

axiomy výrokové logiky vybírat z mnoľiny vąech tautologií.

2.13 Redukce jazyka Chceme-li úsporně zvolit mnoľinu axiomů, je výhodné

redukovat počet logických spojek na několik základních a ostatní spojky chápat

jako odvozené. Ukáľeme, ľe je moľné zvolit negaci a implikaci za základní logické

spojky a ostatní spojky, konjunkci, disjunkci a ekvivalenci chápat jako spojky

odvozené. Formule (

A

&

B

)

;

(

A

_

B

)

;

(

A

$

B

) budeme denovat jako zkratky

za formule vytvořené jen ze základních spojek, negace a implikace.

(

A

&

B

)

je zkratka za formuli

:

(

A

!

:B

)

(

A

_

B

)

je zkratka za formuli

(

:A

!

B

)

(1)

(

A

$

B

) je zkratka za formuli

((

A

!

B

) & (

B

!

A

))

2.3.

F

ORMÁLNÍ

SYSTÉM

VÝR

OK

O

VÉ

LOGIKY

19

Snadno se přesvědčíme, ľe pro libovolné ohodnocení

v

prvotních formulí se

sobě rovnají pravdivostní hodnoty levých i pravých stran v (1). Tak například

v

(

A

&

B

) =

v

(

:

(

A

!

:B

)), odkud plyne, ľe

(

A

&

B

)

$

:

(

A

!

:B

)

je tautologie. Podobně je tomu i se zbývajícími dvěmi zkratkami z (1). Sémanticky

jsou zkratky ekvivalentní s vyjádřením pomocí základních spojek.

2.14 Volba odvozovacích pravidel Odvozovací pravidla výrokové logiky

volíme tak, aby byla korektní, to znamená, aby z formulí pravdivých při nějakém

ohodnocení odvozovala formuli, která je pravdivá při tomtéľ ohodnocení. Inspi-

raci najdeme v odstavci 2.9, který ukazuje, ľe odvozovací pravidlo modus ponens

je korektní.

2.15 Formální systém výrokové logiky obsahuje

Jazyk

L

P

výrokové logiky nad mnoľinou prvotních formulí

P

.

Axiomy

Pro libovolné formule

A;

B

;

C

jazyka

L

P

je kaľdá formule tvaru

A

!

(

B

!

A

)

(A1)

axiomem výrokové logiky. Dále je axiomem výrokové logiky kaľdá formule

(

A

!

(

B

!

C

))

!

[(

A

!

B

)

!

(

A

!

C

)]

(A2)

a kaľdá formule

(

:B

!

:A

)

!

(

A

!

B

)

(A3)

Odvozovací pravidlo (modus ponens)

Z formulí

A

a

A

!

B

odvoď

formuli

B

. Místo modus ponens píąeme krátce MP.

Formule (A1) - (A3) dávají návod jak z daných formulí

A;

B

;

C

sestrojit

nový axiom výrokové logiky. Nejde tedy o jeden axiom, ale kaľdá z formulí (A1) -

(A3) zastupuje nekonečně mnoho speciálních případů. Říkáme proto, ľe výroková

logika je axiomatizována třemi schematy axiomů (A1), (A2) a (A3).

2.16 Pojem důkazu (i) Říkáme, ľe konečná posloupnost formulí

A

1

;

A

2

;

:

:

:

;

A

n

20

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

je důkazem formule

A

, jestliľe

A

n

je formule

A

a pro libovolné

i;

1

i

n

je formule

A

i

buď axiom nebo je odvozena z předchozích formulí

A

j

;

1

j

<

i

pravidlem modus ponens.

(ii) Existuje-li důkaz formule

A;

říkáme, ľe

A

je dokazatelná ve výrokové

logice nebo ľe

A

je větou výrokové logiky, a píąeme

`

A

.

2.17

Jedno

duc

hé

v

ět

y

výrok

o

v

é

logiky

Odvodíme několik jednoduchých

vět výrokové logiky, které později pouľijeme k důkazu věty o úplnosti výrokové

logiky.

A

!

A

(v1)

Důkaz. Sestrojíme posloupnost formulí, která bude důkazem formule (v1).

`

A

!

((

A

!

A

)

!

A

)

(2a)

`

(

A

!

((

A

!

A

)

!

A

))

!

[(

A

!

(

A

!

A

))

!

(

A

!

A

)]

(2b)

`

(

A

!

(

A

!

A

))

!

(

A

!

A

)]

(2c)

`

(

A

!

(

A

!

A

))

(2d)

`

A

!

A

(2e)

Snadno se nahlédne, ľe (2a) je případem axiomu (A1), (2b) je případem axi-

omu (A2) a ľe (2c) je odvozena z (2a) a (2b) podle pravidla modus ponens. Dále

(2d) je opět případem axiomu (A1) a nakonec (2e) je odvozena z (2c) a (2d)

pravidlem modus ponens.

Posloupnost formulí napravo od

`

v (2a) - (2e) tedy tvoří formální důkaz

věty (v1). Tato jednoduchá formule má důkaz, který obsahuje 5 kroků. Můľeme

očekávat, ľe důkazy daląích formulí budou narůstat do délky. Bude proto uľitečné

mít tvrzení, který by dovolovalo přecházet od důkazu jedné formule k důkazu

jiné formule, aniľ bychom potřebovali celý formální důkaz konstruovat. Takové

tvrzení bude hovořit o důkazech ve výrokové logice, nebude to tedy formule ani

věta výrokové logiky. Z hlediska jazyka, ve kterém bude takové tvrzení vysloveno

se jedná o metavětu (větu o důkazech vět výrokové logiky). Z pragmatických

důvodů a při zneuľití jazyka budeme toto tvrzení nazývat také větou,

větou

o

de

dukci

. Dříve neľ ji vyslovíme, zavedeme obecnějąí pojem formálního důkazu.

2.18

Důk

az

z

předp

okladů

Nech»

T

je mnoľina formulí, nech»

A

je formule. Říkáme, ľe posloupnost formulí

A

1

;

A

2

;

:

:

:

;

A

n

je důkaz formule

A

z

(mnoľiny předpokladů)

T

, jestliľe

A

n

je formule

A

a kaľdá formule

A

i

;

1

i

n

2.3.

F

ORMÁLNÍ

SYSTÉM

VÝR

OK

O

VÉ

LOGIKY

21

je buď axiom výrokové logiky, nebo formule z

T

, nebo je odvozena z předchozích

formulí

A

1

;

A

2

;

:

:

:

;

A

i

1

pravidlem modus ponens. Jestliľe existuje důkaz formule

A

z předpokladů

T

, říkáme ľe formule

A

je dokazatelná z

T

a píąeme

T

`

A

.

2.19

V

ěta

o

deduk

ci

Nech»

T

je mnoľina formulí a nech»

A;

B

jsou

formule, potom

T

`

A

!

B

právě kdyľ

T

[

fAg

`

B

Tedy implikace

A

!

B

je dokazatelná z předpokladů

T

právě kdyľ samotná

formule

B

je dokazatelná z mnoľiny předpokladů

T

roząířené o formuli

A

. To

odpovídá způsobu, jakým se implikace neformálně dokazují. Přesný, ale kompli-

kovaný, mnoľinový zápis předpokladů na pravé straně tvrzení věty o dedukci se

zpravidla zjednoduąuje do tvaru

T

;

A

`

B

.

Demonstrace.

1

a) Je-li

T

`

A

!

B

, pak existuje posloupnost formulí

A

1

;

A

2

;

:

:

:

;

A

n

1

;

A

!

B

která je důkazem formule

A

!

B

z předpokladů

T

. Snadno se nahlédne, ľe

posloupnost

A;

A

1

;

:

:

:

;

A

n

1

;

A

!

B

;

B

je důkazem formule

B

z předpokladů

T

;

A

.

b) Nech»

A;

A

1

;

:

:

:

;

A

n

;

je důkaz formule

B

z předpokladů

T

;

A

. Indukcí

pro

i;

1

i

n

dokáľeme

T

`

A

!

A

i

. Tím pro

i

=

n

splníme úkol.

Předpokládejme, ľe pro

j

<

i

jsme jiľ důkazy formulí

A

!

A

j

sestrojili

(pro

i

= 1 jde o prázdný předpoklad). Pro formuli

A

i

podle denice důkazu z

předpokladů mohou nastat tři případy.

b1)

A

i

je axiom výrokové logiky nebo formule z mnoľiny

T

. Potom sama

formule

A

i

jako posloupnost o jediném členu je svým důkazem z předpokladů

T

. Dále formule

A

i

!

(

A

!

A

i

)

je případem axiomu (A1), je dokazatelná ve výrokové logice a tím spíąe z před-

pokladů

T

. Potom posloupnost formulí

A

i

;

A

i

!

(

A

!

A

i

)

;

A

!

A

i

je důkazem

A

!

A

i

z předpokladů

T

(uľij modus ponens na první dvě

formule).

1

Abychom slovo důkaz nepouľívali ve dvojím smyslu jak pro formální důkazy ve výrokové

logice tak pro důkazy (meta)vět o důkazech výrokové logiky, označíme neformální důkaz věty

o dedukci slovem demonstrace.

22

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

b2) Formule

A

i

je formule

A

, potom podle (v1) je formule

A

!

A

i

větou

výrokové logiky a tedy je také dokazatelná z předpokladů

T

.

b3) Formule

A

i

je odvozena pravidlem modus ponens z formulí

A

j

;

A

k

pro

nějaká

j;

k

<

i

. Bez újmy na obecnosti můľeme předpokládat, ľe

A

j

je tvaru

A

k

!

A

i

. Jiľ dříve jsme ukázali, ľe

T

`

A

!

(

A

k

!

A

i

)

|

{z

}

A

j

T

`

A

!

A

k

a z axiomu (A2) plyne

T

`

(

A

!

(

A

k

!

A

i

))

!

((

A

!

A

k

)

!

(

A

!

A

i

))

(3)

Uľijeme-li dvakrát pravidlo modus ponens dostaneme

T

`

A

!

A

i

(4)

Důkaz formule (4) vznikne tím, ľe spojíme důkazy formulí

A

!

A

j

a

A

!

A

k

do posloupnosti a na její konec přidáme formule (3), (

A

!

A

k

)

!

(

A

!

A

i

) a

(4). Tímto postupem nakonec sestrojíme důkaz formule

A

!

A

n

z předpokladů

T

a tím dokončíme důkaz levé strany tvrzení věty o dedukci. Postup, který jsme

zvolili k důkazu druhé implikace ve Větě o dedukci se nazývá demostrace indukcí

podle délky důkazu

a je zaloľen na tom, ľe sestrojíme důkaz nějaké formule

C

tím, ľe přetvoříme jiľ sestrojený důkaz nejaké jiné formule

C

0

.

2.20

Příklad

Ve sloľené implikaci

A

!

(

B

!

C

) nezáleľí na pořadí

předpokladů

A;

B

. Plyne to z věty o dedukci. Přesněji, pro libovolnou mnoľinu

formulí

T

a formule

A;

B

;

C

platí

T

`

A

!

(

B

!

C

) právě kdyľ

T

;

A;

B

`

C

právě kdyľ

T

`

B

!

(

A

!

C

)

Stejným způsobem se dokáľe

T

`

(

A

!

(

B

!

C

))

!

(

B

!

(

A

!

C

))

a věta o skládání implikací

`

(

A

!

B

)

!

[(

B

!

C

)

!

(

A

!

C

)]

2.21

Daląí

v

ět

y

výrok

o

v

é

logiky

Pomocí věty o dedukci odvozujeme daląí

jednoduché věty výrokové logiky. Nesestrojujeme jiľ formální důkazy podle de-

nice 2.16, ale ukazujeme, ľe formální důkazy vět existují. Budeme proto mluvit

o demonstracích místo o (formálních) důkazech.

`

:A

!

(

A

!

B

)

(v2)

Demonstrace.

2.3.

F

ORMÁLNÍ

SYSTÉM

VÝR

OK

O

VÉ

LOGIKY

23

`

:A

!

(

:B

!

:A

)

případ axiomu (A1)

(a)

:A

`

:B

!

:A

VD (věta o dedukci)

(b)

`

(

:B

!

:A

)

!

(

A

!

B

)

(A3)

(c)

:A

`

A

!

B

(b), (c) MP

(d)

`

:A

!

(

A

!

B

)

VD

(e)

`

::A

!

A

(v3)

Demonstrace.

`

::A

!

(

:A

!

:::A

)

(v2)

(a)

::A

`

:A

!

:::A

VD

(b)

`

(

:A

!

:::A

)

!

(

::A

!

A

)

(A3)

(c)

::A

`

::A

!

A

(b), (c) MP

(d)

::A

`

A

VD

(e)

`

::A

!

A

VD

(f)

2.22 Lemma

`

A

!

::A

(v4)

`

(

A

!

B

)

!

(

:B

!

:A

)

(v5)

`

A

!

(

:B

!

:

(

A

!

B

))

(v6)

`

(

:A

!

A

)

!

A

(v7)

Demonstrace. (v4)

`

:::A

!

:A

(v3)

(a)

`

A

!

::A

(A3), (a) MP

(b)

24

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

(v5)

`

::A;

A

!

B

`

A

(v3) MP

(a)

`

::A;

A

!

B

`

B

(a) MP

(b)

`

::A;

A

!

B

`

::B

(v4), (b) MP

(c)

`

A

!

B

`

::A

!

::B

(c) VD

(d)

`

A

!

B

`

:B

!

:A

(A3), (d) MP

(e)

`

(

A

!

B

)

!

(

:B

!

:A

)

(e) VD

(f)

(v6)

A;

A

!

B

`

B

MP

(a)

A

`

(

A

!

B

)

!

B

(a) VD

(b)

A

`

:B

!

:

(

A

!

B

)

(v5), (A3) MP

(c)

`

A

!

(

:B

!

:

(

A

!

B

))

(c) VD

(d)

(v7)

`

:A

!

(

:A

!

:

(

:A

!

A

))

(v6)

(a)

:A

`

:

(

:A

!

A

)

(a) 2 x VD

(b)

`

:A

!

:

(

:A

!

A

)

(b) VD

(c)

`

(

:A

!

A

)

!

A

(A3), (c) MP

(d)

K důkazu věty o úplnosti výrokové logiky budeme kromě vět (v1) - (v7)

potřebovat jeątě dvě věty, které mají charakter pomocných odvozovacích pravidel.

Protoľe jde o tvrzení o důkazech ve výrokové logice, mají stejný charakter jako

věta od dedukci - jsou to metavěty.

2.3.

F

ORMÁLNÍ

SYSTÉM

VÝR

OK

O

VÉ

LOGIKY

25

2.23 Lemma o neutrální formuli Je-li

T

mnoľina formulí,

A;

B

jsou

formule a je-li

T

;

A

`

B

a

T

;

:A

`

B

, potom také

T

`

B

.

Máme-li dva důkazy formule

B

, jeden z předpokladů

T

;

A

a druhý z předpo-

kladů

T

;

:

A

, potom existuje důkaz formule

B

jen z předpokladů

T

. Říkáme,

ľe formule

A

se k důkazu formule

B

chová neutrálně.

Demonstrace. Uľitím věty o dedukci z druhého předpokladu dostáváme

T

`

:A

!

B

T

`

:B

!

::A

(v5) MP

T

;

:B

`

::A

VD

T

;

:B

`

A

(v3) MP

Z prvního předpokladu a věty o dedukci dostáváme

T

`

A

!

B

Tedy uľitím pravidla modus ponens na dvě předchozí formule

T

;

:B

`

B

T

;

`

:B

!

B

VD

`

(

:A

!

A

)

!

A

(v7)

T

`

B

MP

Následující lemma spojuje dokazatelnost ve výrokové logice s pravdivostí for-

mulí. Dříve neľ ho vyslovíme, zavedeme nové označení.

Nech»

v

je ohodnocení prvotních formulí, nech»

B

je formule, potom

B

v

je

formule

B

, jestliľe

v

(

B

) = 1 a

B

v

je formule

:B

, jestliľe

v

(

B

) = 0.

2.23 Lemma Nech»

v

je ohodnocení prvotních formulí, nech»

A

je formule.

Předpokládejme, ľe vąechny prvotní podformule formule

A

jsou mezi formulemi

P

1

;

P

2

;

:

:

:

;

P

n

Potom

P

v

1

;

P

v

2

;

:

:

:

;

P

v

n

`

A

v

(5)

26

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

Demonstrace. indukcí podle sloľitosti formule

A

. a) Je-li

A

prvotní formule,

pak je to některá z formulí

P

i

;

1

i

n

a není co dokazovat.

b) Je-li

A

tvaru

:B

a je-li (5) pro

B

jiľ dokázáno, mohou nastat dva

případy:

b1) Je-li

v

(

B

) = 0 , potom

B

v

je

:B

, to je formule

A

v

a tvrzení (5)

plyne z indukčního předpokladu.

b2) Je-li

v

(

B

) = 1 , potom

B

v

je

B

a z indukčního předpokladu dostáváme

P

v

1

;

P

v

2

;

:

:

:

;

P

v

n

`

B

Uľijeme (v4)

`

B

!

::B

Podle pravidla modus ponens odvodíme

P

v

1

;

P

v

2

;

:

:

:

;

P

v

n

`

::B

Nyní zbývá si uvědomit, ľe

::B

je formule

A

v

a (5) je dokázáno.

c) Nakonec, je-li

A

tvaru

C

!

D

, kde pro formule

C

;

D

jiľ bylo tvrzení

(5) dokázáno, rozliąujeme čtyři případy:

c1) je-li

v

(

C

) =

v

(

D

) = 1, potom také

v

(

A

) = 1. Z axiomu (A1) a věty o

dedukci dostáváme

D

`

C

!

D

. Přitom

D

v

je

D

a podle indukčního před-

pokladu je dokazatelné z předpokladů (5). Pravidlem modus ponens odvodíme

formuli

C

!

D

a to je právě formule

A

v

. Tím je v tomto případě (5) dokázáno.

c2) je-li

v

(

C

) = 1 a

v

(

D

) = 0, potom

v

(

A

) = 0 Uľijeme-li (v6) a větu o

dedukci dostáváme

C

;

:D

`

:

(

C

!

D

)

Nyní si uvědomme, ľe v předpokladech jsou právě formule

C

v

;

D

v

a z nich

je odvozena formule

A

v

. Tvrzení opět plyne z indukčního předpokladu.

c3-4) Oba případy mají společnou hodnotu

v

(

C

) = 0. Uľijeme-li (v2) a větu

o dedukci, dostáváme

:C

`

C

!

D

Tvrzení opět plyne z indukčního předpokladu, protoľe

C

v

je formule

:C

a

A

v

je

C

!

D

.

2.4

V

ět

y

o

úplnosti

Nyní jiľ můľeme dokázat takzvanou slabou formu věty o úplnosti výrokové logiky.

2.4.

VĚTY

O

ÚPLNOSTI

27

2.24

V

ěta

(P

ost)

Pro libovolnou formuli

A

výrokové logiky platí

`

A

právě kdyľ

j

=

A

Ve výrokové logice jsou dokazatelné právě tautologie.

Demonstrace. a) Nejprve dokáľeme, ľe vąechny věty výrokové logiky jsou tau-

tologie. Provedeme to indukcí podle délky důkazu. Ukáľeme, ľe vąechny axiomy

výrokové logiky jsou tautologie a z 2.9 plyne, ľe pravidlo modus ponens je ko-

rektní, tedy ľe ze dvou tautologií odvozuje opět tautologii. Při ověřování, ľe

nějaká formule je tautologie můľeme pouľít obvyklou metodu, která ověřuje, ľe

daná formule je pravdivá pro kaľdé ohodnocení vąech jejích prvotních podformulí.

V řadě případů je rychlejąí metoda nepřímá, která analyzuje nejhorąí moľný pří-

pad. Pouľijeme ji k ověření, ľe druhý axiom výrokové logiky je tautologie.

Analyzujeme podmínky, za kterých by existovalo ohodnocení

v

, takové, ľe

by formule

(

A

!

(

B

!

C

))

!

[(

A

!

B

)

!

(

A

!

C

)]

(A2)

byla nepravdivá při ohodnocení

v

. V takovém případě by bylo

v

((

A

!

B

)

!

(

A

!

C

)) = 0

odkud nutně

v

((

A

!

B

)) = 1 a

v

((

A

!

C

)) = 0. Z poslední rovnosti

dostáváme

v

(

A

) = 1 a

v

(

C

) = 0 . K tomu z předposlední rovnosti jeątě plyne

v

(

B

) = 1. Odtud

v

(

A

!

(

B

!

C

)) = 0 a při tomto ohodnocení musí být

axiom (A2) pravdivá formule. Ukázali jsme, ľe neexistuje ohodnocení, při kterém

by axiom (A2) nebyl pravdivý. Stejný postup lze pouľít i pro zbývající dva typy

axiomů. Tak se ukáľe, ľe vąechny věty výrokové logiky jsou tautologie.

b) Nyní ukáľeme, ľe vąechny tautologie jsou větami výrokové logiky. Nech»

A

je tautologie a nech»

P

1

;

P

2

;

:

:

:

;

P

n

jsou vąechny prvotní podformule formule

A

. Zvolme pravdivostní ohodnocení

v

takové, ľe

v

(

P

1

) =

v

(

P

2

) =

:

:

:

=

v

(

P

n

) = 1

Podle lemmatu 2.23 platí

P

1

;

P

2

;

:

:

:

;

P

n

`

A

protoľe

A

je tautologie a je tedy pravdivá při ohodnocení

v

stejně jako prvotní

formule

P

i

;

1

i

n

. Nyní pozměňme ohodnocení

v

na

w

tak, ľe

w

(

P

n

) = 0

zatímco ohodnocení ostatních prvotních formulí při

v

a

w

je stejné. Potom podle

lemmatu 2.23 dostáváme

P

1

;

P

2

;

:

:

:

;

P

n

1

;

P

n

`

A

P

1

;

P

2

;

:

:

:

;

P

n

1

;

:P

n

`

A

a podle lemmatu o neutrální formuli dostáváme

28

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

P

1

;

P

2

;

:

:

:

;

P

n

1

;

`

A

Opakujeme-li tento postup jeątě (n-1)-krát, dokáľeme ľe formule

A

je věta

výrokové logiky. Tím je věta o úplnosti dokázána.

2.25

Bezesp

ornost

výrok

o

v

é

logiky

Důsledkem věty o ůplnosti je fakt,

ľe formální systém výrokové logiky je bezesporný. Nejdříve zavedeme samotný

pojem bezespornosti.

Říkáme, ľe formální systém je sporný, je-li kaľdá jeho formule dokazatelná.

V opačném případě říkáme, ľe formální systém je bezesporný.

Pojem bezespornosti lze zobecnit i na mnoľiny formulí. Je-li

T

mnoľina

formulí nějakého formálního systému, říkáme, ľe

T

je sporná

, je-li kaľdá formule

(daného formálního systému) dokazatelná z mnoľiny

T

. Jinak říkáme, ľe

T

je

bezesporná

.

Je zřejmé, ľe formální systém je sporný, právě kdyľ je sporná prázdná mno-

ľina formulí. Bezesporné formální systémy a bezesporné mnoľiny formulí se také

nazývají konzistentní, sporné se nazývají inkonzistentní.

Věta o úplnosti 2.24 ztotoľnila věty výrokové logiky a tautologie. Snadno se

přesvědčíme, ľe pro libovolnou formuli

A

formule

:

(

A

!

A

)

;

(

:A

&

A

) nejsou

tautologie. Podle věty o úplnosti ľádná z nich není dokazatelná. To znamená, ľe

formální systém výrokové logiky je bezesporný.

Sémantickým ekvivalentem bezesporné mnoľiny je pojem splnitelné mnoľiny

formulí.

2.26

Důsledek

Mnoľina formulí výrokové logiky je bezesporná, právě kdyľ

je splnitelná.

Demonstrace. a) Je-li

T

splnitelná mnoľina formulí a je-li ohodnocení

v

jejím modelem, potom z korektnosti pravidla modus ponens 2.9 plyne, ľe kaľdá

formule dokazatelná z

T

je pravdivá při ohodnocení

v

. Proto

T

nemůľe být

sporná.

b) Pokud mnoľina

T

není splnitelná, podle věty o kompaktnosti existuje

konečná podmnoľina

fA

1

;

A

2

;

:

:

:

;

A

n

g

T

, která je také nesplnitelná.

To znamená, ľe formule

(

:A

1

_

(

:A

2

_

:

:

:

_

(

:A

n

1

_

:A

n

)

:

:

:

))

(6)

je tautologie a je dokazatelná ve výrokové logice.

Na druhé straně je kaľdá formule

A

i

dokazatelná z

T

a také

T

`

(

A

1

&(

A

2

&

:

:

:

&(

A

n

1

&

A

n

)

:

:

:

))

(7)

Označíme-li symbolem

B

formuli (7), potom podle de Morganových pravidel

je formule (6) ekvivalentní s formulí

:B

. Nyní uľ není těľké ukázat, ľe

T

je

sporná mnoľina. Je-li

C

libovolná formule, potom podle (v2) platí

2.4.

VĚTY

O

ÚPLNOSTI

29

`

:B

!

(

B

!

C

)

(8)

a dvojím uľitím pravidla modus ponens z

`

:B

,

T

`

B

a (8) odvodíme

T

`

C

.

Dokáľeme jeątě silnou formu věty o úplnosti.

2.27

V

ěta

o

úplnosti

výrok

o

v

é

logiky

Nech»

T

je mnoľina formulí a

A

je formule. Potom platí

T

`

A

právě kdyľ

T

j

=

A

Demonstrace. a) Stejným způsobem jako v důkazu věty 2.24 z denice důkazu

z předpokladů, z faktu, ľe axiomy výrokové logiky jsou tautologie a z korektnosti

odvozovacího pravidla modus ponens (2.9) dostáváme, ľe je-li

T

`

A

, potom

A

je tautologickým důsledkem

T

.

b) Předpokládejme, ľe

T

j

=

A

. Podle důsledku 2.11 věty o kompaktnosti

existuje konečná podmnoľina

T

0

=

fA

1

;

A

2

;

:

:

:

;

A

n

g

mnoľiny

T

taková, ľe

A

je tautologickým důsledkem

T

0

. Indukcí podle

n

se dokáľe následující fakt

A

1

;

A

2

;

:

:

:

;

A

n

j

=

A

právě kdyľ

j

=

A

1

!

(

A

2

!

:

:

:

!

(

A

n

!

A

)

:

:

:

)

tedy podle věty 2.24 také

`

A

1

!

(

A

2

!

:

:

:

!

(

A

n

!

A

)

:

:

:

)

odkud plyne

A

1

;

A

2

;

:

:

:

;

A

n

`

A

podle věty o dedukci.

Nakonec také

T

`

A

, protoľe

T

0

=

fA

1

;

A

2

;

:

:

:

;

A

n

g

je podmnoľinou

T

.

2.28

Věta o úplnosti v obou formách ukazuje, ľe přirozený pojem logicky

pravdivé formule, pojem tautologie a tautologického důsledku se podařilo plně

charakterizovat ve formálním systému výrokové logiky pojmem dokazatelnosti,

tedy volbou axiomů a odvozovacího pravidla. Odtud je odvozen i název těchto

vět.

Jiľ věta 2.24 dovoluje rozpoznat dokazatelnou formuli, aniľ bychom byli nu-

ceni konstruovat její důkaz. Je pouze třeba se přesvědčit, ľe daná formule je tau-

tologií, to znamená vyąetřit pravdivostní hodnoty při vąech ohodnoceních jejích

prvotních podformulí. Má-li daná formule

n

prvotních podformulí, je to celkem

2

n

ohodnocení. Tato úloha je tedy exponenciálně sloľitá.

Pokud bychom se spokojili s tímto řeąením, mohli bychom na tomto místě

skončit s vyąetřováním operace

`

dokazatelnosti a logického důsledku a vľdy

místo ní jen zkoumat operaci

j

= tautologického důsledku. Chceme-li vąak hlou-

běji proniknout do struktury důkazů výrokové logiky, je třeba se pojmem doka-

zatelnosti jeątě zabývat.

30

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

Dosud jsme se zabývali jen formulemi sestrojenými ze dvou základních lo-

gických spojek negace

:

a implikace

!

. Budeme se nyní zabývat vąemi for-

mulemi, tedy i takovými, které jsou sestrojeny za pomoci odvozených logických

spojek konjunkce &, disjunkce

_

a ekvivalence

$

. Ukáľeme několik základních

faktů.

2.29 Lemma

A

&

B

`

A

A

&

B

`

B

(v8)

A

;

B

`

A

&

B

(v9)

Demonstrace. (v8)

Výraz

A

&

B

je zkratkou za formuli

:

(

A

!

:B

). Podle (v2) platí

`

:A

!

(

A

!

:B

)

odkud

`

:

(

A

!

:B

)

!

A

(v3), (v5), MP

Z věty o dedukci dostáváme

A

&

B

`

A

Podobně z axiomu (A1) dostáváme

`

:B

!

(

A

!

:B

)

odkud

`

:

(

A

!

:B

)

!

B

(v3), (v5), MP

tedy

A

&

B

`

B

(v9) Z (v4) dostáváme

A;

B

`

::B

dále z (v6) pomocí věty o dedukci plyne

A;

::B

`

:

(

A

!

:B

)

takľe celkem

A;

B

`

A

&

B

2.30 Důsledek Uvědomíme-li si, ľe výraz

A

$

B

je zkratkou za formuli

(

A

!

B

)&(

B

!

A

), dostáváme

2.4.

VĚTY

O

ÚPLNOSTI

31

(i)

A

$

B

`

A

!

B

(ii)

A

$

B

`

B

!

A

(iii)

A

!

B

;

B

!

A

`

A

$

B

(iv) Je-li

`

A

$

B

, potom pro libovolnou mnoľinu formulí

T

platí

T

`

A

právě kdyľ

T

`

B

.

2.31

Důsledek

(i)

`

A

$

(

A

&

A

)

(idempotence)

(ii)

`

(

A

&

B

)

$

(

B

&

A

)

(komutativnost)

(iii)

`

((

A

&

B

)&

C

)

$

(

A

&(

B

&

C

))

(asociativnost)

(iv)

`

(

A

1

!

(

A

2

!

:

:

:

(

A

n

!

B

)

:

:

:

))

$

((

A

1

&

A

2

&

:

:

:

A

n

)

!

B

)

K formulaci pravé strany ekvivalence (iv) poznamenejme, ľe na uzávorkování

konjunkce jiľ nezáleľí, protoľe podle (iii) je konjunkce asociativní.

2.32

V

ěta

o

ekviv

alenci

Nech» formule

A

0

vznikne z formule

A

nahra-

zením některých výskytů podformulí

A

1

;

A

2

;

:

:

:

;

A

n

formulemi

A

0

1

;

A

0

2

;

:

:

:

;

A

0

n

.

Je-li

`

A

1

$

A

0

1

;

:

:

:

;

`

A

n

$

A

0

n

(9)

potom

`

A

$

A

0

.

Demonstrace. Indukcí podle sloľitosti formule

A

.

a)

A

je prvotní formule nebo některá z formulí

A

1

;

A

2

;

:

:

:

;

A

n

. Potom buď

A

0

je

A

, to v případě ľe k nahrazení nedojde, nebo

A

0

je některá formule

A

0

i

v případě, ľe

A

je formule

A

i

. Tvrzení věty plyne z předpokladů (9) a (v1).

b)

A

je tvaru

:B

a pro formuli

B

jiľ bylo tvrzení věty dokázáno. Tedy

`

B

$

B

0

, odkud

`

B

!

B

0

a pomocí (v5) dostáváme

`

A

0

!

A

. Podobně se

dokáľe

`

A

!

A

0

.

c)

A

je tvaru

B

!

C

a pro formule

B

;

C

jiľ bylo tvrzení věty dokázáno.

Tedy

32

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

`

B

$

B

0

`

C

$

C

0

Z důsledku 2.30 dostáváme

`

B

0

!

B

`

C

!

C

0

(10)

Následující tvrzení je zobecněním věty o skládání implikací z příkladu 2.20.

`

(

B

0

!

B

)

!

((

B

!

C

)

!

((

C

!

C

0

)

!

(

B

0

!

C

0

)))

(11)

Podle téhoľ příkladu 2.20 můľeme zaměnit druhý a třetí předpoklad implikace

(11) a dvojím uľitím pravidla modus ponens z (10) dostáváme

`

(

B

!

C

)

!

(

B

0

!

C

0

)

a to je

`

A

!

A

0

Symetricky dokáľeme i obrácenou implikaci a tím i tvrzení věty.

2.33 Lemma (de Morganova pravidla)

(i)

`

:

(

A

&

B

)

$

(

:A

_

:B

)

(ii)

`

:

(

A

_

B

)

$

(

:A

&

:B

)

Demonstrace. Z (v3), (v4) a důsledku 2.30 (iii) plyne

`

A

$

::A

. Uľitím

věty o ekvivalenci dokáľeme (i), (ii) se dokazuje obdobně.

`

:

(

A

&

B

)

$

::

(

A

!

:B

)

`

$

(

::A

!

:B

)

`

$

(

:A

_

:B

)

2.34 Důsledek

(i)

`

A

!

(

A

_

B

)

`

B

!

(

A

_

B

)

(ii)

`

A

$

(

A

_

A

)

(idempotence)

(iii)

`

(

A

_

B

)

$

(

B

_

A

)

(komutativnost)

(iv)

`

((

A

_

B

)

_

C

)

$

(

A

_

(

B

_

C

))

(asociativnost)

2.4.

VĚTY

O

ÚPLNOSTI

33

Demonstrace. (i) Podle denice disjunkce je

`

(

A

_

B

)

$

(

:A

!

B

), proto

formule

A

!

(

A

_

B

) je obdobou (v2) a

B

!

(

A

_

B

) je případ axiomu

(A1).

(ii) - (iv) Podle de Morganových pravidel pro libovolné formule

C

;

D

je

`

:

(

C

_

D

)

$

(

:C

&

:D

). Tak lze důkaz (ii) - (iv) převést na důsledek 2.31.

Následující věta je zobecněním lemmatu 2.23 o neutrální formuli.
2.35 Věta o důkazu rozborem případů Nech»

T

je mnoľina formulí a

nech»

A;

B

;

C

jsou formule. Potom platí

T

;

A

_

B

`

C

právě kdyľ

T

;

A

`

C

a

T

;

B

`

C

.

Demonstrace. a) Je-li

T

;

(

A

_

B

)

`

C

potom z důsledku 2.34 (ii) a z věty

o dedukci také

T

;

A

`

(

A

_

B

)

a

T

;

B

`

(

A

_

B

)

odkud plyne tvrzení věty.

b) Je-li naopak

T

;

A

`

C

a

T

;

B

`

C

, Podle věty o dedukci a (v5)

dostáváme

T

;

:C

`

:A;

:B

odkud z (v9) plyne

T

;

:C

`

:A

&

:B

Uľitím de Morganova pravidla a věty o dedukci dostáváme

T

;

`

:C

!

:

(

A

_

B

)

Odtud tvrzení plyne z axiomu (A3), pravidla modus ponens a věty o dedukci.

2.36 Důsledek (distributivnost konjunkce a disjunkce)

(i)

`

(

A

_

(

B

&

C

))

$

((

A

_

B

)&(

A

_

C

))

(ii)

`

(

A

&(

B

_

C

))

$

((

A

&

B

)

_

(

A

&

C

))

Demonstrace. (i) a) Nejprve dokáľeme implikaci zleva doprava. Podle dů-

sledku 2.34 (i) platí

A

`

(

A

_

B

)

A

`

(

A

_

C

)

tedy podle (v9)

A

`

(

A

_

B

) & (

A

_

C

)

Podobně z (v8)

34

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

B

&

C

`

B

B

&

C

`

C

odkud z důsledku 2.34 (i) pouľitím pravidla modus ponens dostáváme

B

&

C

`

A

_

B

B

&

C

`

A

_

C

nakonec

B

&

C

`

(

A

_

B

) & (

A

_

C

)

a tvrzení plyne z věty 2.35 o důkazu rozborem případů.

b) Implikaci zprava doleva dokáľeme takto. Podle (v8) platí

(

A

_

B

) & (

A

_

C

)

`

(

A

_

B

)

;

(

A

_

C

)

Podle denice disjunkce je formule

A

_

B

zkratka za implikaci

:A

!

B

.

Odtud plyne

:A;

A

_

B

`

B

:A;

A

_

C

`

C

Pomocí (v9) a věty o dedukci pak dostáváme

(

A

_

B

) & (

A

_

C

)

`

:A

!

(

B

&

C

)

tedy

`

((

A

_

B

) & (

A

_

C

))

!

(

A

_

(

B

&

C

))

2.5 Standardní tvary výrokových formulí
Na závěr kapitoly o výrokové logice ukáľeme, ľe kaľdou výrokovou formuli lze

ekvivalentně vyjádřit ve dvou standardních tvarech. Při denici syntaktických

tvarů standardních forem máme moľnost volit spojky, které pouľijeme a potom

jeątě pořadí, v jakém budou pouľity. V předchozím výkladu jsme ukázali, ľe kon-

junkce a disjunkce mají řadu pěkných vlastností, jsou komutativní, asociativní

a distributivní. Základní spojky negace a implikace podobné vlastnosti nemají,

nicméně bez negace se při vyjádření výrokových formulí nemůľeme obejít. Stan-

dardní formy budeme vytvářet pomocí negace, disjunkce a konjunkce, přitom ne-

gaci pouľijeme jako první jen u prvotních formulí. Jedna standardní forma bude

pouľívat disjunkci před konjunkcí a druhá naopak. Tak vzniknou konjunktivní a

disjunktivní standardní tvary formulí.

2.37 Syntax standardních tvarů výrokových formulí Nech»

L

P

je

jazyk výrokové logiky nad mnoľinou prvotních formulí

P

.

(i) Indukcí denujeme následující typy formulí

prvotní formule

2.5.

ST

AND

ARDNÍ

TV

AR

Y

VÝR

OK

O

VÝCH

F

ORMULÍ

35

literály

jsou prvotní formule a negace prvotních formulí

klauzule

jsou disjunkce literálů

(ii) Říkáme, ľe formule je v konjunktivním tvaru, je li to konjunkce klauzulí.

(iii) Říkáme, ľe formule je v disjunktivním tvaru, je-li to disjunkce konjunkcí

literálů.

Tedy formule v konjunktivním tvaru se vytvářejí tak, ľe nejprve pouľijeme negaci

jen u prvotních formulí, potom disjunkcí z literálů tvoříme klauzule a nakonec

konjunkcí z klauzulí vytvoříme konjunktivní tvar. Disjunktivní tvar formule se

tvoří obdobně, jen s opačným pořadím pouľití konjunkce a disjunkce. Z literálů

tvoříme nejprve konjunkce a z nich nakonec disjunkce.

Konjunktivní tvar formulí nachází uplatnění například ve strojovém dokazo-

vání vět, zatímco disjunktivní tvar formulí má blíľe k databázovým aplikacím.

2.38

Příklad

Nech»

p

1

;

p

2

;

:

:

:

jsou prvotní formule.

a) (

p

1

_

:p

3

_

p

6

) &

p

1

& (

p

2

_

p

7

) je formule v konjunktivním tvaru.

b) (

p

2

&

:p

3

&

:p

10

&

p

16

)

_

(

:p

1

&

:p

3

)

_

(

p

2

&

:p

7

)

_

(

:p

5

&

:p

9

)

je formule v disjunktivním tvaru.

2.39

V

ěta

Ke kaľdé formuli

A

výrokové logiky lze sestrojit formuli

A

k v

konjunktivním tvaru a formuli

A

d v disjunktivním tvaru tak, ľe

`

A

$

A

k

a

`

A

$

A

d

Demonstrace. Indukcí podle sloľitosti formule

A

sestrojujeme její ekviva-

lentní konjunktivní a disjunktivní tvar.

a) Je-li

A

prvotní formule, potom

A

je v konjunktivním i disjunktivním

tvaru a není co dokazovat.

b) Předpokládejme, ľe

A

je formule

:B

a ľe konjunktivní tvar

B

k a

disjunktivní tvar

B

d formule

B

jiľ byly sestrojeny. Z předpokladu

`

B

$

B

d

vyplývá

`

:B

$

:B

d

Je-li

B

d tvaru

B

1

_

B

2

_

:

:

:

_

B

n , kde

B

i je tvaru

Li

1

&

Li

2

&

:

:

:

&

Li

m

i

pro

i

n

36

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

potom podle de Morganových pravidel

`

:B

$

(

:B

1

&

:B

2

&

:

:

:

&

:B

n)

a pro kaľdé

i

n

je

:B

i

$

(

:Li

1

_

:Li

2

_

:

:

:

_

:Li

m

i

)

Označíme-li

A

i formuli, která vznikne z (

:Li

1

_

:Li

2

_

:

:

:

_

:Li

m

i

) tím, ľe

vynecháme dvojité negace u prvotních formulí v negovaných literálech, potom

A

i je konjunkce literálů a

`

A

$

(

A

1

&

A

2

&

:

:

:

A

n)

kde na pravé straně ekvivalence je konjunktivní tvar

A

k formule

A

.

Stejným způsobem se pomocí de Morganových pravidel z formule

:B

k se-

strojí disjunktivní tvar

A

d formule

A

.

Ukázali jsme, ľe k negaci formule v konjunktivním tvaru lze sestrojit ekviva-

lentní formuli v disjunktivním tvaru a k negaci formule v disjunktivním tvaru lze

sestrojit ekvivalentní formuli v konjunktivním tvaru.

c) Předpokládejme, ľe formule

A

je tvaru

B

!

C

a ľe formule

B

d

;

C

d

;

B

k

;

C

k jsou jiľ sestrojeny. Podle denice disjunkce

`

(

B

!

C

)

$

(

:B

_

C

)

(12)

K sestrojení disjunktního tvaru formule

A

stačí sestrojit disjunktivní tvar

D

formule

:B

k a formule

D

_

C

d je disjunktivním tvarem formule

A

.

Konjunktivní tvar formule

A

sestrojíme pomocí distributivity konjunkce a

disjunkce. Vyjdeme opět z ekvivalence (12), ale místo formule

:B

k v disjunkci

uvaľujeme formuli

:B

d . K této formuli sestrojíme ekvivalentní formuli v kon-

junktivním tvaru

D

1

&

D

2

&

:

:

:

&

D

n , kde formule

D

i

;

i

n

jsou klauzule,

tedy disjunkce literálů. Dostáváme

`

A

$

((

D

1

&

D

2

&

:

:

:

&

D

n)

_

C

k)

odkud z distributivity plyne

`

A

$

((

D

1

_

C

k) & (

D

2

_

C

k) &

:

:

:

&(

D

n

_

C

k))

(13)

Dále formule

C

k je v konjunktivním tvaru je tedy konjunkcí klauzulí

D

0

1

&

D

0

2

&

:

:

:

&

D

0

m . Z distributivity pak pro kaľdé

i;

i

n

platí

(

D

i

_

C

k)

$

((

D

i

_

D

0

1

)&(

D

i

_

D

0

2

)

:

:

:

(

D

i

_

D

0

m))

kde na pravé straně je jiľ formule v konjunktivním tvaru. Proto i pravou stranu

ekvivalence (13) lze převést do konjunktivního tvaru. Tím je věta dokázána.

2.40 Důkazy a demonstrace V této kapitole jsme poprvé pracovali s ně-

jakým formálním systémem a proto jsme důsledně rozliąovali mezi formálním

2.5.

ST

AND

ARDNÍ

TV

AR

Y

VÝR

OK

O

VÝCH

F

ORMULÍ

37

důkazem ve smyslu uvedené denice a demonstrací, která na některých místech

přechází od dokazatelnosti jedné formule k dokazatelnosti jiné formule aniľ by

konstruovala vąechny kroky jejího důkazu. Sestrojili jsme jen jeden formální důkaz

jednoho z nejjednoduąąích tvrzení výrokové logiky, formule (v1). Upozornili jsme

na to, ľe formální důkazy daląích tvrzení rostou do délky, protoľe pouľití nějaké

jiľ dokázané věty znamená připojit její důkaz k důkazu, který konstruujeme. To

je v principu moľné, ale těľko proveditelné. V Russellově a Whiteheadově knize

Principia Mathematica

je dán odhad, ľe formální důkaz věty 0

6

= 1 v jejich for-

málním systému aritmetiky má nejméně tři tisíce kroků. Proto jsme u prakticky

vąech dokazovaných vět výrokové logiky uváděli demonstrace opírající se o větu

o dedukci.

Máme za to, ľe čtenář jiľ umí rozliąit mezi formálním důkazem ve smyslu

uvedené denice a neformální demonstrací, která zachycuje hlavní kroky důkazu.

V daląím výkladu budeme slovo důkaz, jak je v literatuře obvyklé, pouľívat i k

označení demonstrací.

38

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

2.6

Cvičení

A

Dokaľte
Implikace

a) (

A

!

(

B

!

C

))

!

(

B

!

(

A

!

C

))

(zaměnitelnost

antecedentů implikace)

b) (

A

!

B

)

!

[(

B

!

C

)

!

(

A

!

C

)]

(skládání implikací)

c) (

A

!

B

)

!

(

:B

!

:A

)

d) (

:A

!

B

)

!

(

:B

!

A

)

e) (

A

!

:B

)

!

(

B

!

:A

)

Konjunkce

a) (

A

&

B

)

!

A

b) (

A

&

B

)

!

B

c) (

A

!

(

B

!

(

A

&

B

)))

d) (

A

&

B

)

!

(

B

&

A

)

(komutativnost)

e) ((

A

&

B

) &

C

)

!

(

A

& (

B

&

C

))

(distributivnost)

(

A

& (

B

&

C

))

!

((

A

&

B

) &

C

)

(distributivnost)

f) (

A

&

A

)

!

A

(idempotence)

A

!

(

A

&

A

)

(idempotence)

g) (

A

!

B

)

!

[(

C

!

D

)

!

((

A

&

C

)

!

(

B

&

D

))]

Ekvivalence

a) (

A

$

B

)

!

(

A

!

B

)

b) (

A

$

B

)

!

(

B

!

A

)

c) (

A

!

B

)

!

[(

B

!

A

)

!

(

A

$

B

)]

d) (

A

$

B

)

$

(

B

$

A

)

e) (

A

$

B

)

$

(

:A

$

:B

)

2.6.

CVIČENÍ

A

39

f) (

:A

!

:B

)

$

(

B

!

A

)

g) (

A

!

:B

)

$

(

B

!

:A

)

h) (

:A

!

B

)

$

(

:B

!

A

)

Disjunkce

a)

A

!

(

A

_

B

)

b)

B

!

(

A

_

B

)

c) (

A

!

C

)

!

[(

B

!

C

)

!

((

A

_

B

)

!

C

)]

(

A

!

C

)

!

[(

B

!

D

)

!

((

A

_

B

)

!

(

C

_

D

)]

d) (

A

_

A

)

$

A

(idempotence)

e) (

A

_

B

)

$

(

B

_

A

)

(komutativnost)

f) ((

A

_

B

)

_

C

)

$

(

A

_

(

B

_

C

))

(asociativnost)

Věta o důkazu rozborem případů
Nech»

T

je mnoľina formulí, nech»

A;

B

;

C

jsou formule, potom platí

T

;

(

A

_

B

)

`

C

, právě kdyľ

T

;

A

`

C

a

T

;

B

`

C

(k důkazu pouľijte lemmatu o neutrálni formuli)

Distributivita

a) (

A

& (

B

_

C

))

$

[(

A

&

B

)

_

(

A

&

C

)]

b) (

A

& (

B

1

_

B

2

_

:

:

:

_

B

n

))

$

[(

A

&

B

1

)

_

(

A

&

B

2

)

_

:

:

:

_

(

A

&

B

n

)]

c) (

A

_

(

B

&

C

))

$

[(

A

_

B

) & (

A

_

C

)]

d) (

A

_

(

B

1

&

B

2

&

:

:

:

&

B

n

))

$

[(

A

_

B

1

) & (

A

_

B

2

) &

:

:

:

& (

A

_

B

n

)]

40

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

Normální tvary výrokových formulí
Nech»

A;

B

;

C

;

D

;

E

;

:::

jsou prvotní formule. Sestrojte konjunktivní tvary násle-

dujících formulí

a) ((

A

_

B

)

!

(

A

&

B

))

b) (((

A

!

B

)

!

B

)

!

A

)

c) (

:

(

A

_

:A

)

!

(

A

_

:A

))

d) (

A

!

:

(

A

!

:A

))

e) ((

A

&

B

)

$

(

B

&

A

))

f) ((

A

!

B

)

_

(

B

!

A

))

(

C

!

(

D

!

E

))

!

[(

C

!

E

)

!

(

D

!

E

)]

(

C

!

:D

)

$

(

D

!

:C

)

(

:E

!

F

)

$

(

:F

!

E

)

g) Sestrojte disjunktivní tvary formulí a) - f).
h) Rozhodněte, které z formulí a) - f) jsou dokazatelné ve výrokové logice.

Dokaľte je.

2.7

Cvičení

B

1. (Indukce podle sloľitosti formule)

Nech» je mnoľina vąech formulí výrokové logiky taková, ľe

(i) obsahuje mnoľinu vąech prvotních formulí.

(ii) Jsou-li

A

,

B

formule výrokové logiky,

A

,

B

2

, potom i

:A

, (

A

2

B

)

2

, kde

2

je symbol &,

_

,

!

nebo

$

.

Potom kaľdá výroková formule je prvkem .

2. Nech»

L

je nějaký jazyk, libovolnou konečnou posloupnost

0

,

1

:

:

:

n

symbolů jazyka

L

nazveme výrazem (slovem) jazyka

L

,

a

=

0

:

:

:

n,

b

=

n

+1

:

:

:

n

+

m, potom výraz

0

:

:

:

n

n

+1

:

:

:

n

+

m, který vznikne připo-

jením slova

b

za slovo

a

označíme

ab

a nazveme ho zřetězením (konkatenace)

slov

a

,

b

. Označíme-li symbolem

o

prázdnou posloupnost symbolů, potom

pro libovolná slova

a

,

b

,

c

platí

ao

=

oa

=

a;

(

ab

)

c

=

a

(

bc

)

:

2.7.

CVIČENÍ

B

41

Zřetězení je tedy asociativní operace na mnoľině vąech slov. Tato operace

je komutativní, právě kdyľ jazyk

L

obsahuje nejvýą jeden symbol.

3. (Polský zápis formulí)

Nech»

L

0

je jazyk výrokové logiky s mnoľinou

P

prvotních formulí, ale

bez pomocných symbolů (závorek). Následující syntaktická pravidla denují

bezzávorkový (polský) zápis formulí výrokové logiky. Přitom slovo, které

sestává z jediného symbolu

ztotoľňujeme s tímto symbolem.

(i) Kaľdá prvotní formule je formule.

(ii) Jsou-li výrazy

a

,

b

formule, potom výrazy

:

a

,

_

ab

, &

ab

,

!

ab

,

$

ab

jsou také formule.

(iii) Kaľdá formule vznikne konečným pouľitím pravidel (i) a (ii).

Platí:

(a) Je-li

a

formule (podle předchozí denice), potom buď

a

je prvotní

formule, nebo

a

je tvaru

:b

nebo

2

ab

, kde

b

,

c

jsou formule a

2

je

některý ze symbolů pro logické spojky &,

_

,

!

,

$

.

(b) Je-li

a

formule tvaru

a

0

a

1

:

:

:

a

n

, kde

a

i

,

i

n

jsou formule nebo

slova sestávající z jediného symbolu pro logickou spojku, potom výraz

a

0

:

:

:

a

i

pro ľádné

i

<

n

není formule.

(c) Je-li

a

formule tvaru

:b

nebo

2

bc

(viz bod(a)), potom symbol

2

a

formule

b

,

c

jsou jednoznačně určeny.

[Návod:

(a) se dokáľe indukcí podle sloľitosti formule,

(b) indukcí podle počtu zřetězených slov, (c) je důsledkem (b).]

Tento druh zápisu formulí se také nazývá prexní

, podle toho, ľe symbol

pro logickou spojku předchází obě formule, které spojuje. Jeho výhodou je

jednoznačné členění formulí bez pouľití závorek. Obvyklejąí zápis formulí

zavedený v textu se nazývá inxní

.

4. Formulujte obdobu (a) { (c) z předchozího cvičení pro inxní zápis formulí.
5. Odvozovací pravidlo: z formulí

:A

_

B

,

A

_

C

odvoďte formuli

B

_

C

se nazývá pravidlo řezu. V různých variantách je typické pro Gentzenovy

sytémy výrokové logiky. Pravidlo řezu se pouľívá při takzvaném strojovém

dokazování vět rezoluční metodou na samočinných počítačích.

Dokaľte, ľe pravidlo řezu můľe nahradit pravidlo modus ponens a naopak.
[Návod:

42

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

(a) ve výrokové logice pro libovolné formule

A

,

B

,

C

dokaľte (

:A

_

B

),

(

A

_

C

)

`

(

B

_

C

).

(b) ve formálním systému, který vznikne z výrokové logiky vypuątěním

odvozovacího pravidla modus ponens a přidáním pravidla řezu, pro

libovolné formule

A

,

B

dokaľte

A

,

A

!

B

`

B

. Poľijte 6(a).]

6. Ukaľte, ľe schema (A3) můľe být nahrazeno následujícím schematem

(A4)

(

:B

!

:A

)

!

((

:B

!

A

)

!

B

)

pro libovolné formule

A

,

B

. To znamená, ľe kaľdá formule (A4) je větou

výrokové logiky a kaľdá formule (A3) je větou formálního systému, který

vznikne z výrokové logiky nahrazením schematu (A3) schematem (A4).

7. Konečnou posloupnost nul a jedniček budeme nazývat

Boole

ovská

posloup-

nost

. Říkáme, ľe funkce

f

je

Boole

ovská

funkce

n

proměnných, jestliľe

f

přiřazuje kaľdé Booleovské posloupnosti délky

n

hodnotu 0 nebo 1.

Kaľdé formuli

A

výrokové logiky, která obsahuje

n

prvotnívh formulí, lze

jednoznačně přiřadit Booleovskou funkci

f

A

: Jsou-li

P

1

;

:

:

:

;

P

n

vąechny pr-

votní formule, které se vyskytují v

A

a je-li

p

1

;

:

:

:

;

p

n

libovolná Booleovská

posloupnost délky

n

, poloľíme

f

A

(

p

1

;

:

:

:

;

p

n

) =

v

(

A

)

;

kde

v

je nějaká valuace prvotních formulí taková, ľe

v

(

P

i

) =

p

i

platí pro

i

n

. (Na ohodnocení ostatních prvotních formulí nezáleľí).

Přirozeným způsobem lze přiřadit Booleovské funkce i logickým spojkám.

Negaci odpovídá unární funkce

f

:

denovaná předpisem

f

:

(0) = 1

;

f

:

(1) = 0

:

Ostatním spojkám odpovídají binární funkce denované takto:

p

1

p

2

f

&

(

p

1

;

p

2

)

f

_

(

p

1

;

p

2

)

f

!

(

p

1

;

p

2

)

f

$

(

p

1

;

p

2

)

0 0

0

0

1

1

0 1

0

1

1

0

1 0

0

1

0

0

1 1

1

1

1

1

Je zřejmé, ľe pro libovolnou formuli

A

lze Booleovskou funkci

f

A

denovat

pomocí funkcí přiřazených logickým spojkám, dokonce jen pomocí funkcí

f

:

a

f

!

.

Říkáme, ľe mnoľina

F

Booleovských funkcí tvoří úplný systém, jestliľe kaľ-

dou Booleovskou funkci lze denovat pomocí Booleovských funkcí mnoľiny

F

.

2.7.

CVIČENÍ

B

43

(a) Dokaľte, ľe dvouprvková mnoľina

ff

:

;

f

!

g

sestávající z funkcí

f

:

,

f

!

tvoří úplný systém.

(b) Dokaľte, ľe mnoľiny

ff

:

;

f

&

g

,

ff

:

;

f

_

g

tvoří úplný systém.

(c) Dokaľte, ľe mnoľiny

ff

&

;

f

_

g

,

ff

:

;

f

$

g

úplný systém netvoří.

[Návod:

(a) pomocí věty o disjunktním tvaru výrokové formule ukaľte, ľe kaľdá

Booleovská funkce je tvaru

f

A

pro jistou formuli.

(b) ukaľte, ľe implikaci lze vyjádřit pomocí negace a konjunkce (disjunkce).

(c) ukaľte, ľe negaci nelze vyjádřit pomocí konjunkce a disjunkce a ľe

implikaci nelze vyjádřit pomocí negace a ekvivalence.]

8. Připomeňme, ľe formule

A

je v konjunktivním (disjunktivním) tvaru, je-li

konjunkcí (disjunkcí) konečného počtu formulí

A

1

;

:

:

:

;

A

n

, z nichľ kaľdá je

disjunkcí (konjunkcí) prvotních formulí a negací prvotních formulí. Formu-

lím

A

1

;

:

:

:

;

A

n

říkáme sloľky formule

A

.

(a) Ukaľte, ľe formule

A

v konjunktivním tvaru je tautologie, právě kdyľ

kaľdá její sloľka obsahuje dva opačné literály (to znamená jistou pr-

votní formuli a její negaci).

(b) Ukaľte, ľe formule

A

v disjunktivním tvaru je splnitelná, tedy prav-

divá při alespoň jednom ohodnocení, právě kdyľ alespoň jedna sloľka

formule

A

neobsahuje dva opačné literály.

9. Je-li

T

mnoľina formulí, ukaľte, ľe následující tvrzení jsou ekvivalentní.

(a)

T

je sporná,

(b) pro nějakou formuli

A;

T

`

A

a

T

`

:A

,

(c) pro nějakou formuli

A;

T

`

(

A

&

:A

).

44

KAPITOLA

2.

VÝR

OK

O

V

Á

LOGIKA

Kapitola

3

Predik

áto

v

á

logik

a

V této kapitole se budeme zabývat predikátovou logikou prvního řádu. Budeme

denovat jazyk prvního řádu a jeho sémantiku, zavedeme formální systém pre-

dikátové logiky bez rovnosti, dokáľeme základní věty predikátové logiky, Větu

o dedukci a Větu o uzávěru. Ukáľeme, ľe kaľdou formuli predikátové logiky lze

převést do ekvivalentního standardního tvaru { prenexního normálního tvaru for-

mule. Nakonec zavedeme axiomy rovnosti a dokáľeme základní věty predikátové

logiky s rovností.
3.1 Jazyk a jeho sémantika
Ve výrokové logice jsme detailně zkoumali vlastnosti logických spojek, nyní bu-

deme pracovat s jazykem logiky 1. řádu, který kromě spojek obsahuje jeątě pro-

měnné, funkční symboly a predikátové symboly.

3.1

Jazyk

prvního

řádu

obsahuje

(i) neomezeně mnoho symbolů pro proměnné

x;

y

;

z

;

x

1

;

x

2

;

:

:

:

(ii) symboly pro logické spojky

:;

&

;

_;

!;

$

(iii) symboly pro kvantikátory

8

(obecný),

9

(existenční)

(iv) symboly pro predikáty

p;

g

;

p

1

;

:

:

:

S kaľdým symbolem je dáno přirozené číslo

n

1, které udává počet argumentů

(četnost) predikátu. Pokud je dán i binární predikátový symbol =, mluvíme o

jazyku s rovností.

(v) symboly pro funkce

f

;

g

;

:

:

:

U kaľdého symbolu je dáno přirozené číslo

n

0, které udává četnost funkčního

symbolu. Funkční symboly četnosti nula chápeme jako konstanty.

Má-li funkční nebo predikátový symbol četnost

n

, říkáme, ľe je to symbol

n

-ární. Pro četnost jedna, dvě, tři jsou vľitá označení unární, binární a ternární.

45

46

KAPITOLA

3.

PREDIKÁ

TO

V

Á

LOGIKA

(vi) pomocné symboly (závorky) (

;

)

;

[

;

]

;

:

:

:

Symboly pro proměnné, spojky a kvantikátory nazýváme logické, pokud jde

o jazyk s rovností, symbol predikátu rovnosti rovněľ počítáme k logickým symbo-

lům. Symboly pro ostatní predikáty a symboly pro funkce určují speciku jazyka

(a odráľejí oblast, kterou jazyk můľe popisovat). Proto je nazýváme speciální.

Jazyk 1. řádu je dán výčtem speciálních symbolů.

3.2 Příklad a) Jazyk teorie uspořádání je jazyk s rovností a obsahuje jediný

speciální symbol

<

, je to binární predikátový symbol.

b) Jazyk teorie grup je jazyk 1. řádu s rovností, který obsahuje dva speciální

symboly

e

, konstantu pro jednotkový prvek, a binární funkční symbol `

' pro

grupovou operaci.

c) Jazyk teorie okruhů je jazyk s rovností, který obsahuje dva binární funkční

symboly + (pro sčítání) a

(pro násobení) a dvě konstanty 0

;

1 pro nulu a

jednotkový prvek.

d) Jazyk teorie mnoľin je jazyk s rovností a má jediný speciální symbol

2

,

binární predikátový symbol pro náleľení.

e) Jazyk elementární aritmetiky (s rovností) obsahuje funkční symboly 0 (kon-

stantu pro nulu),

S

(unární symbol pro následující přirozené číslo), + a

(bi-

nární symboly pro sčítání a násobení.

Výrazy jazyka 1. řádu, které mají matematický význam, lze rozdělit do dvou

hlavních skupin: termy a formule. Termy popisují individua (objekty), které lze

sestrojit pomocí operací. Formule jsou tvrzení.

3.3 Termy Induktivně popíąeme konstrukci termů.

(i) Kaľdá proměnná je term.

(ii) Jsou-li výrazy

t

1

;

:

:

:

;

t

n

termy a je-li

f

n

-ární funkční symbol, potom

výraz

f

(

t

1

;

:

:

:

;

t

n

) je term.

(iii) Kaľdý term vznikne konečným pouľitím pravidel (i) a (ii).

3.4 Příklad V jazyce elementární aritmetiky jsou následující výrazy termy:

0

;

S

(

x

)

;

S

(

S

(0))

;

:

:

:

. U vľitých binárních symbolů + a

, případně jiných,

píąeme (

x

+

y

)

;

(

t

1

+

t

2

) namísto +(

x;

y

)

;

+(

t

1

;

t

2

) a (

x

y

) namísto

(

x;

y

).

Proto také ((

x

+

y

)

0

;

((

S

(0)+(

x

y

))

S

(0)) jsou termy. Je-li

f

n

-ární funkční

symbol, také

f

((

x

y

)

;

y

1

;

y

2

;

:

:

:

;

y

n

1

) je term.

3.5 Formule Konstrukci formule popíąeme induktivně.

(i) Je-li

p

n

-ární predikátový symbol a jsou-li výrazy

t

1

;

:

:

:

;

t

n

termy, potom

výraz

p

(

t

1

;

:

:

:

;

t

n

) je atomická formule.

(ii) Jsou-li výrazy

A;

B

formule, potom

:A;

(

A

&

B

)

;

(

A

_

B

)

;

(

A

!

B

) a (

A

$

B

) jsou formule.

3.1.

JAZYK

A

JEHO

SÉMANTIKA

47

(iii) Je-li

x

proměnná,

A

formule, potom (

8x

)

A;

(

9x

)

A

jsou formule.

(iv) Kaľdá formule vznikne konečným pouľitím pravidel (i) { (iii).

Podobně jako v případě binárních funkčních symbolů +

;

atd. budeme psát

(

x

=

y

)

;

(

x

<

y

) namísto = (

x;

y

)

;

<

(

x;

y

) atd. V tomto případě píąeme

(

x

6

=

y

) namísto

:

(

x

=

y

).

3.6 Příklad a)

S

(0) = (0

x

) +

S

(0)

b) (

9x

)(

y

=

x

z

)

c) (

8x

)(

x

6

= 0

!

(

9y

)(

x

=

S

(

y

)))

jsou formule jazyka aritmetiky. Formule a) je atomická, formule b), c) nejsou

atomické.

Formule c) vznikla z atomických formulí (

x

= 0)

;

(

x

=

S

(

y

)) uľitím pravidel

(ii)

:

(

x

= 0)

(iii) (

9y

)(

x

=

S

(

y

))

(ii)

:

(

x

= 0)

!

(

9y

)(

x

=

S

(

y

))

(iii) (

8x

)(

:

(

x

= 0)

!

(

9y

)(

x

=

S

(

y

)))

Právě jsme se přesvědčili, ľe formule c) vznikla předepsaným způsobem. For-

mule, které jsme během konstrukce sestrojili, se nazývají podformule formule c).

3.7 Symboly, slova, zřetězení Z předchozích denic je zřejmé, ľe termy i

formule jsou jisté konečné posloupnosti symbolů daného jazyka sestavené podle

pevných pravidel. Libovolnou konečnou posloupnost symbolů budeme nazývat

krátce slovo nebo výraz. Je-li nějaký symbol

s

napsán na

i

-tém místě ve slově

S

, říkáme, ľe

s

se vyskytuje ve slově

S

na

i

-tém místě

. V takovém případě

i

-tý

symbol ve slově

S

nazýváme výskyt symbolu

s

v

S

. Například `(' se vyskytuje

ve formuli a) z příkladu 3.6 na druhém, ąestém a třináctém místě, symbol

x

se

vyskytuje v téľe formuli na devátém místě.

Spojování slov, kterému se také říká zřetězení (konkatenace), je nejjednoduąąí

operace, kterou lze se slovy provádět. Poslouľí nám k přesnějąímu popisu daląích

syntaktických pojmů, které budeme zavádět.

3.8 Slova a podslova Jsou-li

A;

B

slova, potom výrazem

AB

označíme

slovo, které vznikne ze slov

A;

B

tak, ľe nejprve napíąeme slovo

A

a za po-

slední symbol slova

A

(bez mezery) připojíme slovo

B

. Říkáme, ľe slovo

AB

je

zřetězením slov

A

a

B

.

Například slovo 112 vznikne zřetězení slov 1 12, slov 11 2 nebo také

prázdného slova a slova 112. Slovo, které vznikne spojením slov

A

1

;

A

2

;

:

:

:

;

A

n

v uvedeném pořadí, budeme označovat

A

1

A

2

:

:

:

A

n

.

48

KAPITOLA

3.

PREDIKÁ

TO

V

Á

LOGIKA

Říkáme, ľe slovo

C

je podslovem slova

A

, jestliľe slovo

A

má tvar

B

C

D

pro nějaká slova

B

;

D

, z nichľ jedno nebo obě mohou být prázdná.

3.9 Příklad Nech»

t

je term

f

(

x;

g

(

x;

y

)). Potom slova

g

(

x;

y

) a

g

(

x;

y

))

jsou podslova

t

. První z nich ja samo také termem, druhé ne.

Podobně slovo (

8x

) je podslovem formule c) z příkladu 3.6, ale samo není

formulí.

3.10 Podtermy, podformule, volné a vázané proměnné Nech»

t

je term

a

A

je formule.

(ia) Říkáme, ľe term

s

je podtermem termu

t

, je-li podslovem slova

t

.

(ib) Říkáme, ľe formule

B

je podformulí formule

A

, je-li

B

podslovem slova

A

.

(ii) Říkáme, ľe daný výskyt proměnné

x

ve formuli

A

je vázaný

, je-li součástí

nějaké podformule tvaru (

9x

)

B

nebo (

8x

)

B

formule

A

. Není-li daný výskyt

proměnné

x

vázaný, říkáme, ľe je volný.

(iii) Říkáme, ľe proměnná

x

je volná ve formuli

A

, má-li tam volný výskyt.

Říkáme, ľe proměnná

x

je vázaná ve formuli

A

, má-li tam vázaný výskyt.

(iv) Říkáme, ľe formule

A

je otevřená

, pokud

A

neobsahuje ľádnou vázanou

proměnnou. Říkáme, ľe

A

je uzavřená

, pokud

A

neobsahuje ľádnou volnou

proměnnou.

Je zřejmé, ľe otevřená formule vznikne ze svých atomárních podformulí jen

pomocí logických spojek, neobsahuje tedy ľádné kvantikátory. Uzavřená formule

naopak váľe kaľdou proměnnou některým kvantikátorem.

Uvědomme si, ľe táľ proměnná můľe být v dané formuli současně volná i

vázaná, například ve formuli (

x

=

z

)

!

(

9x

)(

x

=

z

) má proměnná

x

volný i

vázaný výskyt. Tato situace je umoľněna volností v denici formule, v matema-

tické praxi se větąinou takové formule nezavádějí. Jak uvidíme později, vázané

proměnné lze zaměnit a tak se podobné situaci můľeme vľdy vyhnout. Formule,

ve kterých kaľdá proměnná je buď volná (a není vázaná) nebo jenom vázaná (a

ne volná), se někdy nazývají formule s čistými proměnnými.

3.2 Sémantika predikátové logiky
Nyní jiľ máme k dispozici základní fakta a pojmy o syntaxi predikátové logiky,

zavedli jsme pojem termu, formule a vazby, které mohou mít proměnné ve formuli.

Můľeme zkoumat otázku struktur

M

, které realizují symboly jazyka

L

prediká-

tové logiky a zejména to, které formule jsou pravdivé v dané realizaci. Chceme-li

dát symbolům jazyka

L

nějakou matematickou interpretaci, je třeba nejprve začít

od proměnných. Oborem hodnot proměnných bude neprázdná mnoľina

M

6

=

;

,

3.2.

SÉMANTIKA

PREDIKÁ

TO

VÉ

LOGIKY

49

kterou nazveme univerzum

M

a její prvky budeme nazývat individua. Je-li vyme-

zeno univerzum, potom je přirozené se ptát, jak jsou realizovány operace, které

jsou naznačeny v jazyce

L

funkčními symboly. Například se můľeme ptát, které

individuum bude odpovídat součtu nebo jiné operaci z daných individuí univerza.

Funkční

n

-ární symbol

f

z jazyka

L

bude realizován zobrazením

f

M

:

M

n

!

M

tak, ľe rovnost

f

M

(

i

1

;

:

:

:

;

i

n

) =

j

pro

i

1

;

:

:

:

;

i

n

2

M

znamená, ľe individuum

j

bude výsledkem operace

f

provedené na individua

i

1

;

:

:

:

;

i

n

. Nakonec zbývají

predikátové symboly. Máme-li realizovat binární predikátový symbol

<

, který

\porovnává" individua, pouľijeme binární relaci

<

M

M

2

. Podobně realizace

n

-árních predikátových symbolů

p

budou

n

-ární relace

p

M

M

n

. Zvláątní

postavení zde má symbol =, který počítáme k symbolům logickým a který by

měl být realizován tak, aby odpovídal naąim představám o rovnosti. Proto jej ne-

realizujeme jinak neľ jako identitu individuí. V denici pravdivosti se to odráľí

zvláątní klauzulí, která denuje splňování atomických formulí s rovností. Ostatní

logické symboly, jako spojky a kvantikátory nemá smysl realizovat. Popsaná

struktura

M

, která obsahuje univerzum

M

a realizace funkcí a relací na tomto

univerzu, se nazývá relační struktura pro jazyk

L

nebo realizace jazyka

L

.

3.11

Realizace

jazyk

a

Nech»

L

je jazyk 1. řádu. Relační struktura

M

, která

obsahuje

neprázdnou mnoľinu

M

,

zobrazení

f

M

:

M

n

!

M

pro libovolný

n

-ární funkční symbol

f

z jazyka

L

,

n

-ární relaci

p

M

M

n

pro kaľdý

n

-ární predikátový symbol

p

, kromě

symbolu pro rovnost,

se nazývá realizace jazyka

L

. Prvky univerza

M

nazýváme individua, zobrazení

f

M

přísluąné k symbolu

f

a relaci

p

M

přísluąnou k predikátovému symbolu

p

nazýváme realizace funkčního symbolu

f

a realizace predikátového symbolu

p

.

3.12

Příklad

a) Struktura

h!

;

!

!

i

, kde

!

je mnoľina přirozených čísel, je realizací

jazyka z příkladu 3.2 a. Není to ovąem uspořádání.

b) Struktura

hfeg;

e;

e

i

, kde

e

je binární zobrazení

feg

2

!

feg

deno-

vané jediným moľným způsobem, je realizací jazyka teorie grup z příkladu 3.2 b.

Výsledkem je jednoprvková grupa.

c)

N

=

h!

;

;;

;

;

i

, kde

!

je mnoľina přirozených čísel,

;

realizuje

nulu,

je funkce, která číslu

n

přiřazuje následující přirozené číslo a

;

jsou

obvyklé operace součtu a součinu, je realizací jazyka elementární aritmetiky z

příkladu 3.2 e. Pokud

nahradíme nějakým číslem, například jednotkou, vznikne

50

KAPITOLA

3.

PREDIKÁ

TO

V

Á

LOGIKA

struktura, která je realizací jazyka teorie okruhů 3.2 c (to ovąem neznamená, ľe

je okruhem).

3.13 Realizace termů Chceme-li zkoumat pravdivost formulí v nějaké rea-

lizaci jazyka, musíme se nejprve vyrovnat s volnými proměnnými. Těm je třeba

vľdy přiřadit nějaké individuum jako hodnotu. Tuto úlohu budou plnit zobrazení,

které kaľdé proměnné přiřadí nějaké individuum. Zobrazení

e mnoľiny vąech pro-

měnných do univerza

M struktury

M

budeme nazývat ohodnocení proměnných.

Je-li

e ohodnocení proměnných, x proměnná a m

2

M , potom ohodnocení

proměnných, které proměnné

x přiřazuje individuum m a na vąech ostatních

proměnných splývá s ohodnocením

e budeme označovat e(x=m). Zobrazení e

tedy přiřazuje hodnotu vąem proměnným, které jsou nejjednoduąąími případy

termů. Indukcí podle sloľitosti termu

t lze ukázat, ľe ohodnocení e přiřazuje

termu

t jednoznačně hodnotu t[e], kterou budeme nazývat realizací termu t při

ohodnocení

e. Denujeme t[e] následujícím způsobem:

Je-li

t proměnná x, potom t[e] je e(x).

Je-li

t tvaru f(t

1

;:::;t

n

) a hodnoty

t

1

[

e];:::;t

n

[

e] jsou jiľ sestrojeny,

potom

t[e] je individuum f

M