Logika. Funkcje logiczne. Rozwiązywanie równań. Rozwiązywanie równań logicznych w matematyce

26.09.2019

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 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:

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 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).

				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	Przeznaczenie.	Formuła	Liczba zestawów
Zestawy	Przeznaczenie.	Formuła	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

Jak rozwiązać niektóre zadania z części A i B egzaminu z informatyki

Lekcja 3. Logika. Funkcje logiczne. Rozwiązywanie równań

Duża liczba problemów egzaminu Unified State Exam poświęcona jest logice zdań. Do rozwiązania większości z nich wystarczy znajomość podstawowych praw logiki zdań, znajomość tablic prawdy funkcji logicznych jednej i dwóch zmiennych. Podam podstawowe prawa logiki zdań.

Przemienność alternatywy i koniunkcji:
a ˅ b ≡ b ˅ a
a^b ≡ b^a
Prawo rozdzielności dotyczące alternatywy i koniunkcji:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
za ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Negacja negacji:
¬(¬a) ≡ za
Konsystencja:
a ^ ¬a ≡ fałsz
Ekskluzywna trzecia:
a ˅ ¬а ≡ prawda
Prawa De Morgana:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b
Uproszczenie:
a ˄ za ≡ za
a ˅ za ≡ za
a ˄ prawda ≡ a
a ˄ fałsz ≡ fałsz
Wchłanianie:
za ˄ (a ˅ b) ≡ za
a ˅ (a ˄ b) ≡ za
Zastąpienie implikacji
a → b ≡ ¬a ˅ b
Zastąpienie tożsamości
za ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Reprezentacja funkcji logicznych

Dowolną funkcję logiczną n zmiennych - F(x 1, x 2, ... x n) można określić za pomocą tablicy prawdy. Taka tabela zawiera 2n zbiorów zmiennych, dla każdego z nich podana jest wartość funkcji na tym zbiorze. Metoda ta jest dobra, gdy liczba zmiennych jest stosunkowo niewielka. Już dla n > 5 reprezentacja staje się słabo widoczna.

Innym sposobem jest zdefiniowanie funkcji za pomocą jakiegoś wzoru przy użyciu znanych, dość prostych funkcji. Układ funkcji (f 1, f 2, … f k) nazywa się kompletnym, jeśli dowolną funkcję logiczną można wyrazić wzorem zawierającym tylko funkcje f i.

Układ funkcji (¬, ˄, ˅) jest kompletny. Prawa 9 i 10 są przykładami pokazującymi, jak implikacja i tożsamość wyrażają się poprzez negację, koniunkcję i alternatywę.

W rzeczywistości system dwóch funkcji – negacji i koniunkcji lub negacji i alternatywy – jest również kompletny. Z praw De Morgana wynikają idee, które pozwalają wyrazić koniunkcję poprzez negację i alternatywę, a zatem wyrazić alternatywę poprzez negację i koniunkcję:

(a ˅ b) ≡ ¬(¬a ˄ ¬b)
(a ˄ b) ≡ ¬(¬a ˅ ¬b)

Paradoksalnie, system składający się tylko z jednej funkcji jest kompletny. Istnieją dwie funkcje binarne - antykoniukcja i antydysjunkcja, zwane strzałką Peirce'a i skokiem Schaeffera, reprezentujące pusty system.

Do podstawowych funkcji języków programowania zalicza się najczęściej tożsamość, negację, koniunkcję i alternatywę. W Problemy z jednolitym egzaminem państwowym Oprócz tych funkcji często można znaleźć implikacje.

Spójrzmy na kilka proste zadania związane z funkcjami logicznymi.

Zadanie 15:

Podano fragment tabeli prawdy. Która z trzech podanych funkcji odpowiada temu fragmentowi?

X 1	X2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

(X 1 → X 2) ˄ ¬ X 3 ˅ X 4
(¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
¬ X 1 ˅ X 2 ˅ (X 3 ˄ X 4)

Funkcja numer 3.

Aby rozwiązać problem, należy znać tablice prawdy podstawowych funkcji i pamiętać o priorytetach działań. Przypominam, że koniunkcja (mnożenie logiczne) ma wyższy priorytet i jest wykonywana wcześniej niż rozłączenie (dodawanie logiczne). Podczas obliczeń łatwo zauważyć, że funkcje o numerach 1 i 2 w trzecim zbiorze mają wartość 1 i dlatego nie odpowiadają fragmentowi.

Zadanie 16:

Która z podanych liczb spełnia warunek:

(cyfry, zaczynając od cyfry najbardziej znaczącej, są uporządkowane malejąco) → (liczba – parzysta) ˄ (niska cyfra – parzysta) ˄ (wysoka cyfra – nieparzysta)

Jeżeli takich liczb jest kilka, wskaż największą.

13579
97531
24678
15386

Warunek spełnia liczba 4.

Dwie pierwsze liczby nie spełniają warunku, ponieważ najniższa cyfra jest nieparzysta. Koniunkcja warunków jest fałszywa, jeśli jeden z warunków koniunkcji jest fałszywy. Dla trzeciej liczby warunek dotyczący najwyższej cyfry nie jest spełniony. Dla czwartej liczby spełnione są warunki nałożone na dolną i górną cyfrę liczby. Pierwszy człon spójnika jest również prawdziwy, ponieważ implikacja jest prawdziwa, jeśli jej przesłanka jest fałszywa, co ma miejsce w tym przypadku.

Problem 17: Dwóch świadków złożyło następujące zeznania:

Pierwszy świadek: Jeśli A jest winny, to B jest jeszcze bardziej winny, a C jest niewinny.

Drugi świadek: Dwóch jest winnych. A jeden z pozostałych jest zdecydowanie winny i winny, ale nie mogę powiedzieć, kto dokładnie.

Jakie wnioski na temat winy A, B i C można wyciągnąć z zeznań?

Odpowiedź: Z zeznań wynika, że A i B są winni, a C jest niewinny.

Rozwiązanie: Oczywiście odpowiedzi można udzielić kierując się zdrowym rozsądkiem. Ale przyjrzyjmy się, jak można to zrobić ściśle i formalnie.

Pierwszą rzeczą do zrobienia jest sformalizowanie stwierdzeń. Wprowadźmy trzy zmienne logiczne - A, B i C, z których każda ma wartość true (1), jeśli odpowiedni podejrzany jest winny. Wówczas zeznanie pierwszego świadka wyraża się wzorem:

A → (B ˄ ¬C)

Zeznanie drugiego świadka wyraża się wzorem:

A ˄ ((B ˄ ¬C) ˅ (¬B ˄ C))

Zeznania obu świadków przyjmuje się za prawdziwe i stanowią koniunkcję odpowiednich wzorów.

Stwórzmy tabelę prawdy dla tych odczytów:

A	B	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Zbiorczy materiał dowodowy jest prawdziwy tylko w jednym przypadku, co prowadzi do jasnej odpowiedzi – A i B są winni, a C jest niewinny.

Z analizy tej tabeli wynika także, że zeznania drugiego świadka są bardziej pouczające. Z prawdziwości jego świadectwa wynikają tylko dwie rzeczy: możliwe opcje- A i B są winni, a C jest niewinny, lub A i C są winni, a B jest niewinny. Zeznania pierwszego świadka są mniej pouczające – jest ich 5 różne opcje, co odpowiada jego zeznaniom. Łącznie zeznania obu świadków dają jednoznaczną odpowiedź co do winy podejrzanych.

Równania logiczne i układy równań

Niech F(x 1, x 2, …x n) będzie funkcją logiczną n zmiennych. Równanie logiczne wygląda następująco:

F(x 1, x 2, …x n) = C,

Stała C ma wartość 1 lub 0.

Równanie logiczne może mieć od 0 do 2 n 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:

F(x 1 , x 2 , …x n) = 1

Rzeczywiście, niech będzie podane równanie:

F(x 1, x 2, …x n) = 0

W tym przypadku możemy przejść do równoważnego równania:

¬F(x 1 , x 2 , …x n) = 1

Rozważmy układ k równań logicznych:

F 1 (x 1, x 2, …x n) = 1

F 2 (x 1, x 2, …x n) = 1

fa k (x 1 , x 2 , …x n) = 1

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ę pierwotnych funkcji F:

Ф = fa 1 ˄ fa 2 ˄ … fa k

Jeśli liczba zmiennych jest mała, np. mniejsza niż 5, to nie jest trudno skonstruować tablicę prawdy dla funkcji Ф, która pozwala nam powiedzieć, ile rozwiązań ma dany układ i jakie zbiory dostarczają rozwiązań.

W niektórych zadaniach USE związanych ze znalezieniem rozwiązań 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 - x 1, x 2, ...x 5. 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. Odwrotna sytuacja jest również prawdziwa: koniunkcję warunków można uznać za układ równań.

Zbudujmy drzewo decyzyjne dla implikacji (x1 → x2) - pierwszego wyrazu 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ą X 1 . 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 X 2, dla których równanie jest prawdziwe. Ponieważ równanie określa implikację, gałąź, w której X 1 ma wartość 1, wymaga, aby w tej gałęzi X 2 miało wartość 1. Gałąź, w której X 1 ma wartość 0, tworzy dwie gałęzie o wartościach X 2 równe 0 i 1 Skonstruowane drzewo definiuje trzy rozwiązania, na których implikacja X 1 → X 2 przyjmuje wartość 1. Na każdej gałęzi wypisany jest odpowiedni zbiór 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ę X 2 → X 3 . 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 X 2 ma już wartości w drzewie, to na wszystkich gałęziach, w których zmienna X 2 ma wartość 1, zmienna X 3 również będzie miała wartość 1. Dla takich gałęzi konstrukcja drzewa przechodzi do następnego poziomu, ale nowe gałęzie nie pojawiają się. Pojedyncza gałąź, w której zmienna X 2 ma wartość 0, rozgałęzi się na dwie gałęzie, w których zmienna X 3 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:

(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) /\ (x4 → x5) = 1
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:

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

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 dla zmiennych X i można połączyć z każdym rozwiązaniem dla zmiennych Y j Łączna 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?

(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) /\ (x4 → x5) = 1
(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) /\ (y4 → y5) = 1
(x1 → y1) = 1

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 X 1 → Y 1 wynika, że gdy X 1 ma wartość 1 (istnieje jedno takie rozwiązanie), to Y 1 również ma wartość 1. Zatem istnieje jeden zbiór, na którym X 1 i Y 1 mają wartości 1. Gdy X 1 jest równe 0, Y 1 może mieć dowolną wartość, zarówno 0, jak i 1. Zatem każdy zbiór z X 1 równym 0, a jest 5 takich zbiorów, odpowiada wszystkim 6 zbiorom ze zmiennymi Y. Zatem całkowita liczba rozwiązań wynosi 31.

Problem 20

(¬X 1 ˅ X 2) ˄ (¬X 2 ˅ X 3) ˄ (¬X 3 ˅ X 4) ˄ (¬X 4 ˅ X 5) ˄ (¬X 5 ˅ X 1) = 1

Rozwiązanie: Pamiętając o podstawowych równoważnościach, zapisujemy nasze równanie jako:

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 5) ˄ (X 5 → X 1) = 1

Cykliczny łańcuch implikacji oznacza, że zmienne są identyczne, więc nasze równanie jest równoważne równaniu:

X 1 ≡ X 2 ≡ X 3 ≡ X 4 ≡ X 5 = 1

To równanie ma dwa rozwiązania, gdy wszystkie X i wynoszą 1 lub 0.

Zadanie 21

(X 1 → X 2) ˄ (X 2 → X 3) ˄ (X 3 → X 4) ˄ (X 4 → X 2) ˄ (X 4 → X 5) = 1

Rozwiązanie: Podobnie jak w zadaniu 20, przechodzimy od implikacji cyklicznych do tożsamości, przepisując równanie do postaci:

(X 1 → X 2) ˄ (X 2 ≡ X 3 ≡ X 4) ˄ (X 4 → X 5) = 1

Zbudujmy drzewo decyzyjne dla tego równania:

Zadanie 22

Ile rozwiązań ma następujący układ równań?

((X 1 ≡X 2) ˄ (X 3 ≡X 4)) ˅(¬(X 1 ≡X 2) ˄ ¬(X 3 ≡X 4)) = 0

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X6)) = 0

((X 5 ≡X 6) ˄ (X 7 ≡X 8)) ˅(¬(X 5 ≡X 6) ˄ ¬(X 7 ≡X 8)) = 0

((X 7 ≡X 8) ˄ (X 9 ≡X 10)) ˅(¬(X 7 ≡X 8) ˄ ¬(X 9 ≡X 10)) = 0

Odpowiedź: 64

Rozwiązanie: Przejdźmy od 10 zmiennych do 5 zmiennych wprowadzając następującą zmianę zmiennych:

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Wtedy pierwsze równanie przyjmie postać:

(Y 1 ˄ Y 2) ˅ (¬Y 1 ˄ ¬Y 2) = 0

Równanie można uprościć, zapisując je jako:

(Y 1 ≡ Y 2) = 0

Przechodząc do formy tradycyjnej, układ po uproszczeniu zapisujemy w postaci:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

Drzewo decyzyjne dla tego systemu jest proste i składa się z dwóch gałęzi z naprzemiennymi wartościami zmiennych:

Wracając do oryginalnych zmiennych X, zauważ, że dla każdej wartości zmiennej Y przypadają 2 wartości w zmiennych X, więc każde rozwiązanie w zmiennych Y generuje 2 5 rozwiązań w zmiennych X. Obie gałęzie generują 2 * 2 5 rozwiązań, więc całkowita liczba rozwiązań wynosi 64.

Jak widać, każdy problem rozwiązania układu równań wymaga własnego podejścia. Powszechną techniką jest wykonywanie równoważnych przekształceń w celu uproszczenia równań. Powszechną techniką jest konstruowanie drzew decyzyjnych. Zastosowane podejście przypomina częściowo konstruowanie tabeli prawdy z tą różnicą, że konstruowane są nie wszystkie zbiory możliwych wartości zmiennych, a tylko te, na których funkcja przyjmuje wartość 1 (prawda). Często w proponowanych problemach nie ma potrzeby budowania pełnego drzewa decyzyjnego, ponieważ już etap początkowy możliwe jest ustalenie schematu pojawiania się nowych gałęzi na każdym kolejnym poziomie, jak to zrobiono na przykład w zadaniu 18.

Ogólnie rzecz biorąc, zadania polegające na znajdowaniu rozwiązań układu równań logicznych są dobrymi ćwiczeniami matematycznymi.

Jeśli problem jest trudny do rozwiązania ręcznie, można powierzyć rozwiązanie komputerowi, pisząc odpowiedni program do rozwiązywania równań i układów równań.

Napisanie takiego programu nie jest trudne. Taki program z łatwością poradzi sobie ze wszystkimi zadaniami oferowanymi w Unified State Exam.

Co dziwne, znalezienie rozwiązań układów równań logicznych jest dla komputera trudne i okazuje się, że komputer ma swoje ograniczenia. Komputer dość łatwo poradzi sobie z zadaniami, w których liczba zmiennych wynosi 20-30, ale zacznie myśleć o problemach przez długi czas większy rozmiar. Faktem jest, że funkcja 2 n, która określa liczbę zbiorów, jest funkcją wykładniczą, która rośnie szybko wraz ze wzrostem n. Tak szybko, że zwykły komputer osobisty nie jest w stanie w ciągu dnia udźwignąć zadania, które ma 40 zmiennych.

Program w języku C# do rozwiązywania równań logicznych

Napisanie programu do rozwiązywania równań logicznych jest przydatne z wielu powodów, chociażby dlatego, że można za jego pomocą sprawdzić poprawność własnego rozwiązania problemów testowych Unified State Exam. Innym powodem jest to, że taki program jest doskonałym przykładem zadania programistycznego spełniającego wymagania dla zadań kategorii C w Unified State Examination.

Idea budowy programu jest prosta – opiera się na pełnym przeszukiwaniu wszystkich możliwych zbiorów wartości zmiennych. Skoro dla danego równania logicznego lub układu równań znana jest liczba zmiennych n, to znana jest również liczba zbiorów - 2 n, które należy uporządkować. Za pomocą podstawowe funkcje W języku C# - negacja, alternatywna koniunkcja i tożsamość, nie jest trudno napisać program, który dla zadanego zbioru zmiennych obliczy wartość funkcji logicznej odpowiadającej równaniu logicznemu lub układowi równań.

W takim programie trzeba zbudować pętlę na podstawie liczby zbiorów, w treści pętli korzystając z numeru zbioru, utworzyć sam zbiór, obliczyć wartość funkcji na tym zbiorze i jeśli to wartość wynosi 1, wówczas zbiór daje rozwiązanie równania.

Jedyna trudność jaka pojawia się przy wdrażaniu programu związana jest z zadaniem wygenerowania samego zbioru wartości zmiennych na podstawie zadanej liczby. Piękno tego problemu polega na tym, że to pozornie trudne zadanie w rzeczywistości sprowadza się do prostego problemu, który pojawiał się już wiele razy. Rzeczywiście wystarczy zrozumieć, że zbiór wartości zmiennych odpowiadających liczbie i, składający się z zer i jedynek, reprezentuje binarną reprezentację liczby i. Więc trudne zadanie uzyskanie zbioru wartości zmiennych przez ustaloną liczbę sprowadza się do dobrze znanego problemu konwersji liczby do systemu binarnego.

Tak wygląda funkcja w C#, która rozwiązuje nasz problem:

///

/// program do zliczania liczby rozwiązań

/// równanie logiczne (układ równań)

///

/// funkcja logiczna - metoda,

/// którego podpis jest określony przez delegata DF

///

/// liczba zmiennych

/// liczba rozwiązań

statyczny int SolveEquations(DF zabawa, int n)

zestaw bool = nowy bool[n];

int m = (int)Math.Pow(2, n); //liczba zestawów

int p = 0, q = 0, k = 0;

//Zakończ wyszukiwanie według liczby zestawów

for (int i = 0; tj< m; i++)

//Tworzenie kolejnego zestawu - set,

//określony przez binarną reprezentację liczby i

for (int j = 0; j< n; j++)

k = (int)Math.Pow(2, j);

//Oblicz wartość funkcji na zbiorze

Mam nadzieję, że wyjaśnienia idei programu i komentarze w jego tekście wystarczą do zrozumienia programu. Skupię się jedynie na wyjaśnieniu tytułu danej funkcji. Funkcja SolveEquations ma dwa parametry wejściowe. Parametr fun określa funkcję logiczną odpowiadającą rozwiązywanemu równaniu lub układowi równań. Parametr n określa liczbę zmienne funkcyjne zabawa. W rezultacie funkcja SolveEquations zwraca liczbę rozwiązań funkcji logicznej, czyli liczbę tych zbiorów, w których funkcja ma wartość true.

U dzieci w wieku szkolnym często zdarza się, że jakaś funkcja F(x) ma parametr wejściowy x, który jest zmienną typu arytmetycznego, łańcuchowego lub logicznego. W naszym przypadku zastosowano mocniejszą konstrukcję. Funkcja SolveEquations odnosi się do funkcji wyższego rzędu - funkcji typu F(f), których parametrami mogą być nie tylko proste zmienne, ale także funkcje.

Klasę funkcji, która może zostać przekazana jako parametr do funkcji SolveEquations, określa się następująco:

delegat bool DF(bool zmienne);

Do tej klasy należą wszystkie funkcje, którym jako parametr przekazywany jest zbiór wartości zmiennych logicznych określonych przez tablicę vars. Wynikiem jest wartość logiczna reprezentująca wartość funkcji w tym zbiorze.

Na koniec, oto program, który wykorzystuje funkcję SolveEquations do rozwiązywania kilku układów równań logicznych. Funkcja SolveEquations jest częścią poniższej klasy ProgramCommon:

Program zajęć Wspólny

delegat bool DF(bool zmienne);

statyczna nieważność Main(argumenty ciągu)

Console.WriteLine("I funkcje - " +

Rozwiąż Równania(Zabawa, 2));

Console.WriteLine("Funkcja ma 51 rozwiązań - " +

Rozwiąż Równania(Zabawa51, 5));

Console.WriteLine("Funkcja ma 53 rozwiązania - " +

Rozwiąż Równania(Zabawa53, 10));

statyczny bool FunAnd(bool vars)

zwróć vars && vars;

statyczny bool Fun51(bool vars)

f = f && (!vars || Vars);

statyczny bool Fun53(bool vars)

f = f && ((vars == vars) || (vars == vars));

f = f && (!((vars == vars) || (vars == vars)));

Oto jak wyglądają wyniki rozwiązania dla tego programu:

10 zadań do samodzielnej pracy

Które z trzech funkcji są równoważne:
1. (X → Y) ˅ ¬Y
2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
3. ¬X ˄Y
Podano fragment tabeli prawdy:

X 1	X2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Której z trzech funkcji odpowiada ten fragment:

(X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
(X 1 → X 3) ˄ X 2 ˅ X 4
X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
Jury składa się z trzech osób. Decyzja zostaje podjęta, jeżeli zagłosuje na nią przewodniczący jury, poparty przez co najmniej jednego z członków jury. W przeciwnym razie nie zostanie podjęta żadna decyzja. Zbuduj funkcję logiczną formalizującą proces decyzyjny.
X wygrywa z Y, jeśli w czterech rzutach monetą wypadnie trzy reszki. Zdefiniuj funkcję logiczną opisującą wypłatę X.
Słowa w zdaniu są numerowane począwszy od jednego. Zdanie uważa się za poprawnie zbudowane, jeśli spełnione są następujące zasady:
1. Jeśli słowo o liczbie parzystej kończy się samogłoską, to następne słowo, jeśli istnieje, musi zaczynać się od samogłoski.
2. Jeśli słowo o liczbie nieparzystej kończy się spółgłoską, wówczas następne słowo, jeśli istnieje, musi zaczynać się od spółgłoski i kończyć samogłoską.
  Które z poniższych zdań jest poprawnie zbudowane:
3. Mama umyła Maszę mydłem.
4. Lider jest zawsze wzorem.
5. Prawda jest dobra, ale szczęście jest lepsze.
Ile rozwiązań ma równanie:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
Wypisz wszystkie rozwiązania równania:
(a → b) → do = 0
Ile rozwiązań ma następujący układ równań:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X 5 → X 6 ˄ X 6 → X 7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1
Ile rozwiązań ma równanie:
((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Odpowiedzi na problemy:

Funkcje b i c są równoważne.
Fragment odpowiada funkcji b.
Niech zmienna logiczna P przyjmie wartość 1, gdy przewodniczący jury głosuje „za” decyzją. Zmienne M 1 i M 2 reprezentują opinie członków jury. Funkcję logiczną określającą podjęcie pozytywnej decyzji można zapisać w następujący sposób:
P ˄ (M 1 ˅ M 2)
Niech zmienna logiczna P i przyjmie wartość 1, gdy i-ty rzut monetą zakończy się reszką. Funkcję logiczną określającą wypłatę X można zapisać w następujący sposób:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))
Zdanie b.
Równanie ma 3 rozwiązania: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

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 znajdować się tylko w jednej z nowych zmienne A, B, C, D, E, tj. 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:

		X1 ≡ X2

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:

X1 ∧ X10	¬X1 ∧ ¬X10	(X1 ∧ X10) ∨ (¬X1 ∧ ¬ X10)

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

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 nawias(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 rozwiązań 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.

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:

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ązania.

W niektórych zadaniach USE związanych ze znalezieniem rozwiązań 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 innej ogólnej metody niż wyliczenie, która pozwalałaby na rozwiązanie takich problemów.

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. Inna przydatna technika rozwiązania tego problemu jest następująca. Nie interesują nas wszystkie zbiory, a jedynie te, na których funkcja ma wartość 1. Zamiast budować kompletną tablicę prawdy, zbudujemy jej odpowiednik – 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 wyrazu 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ń. Oto jak wygląda pełne drzewo decyzyjne 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 rozwiązań wynosi 36.

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ń?

Możesz wybrać różne drogi 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ż iloś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.

Udawajmy, że X 1 – jest prawdą, to z pierwszego równania to otrzymujemy X 2 to również 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ązań za pomocą 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)*