Matematické Fórum

Nevíte-li si rady s jakýmkoliv matematickým problémem, toto místo je pro vás jako dělané.

Nástěnka
22. 8. 2021 (L) Přecházíme zpět na doménu forum.matweb.cz!
04.11.2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
23.10.2013 (Jel.) Zkuste před zadáním dotazu použít některý z online-nástrojů, konzultovat použití můžete v sekci CAS.

Nejste přihlášen(a). Přihlásit

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

Slazer
Zelenáč
Místo: v izbe
Příspěvky: 10
Škola: ano
Pozice: vertikálna
Web
 

Úplné systémy logických spojok

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 $$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.

Offline

  • (téma jako nevyřešené označil(a) jelena)

#2 04. 11. 2016 11:44 — Editoval Sherlock (04. 11. 2016 11:54)

Sherlock
Příspěvky: 859
Škola: PřF MUNI
Pozice: student
Reputace:   33 
 

Re: Úplné systémy logických spojok

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áš. :)

Offline

 

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

Slazer
Zelenáč
Místo: v izbe
Příspěvky: 10
Škola: ano
Pozice: vertikálna
Web
 

Re: Úplné systémy logických spojok

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$?

Offline

 

#4 05. 11. 2016 09:55 Příspěvek uživatele Sherlock byl skryt uživatelem byk7.

#5 05. 11. 2016 10:23 Příspěvek uživatele jelena byl skryt uživatelem byk7.

#6 07. 11. 2016 12:08

byk7
InQuisitor
Příspěvky: 4691
Škola: PřF MUNI
Reputace:   220 
 

Re: Úplné systémy logických spojok

↑ 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.


Příspěvky psané červenou barvou jsou moderátorské, šedá je offtopic.

Offline

 

Zápatí

Powered by PunBB
© Copyright 2002–2005 Rickard Andersson