Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
Математикалық логикада, импликациялық пропозициялық есептеу - классикалық пропозициялық есептеудің тек бір байланыстырушыны қолданатын нұсқасы, оны импликация немесе шартты деп атайды. Формулаларда бұл екілік операция "имплицидтер", "егер , онда", "→", "", және т.б.
In mathematical logic, the implicational propositional calculus is a version of classical propositional calculus that uses only one connective, called implication or conditional. In formulas, this binary operation is indicated by "implies", "if , then ", "→", "", etc
Толықтығы
Импликациялық пропозициялық есептеу классикалық пропозициялық логиканың әдеттегі екі бағаланған семантикасына қатысты семантикалық жағынан толық. Яғни, егер Γ - импликациялық формулалардың жиынтығы болса, ал A - импликациялық формула, онда .
The implicational propositional calculus is semantically complete with respect to the usual two valued semantics of classical propositional logic. That is, if Γ is a set of implicational formulas, and A is an implicational formula entailed by Γ, then .
Аксиома схемасын қосу
Жоғарыда аталғандарға тағы бір аксиомалық схема қосылса не болады? Екі жағдай бар: 1) ол таутология; немесе 2) ол таутология емес. Егер бұл таутология болса, онда теоремалардың жиынтығы бұрынғыдай таутологиялардың жиынтығы болып қалады. Алайда, кейбір жағдайларда теоремалардың айтарлықтай қысқа дәлелдемелерін табуға болады. Дегенмен, теоремаларды дәлелдеудің ең аз ұзындығы шексіз болып қала береді, яғни кез келген n табиғи сан үшін әлі де n немесе одан аз қадамда дәлелденбейтін теоремалар болады. Егер жаңа аксиомалық схема таутология болмаса, онда әрбір формула теоремаға айналады (бұл жағдайда теорема ұғымын пайдасыз етеді). Сонымен қатар, әрбір формуланың дәлелденуінің ең аз ұзындығының жоғарғы шегі бар, өйткені әрбір формуланы дәлелдеудің ортақ әдісі бар. Мысалы, жаңа аксиомалар схемасы ((B→C)→C)→B. Содан кейін ((A→(A→A))→(A→A))→A инстанция (жаңа аксиомалардың бірі) және тавтология емес. Бірақ [((A→(A→A))→(A→A))→A]→A - таутология және осылайша ескі аксиомаларға байланысты теорема (жоғарыдағы толық нәтижеді пайдаланып). Modus ponens-ті қолданғанда, біз A кеңейтілген жүйенің теоремасы екенін білеміз. Кез келген формуланы дәлелдеу үшін A-ны A-ның дәлелденуі барысында қажетті формуламен ауыстыру керек. Бұл дәлелдеу А-ның дәлелдеуіне тең қадамдар санымен жасалады.
What would happen if another axiom schema were added to those listed above? There are two cases: (1) it is a tautology; or (2) it is not a tautology. If it is a tautology, then the set of theorems remains the set of tautologies as before. However, in some cases it may be possible to find significantly shorter proofs for theorems. Nevertheless, the minimum length of proofs of theorems will remain unbounded, that is, for any natural number n there will still be theorems that cannot be proved in n or fewer steps. If the new axiom schema is not a tautology, then every formula becomes a theorem (which makes the concept of a theorem useless in this case). What is more, there is then an upper bound on the minimum length of a proof of every formula, because there is a common method for proving every formula. For example, suppose the new axiom schema were ((B→C)→C)→B. Then ((A→(A→A))→(A→A))→A is an instance (one of the new axioms) and also not a tautology. But [((A→(A→A))→(A→A))→A]→A is a tautology and thus a theorem due to the old axioms (using the completeness result above). Applying modus ponens, we get that A is a theorem of the extended system. Then all one has to do to prove any formula is to replace A by the desired formula throughout the proof of A. This proof will have the same number of steps as the proof of A.