Temat lekcji: Rozwiązanie równania logiczne
Edukacyjne – poznawanie metod rozwiązywania równań logicznych, rozwijanie umiejętności rozwiązywania równań logicznych i konstruowania wyrażeń logicznych z wykorzystaniem tabeli prawdy;Rozwojowe - stworzyć warunki do rozwoju zainteresowanie poznawcze uczniom, sprzyjają rozwojowi pamięci, uwagi, logiczne myślenie;
Edukacyjny : promowanie umiejętności słuchania opinii innych, pielęgnowanie woli i wytrwałości w osiąganiu końcowych rezultatów.
Typ lekcji: lekcja łączona
Sprzęt: komputer, rzutnik multimedialny, prezentacja 6.
Postęp lekcji
Powtarzanie i aktualizacja podstawowej wiedzy. Badanie praca domowa(10 minut)
Na poprzednich lekcjach zapoznaliśmy się z podstawowymi prawami algebry logicznej i nauczyliśmy się wykorzystywać te prawa do upraszczania wyrażeń logicznych.
Sprawdźmy naszą pracę domową dotyczącą upraszczania wyrażeń logicznych:
1. Które z poniższych słów spełnia warunek logiczny:
(pierwsza spółgłoska litera → druga spółgłoska litera)٨ (samogłoska ostatniej litery → samogłoska przedostatniej litery)? Jeżeli jest kilka takich słów, wskaż najmniejsze z nich.
1) ANNA 2) MARIA 3) OLEG 4) STEPAN
Wprowadźmy następującą notację:
A – spółgłoska pierwszej litery
B – spółgłoska drugiej litery
S – samogłoska ostatniej litery
D – przedostatnia litera samogłoski
Zróbmy wyrażenie:
Zróbmy tabelę:
2. Wskaż, które wyrażenie logiczne jest równoważne wyrażeniu
Uprośćmy zapis oryginalnego wyrażenia i proponowanych opcji:
3. Biorąc pod uwagę fragment tabeli prawdy wyrażenia F:
Które wyrażenie pasuje do F?
Określmy wartości tych wyrażeń dla określonych wartości argumentów:
Wprowadzenie do tematu lekcji, prezentacja nowego materiału (30 minut)
Kontynuujemy naukę podstaw logiki, a tematem naszej dzisiejszej lekcji jest „Rozwiązywanie równań logicznych”. Po przestudiowaniu tego tematu poznasz podstawowe metody rozwiązywania równań logicznych, zdobędziesz umiejętności rozwiązywania tych równań z wykorzystaniem języka algebry logicznej oraz umiejętność komponowania wyrażenia logicznego z wykorzystaniem tabeli prawdy.
1. Rozwiąż równanie logiczne
(¬K M) → (¬L M N) =0
Zapisz swoją odpowiedź jako ciąg czterech znaków: wartości zmiennych K, L, M i N (w tej kolejności). I tak np. linia 1101 odpowiada faktowi, że K=1, L=1, M=0, N=1.
Rozwiązanie:
Przekształćmy wyrażenie(¬K M) → (¬L M N)
Wyrażenie jest fałszywe, gdy oba wyrazy są fałszywe. Drugi wyraz jest równy 0, jeśli M =0, N =0, L =1. W pierwszym terminie K = 0, ponieważ M = 0, i 
.
Odpowiedź: 0100
2. Ile rozwiązań ma równanie (w odpowiedzi wpisz tylko liczbę)?
Rozwiązanie: przekształć wyrażenie
(A +B)*(C +D)=1
A +B =1 i C +D =1
Metoda 2: sporządzenie tabeli prawdy
3 sposoby: konstrukcja SDNF - doskonałej rozłącznej postaci normalnej funkcji - alternatywy pełnych regularnych elementarnych koniunkcji.Przekształćmy pierwotne wyrażenie, otwórzmy nawiasy, aby uzyskać alternatywę spójników:
(A+B)*(C+D)=A*C+B*C+A*D+B*D=
Uzupełnijmy spójniki, aby uzupełnić spójniki (iloczyn wszystkich argumentów), otwórz nawiasy:
Weźmy pod uwagę te same spójniki:
W rezultacie otrzymujemy SDNF zawierający 9 spójników. Dlatego tablica prawdy dla tej funkcji ma wartość 1 w 9 wierszach po 2 4 = 16 zestawów wartości zmiennych.
3. Ile rozwiązań ma równanie (w odpowiedzi wpisz tylko liczbę)?
Uprośćmy wyrażenie:
,
3 sposoby: budowa SDNF
Weźmy pod uwagę te same spójniki:
W rezultacie otrzymujemy SDNF zawierający 5 spójników. Dlatego tablica prawdy dla tej funkcji ma wartość 1 w 5 wierszach po 2 4 = 16 zestawów wartości zmiennych.
Konstruowanie wyrażenia logicznego przy użyciu tabeli prawdy:
dla każdego wiersza tabeli prawdy zawierającego 1, tworzymy iloczyn argumentów, a zmienne równe 0 włączamy do iloczynu z negacją, a zmienne równe 1 uwzględniamy bez negacji. Pożądane wyrażenie F będzie składać się z sumy otrzymanych produktów. Następnie, jeśli to możliwe, wyrażenie to należy uprościć.
Przykład: podana jest tabela prawdy wyrażenia. Zbuduj wyrażenie logiczne.
Rozwiązanie:3. Praca domowa (5 minut)
Rozwiąż równanie:
Ile rozwiązań ma równanie (w odpowiedzi wpisz tylko liczbę)?
Korzystając z podanej tabeli prawdy, skonstruuj wyrażenie logiczne i
uprościć to.
Rozwiązywanie układów równań logicznych poprzez zmianę zmiennych
Metodę podstawienia zmiennych stosuje się wówczas, gdy niektóre zmienne włącza się do równań jedynie w postaci określonego wyrażenia i nic więcej. Następnie wyrażenie to można oznaczyć nową zmienną.
Przykład 1.
Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, x5, x6, x7, x8, które spełniają wszystkie poniższe warunki?
(x1 → x2) → (x3 → x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Odpowiedź nie wymaga wymieniania wszystkich różnych zbiorów wartości zmiennych x1, x2, x3, x4, x5, x6, x7, x8, dla których spełniony jest ten układ równości. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Następnie możemy zapisać układ w postaci pojedynczego równania:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Koniunkcja wynosi 1 (prawda), gdy każdy operand przyjmuje wartość 1. Oznacza to, że każda z implikacji musi być prawdziwa i dotyczy to wszystkich wartości z wyjątkiem (1 → 0). Te. w tabeli wartości zmiennych y1, y2, y3, y4 nie należy znajdować się na lewo od zera:
Te. warunki są spełnione dla 5 serii y1-y4.
Ponieważ y1 = x1 → x2, wówczas wartość y1 = 0 osiągana jest na pojedynczym zestawie x1, x2: (1, 0), a wartość y1 = 1 – na trzech zbiorach x1, x2: (0,0) , (0 ,1), (1.1). Podobnie dla y2, y3, y4.
Ponieważ każdy zbiór (x1,x2) dla zmiennej y1 jest łączony z każdym zbiorem (x3,x4) dla zmiennej y2 itd., to liczby zbiorów zmiennych x są mnożone:
|
Liczba zestawów na x1…x8 |
||||
Dodajmy liczbę zestawów: 1 + 3 + 9 + 27 + 81 = 121.
Odpowiedź: 121
Przykład 2.
Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, ... x9, y1, y2, ... y9, które spełniają wszystkie wymienione poniżej warunki?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
W odpowiedzi nie ma potrzeby wymień wszystkie różne zbiory wartości zmiennych x1, x2, ... x9, y1, y2, ... y9, dla których spełniony jest dany układ równości. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
Dokonajmy zmiany zmiennych:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Układ można zapisać w postaci pojedynczego równania:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Równoważność jest prawdziwa tylko wtedy, gdy oba operandy są równe. Istnieją dwa zestawy rozwiązań tego równania:
| 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 |
Ponieważ zi = (xi ≡ yi), wówczas wartość zi = 0 odpowiada dwóm zbiorom (xi,yi): (0,1) i (1,0), a wartość zi = 1 odpowiada dwóm zbiorom (xi,yi ): (0,0) i (1,1).
Wtedy pierwszy zbiór z1, z2,…, z9 odpowiada 2 9 zbiorom (x1,y1), (x2,y2),…, (x9,y9).
Ta sama liczba odpowiada drugiemu zestawowi z1, z2,…, z9. Zatem jest w sumie 2 9 +2 9 = 1024 zestawy.
Odpowiedź: 1024
Rozwiązywanie układów równań logicznych metodą wizualnego wyznaczania rekurencji.
Metodę tę stosuje się, jeśli układ równań jest dość prosty i kolejność zwiększania liczby zbiorów przy dodawaniu zmiennych jest oczywista.
Przykład 3.
Ile różnych rozwiązań ma układ równań?
¬x9 ∨ x10 = 1,
gdzie x1, x2, … x10 to zmienne logiczne?
Odpowiedź nie wymaga wymieniania wszystkich różnych zbiorów wartości x1, x2, ... x10, dla których spełniony jest ten układ równości. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
Rozwiążmy pierwsze równanie. Dysjunkcja jest równa 1, jeśli przynajmniej jeden z jej argumentów jest równy 1. To znaczy rozwiązaniami są zbiory:
Dla x1=0 istnieją dwie wartości x2 (0 i 1), a dla x1=1 istnieje tylko jedna wartość x2 (1), tak że zbiór (x1,x2) jest rozwiązaniem równania. W sumie są 3 komplety.
Dodajmy zmienną x3 i rozważmy drugie równanie. Jest ona podobna do pierwszej, co oznacza, że dla x2=0 istnieją dwie wartości x3 (0 i 1), a dla x2=1 tylko jedna wartość x3 (1), tak że zbiór (x2 ,x3) jest rozwiązaniem równania. W sumie są 4 komplety.
Łatwo zauważyć, że dodając kolejną zmienną, dodawany jest jeden zbiór. Te. rekurencyjny wzór na liczbę zbiorów (i+1) zmiennych:
N i +1 = N i + 1. Wtedy dla dziesięciu zmiennych otrzymujemy 11 zbiorów.
Odpowiedź: 11
Rozwiązywanie układów równań logicznych różnych typów
Przykład 4.
Ile jest różnych zbiorów wartości zmiennych logicznych x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4, które spełniają wszystkie poniższe warunki ?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → r 2) ∧ (y 2 → r 3) ∧ (y 3 → r 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
W odpowiedzi nie ma potrzeby wymień wszystkie różne zbiory wartości zmiennych x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, dla których spełniony jest dany układ równości .
W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
Należy zauważyć, że trzy równania układu są takie same dla różnych niezależnych zbiorów zmiennych.
Spójrzmy na pierwsze równanie. Spójnik jest prawdziwy (równy 1) tylko wtedy, gdy wszystkie jego operandy są prawdziwe (równe 1). Implikacja wynosi 1 dla wszystkich krotek z wyjątkiem (1,0). Oznacza to, że rozwiązaniem pierwszego równania będą następujące zbiory x1, x2, x3, x4, w których 1 nie leży na lewo od 0 (5 zbiorów):
Podobnie rozwiązania drugiego i trzeciego równania będą absolutnie tymi samymi zbiorami y1,…,y4 i z1,…, z4.
Przeanalizujmy teraz czwarte równanie układu: x 4 ∧ y 4 ∧ z 4 = 0. Rozwiązaniem będą wszystkie zbiory x4, y4, z4, w których przynajmniej jedna ze zmiennych jest równa 0.
Te. dla x4 = 0 odpowiednie są wszystkie możliwe zbiory (y4, z4), a dla x4 = 1 odpowiednie są zbiory (y4, z4), w których jest przynajmniej jedno zero: (0, 0), (0,1 ) , (1, 0).
|
Liczba zestawów |
||||
Całkowita liczba zestawów wynosi 25 + 4*9 = 25 + 36 = 61.
Odpowiedź: 61
Rozwiązywanie układów równań logicznych poprzez konstruowanie wzorów rekurencyjnych
Metodę konstruowania formuł rekurencyjnych stosuje się przy rozwiązywaniu złożonych układów, w których kolejność zwiększania liczby zbiorów nie jest oczywista, a zbudowanie drzewa jest niemożliwe ze względu na objętości.
Przykład 5.
Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2,...x7, y1, y2,...y7, które spełniają wszystkie poniższe warunki?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Odpowiedź nie wymaga wymieniania wszystkich różnych zbiorów wartości zmiennych x1, x2, ..., x7, y1, y2, ..., y7, dla których ten układ równości jest spełniony. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
Należy zauważyć, że pierwsze sześć równań układu jest identycznych i różni się jedynie zbiorem zmiennych. Spójrzmy na pierwsze równanie. Jego rozwiązaniem będą następujące zestawy zmiennych:
Oznaczmy:
liczba krotek (0,0) na zmiennych (x1,y1) do A 1,
liczba krotek (0,1) na zmiennych (x1,y1) do B 1,
liczba krotek (1,0) na zmiennych (x1,y1) do C 1,
liczba krotek (1,1) na zmiennych (x1,y1) do D 1 .
liczba krotek (0,0) na zmiennych (x2,y2) do A 2 ,
liczba krotek (0,1) na zmiennych (x2,y2) do B 2,
liczba krotek (1,0) na zmiennych (x2,y2) do C 2,
liczba krotek (1,1) na zmiennych (x2,y2) do D 2 .
Widzimy to z drzewa decyzyjnego
ZA 1 =0, B 1 =1, Do 1 =1, D 1 =1.
Należy zauważyć, że zbiór (0,0) na zmiennych (x2,y2) otrzymuje się ze zbiorów (0,1), (1,0) i (1,1) na zmiennych (x1,y1). Te. ZA 2 = B 1 + C 1 + D 1.
Zbiór (0,1) na zmiennych (x2,y2) otrzymuje się ze zbiorów (0,1), (1,0) i (1,1) na zmiennych (x1,y1). Te. B 2 = B 1 + C 1 + D 1.
Argumentując podobnie, zauważamy, że C 2 = B 1 + C 1 + D 1. D2 = D1.
Otrzymujemy w ten sposób powtarzające się wzory:
A ja+1 = B ja + do ja + re ja
B ja+1 = B ja + do ja + re ja
do ja+1 = b ja + do ja + re ja
re ja+1 = ZA ja + B ja + do ja + re ja
Zróbmy stół
| Zestawy | Oznaczenie. | Formuła |
Liczba zestawów |
||||||
| ja=1 | ja=2 | ja=3 | ja=4 | ja=5 | ja=6 | ja=7 | |||
| (0,0) | A ja | A i+1 =B i +C i +D ja | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B ja | B i+1 =B i +C i +D ja | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C ja | C i+1 =B i +C i +D ja | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D ja | D ja+1 =D ja | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Ostatnie równanie (x7 ∨ y7) = 1 spełniają wszystkie zbiory z wyjątkiem tych, w których x7=0 i y7=0. W naszej tabeli liczba takich zestawów wynosi A 7.
Wtedy całkowita liczba zestawów wynosi B 7 + C 7 + D 7 = 127+127+1 = 255
Odpowiedź: 255
Niech będzie funkcją logiczną n zmiennych. Równanie logiczne wygląda następująco:
Stała C ma wartość 1 lub 0.
Równanie logiczne może mieć od 0 do różnych rozwiązań. Jeżeli C jest równe 1, to rozwiązaniami są wszystkie te zbiory zmiennych z tablicy prawdy, dla których funkcja F przyjmuje wartość true (1). Pozostałe zbiory to rozwiązania równania o C równym zero. Zawsze możesz rozważyć tylko równania postaci:
Rzeczywiście, niech będzie podane równanie:
W tym przypadku możemy przejść do równoważnego równania:
Rozważmy układ k równań logicznych:
Rozwiązaniem układu jest zbiór zmiennych, dla którego spełnione są wszystkie równania układu. W zakresie funkcji logicznych, aby otrzymać rozwiązanie układu równań logicznych, należy znaleźć zbiór, na którym prawdziwa jest funkcja logiczna Ф, reprezentująca koniunkcję funkcji pierwotnych:
Jeśli liczba zmiennych jest mała, np. mniejsza niż 5, to nie jest trudno skonstruować tablicę prawdy dla tej funkcji, która pozwala nam powiedzieć, ile rozwiązań ma dany układ i jakie zbiory dostarczają rozwiązań.
W niektórych Problemy z jednolitym egzaminem państwowym aby znaleźć rozwiązania układu równań logicznych, liczba zmiennych sięga 10. Wtedy skonstruowanie tabeli prawdy staje się zadaniem prawie niemożliwym. Rozwiązanie problemu wymaga innego podejścia. Dla dowolnego układu równań nie ma metoda ogólna, różni się od brutalnej siły, która pozwala rozwiązywać takie problemy.
W zadaniach proponowanych na egzaminie rozwiązanie zazwyczaj opiera się na uwzględnieniu specyfiki układu równań. Powtarzam, poza wypróbowaniem wszystkich opcji zestawu zmiennych, nie ma ogólnego sposobu rozwiązania problemu. Rozwiązanie musi być zbudowane w oparciu o specyfikę systemu. Często przydatne jest wstępne uproszczenie układu równań przy użyciu znanych praw logiki. Inny przydatna sztuczka Rozwiązanie tego problemu jest następujące. Nie interesują nas wszystkie zbiory, a jedynie te, na których funkcja ma wartość 1. Zamiast konstruować pełny stół prawdę mówiąc, zbudujemy jego analogię - binarne drzewo decyzyjne. Każda gałąź tego drzewa odpowiada jednemu rozwiązaniu i określa zbiór, na którym funkcja ma wartość 1. Liczba gałęzi w drzewie decyzyjnym pokrywa się z liczbą rozwiązań układu równań.
Wyjaśnię, czym jest binarne drzewo decyzyjne i jak jest zbudowane na przykładach kilku problemów.
Problem 18
Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, które spełniają układ dwóch równań?
Odpowiedź: System ma 36 różnych rozwiązań.
Rozwiązanie: Układ równań zawiera dwa równania. Znajdźmy liczbę rozwiązań pierwszego równania w zależności od 5 zmiennych - . Pierwsze równanie można z kolei uznać za układ 5 równań. Jak pokazano, układ równań faktycznie reprezentuje koniunkcję funkcji logicznych. Prawdziwe jest także stwierdzenie odwrotne – koniunkcję warunków można traktować jako układ równań.
Zbudujmy drzewo decyzyjne dla implikacji () - pierwszego członu koniunkcji, który można uznać za pierwsze równanie. Tak wygląda graficzna reprezentacja tego drzewa
Drzewo składa się z dwóch poziomów w zależności od liczby zmiennych w równaniu. Pierwszy poziom opisuje pierwszą zmienną. Dwie gałęzie tego poziomu odzwierciedlają możliwe wartości tej zmiennej - 1 i 0. Na drugim poziomie gałęzie drzewa odzwierciedlają tylko te możliwe wartości zmiennej, dla których równanie ma wartość true. Ponieważ równanie określa implikację, gałąź, na której ma wartość 1, wymaga, aby na tej gałęzi znajdowała się wartość 1. Gałąź, na której ma wartość 0, generuje dwie gałęzie o wartościach równych 0 i 1. Skonstruowana drzewo określa trzy rozwiązania, z których implikacja przyjmuje wartość 1. Na każdej gałęzi zapisywany jest odpowiedni zestaw wartości zmiennych, dający rozwiązanie równania.
Te zbiory to: ((1, 1), (0, 1), (0, 0))
Kontynuujmy budowanie drzewa decyzyjnego, dodając następujące równanie i następującą implikację. Specyfika naszego układu równań polega na tym, że każde nowe równanie układu wykorzystuje jedną zmienną z poprzedniego równania, dodając jedną nową zmienną. Ponieważ zmienna ma już wartości w drzewie, to na wszystkich gałęziach, w których zmienna ma wartość 1, zmienna również będzie miała wartość 1. Dla takich gałęzi konstrukcja drzewa przechodzi na kolejny poziom, ale nowe gałęzie nie pojawiają się. Pojedyncza gałąź, w której zmienna ma wartość 0, rozgałęzi się na dwie gałęzie, w których zmienna otrzyma wartości 0 i 1. Zatem każde dodanie nowego równania, biorąc pod uwagę jego specyfikę, dodaje jedno rozwiązanie. Oryginalne pierwsze równanie:
ma 6 rozwiązań. Tak to wygląda pełne drzewo rozwiązania tego równania:
Drugie równanie naszego układu jest podobne do pierwszego:
Jedyna różnica polega na tym, że równanie wykorzystuje zmienne Y. To równanie ma również 6 rozwiązań. Ponieważ każde rozwiązanie zmienne można połączyć z każdym rozwiązaniem zmiennym całkowita liczba Istnieje 36 rozwiązań.
Należy pamiętać, że skonstruowane drzewo decyzyjne podaje nie tylko liczbę rozwiązań (według liczby gałęzi), ale także same rozwiązania zapisane na każdej gałęzi drzewa.
Problem 19
Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, które spełniają wszystkie poniższe warunki?
To zadanie jest modyfikacją poprzedniego zadania. Różnica polega na tym, że dodano kolejne równanie, które wiąże zmienne X i Y.
Z równania wynika, że gdy ma wartość 1 (istnieje jedno takie rozwiązanie), to ma wartość 1. Zatem istnieje jeden zbiór, na którym i ma wartości 1. Gdy jest równe 0, może mają dowolną wartość, zarówno 0, jak i 1. Dlatego każdy zbiór z , równy 0, a jest 5 takich zbiorów, odpowiada wszystkim 6 zbiorom ze zmiennymi Y. Zatem całkowita liczba rozwiązań wynosi 31.
Problem 20
Rozwiązanie: Pamiętając o podstawowych równoważnościach, zapisujemy nasze równanie jako:
Cykliczny łańcuch implikacji oznacza, że zmienne są identyczne, więc nasze równanie jest równoważne równaniu:
To równanie ma dwa rozwiązania, gdy wszystkie mają wartość 1 lub 0.
Zadanie 21
Ile rozwiązań ma równanie:
Rozwiązanie: Podobnie jak w zadaniu 20, przechodzimy od implikacji cyklicznych do tożsamości, przepisując równanie do postaci:
Zbudujmy drzewo decyzyjne dla tego równania:
Zadanie 22
Ile rozwiązań ma następujący układ równań?
Noskin Andriej Nikołajewicz,
nauczyciel informatyki
najwyższa kategoria kwalifikacyjna,
Kandydat nauk wojskowych, profesor nadzwyczajny
Liceum GBOU nr 1575, Moskwa
Zoptymalizowana metoda mapowania do rozwiązania problemu 23 z KIM Unified State Examination z informatyki i ICT
Jednym z najtrudniejszych zadań w egzaminie Unified State Exam KIM jest zadanie 23, w którym należy znaleźć liczbę różnych zbiorów wartości zmiennych logicznych spełniających podany warunek.
To zadanie jest chyba najtrudniejszym zadaniem KIM Unified State Examination z informatyki i ICT. Z reguły radzi sobie z tym nie więcej niż 5% zdających (1).
Tak niewielki odsetek uczniów, którzy wykonali to zadanie, tłumaczy się następująco:
- uczniowie mogą pomylić (zapomnieć) znaki operacji logicznych;
- błędy matematyczne w procesie wykonywania obliczeń;
- błędy w rozumowaniu przy poszukiwaniu rozwiązania;
- błędy w procesie upraszczania wyrażeń logicznych;
- nauczyciele zalecają rozwiązanie tego problemu po ukończeniu całej pracy, ponieważ prawdopodobieństwo
błędów jest bardzo dużo, a „waga” zadania to tylko jeden z głównych punktów.
Ponadto niektórzy nauczyciele sami mają trudności z rozwiązaniem tego typu problemów i dlatego starają się z dziećmi rozwiązywać prostsze problemy.
Sytuację komplikuje również fakt, że w tym bloku jest duża liczba różne zadania i nie ma możliwości wyboru rozwiązania szablonowego.
Aby naprawić tę sytuację, społeczność nauczycielska finalizuje dwie główne metody rozwiązywania problemów tego typu: rozwiązanie wykorzystujące łańcuchy bitów (2) i metodę mapowania (3).
Konieczność udoskonalenia (optymalizacji) tych metod wynika z faktu, że zadania stale zmieniają się zarówno pod względem struktury, jak i liczby zmiennych (tylko jeden typ zmiennych X, dwa typy zmiennych X i Y, trzy typy: X, Y , Ż.).
Trudność opanowania tych metod rozwiązywania problemów potwierdza fakt, że na stronie internetowej K.Yu. Polyakova istnieje 38 analiz tego typu problemu (4). Niektóre analizy dostarczają więcej niż jednego rodzaju rozwiązania problemu.
Ostatnio w KIM Unified State Examination z informatyki występują problemy z dwoma rodzajami zmiennych X i Y.
Zoptymalizowałem metodę wyświetlania i zachęcam moich uczniów do korzystania z ulepszonej metody.
To daje rezultaty. Odsetek moich uczniów, którzy radzą sobie z tym zadaniem, waha się w granicach 43% zdających. Z reguły co roku do Jednolitego Egzaminu Państwowego z informatyki przystępuje od 25 do 33 uczniów ze wszystkich 11. klas.
Przed pojawieniem się problemów z dwoma typami zmiennych uczniowie z powodzeniem stosowali metodę mapowania, jednak po pojawieniu się Y w wyrażeniu logicznym zaczęłam zauważać, że odpowiedzi dzieci nie pokrywały się już z testami. Okazało się, że nie byli do końca pewni, jak utworzyć tabelę odwzorowań z nowym typem zmiennej. Wtedy przyszła mi do głowy myśl, że dla wygody całe wyrażenie należy sprowadzić do jednego typu zmiennej, tak jak jest to wygodne dla dzieci.
Podam tę technikę bardziej szczegółowo. Dla wygody rozważę to na przykładzie układu wyrażeń logicznych podanego w (4).
Ile różnych rozwiązań ma układ równań logicznych?
(x 1 ^ tak 1)=(¬x 2 V ¬
y 2
)
(x 2 ^ tak 2)= (¬
X 3
V ¬
y 3
)
...
(x 5 ^ y 5)
= (¬
X 6
V ¬
y 6
)
Rozwiązanie:
1. Z analizy układu równań logicznych widzimy, że istnieje 6 zmiennych X i 6 zmiennych U. Ponieważ każda z tych zmiennych może przyjmować tylko dwie wartości (0 i 1), zastępujemy te zmienne 12 zmiennymi tego samego typu, na przykład Z.
2. Przepiszmy teraz system, dodając nowe zmienne tego samego typu. Trudność zadania będzie polegać na robieniu dokładnych notatek podczas zastępowania zmiennych.
(z 1 ^ z 2)=
(¬z 3V¬
z 4
)
(z 3 ^ z 4)=
(¬
z 5
V¬
z 6
)
...
(z 9 ^ z 10)
=
(¬
z 11
V¬
z 12)
3. Stwórzmy tabelę, w której omówimy wszystkie opcje z 1 , z 2 , z 3 , z 4 , ponieważ w pierwszym równaniu logicznym znajdują się cztery zmienne, tabela będzie miała 16 wierszy (16=2 4); usuń takie wartości z tabeli z 4 , dla którego pierwsze równanie nie ma rozwiązania (liczby przekreślone).
| 0 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | 0 |
| 1 | |||
| 1 | 0 | ||
| 1 | |||
| 1 | 0 | 0 | |
| 1 | |||
| 1 | 0 | ||
| 1 |
4. Analizując tabelę budujemy regułę wyświetlania par zmiennych (np. para Z 1 Z 2 =00 odpowiada para Z 3 Z 4 = 11) .
5. Wypełnij tabelę, obliczając liczbę par zmiennych, dla których system ma rozwiązanie. 
6. Dodaj wszystkie wyniki: 9 + 9 + 9 + 27 = 54
7. Odpowiedź: 54.
Powyższa zoptymalizowana metoda rozwiązania problemu 23 z egzaminu Unified State Exam KIM pozwoliła uczniom odzyskać pewność siebie i skutecznie rozwiązać tego typu problem.
Literatura:
1. FIPI. Zalecenia metodyczne dla nauczycieli, przygotowane na podstawie analizy typowe błędy uczestnicy Unified State Exam 2015 z zakresu INFORMATION SCIENCE i ICT. Tryb dostępu: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf
2. K.Yu. Polyakov, MA Roitberga.Układy równań logicznych: rozwiązanie za pomocą ciągów bitowych. Journal of Informatics, nr 12, 2014, s. 10-12. 4-12. Wydawnictwo„Pierwszy września”, Moskwa.3. EA Mironczik, Metoda wyświetlania. Magazyn Informatyka, nr 10, 2013, s. 10-10. 18-26. Wydawnictwo „Pierwszy września”, Moskwa.
Możesz wybrać różne sposoby rozwiązywanie układów równań logicznych. Jest to redukcja do jednego równania, konstrukcja tabeli prawdy i dekompozycja.
Zadanie: Rozwiąż układ równań logicznych:
Rozważmy metoda redukcji do jednego równania . Metoda ta polega na przekształceniu równań logicznych w taki sposób, aby ich prawe strony były równe wartości logicznej (czyli 1). Aby to zrobić, użyj operacji logicznej negacji. Następnie, jeśli równania zawierają złożone operacje logiczne, zastępujemy je podstawowymi: „AND”, „OR”, „NOT”. Kolejnym krokiem jest połączenie równań w jedno, równoważne układowi, za pomocą operacji logicznej „AND”. Następnie należy przekształcić powstałe równanie w oparciu o prawa algebry logicznej i uzyskać konkretne rozwiązanie układu.
Rozwiązanie 1: Zastosuj inwersję do obu stron pierwszego równania:
Wyobraźmy sobie implikację poprzez podstawowe operacje „LUB” i „NIE”:
Ponieważ lewe strony równań są równe 1, możemy je połączyć za pomocą operacji „AND” w jedno równanie równoważne układowi pierwotnemu:
Otwieramy pierwszy nawias zgodnie z prawem De Morgana i otrzymany wynik przekształcamy:
Otrzymane równanie ma jedno rozwiązanie: A =0, B=0 i C=1.
Następna metoda to konstruowanie tablic prawdy . Ponieważ wielkości logiczne mają tylko dwie wartości, można po prostu przejrzeć wszystkie opcje i znaleźć wśród nich te, dla których spełniony jest dany układ równań. Oznacza to, że budujemy jedną wspólną tabelę prawdy dla wszystkich równań układu i znajdujemy linię z wymaganymi wartościami.
Rozwiązanie 2: Utwórzmy tabelę prawdy dla systemu:
|
0 |
0 |
1 |
1 |
0 |
1 |
Linia, dla której spełnione są warunki zadania, została wyróżniona pogrubioną czcionką. Zatem A=0, B=0 i C=1.
Sposób rozkład . Chodzi o to, aby ustalić wartość jednej ze zmiennych (ustawić ją na 0 lub 1) i w ten sposób uprościć równania. Następnie możesz ustalić wartość drugiej zmiennej i tak dalej.
Rozwiązanie 3: Niech A = 0, wówczas:
Z pierwszego równania otrzymujemy B = 0, a z drugiego - C = 1. Rozwiązanie układu: A = 0, B = 0 i C = 1.
Na egzaminie jednolitym z informatyki bardzo często konieczne jest określenie liczby rozwiązań układu równań logicznych, bez znajdowania samych rozwiązań, są też na to pewne metody; Głównym sposobem znalezienia liczby rozwiązań układu równań logicznych jestzastąpienie zmiennych. Najpierw należy maksymalnie uprościć każde z równań w oparciu o prawa algebry logicznej, a następnie zastąpić złożone części równań nowymi zmiennymi i określić liczbę rozwiązań nowy system. Następnie wróć do zamiennika i określ liczbę rozwiązań dla niego.
Zadanie: Ile rozwiązań ma równanie (A →B) + (C →D) = 1? Gdzie A, B, C, D są zmiennymi logicznymi.
Rozwiązanie: Wprowadźmy nowe zmienne: X = A →B i Y = C →D. Biorąc pod uwagę nowe równanie zmienne zostanie zapisane w postaci: X + Y = 1.
Rozłączenie jest prawdziwe w trzech przypadkach: (0;1), (1;0) i (1;1), natomiast X i Y są implikacjami, czyli jest prawdziwe w trzech przypadkach i fałszywe w jednym. Zatem przypadek (0;1) będzie odpowiadał trzem możliwym kombinacjom parametrów. Przypadek (1;1) – będzie odpowiadał dziewięciu możliwym kombinacjom parametrów pierwotnego równania. Oznacza to, że suma możliwych rozwiązań dane równanie 3+9=15.
Następnym sposobem określenia liczby rozwiązań układu równań logicznych jest drzewo binarne. Przyjrzyjmy się tej metodzie na przykładzie.
Zadanie: Ile różnych rozwiązań ma układ równań logicznych:
Podany układ równań jest równoważny równaniu:
(X 1 → X 2 )*(X 2 → X 3 )*…*(x m -1 → x m) = 1.
Załóżmy, że X 1 – jest prawdą, to z pierwszego równania to otrzymujemy X 2 to samo prawda, od drugiego - X 3 =1 i tak dalej, aż x m= 1. Oznacza to, że zbiór (1; 1; …; 1) m jednostek jest rozwiązaniem układu. Niech to teraz X 1 =0, to z pierwszego równania, które mamy X 2 =0 lub X 2 =1.
Gdy X 2 prawda, otrzymujemy, że pozostałe zmienne są również prawdziwe, czyli zbiór (0; 1; ...; 1) jest rozwiązaniem układu. Na X 2 =0 rozumiemy to X 3 =0 lub X 3 = i tak dalej. Kontynuując ostatnią zmienną stwierdzamy, że rozwiązaniami równania są następujące zbiory zmiennych (rozwiązanie m +1, każde rozwiązanie zawiera m wartości zmiennych):
(1; 1; 1; …; 1)
(0; 1; 1; …; 1)
(0; 0; 0; …; 0)
Podejście to dobrze ilustruje konstrukcja drzewa binarnego. Liczba możliwych rozwiązań to liczba różnych gałęzi skonstruowanego drzewa. Łatwo zauważyć, że jest ono równe m +1.
|
Drzewo |
Liczba rozwiązań |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
W przypadku trudności w rozumowaniu badania i budownictworozwiązań, za pomocą których możesz szukać rozwiązania używając tablice prawdy, dla jednego lub dwóch równań.
Zapiszmy układ równań w postaci:
I utwórzmy osobno tabelę prawdy dla jednego równania:
|
x 1 |
x 2 |
(x 1 → x 2) |
Utwórzmy tabelę prawdy dla dwóch równań:
|
x 1 |
x 2 |
x 3 |
x 1 → x 2 |
x 2 → x 3 |
(x 1 → x 2) * (x 2 → x 3) |