Метода за решаване на системи за логически уравнения. Логика
Позволявам е логическата функция от n променливи. Логическото уравнение е:
Константа С има стойност 1 или 0.
Логическото уравнение може да има от 0 до различни решения. Ако c е равна на 1, тогава решенията са тези комплекти от променливи от таблицата за истината, на която функцията f взема стойността на истината (1). Останалите комплекти са разтвори на уравнението при С, равно на нула. Винаги можете да разгледате само уравненията на формуляра:
Всъщност оставете уравнението:
В този случай можете да отидете в еквивалентното уравнение:
Помислете за системата от K логически уравнения:
Решението на системата е набор от променливи, върху които се извършват всички уравнения на системата. По отношение на логическите функции, за получаване на решение на системата за логическо уравнение, трябва да намерите набор, на който логическата функция F е вярна, представяща връзката на функциите на източника:
Ако броят на променливите е малък, например, по-малко от 5, не е трудно да се изгради таблица за истината за функция, която ви позволява да кажете колко решения имат система и какви са множествата, които дават решения.
В някои задачи на EGE за намиране на решения на системата на логическите уравнения, броят на променливите достига до стойност 10. След това изграждане на таблица за истината става практически неподатлива задача. За да разрешите проблема, се изисква друг подход. За произволна система на уравнения няма общ метод, различен от разбиването, който ви позволява да решите такива задачи.
В предложените задачи на изпита, решението обикновено се основава на спецификата на системата на уравнения. Повтарям, освен търсенето на всички варианти на набор от променливи, няма общ начин за решаване на проблема. Решението трябва да бъде изградено въз основа на спецификата на системата. Често е полезно за предварително опростяване на системата на уравнения, използвайки добре познати логически закони. Друго полезно приемане на тази задача е следното. Ние не се интересуваме от всички комплекти, но само тези, на които функцията е важна за 1. Вместо да изграждат пълна таблица за истината, ще изградим аналога - двоични дървесни решения. Всеки клон на това дърво съответства на едно решение и задава зададената функция, на която има значение 1. Броят на клоновете в дървово дърво съвпада с броя на решенията на уравнението.
Какво е дворно дърво и как се изгражда, обяснявайте при примерите за няколко задачи.
Задача 18.
Колко различни комплекта стойности на логически променливи X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, които отговарят на системата от две уравнения?
Отговор: Системата има 36 различни решения.
Решение: Системата на уравненията включва две уравнения. Ние намираме броя на решенията за първото уравнение, зависещо от 5 променливи. Първото уравнение може на свой ред да разгледа като система от 5 уравнения. Както е показано, системата на уравненията всъщност представлява връзката с логически функции. Обратното изявление също е вярно, връзката на условията може да се разглежда като система от уравнения.
Ние изграждаме черупките за импликация () - първият член на връзката, който може да се счита за първото уравнение. Ето как изглежда графичният образ на това дърво
Дървото се състои от две нива по брой на уравнения променливи. Първото ниво описва първата променлива. Двата клона на това ниво отразяват възможните стойности на тази променлива - 1 и 0. На второ ниво на клона на дървото, само тези възможни променливи стойности отразяват, за които уравнението взема стойността на истината. Тъй като уравнението определя влиянието, клонът, на който става 1, изисква стойността на 1. клонът, на който има 0, генерира два клона със стойности, равни на 0 и 1. Изграденото дърво поставя три решения Кое импликация има стойност 1. На всеки клон, подходящ набор от променливи стойности, които придават на разтвора на уравнението, се разрежда.
Това са тези комплекти: ((1, 1), (0, 1), (0, 0))
Ще продължим да изграждаме едно дърво, като добавим следното уравнение към следното отражение. Спецификата на нашата система от уравнения са, че всяко ново уравнение на системата използва една променлива от предишното уравнение, добавяйки една нова променлива. Тъй като променливата вече има стойности на дърво, на всички клонове, където променливата е 1, променливата ще има и стойност 1. за такива клонове, изграждането на дърво продължава до следващото ниво, но новите клонове правят не се появява. Единственият клон, в който променливата е 0, ще даде разклоняване на два клона, където променливата ще получи стойността 0 и 1. Така всяка добавка на ново уравнение, като се има предвид неговата специфичност, добавя едно решение. Източник първо уравнение:
има 6 решения. Ето какво изглежда пълното дърво на решенията за това уравнение:
Второто уравнение на нашата система е подобно на първия:
Единствената разлика е, че уравненията използват променливи y. Това уравнение има и 6 решения. Тъй като всяко решение за променливи може да се комбинира с всяко решение за променливи, общият брой на разтворите е равен на 36.
ЗАБЕЛЕЖКА, Изградените решения дървото дава не само броя на решенията (по броя на клоновете), но и решенията, които сами са освободени от всеки клон на дървото.
Задача 19.
Колко различни комплекта стойности на логически променливи X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, които отговарят на всички условия, изброени по-долу?
Тази задача е промяна на предишната задача. Разликата е, че се добавя друго уравнение, свързващо променливите X и Y. обаче.
От уравнението следва, че когато има стойност от 1 (едно такова решение съществува), то има значение 1. По този начин има един набор, на който стойностите 1. при равни на 0 могат да имат всяка стойност като 0 , така и 1. Следователно всеки комплект с равен на 0 и такива комплекти 5 съответства на всичките 6 комплекта с променлива y. Следователно общият брой на разтворите е равен на 31.
Задача 20.
Решение: запомняне на основната еквивалентност, напишете нашето уравнение във формата:
Цикличната верига на последиците означава идентичност на променливите, така че нашето уравнение е еквивалентно на уравнението:
Това уравнение има две решения, когато всички са равни на 1 или 0.
Задача 21.
Колко решения имат уравнение:
Решение: точно както в проблема 20, ние продължаваме с циклични последици за идентичността, пренаписват уравнението във формата:
Ние изграждаме дърво за това уравнение:
Задача 22.
Колко решения имат следната система на уравнения?
Решаване на система от логически уравнения чрез замяна на променливи
Методът за смяна на променливата се използва, ако някои променливи са включени в уравненията само като специфичен израз, и по никакъв начин по различен начин. Тогава този израз може да бъде обозначен с нова променлива.
Пример 1.
Колко различни комплекта стойности на логически променливи X1, X2, X3, X4, X5, X6, X7, X8, които отговарят на всички посочени по-долу условия?
(x1 → x2) → (x3 → x4) \u003d 1
(x3 → x4) → (x5 → x6) \u003d 1
(x5 → x6) → (x7 → x8) \u003d 1
В отговор не е необходимо да изброявате всички различни набори от стойности на променливите X1, X2, X3, X4, X5, X6, X7, X8, при които се извършва тази система от равенства. Като отговор трябва да посочите броя на тези комплекти.
Решение:
(x1 → x2) \u003d y1; (x3 → x4) \u003d Y2; (x5 → x6) \u003d y3; (x7 → x8) \u003d y4.
След това можете да напишете системата под формата на едно уравнение:
(Y1 → Y2) ∧ (Y2 → Y3) ∧ (Y3 → Y4) \u003d 1. Съединението е 1 (вярно), когато всеки операнд приема стойност 1. тези. Всяко от последиците трябва да е вярно и това се извършва на всички стойности, с изключение на (1 → 0). Тези. В таблицата на стойностите на променливите Y1, Y2, Y3, Y4, устройството не трябва да стои наляво от лявата страна на нула:
Тези. Условия се извършват за 5 комплекта Y1-Y4.
Като Y1 \u003d x1 → x2, след това стойността y1 \u003d 0 се постига на един комплект X1, x2: (1, 0) и стойността y1 \u003d 1 - на три комплекта X1, x2: (0,0), (0) , 1), (1,1). Подобно на Y2, Y3, Y4.
Тъй като всеки комплект (x1, x2) за променлива Y1 се комбинира с всеки комплект (x3, x4) за променлива Y2 и т.н., броят на комплектите променливи X се умножава:
|
Брой комплекти на x1 ... x8 |
||||
Преместване на броя на комплекти: 1 + 3 + 9 + 27 + 81 \u003d 121.
Отговор: 121
Пример 2.
Колко различни комплекта логически променливи X1, X2, ... X9, Y1, Y2, ... Y9, които отговарят на всички посочени по-долу условия?
(¬ (x1 y1)) ≡ (x2 y y2)
(¬ (x2 y2)) ≡ (x3 y y3)
(¬ (x8 y y8)) ≡ (x9 y y9)
В отговор не е задължителноизбройте всички различни комплекти от стойности на променливи X1, X2, ... X9, Y1, Y2, ... Y9, при които се прави тази система от равенства. Като отговор трябва да посочите броя на тези комплекти.
Решение:
Ще заменим променливите:
(x1 y1) \u003d z1, (x2 y2) \u003d z2, .... , (x9 y9) \u003d z9
Системата може да бъде написана като едно уравнение:
(¬ z1 ≡ Z2) ∧ (¬ z2 z3) ∧ ... ..∧ (¬ z8 z9)
Еквивалентността е вярна само ако и двете операнди са равни. Решенията на това уравнение ще бъдат два комплекта:
| z1. | z2. | z3. | z4. | z5. | z6. | z7. | z8. | z9. |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Като Zi \u003d (xi ≡ yi), след това стойността zi \u003d 0 съответства на два комплекта (xi, yi): (0.1) и (1.0) и стойността zi \u003d 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 \u003d 1024 комплекта.
Отговор:1024
Решаване на система от логически уравнения по метода на визуално определяне на рекурсията.
Този метод се използва, ако системата на уравненията е доста проста и реда за увеличаване на броя на комплектите при добавянето на променливи е очевидно.
Пример 3.
Колко различни решения има система от уравнения
¬x9 ∨ x10 \u003d 1,
където x1, x2, ... x10 - логически променливи?
В отговор не е необходимо да изброявате всички различни групи стойности x1, x2, ... x10, на която се прави тази система от равенства. Като отговор трябва да посочите броя на тези комплекти.
Решение:
Изпълнява първото уравнение. Диспергирането е 1, ако поне един от операндите е 1. тези. Решенията са комплекти:
За X1 \u003d 0 има две стойности X2 (0 и 1) и за X1 \u003d 1, само една стойност X2 (1), така че комплектът (X1, X2) е разтвор на уравнението. Общо 3 комплекта.
Добавете променлива x3 и помислете за второто уравнение. Той е подобен на първия, това означава за x2 \u003d 0 има две стойности x3 (0 и 1) и за x2 \u003d 1, само една стойност x3 (1), така че комплектът x2, x3) е решение на уравнението. Общо 4 комплекта.
Лесно е да забележите, че при добавяне на друга променлива се добавя един комплект. Тези. Рекурсивна формула за броя на настройките (I + 1) променливи:
N i +1 \u003d n i + 1. след това за десет променливи, получаваме 11 комплекта.
Отговор: 11
Решаване на системи за логически уравнения на различни видове
Пример 4.
Колко различни комплекта стойности на логически променливи х 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, които отговарят на всички посочени по-долу условия?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) \u003d 1
(Y 1 → Y2) ∧ (Y 2 → Y 3) ∧ (Y 3 → Y 4) \u003d 1
(z 1 → z2) ∧ (z2 → z 3) ∧ (z 3 → z 4) \u003d 1
x 4 ∧ y 4 z 4 \u003d 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 \u003d 0. Разтворът ще бъде всички комплекти X4, Y4, Z4, в който поне една от променливите е 0.
Тези. За X4 \u003d 0 всички възможни комплекти (Y4, Z4) са подходящи и за X4 \u003d 1, комплекти (Y4, Z4) са подходящи, в които има най-малко една нула: (0, 0), (0,1 ), (1, 0).
|
Брой комплекти |
||||
Общият брой на комплекти 25 + 4 * 9 \u003d 25 + 36 \u003d 61.
Отговор: 61
Решаване на системи от логически уравнения по метода на конструиране на повтарящи се формули
Методът за изграждане на повтарящи се формули се използва в решаването на сложни системи, в които редът за увеличаване на броя на комплектите не е очевиден и конструкцията на дървото е невъзможна поради обемите.
Пример 5.
Колко различни комплекта логически променливи X1, X2, ... X7, Y1, Y2, ... X7, Y1, Y2, ... Y7, които отговарят на всички посочени по-долу условия?
(x1 y1) ∧ ((x2 y2) → (x1 y1)) \u003d 1
(x2 y2) ∧ ((x3 y3) → (x2 y y2)) \u003d 1
(x6 ∨ y6) ∧ ((x7 y7) → (x6 y6)) \u003d 1
Отговорът не трябва да посочва всички различни комплекти от променливите X1, X2, ..., X7, Y1, Y2, ..., X7, Y1, Y2, ..., Y7, при което Тази система от равенства се прави. Като отговор трябва да посочите броя на тези комплекти.
Решение:
Обърнете внимание, че първите шест уравнения са еднакви и се различават само в набор от променливи. Разгледайте първото уравнение. Неговото решение ще бъде следните набори от променливи:
Обозначаваме:
броя на комплектите (0.0) върху променливите (X1, Y1) през 1,
брой набори (0.1) на променливи (X1, Y1) чрез B 1,
броя на комплектите (1.0) върху променливите (X1, Y1) до C 1,
броят на комплектите (1.1) върху променливите (X1, Y1) до D1.
броя на комплектите (0.0) върху променливите (X2, Y2) през 2,
брой набори (0.1) на променливи (X2, Y2) чрез B 2,
брой набори (1.0) на променливи (X2, Y2) до C 2,
броят на комплектите (1.1) върху променливите (X2, Y2) до D2.
От дървесни решения виж това
A 1 \u003d 0, b 1 \u003d 1, c 1 \u003d 1, d 1 \u003d 1.
Обърнете внимание, че наборът (0.0) върху променливите (X2, Y2) се получава от комплектите (0.1), (1.0) и (1,1) върху променливите (X1, Y1). Тези. 2 \u003d B 1 + C 1 + D1.
Комплектът (0.1) върху променливите (X2, Y2) се получава от множествата (0.1), (1.0) и (1,1) върху променливите (X1, Y1). Тези. B 2 \u003d B 1 + C 1 + D1.
По същия начин, твърдейки, ние отбелязваме, че с 2 \u003d B 1 + C 1 + d1. D2 \u003d d 1.
Така получаваме повтарящи се формули:
A i + 1 \u003d b i + c i + d i
B i + 1 \u003d b i + c i + d i
C I + 1 \u003d B I + C I + D I
D i + 1 \u003d a i + b i + c i + d i
Направете таблица
| Комплекти | Собствен. | Формула |
Брой комплекти |
||||||
| i \u003d 1. | i \u003d 2. | i \u003d 3. | i \u003d 4. | i \u003d 5. | i \u003d 6. | i \u003d 7. | |||
| (0,0) | А I. | A i + 1 \u003d b i + c i + d i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | Б Г. | B i + 1 \u003d b i + c i + d i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C I. | C I + 1 \u003d B I + C I + D I | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D I. | D i + 1 \u003d d i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Последното уравнение (x7 y7) \u003d 1 удовлетворява всички комплекти, с изключение на тези, в които x7 \u003d 0 и y7 \u003d 0. Нашата маса е броят на тези комплекти A 7.
След това общият брой на комплекти е B 7 + C 7 + D 7 \u003d 127 + 127 + 1 \u003d 255
Отговор: 255
UDC 004.023.
Семенов Сергей Максимович
Владивосток Държавен университет по икономика и обслужване Русия. Владивосток.
Относно един метод за решаване на системи за логически уравнения
Разглежда се метод за определяне на броя на решенията на системата на логически уравнения. Методът се основава на изграждането на дървесни решения и определяне на повтарящи се съотношения за N. Прилагането на разработения метод осигурява конструктивен подход за решаване на проблема с B15 EGE.
Ключови думи и фрази: система от логически уравнения, дървени решения, повтарящи се отношения, B15, EGE.
На практика системата на логическите уравнения е полезна при разработването на цифрови логически устройства. Една от задачите на EGE на компютърната наука е посветена на решаването на системи за логически уравнения. За съжаление, различни известни начини за решаване на този проблем не позволяват да се формира един подход за решаване на тази задача. В резултат на това решаването на проблема причинява големи трудности за завършилите. Ние предлагаме начин за решаване на системи за логически уравнения, което позволява завършил да следва добре дефиниран алгоритъм. Идеята за този метод е изложена в. Приложихме и разработихме тази идея (изграждане на решения за дърво), почти използвайки масите за истината за цялото дърво. Когато решават различни проблеми, се оказа, че броят на решенията на много системи на логически уравнения е предмет на повтарящи се съотношения, като Fibonacci и др.
Системи за логически уравнения. Ще се придържаме към следните наименования: disjunction (+), комбинация (), с изключение или (©), импликация (-\u003e ■), еквивалентност (\u003d), отказ (- ■). На фигурите тъмният кръг означава 1, а лекият кръг е 0. fl - броя на разтворите при X1, равен на 1. fo - броя на разтворите при X1, равен на 0. N - броя на променливите в системата за уравнение. F (n) \u003d f1 (n) + f0 (n) е общият брой на решенията.
Задача 1. Необходимо е да се намери броя на решенията на системата на уравнения (, тест номер 2)
Първо приемаме X1 \u003d 1. След това за първото уравнение стойностите на x2 и X могат да бъдат всички. Така дървото е изградено до третото ниво. След това се вземат предвид X2 и XS, изберете X4. След това алгоритъмът се повтаря за всяка тройна променлива (фиг. 1). Започвайки от четвъртото ниво, може да се отбележи, че FL (4) \u003d FL (3) + FL (1), FL (5) \u003d FL (4) + FL (2). Така получаваме fl (n) \u003d fl (n - 1) + fl (n-3) (1)
Фиг. 1. Задача 1.
От уравнение (1) следва: \\ t
BH (8) \u003d 16 + 7 \u003d 23,
FL (9) \u003d 23 + 11 \u003d 34.
За да построите дърво от нула, можете да използвате долния клон от фиг. 1. Лесно е да се види, че то повтаря основното дърво, но с промяна вдясно до 2, т.е.
Общо, F (9) \u003d FL (9) + FO (9) \u003d 34 + 16 \u003d 50.
Когато изграждате дървесни решения, можете да установите визуално повтарящи се отношения, за да определите броя на решенията в N.
Принципът на математическата индукция гласи: Нека има последователност от FL, F2, FD твърдения и да оставите първото изявление правилно. Можем да докажем, че фантазията на декларацията на FN следва верността на FN + L. Тогава всички изявления в тази последователност са верни.
Помислете за фиг. 2 за задача 1.
k2\u003e 3 x5 HB x7
Фиг. 2. Анализ на дървото на решенията
Фигура 2 показва формите, които имат общ връх (комбинации от променливи стойности) за първите пет уравнения на системата. Във всяко уравнение участват три променливи, така че цифрите се компилират от стойностите на три променливи (три нива на дърво). За да се идентифицират цифрите, би било възможно да се въведе нотация. Въпреки това, ние ще продължим по следния начин: всяка фигура се поставя в съответствие с броя на компонентите на неговите кръгове (променливи стойности). След това получаваме следните уравнения за последователността:
4. 7, 4, 4, 1, 7
5. 7, 4, 4, 1, 7, 7, 4.
От уравнение 4 може да се види, че цифрите за уравнението n се състоят от фигурите на N-1 уравнението и цифрите на N-3 уравнението. Важно е да няма други фигури и не могат да бъдат за този вид уравнения, т.е. преходът от едно уравнение в друг се произвежда чрез увеличаване на броя на цифрите от ограничен набор според строго определени правила. Този факт е основен, за да се твърди, че за уравнение N + 1 набор от фигури ще се състои от фигури от уравнението N и цифрите на N-2 уравнението.
Друг начин за идентифициране на цифрите е да се определи броят на стойностите на променливите на последното ниво за това уравнение, т.е. трябва да отидете от броя на уравнението на номера на нивото на дървото, тъй като трябва да определим Брой на решенията за системата на уравнения, след това за конструираното дърво получаваме последователност: 1, 2, 4, 5, 7, 11, 16. За тази последователност формулата е валидна: fn \u003d fn - 1 + fn- 3.
В съответствие с нашите аргументи, тази формула ще бъде вярна за n + 1 и в индукция и за всеки Н.
Посоченият метод на доказване може да се използва за всякакви системи от този тип. На практика е достатъчно да се определи повтарящото съотношение за ниво N, тъй като се основава на ограничен набор от цифри и методи за тяхното преобразуване по време на прехода от уравнението, съответстващо на нивото N към уравнението, съответстващо на N + 1 ниво.
Задача 2. Необходимо е да се намери броя на решенията на системата на уравнения (4.16)
(X1 \u003d x2) + (x1 \u003d x3) \u003d 1 (x2 \u003d XS) + (x2 \u003d x4) \u003d 1 (XS \u003d x4) + (XS \u003d x5) \u003d 1 (x4 \u003d x5) + (x4 \u003d x6) \u003d 1 (x5 \u003d x6) + (x5 \u003d x7) \u003d 1
XI X2 XS\u003e: 1 x5 HB x7
Фиг. 3. Задача 2.
За да се получи броя на решенията на задачата 2, е възможно да не се изграждат напълно дървото на решенията (фиг. 3), тъй като е очевидно, че fl (n) \u003d N. също така, fo (n) \u003d n. общо f (7) \u003d 7 + 7 \u003d четиринадесет.
Задача 3. Необходимо е да се намери броя на решенията на системата на уравнения (, тест номер 1)
(X1 ^ x2) ■ (x2 ^ Xs) ■ (XS ^ x4) ■ (x4 ^ x5) \u003d 1
(Yl ^ y2) ■ (U2 ^ yz) ■ (yz ^ y4) ■ (Y4 ^ y5) \u003d 1
(Yl ^ x1) ■ (U2 ^ x2) ■ (yz ^ xs) ■ (Y4 ^ x4) ■ (Y5 ^ x5) \u003d 1
Фигура 4 показва дърветата на разтворите за X и Y и се показват съответните таблици за истината.
Фиг. 4. Задача 3.
От първите две уравнения, тъй като X и Y са независими, следва, че общият брой на разтворите F (5) \u003d 6 * 6 \u003d 36. За да се вземе предвид третото уравнение, е необходимо да се изчисли за всяка променлива Y, \\ t Кой брой набори от таблица X не отговаря на уравнението. Импликирането на Yi ^ xi \u003d 0, ако yi \u003d 1 и xi \u003d 0. с други думи, за YL \u003d 1, третото уравнение не отговаря на всички линии от таблицата X, където X1 \u003d 0. Броят на Такива струни са 5. за Y2 \u003d 1 редове - 4 и др. Общият брой на линиите, които не отговарят на третото уравнение, е равно на 5 + 4 + 3 + 2 + 1 \u003d 15.
По този начин общият брой на допустимите решения е равен на 36 - 15 \u003d 21. Задача 4. Необходимо е да се намери броя на решенията на системата на уравнения (4.17.а)
(X1 \u003d x2) + (x1 \u003d x3) \u003d (x2 \u003d x3) + (x2 \u003d x4) \u003d (x4 \u003d x5) + (x4 \u003d x6) \u003d (x5 \u003d x6) + (x5 \u003d x7) \u003d (HB \u003d X7) + (HB \u003d x8) \u003d (x5 \u003d x6) \u003d 0
Фиг. 5. Задача 4.
За този пример е трудно да се определи последната формула F (n), по-лесно е да се изградят дърво на решенията до края (или поне до х6). Фигура 5 показва изградените дърво. В резултат на това получаваме F (8) \u003d FL (8) + FO (8) \u003d 5 + 5 \u003d 10.
Задача 5. Необходимо е да се намери броя на решенията на системата на уравнения (4.17.b)
(X1 \u003d x2) + (x1 \u003d x3) \u003d 1 (x2 \u003d x3) + (x2 \u003d x4) \u003d 1 (x3 \u003d x4) + (x3 \u003d x5) \u003d 1 (x4 \u003d x5) + (x4 \u003d x6) \u003d 1 (x5 \u003d x6) + (x5 \u003d x7) \u003d 1 (x6 \u003d x8) \u003d 1
За този пример, както за предишния, е по-лесно да се изграждат дървесни решения до края (фиг. 6). В резултат на това получаваме F (8) \u003d FL (8) + FO (8) \u003d 7 + 7 \u003d 14.
Задача 6. Необходимо е да се намери броя на решенията на уравнението (!]\u003e 4.17.V)
(X! 8 "x2) + (x2Hz) \u003d 1 (x2fx) + (xs \u003d x4) \u003d 1 (XS8" x4) + (x4 \u003d x5) \u003d 1 (x4 © x5) + (x5 \u003d hB) \u003d 1 (X5FHB) + (HB \u003d X7) \u003d 1 (HB © X7) + (x7 \u003d x8) \u003d 1 Дървото на разтворите е показано на фиг. 7.
XI X2 XS X4 x5 x6 x7 x8 xi x2 XS x4 x5 x6 x7 x8
Фиг. 6. Задача 5 Фиг. 7. Задача 6.
За тази система на уравнения не беше възможно да се изградят цялостно дърво, тъй като вече от третата четвърта стъпка е ясно, че F1 (N) \u003d N. Лесно е да се види, че FO (n) може да бъде получено от дърво, започващо на второ ниво от нула. След това fo (n) \u003d n. Общо, f (8) \u003d fl (8) + fo (8) \u003d 8 + 8 \u003d 16.
Задача 7. Трябва да намерите броя на решенията на системата на уравнения
(X4H5) + (x4 © X6) \u003d 1 (x5 © HB) + (x5 © x7) \u003d 1
Обърнете внимание, че ако x! \u003d X2 \u003d 1, първото уравнение се извършва при Xs \u003d 0. Първо ще изградим дърво за xl \u003d x2 \u003d 1 (фиг. 8). След това броят на разтворите fl (n) \u003d fll (n) + flo (n).
Xi x2 xs x4 x5 x6 x7 x8
Фиг. 8. Задача 7.
От Фигура 8 може да се види, че броят на разтворите F11 (N) \u003d F11 (N- 1) + F11 (N-2). С други думи, броят на решенията е описан от цифрите на FibonAcci. Второто дърво за F10 не може да бъде изградено, тъй като се оказва от фиг. 1, започвайки от второто ниво. След това F10 (n) \u003d F11 (n + 1). Най-накрая получаваме, че FLL (8) \u003d 1Z и Flo (8) \u003d FLL (9) \u003d 1Z + 8 \u003d 21. След това fl (8) \u003d FLL (8) + Flo (8) \u003d 1Z + 21 \u003d C4.
За да се получи F0 (n), също така не е необходимо да се изграждат дървото на решенията, тъй като е получено от фиг. 1, започвайки от третото ниво. След това fo (n) \u003d FLL (n + 2). От тук получаваме това за (8) \u003d FLL (10) \u003d FLL (9) + FLL (8) \u003d 21 + 1Z \u003d С4. По този начин общият брой на разтворите F (8) \u003d F1 (8) + F0 (8) \u003d Z4 + Z4 \u003d 68.
Задача 8. Необходимо е да се намери броя на решенията на системата на уравнения ([и], задача 2)
(X1 + x2) ^ (XS + x4) \u003d 1 (XS + x4) ^ (x5 + x6) \u003d 1 (x5 + x6) ^ (x7 + x8) \u003d 1 (x7 + x8) ^ (x9 + x10) \u003d 1.
Направете заместване (X1 + x2) \u003d YL и т.н. И получаваме системата на уравнения:
^ ^ Y2 \u003d 1 y2 ^ yz \u003d 1 yz ^ y4 \u003d 1 y4 ^ y5 \u003d 1
Дървото на решенията и таблицата за истината за тази система са точно съвпадащи с дървото и масата, показана на фиг. 4. Като се има предвид заместването, отбелязваме, че експресията (X1 + X2) е равна на една в три случая (с изключение на опцията, когато двете променливи са нулеви).
Тъй като променливите y са независими, след това за първия ред на таблицата с истината, показана на фиг. 4, броят на различните комбинации е 35, за втория ред - 34 и др. Общият брой на различните комбинации е 35 + 34 + 33 + 32 + 31 + 30 \u003d 364.
Задача 9. Необходимо е да се намери броя на решенията на системата на уравнения (, задача 4)
(^ ^) ■ (-X ^ x) ■ № ^ x) ■ (-X ^ kz) \u003d 1 no. ^ y2) ■ (u1 ^ yz) ■ (-g1 ^ y4) ■ (U1 ^ y5) \u003d 1 (-X + Y 1) ■ (-X + Y5) \u003d 1
За x и y имаме следните дървета на решения
Фиг. 9. Задача 8.
Като се вземат предвид третото уравнение, ние получаваме следните четири комплекта комбинации:
A - C: 4 * 4 \u003d 16 ((- £ 1 + y 1) ■ (-x + y5) \u003d (0 + 1) ■ (0 + 1) \u003d 1) В - С: 4 * 4 \u003d 16 ( (-X + Y 1) ■ (-X + Y5) \u003d (1 + 1) ■ (1 + 1) \u003d 1) a - d: \u003d 0 (0 + 0) ■ (-X + y5) \u003d 0) B - D: 4 * 4 \u003d 16 (1 + 0) ■ (1 + y5) \u003d 1) Общо е 48 комплекта разтвори.
Задача 10. Необходимо е да се намери броя на решенията на системата на уравнения (^ 1 \u003d b) + (xz \u003d x)) ■ \u003d ъ) + -fz \u003d x4)) \u003d 1 ((x3 x4) + ( x5 \u003d x6)) ■ (- (x \u003d x) + - (x \u003d x6)) \u003d 1 ((x5 \u003d x6) + ^ 7 \u003d x ")) ■ (- (x \u003d x6) + - (^ 7) \u003d x8)) \u003d 1
((X7 \u003d x8) + (x9 \u003d xlo)) ■ (- ^ 7 \u003d x8) + \u003d xlo)) \u003d 1 Ще сменим: (xl \u003d b) \u003d yl (xz \u003d x4) \u003d y2
(X5 \u003d x) \u003d yz (x7 \u003d x8) \u003d y4 (x9 \u003d x10) \u003d y5
(Y ^ 2) ■ (- + ^) \u003d 1
(Y2 + YZ) ■ № + -tz) \u003d 1
(Yz + y4) ■ № + ^) \u003d 1
(Y4 + Y5) ■ (^ 4 + ^) \u003d 1
Фигура 10 показва дървото на решенията
U1 U2 UZ U4 U5
Фиг. 10. Задача 10.
Задача 11. Необходимо е да се намери броя на решенията на системата на уравнения (Пример 2)
X1 + x2 \u003d 1 -х2 + xs \u003d 1
Фигура 11 показва дървото на решенията. Ние ограничихме до четирите нива вместо десет, тъй като е очевидно, че F1 (n) \u003d 1 и f0 (n) \u003d n. след това p (s) \u003d p1 (s) + bosi) \u003d 1 + n. в нашия случай p (10) \u003d 1 + 10 \u003d 11.
Фиг. 11. Задача 11.
Задача 12. Необходимо е да се намери броя на решенията на системата на уравнения (, например Н)
(X1 \u003d x2) + (x2 \u003d xs) \u003d 1
(X1 \u003d XS) + (XS \u003d X4) (x1 \u003d x4) + (x4 \u003d x5) (x1 \u003d x5) + (x5 \u003d x6) (x1 \u003d x6) + (x6 \u003d x7) (x1 \u003d x7) + (X7 \u003d x8) (x1 \u003d x) + (x8 \u003d x9) (x1 \u003d x9) + (x9 \u003d x10) (x1 \u003d x10) \u003d 0
Фиг. 12. Задача 12.
Чрез изграждането на решенията от "1" (лимит до пет нива), отбелязваме, че FL (N) \u003d N. и стойностите на HN се състоят от N-1 "0" стойности и една стойност "1 ". Въпреки това, последното уравнение в нашата система забранява стойността "1" за X10. Следователно, броят на решенията FL (10) \u003d 10 - 1. Не е трудно да се отбележи, че дървото на решенията от "0" ще бъде симетрично (вместо нули ще бъдат единици). Следователно, F0 \u003d 10 - 1. Накрая
F (n) \u003d 2 x 9 \u003d 18.
Задача 13. Необходимо е да се намери броя на решенията на системата на уравнения (, Пример 4)
- (x1 \u003d x2) + (xs \u003d x4) \u003d 1
- (XS \u003d x4) + (x5 \u003d x) \u003d 1
- (x \u003d x) + (x7 \u003d x) \u003d 1
- (x7 \u003d x8) + (x9 \u003d x10) \u003d 1
Ще заменим:
(X1 \u003d x2) \u003d ил
(X5 \u003d x) \u003d yz
(X7 \u003d x8) \u003d y4
(X9 \u003d x10) \u003d y5
Пренаписваме система от уравнения със замяна:
От задача 11 може да се види, че f (5) \u003d 5 + 1 \u003d 6. Таблицата за истината е представена на фиг. 13.
U1 U2 UZ U4 U5
Фиг. 13. Задача 13.
Като се има предвид заместването, отбелязваме, че експресията ^ \u003d x2) е равна на една (или нула) в два случая (когато стойностите на променливите съвпадат). Като се вземат предвид независимостта на променливите за всеки ред от таблицата, ние получаваме, че броят на наборите за разтвори е 25 \u003d 32. Общият брой на комплектите решения е 6 * 32 \u003d 192.
Задача 14. Необходимо е да се намери броя на решенията на системата на уравнения (, задача 1)
((X \u003d ъ) ■ (xz \u003d x4)) + (4x1 \u003d an) ■ - (x \u003d x)) \u003d 0 ((xz \u003d x4) ■ (x5 \u003d x6)) + (4x3 \u003d x4) ■ - (X \u003d x6)) \u003d 0
((X5 \u003d x) ■ (x7 \u003d x8)) + (- (x \u003d x6) ■ 4x7 \u003d x8)) \u003d 0 (((x7 \u003d x8) ■ (x9 \u003d x ",)) + (- (^ 7 \u003d x8) ■ ^ 9 \u003d xlo)) \u003d 0 Ние ще заменим:
Комерсант) \u003d Yl (x \u003d ^ 4) \u003d y2
(X5 \u003d x6) \u003d yz ^ 7 \u003d x8) \u003d y4 ^ 9 \u003d xlo) \u003d y5
Пренаписваме система от уравнения със замяна:
(UL) + (-U "■ -U2) \u003d 0
(Y2 yz) + (-U2 ■ -U3) \u003d 0 (U3-U4) + (-U3 ■ -U4) \u003d 0 (U4-U5) + (-U4 ■ -U5) \u003d 0
(U2 \u003d yz) \u003d 0 (uz \u003d u4) \u003d 0 (u4 \u003d u5) \u003d 0
Фигура 14 показва дървото на решенията
U1 U2 UZ U4 U5
Фиг. 14. Задача 14.
Като се има предвид заместването, отбелязваме, че експресията (x1 \u003d x2) е равна на една (или нула) в два случая (когато стойностите на променливите съвпадат). Като се вземат предвид независимостта на променливите за всяко дърво, ние получаваме, че броят на наборите за решения е 25 \u003d З2. Общият брой на решенията е 64.
Задача 15. Необходимо е да се намери броя на решенията на системата на уравненията (, задача 2)
(X4 x5) + (-Н4 -х5) + (x4 \u003d x) \u003d 1
(X5 x) + (-х -х6) + (x5 \u003d x7) \u003d 1
(X x7) + (-х -х7) + (x \u003d x8) \u003d 1
(X7 x) + (-х7 -х8) + (x7 \u003d x9) \u003d 1
(X8 x9) + (-х -х9) + (x8 \u003d x10) \u003d 1
(X1 \u003d x2) + (x1 \u003d xs) \u003d 1
(X \u003d xs) + (x2 \u003d x4) \u003d 1
(Xs \u003d x4) + (xs \u003d x5) \u003d 1
(X4 \u003d x5) + (x4 \u003d x) \u003d 1
(X5 \u003d x6) + (x5 \u003d x7) \u003d 1
(X \u003d x7) + (x6 \u003d x8) \u003d 1
(X7 \u003d x8) + (x7 \u003d x9) \u003d 1
(X \u003d x9) + (x8 \u003d x10) \u003d 1
Но тази система повтаря системата от задача 5, само без граничното състояние за n \u003d 10. след това броят на разтворите е f (n) \u003d f1 (n) + f0 (n) \u003d n + n. При n \u003d 10 Получаваме F (n) \u003d 20.
Задача 16. Необходимо е да се намери броя на решенията на системата на уравненията (, задача 3)
(X1 x2) + (-х1 -х2) + (x1 \u003d xs) \u003d 1
(X2 xs) + (-m -kHz) + (x2 \u003d x4) \u003d 1
(XS X4) + (-KHz -х4) + (XS \u003d X5) \u003d 1
(X4 x5) + (-х -х5) + (x4 \u003d HB) \u003d 1
(X5 HB) + (-H-CHB) + (x5 \u003d x7) \u003d 1
(HB X7) + (-CHB -х7) + (HB \u003d X8) \u003d 1
(X7 x8) + (-х7 -х8) + (x7 \u003d x9) \u003d 1
(X8 x9) + (-х8 -х9) + (x8 \u003d x10) \u003d 0
Тази система на уравнения, както в предишната задача, може да бъде пренаписана като:
(Xi \u003d x2) + (xi \u003d xs) \u003d 1 (x \u003d xs) + (x2 \u003d x) \u003d 1 (xs \u003d x) + (xs \u003d x5) \u003d 1 (x \u003d x5) + (x4 \u003d HB) \u003d 1 (x5 \u003d HB) + (x5 \u003d x7) \u003d 1 (HB \u003d x7) + (HB \u003d x8) \u003d 1 (x \u003d x8) + (x7 \u003d x9) \u003d 1 (x \u003d x9) + (x8 \u003d) Xx) \u003d 0
От последното уравнение е лесно да се провери дали след n \u003d 8 броят на решенията престава да се увеличава. След това F (10) \u003d F (8) \u003d 8 + 8 \u003d 16.
Задача 17. Необходимо е да се намери броя на решенията на уравнението (, задача 4)
(X1 x2) + (-х1 -х2) + (x2 xs) + (-х2 -kHz) \u003d 1
(X2 xs) + (-х2 -kHz) + (xs x) + (-kHz ■ -х4) \u003d 1
(XS X) + (-KHz -х4) + (x4 x5) + (-х4 -х5) \u003d 1
(X4 x) + (-X5) + (x5 HB) + (-H5-cHB) \u003d 1
(X5 HB) + (-H-CHB) + (HB X7) + (-CHB ■ -х7) \u003d 1
(HB X7) + (-KHB -х7) + (x7 x8) + (-х7 -х8) \u003d 1
(X7 x) + (-х7 -х8) + (x8 x9) + (-х8 -х9) \u003d 1
(X8 x9) + (-х8 -х9) + (x9 x10) + (-х9 ■ -х10) \u003d 1
Имайте предвид, че системата на уравненията може да бъде пренаписана като:
(X \u003d x2) + (x \u003d xs) \u003d 1 (x \u003d xs) + (x \u003d x) \u003d 1 (xs \u003d x4) + (x4 \u003d x5) \u003d 1 (x \u003d x5) + (x5 \u003d HB) \u003d 1 (x5 \u003d HB) + (HB \u003d x7) \u003d 1
(HB \u003d x7) + (x7 \u003d x) \u003d 1 (x7 \u003d x8) + (x8 \u003d x9) \u003d 1 (x9 \u003d x 9) + (x9 \u003d x10) \u003d 1
На фигура 15 дървото е изградено до петото ниво и може да се види, че броят на разтворите е описан от числата на Фибоначи, т.е. FL (N) \u003d FL (N- 1) + FL (N-2) ). След това fl (10) \u003d 89. Лесно е да се провери дали за F0 (n) дървото ще бъде симетрично. Следователно, FO (10) \u003d 89.b (10) \u003d P1 (10) + PO (10) \u003d 89 + 89 \u003d 178.
Фиг. 15. Задача 17.
Задача 18. Необходимо е да се намери броя на решенията на системата на уравнения (, задача 5)
(X1 x2) + (-х1 -х2) + (x2 xs) + (-х2 ■ -kHz) \u003d 1
(X2 XS) + (-H -KHz) + (XS X4) + (-KHz -х4) \u003d 1
(XS X4) + (-kHz -х4) + (x4 x5) + (-х4 ■ -х5) \u003d 1
(X4 x5) + (-х4 -х5) + (x HB) + (-х5 ■ -HB) \u003d 1
(X5 HB) + (-H5 -HB) + (HB X7) + (-KB ■ -х7) \u003d 1
(HB X7) + (-HB -H7) + (x7 x8) + (-х7 ■ -х8) \u003d 1
(X7 x8) + (-х7 -х8) + (x8 x9) + (-х8 -х9) \u003d 1
(X8 x9) + (-х8 -х9) + (x9 x10) + (-х9 ■ -х10) \u003d 0
Имайте предвид, че системата на уравненията може да бъде пренаписана като:
(X \u003d x2) + (x2 \u003d x3) \u003d 1 (x2 \u003d XS) + (XS \u003d x4) \u003d 1
(XS \u003d X) + (x4 \u003d x5) \u003d 1 (x \u003d x5) + (x5 \u003d HB) \u003d 1 (x \u003d HB) + (HB \u003d x7) \u003d 1 (HB \u003d x7) + (x7 \u003d x8) \u003d 1 (x7 \u003d x8) + (x8 \u003d x9) \u003d 1 (x8 \u003d x 9) + (x \u003d x10) \u003d 0
Задача 18 е подобна на задачата 17, но последното уравнение води до факта, че след седмото ниво броят на решенията не се увеличава. В резултат, F (10) \u003d FL (10) + FO (10) \u003d FL (7) + FO (7) \u003d 21 + 21 \u003d 42.
Задача 19. Необходимо е да се намери броя на решенията на системата на уравнения (, задача Б)
(X \u003d x2) + (x \u003d x10) \u003d 1 (x \u003d XS) + (x2 \u003d x10) \u003d 1 (xs \u003d x4) + (x \u003d x10) \u003d 1 (x \u003d x5) + (x \u003d x10) \u003d 1 (x \u003d HB) + (x5 \u003d x10) \u003d 1 (HB \u003d x7) + (HB \u003d x10) \u003d 1 (x7 \u003d x) + (x \u003d x10) \u003d 1 (x8 \u003d x9) + (x \u003d X10) \u003d 1 (x9 \u003d x10) + (x9 \u003d x10) \u003d 1 (x \u003d x10) \u003d 0
- - - -*- - - -*-относно
Фиг. 1б. Задача 19.
Дървета от разтвори за получаване на F1 (n) и F0 (n) са показани на фиг. 1б. Въпреки това, уравнението (x9 \u003d x10) \u003d 1 не може да се извърши. Следователно системата на уравненията няма решения.
Задача 20. Необходимо е да се намери броя на решенията на системата на уравненията (, задача 7)
(X ^ x2) + (x ^ xz) \u003d 1 (x2 ^ Xs) + (x2 * x4) \u003d 1 (XS ^ x4) + (XS ^ x5) \u003d 1 (x ^ x5) + (x4 ^ HB) \u003d 1 (x5 ^ HB) + (x5 ^ x7) \u003d 1 (HB ^ x7) + (HB ^ x8) \u003d 1
(X7 ^ xs) + (x7 ^ x9) \u003d 1 (XS ^ x9) + (XS ^ x10) \u003d 1
Фигура 17 показва дървото на решенията от "1".
Фиг. 17. Задача 20 Фиг. 18. Задача 20.
Вместо десет нива, ние ограничихме до пет, тъй като задачата е подобна на задачата 17. Въпреки това, от "0" дървото ще изглежда различно (фиг. 18).
Обърнете внимание, че F0 (N) \u003d FX (N + 1) - 1. след това FX (10) \u003d 89 и F0 (10) \u003d FX (11) - 1 \u003d 144 - 1. общо, F (10) \u003d F1 ( 10) + F0 (10) \u003d 89 + 143 \u003d 232.
В заключение, ние даваме програма на основна VBA, с която можете да решите системата на логически уравнения. Програмата може да е необходима за събиране на нови системи на уравнения. Фигура 19 показва програмата, с която е решена системата на уравнения от задачата 7.
В програмата, показана на фиг. 19, m масив и променлива c съдържат стойности на променливи, които отговарят на системата на уравнения от задачата 7. Програмата дава отговор 68. Програмата използва факта, че броят на различните групи стойности на N логиката Променливите са 2n. За да получите всички комплекти, трябва да извършите цикъл от 0 до 2N-1. Променливата на цикъла на всяка стъпка се превежда в двоичната система, резултатът се записва в масив m и след това са проверени условия от уравнението. За да се реши друга система от уравнения, е достатъчно да се промени размерът на Marray M, да промените стойността на VG променлива (равна на измерението) и да промените валидността на проверката.
Dim m (s) като цяло число, k като цяло число, j. Като цяло число. _ J като цяло число. N като цяло число, VG като цяло е затъмняване с string vg \u003d s j-0
За 1 до 2 ■ "" ■ VG "цикъл от ^ от 1 до 2n. Където n \u003d ,. g за k \u003d 1 до VG
N \u003d) .- 1: binary e pp e c инсталиран e nno започва от нулата k \u003d 1
Do "^ tiils n\u003e 0" превод e binary xuramp m (k) \u003d n mod 2 k \u003d n ■ 2 k \u003d k +! Линия.
IFIM (l) o m (2) или m (l) 0- ni (3)) и_ "условия на уравнение (m (2) \\ t c \u003d "" "" Променливата от всяка стъпка ще може да съдържа решението на системата за k \u003d 1, че VG c \u003d c - foimat (m (k) j следващ k j-j-1 край, ако следващата I. MS ^ EOX I "Брой решения Vvvvvvvvv--1 I. Фиг. 19. Програма за задача 7 1. WINGS S.S. EGGE 2014. Информатика. Тематични задачи за тестове / S.S. Ловец, d.m. Ушаков. - m.: Издателство "Изпит". - 245 p. 2. Сайт K.YU. Полякова. Режим на достъп: http: //kpolyakov.namd.-ru/download/inf-2011-14.pdf 3. Методичен сертифициран курс на компанията "1c" "подготовка за изпита в компютърните науки. Модул 1 ". - m.: Издателство "1c". - 218 p. 4. Успешно да предадат ECH за компютърните науки. Режим на достъп: http://infoegehelp.ru/index.php?itemid\u003d77&id\u003d103&option\u003dcom_con- Този материал съдържа презентация, при която са представени методи за решаване на логически уравнения и системи на логически уравнения в задачата на Б15 (№ 23, 2015) на EGE за компютърните науки. Известно е, че тази задача е една от най-сложните сред задачите на ЕГГ. Представянето може да бъде полезно при провеждането на уроци по темата "Логика" в класовете по профил, както и при подготовката за доставка на употребата. За да се насладите на преглед на презентации, създайте себе си профил (акаунт) Google и влезте в него: https://accounts.google.com Решаване на задачата на B15 (система от логически уравнения) Вишневская, ма.Е. Гимназия №3 "18 ноември 2013 г., Саратов Задачата B15 е една от най-трудните в изпита в компютърните науки !!! Проверени са умения: конвертиране на изрази, съдържащи логически променливи; да се опише на естествения език множество логически променливи стойности, при които даден набор от логически променливи е вярно; Изчислете броя на двоичните комплекти, които отговарят на посочените условия. Най-трудното нещо, защото Няма официални правила как да го направите, се изисква задача. Без нищо не! Без нищо не! Свързваща връзка: A / B, A B, AB, A & B, A и B DUSUUNCAULT: A / B, A + B, A | B, и или b отрицание: а, а, не е еквивалентност: a b, a b, a b, изключващи "или": a b, xor b Метод за подмяна на променливите Колко различни комплекта логически променливи X1, X2, ..., X9, X10, които отговарят на всички условия, изброени по-долу: ((x1)) / (x3 ≡ x4)) / (¬ (¬ (¬ ()) \\ t X1 ≡ x2) / ¬ (x3 ≡ x4)) \u003d 1 ((x3 \u003d x4) / (x5 ° х6)) / (¬ (x3 ≡ x4) / ¬ (x5 \u003d x6)) \u003d 1 ( (x5 ≡ x6) / (x7 ° x8)) / (¬ (x5 \u003d x7) / ¬ (x7 ° x8)) \u003d 1 ((x7 ° x8) / (x9 \u003d x10)) / \\ t ¬ (x7 ≡ x8) / ¬ (x9 ≡ x8)) \u003d 1 в отговор, не е необходимо да изброявате всички различни комплекти X1, X2, ..., X9, X10, на която се извършва тази система от равенства. Като отговор трябва да посочите броя на тези комплекти (DEMO версия 2012) Стъпка на решения 1. Ние опростим, чрез замяна на променливите T1 \u003d X1 x2 t2 \u003d x3 x4 t3 \u003d x5 x6 t4 \u003d x7 x8 t5 \u003d x9 x10 след опростяване: (t1 / t2) / (¬t1 / ¬ t2) \u003d 1 (t2 / t3) / (¬t2 / ¬ t3) \u003d 1 (t3 / t4) / (¬t3 / ¬ t4) \u003d 1 (t4 / t5) / (¬t4 / ¬ t5) \u003d 1 Разгледайте едно от уравненията: (t1 / t2) / (¬t1 / ¬ t2) \u003d 1 очевидно, it \u003d 1 само ако една от променливите е 0, и Другият е 1. Използваме формулата за експресиране на XOR операция чрез връзка и disjunction: (t1 / t2) / (¬T1 / ¬ t2) \u003d t1 t2 \u003d ¬ (t1 ≡ t2) \u003d 1 ¬ ( T1 ≡ t2) \u003d 1 ¬ (t2 ≡ t3) \u003d 1 ¬ (t3 ≡ t4) \u003d 1 ¬ (t4 ≡ t5) \u003d 1 Стъпка 2. Анализ на системата ¬ (t1 ≡ t2) \u003d 1 ¬ (t2 ≡ t3) \u003d 1 ¬ (t3 ≡ t4) \u003d 1 ¬ (t4 ≡ t5) \u003d 1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 t .да се. Tk \u003d x2k-1 ≡ x2k (t1 \u003d x1 x2, ...), всяка стойност на TK съответства на две двойки X2K-1 и X2K стойности, например: tk \u003d 0 съответстват на два двойки - (0.1) и (1, 0) и TK \u003d 1 - двойки (0.0) и (1,1). Стъпка3. Преброяване на броя на решенията. Всеки t има 2 решения, броя t - 5. така За променливи t съществува 2 5 \u003d 32 решения. Но всеки t съответства на двойка решения X, т.е. Изходната система има 2 * 32 \u003d 64 решения. Отговор: 64. Метод за изключване на част от решенията. Колко различни комплекта стойности на логически променливи X1, X2, ..., X5, Y1, Y2, ..., Y5, които отговарят на всички посочени по-долу условия: (x1 → x2 ) ∧ (x2 → x4) ∧ (x3 → x4) ∧ (x4 → x5) \u003d 1; (Y1 → Y2) ∧ (Y2 → Y3) ∧ (Y3 → Y4) ∧ (Y4 → Y5) \u003d 1; Y5 → x5 \u003d 1. Отговорът не трябва да изброява всички различни комплекти X1, X2, ..., X5, Y 1, Y2, ..., Y5, в която се извършва тази система от равенства. Като отговор трябва да посочите броя на тези комплекти. Решение. Етап 1. Последователно решение на уравнения X1 1 0 x2 1 0 1 X3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 Първо уравнение - връзката с няколко операции по тях е 1, т.е. Всяко от последиците е вярно. Въпросът за фалшивост е само в един случай, когато 1 0, във всички останали случаи (0 0, 0 1, 1 1) операция се връща 1. Напишете го под формата на таблица: Етап 1. Последователното решение на T.O. уравненията Получават се 6 комплекта разтвори за X1, X2, X3, X4, X5, X3, X4, X5: (00000), (00001), (00011), (00111), (01111), (11111). Според подобен начин стигаме до заключението, че за Y1, Y2, Y3, Y4, Y5 Има същия набор от решения. Като Тези уравнения са независими, т.е. Те нямат общи променливи, след това решаването на тази система на уравнения (с изключение на третото уравнение) ще бъде 6 * 6 \u003d 36 двойки "IKS" и "Игареков". Помислете за третото уравнение: y5 → x5 \u003d 1 решението са двойки: 0 0 0 1 1 1 не е пара разтвор: 1 0 Ние сравняваме получените разтвори, където Y5 \u003d 1 не е подходящ х5 \u003d 0. Такива двойки 5. Броят на системните разтвори: 36-5 \u003d 31. Отговор: 31 Необходимо комбинаторика !!! Методът на динамично програмиране Колко различни разтвори има логическо уравнение x 1 → x 2 → x 3 → x 4 → x 5 → x 6 \u003d 1, където x 1, x 2, ..., x 6 - логически променливи? В отговор не е необходимо да посочвате всички различни групи променливи, в които се извършва това равенство. Като отговор трябва да посочите количеството такива набори. Решение Стъпка1. Анализът на състоянието отляво в уравнението се записва последователно чрез операцията по линията, приоритетът е един и същ. Пренаписваме: ((((x 1 → x 2) → x 3) → x 4) → x 5) → x 6 \u003d 1 nb! Всяка следваща променлива зависи от предишната, но в резултат на предишното отражение! Стъпка 2. Откриване на модели Разгледайте първото значение, X 1 → X 2. Татак на истината: x 1 x 2 x 1 → x 2 0 0 1 0 1 1 1 0 0 1 1 1 от един 0 получени 2 единици и от 1 получен Един 0 и един 1. Само един 0 и три 1, това е резултат от първата операция. Стъпка 2. Откриване на модели чрез свързване на резултата от първата работа x 3, получаваме: f (x 1, x 2) x 3 f (x 1, x 2) x 3 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 1 1 1 от две 0 - две 1, от всеки 1 (от него 3) един 0 и 1 (3 + 3) Стъпка 3. Изходът на формулата T.O. Можете да образувате формули за изчисляване на броя на zeros n i и броя на единиците e i за уравнението с i променливи:, Стъпка 4. Запълване на таблицата Напълнете отляво на дясна маса за I \u003d 6, изчисляване на броя на нулите и устройствата съгласно горните формули; Таблицата показва как следващата колона е построена съгласно предишната :: Брой променливи 1 2 3 4 5 6 Брой Zeros N I 1 1 3 5 11 21 Брой единици E I 1 2 * 1 + 1 \u003d 3 2 * 1 + 3 \u003d 5 11 21 43 Отговор: 43 Метод, използвайки опростявания на логически изрази Колко различни разтвора има уравнение (J → K) → (m n l)) ((m n) → (¬ ¬ k)) (m → j) ) \u003d 1, където J, K, L, M, N са логически променливи? В отговор не е необходимо да изброявате всички различни комплекти от J, K, L, M и N, при които се прави това равенство. Като отговор трябва да посочите броя на тези комплекти. Отбележете, че J → K \u003d ¬ J k Ние въвеждаме подмяната на променливите: J → K \u003d A, m n l \u003d в уравнението за пренаписване, като се вземе предвид подмяната: (a → b) (b → A) (m → J) \u003d 1 4. (a б) (m → й) \u003d 1 5. Очевидно е, че a b със същите стойности на А и в 6. Обмислете най-новите Implication m → J \u003d 1 е възможно, ако: m \u003d j \u003d 0 m \u003d 0, j \u003d 1 m \u003d j \u003d 1 Решение, защото A b, след това при m \u003d j \u003d 0 получаваме 1 + k \u003d 0. Няма решения. Когато m \u003d 0, j \u003d 1, получаваме 0 + k \u003d 0, k \u003d 0 и n и l - всеки, 4 разтвора: ¬ k \u003d m n lknl 0 0 0 0 0 1 0 1 0 0 1 Решение 10. с m \u003d j \u003d 1, получаваме 0 + k \u003d 1 * n * l, или k \u003d n * l, 4 решения: 11. има 4 + 4 \u003d 8 решения Отговор: 8 knl 0 0 0 0 0 1 0 1 0 1 1 1 Източници на информация: OB Богомолова, Д.ю. Usenkov. B15: Нови задачи и ново решение // Информатика, № 6, 2012, p. 35 - 39. К.Ю. Поляци. Логически уравнения // Информатика, № 14, 2011, p. 30-35. http://ege-go.ru/zadania/grb/B15/, [електронен ресурс]. http://kpolyakov.narod.ru/school/ege.htm, [електронен ресурс]. Методи за решаване на системи за логически уравнения Възможно е да се реши системата от логически уравнения, например, като се използва таблица за истината (ако броят на променливите не е твърде голям) или с решенията дърво, преди това опростява всяко уравнение. 1. Метод за подмяна на променливи. Въвеждането на нови променливи ви позволява да опростите системата на уравненията, като намалите броя на неизвестните.Новите променливи трябва да бъдат независими един от друг..
След решаването на опростената система е необходимо отново да се върнете към първоначалните променливи. Помислете за прилагането на този метод в конкретен пример. Пример. ((X1 ° x) ∧ (x3 ≡ x4)) ∨ (¬ (x1 ° x2) ¬ (x3 ≡ x4)) \u003d 0 ((X3 ≡ x4) ∧ (x5 ° x6)) ∨ (¬ (x3 ≡ x4) ¬ (x5 ≡ x6) \u003d 0 ((X5 ≡ x6) ∧ (x7 ° x8)) ∨ (¬ (x5 ≡ x6) ¬ (x7 ≡ x8)) \u003d 0 ((X7 ° x8) ∧ (x9 ≡ x10)) ∨ (¬ (x7 ≡ x8) ¬ (x9 ≡ x10)) \u003d 0 Решение: Въвеждаме нови променливи: a \u003d (x1≡ x2); B \u003d (x3 ≡ x4); C \u003d (x5 ≡ x6); D \u003d (x7 ≡ x8); E \u003d (x9 ≡ x10). (Внимание! Всяка от техните променливи X1, X2, ..., X10 трябва да бъде включена само в една от новите променливи A, B, C, D, E, т.е. нови променливи са независими един от друг). Тогава системата на уравненията ще изглежда така: (A ∧ b) ∨ (¬ ∧ ¬V) \u003d 0 (В ∧ в) ∨ (¬ ∧ ¬) \u003d 0 (C ∧ d) ∨ (¬) \u003d 0 (D ∧ e) ∨ (¬ ¬ ¬) \u003d 0 Ние изграждаме решенията дърво на получената система: Помислете за уравнението a \u003d 0, т.е. (X1.≡
X2) \u003d 0. Има 2 корени: X1 ≡ x2. От една и съща таблица може да се види, че уравнението a \u003d 1 също има 2 корени. Изберете броя на корените на решенията на дървото: За да намерите броя на решенията на един клон, умножете броя на решенията на всяко ниво. Ляв клон има 2⋅
2
⋅
2
⋅
2
⋅
2 \u003d 32 решения; Десният клон има и 32 решения. Тези. Цялата система има 32 + 32 \u003d 64 решения. Отговор: 64. 2. Метод на разсъжденията. Сложността на решаването на системите на логическите уравнения се състои в насипността на общото дърво. Методът за разсъждение позволява да не изграждате цялото дърво напълно, но да се разбере колко ще има клонове. Помислете за този метод в конкретни примери. Пример 1. Колко различни комплекта стойности на логически променливи X1, X2, X3, X4, X5, Y1, Y2, Y3, Y4, Y5, които отговарят на всички условия, изброени по-долу? (x1 → x2) / (x2 → x3) / (x3 → x4) / (x4 → x5) \u003d 1 (Y1 → Y2) / (Y2 → Y3) / (Y3 → Y4) / (Y4 → Y5) \u003d 1 x1 / y1 \u003d 1 Отговорът не трябва да посочва всички различни набори от променливи X1, X2, X3, X4, X5, Y1, Y2, X4, X5, Y1, Y2, Y3, Y4, Y5, при което се прави тази система от равенства. Като отговор трябва да посочите броя на тези комплекти. Решение: Първото и второто уравнение съдържат независими променливи, които са свързани с третото състояние. Ние изграждаме дърво от решения на първото и второто уравнения. За да представите решения на дърво от първото и второто уравнение, всеки клон на първото дърво трябва да бъде продължен от дърво за променливиw. . Дървото, построено по този начин, ще съдържа 36 клона. Някои от тези клонове не отговарят на третото уравнение на системата. Забележка за първото дърво броят на клоните на дърветата"U" които отговарят на третото уравнение: Нека обясним: да извърши третото състояние при x1 \u003d 0 трябва да бъде u1 \u003d 1, т.е. всички дървесни клони"Х" където X1 \u003d 0 може да бъде продължено само с един клон на дърво"U" . И само за един бранш"Х" (вдясно) предполагат всички клонове на дърветата"U". Така пълното дърво на цялата система съдържа 11 клона. Всеки клон представлява едно решение на оригиналната система на уравнения. Така че цялата система има 11 решения. Отговор: 11. Пример 2. Колко различни решения има система от уравнения (X1 ≡ x2) ∨ (x1 ° x10) ∨ (¬x1 ∧ ¬ x10) \u003d 1 (X2 ≡ x3) ∨ (x2.1 x10) ∨ (¬x2 ∧ ¬ x10) \u003d 1. ………………
(X9 ≡ x10) ∨ (x9 ∧ x10) ∨ (¬x9 ∧ ¬ x10) \u003d 1 (X1 ≡ x10) \u003d 0 къде X1, X2, ..., X10 - логически променливи? В отговор не е необходимо да посочвате всички различни групи променливи, в които се извършва това равенство. Като отговор трябва да посочите броя на тези комплекти. Решение: Опростяваме системата. Ние изграждаме таблица на истината на първата уравнение: X1 ∧ x10. ¬x1 ¬ ¬ x10 (X1 ° x10) ∨ (¬x1 ∧ ¬ x10) Обърнете внимание на последната колона, тя съвпада с резултата от действиетоX1 ≡ x10. X1 ≡ x10. След опростяване получаваме: (X1 ≡ x2) ∨ (x1 ≡ x10) \u003d 1 (X2 ≡ x3) ∨ (x2 ≡ x10) \u003d 1 (X3 ≡ x4) ∨ (x3 ≡ x10) \u003d 1 ……
(X9 ≡ x10) ∨ (x9 ≡ x10) \u003d 1 (X1 ≡ x10) \u003d 0 Помислете за последното уравнение:(X1 ≡ x10) \u003d 0, т.е. x1 не трябва да съвпада с X10. За първото уравнение да бъде 1, трябва да се извърши равенство.(X1 ≡ x2) \u003d 1, т.е. x1 трябва да съвпада с X2. Ние изграждаме дърво от решения на първото уравнение: Помислете за второто уравнение: при x10 \u003d 1 и при скоба x2 \u003d 0трябва да бъде равен на 1 (т.е. x2 съвпада с X3); при x10 \u003d 0 и при скоба x2 \u003d 1(X2 ≡ x10) \u003d 0, това означава, че скобата (x2 ≡ x3) тя трябва да бъде равна на 1 (т.е. x2 съвпада с x3): Според по този начин ние изграждаме решенията дърво за всички уравнения: По този начин системата на уравненията има само 2 решения. Отговор: 2. Пример 3. Колко различни комплекта от стойности на логически променливи X1, X2, X3, X4, Y1, Y2, Y3, Y4, Z1, Z2, Z3, Z4, които отговарят на всички посочени по-долу условия? (x1 → x2) / \\ t (x2 → x3) / (x3 → x4) \u003d 1 (¬x1 / y1 / z1) / (x1 / ¬ z1) / (x1 / y1 / ¬z1) \u003d 1 (¬x2 / y2 / z2) / (x2 / ¬2 / z2) / (x2 / y2 / ¬z2) \u003d 1 (¬x3 / y3 / z3) \\ t / (x3 / ¬) / z3) \\ t / (x3 / y3 / ¬z3) \u003d 1 (¬x4 / y4 / z4) / (x4 / ¬ 1 / z4) / (x4 / y4 / ¬z4) \u003d 1 Решение: Ние изграждаме решенията на 1-то уравнение: Помислете за второто уравнение: Подобно на останалите уравнения. Отбелязваме получения брой решения от всеки възел на дървото: За да разберете броя на решенията за всеки клон, заменете числата, получени поотделно за всеки клон (останали живи). 1 клон: 1 ⋅ 1 ⋅ 1 ⋅ 1 \u003d 1 разтвор 2 клон: 1 ⋅ 1 ⋅ 1 ⋅ 2 \u003d 2 решения 3 клон: 1 ⋅ 1 ⋅ 2 ⋅ 2 \u003d 4 решения 4 клон: 1 ⋅ 2 ⋅ 2 ⋅ 2 \u003d 8 решения 5 клон: 2 ⋅ 2 ⋅ 2 ⋅ 2 \u003d 16 решения Преместване на получените числа: общо 31 разтвор. Отговор: 31. 3. Постави нарастването на броя на корените В някои системи броят на корените на следващото уравнение зависи от броя на корените на предишното уравнение. Пример 1. Колко различни комплекта стойности на логически променливи X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, които отговарят на всички условия, изброени по-долу? ¬ (x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) \u003d 0 ¬ (x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) \u003d 0 ¬ (x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) \u003d 0 Опростяване първо уравнение:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3) \u003d x1 ⊕ x3 \u003d ¬ (x1 x3). След това системата ще приеме формата: ¬ (x1 ≡ x2) ¬ (x1 ≡ x3) \u003d 0 ¬ (x2 ≡ x3) ¬ (x2 ≡ x4) \u003d 0 ¬ (x8 ≡ x9) ¬ (x8 ≡ x10) \u003d 0 И т.н. Всяко следващо уравнение има 2 корени повече от предишния. 4 уравнението има 12 корени; 5 уравнение има 14 корени 8 Уравнението има 20 корени. Отговор: 20 корени. Понякога броят на корените нараства в съответствие със закона на фибоначи. Решението на системата на логическите уравнения изисква творчески подход.Изтегли:
Визуализация:
Подписи за слайдове:
