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

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

Методът за промяна на променливите се използва, ако някои променливи са включени в уравненията само под формата на конкретен израз и нищо друго. Тогава този израз може да бъде обозначен с нова променлива.

Пример 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: // site. Безплатният онлайн решаващ инструмент ще ви позволи да решите онлайн уравнение с всякаква сложност за секунди. Всичко, което трябва да направите, е просто да въведете данните си в решаващия инструмент. Можете също така да гледате видео инструкцията и да научите как да решите уравнението на нашия уебсайт. И ако имате въпроси, можете да ги зададете в нашата група Vkontakte http://vk.com/pocketteacher. Присъединете се към нашата група, винаги се радваме да ви помогнем.

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

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

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

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

Способността да се мисли последователно, да се аргументира убедително, да се изграждат хипотези, да се опровергават отрицателни заключения, не идва от само себе си, това умение се развива от науката на логиката. Логиката е наука, която изучава методите за установяване на истинността или неистинността на някои твърдения въз основа на истинността или неистинността на други твърдения.

Овладяването на основите на тази наука е невъзможно без решаване на логически проблеми. Проверката на формирането на умения за прилагане на знанията в нова ситуация се извършва чрез преминаване. По-специално, това е способността за решаване на логически проблеми. Задачи B15 от изпита са задачи с повишена сложност, тъй като съдържат системи от логически уравнения. Има различни начини за решаване на системи от логически уравнения. Това е свеждане до едно уравнение, изграждане на таблица на истината, разлагане, последователно решаване на уравнения и т.н.

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

Обмисли метод на свеждане до едно уравнение . Този метод включва преобразуване на логически уравнения, така че техните десни части да са равни на истинската стойност (т.е. 1). За да направите това, използвайте операцията на логическо отрицание. След това, ако в уравненията има сложни логически операции, ги заменяме с основни: „И“, „ИЛИ“, „НЕ“. Следващата стъпка е да комбинирате уравненията в едно, еквивалентно на системата, като използвате логическата операция "И". След това трябва да направите трансформации на полученото уравнение въз основа на законите на алгебрата на логиката и да получите конкретно решение на системата.

Решение 1:Приложете инверсията към двете страни на първото уравнение:

Нека представим импликацията чрез основните операции "ИЛИ", "НЕ":

Тъй като левите части на уравненията са равни на 1, можете да ги комбинирате с помощта на операцията „И“ в едно уравнение, което е еквивалентно на оригиналната система:

Отваряме първата скоба според закона на де Морган и трансформираме резултата:

Полученото уравнение има едно решение:А= 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 .

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

Първото уравнение на системата зависи само от A и B, а второто уравнение от A и C. Променлива A може да приеме 2 стойности 0 и 1:

От първото уравнение следва, че , Така че, когато A = 0 получаваме B = 0, а за A = 1 имаме B = 1. И така, първото уравнение има две решения по отношение на променливите A и B.

Изчертаваме второто уравнение, от което определяме стойностите на C за всяка опция. За A =1 импликацията не може да бъде невярна, тоест вторият клон на дървото няма решение. ПриА= 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), докато X и Y е импликация, тоест е вярно в три случая и невярно в един. Следователно случаят (0;1) ще съответства на три възможни комбинации от параметри. Случай (1;1) - ще съответства на девет възможни комбинации от параметрите на първоначалното уравнение. Следователно има 3+9=15 възможни решения на това уравнение.

Следният начин за определяне на броя решения на система от логически уравнения е − двоично дърво. Нека разгледаме този метод с пример.

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

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

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

Нека се преструваме, чех 1 е вярно, тогава от първото уравнение получаваме товах 2 също вярно, от второто -х 3 =1 и така нататък, докато x m= 1. Следователно множеството (1; 1; …; 1) отм единици е решението на системата. Нека сегах 1 =0, тогава от първото уравнение имамех 2 =0 или х 2 =1.

Кога х 2 вярно, получаваме, че другите променливи също са верни, т.е. множеството (0; 1; ...; 1) е решението на системата. Прих 2 =0 получаваме това х 3 =0 или х 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  г1 )  (х2  г2 ))  (х1  х2 )  (г1  г2 ) =1

((х2  г2 )  (х3  г3 ))  (х2  х3 )  (г2  г3 ) =1

((х7  г7 )  (х8  г8 ))  (х7  х8 )  (г7  г8 ) =1

където х1 , х2 ,…, х8, при1 ,г2 ,…,y8 - Булеви променливи? Отговорът не трябва да изброява всички различни набори от стойности на променливи, за които е валидно това равенство. Като отговор трябва да посочите броя на тези комплекти.

Решение. Всички уравнения, включени в системата, са от един и същи тип и четири променливи са включени във всяко уравнение. Познавайки x1 и y1, можем да намерим всички възможни стойности на x2 и y2, които отговарят на първото уравнение. Като се аргументираме по подобен начин, от известните x2 и y2 можем да намерим x3, y3, които удовлетворяват второто уравнение. Тоест, знаейки двойката (x1, y1) и определяйки стойността на двойката (x2, y2), ние ще намерим двойката (x3, y3), което от своя страна ще доведе до двойката (x4, y4) и така На.

Нека намерим всички решения на първото уравнение. Това може да стане по два начина: да се изгради таблица на истината, чрез разсъждения и прилагане на законите на логиката.

Таблица на истината:

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

(х1  г1 )  (х2  г2 ))=1

(х1  х2 ) =1

(г1  г2 ) =1

Разгледайте първото уравнение. Следващото е равно на 1, когато 0 0, 0 1, 1 1, тогава (x1 y1)=0 при (01), (10), тогава двойката (х2  г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 Поляков К.Ю.) Колко различни решения има система от логически уравнения

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

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

...

( х 6  ( х 7  г 7 ))  ( г 6  г 7 ) = 1

х 7  г 7 = 1

Решение. 1) Уравненията са от един и същи тип, така че чрез метода на разсъждение ще намерим всички възможни двойки (x1,y1), (x2,y2) на първото уравнение.

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

(г1  г2 ) = 1

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

Нека намерим решения на първото уравнение. Ако x1=0, тогава x2 , y2 - всякакви, ако x1=1, тогава x2 , y2 приема стойността (11).

Нека направим връзки между двойки (x1, y1) и (x2, y2).

Нека направим таблица, за да изчислим броя на двойките на всеки етап.

Като се вземат предвид решенията на последното уравнение х 7  г 7 = 1, елиминираме двойката (10). Намерете общия брой решения 1+7+0+34=42

3)(23.180) Колко различни решения има системата от логически уравнения

(х1  х2 )  (х3  х4 ) = 1

(х3  х4 )  (х5  х6 ) = 1

(х5  х6 )  (х7  х8 ) = 1

(х7  х8 )  (х9  х10 ) = 1

х1  х3  х5  х7  х9 = 1

Решение. 1) Уравненията са от един и същи вид, така че чрез метода на разсъждение ще намерим всички възможни двойки (x1,x2), (x3,x4) на първото уравнение.

(х1  х2 )  (х3  х4 ) = 1

Изключваме от решението двойките, които дават 0 (1 0) по-долу, това са двойките (01, 00, 11) и (10).

Съставяне на връзки между двойки (x1,x2), (x3,x4)