Matematické Fórum

Slazer · 04. 11. 2016 08:03 — Editoval Slazer (04. 11. 2016 09:13)

Mám zadefinovať sémantiku spojky $\square$ aby platilo, že $L(\Leftrightarrow,\square)$ je úplný (plnohodnotný), ale $L(\oplus,\square)$ nie je. Predpokladať môžem len plnohodnotnosť $L(NOT,\wedge)$ , $L(NOT,\vee)$ a $L(NOT,\Rightarrow)$ .

Problém je, že neviem nájsť binárnu logickú spojku, ktorá spolu s $\Leftrightarrow$ tvorí úplný systém. Píšem moje doterajšie úvahy.

Ak by $\square$ bolo napríklad priamo $\oplus$ , tak zo spojok $\Leftrightarrow$ a $\oplus$ dokážem vytvoriť $\neg$ pomocou kontradikcie cez $\oplus$ . Systém $L(\oplus,\oplus)$ stále nebude plnohodnotný, ale $L(\Leftrightarrow,\oplus$ (teda $L(\Leftrightarrow,\oplus,\neg)$ by zrejme mohol, ale neviem nájsť formulu vyjadrujúcu $\wedge$ alebo $\vee$ alebo $\Rightarrow$ .

Ak by $\square$ nebolo $\oplus$ , tak mi zostáva posúdiť $2^4-1=15$ ďaľších spojok. Dve Shefferovské môžem vyradiť hneď, pretože $L(\oplus,\square)$ by bol plnohodnotný. Tiež môžeme vylúčiť $\neg$ a $\Rightarrow$ , lebo $L(\Leftrightarrow,\square)$ nebude úplný. Momentálne uvažujem nad T (tautológiou) a K (kontradikciou). Pomocou $\oplus$ a T viem vytvoriť $\neg\varphi$ a preto aj $\Leftrightarrow$ , čím by sa však $L(\oplus,T)$ stal úplným (za podmienky, že $L(\Leftrightarrow,T)$ je úplný), čo je spor. Pomocou K viem vytvoriť $\neg$ v $L(\Leftrightarrow,K)$ a tu som zatiaľ skončil.

V systéme $L(\square)$ ani $L(\oplus,\square)$ nesmie byť možné vytvoriť $\neg\varphi$ . Ak by to možné bolo, tak keďže $\neg(\varphi \oplus\psi )$ je ekvivalentné s $\varphi \Leftrightarrow \psi$ a $L(\Leftrightarrow,\square)$ (teda vlastne $L(\Leftrightarrow,\square,\neg)$ ) je úplný, tak aj $L(\oplus,\square,...)$ by bol úplný, čo je spor.

Neúplné systémy:
$L(\oplus,\neg)$
$L(\oplus,T)$
$L(\Leftrightarrow,\neg)$ (neviem vyjadriť $\wedge$ )
$L(\Leftrightarrow,\Rightarrow)$

Úplné systémy:
$L(\oplus,\Rightarrow)$
$L(\oplus,T,\wedge)$
$L(\oplus,T,\vee)$
V úplnom systéme nemusí byť negácia (ako spojka).

Uvažujem nad úplnosťou:
( $\square=\ldots$ )
$L(\Leftrightarrow,\oplus)$
$L(\Leftrightarrow,K)$
$L(\Leftrightarrow,\wedge)$
$L(\Leftrightarrow,\vee)$

Sem som sa zatiaľ dostal. Ďakujem za pomoc.

Sherlock

Dělám ten samej úkol ;)

Pokud je $L(\Leftrightarrow,\neg)$ neúplný, je neúplný i $L(\Leftrightarrow,\oplus)$ (negaci odpovídá $A\Leftrightarrow (A\oplus A)$ )

Podle mě sis správně všimnul, že $L(\Leftrightarrow,\Rightarrow)$ není úplný, ale $L(\oplus,\Rightarrow)$ úplný je - zkus to nějak "obrátit", aby ti to vyšlo naopak.

V úplnom systéme nemusí byť negácia (ako spojka).

Nemusí tam být přímo, musí ale být vyjádřitelná pomocí spojek, co v tom systému máš. :)

Slazer · 04. 11. 2016 15:52 — Editoval Slazer (04. 11. 2016 15:55)

Hmm, zrejme som na to prišiel. Ešte rozmýšľam, ako dokázať, že $L(\oplus,\neg\Rightarrow)$ nie je úplný systém. Nejak ma to vedie k dôkazu, že nie je úplný pretože v $L(\oplus,\neg\Rightarrow)$ nemožno odvodiť tautológiu.

Ak by mal byť $L(\oplus,\neg\Rightarrow)$ úplný, musí v ňom existovať formula pre negáciu. Predpokladám, že negáciu viem vytvoriť LEN ak viem vytvoriť tautológiu v systéme $L(\oplus,\neg\Rightarrow)$ , ale neviem to dokázať.

Viem, že sa to dá spraviť použiťím
a) $\oplus$ a $T$
b) $\neg\Rightarrow$ a $T$
ale ako dokázať, že bez tautológie nikdy nebude $\neg$ ?

byk7 · 07. 11. 2016 12:08

↑ Slazer: Ono to platí i naopak, přesněji "negaci umím vytvořit právě tehdy, když umím vytvořit tautologii". Důkaz je jednoduchý:

(i) $\exists(\neg A)\Rightarrow\exists T$ : pak $T\approx A\oplus(\neg A)$
(ii) $\exists T\Rightarrow\exists(\neg A)$ : pak $\neg A\approx A\oplus T\approx T\oplus A$ .

Hotovo. :)

Řekněme tedy, že máme v $L(\oplus,\neg\Rightarrow)$ formuli $\varphi$ odpovídající negaci a předpokládejme navíc, že $|\varphi|$ je minimální. Potom musí nastat jedna z možností $\varphi=\psi_1\oplus\psi_2,\varphi=\psi_1\neg\Rightarrow\psi_2,\varphi=\psi_2\neg\Rightarrow\psi_1$ , kde $|\psi_1|,|\psi_2|<|\varphi|$ , $\psi_1=K$ a $v$\psi_2$=v(A)$ . Pak se ale snadno ukáže, že ani jedna z možností negaci neodpovídá. Spor. V $L(\oplus,\neg\Rightarrow)$ negaci nemáme.