Решение на уравнението 1. Преминете към префиксната форма на писане на уравнението, като замените символите на отрицанията с ¬ 2. Конструирайте заглавието на таблица на истината от специален тип 3. Попълнете редовете на таблицата на истината за всички комбинации от A и B, замествайки 0 или 1 вместо X. 4. Генерирайте таблица на истината за X = F (A,B) 5. Използвайки таблицата на истината, определете типа на функцията X, ако е необходимо, като използвате методите за конструиране на SCNF и SDNF, които ще бъдат обсъдени по-долу.
Конструиране на таблица на истинност със специална форма ¬((A+B)·(X A·B))=¬(B+¬(X A))
Таблица на истината X=F(A, B) ABX Съответства на отрицанието на импликация B в A ОТГОВОР:
Комбинационни схеми на логически устройства Основни елементи (GOST): 1 A B Дизюнкция A B Еквивалентност & A B Конюнкция M2 A B XOR
Комбинационни схеми на логически устройства Основни елементи (GOST): 1 A B Импликация & A B Schaeffer елемент & A B Коимпликация 1 A B Webb елемент
Примерна верига F 1 & 1 & & 1M2 B A
Решаване на вериги 1 Вариант - преобразуване на схема в сложен логически израз и след това опростяването й според законите на логиката. Вариант 2 - конструиране на таблица на истината и след това, ако е необходимо, конструиране чрез SKNF или SDNF (виж по-долу). Нека разгледаме втория вариант, тъй като е по-прост и по-разбираем.
Изграждане на таблицата на истината AB A + B + · B B · A + A B A + · ·
Таблица на истината F(A, B) ABX Съответства на отрицанието на импликацията B в A ОТГОВОР:
SDNF и SKNF (дефиниции) Елементарна конюнкция е конюнкция на няколко променливи, взети с или без отрицание, като сред променливите може да има идентични. Елементарна дизюнкция се нарича дизюнкция на няколко променливи, взети с или без отрицание, и. сред променливите може да има еднакви такива. Всяка конюнкция на елементарни конюнкции Нека я наречем дизюнктивна нормална форма (DNF) Нека наречем всяка конюнкция на елементарни дизюнкции конюнктивна нормална форма (DNF).
SDNF и SCNF (дефиниции) Перфектна дизюнктивна нормална форма (PDNF) се нарича DNF, в която няма идентични елементарни връзки и всички връзки се състоят от един и същ набор от променливи, в които всяка променлива се появява само веднъж (евентуално с отрицание). Перфектната конюнктивна нормална форма (PCNF) е CNF, в която няма идентични елементарни дизюнкции и всички дизюнкции се състоят от един и същ набор от променливи, в които всяка променлива се появява само веднъж (евентуално с отрицание).
Алгоритъм за получаване на SDNF от таблицата на истинността 1. Маркирайте редовете на таблицата на истинността в последната колона, от които има 1. 2. Запишете за всеки маркиран ред конюнкцията на всички променливи, както следва: ако стойността на променлива в даден ред е 1, тогава включете самата тази променлива във връзката, ако е равно на 0, тогава нейното отрицание. 3. Свържете всички получени съюзи в дизюнкция. Алгоритъм за получаване на SCNF от таблицата на истината 1. Маркирайте редовете на таблицата на истината, в последната колона от които има 0. 2. Запишете за всеки маркиран ред дизюнкцията на всички променливи, както следва: ако стойността на променлива в даден ред е 0, тогава включете самата тази променлива в конюнкцията, ако е равно на 1, тогава нейното отрицание. 3. Свържете всички получени дизюнкции в конюнкция.
Пример за конструиране на SKNF XY F(X,Y) Маркирайте нули 2. Дизюнкции: X + Y 3. Конюнкция: (X + Y) · (X + Y)
Решаване на системи от логически уравнения чрез промяна на променливи
Методът на заместване на променливи се използва, ако някои променливи са включени в уравненията само под формата на конкретен израз и нищо друго. Тогава този израз може да бъде обозначен с нова променлива.
Пример 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 се умножава:
|
Брой комплекти на x1…x8 |
||||
Нека съберем броя на комплектите: 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)
Еквивалентността е вярна само ако и двата операнда са равни. Има два набора от решения на това уравнение:
| 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 = (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 = B 1 + C 1 + D 1.
Множеството (0,1) на променливите (x2,y2) се получава от множествата (0,1), (1,0) и (1,1) на променливите (x1,y1). Тези. B 2 = B 1 + C 1 + D 1.
Разсъждавайки по подобен начин, отбелязваме, че C 2 =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
Да направим маса
| Комплекти | Обозначаване. | Формула |
Брой комплекти |
||||||
| i=1 | i=2 | i=3 | i=4 | i=5 | i=6 | i=7 | |||
| (0,0) | A i | A i+1 =B i +C i +D i | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B i | B i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C i | C i+1 =B i +C i +D i | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D i | D i+1 =D i | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Последното уравнение (x7 ∨ y7) = 1 е изпълнено от всички комплекти, с изключение на тези, в които x7=0 и y7=0. В нашата таблица броят на тези комплекти е A 7.
Тогава общият брой серии е B 7 + C 7 + D 7 = 127+127+1 = 255
Отговор: 255
Решаване на системи от логически уравнения чрез таблични методи чрез трансформиране на логически изрази.Тази техника се основава на използването на таблици на истината и е предназначена за ученици, които знаят как да конвертират логически изрази. Ако учениците не владеят тези методи, те могат да се използват без трансформации. (Ще използваме трансформации). За да се овладее този метод на решение, е наложително да се познават свойствата на основните логически операции: конюнкция, дизюнкция, инверсия, импликация и еквивалентност.
Алгоритъм за решаване на системи от уравнения по този метод:
Трансформирайте логическото уравнение и го опростете.
Определете последователността на решаване на уравнения в системата, тъй като в повечето случаи има последователно решаване на уравнения отгоре надолу (както са разположени в системата), но има опции, когато е по-удобно и по-лесно да започнете решаването от отдолу нагоре.
Създайте таблица с променливи, където можете да зададете първоначалните стойности на първата променлива (или последната).
Запишете последователно възможните опции за следната променлива, когато всекисмисъл на първото.
След решаването на предишното уравнение, преминавайки към следващото, не забравяйте да обърнете внимание какви променливи се използват в предишните и следващите уравнения, тъй като стойностите на променливите, получени при решаването на предишните уравнения, се предават като опции за следните уравнения.
Обърнете внимание на получените количества от разтвора, когато преминавате към следващата променлива, защото може да се идентифицира модел в увеличаването на решенията.
Пример 1.
¬ х1 ˅ х2=1
¬ х2 ˅ х3=1
¬ х3 ˅ х4=1
¬ х9 ˅ х10=1
Нека започнем с X1 и да видим какви стойности може да приеме тази променлива: 0 и 1.
Тогава нека разгледаме всяка от тези стойности и да видим какво може да бъде X2.
Отговор: 11 решения
Пример 2.
( х1х2)˅(¬х1˄¬х2) ˅( х1↔ х3)=1
( х2˄х3)˅(¬х2˄¬х3) ˅( х2↔ х4)=1
(X8˄ X9)˅(¬X8˄¬X9)˅(X8↔X10)=0
Нека трансформираме по формулата (А˄ б)˅ (¬ А ˄ ¬ б)= А↔ б
Получаваме:
( х1↔ х2) ˅ (х1↔ х3) =1
( х2↔ х3) ˅ (х2↔ х4) =1
( х8↔ х9 (х8↔ х10) =0
За X1 =0 - 8 решения
Нека вземем X1=1 и да видим каква стойност може да приеме X2. Сега за всеки X2 ще разгледаме какви стойности може да приеме X3 и т.н.
За X1=1 – 8 решения
Общо 8+8=16 решения
Отговор. 16 решения
Пример 3 .
¬ ( х1↔ х2) ˄ ( х1х3) ˄ (¬х1˅¬х3 )=0
¬ ( х2↔ х3) ˄ (х2 ˅х4) ˄ (¬х2˅¬х4)=0
….
¬ ( х8↔ х9 (х8х10) ˄ (¬х8˅¬х10)=0
След трансформациите (А˅ б) ˄(¬ А ˅¬ б)= ¬( А ↔ б)
получаваме:
¬ ( х1↔ х2) ˄ ¬ (х1↔ х3)=0
¬ ( х2↔ х3) ˄ ¬ (х2↔ х4)=0
…..
¬ ( х8↔ х9) ˄ ¬ (х8↔ х10)=0
Нека вземем X1=0 и да видим каква стойност може да приеме X2. Сега за всеки X2 ще разгледаме какви стойности може да приеме X3 и т.н.
Имаме 10 решения за X1=0
Нека направим същото за X1=1. Получаваме и 10 решения
Общо:10+10=20
Отговор: 20 решения.
Пример 4.
(Х1 ˄ Х2) ˅ (¬Х1 ˄ ¬Х2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1
(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬ X4)=1
….
(Х8 ˄ Х9) ˅ (¬Х8˄ ¬Х9) ˅ (Х9 ˄ Х10) ˅ (¬Х9 ˄¬ Х10)=0
Нека преобразуваме с помощта на формули. (А˄ б)˅ (¬ А ˄ ¬ б)= А↔ б. Получаваме:
(X1↔ X2) ˅ (X2↔ X3)=1
(X2↔ X3) ˅ (X3↔ X4)=1
(X3↔ X4) ˅ (X4↔ X5)=1
(X4↔ X5) ˅ (X5↔ X6)=1
(X5↔ X6) ˅ (X6↔ X7)=1
(X6↔ X7) ˅ (X7↔ X8)=1
(X7↔ X8) ˅ (X8↔ X9)=1
(X8↔ X9) ˅ (X9↔ X10)=0
Да започнем от края, защото в последното уравнение променливите се определят еднозначно.
Нека X10=0, тогава X9=1, X8=0, X7=0, X6=0 и следните променливи могат да приемат различни стойности. Ще разгледаме всеки.
Общо 21 решения за X10=0
Сега помислете за X10=1. Получаваме и 21 решения
Общо:21+21=42
Отговор: 42 решения
Пример 5.
( х1х2) ˅ (¬х1 ˄ ¬х2) ˅ (¬х3 ˄х4 (х3 ˄ ¬х4)=1
( х3 ˄х4) ˅ (¬х3 ˄ ¬х4) ˅ (¬х5х6) ˅ (х5˄¬х6)=1
( х5х6) ˅ (¬х5˄¬х6) ˅ (¬х7˄х8 (х7 ˄ ¬х8)=1
( х7˄х8) ˅ (¬х7 ˄ ¬х8) ˅ (¬ х9х10 (х9˄ ¬х10) =1
Нека трансформираме по формулите:(¬ А ˄ б) ˅ ( А ˄ ¬ б)= А↔ ¬ б
( А˄ б)˅ (¬ А ˄ ¬ б)= А↔ б
( х1↔ х2) ˅ (х3 ↔ ¬х4)=1
( х3↔ х4 (х5 ↔ ¬х6)=1
( х5↔ х6) ˅ (х7 ↔ ¬х8)=1
( х7↔ х8 (х9 ↔ ¬х10)=1
Нека да разгледаме какви стойности X1 и X2 могат да приемат: (0,0), (0,1), (1,0), (1,1).
Нека разгледаме всяка опция и да видим какви стойности могат да приемат X3, X4.
Започвайки от X7, X8, веднага ще запишем броя на решенията, тъй като веднага става ясно, че когато стойностите са еднакви (1,1) и (0,0), тогава следните променливи имат 4 решения, а когато са различни (0,1) и (1 ,0) – 2 решения.
Общо: 80+80+32=192
Отговор: 192 решения
Пример 6.
(X1↔X2) ˅ (X2 ↔X3)=1
(X2↔X3) ˅ (X3↔X4)=1
(X3↔X4) ˅ (X4 ↔X5)=1
….
(X8↔X9) ˅ (X9 ↔X10)=1
Нека вземем X1=0 и да видим каква стойност може да приеме X2. Сега за всеки X2 ще разгледаме какви стойности може да приеме X3 и т.н.
Виждаме определен модел: Броят на следващите решения е равен на сумата от предходните две.
Същото за X1=1 получаваме 89 решения
Общо: 89+89=178 решения
Отговор: 178 решения
Нека го решим по още един начин
(X1↔X2) ˅ (X2 ↔X3)=1
(X2↔X3) ˅ (X3↔X4)=1
(X3↔X4) ˅ (X4 ↔X5)=1
….
(X8↔X9) ˅ (X9 ↔X10)=1
Нека представим замяната:
T 1 =(X1↔X2)
T 2 =(X2↔X3)
T 3 =(X3↔X4)
T 4 =(X4↔X5)
T 5 =(X5↔X6)
T 6 =(X6↔X7)
T 7 =(X7↔X8)
T 8 =(X8↔X9)
T 9 =(X9↔X10)
Получаваме:
T1T2=1
T2 ˅T3=1
T3˅T4=1
T4T5=1
T5T6=1
T6˅T7=1
T7˅T8=1
T8T9=1
T9T10=1
Да вземемT1=1 и използвайте свойствата на дизюнкция:
НО нека си припомним това
T 1 =(X1↔X2)
T 2 =(X2↔X3) и т.н.
Нека използваме свойството за еквивалентност и да се уверим, че гледаме таблицата
Когато T = 1, тогава се получават две решения. И когато =0 има едно решение.
Следователно можем да преброим броя на единиците и да ги умножим по 2+ броя на нулите. Броене, също с помощта на модел.
Оказва се, че броят единици е равен на предишния общ брой решения T, а броят на нулите е равен на предишния брой единици
Така. Ще го вземем. Тъй като едно дава две решения, тогава 34 * 2 = 68 решения от едно + 21 решения от 0.
Общо 89 решения за T=1. По подобен начин получаваме 89 решения за T=0
Общо 89+89=178
Отговор: 178 решения
Пример 7.
(х1 ↔ х2) ˅ (х3↔ х4) ˄ ¬(х1 ↔ х2) ˅ ¬(х3↔ х4)=1
(х3 ↔ х4 (х5↔ х6) ˄ ¬(х3 ↔ х4) ˅ ¬(х5↔ х6)=1
(х5 ↔ х6) ˅ (х7↔ х8) ˄ ¬(х5 ↔ х6) ˅ ¬(х7↔ х8)=1
(х7 ↔ х8 (х9↔ х10) ˄ ¬(х7 ↔ х8) ˅ ¬(х9↔ х10)=1
Нека представим замяната:
T1=(х1 ↔ х2)
T2=(х3↔ х4)
T3=(х5↔ х6)
T4=(х7 ↔ х8)
T5=(х9↔ х10)
Получаваме:
(T1 ˅ T2) ˄ ¬(T1 ˅¬ T2)=1
(T2 ˅ T3) ˄ ¬(T2˅¬ T3)=1
(T3 ˅ T4) ˄ ¬(T3 ˅¬ T4)=1
(T4 ˅ T5) ˄ ¬(T4˅¬ T5)=1
Нека да разгледаме какво може да бъде Ts:
T1
Т2
Т3
Т4
Т5
Обща сума
0
1
0
1
0
32
1
0
1
0
1
32
T К ≠T К+1 ТО К = Т К+2
Получаваме: 2 5 =32 за Т
Общо: 32+32=64
Отговор: 64 решения.
Общинско бюджетно учебно заведение
"Средно училище №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 y 1 | х 2 y 2 | (х 1 y 1) (x2 y2) | (х 1 х2) | (y 1 y2) | (х 1 х2) (y 1 y2) | |||||
Конструирането на таблица на истината е трудоемко и време неефективно, затова използваме втория метод – логическо разсъждение. Продуктът е равен на 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 ) | (х2 , г2 ) |
Общ брой двойки 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).
| (х1 , г1 ) | (х2 , г2 ) |
Нека създадем таблица за изчисляване на броя на двойките на всеки етап.
| 0 |
|||||||
Като се вземат предвид решенията на последното уравнение х 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)
Тема на урока: Решаване на логически уравнения
Образователни – изучаване на методи за решаване на логически уравнения, развиване на умения за решаване на логически уравнения и конструиране на логически израз с помощта на таблица на истината;развитие - създават условия за развитие на познавателния интерес на учениците, насърчават развитието на паметта, вниманието и логическото мислене;
Образователни : насърчаване на способността да се изслушват мненията на другите,възпитаване на воля и постоянство за постигане на крайни резултати.
Тип урок: комбиниран урок
Оборудване: компютър, мултимедиен проектор, презентация 6.
По време на часовете
Повторение и актуализиране на основни знания. Проверка на домашното (10 минути)
В предишните уроци се запознахме с основните закони на логическата алгебра и се научихме да използваме тези закони за опростяване на логически изрази.
Нека проверим домашното си за опростяване на логически изрази:
1. Коя от следните думи отговаря на логическото условие:
(съгласна първа буква→ съгласна втора буква)٨ (гласна на последната буква → гласна на предпоследната буква)? Ако има няколко такива думи, посочете най-малката от тях.
1) АННА 2) МАРИЯ 3) ОЛЕГ 4) СТЕПАН
Нека въведем следната нотация:
А – първа съгласна буква
Б – съгласна от втора буква
S – гласна последна буква
D – предпоследна гласна буква
Нека направим израз:
Нека направим таблица:
2. Посочете кой логически израз е еквивалентен на израза
Нека опростим записа на оригиналния израз и предложените опции:
3. Даден е фрагмент от таблицата на истинността на израз F:
Кой израз съответства на F?
Нека определим стойностите на тези изрази за посочените стойности на аргументите:
Въведение в темата на урока, представяне на нов материал (30 минути)
Продължаваме да изучаваме основите на логиката и темата на днешния ни урок е „Решаване на логически уравнения“. След изучаването на тази тема ще научите основните начини за решаване на логически уравнения, ще придобиете умения за решаване на тези уравнения с помощта на езика на логическата алгебра и способността да съставяте логически израз с помощта на таблица на истината.
1. Решете логическо уравнение
(¬K M) → (¬L М N) =0
Напишете отговора си като низ от четири знака: стойностите на променливите K, L, M и N (в този ред). Така, например, ред 1101 съответства на факта, че K=1, L=1, M=0, N=1.
Решение:
Нека трансформираме израза(¬K M) → (¬L М Н)
Един израз е неверен, когато и двата термина са неверни. Вторият член е равен на 0, ако M =0, N =0, L =1. В първия член K = 0, тъй като M = 0 и 
.
Отговор: 0100
2. Колко решения има уравнението (посочете само числото в отговора си)?
Решение: преобразувайте израза
(A +B )*(C +D )=1
A +B =1 и C +D =1
Метод 2: съставяне на таблица на истината
3 начина: изграждане на SDNF - перфектна дизюнктивна нормална форма за функция - дизюнкция на пълни редовни елементарни конюнкции.Нека трансформираме оригиналния израз, отваряме скобите, за да получим дизюнкцията на съюзите:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Нека допълним съюзите до пълни съюзи (произведението на всички аргументи), отворете скобите:
Нека вземем предвид същите връзки:
В резултат на това получаваме SDNF, съдържащ 9 конюнкции. Следователно таблицата на истината за тази функция има стойност 1 в 9 реда от 2 4 =16 набора от стойности на променливи.
3. Колко решения има уравнението (посочете само числото в отговора си)?
Нека опростим израза:
,
3 начина: изграждане на SDNF
Нека вземем предвид същите връзки:
В резултат на това получаваме SDNF, съдържащ 5 конюнкции. Следователно таблицата на истината за тази функция има стойност 1 на 5 реда от 2 4 =16 набора от стойности на променливи.
Конструиране на логически израз с помощта на таблица на истината:
за всеки ред от таблицата на истината, съдържащ 1, съставяме произведение от аргументи и променливи, равни на 0, се включват в произведението с отрицание, а променливи, равни на 1, се включват без отрицание. Желаният израз F ще бъде съставен от сумата на получените продукти. След това, ако е възможно, този израз трябва да бъде опростен.
Пример: дадена е таблица на истинност на израз. Конструирайте логически израз.
Решение:3. Домашна работа (5 минути)
Решете уравнението:
Колко решения има уравнението (посочете само числото в отговора си)?
Използвайки дадена таблица на истинност, съставете логически израз и
опростете го.