Postov izrek o funkcijski polnosti : delo diplomskega seminarja

Tekavc, Lucija (author), Kudryavtseva, Ganna (mentor)

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.

• Language: Slovenian
• Keywords: izjavni izraz, logična funkcija, polni nabori, razredi logičnih funkcij, funkcijska polnost
• Work type: Final seminar paper
• Typology: 2.11 - Undergraduate Thesis
• Organization: FMF - Faculty of Mathematics and Physics
• Year: 2025
• PID: 20.500.12556/RUL-172992
• UDC: 510.6
• COBISS.SI-ID: 248767747
• Publication date in RUL: 12.09.2025

Secondary language

• Language: English
• Title: Post's theorem on functional completeness

Abstract

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.

• Keywords: propositional formula, truth function, complete sets, classes of truth functions, functional completeness