Математикадан логикалық теңдеулерді шешу. Логикалық теңдеулер жүйесін шешу әдістері Бульдік теңдеулер жүйесі

Айнымалыларды өзгерту арқылы логикалық теңдеулер жүйесін шешу

Айнымалыларды өзгерту әдісі, егер кейбір айнымалылар теңдеулерге тек нақты өрнек түрінде ғана қосылса, басқа ештеңе болмаса қолданылады. Сонда бұл өрнекті жаңа айнымалымен белгілеуге болады.

1-мысал

Төмендегі шарттардың барлығын қанағаттандыратын x1, x2, x3, x4, x5, x6, x7, x8 логикалық айнымалы мәндерінің қанша түрлі жиыны бар?

(x1 → x2) → (x3 → x4) = 1

(x3 → x4) → (x5 → x6) = 1

(x5 → x6) → (x7 → x8) = 1

Жауапта бұл теңдіктер жүйесі қанағаттандырылатын x1, x2, x3, x4, x5, x6, x7, x8 айнымалы мәндерінің барлық әртүрлі жиындарын тізбеудің қажеті жоқ. Жауап ретінде мұндай жиынтықтардың санын көрсету керек.

Шешімі:

(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.

Сонда жүйені бір теңдеу түрінде жазуға болады:

(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Әрбір операнд 1-ге бағаланғанда конъюнкция 1 (шын) болады. Яғни, салдарлардың әрқайсысы дұрыс болуы керек және бұл (1 → 0) қоспағанда, барлық мәндерге қатысты. Анау. y1, y2, y3, y4 айнымалыларының мәндерінің кестесінде бірлік нөлдің сол жағында болмауы керек:

Анау. y1-y4 5 жиынтық үшін шарттар орындалады.

Өйткені y1 = x1 → x2, онда y1 = 0 мәні бір x1, x2 жиынында қол жеткізіледі: (1, 0), ал y1 = 1 мәні үш x1, x2 жиынында қол жеткізіледі: (0,0) , ( 0,1), (1.1). Сол сияқты y2, y3, y4 үшін.

y1 айнымалысы үшін әрбір жиын (x1,x2) y2 айнымалысы үшін әрбір жиынмен (x3,x4) біріктірілгендіктен және т.б. айнымалы x жиындарының сандары көбейтіледі:

Жиындар санын қосайық: 1 + 3 + 9 + 27 + 81 = 121.

Жауап: 121

2-мысал

Төмендегі барлық шарттарды қанағаттандыратын x1, x2, ... x9, y1, y2, ... y9 логикалық айнымалы мәндерінің қанша әртүрлі жиыны бар?

(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)

(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)

(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)

Жауапқа керек емесберілген теңдік жүйесі орындалатын x1, x2, ... x9, y1, y2, ... y9 айнымалы мәндерінің барлық әртүрлі жиындарын тізіп көрсетіңіз. Жауап ретінде мұндай жиынтықтардың санын көрсету керек.

Шешімі:

Айнымалыларға өзгеріс енгізейік:

(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9

Жүйені бір теңдеу түрінде жазуға болады:

(¬z1 ≡ z2) ∧ (¬z2 ≡ z3) ∧ …..∧ (¬z8 ≡ z9)

Эквиваленттік екі операнд тең болған жағдайда ғана дұрыс болады. Бұл теңдеудің шешімдері екі жиын болады:

Өйткені zi = (xi ≡ yi), онда zi = 0 мәні екі жиынға (xi,yi): (0,1) және (1,0) сәйкес келеді, ал zi = 1 мәні екі жиынға (xi,yi) сәйкес келеді. ): (0 ,0) және (1,1).

Сонда бірінші z1, z2,…, z9 жиыны 2 9 жиынға (x1,y1), (x2,y2),..., (x9,y9) сәйкес келеді.

Дәл сол сан екінші z1, z2,…, z9 жиынына сәйкес келеді. Сонда барлығы 2 9 +2 9 = 1024 жиын бар.

Жауап: 1024

Рекурсияның көрнекі анықтамасы арқылы логикалық теңдеулер жүйесін шешу.

Бұл әдіс теңдеулер жүйесі жеткілікті қарапайым болса және айнымалыларды қосу кезінде жиындар санын көбейту реті айқын болса қолданылады.

3-мысал

Теңдеулер жүйесінің неше түрлі шешімі бар

¬x9 ∨ x10 = 1,

мұндағы x1, x2, ... x10 логикалық айнымалылар?

Жауапта берілген теңдіктер жүйесі орындалатын x1, x2, ... x10 мәндерінің барлық әртүрлі жиындарын санаудың қажеті жоқ. Жауап ретінде мұндай жиынтықтардың санын көрсету керек.

Шешімі:

Бірінші теңдеуді шешейік. Дизъюнкция 1-ге тең, егер оның операндтарының кем дегенде біреуі 1-ге тең болса. Яғни, шешімдер жиынтық болып табылады:

x1=0 үшін екі x2 мәні (0 және 1), ал x1=1 үшін тек бір x2 мәні (1) бар, сондықтан жиын (x1,x2) теңдеудің шешімі болады. Тек 3 жиынтық.

x3 айнымалысын қосып, екінші теңдеуді қарастырайық. Ол біріншіге ұқсас, яғни x2=0 үшін x3-тің екі мәні (0 және 1), ал x2=1 үшін x3-тің (1) бір ғана мәні бар, сондықтан жиын ( x2,x3) теңдеудің шешімі болып табылады. Барлығы 4 жиынтық бар.

Басқа айнымалыны қосқанда бір жиын қосылатынын көру оңай. Анау. (i+1) айнымалылардағы жиындар санының рекурсивті формуласы:

N i +1 = N i + 1. Сонда он айнымалы үшін 11 жиын аламыз.

Жауап: 11

Әртүрлі типтегі логикалық теңдеулер жүйесін шешу

4-мысал

x 1 , ..., x 4 , y 1 ,..., y 4 , z 1 ,..., z 4 логикалық айнымалылардың мәндерінің неше түрлі жиыны келесі шарттардың барлығын қанағаттандырады?

(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1

(y 1 → y 2) ∧ (y 2 → y 3) ∧ (y 3 → y 4) = 1

(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1

x 4 ∧ y 4 ∧ z 4 = 0

Жауапқа керек емесберілген теңдік жүйесі орындалатын x 1 , ..., x 4 , y 1 , ..., y 4 , z 1 , ..., z 4 айнымалы мәндерінің барлық әртүрлі жиындарын тізімдеңіз .

Жауап ретінде мұндай жиынтықтардың санын көрсету керек.

Шешімі:

Жүйенің үш теңдеуі айнымалылардың әртүрлі тәуелсіз жиындарында бірдей екенін ескеріңіз.

Бірінші теңдеуді қарастырайық. Конъюнкция оның барлық операндтары ақиқат (1-ге тең) болғанда ғана ақиқат (1-ге тең) болады. (1,0) қоспағанда, барлық жиындардағы әсер 1-ге тең. Бұл бірінші теңдеудің шешімі x1, x2, x3, x4 жиындары болатынын білдіреді, онда 1 саны 0-нің сол жағында емес (5 жиын):

Сол сияқты, екінші және үшінші теңдеулердің шешімдері y1,…,y4 және z1,…,z4 жиындарының тура бірдей болады.

Енді жүйенің төртінші теңдеуін талдап көрейік: x 4 ∧ y 4 ∧ z 4 = 0. Шешімі айнымалылардың кем дегенде біреуі 0-ге тең x4, y4, z4 барлық жиындары болады.

Анау. x4 = 0 үшін барлық ықтимал жиындар (y4, z4) қолайлы, ал x4 = 1 үшін кем дегенде бір нөлден тұратын жиындар (y4, z4) қолайлы: (0, 0), (0,1) , ( 1, 0).

Жиындардың жалпы саны 25 + 4*9 = 25 + 36 = 61.

Жауап: 61

Қайталанатын формулаларды құру арқылы логикалық теңдеулер жүйесін шешу

Қайталанатын формулаларды құру әдісі жиындар санын көбейту реті анық емес, ал ағашты салу көлемге байланысты мүмкін болмайтын күрделі жүйелерді шешу үшін қолданылады.

5-мысал

Төмендегі барлық шарттарды қанағаттандыратын x1, x2, ... x7, y1, y2, ... y7 логикалық айнымалы мәндерінің қанша түрлі жиыны бар?

(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1

(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1

(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1

Жауапта берілген теңдіктер жүйесі орындалатын x1, x2, ..., x7, y1, y2, ..., y7 айнымалыларының мәндерінің барлық әртүрлі жиындарын тізіп шығудың қажеті жоқ. Жауап ретінде мұндай жиынтықтардың санын көрсету керек.

Шешімі:

Жүйенің алғашқы алты теңдеуі бірдей және тек айнымалылар жиынында ғана ерекшеленетінін ескеріңіз. Бірінші теңдеуді қарастырайық. Оның шешімі келесі айнымалылар жиыны болады:

Белгілеу:

(x1,y1) және A 1 аралығындағы айнымалылардағы жиындар саны (0,0),

(x1,y1) және B 1 аралығындағы айнымалылардағы жиындар саны (0,1),

C 1 арқылы айнымалылардағы (x1,y1) жиындар саны (1,0),

(x1,y1) айнымалылардағы жиындар саны (1,1) D 1 арқылы.

(x2,y2) және A 2 аралығындағы айнымалылардағы жиындар саны (0,0),

B 2 арқылы айнымалылардағы (x2,y2) жиындар саны (0,1),

C 2 арқылы айнымалылардағы (x2,y2) жиындар саны (1,0),

(x2,y2) айнымалылардағы жиындар саны (1,1) D 2 арқылы.

Шешім ағашынан біз мұны көреміз

A 1 =0, B 1 =1, C 1 =1, D 1 =1.

(x2,y2) айнымалылардағы (0,0) кортеж (x1,y1) айнымалылардағы (0,1), (1,0) және (1,1) кортеждерден алынғанын ескеріңіз. Анау. A 2 \u003d B 1 + C 1 + D 1.

(x2,y2) айнымалылардағы (0,1) жиыны (x1,y1) айнымалылардағы (0,1), (1,0) және (1,1) жиындарынан алынады. Анау. B 2 \u003d B 1 + C 1 + D 1.

Сол сияқты дәлелдей отырып, біз C 2 \u003d B 1 + C 1 + D 1 екенін ескереміз. D2 = D1.

Осылайша, біз рекурсивті формулаларды аламыз:

A i+1 = B i + C i + D i

B i+1 = B i + C i + D i

C i+1 = B i + C i + D i

D i+1 = A i + B i + C i + D i

Кесте жасайық

Соңғы теңдеу (x7 ∨ y7) = 1 x7=0 және y7=0 болатын жиындардан басқа барлық жиындармен орындалады. Біздің кестеде мұндай жиынтықтардың саны А 7 .

Сонда жиындардың жалпы саны B 7 + C 7 + D 7 = 127+127+1 = 255 болады.

Жауап: 255

Теңдеулерді қолдану өмірімізде кең таралған. Олар көптеген есептеулерде, құрылымдарды салуда және тіпті спортта қолданылады. Теңдеулерді адам ерте заманнан бері қолданып келеді, содан бері олардың қолданылуы тек қана арта түсті. Математикада ұсыныстардың логикасына арналған белгілі бір тапсырмалар бар. Теңдеудің мұндай түрін шешу үшін сізде белгілі бір білім болуы керек: болжамдық логика заңдарын білу, 1 немесе 2 айнымалының логикалық функцияларының ақиқат кестелерін білу, логикалық өрнектерді түрлендіру әдістері. Сонымен қатар логикалық амалдардың келесі қасиеттерін білу керек: конъюнкциялар, дизъюнкциялар, инверсиялар, импликациялар және эквиваленттіліктер.

\ айнымалылардан - \ кез келген логикалық функция ақиқат кестесі арқылы көрсетілуі мүмкін.

Кейбір логикалық теңдеулерді шешейік:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

Шешімді \[X1\] арқылы бастайық және бұл айнымалы қандай мәндерді қабылдай алатынын анықтайық: 0 және 1. Әрі қарай, жоғарыдағы мәндердің әрқайсысын қарастырып, \[X2.\] не болатынын көріңіз. бұл жағдайда болуы мүмкін

Кестеден көріп отырғанымыздай, логикалық теңдеуіміздің 11 шешімі бар.

Логикалық теңдеуді онлайн қай жерде шешуге болады?

Теңдеуді біздің https: // сайтында шеше аласыз. Тегін онлайн шешуші кез келген күрделіліктегі онлайн теңдеуді секундтарда шешуге мүмкіндік береді. Сізге тек шешушіге деректеріңізді енгізу жеткілікті. Сондай-ақ біздің веб-сайттан бейне нұсқаулығын көре аласыз және теңдеуді шешу жолын біле аласыз. Ал сұрақтарыңыз болса, біздің http://vk.com/pocketteacher Вконтакте тобымызда қоя аласыздар. Біздің топқа қосылыңыз, біз сізге көмектесуге әрқашан қуаныштымыз.

Логикалық теңдеулер жүйесін шешу жолдары

Киргизова Е.В., Немкова А.Е.

Лесосібір педагогикалық институты -

Сібір федералды университетінің филиалы, Ресей

Жүйелі ойлау, тұжырымды дәлелдеу, гипотеза құру, теріс қорытындыларды жоққа шығару өздігінен пайда болмайды, бұл дағдыны логика ғылымы дамытады. Логика – басқа тұжырымдардың ақиқаттығы немесе жалғандығы негізінде кейбір тұжырымдардың ақиқаттығын немесе жалғандығын анықтау әдістерін зерттейтін ғылым.

Бұл ғылымның негіздерін меңгеру логикалық есептерді шешпей мүмкін емес. Алған білімдерін жаңа жағдайда қолдана білу дағдыларының қалыптасуын тексеру өту арқылы жүзеге асырылады. Атап айтқанда, бұл логикалық есептерді шығару қабілеті. Емтихандағы B15 тапсырмалары күрделілігі жоғары тапсырмалар болып табылады, өйткені олардың құрамында логикалық теңдеулер жүйесі бар. Логикалық теңдеулер жүйесін шешудің әртүрлі тәсілдері бар. Бұл бір теңдеуге келтіру, ақиқат кестесін құру, декомпозиция, теңдеулерді тізбектей шешу және т.б.

Тапсырма:Логикалық теңдеулер жүйесін шешіңіз:

Қарастырыңыз бір теңдеуге келтіру әдісі . Бұл әдіс логикалық теңдеулерді олардың оң жақтары ақиқат мәніне (яғни 1) тең болатындай түрлендіруді қамтиды. Ол үшін логикалық терістеу операциясын қолданыңыз. Содан кейін теңдеулерде күрделі логикалық амалдар болса, оларды негізгілерімен ауыстырамыз: «ЖӘНЕ», «НЕМЕСЕ», «ЕМЕС». Келесі қадам «ЖӘНЕ» логикалық операциясын қолдана отырып, жүйеге эквивалентті теңдеулерді біріктіру болып табылады. Осыдан кейін логика алгебрасы заңдары негізінде алынған теңдеуді түрлендірулер жасап, жүйенің нақты шешімін алу керек.

Шешім 1:Бірінші теңдеудің екі жағына да инверсияны қолданыңыз:

«НЕМЕСЕ», «ЕМЕС» негізгі операциялары арқылы импликацияны көрсетейік:

Теңдеулердің сол жақтары 1-ге тең болғандықтан, оларды «ЖӘНЕ» операциясы арқылы бастапқы жүйеге баламалы бір теңдеуге біріктіруге болады:

Де Морган заңы бойынша бірінші жақшаны ашып, нәтижені түрлендіреміз:

Алынған теңдеудің бір шешімі бар: A= 0 , B=0 және C=1 .

Келесі жолы ақиқат кестелерін құру . Логикалық мәндердің тек екі мәні бар болғандықтан, сіз жай ғана барлық опцияларды қарап шығып, олардың арасынан берілген теңдеулер жүйесі қанағаттандырылатынын таба аласыз. Яғни, жүйенің барлық теңдеулері үшін бір ортақ ақиқат кестесін құрастырамыз және қажетті мәндері бар сызықты табамыз.

Шешім 2:Жүйе үшін ақиқат кестесін құрайық:

Қалың – мәселенің шарттары орындалатын жол. Сонымен A =0, B =0 және C =1.

Жол ыдырау . Идея айнымалылардың бірінің мәнін бекіту (оны 0 немесе 1-ге теңестіру) және сол арқылы теңдеулерді жеңілдету. Содан кейін екінші айнымалының мәнін түзетуге болады және т.б.

3-шешім:Болсын A = 0, онда:

Бірінші теңдеуден біз аламызБ =0, ал екіншісінен - ​​С=1. Жүйелік шешім: A = 0 , B = 0 және C = 1 .

Сіз сондай-ақ әдісті пайдалана аласыз теңдеулерді ретімен шешу , әрбір қадамда қарастырылатын жиынға бір айнымалыны қосу. Ол үшін теңдеулерді айнымалылар алфавиттік ретпен енгізілетіндей етіп түрлендіру қажет. Әрі қарай, біз оған айнымалыларды дәйекті түрде қоса отырып, шешім ағашын жасаймыз.

Жүйенің бірінші теңдеуі тек А мен В-ға, ал екінші теңдеуі А мен С-ға тәуелді. А айнымалысы 0 және 1 мәндерін қабылдай алады:

Бірінші теңдеуден бұл шығады , енді қашан A = 0 біз B = 0 аламыз, ал A = 1 үшін бізде B = 1 болады. Сонымен, бірінші теңдеудің A және B айнымалыларына қатысты екі шешімі бар.

Біз екінші теңдеуді саламыз, одан әрбір опция үшін С мәндерін анықтаймыз. A =1 үшін импликация жалған болуы мүмкін емес, яғни ағаштың екінші тармағында шешім жоқ. Сағат A= 0 жалғыз шешімді аламыз C= 1 :

Осылайша, біз жүйенің шешімін алдық: A = 0 , B = 0 және C = 1 .

Информатикадағы USE-де логикалық теңдеулер жүйесінің шешімдерінің санын анықтау өте жиі қажет, шешімдердің өзін таппай, бұл үшін белгілі әдістер де бар. Логикалық теңдеулер жүйесінің шешімдерінің санын табудың негізгі жолы болып табылады айнымалылардың өзгеруі. Біріншіден, логика алгебрасы заңдарына сүйене отырып, теңдеулердің әрқайсысын мүмкіндігінше жеңілдету керек, содан кейін теңдеулердің күрделі бөліктерін жаңа айнымалылармен ауыстырып, жаңа жүйенің шешімдерінің санын анықтау керек. Содан кейін ауыстыруға оралыңыз және оған арналған шешімдердің санын анықтаңыз.

Тапсырма:( теңдеуінің неше шешімі бар A → B ) + (C → D ) = 1? Мұндағы A, B, C, D логикалық айнымалылар.

Шешімі:Жаңа айнымалыларды енгізейік: X = A → B және Y = C → D . Жаңа айнымалыларды ескере отырып, теңдеуді былай жазуға болады: X + Y = 1.

Дизъюнкция үш жағдайда дұрыс болады: (0;1), (1;0) және (1;1), while X және Y импликация болып табылады, яғни үш жағдайда ақиқат, біреуінде жалған. Сондықтан (0;1) жағдай параметрлердің үш мүмкін комбинациясына сәйкес болады. Жағдай (1;1) - бастапқы теңдеу параметрлерінің тоғыз мүмкін комбинациясына сәйкес болады. Демек, бұл теңдеудің 3+9=15 мүмкін шешімі бар.

Логикалық теңдеулер жүйесінің шешімдерінің санын анықтаудың келесі жолы – − екілік ағаш. Бұл әдісті мысалмен қарастырайық.

Тапсырма:Логикалық теңдеулер жүйесінің неше түрлі шешімі бар:

Берілген теңдеулер жүйесі мына теңдеуге эквивалентті:

( x 1 → x 2 )*( x 2 → x 3 )*…*( x м -1 → x м) = 1.

Солай етейікx 1 дұрыс болса, онда бірінші теңдеуден біз оны аламызx 2 да дұрыс, екіншісінен -x 3 =1 және т.б. дейін x м= 1. Осыдан (1; 1; …; 1) жиыны шығадым бірліктер жүйенің шешімі болып табылады. Енді рұқсат етіңізx 1 =0, онда бірінші теңдеуден бізде барx 2 =0 немесе x 2 =1.

Қашан x 2 ақиқат болса, біз басқа айнымалылардың да ақиқат екенін аламыз, яғни жиын (0; 1; ...; 1) жүйенің шешімі болып табылады. Сағатx 2 =0 біз оны аламыз x 3 =0 немесе x 3 = және т.б. Соңғы айнымалыны жалғастыра отырып, теңдеудің шешімдері келесі айнымалылар жиыны (м +1 ерітінді, әрбір ерітіндідем айнымалы мәндер):

(1; 1; 1; …; 1)

(0; 1; 1; …; 1)

(0; 0; 0; …; 0)

Бұл тәсіл екілік ағашты құру арқылы жақсы суреттелген. Ықтимал шешімдер саны - салынған ағаштың әртүрлі бұтақтарының саны. Ол екенін байқау қиын емес m+1.

Шешім ағашын құру және пайымдау кезінде қиындықтар туындаған жағдайда, сіз шешімді пайдаланып іздеуге болады ақиқат кестелері, бір немесе екі теңдеу үшін.

Теңдеулер жүйесін келесі түрде қайта жазамыз:

Ал бір теңдеу үшін ақиқат кестесін бөлек құрайық:

Екі теңдеу үшін ақиқат кестесін құрайық:

Келесі үш жағдайда бір теңдеудің ақиқат екенін көруге болады: (0; 0), (0; 1), (1; 1). Екі теңдеулер жүйесі төрт жағдайда (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1) дұрыс болады. Бұл жағдайда тек нөлдерден және одан да көп сандардан тұратын шешім бар екені бірден анық болады мсоңғы орыннан бастап барлық мүмкін орындар толтырылғанға дейін бір бірлік қосылған шешімдер. Жалпы шешім бірдей пішінде болады деп болжауға болады, бірақ мұндай тәсіл шешімге айналуы үшін болжамның ақиқат екендігін дәлелдеу қажет.

Жоғарыда айтылғандардың барлығын қорытындылай келе, қарастырылған әдістердің барлығы әмбебап емес екеніне назар аударғым келеді. Әрбір логикалық теңдеулер жүйесін шешу кезінде оның ерекшеліктерін ескеріп, соның негізінде шешу әдісін таңдау керек.

Әдебиет:

1. Логикалық тапсырмалар / О.Б. Богомолов - 2-ші басылым. – М.: БИНОМ. Білім зертханасы, 2006. - 271 б.: сырқат.

2. Поляков К.Ю. Логикалық теңдеулер жүйесі / Информатика мұғалімдеріне арналған оқу-әдістемелік газет: Информатика No14, 2011 ж.

Логикалық теңдеулер жүйесін шешу әдістері

Логикалық теңдеулер жүйесін шешуге болады, мысалы, ақиқат кестесін (егер айнымалылар саны тым көп болмаса) немесе шешім ағашын пайдаланып, әрбір теңдеуді жеңілдеткеннен кейін.

1. Айнымалыларды өзгерту әдісі.

Жаңа айнымалыларды енгізу белгісіздер санын азайту арқылы теңдеулер жүйесін жеңілдетуге мүмкіндік береді.Жаңа айнымалылар бір-бірінен тәуелсіз болуы керек. Жеңілдетілген жүйені шешкеннен кейін бастапқы айнымалыларға қайта оралу қажет.

Бұл әдісті нақты мысалда қолдануды қарастырыңыз.

Мысал.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Шешімі:

Жаңа айнымалыларды енгізейік: А=(X1≡X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Назар аударыңыз! Олардың әрбір айнымалысы x1, x2, ..., x10 жаңа A, B, C, D, E айнымалыларының біреуіне ғана қосылуы керек, яғни жаңа айнымалылар бір-бірінен тәуелсіз).

Сонда теңдеулер жүйесі келесідей болады:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Алынған жүйенің шешім ағашын құрастырайық:

A=0 теңдеуін қарастырайық, яғни. (X1≡ X2)=0. Оның 2 тамыры бар:

Сол кестеден A \u003d 1 теңдеуінің де 2 түбірі бар екенін көруге болады. Шешім ағашындағы түбірлердің санын реттейік:

Бір тармақтың шешімдерінің санын табу үшін әр деңгейдегі шешімдердің санын көбейту керек. Сол тармақта 2 бар⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 шешім; оң тармақта да 32 шешім бар. Анау. бүкіл жүйенің 32+32=64 шешімі бар.

Жауабы: 64.

2. Қорытындылау әдісі.

Логикалық теңдеулер жүйесін шешудің күрделілігі толық шешім ағашының көлемділігінде жатыр. Дәлелдеу әдісі бүкіл ағашты толығымен салуға емес, сонымен бірге оның қанша бұтақтары болатынын түсінуге мүмкіндік береді. Бұл әдісті нақты мысалдар бойынша қарастырайық.

1-мысал Төмендегі барлық шарттарды қанағаттандыратын x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 логикалық айнымалылардың мәндерінің қанша әртүрлі жиыны бар?

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1

(y1→y2) /\ (y2→y3) /\ (y3→y4) /\ (y4→y5) = 1

x1\/y1 =1

Жауапта берілген теңдіктер жүйесі қанағаттандырылатын x1, x2, x3, x4, x5, y1, y2, y3, y4, y5 айнымалыларының мәндерінің барлық әртүрлі жиындарын тізіп шығудың қажеті жоқ. Жауап ретінде мұндай жиынтықтардың санын көрсету керек.

Шешім:

Бірінші және екінші теңдеулерде үшінші шартпен байланысқан тәуелсіз айнымалылар бар. Бірінші және екінші теңдеулер үшін шешім ағашын құрастырайық.

Бірінші және екінші теңдеулерден жүйенің шешім ағашын көрсету үшін бірінші ағаштың әрбір тармағын айнымалылар ағашымен жалғастыру керек.сағ . Осылайша салынған ағашта 36 бұтақ болады. Бұл тармақтардың кейбірі жүйенің үшінші теңдеуін қанағаттандырмайды. Бірінші ағашқа ағаштың бұтақтарының санын белгілеңіз"ат" , үшінші теңдеуді қанағаттандыратын:

Түсіндірейік: үшінші шарттың орындалуы үшін x1=0 кезінде y1=1, яғни ағаштың барлық бұтақтары болуы керек."X" , мұнда x1=0 ағаштан бір ғана бұтақпен жалғастыруға болады"ат" . Және тек ағаштың бір бұтағы үшін"X" (оң жақта) ағаштың барлық бұтақтарына сәйкес келеді«ат». Осылайша, бүкіл жүйенің толық ағашы 11 тармақты қамтиды. Әрбір тармақ бастапқы теңдеулер жүйесінің бір шешімін білдіреді. Сонымен, бүкіл жүйеде 11 шешім бар.

Жауабы: 11.

2-мысал Теңдеулер жүйесінің неше түрлі шешімі бар

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬X10)= 1

(X1 ≡ X10) = 0

мұндағы x1, x2, …, x10 логикалық айнымалылар? Жауапта бұл теңдік сақталатын айнымалы мәндердің барлық әртүрлі жиындарын тізімдеу қажет емес. Жауап ретінде мұндай жиынтықтардың санын көрсету керек.

Шешім: Жүйені жеңілдетейік. Бірінші теңдеудің бөлігінің ақиқат кестесін құрайық:

Соңғы бағанға назар аударыңыз, ол әрекеттің нәтижесіне сәйкес келеді X1 ≡ X10.

Жеңілдетілгеннен кейін біз мынаны аламыз:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Соңғы теңдеуді қарастырайық:(X1 ≡ X10) = 0 , яғни. x1 x10 сияқты болмауы керек. Бірінші теңдеу 1-ге тең болуы үшін теңдік сақталуы керек(X1 ≡ X2)=1, яғни. x1 x2 сәйкес келуі керек.

Бірінші теңдеу үшін шешім ағашын құрайық:

Екінші теңдеуді қарастырайық: x10=1 үшін және x2=0 үшін жақша1-ге тең болуы керек (яғни x2 х3 сияқты); x10=0 және x2=1 жақшада(X2 ≡ X10)=0, сондықтан жақша (X2 ≡ X3) 1-ге тең болуы керек (яғни x2 x3 сияқты):

Осылай дәлелдей отырып, біз барлық теңдеулер үшін шешім ағашын саламыз:

Сонымен, теңдеулер жүйесінің тек 2 шешімі бар.

Жауабы: 2.

3-мысал

x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4 логикалық айнымалылардың мәндерінің неше түрлі жиыны келесі шарттардың барлығын қанағаттандырады?

(x1→x2) /\ (x2→x3) /\ (x3→x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Шешімі:

1-ші теңдеудің шешім ағашын құрастырайық:

Екінші теңдеуді қарастырайық:

• x1=0 болғанда : екінші және үшінші жақшалар 0 болады; бірінші жақша 1-ге тең болуы үшін y1=1 , z1=1 болуы керек (яғни, бұл жағдайда - 1 шешім)
• x1=1 арқылы : бірінші жақша 0 болады; екіншінемесе үшінші жақша 1-ге тең болуы керек; y1=0 және z1=1 болғанда екінші жақша 1-ге тең болады; үшінші жақша y1=1 және z1=0 үшін 1-ге тең болады (яғни, бұл жағдайда - 2 шешім).

Қалған теңдеулер үшін де солай. Ағаштың әрбір түйіні үшін алынған шешімдердің санын ескеріңіз:

Әрбір тармақ бойынша шешімдердің санын білу үшін алынған сандарды әр тармаққа (солдан оңға қарай) бөлек көбейтеміз.

1 тармақ: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 ерітінді

2 тармақ: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 шешім

3-тармақ: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 шешім

4 тармақ: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 шешім

5 тармақ: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 шешім

Алынған сандарды қосайық: барлығы 31 шешім.

Жауабы: 31.

3. Тамыр санының жүйелі түрде көбеюі

Кейбір жүйелерде келесі теңдеудің түбірлерінің саны алдыңғы теңдеудің түбірлерінің санына байланысты болады.

1-мысал Төмендегі барлық шарттарды қанағаттандыратын x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 логикалық айнымалы мәндерінің қанша түрлі жиыны бар?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Жеңілдету бірінші теңдеу:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡) x3). Содан кейін жүйе келесі пішінді алады:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

Және т.б.

Әрбір келесі теңдеудің алдыңғыға қарағанда 2 түбірі көп.

4 теңдеудің 12 түбірі бар;

5-теңдеудің 14 түбірі бар

8 теңдеудің 20 түбірі бар.

Жауабы: 20 тамыр.

Кейде түбірлердің саны Фибоначчи сандарының заңы бойынша өседі.

Логикалық теңдеулер жүйесін шешу шығармашылық көзқарасты қажет етеді.

Қалалық бюджеттік білім беру мекемесі

«No18 орта мектеп»

Башқұртстан Республикасы Салават қаласындағы қалалық округ

Логикалық теңдеулер жүйесі

информатикадан емтихан тапсырмаларында

Емтихан тапсырмаларындағы «Логика алгебрасының негіздері» бөлімі ең қиын және нашар шешілген бөлімдердің бірі болып саналады. Осы тақырып бойынша тапсырмаларды орындаудың орташа пайызы ең төмен және 43,2 құрайды.

KIM 2018 спецификациясының негізінде бұл блок күрделілік деңгейі әртүрлі төрт тапсырманы қамтиды.

23-тапсырма күрделіліктің жоғары деңгейі, сондықтан оның орындалу пайызы ең төмен. Дайындалған түлектер арасында (81-100 балл) 49,8% тапсырманы орындады, орташа дайындық (61-80 балл) 13,7% орындады, қалған студенттер тобы бұл тапсырманы орындамайды.

Логикалық теңдеулер жүйесін шешудің табыстылығы логика заңдарын білуге ​​және жүйені шешу әдістерін дәл қолдануға байланысты.

Логикалық теңдеулер жүйесін картаға түсіру әдісімен шешуді қарастырыңыз.

(23.154 Поляков К.Ю.) Теңдеулер жүйесінің неше түрлі шешімі бар?

((x1  ж1 )  (x2  ж2 ))  (x1  x2 )  (ж1  ж2 ) =1

((x2  ж2 )  (x3  ж3 ))  (x2  x3 )  (ж2  ж3 ) =1

((x7  ж7 )  (x8  ж8 ))  (x7  x8 )  (ж7  ж8 ) =1

Қайда x1 , x2 ,…, x8, сағ1 , ж2 ,…,ж8 - Логикалық айнымалылар? Жауапта бұл теңдік сақталатын айнымалы мәндердің барлық әртүрлі жиындарын тізімдеу қажет емес. Жауап ретінде мұндай жиынтықтардың санын көрсету керек.

Шешім. Жүйеге енгізілген барлық теңдеулер бір типті және әр теңдеуде төрт айнымалы бар. x1 және y1 біле отырып, біз бірінші теңдеуді қанағаттандыратын x2 және y2 барлық мүмкін мәндерін таба аламыз. Осыған ұқсас түрде дәлелдей отырып, белгілі x2 және y2-тен екінші теңдеуді қанағаттандыратын x3, y3-ті табуға болады. Яғни (x1 , y1) жұбын біліп, (x2 , y2) жұбының мәнін анықтай отырып, (x3 , y3 ) жұбын табамыз, ол өз кезегінде (x4 , y4 ) жұбына әкеледі және т.б. қосулы.

Бірінші теңдеудің барлық шешімдерін табайық. Мұны екі жолмен жасауға болады: ақиқат кестесін құру, логика заңдарын пайымдау және қолдану арқылы.

Ақиқат кестесі:

Ақиқат кестесін құру көп еңбекті және уақытты тиімсіз, сондықтан біз екінші әдісті – логикалық пайымдауды қолданамыз. Әрбір фактор 1 болса ғана туынды 1 болады.

(x1  ж1 )  (x2  ж2 ))=1

(x1  x2 ) =1

(ж1  ж2 ) =1

Бірінші теңдеуді қарастырайық. Келесі 1-ге тең, 0 0, 0 1, 1 1, содан кейін (01), (10) кезінде (x1 y1)=0, содан кейін жұп (x2  ж2 ) кез келген (00), (01), (10), (11) болуы мүмкін және (x1 y1)=1 үшін, яғни (00) және (11) жұбы (x2 y2)=1 бірдей мәндерді қабылдайды (00) және (11). Бұл шешімнен екінші және үшінші теңдеулері жалған, яғни x1=1, x2=0, y1=1, y2=0 болатын жұптарды алып тастаймыз.

Жұптардың жалпы саны 1+1+1+22= 25

2) (23.160 Поляков К.Ю.) Логикалық теңдеулер жүйесінің неше түрлі шешімі бар

(x 1  (x 2  ж 2 ))  (ж 1  ж 2 ) = 1

(x 2  (x 3  ж 3 ))  (ж 2  ж 3 ) = 1

...

( x 6  ( x 7  ж 7 ))  ( ж 6  ж 7 ) = 1

x 7  ж 7 = 1

Шешім. 1) Теңдеулер бір типті, сондықтан пайымдау әдісі арқылы бірінші теңдеудің барлық мүмкін жұптарын (x1,y1), (x2,y2) табамыз.

(x1  (x2  ж2 ))=1

(ж1  ж2 ) = 1

Екінші теңдеудің шешімі (00), (01), (11) жұптары.

Бірінші теңдеудің шешімдерін табайық. Егер x1=0 болса, онда x2 , y2 - кез келген, егер x1=1 болса, онда x2 , y2 (11) мәнін қабылдайды.

(x1 , y1) және (x2 , y2) жұптары арасында байланыс орнатайық.

Әр кезеңдегі жұптардың санын есептеу үшін кесте құрайық.

Соңғы теңдеудің шешімдерін есепке алу x 7  ж 7 = 1, (10) жұбын жоямыз. 1+7+0+34=42 шешімдерінің жалпы санын табыңыз

3)(23.180) Логикалық теңдеулер жүйесінің неше түрлі шешімі бар

(x1  x2 )  (x3  x4 ) = 1

(x3  x4 )  (x5  x6 ) = 1

(x5  x6 )  (x7  x8 ) = 1

(x7  x8 )  (x9  x10 ) = 1

x1  x3  x5  x7  x9 = 1

Шешім. 1) Теңдеулер бір типті, сондықтан пайымдау әдісі арқылы бірінші теңдеудің барлық мүмкін жұптарын (x1,x2), (x3,x4) табамыз.

(x1  x2 )  (x3  x4 ) = 1

Келесіде 0 (1 0) беретін жұптарды шешімнен шығарамыз, бұлар (01, 00, 11) және (10) жұптары.

(x1,x2), (x3,x4) жұптар арасындағы сілтемелерді құрастыру