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
! 04. 11. 2016 (Jel.) Čtete, prosím, před vložení dotazu, děkuji!
17. 01. 2016 (Jel.) Rok 2016 s novými a novějšími krystaly od kolegy Pavla!
17. 01. 2016 (Jel.) Nabídka knih z oborů matematiky, fyziky, chemie
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: 9
Š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: 843
Škola: PřF MUNI
Pozice: student
Reputace:   32 
 

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: 9
Š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
Místo: Břeclav, Brno
Příspěvky: 4455
Škola: PřF MUNI, konzervatoř Brno
Pozice: student
Reputace:   216 
 

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