Jak rozwiązywać formuły logiczne. Układy równań logicznych w zadaniach egzaminu jednolitego z informatyki

Stosowanie równań jest szeroko rozpowszechnione w naszym życiu. Wykorzystuje się je w wielu obliczeniach, budowie konstrukcji, a nawet sporcie. Człowiek używał równań w czasach starożytnych i od tego czasu ich użycie tylko wzrosło. W matematyce istnieją pewne problemy związane z logiką zdań. Aby rozwiązać tego rodzaju równanie, trzeba posiadać pewną wiedzę: znajomość praw logiki zdań, znajomość tablic prawdy funkcji logicznych 1 lub 2 zmiennych, metod konwersji wyrażeń logicznych. Ponadto musisz znać następujące właściwości operacji logicznych: koniunkcja, alternatywna, inwersja, implikacja i równoważność.

Dowolną funkcję logiczną \zmiennych - \można określić za pomocą tabeli 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\]

Rozpocznijmy rozwiązanie od \[X1\] i określmy, jakie wartości może przyjmować ta zmienna: 0 i 1. Następnie rozważymy każdą z powyższych wartości i zobaczymy, jakie może być \[X2.\].

Jak widać z tabeli, nasze równanie logiczne ma 11 rozwiązań.

Gdzie mogę rozwiązać równanie logiczne online?

Równanie możesz rozwiązać na naszej stronie internetowej https://site. Bezpłatny solwer online pozwoli Ci rozwiązać równania online o dowolnej złożoności w ciągu kilku sekund. Wystarczy, że wprowadzisz swoje dane do solwera. Możesz także obejrzeć instrukcje 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 naszej grupy, zawsze chętnie Ci pomożemy.

Rozwiązywanie układów równań logicznych poprzez zmianę zmiennych

Metodę podstawienia zmiennych stosuje się, jeśli niektóre zmienne są uwzględniane w równaniach tylko 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:

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 poniższe 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:

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 ten 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. Koniunkcja jest prawdziwa (równa 1) tylko wtedy, gdy wszystkie jej 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).

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ół

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

Miejska budżetowa instytucja oświatowa

„Szkoła Gimnazjum nr 18”

dzielnica miejska miasta Salavat w Republice Baszkortostanu

Układy równań logicznych

w zagadnieniach jednolitego egzaminu państwowego z informatyki

Sekcja „Podstawy algebry logiki” w zadaniach egzaminu Unified State Examination jest uważana za jedną z najtrudniejszych i najtrudniejszych do rozwiązania. Średni odsetek wykonanych zadań z tego tematu jest najniższy i wynosi 43,2.

W oparciu o specyfikację KIM 2018 blok ten zawiera cztery zadania o różnym stopniu trudności.

Zadanie 23 ma wysoki poziom trudności, dlatego też ma najniższy procent ukończenia. Wśród absolwentów przygotowanych (81-100 punktów) zadanie wykonało 49,8%, absolwentów średnio przygotowanych (61-80 punktów) wykonało 13,7%, pozostała grupa studentów nie wykonała tego zadania.

Sukces w rozwiązaniu układu równań logicznych zależy od znajomości praw logiki i precyzyjnego zastosowania metod rozwiązywania układu.

Rozważmy 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  y1 )  (X2  y2 ))  (X1  X2 )  (j1  y2 ) =1

((X2  y2 )  (X3  y3 ))  (X2  X3 )  (j2  y3 ) =1

((X7  y7 )  (X8  y8 ))  (X7  X8 )  (y7  y8 ) =1

Gdzie X1 , X2 ,…, X8, Na1 , j2 ,…,j8 - zmienne logiczne? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości zmiennych, dla których zachodzi ta równość. W odpowiedzi należy podać liczbę takich zestawów.

Rozwiązanie. Wszystkie równania zawarte w układzie 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. Rozumując w podobny sposób, ze znanych x2 i y2 możemy znaleźć x3, y3, które spełniają drugie równanie. Oznacza to, że znając parę (x1, y1) i określając wartość pary (x2, y2), znajdziemy parę (x3, y3), co z kolei doprowadzi do pary (x4, y4) i tak dalej.

Znajdźmy wszystkie rozwiązania pierwszego równania. Można tego dokonać na dwa sposoby: skonstruować tabelę prawdy poprzez rozumowanie i zastosowanie praw logiki.

Tabela prawdy:

Konstruowanie tabeli prawdy jest pracochłonne i nieefektywne czasowo, dlatego stosujemy drugą metodę - logiczne wnioskowanie. Iloczyn jest równy 1 wtedy i tylko wtedy, gdy każdy czynnik jest równy 1.

(X1  y1 )  (X2  y2 ))=1

(X1  X2 ) =1

(y1  y2 ) =1

Spójrzmy na pierwsze równanie. Konsekwencja jest równa 1, gdy 0 0, 0 1, 1 1, co oznacza (x1 y1)=0 dla (01), (10), to para (X2  y2 ) może mieć dowolną wartość (00), (01), (10), (11), a gdy (x1 y1) = 1, czyli (00) i (11) para (x2 y2) = 1 przyjmuje te same wartości (00) i (11). Wykluczmy z tego rozwiązania te pary, dla których równanie drugie i trzecie jest fałszywe, czyli x1=1, x2=0, y1=1, y2=0.

Całkowita liczba par 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  y 2 ))  (j 1  y 2 ) = 1

(X 2  (X 3  y 3 ))  (j 2  y 3 ) = 1

...

( X 6  ( X 7  y 7 ))  ( y 6  y 7 ) = 1

X 7  y 7 = 1

Rozwiązanie. 1) Równania są tego samego typu, więc rozumując znajdziemy wszystkie możliwe pary (x1,y1), (x2,y2) pierwszego równania.

(X1  (X2  y2 ))=1

(y1  y2 ) = 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).

Utwórzmy połączenia pomiędzy parami (x1, y1) i (x2, y2).

Stwórzmy tabelę, aby obliczyć liczbę par na każdym etapie.

Uwzględniając rozwiązania ostatniego równania X 7  y 7 = 1, wykluczmy 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, więc rozumując znajdziemy wszystkie możliwe pary (x1,x2), (x3,x4) pierwszego równania.

(X1  X2 )  (X3  X4 ) = 1

Wykluczmy z rozwiązania pary, które w ciągu dają 0 (1 0), są to pary (01, 00, 11) i (10).

Utwórzmy połączenia pomiędzy parami (x1,x2), (x3,x4)

Instrukcje. Wpisując z klawiatury, należy stosować następujące konwencje:

Zasady wprowadzania funkcji logicznej

1. Zamiast symbolu v (alternatywa, OR) użyj znaku +.
2. Nie ma potrzeby podawania oznaczenia funkcji przed funkcją logiczną. Na przykład zamiast F(x,y)=(x|y)=(x^y) musisz po prostu wpisać (x|y)=(x^y) .
3. Maksymalna liczba zmiennych wynosi 10.

Projektowanie i analiza komputerowych obwodów logicznych odbywa się za pomocą specjalnej gałęzi matematyki - algebry logicznej. W algebrze logiki można wyróżnić trzy główne funkcje logiczne: „NOT” (negacja), „AND” (koniunkcja), „OR” (alternatywa).
Aby stworzyć dowolne urządzenie logiczne, należy określić zależność każdej ze zmiennych wyjściowych od istniejących zmiennych wejściowych; zależność tę nazywa się funkcją przełączającą lub funkcją algebry logicznej.
Funkcję algebry logicznej nazywa się całkowicie zdefiniowaną, jeśli podane są wszystkie 2n jej wartości, gdzie n jest liczbą zmiennych wyjściowych.
Jeśli nie wszystkie wartości są zdefiniowane, funkcję nazywa się częściowo zdefiniowaną.
Urządzenie nazywamy logicznym, jeżeli jego stan opisujemy za pomocą funkcji algebry logicznej.
Do przedstawienia funkcji algebry logicznej służą następujące metody:
W formie algebraicznej można zbudować obwód urządzenia logicznego za pomocą elementów logicznych.


Rysunek 1 - Schemat urządzenia logicznego

Wszystkie operacje algebry logicznej są zdefiniowane tablice prawdy wartości. Tabela prawdy określa wynik operacji dla każdy jest możliwy x wartości logiczne oryginalnych instrukcji. Liczba opcji odzwierciedlających wynik zastosowania operacji będzie zależała od liczby instrukcji w wyrażeniu logicznym. Jeśli liczba instrukcji w wyrażeniu logicznym wynosi N, wówczas tabela prawdy będzie zawierać 2 N wierszy, ponieważ istnieje 2 N różnych kombinacji możliwych wartości argumentów.

Działanie NOT - negacja logiczna (inwersja)

• jeśli pierwotne wyrażenie jest prawdziwe, to wynik jego negacji będzie fałszywy;
• jeśli pierwotne wyrażenie jest fałszywe, to wynik jego negacji będzie prawdziwy.

Operacja OR - dodawanie logiczne (alternatywa, suma)

Operacja AND - mnożenie logiczne (koniunkcja)

Operacja „JEŚLI-TO” – konsekwencja logiczna (implikacja)

Działanie „A wtedy i tylko wtedy, gdy B” (równoważność, równoważność)

Operacja „Dodawanie modulo 2” (XOR, wyłączność lub ścisła alternatywa)

Priorytet operacji logicznych

• Akcje w nawiasach
• Inwersja
• Spójnik (&)
• Rozłączenie (V), wyłączne OR (XOR), suma modulo 2
• Implikacja (→)
• Równoważność (↔)

Doskonała rozłączna postać normalna

1. Każdy wyraz logiczny wzoru zawiera wszystkie zmienne zawarte w funkcji F(x 1,x 2,...x n).
2. Wszystkie terminy logiczne wzoru są różne.
3. Żaden termin logiczny nie zawiera zmiennej i jej negacji.
4. Żaden termin logiczny w formule nie zawiera dwukrotnie tej samej zmiennej.

Doskonała spójna forma normalna

1. Wszystkie elementarne alternatywy zawierają wszystkie zmienne zawarte w funkcji F(x 1 ,x 2 ,...x n).
2. Wszystkie elementarne alternatywy są różne.
3. Każda elementarna dysjunkcja zawiera zmienną jeden raz.
4. Żadna elementarna alternatywa nie zawiera zmiennej i jej negacji.

Metody rozwiązywania układów równań logicznych

Można rozwiązać układ równań logicznych, np. korzystając z tabeli prawdy (jeśli liczba zmiennych nie jest zbyt duża) lub korzystając z drzewa decyzyjnego, uprzednio upraszczając każde równanie.

1. Metoda zastępowania zmiennych.

Wprowadzenie nowych zmiennych pozwala uprościć układ równań, zmniejszając liczbę niewiadomych.Nowe zmienne muszą być od siebie niezależne. Po rozwiązaniu układu uproszczonego musimy wrócić do oryginalnych zmiennych.

Rozważmy zastosowanie tej metody na konkretnym przykładzie.

Przykład.

((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0

((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0

((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0

((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0

Rozwiązanie:

Wprowadźmy nowe zmienne: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).

(Uwaga! Każda ze zmiennych x1, x2, ..., x10 musi być zawarta tylko w jednej z nowych zmiennych A, B, C, D, E, czyli nowe zmienne są od siebie niezależne).

Wtedy układ równań będzie wyglądał następująco:

(A ∧ B) ∨ (¬A ∧ ¬B)=0

(B ∧ C) ∨ (¬B ∧ ¬C)=0

(C ∧ D) ∨ (¬C ∧ ¬D)=0

(D ∧ E) ∨ (¬D ∧ ¬E)=0

Zbudujmy drzewo decyzyjne dla powstałego systemu:

Rozważmy równanie A=0, tj. (X1≡ X2)=0. Ma 2 korzenie:

Z tej samej tabeli widać, że równanie A=1 ma również 2 pierwiastki. Uporządkujmy liczbę korzeni w drzewie decyzyjnym:

Aby znaleźć liczbę rozwiązań jednej gałęzi, należy pomnożyć liczbę rozwiązań na każdym poziomie. Lewa gałąź ma 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 rozwiązania; prawa gałąź również ma 32 rozwiązania. Te. cały układ ma 32+32=64 rozwiązania.

Odpowiedź: 64.

2. Sposób rozumowania.

Trudność rozwiązywania układów równań logicznych polega na uciążliwości całego drzewa decyzyjnego. Metoda rozumowania pozwala nie budować całego drzewa, ale zrozumieć, ile będzie miało gałęzi. Przyjrzyjmy się tej metodzie na konkretnych przykładach.

Przykład 1. 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?

(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) /\ (x4 → x5) = 1

(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) /\ (y4 → y5) = 1

x1\/y1 =1

Odpowiedź nie musi wymieniać wszystkich różnych zbiorów wartości zmiennych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, dla których ten układ równości jest spełniony. W odpowiedzi należy podać liczbę takich zestawów.

Rozwiązanie :

Pierwsze i drugie równanie zawierają zmienne niezależne, które są powiązane trzecim warunkiem. Zbudujmy drzewo rozwiązań dla pierwszego i drugiego równania.

Aby przedstawić drzewo rozwiązań układu pierwszego i drugiego równania, każda gałąź pierwszego drzewa musi być kontynuowana drzewem zmiennych Na . Zbudowane w ten sposób drzewo będzie miało 36 gałęzi. Niektóre z tych gałęzi nie spełniają trzeciego równania układu. Zaznaczmy liczbę gałęzi drzewa na pierwszym drzewie„y” , które spełniają trzecie równanie:

Wyjaśnijmy: aby spełnić trzeci warunek, gdy x1=0 musi istnieć y1=1, czyli wszystkie gałęzie drzewa"X" , gdzie x1=0 można kontynuować tylko z jedną gałęzią drzewa„y” . I tylko dla jednej gałęzi drzewa"X" (po prawej) wszystkie gałęzie drzewa pasują„y”. Zatem pełne drzewo całego systemu zawiera 11 gałęzi. Każda gałąź reprezentuje jedno rozwiązanie pierwotnego układu równań. Oznacza to, że cały układ ma 11 rozwiązań.

Odpowiedź: 11.

Przykład 2. Ile różnych rozwiązań ma układ równań?

(X1 ≡ X2) ∨ (X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)= 1

(X2 ≡ X3) ∨ (X2 ∧ X10) ∨ (¬X2 ∧ ¬ X10)= 1.

………………

(X9 ≡ X10) ∨ (X9 ∧ X10) ∨ (¬X9 ∧ ¬ X10)= 1

(X1 ≡ X10) = 0

gdzie x1, x2,…, x10 są zmiennymi logicznymi? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości zmiennych, dla których zachodzi ta równość. W odpowiedzi należy podać liczbę takich zestawów.

Rozwiązanie : Uprośćmy system. Zbudujmy tabelę prawdy dla części pierwszego równania:

Zwróć uwagę na ostatnią kolumnę, odpowiada ona wynikowi akcji X1 ≡ X10.

Po uproszczeniu otrzymujemy:

(X1 ≡ X2) ∨ (X1 ≡ X10)=1

(X2 ≡ X3) ∨ (X2 ≡ X10)=1

(X3 ≡ X4) ∨ (X3 ≡ X10)=1

……

(X9 ≡ X10) ∨ (X9 ≡ X10)=1

(X1 ≡ X10) = 0

Rozważmy ostatnie równanie:(X1 ≡ X10) = 0, tj. x1 nie powinno pokrywać się z x10. Aby pierwsze równanie było równe 1, równość musi być prawdziwa(X1 ≡ X2)=1, tj. x1 musi pasować do x2.

Zbudujmy drzewo rozwiązań pierwszego równania:

Rozważmy drugie równanie: dla x10=1 i dla x2=0 nawiasmusi być równe 1 (tzn. x2 pokrywa się z x3); dla x10=0 i dla x2=1 nawiasu(X2 ≡ X10)=0, co oznacza nawias (X2 ≡ X3) powinno być równe 1 (tzn. x2 pokrywa się z x3):

Rozumując w ten sposób budujemy drzewo decyzyjne dla wszystkich równań:

Zatem układ równań ma tylko 2 rozwiązania.

Odpowiedź: 2.

Przykład 3.

Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, y1, y2, y3, y4, z1, z2, z3, z4, które spełniają wszystkie poniższe warunki?

(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) = 1

(¬x1 /\ y1 /\ z1) \/ (x1 /\ ¬y1 /\ z1) \/ (x1 /\ y1 /\ ¬z1) = 1

(¬x2 /\ y2 /\ z2) \/ (x2 /\ ¬y2 /\ z2) \/ (x2 /\ y2 /\ ¬z2) = 1

(¬x3 /\ y3 /\ z3) \/ (x3 /\ ¬y3 /\ z3) \/ (x3 /\ y3 /\ ¬z3) = 1

(¬x4 /\ y4 /\ z4) \/ (x4 /\ ¬y4 /\ z4) \/ (x4 /\ y4 /\ ¬z4) = 1

Rozwiązanie:

Zbudujmy drzewo rozwiązań dla pierwszego równania:

Rozważmy drugie równanie:

• Gdy x1=0 : drugi i trzeci nawias będą równe 0; aby pierwszy nawias był równy 1, y1=1, z1=1 (czyli w tym przypadku - 1 rozwiązanie)
• Kiedy x1=1 : pierwszy nawias będzie równy 0; drugi Lub trzeci nawias musi być równy 1; drugi nawias będzie równy 1, gdy y1=0 i z1=1; trzeci nawias będzie równy 1, gdy y1=1 i z1=0 (czyli w tym przypadku - 2 rozwiązania).

Podobnie dla pozostałych równań. Zanotujmy wynikową liczbę rozwiązań dla każdego węzła drzewa:

Aby poznać liczbę rozwiązań dla każdej gałęzi, należy pomnożyć otrzymane liczby osobno dla każdej gałęzi (od lewej do prawej).

1 gałąź: 1 ⋅ 1 ⋅ 1 ⋅ 1 = 1 rozwiązanie

Oddział 2: 1 ⋅ 1 ⋅ 1 ⋅ 2 = 2 rozwiązania

3. gałąź: 1 ⋅ 1 ⋅ 2 ⋅ 2 = 4 rozwiązania

4. gałąź: 1 ⋅ 2 ⋅ 2 ⋅ 2 = 8 rozwiązań

5. gałąź: 2 ⋅ 2 ⋅ 2 ⋅ 2=16 rozwiązań

Dodajmy otrzymane liczby: w sumie jest 31 rozwiązań.

Odpowiedź: 31.

3. Naturalny wzrost liczby korzeni

W niektórych układach liczba pierwiastków następnego równania zależy od liczby pierwiastków poprzedniego równania.

Przykład 1. Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, x5, x6, x7, x8, x9, x10, które spełniają wszystkie poniższe warunki?

¬(x1 ≡ x2) ∧ ((x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)) = 0

¬(x2 ≡ x3) ∧ ((x2 ∧ ¬x4) ∨ (¬x2 ∧ x4)) = 0

¬(x8 ≡ x9) ∧ ((x8 ∧ ¬x10) ∨ (¬x8 ∧ x10)) = 0

Uprośćmy pierwsze równanie:(x1 ∧ ¬x3) ∨ (¬x1 ∧ x3)=x1 ⊕ x3=¬(x1 ≡ x3). Wtedy system przyjmie postać:

¬(x1 ≡ x2) ∧ ¬(x1 ≡ x3) = 0

¬(x2 ≡ x3) ∧ ¬(x2 ≡ x4)= 0

¬(x8 ≡ x9) ∧ ¬(x8 ≡ x10) = 0

Itp.

Każde kolejne równanie ma o 2 pierwiastki więcej niż poprzednie.

4 równanie ma 12 pierwiastków;

Równanie 5 ma 14 pierwiastków

Równanie 8 ma 20 pierwiastków.

Odpowiedź: 20 korzeni.

Czasami liczba pierwiastków rośnie zgodnie z prawem Fibonacciego.

Rozwiązywanie układu równań logicznych wymaga kreatywnego podejścia.