Co to jest równanie logiczne. Metody rozwiązywania układów równań logicznych

Metody rozwiązywania układów równania logiczne

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 zestawów wartości zmiennych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, dla których ten system równa się 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óżne rozwiązania 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 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 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.

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

1. Przemienność alternatywy i koniunkcji:
   a ˅ b ≡ b ˅ a
   a^b ≡ b^a
2. Prawo rozdzielności dotyczące alternatywy i koniunkcji:
   a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
   za ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
3. Negacja negacji:
   ¬(¬a) ≡ za
4. Konsystencja:
   a ^ ¬а ≡ fałsz
5. Ekskluzywna trzecia:
   a ˅ ¬а ≡ prawda
6. Prawa De Morgana:
   ¬(a ˅ b) ≡ ¬a ˄ ¬b
   ¬(a ˄ b) ≡ ¬a ˅ ¬b
7. Uproszczenie:
   a ˄ za ≡ za
   a ˅ za ≡ za
   a ˄ prawda ≡ a
   a ˄ fałsz ≡ fałsz
8. Wchłanianie:
   za ˄ (a ˅ b) ≡ za
   a ˅ (a ˄ b) ≡ za
9. Zastąpienie implikacji
   a → b ≡ ¬a ˅ b
10. 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 Zadania ujednoliconego egzaminu państwowego 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

1. (X 1 → X 2) ˄ ¬ X 3 ˅ X 4
2. (¬ X 1 ˄ X 2) ˅ (¬ X 3 ˄ X 4)
3. ¬ 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ą.

1. 13579
2. 97531
3. 24678
4. 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 odpowiedź można udzielić na podstawie zdrowy rozsądek. 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. Następnie zeznanie pierwszego świadka wyraża się wzorem:

A → (B ˄ ¬C)

Zeznanie drugiego świadka wyraża się wzorem:

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

Przyjmuje się, że zeznania obu świadków są 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 - istnieje 5 różnych opcji odpowiadających 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ą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 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 to wygląda obraz graficzny to drzewo:

Drzewo składa się z dwóch poziomów w zależności od liczby zmienne równania. 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ń. Oto jak wygląda pełne drzewo decyzyjne 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 również ma 6 rozwiązań. Ponieważ każde rozwiązanie zmiennej X i można połączyć z każdym rozwiązaniem zmiennej Y j , 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?

(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

Przejść do tradycyjna forma, zapisujemy układ po uproszczeniu 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 problemami, w których liczba zmiennych wynosi 20-30, ale zacznie myśleć długo nad problemami o większym rozmiarze. 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 egzaminie Unified State Exam.

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ć. Korzystając z podstawowych funkcji języka C# - negacji, alternatywy, koniunkcji i tożsamości, 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 następny zestaw- ustawić

//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 należy do funkcji wyższy porządek– funkcje 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);

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

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

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

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

statyczny bool Fun53(bool vars)

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

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

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

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

f = f && ((vars == vars) || (vars == 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

1. Które z trzech funkcji są równoważne:
   1. (X → Y) ˅ ¬Y
   2. ¬(X ˅ ¬Y) ˄ (X → ¬Y)
   3. ¬X ˄Y
2. 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:

1. (X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
2. (X 1 → X 3) ˄ X 2 ˅ X 4
3. X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
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.
5. X wygrywa z Y, jeśli w czterech rzutach monetą wypadnie trzy reszki. Zdefiniuj funkcję logiczną opisującą wypłatę X.
6. 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ą, wówczas 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.
7. Ile rozwiązań ma równanie:
   (a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
8. Wypisz wszystkie rozwiązania równania:
   (a → b) → do = 0
9. 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
10. Ile rozwiązań ma równanie:
    ((((X 0 → X 1) → X 2) → X 3) →X 4) →X 5 = 1

Odpowiedzi na problemy:

1. Funkcje b i c są równoważne.
2. Fragment odpowiada funkcji b.
3. 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)
4. 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))
5. Zdanie b.
6. Równanie ma 3 rozwiązania: (a = 1; b = 1; c = 0); (a = 0; b = 0; c = 0); (a = 0; b = 1; c = 0)

Niech będzie funkcją logiczną n zmiennych. Równanie logiczne wygląda następująco:

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

Równanie logiczne może mieć od 0 do różnych rozwiązań. Jeżeli C jest równe 1, to rozwiązaniami są wszystkie te zbiory zmiennych z tablicy prawdy, dla których funkcja F przyjmuje wartość true (1). Pozostałe zbiory to rozwiązania równania o C równym zero. Zawsze możesz rozważyć tylko równania postaci:

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

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

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

Rozwiązaniem układu jest zbiór zmiennych, dla którego spełnione są wszystkie równania układu. W zakresie funkcji logicznych, aby otrzymać rozwiązanie układu równań logicznych, należy znaleźć zbiór, na którym prawdziwa jest funkcja logiczna Ф, reprezentująca koniunkcję funkcji pierwotnych:

Jeśli liczba zmiennych jest mała, np. mniejsza niż 5, to nie jest trudno skonstruować tablicę prawdy dla tej funkcji, która pozwala nam powiedzieć, ile rozwiązań ma dany układ i jakie zbiory dostarczają rozwią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 członu koniunkcji, który można uznać za pierwsze równanie. Tak wygląda graficzna reprezentacja tego drzewa

Drzewo składa się z dwóch poziomów w zależności od liczby zmiennych w równaniu. Pierwszy poziom opisuje pierwszą zmienną. Dwie gałęzie tego poziomu odzwierciedlają możliwe wartości tej zmiennej - 1 i 0. Na drugim poziomie gałęzie drzewa odzwierciedlają tylko te możliwe wartości zmiennej, dla których równanie ma wartość true. Ponieważ równanie określa implikację, gałąź, na której ma wartość 1, wymaga, aby na tej gałęzi znajdowała się wartość 1. Gałąź, na której ma wartość 0, generuje dwie gałęzie o wartościach równych 0 i 1. Skonstruowana drzewo określa trzy rozwiązania, z których implikacja przyjmuje wartość 1. Na każdej gałęzi zapisywany jest odpowiedni zestaw wartości zmiennych, dający rozwiązanie równania.

Te zbiory to: ((1, 1), (0, 1), (0, 0))

Kontynuujmy budowanie drzewa decyzyjnego, dodając następujące równanie i następującą implikację. Specyfika naszego układu równań polega na tym, że każde nowe równanie układu wykorzystuje jedną zmienną z poprzedniego równania, dodając jedną nową zmienną. Ponieważ zmienna ma już wartości w drzewie, to na wszystkich gałęziach, w których zmienna ma wartość 1, zmienna również będzie miała wartość 1. Dla takich gałęzi konstrukcja drzewa przechodzi na kolejny poziom, ale nowe gałęzie nie pojawiają się. Pojedyncza gałąź, w której zmienna ma wartość 0, rozgałęzi się na dwie gałęzie, w których zmienna otrzyma wartości 0 i 1. Zatem każde dodanie nowego równania, biorąc pod uwagę jego specyfikę, dodaje jedno rozwiązanie. Oryginalne pierwsze równanie:

ma 6 rozwiązań. 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 również ma 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 mieć dowolną wartość, zarówno 0, jak i 1. Zatem 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ń?

Temat lekcji: Rozwiązywanie równań logicznych

Edukacyjny - poznawanie metod rozwiązywania równań logicznych, rozwijanie umiejętności rozwiązywania równań logicznych i konstruowania wyrażeń logicznych z wykorzystaniem tabeli prawdy;

Rozwojowe - stwarzać warunki do rozwoju zainteresowań poznawczych uczniów, sprzyjać rozwojowi pamięci, uwagi, logiczne myślenie;

Edukacyjny : promowanie umiejętności słuchania opinii innych, pielęgnowanie woli i wytrwałości w osiąganiu końcowych rezultatów.

Typ lekcji: lekcja łączona

Sprzęt: komputer, rzutnik multimedialny, prezentacja 6.

Podczas zajęć

Powtarzanie i aktualizacja podstawowej wiedzy. Badanie Praca domowa(10 minut)

Na poprzednich lekcjach zapoznaliśmy się z podstawowymi prawami algebry logicznej i nauczyliśmy się wykorzystywać te prawa do upraszczania wyrażeń logicznych.

Sprawdźmy naszą pracę domową dotyczącą upraszczania wyrażeń logicznych:

1. Które z poniższych słów spełnia warunek logiczny:

(pierwsza spółgłoska litera → druga spółgłoska litera)٨ (samogłoska ostatniej litery → samogłoska przedostatniej litery)? Jeżeli jest kilka takich słów, wskaż najmniejsze z nich.

1) ANNA 2) MARIA 3) OLEG 4) STEPAN

Wprowadźmy następującą notację:

A – spółgłoska pierwszej litery

B – spółgłoska drugiej litery

S – samogłoska ostatniej litery

D – przedostatnia litera samogłoski

Zróbmy wyrażenie:

Zróbmy tabelę:

2. Wskaż, które wyrażenie logiczne jest równoważne wyrażeniu

Uprośćmy zapis oryginalnego wyrażenia i proponowanych opcji:

3. Biorąc pod uwagę fragment tablicy prawdy wyrażenia F:

Które wyrażenie pasuje do F?

Określmy wartości tych wyrażeń dla określonych wartości argumentów:

Wprowadzenie do tematu lekcji, prezentacja nowego materiału (30 minut)

Kontynuujemy naukę podstaw logiki, a tematem naszej dzisiejszej lekcji jest „Rozwiązywanie równań logicznych”. Studiowałem ten temat, poznasz podstawowe metody rozwiązywania równań logicznych, zdobędziesz umiejętność rozwiązywania tych równań z wykorzystaniem języka algebry logicznej oraz umiejętność komponowania wyrażenia logicznego z wykorzystaniem tabeli prawdy.

1. Rozwiąż równanie logiczne

(¬K M) → (¬L M N) =0

Zapisz swoją odpowiedź jako ciąg czterech znaków: wartości zmiennych K, L, M i N (w tej kolejności). I tak np. linia 1101 odpowiada faktowi, że K=1, L=1, M=0, N=1.

Rozwiązanie:

Przekształćmy wyrażenie(¬K  M) → (¬L  M  N)

Wyrażenie jest fałszywe, gdy oba wyrazy są fałszywe. Drugi wyraz jest równy 0, jeśli M =0, N =0, L =1. W pierwszym terminie K = 0, ponieważ M = 0, i
.

Odpowiedź: 0100

2. Ile rozwiązań ma równanie (w odpowiedzi wpisz tylko liczbę)?

Rozwiązanie: przekształć wyrażenie

(A +B)*(C +D)=1

A +B =1 i C +D =1

Metoda 2: sporządzenie tabeli prawdy

3 sposoby: konstrukcja SDNF - doskonałej rozłącznej postaci normalnej funkcji - alternatywy pełnych regularnych elementarnych koniunkcji.

Przekształćmy pierwotne wyrażenie, otwórzmy nawiasy, aby uzyskać alternatywę spójników:

(A+B)*(C+D)=A*C+B*C+A*D+B*D=

Uzupełnijmy spójniki, aby uzupełnić spójniki (iloczyn wszystkich argumentów), otwórz nawiasy:

Weźmy pod uwagę te same spójniki:

W rezultacie otrzymujemy SDNF zawierający 9 spójników. Dlatego tablica prawdy dla tej funkcji ma wartość 1 w 9 wierszach po 2 4 = 16 zestawów wartości zmiennych.

3. Ile rozwiązań ma równanie (w odpowiedzi wpisz tylko liczbę)?

Uprośćmy wyrażenie:

,

3 sposoby: budowa SDNF

Weźmy pod uwagę te same spójniki:

W rezultacie otrzymujemy SDNF zawierający 5 spójników. Dlatego tablica prawdy dla tej funkcji ma wartość 1 w 5 wierszach po 2 4 = 16 zestawów wartości zmiennych.

Konstruowanie wyrażenia logicznego przy użyciu tabeli prawdy:

dla każdego wiersza tabeli prawdy zawierającego 1, tworzymy iloczyn argumentów, a zmienne równe 0 włączamy do iloczynu z negacją, a zmienne równe 1 uwzględniamy bez negacji. Pożądane wyrażenie F będzie składać się z sumy otrzymanych produktów. Następnie, jeśli to możliwe, wyrażenie to należy uprościć.

Przykład: podana jest tabela prawdy wyrażenia. Zbuduj wyrażenie logiczne.

Rozwiązanie:

3. Praca domowa (5 minut)

Rozwiązać równanie:

Ile rozwiązań ma równanie (w odpowiedzi wpisz tylko liczbę)?

Korzystając z podanej tabeli prawdy, skonstruuj wyrażenie logiczne i

uprościć to.

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 operacje logiczne: spójniki, alternatywy, inwersje, implikacje i równoważności.

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.