Matematické Fórum

Prochycz

Dobrý den,

po dlouhé době bych potřeboval opět radu, se kterou si vůbec nejsem schopen poradit. Věřím, že to je trivialita, ale pořádně tomu nerozumím. Mám dva příklady:
$\{\leftarrow,\neg\}$
$\{\wedge,\not\leftrightarrow,1\}$

A mám určit, jestli se jedná o funkční úplnost. Potřeboval bych jakkoliv nakopnout, protože sem se z místa vůbec nepohnul, jelikož nevím přesně, co s tím dělat.

Nejsem si jistý, jestli se jedná o správný termín "Funkční úplnost", jedná se o příklad z německý prezentace, kde je to popsaný jako "funktional vollständig", popř. pravděpodobně ještě "Vollständigkeit" . Bohužel jsem se snažil k tomu najít České materiály, ale bohužel bez úspěchu. Popravdě ani ty značky mi pořádně nic neříkají.

Předem děkuji za jakoukoliv radu

Jj · 18. 01. 2016 11:16

↑ Prochycz:

Dobrý den.

Řekl bych, že termín může být "úplný soubor logických funkcí".

lucash · 18. 01. 2016 11:17

↑ Prochycz:
//forum.matweb.cz/upload3/img/2016-01/12203_v%25C3%25BDroky.JPG
nevím jak víc ti pomoci

Prochycz · 18. 01. 2016 11:24

Děkuji za rychlou odpověď

Takže pokud tomu správně rozumím, tak musím dokázat, že pomocí $\{\leftarrow,\neg\}$ , to znamená pomocí $x+\neg{y}$ a negace jsem schopen vytvořit jakoukoliv logickou funkci, pokud to nedokážu, tak to pravděpodobně není úplný soubor logických funkcí?

lucash · 18. 01. 2016 11:43

↑ Prochycz:
Upřímě netuším. S takovýmdle příkladem jsem se nesetkal, ale předpokládám že by to mohlo být něco takového..:)

Wotton · 18. 01. 2016 11:51

↑ Prochycz:

Abych ti to trochu učesal.

Máme 16 dvojargumentových funkcí (spojek) a 4 jednoargumentové. Některé stačí k nadefinování všech ostatních funkcí. Nejznámnější základní sada je Negace, Konjinkce, Disjunkce, Implikace (z leva do prava) a ekvivalence.
Není ale takový problém dokázat, že k nadefinování těchto (a tím vlastně všech) stačí Negace spolu s Disjunkci nebo Konjukncí (ve skutečnosti stačí ještě míň, ale to sem teď nebudu tahat).

Takže tobě vlastně stačí ukázat nadefinovatelnost Negace a Disjunkce/Konjunkce.

Pro zjednodušení dodávám, že obě varianty v zadání k jejich nadefinování stačí.

... pokud to nedokážu, tak to pravděpodobně není úplný soubor logických funkcí?

tohle mě pobavilo To je odvážné tvrzení:-D

Wotton · 18. 01. 2016 12:00

↑ Prochycz:

a ještě odkaz na teorii
Odkaz

Prochycz · 18. 01. 2016 17:42

Wotton napsal(a):
tohle mě pobavilo To je odvážné tvrzení:-D

Tak samozřejmě já nejsem taková kapacita, aby to byla pravda, ale např. když bych to dělal v testu, tak to musím brát tak, že sem to udělal dobře.

Jinak děkuji za nakopnutí, večer to prozkoumám.

Wotton · 18. 01. 2016 19:59

↑ Prochycz:
neber to zle. Tím nikaj nezpochybňuju tvé schopnosti. Já jen, že v matematice, a ještě míň v logice je tohle nemyslyelná věta. Z toho, že jsem neco nedokázal, ještě nemůžu usoudit, že to nejde. A to nezávysle na tom, jak jsem v daném oboru dobrý.

Abych mohl říct, že to nejde, tak musím dokázat nemožnost toho že do jde.

Prochycz · 20. 01. 2016 19:23

Tak říkal jsem, že se na to podívám v pondělí, bohužel to vyšlo až dnes.

Tak se tedy zeptám, jestli jsem postup udělal správně:

Př. 1:
$\{\leftarrow,\neg\}$ , $x+\neg{y}$

Takže negaci tu samozřejmě dokazovat nemusím, takže už stačí jenom Disjunkce/Konjunkce. Přijde mi to v tomto případě až příliš jednoduché, že si myslím, že ten postup je špatně.

Disjunkce: Využiji negace a zneguji y -> $(x+\neg{\neg{y}})=x+y$
Konjunkce: Opět použiji negaci zneguji x a pak celý výraz: $\neg({\neg{x}+\neg{y})}=x\cdot y$

Popravdě říkám si, jestli můžu tu negaci používat na jednotlivé členy, nebo je nutné to použí na celý výraz $x+\neg{y}$ , tzn. jestli není možné použít tu operaci negace pouze následovně $\neg{(x+\neg{y})}$

Wotton · 21. 01. 2016 09:40

↑ Prochycz:
já neříkal že to není jednoduché. Samozřejmě, že to je dobře.

A to co máš už odvozené, můžeš použít pro libovolné formule (případně formuli, jde-li o jednoargumentovou funkci), tedy jak pro celou, tak pro jednotlivé podformule, či atomy.

A stačilo ukázat jen disjunkci. Konjunkce už pak nutná není (jak jsem psal, stačí kterákoli z nich).

Prochycz

Já si říkal, že to bude asi jednoduchý, ale nečekal jsem, že až takhle v tomto případě. Věřím, že existují daleko složitější příklady na dokázání, jestli se jedná o úplný soubor log. funkcí či nikoliv.

Jen teda doplním, že ten druhý příklad bude následovně:
Př. 2: $\{\wedge,\not\leftrightarrow,1\}$ ´
Nonekvivalence: $\bar{A}\cdot B + A\cdot \bar{B}$ , když dosadím za $A=1\space$ nebo $B=1$ automaticky si tím vytvořím negaci druhého vstupu, čímž je dokázáno, že jde o ÚSLF.

Děkuji tedy za dokopání k výsledku. Tímto to považuij asi za vyřešené. :-)

Matematické Fórum

#1 18. 01. 2016 10:59 — Editoval Prochycz (20. 01. 2016 19:26)

Úplný soubor logických funkcí

#2 18. 01. 2016 11:16

Re: Úplný soubor logických funkcí

#3 18. 01. 2016 11:17

Re: Úplný soubor logických funkcí

#4 18. 01. 2016 11:24

Re: Úplný soubor logických funkcí

#5 18. 01. 2016 11:43

Re: Úplný soubor logických funkcí

#6 18. 01. 2016 11:51

Re: Úplný soubor logických funkcí

#7 18. 01. 2016 12:00

Re: Úplný soubor logických funkcí

#8 18. 01. 2016 17:42

Re: Úplný soubor logických funkcí

Wotton napsal(a):

#9 18. 01. 2016 19:59

Re: Úplný soubor logických funkcí

#10 20. 01. 2016 19:23

Re: Úplný soubor logických funkcí

#11 21. 01. 2016 09:40

Re: Úplný soubor logických funkcí

#12 21. 01. 2016 13:26 — Editoval Prochycz (21. 01. 2016 13:28)

Re: Úplný soubor logických funkcí

Zápatí