Решавање на логички равенки во математиката. Методи за решавање системи на логички равенки Систем на Булови равенки

Решавање системи на логички равенки со промена на променливи

Методот за промена на променливи се користи ако некои променливи се вклучени во равенките само во форма на специфичен израз, и ништо друго. Тогаш овој израз може да се означи со нова променлива.

Пример 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, единицата не смее да биде лево од нулата:

Оние. исполнети се услови за 5 сета y1-y4.

Бидејќи y1 = x1 → x2, тогаш вредноста y1 = 0 се постигнува на едно множество x1, x2: (1, 0), а вредноста y1 = 1 се постигнува на три множества x1, x2: (0,0) , ( 0,1), (1,1). Слично за y2, y3, y4.

Бидејќи секое множество (x1,x2) за променливата y1 е комбинирано со секое множество (x3,x4) за променливата y2 и така натаму, се множат броевите на множества на променливи 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 на сите множества освен (1,0). Ова значи дека решението на првата равенка ќе биде такви множества x1, x2, x3, x4, во кои 1 не е лево од 0 (5 множества):

Слично, решенијата на втората и третата равенка ќе бидат токму истите множества од y1,…,y4 и z1,…,z4.

Сега да ја анализираме четвртата равенка на системот: x 4 ∧ y 4 ∧ z 4 = 0. Решението ќе бидат сите множества x4, y4, z4 во кои барем една од променливите е еднаква на 0.

Оние. за 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, под кои важи дадениот систем на еднаквости. Како одговор, треба да го наведете бројот на такви сетови.

Решение:

Забележете дека првите шест равенки на системот се исти и се разликуваат само во множеството променливи. Размислете за првата равенка. Неговото решение ќе биде следниве групи на променливи:

Означи:

број на множества (0,0) на променливите (x1,y1) до A 1,

број на множества (0,1) на променливите (x1,y1) до B 1,

број на множества (1,0) на променливите (x1,y1) преку C 1 ,

број на множества (1,1) на променливите (x1,y1) преку D 1 .

број на множества (0,0) на променливите (x2,y2) до A 2,

број на множества (0,1) на променливите (x2,y2) преку B 2 ,

број на множества (1,0) на променливите (x2,y2) преку C 2,

број на множества (1,1) на променливите (x2,y2) преку D 2 .

Од дрвото на одлуки, го гледаме тоа

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

Забележете дека торката (0,0) на променливите (x2,y2) се добива од торките (0,1), (1,0) и (1,1) на променливите (x1,y1). Оние. A 2 \u003d B 1 + C 1 + D 1.

Множеството (0,1) на променливите (x2,y2) се добива од множествата (0,1), (1,0) и (1,1) на променливите (x1,y1). Оние. 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. Во нашата табела, бројот на такви множества е A 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: // страница. Бесплатен онлајн решавач ќе ви овозможи да решите онлајн равенка од секаква сложеност за неколку секунди. Сè што треба да направите е само да ги внесете вашите податоци во решавачот. Можете исто така да ја гледате видео-инструкцијата и да научите како да ја решите равенката на нашата веб-страница. И ако имате какви било прашања, можете да ги поставите во нашата група Vkontakte http://vk.com/pocketteacher. Придружете се на нашата група, ние секогаш сме среќни да ви помогнеме.

Начини за решавање системи на логички равенки

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

Лесосибирск педагошки институт -

филијала на Сибирскиот федерален универзитет, Русија

Способноста да се размислува доследно, да се расправа убедливо, да се градат хипотези, да се побиваат негативните заклучоци, не доаѓа сама по себе, оваа вештина е развиена од науката за логика. Логиката е наука која ги проучува методите за утврдување на вистинитоста или неточноста на некои изјави врз основа на вистинитоста или неточноста на други изјави.

Совладувањето на основите на оваа наука е невозможно без решавање на логички проблеми. Проверката на формирањето на вештини за примена на нивното знаење во нова ситуација се врши со полагање. Особено, ова е способност за решавање на логички проблеми. Задачите Б15 на испитот се задачи со зголемена сложеност, бидејќи содржат системи на логички равенки. Постојат различни начини за решавање на системи на логички равенки. Ова е намалување на една равенка, изградба на табела на вистинитост, распаѓање, секвенцијално решение на равенките итн.

Задача:Решете систем на логички равенки:

Да се ​​разгледа метод за намалување на една равенка . Овој метод вклучува трансформација на логички равенки, така што нивните десни страни се еднакви на вредноста на вистината (т.е. 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 .

Можете исто така да го користите методот секвенцијално решение на равенките , додавајќи по една променлива на множеството што се разгледува на секој чекор. За да го направите ова, неопходно е да се трансформираат равенките на таков начин што променливите се внесуваат по азбучен ред. Следно, градиме дрво за одлуки, секвенцијално додавајќи променливи на него.

Првата равенка на системот зависи само од А и Б, а втората равенка од А и В. Променливата А може да земе 2 вредности 0 и 1:

Од првата равенка произлегува дека , па кога A = 0 добиваме B = 0 , а за A = 1 имаме B = 1 . Значи, првата равенка има две решенија во однос на променливите A и B.

Ја цртаме втората равенка, од која ги одредуваме вредностите на C за секоја опција. За A =1, импликацијата не може да биде лажна, односно втората гранка од дрвото нема решение. На A= 0 го добиваме единственото решение C= 1 :

Така, го добивме решението на системот: A = 0 , B = 0 и C = 1 .

Во УПОТРЕБАТА во компјутерската наука, многу често е потребно да се одреди бројот на решенија на систем на логички равенки, без да се најдат самите решенија, постојат и одредени методи за ова. Главниот начин да се најде бројот на решенија на систем на логички равенки е промена на променливите. Прво, потребно е да се поедностави секоја од равенките што е можно повеќе врз основа на законите на алгебрата на логиката, а потоа да се заменат сложените делови од равенките со нови променливи и да се одреди бројот на решенија за новиот систем. Потоа вратете се на замена и утврдете го бројот на решенија за него.

Задача:Колку решенија има равенката ( A → B ) + (C → D ) = 1? Каде што A, B, C, D се булови променливи.

Решение:Ајде да воведеме нови променливи: X = A → B и Y = C → D . Земајќи ги предвид новите променливи, равенката може да се запише како: X + Y = 1.

Дисјункцијата е точна во три случаи: (0;1), (1;0) и (1;1), додека X и Y е импликација, односно во три случаи е точно, а во еден неточно. Затоа, случајот (0;1) ќе одговара на три можни комбинации на параметри. Случај (1;1) - ќе одговара на девет можни комбинации на параметрите на оригиналната равенка. Оттука, постојат 3+9=15 можни решенија на оваа равенка.

Следниот начин за одредување на бројот на решенија на систем од логички равенки е − бинарно дрво. Да го разгледаме овој метод со пример.

Задача:Колку различни решенија има системот на логички равенки:

Дадениот систем на равенки е еквивалентен на равенката:

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

Ајде да се преправаме декаx 1 е точно, тогаш од првата равенка го добиваме тоаx 2 исто така точно, од втората -x 3 =1, и така натаму додека x m= 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. Полјаков К.Ју. Системи на логички равенки / Едукативен и методички весник за наставници по компјутерски науки: Информатика бр. 14, 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, т.е. сите гранки на дрвото"Х" , каде што x1=0 може да се продолжи со само една гранка од дрвото"на" . И тоа само за една гранка од дрвото"Х" (десно) одговара на сите гранки на дрвото"во". Така, целосното дрво на целиот систем содржи 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 е исто како x3); во 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

Решение:

Ајде да изградиме дрво на одлуки од првата равенка:

Размислете за втората равенка:

• Кога x1=0 : втората и третата заграда ќе бидат 0; за првата заграда да биде еднаква на 1, мора y1=1 , z1=1 (т.е. во овој случај - 1 решение)
• Со x1=1 : првата заграда ќе биде 0; второили третата заграда мора да биде еднаква на 1; втората заграда ќе биде еднаква на 1 кога y1=0 и z1=1; третата заграда ќе биде еднаква на 1 за y1=1 и z1=0 (т.е. во овој случај - 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 корени.

Понекогаш бројот на корените расте според законот на броевите на Фибоначи.

Решавањето на систем на логички равенки бара креативен пристап.

Општинска буџетска образовна институција

„СОУ бр.18“

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

Системи на логички равенки

во задачите на испитот по информатика

Делот „Основи на алгебрата на логиката“ во задачите на испитот се смета за еден од најтешките и слабо решените. Просечниот процент на исполнување задачи на оваа тема е најмал и изнесува 43,2.

Врз основа на спецификацијата на KIM 2018, овој блок вклучува четири задачи од различни нивоа на сложеност.

Задачата 23 е високо ниво на тежина, затоа има најмал процент на завршено. Од обучените дипломци (81-100 поени) 49,8% ја завршиле задачата, просечно подготвените (61-80 поени) се справуваат со 13,7%, останатата група студенти не ја завршуваат оваа задача.

Успешноста во решавањето на системот на логички равенки зависи од познавањето на законите на логиката и од прецизната примена на методите за решавање на системот.

Да го разгледаме решението на систем од логички равенки со методот на пресликување.

(23.154 Полјаков К.Ју.) Колку различни решенија има системот на равенки?

((х1  y1 )  (х2  y2 ))  (х1  x2 )  (y1  y2 ) =1

((х2  y2 )  (х3  y3 ))  (х2  x3 )  (y2  y3 ) =1

((x7  y7 )  (x8  y8 ))  (x7  x8 )  (y7  y8 ) =1

каде x1 , x2 ,…, x8, на1 , y2 ,…,y8 - Булови променливи? Одговорот не треба да ги наведе сите различни групи на променливи вредности за кои важи оваа еднаквост. Како одговор, треба да го наведете бројот на такви сетови.

Решение. Сите равенки вклучени во системот се од ист тип, а во секоја равенка се вклучени четири променливи. Знаејќи ги x1 и y1, можеме да ги најдеме сите можни вредности на x2 и y2 кои ја задоволуваат првата равенка. Аргументирајќи на сличен начин, од познатите x2 и y2 можеме да најдеме x3, y3 што ја задоволува втората равенка. Односно, познавајќи го парот (x1 , y1) и одредувајќи ја вредноста на парот (x2 , y2) , ќе го најдеме парот (x3 , y3 ), кој пак ќе доведе до парот (x4 , y4 ) и т.н. на.

Да ги најдеме сите решенија на првата равенка. Ова може да се направи на два начина: да се изгради табела за вистинитост, преку расудување и примена на законите на логиката.

Табела на вистината:

Изградбата на табела за вистинитост е макотрпна и временски неефикасна, затоа го користиме вториот метод - логично расудување. Производот е 1 ако и само ако секој фактор е 1.

(x1  y1 )  (x2  y2 ))=1

(x1  x2 ) =1

(y1  y2 ) =1

Размислете за првата равенка. Следното е еднакво на 1, кога 0 0, 0 1, 1 1, тогаш (x1 y1)=0 на (01), (10), тогаш парот (x2  y2 ) може да биде било кој (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 Полјаков К.Ју.) Колку различни решенија има системот на логички равенки

(х 1  (х 2  y 2 ))  (y 1  y 2 ) = 1

(х 2  (х 3  y 3 ))  (y 2  y 3 ) = 1

...

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

x 7  y 7 = 1

Решение. 1) Равенките се од ист тип, па со методот на расудување ќе ги најдеме сите можни парови (x1,y1), (x2,y2) од првата равенка.

(x1  (x2  y2 ))=1

(y1  y2 ) = 1

Решението на втората равенка се парови (00), (01), (11).

Ајде да најдеме решенија за првата равенка. Ако x1=0, тогаш x2, y2 - било, ако x1=1, тогаш x2, y2 ја зема вредноста (11).

Ајде да направиме врски помеѓу парови (x1 , y1) и (x2 , y2).

Ајде да направиме табела за да го пресметаме бројот на парови во секоја фаза.

Земајќи ги предвид решенијата на последната равенка x 7  y 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)