Stosowanie równań jest szeroko rozpowszechnione w naszym życiu. Wykorzystywane są w wielu obliczeniach, budownictwie, a nawet sporcie. Człowiek używał równań w starożytności i od tego czasu ich zastosowanie tylko wzrosło. W matematyce istnieją pewne problemy poświęcone logice zdań. Do rozwiązania tego rodzaju równania niezbędna jest pewna wiedza: znajomość praw logiki zdań, znajomość tablic prawdy funkcji logicznych 1 lub 2 zmiennych, metody przekształcania wyrażeń logicznych. Ponadto konieczna jest znajomość następujących właściwości operacji logicznych: koniunkcja, alternatywa, inwersja, implikacja i równoważność.
Dowolna funkcja logiczna \ zmienne - \ może być określona przez tablicę prawdy.
Rozwiążmy kilka równań logicznych:
\ [\ rightharpoondown X1 \ vee X2 = 1 \]
\ [\ rightharpoondown X2 \ vee X3 = 1 \]
\ [\ rightharpoondown X3 \ vee X4 = 1 \]
\ [\ rightharpoondown X9 \ vee X10 = 1 \]
Zacznijmy rozwiązanie od \ [X1 \] i określmy, jakie wartości może przyjąć ta zmienna: 0 i 1. Następnie rozważmy każdą z powyższych wartości i zobaczmy, co może być w tym przypadku \ [X2. \]
Jak widać z tabeli, nasze równanie logiczne ma 11 rozwiązań.
Gdzie możesz rozwiązać równanie logiczne online?
Możesz rozwiązać równanie na naszej stronie https: // site. Darmowy solwer online pozwoli Ci rozwiązać równanie online o dowolnej złożoności w ciągu kilku sekund. Wszystko, co musisz zrobić, to po prostu wprowadzić swoje dane do solvera. Możesz również obejrzeć instrukcję wideo i dowiedzieć się, jak rozwiązać równanie na naszej stronie internetowej. A jeśli nadal masz pytania, możesz je zadać w naszej grupie Vkontakte http://vk.com/pocketteacher. Dołącz do naszego grona, zawsze chętnie Ci pomożemy.
Rozwiązywanie układów równań logicznych w sposób tabelaryczny poprzez przekształcanie wyrażeń logicznych.Ta technika opiera się na wykorzystaniu tabel prawdy i jest przeznaczona dla uczniów biegle posługujących się metodami konwersji wyrażeń logicznych. Jeśli uczniowie są słabi w tych metodach, możesz ich używać bez konwersji. (Będziemy używać przekształceń.) Aby opanować tę metodę rozwiązywania, konieczna jest znajomość właściwości podstawowych operacji logicznych: koniunkcja, alternatywa, inwersja, implikacja i równoważność.
Algorytm rozwiązywania układów równań tą metodą:
Przekształć równanie logiczne, uprość je.
Określ kolejność rozwiązywania równań w systemie, ponieważ w większości przypadków istnieje sekwencyjne rozwiązanie równań od góry do dołu (ponieważ znajdują się w systemie), ale są opcje, gdy jest to wygodniejsze, łatwiej aby rozpocząć rozwiązywanie od dołu do góry.
Zbuduj tabelę zmiennych, w której ustawisz początkowe wartości pierwszej zmiennej (lub ostatniej).
Kolejno zapisz możliwe warianty następnej zmiennej w każdy znaczenie pierwszego.
Po rozwiązaniu poprzedniego równania, przechodząc do następnego, należy zwrócić uwagę na to, jakie zmienne są używane w poprzednim i kolejnych równaniach, ponieważ wartości zmiennych uzyskane przez rozwiązanie w poprzednich równaniach są przekazywane jako opcje dla następujące równania.
Zwróć uwagę na otrzymane ilości roztworu przy przechodzeniu do następnej zmiennej, ponieważ można zidentyfikować wzorzec wzrostu roztworów.
Przykład 1.
¬ x1 ˅ x2=1
¬ x2 ˅ x3=1
¬ x3 ˅ x4=1
¬ x9 ˅ x10=1
Zacznijmy od X1 i zobaczmy jakie wartości może przyjąć ta zmienna: 0 i 1.
Następnie rozważymy każdą z tych wartości i zobaczymy, czym może być X2.
Odpowiedź: 11 rozwiązań
Przykład 2.
( xjedenx2) ˅ (¬x1˄¬x2) ˅( x1↔ x3)=1
( x2˄x3) ˅ (¬x2˄¬x3) ˅( x2↔ x4)=1
(X8˄ X9) ˅ (¬X8˄¬X9)˅ (X8↔X10) = 0
Przekształcamy według wzoru (A˄ b)˅ (¬ A ˄ ¬ b)= A↔ b
Otrzymujemy:
( x1↔ x2) (x1↔ x3) =1
( x2↔ x3) (x2↔ x4) =1
( x8↔ x9 (x8↔ x10) =0
Dla X1 = 0 - 8 roztworów
Weźmy X1 = 1 i zobaczmy, jakie wartości może przyjąć X2. Teraz dla każdego X2 zastanów się, jakie wartości może przyjąć X3 itp.
Dla X1 = 1 - 8 roztworów
Razem 8 + 8 = 16 rozwiązań
Odpowiedź. 16 rozwiązań
Przykład 3 .
¬ ( x1↔ x2) ( xjedenx3) ˄ (¬x1 ˅ ¬x3 )=0
¬ ( x2↔ x3) (x2x4) ˄ (¬x2 ˅ ¬x4)=0
….
¬ ( x8↔ x9 (xosiemx10) ˄ (¬x8 ˅ ¬x10)=0
Po przekształceniach (A˅ b) ˄(¬ A ˅¬ b)= ¬( A ↔ b)
otrzymujemy:
¬ ( x1↔ x2) ˄ ¬ (x1↔ x3)=0
¬ ( x2↔ x3) ˄ ¬ (x2↔ x4)=0
…..
¬ ( x8↔ x9) ˄ ¬ (x8↔ x10)=0
Weźmy X1 = 0 i zobaczmy jakie wartości może przyjąć X2. Teraz dla każdego X2 zastanów się, jakie wartości może przyjąć X3 itp.
Okazało się, że 10 rozwiązań dla X1 = 0
Zrobimy to samo dla X1 = 1. Dostajemy również 10 rozwiązań
Razem: 10 + 10 = 20
Odpowiedź: 20 rozwiązań.
Przykład 4.
(X1 ˄ X2) ˅ (¬X1 ˄ ¬X2) ˅ (X2 ˄ X3) ˅ (¬X2 ˄¬ X3)=1
(X2 ˄ X3) ˅ (¬X2 ˄ ¬X3) ˅ (X3˄ X4) ˅ (¬X3 ˄¬X4) = 1
….
(X8 ˄ X9) ˅ (¬X8˄ ¬X9) ˅ (X9 ˄ X10) ˅ (¬X9 ˄¬ X10) = 0
Przekształćmy przez formuły. (A˄ b)˅ (¬ A ˄ ¬ b)= A↔ b... Otrzymujemy:
(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
Zacznijmy od końca, ponieważ w ostatnim równaniu zmienne są jednoznacznie określone.
Niech X10 = 0, następnie X9 = 1, X8 = 0, X7 = 0, X6 = 0, a następujące zmienne mogą przyjmować różne wartości. Rozważymy każdy.
Łącznie 21 rozwiązań dla X10 = 0
Rozważmy teraz dla X10 = 1. Dostajemy również 21 rozwiązań
Razem: 21 + 21 = 42
Odpowiedź: 42 rozwiązania
Przykład 5.
( xjedenx2) ˅ (¬x1 ˄ ¬x2) ˅ (¬x3x4 (x3 ˄ ¬x4)=1
( x3x4) ˅ (¬x3 ˄ ¬x4) ˅ (¬x5x6) (x5 ˄ ¬x6)=1
( x5x6) ˅ (¬x5 ˄ ¬x6) ˅ (¬x7 dnixosiem (x7 ˄ ¬x8)=1
( x7 dnix8) ˅ (¬x7 ˄ ¬x8) ˅ (¬ x9x10 (x9˄ ¬x10) =1
Przekształćmy według wzorów:(¬ A ˄ b) ˅ ( A ˄ ¬ b)= A↔ ¬ b
( A˄ b)˅ (¬ A ˄ ¬ b)= A↔ b
( x1↔ x2) (x3 ↔ ¬x4)=1
( x3↔ x4 (x5 ↔ ¬x6)=1
( x5↔ x6) (x7 ↔ ¬x8)=1
( x7↔ xosiem (x9 ↔ ¬x10)=1
Zastanówmy się, jakie wartości mogą przyjąć X1 i X2: (0,0), (0,1), (1,0), (1,1).
Rozważmy każdą opcję i zobaczmy, jakie wartości mogą przyjąć X3, X4.
Zaczynając od X7, X8, natychmiast zapiszemy liczbę rozwiązań, ponieważ od razu wiadomo, że gdy wartości są takie same (1,1) i (0,0), to następujące zmienne mają 4 rozwiązania, a gdy różne (0,1) i (1 , 0) - 2 rozwiązania.
Razem: 80 + 80 + 32 = 192
Odpowiedź: 192 rozwiązania
Przykład 6.
(X1↔ X2) ˅ (X2 ↔X3) = 1
(X2↔ X3) ˅ (X3↔X4) = 1
(X3↔ X4) ˅ (X4 ↔X5) = 1
….
(X8↔ X9) ˅ (X9 ↔X10) = 1
Weźmy X1 = 0 i zobaczmy jakie wartości może przyjąć X2. Teraz dla każdego X2 zastanów się, jakie wartości może przyjąć X3 itp.
Widzimy pewną prawidłowość: liczba kolejnych decyzji jest równa sumie dwóch poprzednich.
To samo dla X1 = 1 otrzymujemy 89 rozwiązań
Razem: 89 + 89 = 178 rozwiązań
Odpowiedź: 178 rozwiązań
Rozwiążmy to jeszcze w jeden sposób
(X1↔ X2) ˅ (X2 ↔X3) = 1
(X2↔ X3) ˅ (X3↔X4) = 1
(X3↔ X4) ˅ (X4 ↔X5) = 1
….
(X8↔ X9) ˅ (X9 ↔X10) = 1
Wprowadźmy zamiennik:
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)
Otrzymujemy:
TjedenT2=1
T2T3=1
T3T4=1
T4T5=1
T5T6=1
T6T7=1
T7 dniT8=1
TosiemT9=1
T9T10=1
WeźmyT1 = 1 i użyj właściwości alternatywnych:
ALE pamiętaj, że
T 1 =(X1↔X2)
T 2 =(X2↔X3) itd.
Wykorzystajmy własność równoważności i upewnijmy się, patrząc na tabelę, że
Gdy T = 1, otrzymuje się dwa rozwiązania. A gdy = 0 - jedno rozwiązanie.
Można więc policzyć liczbę jedynek i pomnożyć je przez 2+ liczbę zer. Liczenie według tego samego wzoru.
Okazuje się, że liczba jedynek = poprzednia całkowita liczba rozwiązań T, a liczba zer jest równa poprzedniej liczbie jedynek
Więc. Otrzymamy. Skoro jeden daje dwa rozwiązania, to 34 * 2 = 68 rozwiązań z jednego + 21 rozwiązań z 0.
Łącznie 89 rozwiązań dla T = 1. W podobny sposób otrzymujemy 89 rozwiązań dla T = 0
Razem 89 + 89 = 178
Odpowiedź: 178 rozwiązań
Przykład 7.
(x1 ↔ x2) (x3↔ x4) ˄ ¬ (x1 ↔ x2) ˅ ¬ (x3↔ x4)=1
(x3 ↔ x4 (x5↔ x6) ˄ ¬ (x3 ↔ x4) ˅ ¬ (x5↔ x6)=1
(x5 ↔ x6) (x7↔ x8) ˄ ¬ (x5 ↔ x6) ˅ ¬ (x7↔ x8)=1
(x7 ↔ xosiem (x9↔ x10) ˄ ¬ (x7 ↔ x8) ˅ ¬ (x9↔ x10)=1
Wprowadźmy zamiennik:
T1=(x1 ↔ x2)
T2=(x3↔ x4)
T3=(x5↔ x6)
T4=(x7 ↔ x8)
T5=(x9↔ x10)
Otrzymujemy:
(T1 ˅ T2) ˄ ¬ (T1 ˅¬ T2) = 1
(T2 ˅ T3) ˄ ¬ (T2˅¬ T3) = 1
(T3 ˅ T4) ˄ ¬ (T3 ˅¬ T4) = 1
(T4 ˅ T5) ˄ ¬ (T4˅¬ T5) = 1
Zastanów się, czym może być T:
T1
T2
T3
T4
T5
Całkowity
0
1
0
1
0
32
1
0
1
0
1
32
T K T K + 1 Oraz T K = T K + 2
Otrzymujemy: 2 5 = 32 dla T
Razem: 32 + 32 = 64
Odpowiedź: 64 rozwiązania.
Miejska Budżetowa Instytucja Oświatowa
„Szkoła średnia nr 18”
miejski okręg miejski Salavat, Republika Baszkirii
Układy równań logicznych
w zadaniach egzaminu z informatyki
Sekcja „Podstawy algebry logicznej” w zadaniach USE jest uważana za jedną z najtrudniejszych i najsłabiej rozwiązanych. Średni odsetek realizacji zadań na ten temat jest najniższy i wynosi 43,2.
| Sekcja kursu | Średni procent ukończenia według grupy zadaniowej |
| Kodowanie informacji i mierzenie ich ilości | |
| Modelowanie informacji | |
| Systemy liczbowe | |
| Podstawy algebry Boole'a | |
| Algorytmizacja i programowanie | |
| Podstawy technologii informacyjno-komunikacyjnych |
W oparciu o specyfikację CMM 2018, blok ten zawiera cztery zadania o różnym stopniu trudności.
| № zadania | W kratkę elementy treści | Poziom trudności zadania |
| Umiejętność budowania tabel prawdy i diagramów logicznych | ||
| Możliwość wyszukiwania informacji w Internecie | ||
| Znajomość podstawowych pojęć i praw logika matematyczna | ||
| Umiejętność budowania i przekształcania wyrażeń logicznych |
Zadanie 23 ma najwyższy poziom trudności, dlatego ma najniższy procent ukończenia. Wśród przygotowanych absolwentów (81-100 punktów) 49,8% tych, którzy go ukończyli, średnio przygotowani (61-80 punktów) radzi sobie o 13,7%, pozostała grupa studentów nie wywiązuje się z tego zadania.
Powodzenie rozwiązania układu równań logicznych zależy od znajomości praw logiki i trafnego zastosowania metod rozwiązywania układu.
Rozważ rozwiązanie układu równań logicznych metodą mapowania.
(23.154 Polyakov K.Yu.) Ile różnych rozwiązań ma układ równań?
((x1 tak1 ) (x2 tak2 )) (x1 x2 ) (y1 tak2 ) =1
((x2 tak2 ) (x3 tak3 )) (x2 x3 ) (y2 tak3 ) =1
((x7 tak7 ) (x8 tak8 )) (x7 x8 ) (tak7 tak8 ) =1
gdzie x1 , x2 ,…, x8, w1 , w2 , ..., tak8 - zmienne logiczne? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości zmiennych, dla których obowiązuje ta równość. W odpowiedzi musisz podać liczbę takich zestawów.
Rozwiązanie... Wszystkie równania zawarte w systemie są tego samego typu, a każde równanie zawiera cztery zmienne. Znając x1 i y1, możemy znaleźć wszystkie możliwe wartości x2 i y2, które spełniają pierwsze równanie. Argumentując w podobny sposób, ze znanych x2 i y2 możemy znaleźć x3, y3 spełniające drugie równanie. Czyli znając parę (x1, y1) i określając wartość pary (x2, y2), znajdziemy parę (x3, y3), która z kolei doprowadzi do pary (x4, y4) i tak dalej.
Znajdźmy wszystkie rozwiązania pierwszego równania. Można to zrobić na dwa sposoby: zbudować tabelę prawdy, poprzez rozumowanie i zastosowanie praw logiki.
Tabela prawdy:
| x 1 r 1 | x 2 r 2 | (x 1 y 1) (x 2 y 2) | (x 1 x 2) | (y 1 y 2) | (x 1 x 2) (y 1 y 2) | |||||
Budowa tabeli prawdy jest pracochłonna i nieefektywna w czasie, dlatego stosujemy drugą metodę - logiczne rozumowanie. Iloczyn wynosi 1 wtedy i tylko wtedy, gdy każdy czynnik wynosi 1.
(x1 tak1 ) (x2 tak2 ))=1
(x1 x2 ) =1
(tak1 tak2 ) =1
Rozważ pierwsze równanie. Sekwencja wynosi 1, gdy 0 0, 0 1, 1 1, więc (x1 y1) = 0 dla (01), (10), to para (x2 tak2 ) może być dowolny (00), (01), (10), (11), a dla (x1 y1) = 1, czyli (00) i (11), para (x2 y2) = 1 przyjmuje te same wartości (00) i (11). Wykluczamy z tego rozwiązania te pary, dla których równanie drugie i trzecie są fałszywe, czyli x1 = 1, x2 = 0, y1 = 1, y2 = 0.
| (x1 , tak1 ) | (x2 , tak2 ) |
Całkowita liczba par wynosi 1 + 1 + 1 + 22 = 25
2) (23.160 Polyakov K.Yu.) Ile różnych rozwiązań ma układ równań logicznych
(x 1 (x 2 tak 2 )) (y 1 tak 2 ) = 1
(x 2 (x 3 tak 3 )) (y 2 tak 3 ) = 1
...
( x 6 ( x 7 tak 7 )) ( tak 6 tak 7 ) = 1
x 7 tak 7 = 1
Rozwiązanie. 1) Równania są tego samego typu, dlatego metodą rozumowania znajdujemy wszystkie możliwe pary (x1, y1), (x2, y2) pierwszego równania.
(x1 (x2 tak2 ))=1
(tak1 tak2 ) = 1
Rozwiązaniem drugiego równania są pary (00), (01), (11).
Znajdźmy rozwiązania pierwszego równania. Jeśli x1 = 0, to x2, y2 - dowolne, jeśli x1 = 1, to x2, y2 przyjmuje wartość (11).
Zróbmy połączenia między parami (x1, y1) i (x2, y2).
| (x1 , tak1 ) | (x2 , tak2 ) |
Stwórzmy tabelę, aby obliczyć liczbę par na każdym etapie.
| 0 |
|||||||
Uwzględnienie rozwiązań ostatniego równania x 7 tak 7 = 1, wyklucz parę (10). Znajdź całkowitą liczbę rozwiązań 1 + 7 + 0 + 34 = 42
3)(23.180) Ile różnych rozwiązań ma układ równań logicznych?
(x1 x2 ) (x3 x4 ) = 1
(x3 x4 ) (x5 x6 ) = 1
(x5 x6 ) (x7 x8 ) = 1
(x7 x8 ) (x9 x10 ) = 1
x1 x3 x5 x7 x9 = 1
Rozwiązanie. 1) Równania są tego samego typu, dlatego metodą rozumowania znajdujemy wszystkie możliwe pary (x1, x2), (x3, x4) pierwszego równania.
(x1 x2 ) (x3 x4 ) = 1
Wykluczamy z rozwiązania pary, które w ciągu dają 0 (1 0), są to pary (01, 00, 11) i (10).
Zróbmy połączenia między parami (x1, x2), (x3, x4)
Niniejszy materiał zawiera prezentację, która przedstawia metody rozwiązywania równań logicznych i układów równań logicznych w zadaniu B15 (№ 23, 2015) Zunifikowanego Egzaminu Państwowego z Informatyki. Wiadomo, że to zadanie jest jednym z najtrudniejszych spośród zadań egzaminu. Prezentacja może być przydatna podczas prowadzenia lekcji na temat „Logika” na zajęciach specjalistycznych, a także w przygotowaniu do zdania egzaminu.
Ściągnij:
Zapowiedź:
Aby skorzystać z podglądu prezentacji, załóż sobie konto Google (konto) i zaloguj się do niego: https://accounts.google.com
Podpisy slajdów:
Rozwiązanie zadania B15 (układy równań logicznych) MP Vishnevskaya, MAOU „Gimnasium nr 3” 18 listopada 2013 r., Saratów
Zadanie B15 jest jednym z najtrudniejszych na egzaminie z informatyki !!! Testowane są umiejętności: przekształcenia wyrażeń zawierających zmienne logiczne; opisać w języku naturalnym zbiór wartości zmiennych logicznych, dla których dany zbiór zmiennych logicznych jest prawdziwy; policz liczbę zestawów binarnych, które spełniają określone warunki. Najtrudniejsza rzecz, bo nie ma żadnych formalnych zasad, jak to zrobić, wymagane jest zgadywanie.
Bez czego nie możesz się obejść!
Bez czego nie możesz się obejść!
Legenda koniunkcja: A / \ B, A B, AB, A & B, A i B alternatywa: A \ / B, A + B, A | B, A lub B negacja: A, A, nie jest odpowiednikiem A: A B, A B, A B wyłączne "lub": A B, A xor B
Metoda zmiany zmiennej Ile jest różnych zestawów wartości zmiennych logicznych x1, x2, ..., x9, x10, które spełniają wszystkie poniższe warunki: ((x1 ≡ x2) \ / (x3 ≡ x4)) / \ (¬ (x1 ≡ x2) \ / ¬ (x3 ≡ x4)) = 1 ((x3 ≡ x4) \ / (x5 ≡ x6)) / \ (¬ (x3 ≡ x4) \ / ¬ (x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \ / (x7 ≡ x8)) / \ (¬ (x5 ≡ x7) \ / ¬ (x7 ≡ x8)) = 1 ((x7 ≡ x8) \ / (x9 ≡ x10)) / \ (¬ (x7 ≡ x8) \ / ¬ (x9 ≡ x10)) = 1 Odpowiedź nie musi wymieniać wszystkich różnych zbiorów x1, x2, ..., x9, x10, w ramach których dany układ równości jest spełniony. W odpowiedzi należy podać ilość takich zestawów (wersja demo 2012)
Rozwiązanie Krok 1. Uprość, zmieniając zmienne t1 = x1 x2 t2 = x3 x4 t3 = x5 x6 t4 = x7 x8 t5 = x9 x10 Po uproszczeniu: (t1 \ / t2) / \ (¬t1 \ / ¬ t2) = 1 (t2 \ / t3) / \ (¬t2 \ / ¬ t3) = 1 (t3 \ / t4) / \ (¬t3 \ / ¬ t4) = 1 (t4 \ / t5) / \ ( ¬ t4 \ / ¬ t5) = 1 Rozważ jedno z równań: (t1 \ / t2) / \ (¬t1 \ / ¬ t2) = 1 Oczywiście = 1 tylko wtedy, gdy jedna ze zmiennych wynosi 0, a druga 1 Użyjmy wzoru, aby wyrazić operację XOR w postaci koniunkcji i alternatywy: (t1 \ / t2) / \ (¬t1 \ / ¬ t2) = t1 t2 = ¬ (t1 ≡ t2) = 1 ¬ (t1 ≡ t2) = 1 ¬ ( t2 ≡ t3) = 1 ¬ (t3 ≡ t4) = 1 ¬ (t4 ≡ t5) = 1
Krok 2. Analiza systemu ¬ (t1 ≡ t2) = 1 ¬ (t2 ≡ t3) = 1 ¬ (t3 ≡ t4) = 1 ¬ (t4 ≡ t5) = 1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .Do. tk = x2k-1 ≡ x2k (t1 = x1 x2,….), to każda wartość tk odpowiada dwóm parom wartości x2k-1 i x2k, np.: tk = 0 odpowiada dwóm parom - (0 ,1) i (1, 0), a tk = 1 są parami (0,0) i (1,1).
Krok 3. Liczenie liczby rozwiązań. Każdy t ma 2 rozwiązania, liczba t - 5. Tak więc. dla zmiennych t mamy 2 5 = 32 rozwiązania. Ale każde t odpowiada parze rozwiązań x, tj. oryginalny system ma 2 * 32 = 64 rozwiązania. Odpowiedź: 64
Metoda eliminacji części rozwiązań Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2,…, x5, y1, y2,…, y5, które spełniają wszystkie następujące warunki: (x1 → x2) ∧ (x2 → x3) ∧ (x3 → x4 ) ∧ (x4 → x5) = 1; (y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) ∧ (y4 → y5) = 1; y5 → x5 = 1. Odpowiedź nie musi wymieniać wszystkich różnych zbiorów x1, x2,…, x5, y1, y2,…, y5, dla których dany układ równości jest spełniony. Jako odpowiedź musisz podać liczbę takich zestawów.
Rozwiązanie. Krok 1. Sekwencyjne rozwiązanie równań х1 1 0 х2 1 0 1 х3 1 0 1 1 х4 1 0 1 1 1 х5 1 0 1 1 1 1 Pierwsze równanie jest koniunkcją kilku operacji implikacji, jest równe 1, tj. każda z implikacji jest prawdziwa. Implikacja jest fałszywa tylko w jednym przypadku, gdy 1 0, we wszystkich pozostałych przypadkach (0 0, 0 1, 1 1) operacja zwraca 1. Zapiszmy to w formie tabeli:
Krok 1. Sekwencyjne rozwiązanie T.®. Otrzymano 6 zestawów rozwiązań dla x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Argumentując w podobny sposób dochodzimy do wniosku, że dla y1, y2, y3, y4, y5 istnieje ten sam zbiór rozwiązań. Bo równania te są niezależne, tj. nie mają wspólnych zmiennych, to rozwiązaniem tego układu równań (bez uwzględnienia trzeciego równania) będzie 6 * 6 = 36 par „x” i „igrykov”. Rozważmy trzecie równanie: y5 → x5 = 1 Rozwiązaniem są pary: 0 0 0 1 1 1 Nie jest rozwiązaniem do pary: 1 0
Porównajmy otrzymane rozwiązania, gdzie y5 = 1, x5 = 0 nie pasuje. takie pary 5. Liczba rozwiązań układu: 36-5 = 31. Odpowiedź: 31 Kombinatoryka była potrzebna !!!
Dynamiczna metoda programowania Ile różnych rozwiązań ma równanie logiczne x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, gdzie x 1, x 2,…, x 6 są zmiennymi logicznymi? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości zmiennych, dla których obowiązuje ta równość. W odpowiedzi należy podać ilości takich zestawów.
Rozwiązanie Krok1. Analiza warunku Po lewej stronie w równaniu operacje implikacji są zapisywane sekwencyjnie, priorytet jest taki sam. Przepiszmy: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Uwaga! Każda następna zmienna nie zależy od poprzedniej, ale od wyniku poprzedniej implikacji!
Krok 2. Ujawnienie wzoru Rozważmy pierwszą implikację, X 1 → X 2. Tablica prawdy: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jednego 0 otrzymaliśmy 2 jednostki, a z 1 mamy dostałem jedno 0 i jedno 1. Tylko jedno 0 i trzy 1, to jest wynik pierwszej operacji.
Krok 2. Odsłonięcie wzorca Po połączeniu x 3 z wynikiem pierwszej operacji otrzymujemy: F (x 1, x 2) x 3 F (x 1, x 2) x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Z dwóch zer - dwa 1, z każdego 1 (jest ich 3) po jednym 0 i 1 (3 + 3)
Krok 3. Wyprowadzenie wzoru. możesz pisać wzory do obliczania liczby zer N i i liczby jednostek E i dla równania z i zmiennymi:,
Krok 4. Wypełnianie tabeli Wypełnijmy tabelę od lewej do prawej dla i = 6, obliczając liczbę zer i jedynek zgodnie z powyższymi wzorami; tabela pokazuje jak zbudowana jest następna kolumna według poprzedniej: liczba zmiennych 1 2 3 4 5 6 liczba zer N i 1 1 3 5 11 21 liczba jednostek E i 1 2 * 1 + 1 = 3 2 * 1 + 3 = 5 11 21 43 Odpowiedź: 43
Metoda wykorzystująca uproszczenia wyrażeń logicznych Ile różnych rozwiązań ma równanie ((J → K) → (M N L)) ((M N L) → (¬ J K)) (M → J) = 1 gdzie J, K, L, M, N są zmiennymi boolowskimi? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości J, K, L, M i N, dla których obowiązuje ta równość. W odpowiedzi musisz podać liczbę takich zestawów.
Rozwiązanie Zauważ, że J → K = ¬ J K Wprowadź zmianę zmiennych: J → K = A, M N L = B Przepisz równanie uwzględniając zmianę: (A → B) (B → A) (M → J) = 1 4. (A B) (M → J) = 1 5. Oczywiście A B dla tych samych wartości A i B 6. Rozważ ostatnią implikację M → J = 1 Jest to możliwe, jeśli: M = J = 0 M = 0, J = 1 M = J = 1
Rozwiązanie Ponieważ A B, wtedy Dla M = J = 0 otrzymujemy 1 + K = 0. Nie ma rozwiązań. Dla M = 0, J = 1 otrzymujemy 0 + K = 0, K = 0, a N i L są dowolne, 4 rozwiązania: ¬ J K = M N LKNL 0 0 0 0 0 1 0 1 0 0 1 jeden
Rozwiązanie 10. Przy M = J = 1 otrzymujemy 0 + K = 1 * N * L lub K = N * L, 4 rozwiązania: 11. Suma ma 4 + 4 = 8 rozwiązań Odpowiedź: 8 KNL 0 0 0 0 0 1 0 1 0 1 1 1
Źródła informacji: O.B. Bogomolova, D.Yu. Usenkow. В15: nowe zadania i nowe rozwiązanie Informatyka, nr 6, 2012, s. 35 - 39. K.Yu. Poliakow. Równania logiczne // Informatyka, nr 14, 2011, s. 30-35. http://ege-go.ru/zadania/grb/b15/, [Zasoby elektroniczne]. http://kpolyakov.narod.ru/school/ege.htm, [Zasoby elektroniczne].
Istnieją różne sposoby rozwiązywania układów równań logicznych. Jest to redukcja do jednego równania, budowanie i dekompozycja tabeli prawdy.
Zadanie: Rozwiąż układ równań logicznych:
Rozważać 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). W tym celu wykorzystywana jest operacja logicznej negacji. Następnie, jeśli w równaniach występują złożone operacje logiczne, zastępujemy je podstawowymi: „AND”, „LUB”, „NIE”. Kolejnym krokiem jest połączenie równań w jedno, równoważne systemowi, za pomocą operacji logicznej „AND”. Następnie należy dokonać transformacji wynikowego równania w oparciu o prawa algebry logicznej i uzyskać konkretne rozwiązanie układu.
Rozwiązanie 1: Zastosuj odwrotność do obu stron pierwszego równania:
Zaprezentujmy implikację za pomocą podstawowych operacji „LUB”, „NIE”:
Ponieważ lewe strony równań są równe 1, można je połączyć za pomocą operacji „AND” w jedno równanie, które jest równoważne z oryginalnym układem:
Otwieramy pierwszy nawias zgodnie z prawem de Morgana i przekształcamy otrzymany wynik:
Otrzymane równanie ma jedno rozwiązanie: A = 0, B = 0 i C = 1.
Następnym sposobem jest budowanie tabel prawdy ... Ponieważ wartości logiczne mają tylko dwie wartości, możesz po prostu przejrzeć wszystkie opcje i znaleźć wśród nich te, dla których dany układ równań jest spełniony. Oznacza to, że budujemy jedną wspólną tabelę prawdy dla wszystkich równań w systemie i znajdujemy wiersz z wymaganymi wartościami.
Rozwiązanie 2: Skomponujmy 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ą. A więc A = 0, B = 0 i C = 1.
Sposób rozkład ... Pomysł polega na ustaleniu wartości jednej ze zmiennych (ustaw ją na 0 lub 1) i tym samym uproszczeniu równań. Następnie możesz ustalić wartość drugiej zmiennej itp.
Rozwiązanie 3: Niech A = 0, wtedy:
Z pierwszego równania otrzymujemy B = 0, a z drugiego - C = 1. Rozwiązanie systemowe: A = 0, B = 0 i C = 1.
Na egzaminie z informatyki bardzo często wymagane jest określenie liczby rozwiązań układu równań logicznych, bez znajdowania samych rozwiązań, do tego też są pewne metody. Głównym sposobem znalezienia liczby rozwiązań układu równań logicznych jestzmiana 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ń nowego układu. Następnie wróć do wymiany i określ liczbę rozwiązań dla niej.
Zadanie: Ile rozwiązań ma równanie (A → B) + (C → D) = 1? Gdzie A, B, C, D są zmiennymi boolowskimi.
Rozwiązanie: Wprowadźmy nowe zmienne: X = A → B i Y = C → D. Uwzględniając nowe zmienne, równanie zostanie zapisane jako: X + Y = 1.
Argumentacja jest prawdziwa w trzech przypadkach: (0; 1), (1; 0) i (1; 1), natomiast X i Y są implikacjami, to znaczy jest prawdziwe w trzech przypadkach i fałszywe w jednym. Dlatego 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 istnieje 3 + 9 = 15 możliwych rozwiązań tego równania.
Następnym sposobem określenia liczby rozwiązań układu równań logicznych jest drzewo binarne... Rozważmy tę metodę na przykładzie.
Zadanie: Ile różnych rozwiązań ma układ równań logicznych:
Dany układ równań jest równoważny równaniu:
(x 1 → x 2 )*(x 2 → x 3 )*…*(x m -1 → x m) = 1.
Udawajmy, że x 1 - jest prawdziwe, to z pierwszego równania otrzymujemy, że x 2 również prawda, od drugiego - x 3 = 1 i tak dalej, aż x m= 1. Czyli zbiór (1; 1;…; 1) m jednostek jest rozwiązaniem układu. Niech teraz x 1 = 0, to z pierwszego równania mamy x 2 = 0 lub x 2 =1.
Kiedy x 2 tak naprawdę otrzymujemy, że pozostałe zmienne też są prawdziwe, czyli zbiór (0; 1;…; 1) jest rozwiązaniem układu. Na x 2 = 0 otrzymujemy to x 3 = 0 lub x 3 = i tak dalej. Idąc do ostatniej zmiennej 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)
To podejście dobrze ilustruje budowanie drzewa binarnego. Liczba możliwych rozwiązań to liczba różnych gałęzi zbudowanego drzewa. Łatwo zauważyć, że jest to m +1.
|
Drzewo |
Liczba rozwiązań |
|
|
x 1 |
|
|
|
x 2 |
||
|
x 3 |
||
|
… |
W przypadku trudności w rozumowaniu niyah i budynek deszum rozwiązań, możesz szukać rozwiązania z za pomocą tablice prawdy, dla jednego lub dwóch równań.
Przepiszmy układ równań w postaci:
I skompilujmy tabelę prawdy osobno 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) |
