15. Дедукция теоремасы. Дедукция теоремасының салдарлары.

А) Дедукция теоремасын дәлелдеуге қолданылатын аксиомалар.

Дедукция теоремасы. Еген Г предикаттар есептеуінің формулалар жиыны, ал φ және ψ предикаттар есептеуінің формулалары болса, Г U {φ} ├ <=>Г├φ→ψ.

Жеке жағдайы: φ├ ψ <=> ├ φ→ψ. (Айтылуы: Еген ψ формуласы φ формуласының салдары болса, онда φ→ψ формуіласы теорема болады.

Дәлелдеуі. (=>): Дәлелдеуді қорытудың ұзындығы n бойынша индукциямен жүргізейік. Пара-парлықтың сол жағы орындалып, Г U {φ} ├ ψ болсын.

Еген қорыту бір ғана формуладан тұрса, яғни n=1, онда үш жағдай болуы мүмкін:

ψ=φ. Онда ├ φ→φ болғандықтан ├ φ→ψ. Яғни Г ├ φ→ψ.

ψ€Г. Онда Г├ φ. Бұдан ├ ψ→(φ→ψ) аксиомасына және Г├ ψ қорытуына МР ережесін қолдансақ, Г├ φ→ψ болады.

Ψ – предикаттар есептеуінің аксиомасы болсын. Онда Г├ ψ және ├ ψ→ (φ→ψ) қорытуларын МР ережесін қолдану нәтижесінде Г ├ φ→ψ болады.

n>1 жағдайы: ψ формуласы өзінің алдынлағы формулалардан МР ережесі бойынша алынған жағдайды қарастырайық. Яғни θ формуласы табылып, ψ формуласы Г,φ├ θ және Г,φ├ θ→ψ қорытуларынан МР ережесінің нәтижесінде алынды деликү Индукция жоруы бойынша: Г,φ├ θ және бірінші аксиома нұсқасынан Г ├ φ→(θ→ψ). Онда предикаттар есептеуінің (φ→(θ→ψ))→((φ→θ)→(φ→ψ)) аксиомалар нұсқасына екі рет МР ережесін қолдану арқылы Г ├ φ→ψ қорытуын аламыз.

Енди ψ формуласы ∀vθ түрінде болып, ол θ формуласына жалпылау ережесін қолдану жолымен алынсын. Индукция жоруы бойынша Г, φ├ θ. Еки жағдай болуы мүмкін.

Г, φ├ θ қорытуында φ кездеспесе, Г├ θ болады. Бұл қорытуға жалпылау ережесін қолдансақ, Г├ ∀vθ. Ал Г1 аксиомалар нұсқасынан Г├ ∀vθ→(φ→∀vθ). МР ережесин қолданудан кейін Г├ φ→∀vθ немесе Г├ φ→ψ.

Φ формуласы Г, φ├ θ қорытуында φ гипотеза ретінде кездессін. ∑1 осы қорытудың φ формуласынан өзге мүшелерінің жиына болсын. ∑1, φ├ ψ. Индукция жоруы бойынша ∑1├ ∀ ν(φ→ψ). Ал Г1 аксиомалар нұсқасынан ∑1├ ∀ ν(φ→ψ)→(φ→∀νψ). Енді МР ережесін қолдансақ, ∑1 - φ→∀νψ немесе ∑1 - φ→ψ.

Егер ψ формуласы өзінің алдындағы қандай да бір формуладан ІІІ-ші ереже арқылы алынса, бұл жағдай алдыңғы жағдайға ұқсас дәлелденеді.

Кері дәлелдеу. Бұл импликацияның дәлелдеуі пікірлер есептеуінде келтірілген дәлелдеуді толығымен қайталайды. Теорема дәлелденді.

В) Дедукция теоремасының салдарлары.

Салдар 6.2. Егер у- айнымалысы θ-да бос кездеспесе, онда

∀у(φ(у)→θ)→(∃уφ(у)→θ),

∀х(φ→θ(х))→(φ→∀хθ(х)).

Дәлелдеуі.

∀у(φ(у)→θ)├ (∃уφ(у)→θ) қорытуын дәлелдейік. Осы қорытуды құрайық.

φ1: ∀у(φ(у)→θ)- гипотеза,

φ2: ∀у(φ(у)→θ)→ (φ(у)→θ) – Г11 аксиомалар нұсқасынан, өйткені у – у үшін бос, ал θ-да у бос кездеспейді,

φ3: φ(у)→θ – МР қорыту ережесін 1 мен 2-ге қолдану арқылы,

φ4: (φ(у)→θ)→(∃уφ(у)→θ) – Г12 аксиомалар нұсқасынан аламыз,

φ5: ∃уφ(у)→θ – МР қорыту ережесін 3 пен 2-ге қолданамыз.

Сонымен ∀у(φ(у)→θ)├ ∃уφ(у)→θ . Оған дедукция теоремасын бір рет қолдансақ, онда ∀у(φ(у)→θ)├ (∃уφ(у)→θ).

Бұл қорыту да алдынғыға ұқсас құрылады.

Математикалық практикада төмендегі қорыту ережелері аты аталмай-ақ қолданыла береді. Оларды табиғи қорытудың құрылымдық ережелері деп атаймыз: Олар

Тепе-теңдік заңы: φ├ φ;

Қосу ережесі: Г├ φ болса, онда Г,ψ├ φ;

Алмастыру ережесі: ;

Қысқарту ережесі: ;

Қима ережесі: ;