20.500.12556/RUL-172992 Postov izrek o funkcijski polnosti delo diplomskega seminarja Post's theorem on functional completeness Diplomsko delo je namenjeno Postovemu izreku o funkcijski polnosti, ki spada v področje matematične logike. Najprej predstavimo Postove razrede logičnih funkcij, in sicer zaprtost za vsako izmed logičnih konstant, štetje, monotonost ter sebi-dualnost. Nabor logičnih funkcij je poln, če lahko preko tega nabora izrazimo vsako logično funkcijo. Postov izrek, ki ga predstavimo in dokažemo v delu, pravi, da je nabor logičnih funkcij $X$ poln natanko tedaj, ko za vsakega od Postovih razredov obstaja element množice $X$, ki temu razredu ne pripada. The thesis is dedicated to Post's theorem on functional completeness, which falls within the field of mathematical logic. First, we present Post’s classes of logical functions, namely being closed under each of the logical constants, being a counting function, being monotone, and being self-dual. A set of logical functions is complete if every logical function can be expressed using that set. Post's theorem, which we present and prove in this thesis, states that a set $X$ of truth functions is functionally complete if and only if for each of Post's classes, there is a member of $X$ which does not belong to that class. izjavni izraz logična funkcija polni nabori razredi logičnih funkcij funkcijska polnost propositional formula truth function complete sets classes of truth functions functional completeness true false false Slovenski jezik Angleški jezik Delo diplomskega seminarja/zaključno seminarsko delo/naloga 2025-09-12 08:15:35 2025-09-12 08:15:35 2025-10-29 03:55:34 0000-00-00 00:00:00 2025 0 0 0000-00-00 NiDoloceno NiDoloceno NiDoloceno 0000-00-00 0000-00-00 0000-00-00 510.6 153213 248767747 19249.pdf 19249.pdf 1 855D61960486B3506C462083DCABDFD6 f335255e512fa92e33b2877d49aa86db29579fda2332eec0a2e4f2b09f37cde2 bb37cc6a-8f9f-11f0-9328-0050569b8976 https://repozitorij.uni-lj.si/Dokument.php?lang=slv&id=217144 Fakulteta za matematiko in fiziko 0 0 0