Кукон давлат педагогика институти

3.Маруза: МУЛОХАЗАЛАР АЛГЕБРАСИДАГИ ТАВТОЛОГИЯЛАР.

Режа.

1. 
   Тавтологияларнинг мохияти.
   
2. 
   Асосий тавтологиялар.
   
3. 
   Логик амаллар хоссаларини белгилаб берувчи тавтологиялар.
   
4. 
   Тавтология хосил ыилишнинг асосий ыоидалари.
   

Таянч иборалари.

Рост мулохаза хосил ыилиш,тавтология, ыонунлар, ыоидалар, конoюнкция ва дизoюнкция хоссалари. Импликация ва эквивалентлик хоссалари, бир логик амални бошыаси орыали ифодалаш, хулосалаш ыоидаси, mоdus роnens, щрнига ыщйиш ыоидаси.

Юыоридаги мавзуда аниыланган айнан рост формулалар ёки тавтологиялар таркибига кирувчи мулохазаларнинг мазмунидан ва логик ыийматидан ыатoий назар рост мулохазалар ыуриш ыонун ыоидаларини кщрсатиб беради.Куйда биз мулохазалар алгебрасининг асосий тавталогиялари билан танишамиз.

3.1 Асосий тавтологиялар.

а) P P б)  (P P) в)   PP г) PP

д) (PQ) ( Q P) е) ((PQ) (QR)) (PR)

ж) (PQ) ( P Q) з) P (QP) и)  P(PQ к) (P(PQ)) Q л) ((PQ Q)  P м) (P(QR)) (Q(PR))

н) (P(QR)) ((PQ) R)

о) ((PR) (QR))((PQ)R)

п) ((  PQ) ( P Q))P , ( P(Q  Q)) P

Куйида келтириладиган тавтологиялар логик амалларнинг хоссаларини хам курсатиб беради.

3.2 Конoюнкция ва дизoюнкция хоссалари .

а) (PP) P , (PP) P б) (PQ) P , P(PQ)

в) (PQ) (QP) , (PQ) (QP)

г) (P(QR)) ((PQ)R) , (P(QR)) ((PQ)R)

д) P(QR)) ((PQ) (PR)) , P(QR)) ((PQ) (PR))

е) (P(PQ)) P , (P(PQ)) P

ж)  (PQ)(  P Q) ,  (PQ)(  P Q)

3.3 Импликация ва эквивалентлик хоссалари .

а) (P(QR))((PQ)(PR))

б) P(Q(PQ))

в) (PR) ((QR) ((PQ)R))

г) (PQ) ((P Q)R))

д) ( Q(PQ))  P

е) ( P(PQ))Q

ж) (PQ)((PR)(QR))

з) (PQ) (PR)(QR))

и) (PQ) ((QR) PR))

к) (PQ)  (QP)

л) ( Q P) (( QP)Q))

м) ((PQ) (RQ)) ((PR)Q)

н) ((PQ) (PR)) (P(QR))

о) PP

п) (PQ) (QP)

р) ((PQ) (QR)) (PR)

3.4 Бир логик амалларни бошка логик амаллар оркали ифодалаш.

а)(PQ)(  PQ)

б) (PQ) (P Q)

в) (PQ)( PQ)

г) (PQ)(P Q)

д) (PQ)( P Q)

е) (PQ)(  PQ)

ж) (PQ)((PQ)(QP))
Тавтология хосил килишнинг асосий коидалари.
Куйида биз иккита коидани келтирамиз. Бу коидалар мавжуд булган тавтологиялардан янги тавтологиялар хосил килиш усулларини курсатиб беради.

Теорема (хулосалаш коидаси): Агар F ва FH куринишдаги формулалар тавтологиялар булса, у холда H формула хам тавтологиядир. F , FHH .

Хулосалаш коидаси бошкача килиб, ажратиш коидаси ёки Модус поненс (modus ponens) дейилади.

Айтайлик, F формулада Х пропорционал узгарувчи катнашган булсин (бундан бошка узгарувчилар катнашиши мумкин) ва ихтиёрий H ихтиёрий формула булсин. F формулада каерда Х узгарувчи келса, урнига H формулани куйиб чиксак, натижада янги формула хосил булади. Хосил булган формулани SF куринишда белгилаймиз. Уни F формулада Х узгарувчи урнига Н формулани куйишдан хосил булган формула деймиз.

Масалан: Х урнига Н=ZT формулани куйсак,

F=(XY) ( XY) SF=((ZT) Y) ( (ZT)Y)

Агар F формулада Х ва Y узгарувчилар катнашган булиб, бу узгарувчилар урнига мос равишда H ва G формулаларни куйсак, натижада хосил булган формула SF куринишда булади.

Худди шу каби, F формулада бир нечта узгарувчилар урнига киритилган алмаштиришларни хам белгилашимиз мумкин.

Теорема ( урнига куйиш коидаси): Таркибида Х узгарувчи катнашган F формула тавтология булса, у холда F формуладаги Х урнига ихтиёрий H формулани куйишдан хосил булган формула хам ёна тавтология булади. F SF.

Урнига куйиш коидаси шуни курсатиб берадики, юкоридаги 3.1-3.4 даги формулалар нафакат алохида олинган тавталогиялар булиб колмай балки, тавталогиялар хосил килишнинг умумий схемаларини хам курсатиб беради. Яъни бу формуладаги иштирок этган хар бир пропорционал узгарувчини мулохазалар алгебрасидаги ихтиёрий формула деб караш мумкин.

Юкорида курилган икки коида бу тавтология хосил килишнинг асосий коидалари хисобланади. Тавтология хосил килишнинг бундай бошка коидалари хам мавжуд ва улар кейинчалик куриб чикилади.