Systémy úplných logických spojek

Nyní budeme zkoumat systémy spojek, které postačují k popisu celé výrokové logiky. Ukážeme si, že každá formule výrokové logiky se dá vyjádřit formulí obsahující kromě proměnných jen spojky negace, konjunkce a disjunkce.

De Morganovy zákony (tautologie (15) a (16)) a také pravidla (23) až (26) z předcházejícího odstavce dávají návod, jak lze pomocí ekvivalentní formule nahradit určitou výrokovou spojku jinými výrokovými spojkami.

Nabízí se tedy otázka, zda existují takové podmnožiny výrokových spojek, kterými lze nahradit všechny zbývající výrokové spojky a obsáhnout tak celou výrokovou logiku. Neboli zda můžeme pro každou formuli najít formuli logicky ekvivalentní, která však obsahuje jen předem dané výrokové spojky. Ano, existují takové systémy výrokových spojek.

Množina výrokových spojek M je funkčně úplná, jestliže lze pomocí těchto spojek vyjádřit všechny zbývající výrokové spojky, to znamená, jestliže lze každou formuli A přepsat na formuli A´ s ní ekvivalentní, která používá pouze spojky z množiny M.

Uvedeme si několik funkčně úplných množin výrokových spojek:

1) Množina je funkčně úplná.

To bude platit, podaří-li se nám pomocí spojek vyjádřit zbývající výrokové spojky, což jsou a . Musíme tedy ukázat, že formule obsahující spojky  a  lze přepsat na ekvivalentní formule, které obsahují jen spojky . To je však snadné pomocí ekvivalencí (23), (24). Připomeňme si je:

	náhrada za a
	náhrada za dvě

Tedy podle ekvivalence (23) přepíšeme libovolnou implikaci na ekvivalentní formuli obsahující  a , což jsou prvky z množiny , jejíž funkční úplnost právě zkoumáme. Podobně pomocí ekvivalence (24) přepíšeme libovolnou ekvivalenci na konjunkci dvou implikací a obě implikace pomocí (23) opět na ekvivalentní formule obsahující jen spojky a , tedy:

                  

Podařilo se nám ukázat, že množina je skutečně funkčně úplná.

2) Množina je funkčně úplná.

Musíme ukázat, že formule obsahující spojky , a lze přepsat na ekvivalentní formule, které obsahují jen spojky  a . To je snadné pomocí následujících ekvivalencí:

	náhrada spojek  a
	spojkami a
	náhrada za dvě

Ekvivalenci můžeme upravit také následujícím způsobem:

Množina je tedy funkčně úplná.

3) Protože spojku  lze vyjádřit pomocí spojek a naopak spojku  pomocí spojek  De Morganovými zákony, je funkčně úplná i množina , resp. množina (množina nikoliv).

Existují ještě další úplné systémy logických spojek, ale ty pro nás nejsou tak zajímavé. Nejdůležitějším systémem pro nás bude množina . Jak bylo slíbeno v předchozím odstavci, teď již vidíme, proč se budeme věnovat jen jedné dvojici duálních spojek a to dvojici konjunkce-disjunkce.