14.A импликация a формуласының теорема болатыны туралы лемма.

а) Қорытудың қарапайым қасиеттері.

в) Лемманы дәлелдеуге қолданылатын аксиомалар..

Лемма. Пікірлер есептеуінің кез келген А формуласы үшін А ->А формуласы теорема болады, яғни |-A->A.

Дәлелдеуі. Анықтама бойынша, А ->А формуласының қорытуы болатын формулалар тізбегі табылуы керек.Енді сол қорытуды келтірейік.

(А->(A->A))->((A->((A->A)->A))->(A->A)) – Г2 нұсқасы бойынша аксиома.

(А->(A->A) –Г1 нұсқасы бойынша аксиома

(А->((A->A)->A))->(A->A) – 2 ші және 1ші формулалардың МР ережесі бойынша тікелей салдары.

(А->((A->A)->A)- Г1 нұсқасы бойынша аксиома.

А ->А – 4 ші және 3ші формулаларының МР ережесі бойынша тікелей салдары.

Сонымен|- А ->А .

Қорытудың қарапайым қасиеттері

Әрбір аксиома теорема болады. Яғни ϕ аксиома болса, онда |-ϕ.

Әрбір теорема кез келген формулалар жиынының салдары болады.

Егер ϕ € Г, онд а Г|-ϕ. Мысалы,кез келген ϕ формуласы үшін ϕ|-ϕ.

Егер Г|-ϕ және ГĆΣ болса, онда Σ|-ϕ

Егер Г|-ϕ болса,онда Г жиынының ақырлы ішкі жиыны Г₁(Г₁ĆГ) табылып, ол үшін Г|-ϕ болады.Бұл қасиет қорытудың финиттілігі деп аталады.

Г,Σ формулалар жиындары берілсін. Егер Г|-ϕ және Г жиынының әрбір θ формуласы үшін Σ|-Ө болса,онда Σ|-ϕ. Бұл қасиет қорытудың транзитивтілігі деп аталады.

Дәлелдеулері. Жоғарыдағы қасиеттердің алғашқы төртеуі қорыту анықтамасынан тікелей шығады.Сонда да толықтық үшін олардың дәлелдерін келтіреміз.

1-ші қасиет Егер ϕ аксиома болса, онда оның қорытуы тек соның өзінен ғана тұрады.

2-ші қасиет. Егер ϕ теорема болса,онда ол бос жиыннан қорытылады.Бос жиын кез келген жиынның ішкі жиыны болғандықтан,онда ол ϕ формуласы барлық жиыннан қорытылады.

3-қасиет. Егер ϕ€Г болса, онда бұл формуланың Г жиынындағы қорытуы тек осы формуладан ғана тұрады.

4-ші қасиет. Егер Г|-ϕ және ГĆΣ болса онда бұл формуланың қамтушы жиындағы қорытуы оның Г жиынындағы қорытуымен бірдей.

5-ші қасиет. Φ₁ ϕ₂ ….ϕ_n формулалар тізбегі Г жиынындағы ϕ формуласының қорытуы болсын. Бұл тізбекте Г жиынының элементтері кездесуі мүмкін. Олардан тұратын жиынды Г арқылы белгілейк. Онда Г ақырлы жиын шарттағы Г жиынын Г₁ жиынымен ауыстыруға болады. Ендеше Г₁|-ϕ.

6-ші қасиет. Φ₁ ϕ₂ ….ϕ_n формулалар тізбегі Г жиынындағы ϕ формуласының қорытуы болсын. Шарт бойынша бұл тізбектегі әр формуланың Σ жиынында қорытуы болады. Ол қорыту формулалардың ақырлы тізбегі болады. Егер ол формулаларды оларға сәйкес Σ жиынындағы қортуларымен ауыстырайық, онда ϕ формуласының Σ жиынындағы қорытуын аламыз. Яғни Σ|-ϕ

в) Лемманы дәлелдеуге арналған аксиомалар.Дедукция теоремасы. Дедукция теоремасының салдары.

Г1. ϕ->(Ψ->ϕ)

Г2.(ϕ->Ψ)->((ϕ->(Ψ->θ))->(ϕ->θ)),

Г3.(ϕɅΨ)->ϕ

Г4.(ϕɅΨ)->Ψ

Г5.ϕ->(ϕѵΨ)

Г6.Ψ->(ϕѵϕ)

Г7. (ϕ->Ψ)->((ϕ->θ)->(ϕ->(ϕɅθ)))

Г8.(ϕ->θ)->((Ψ->θ)->((ϕѴΨ)->θ)),

Г9.(ϕ->˥Ψ)->(Ψ->˥ϕ)

Г10.˥˥ϕ->ϕ

Анықтама. Қандай да бір аксиома нұсқасында кездесетін ϕΨ және θ символдарын кез келген пікірлер логикасының формулаларымен бір мезгілде ауыстыру арқылы пайда болған формуланы пікірлер есептеуінің аксиомасы деп атаймыз.

Мысалдар.

Г1 аксиомалар нұсқасындағы ϕ және Ψ символдарын, сәйкес ˥А және В пікірлер логикасының формулаларымен ауыстырғаннан пайда болған ˥А->(B->˥A) формуласы пікірлер есептеуінің аксиомасы болады.

Г8. Аксиомалар нұсқасындағы ϕ,Ψ және θ символдарын пікірлер логикасының сәйкес В,˥А және А->˥B формулаларымен ауыстырғаннан пайда болған

(В->(A->˥B))->((˥A->(A->˥B))->((B˅˥A)->(A->˥B)))

Формуласы пікірлер есептеуінің аксиомасы болады.

Бұдан кейін де ауыстыру арқылы алынған басқа да аксиомалар мысалдарымен танысамыз.

Пікірлер есептеуінде бір қорыту ережесі бар. Ол ереже модус поненс деп аталады.

МР:

Теорема (Дедукция теоремасы). Г формулалар жиыны берілсін. Онда кандай да бір ϕ және Ψ формулалары үшін Г,ϕ|-Ψ болады сонда тек сонда ғана , егер Г|-ϕ->Ψ болса.Мысалы Г бос жиын болған жағдайда, ϕ|-Ψ<->|-ϕ->Ψ

Дәлелдеуі. Айталық ϕ₁ ϕ₂ ϕ₃ формулалар тізбегі Г жиынындағы ϕ формуласы ның қорытуы болсын.Онда анықтама бойынша ϕ_n=Ψ болады. Теореманы дәлелдеуді қорытудағы формулалардың саны бойынша индукцияны пайдаланып жүргізейік.

n=1 болғанда ϕ₁=Ψ .Біз Г|-ϕ->ϕ₁ қорытуының орындалатынын көрсетуіміз керек. Мұндағы ϕ₁ формуласы үшін төмендегі жағдайлардың бірі орындалады.

а)ϕ₁=аксиома

в) ϕ₁€ Гᴗ{ϕ}. Онда ϕ₁€ Г немесе ϕ₁=ϕ жағдайларының бірі болады

Салдар. а) ϕ->Ψ,Ψ->θ|-ϕ->θ,

b)ϕ->(Ψ->θ),Ψ|-ϕ->θ

Дәлелдеуі. (а): Алдымен ϕ->Ψ,Ψ->θ,ϕ|-θ(*)

Қорытуының орындалатынын көрсетеміз.

1.ϕ->Ψ – гипотеза

2.Ψ->θ- гипотеза

3.ϕ- гипотеза

4.Ψ- 3ші 1ші формулалардың тікелей салдары.

5.θ- 4-ши және 2-ші формулалардың тікелей салдары.

Сонымен (*) қорытуы ϕ->Ψ,Ψ->θ дәлелденді,енді (*)-ға дедукция теоремасын қолдансақ, ϕ->Ψ,Ψ->θ|-ϕ->θ болады.Салдардың бұл пункті дәлелденді.

(b): Бұл жолы алдымен ϕ->(Ψ->θ),Ψ|-ϕ->θ болатынын көрсетіп алып,артынан дедукция теоремасын қолданамыз.

Сонымен ϕ->(Ψ->θ),Ψ|-ϕ->θ(**) дәлелдеп алайық.

1.ϕ->(Ψ->θ)- гипотеза

2. Ψ-гипотеза

3.ϕ-гипотеза

4.Ψ->θ- 3 ші және 1ші формулалардың тікелей салдары

5.θ-2 ші 4 ші формулалардың тікелей салдары

Сонымен (**) қорытуы дәлелденді, енді (**) –ға дедукция теоремасын қолдансақ.

ϕ->(Ψ->θ),Ψ|-ϕ->θ болады.Салдардың бұл пунктіде дәлелденді.