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

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:

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

Materiał zawiera prezentację przedstawiającą metody rozwiązywania równań logicznych i układów równań logicznych w zadaniu B15 (nr 23, 2015) egzaminu Unified State Exam z informatyki. Wiadomo, że zadanie to należy do najtrudniejszych wśród zadań Jednolitego Egzaminu Państwowego. Prezentacja może być przydatna podczas prowadzenia zajęć z tematu „Logika” w klasach specjalistycznych, a także podczas przygotowań do egzaminu Unified State Exam.

Pobierać:

Zapowiedź:

Aby skorzystać z podglądu prezentacji utwórz konto Google i zaloguj się na nie: https://accounts.google.com

Podpisy slajdów:

Rozwiązanie zadania B15 (układy równań logicznych) Vishnevskaya M.P., MAOU „Gimnazjum nr 3” 18 listopada 2013 r., Saratów

Zadanie B15 jest jednym z najtrudniejszych na egzaminie jednolitym z informatyki!!! Testowane są następujące umiejętności: konwertowanie wyrażeń zawierających zmienne logiczne; opisać w języku naturalnym zbiór wartości zmiennych logicznych, dla którego dany zbiór zmiennych logicznych jest prawdziwy; policzyć liczbę zbiorów binarnych spełniających podane warunki. Najtrudniej jest dlatego, że... nie ma formalnych zasad, jak to zrobić, wymaga to domysłów.

Bez czego nie możesz się obejść!

Symbole koniunkcji: A /\ B , A  B , AB , A &B, A i B alternatywna: A \ / B , A + B , A | Negacja B , A lub B:  A , A, nie A Równoważność: A  B, A  B, A  B wyłączne „lub”: A  B , A xor B

Metoda zastępowania zmiennych Ile istnieje różnych zbiorów wartości zmiennych logicznych x1, x2, ..., x9, x10, które spełniają wszystkie poniższe warunki: ((x1 ≡ x2) \/ (x3 ≡ x4)) /\ (¬(x1 ≡ x2) \/ ¬(x3 ≡ x4)) = 1 ((x3 ≡ x4) \/ (x5 ≡ x6)) /\ (¬(x3 ≡ x4) \/ ¬(x5 ≡ x6)) = 1 ((x5 ≡ x6 ) \/ (x7 ≡ x8)) /\ (¬(x5 ≡ x7) \/ ¬(x7 ≡ x8)) = 1 ((x7 ≡ x8) \/ (x9 ≡ x10)) /\ (¬(x7 ≡ x8) \/ ¬(x9 ≡ x10)) = 1 Odpowiedź nie musi wymieniać wszystkich różnych zbiorów x1, x2, …, x9, x10, dla których ten system równości obowiązuje. W odpowiedzi należy podać ilość takich zestawów (wersja demonstracyjna 2012)

Rozwiązanie Krok 1. Uprość, zmieniając zmienne t1 = x1  x2 t2 = x3  x4 t3 = x5  x6 t4 = x7  x8 t5 = x9  x10 Po uproszczeniu: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 (t2 \/ t3) /\ (¬t2 \/ ¬ t3) =1 (t3 \/ t4) /\ (¬t3 \/ ¬ t4) =1 (t4 \/ t5) /\ ( ¬ t4 \/ ¬ t5) =1 Rozważmy jedno z równań: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Oczywiście =1 tylko wtedy, gdy jedna ze zmiennych wynosi 0, a druga 1 Użyjmy wzoru do wyrażenia operacji XOR poprzez koniunkcję i alternatywę: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) = t1  t2 = ¬(t1 ≡ t2) =1 ¬(t1 ≡ t2) =1 ¬( t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1

Krok 2. Analiza systemu ¬(t1 ≡ t2) =1 ¬(t2 ≡ t3) =1 ¬(t3 ≡ t4) =1 ¬(t4 ≡ t5) =1 t1 t2 t3 t4 t5 0 1 0 1 0 1 0 1 0 1 Т .Do. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), wówczas każdej wartości tk odpowiadają dwie pary wartości x2k-1 i x2k, przykładowo: tk =0 odpowiada dwóm parom - (0 ,1) i (1, 0) oraz tk =1 – pary (0,0) i (1,1).

Krok 3. Liczenie liczby rozwiązań. Każde t ma 2 rozwiązania, liczba ts wynosi 5. Zatem. dla zmiennych t istnieje 2 5 = 32 rozwiązań. Ale każdemu t odpowiada para rozwiązań x, tj. oryginalny system ma 2*32 = 64 rozwiązania. Odpowiedź: 64

Metoda eliminacji części rozwiązań Ile istnieje różnych zbiorów wartości zmiennych logicznych x1, x2, ..., x5, y1,y2,..., 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; y5 → x5 =1. Odpowiedź nie wymaga wymieniania wszystkich różnych zbiorów x1, x2, ..., x5, y 1 , y2, ... , y5, dla których obowiązuje ten układ równości. Odpowiedź musi wskazywać liczbę takich zestawów.

Rozwiązanie. Krok 1. Sekwencyjne rozwiązanie równań x1 1 0 x2 1 0 1 x3 1 0 1 1 x4 1 0 1 1 1 x5 1 0 1 1 1 1 Pierwsze równanie jest koniunkcją kilku operacji implikacji równych 1, tj. każda z implikacji jest prawdziwa. Implikacja jest fałszywa tylko w jednym przypadku, gdy 1  0, we wszystkich pozostałych przypadkach (0  0, 0  1, 1  1) operacja zwraca 1. Zapiszmy to w formie tabelarycznej:

Krok 1. Sekwencyjne rozwiązanie równań T.o. Otrzymano 6 zestawów rozwiązań dla x1, x2, x3, x4, x5: (00000), (00001), (00011), (00111), (01111), (11111). Rozumując podobnie dochodzimy do wniosku, że dla y1, y2, y3, y4, y5 istnieje ten sam zbiór rozwiązań. Ponieważ równania te są niezależne, tj. nie mają wspólnych zmiennych, wówczas rozwiązaniem tego układu równań (bez uwzględnienia trzeciego równania) będzie 6 * 6 = 36 par „X” i „Y”. Rozważmy trzecie równanie: y5 → x5 =1 Rozwiązaniem są pary: 0 0 0 1 1 1 Para nie jest rozwiązaniem: 1 0

Porównajmy otrzymane rozwiązania, gdzie y5 =1, x5=0 nie jest odpowiednie. takich par jest 5. Liczba rozwiązań układu: 36-5= 31. Odpowiedź: Potrzebna była 31 kombinatoryka!!!

Metoda programowania dynamicznego Ile różnych rozwiązań ma równanie logiczne x 1 → x 2 → x 3 → x 4 → x 5 → x 6 = 1, gdzie x 1, x 2, …, x 6 są zmiennymi logicznymi? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości zmiennych, dla których zachodzi ta równość. W odpowiedzi należy podać ilości takich zestawów.

Rozwiązanie Krok 1. Analiza warunku Po lewej stronie w równaniu zapisywane są kolejno operacje implikacji, priorytet jest taki sam. Przepiszmy: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Uwaga! Każda kolejna zmienna zależy nie od poprzedniej, ale od wyniku poprzedniej implikacji!

Krok 2. Odkrywanie wzoru Rozważmy pierwszą implikację, X 1 → X 2. Tabela prawdy: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jednego 0 otrzymaliśmy 2 jednostki, a z 1 mamy jedno 0 i jedno 1. Jest tylko jedno 0 i trzy jedynki, to jest wynik pierwszej operacji.

Krok 2. Odkrywanie wzoru Łącząc x 3 z wynikiem pierwszej operacji, otrzymujemy: F(x 1 ,x 2) x 3 F(x 1 ,x 2)  x 3 0 0 1 0 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1 0 0 1 1 1 Z dwóch 0 – dwa 1, z każdego 1 (jest ich 3) jedno 0 i jedno 1 (3+3)

Krok 3. Wyprowadzenie wzoru T.o. można tworzyć wzory na obliczenie liczby zer N i liczby jedynek E i dla równania z i zmiennymi: ,

Krok 4. Wypełnianie tabeli Wypełnijmy tabelę od lewej do prawej dla i = 6, obliczając liczbę zer i jedynek za pomocą powyższych wzorów; tabela pokazuje jak zbudowana jest kolejna kolumna z poprzedniej: liczba zmiennych 1 2 3 4 5 6 liczba zer N i 1 1 3 5 11 21 liczba jedynek E i 1 2*1+1= 3 2*1 +3= 5 11 21 43 Odpowiedź: 43

Metoda wykorzystująca uproszczenia wyrażeń logicznych Ile różnych rozwiązań ma równanie ((J → K) → (M  N  L))  ((M  N  L) → (¬ J  K))  (M → J) = 1 gdzie J, K, L, M, N są zmiennymi logicznymi? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości J, K, L, M i N, dla których zachodzi ta równość. W odpowiedzi należy podać liczbę takich zestawów.

Rozwiązanie Zauważ, że J → K = ¬ J  K Wprowadźmy zmianę zmiennych: J → K=A, M  N  L =B Przepiszmy równanie uwzględniając zmianę: (A → B)  (B → A)  (M → J)=1 4. (A  B)  (M → J)= 1 5. Oczywiście A  B dla tych samych wartości A i B 6. Rozważmy ostatnią implikację M → J =1 Jest to możliwe jeżeli: M= J=0 M=0, J=1 M=J=1

Rozwiązanie Ponieważ A  B, wtedy Gdy M=J=0 otrzymujemy 1 + K=0. Żadnych rozwiązań. Gdy M=0, J=1 otrzymujemy 0 + K=0, K=0, a N i L są dowolne, 4 rozwiązania: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 1

Rozwiązanie 10. Gdy M=J=1 otrzymujemy 0+K=1 *N * L lub K=N*L, 4 rozwiązania: 11. Suma ma 4+4=8 rozwiązań Odpowiedź: 8 K N L 0 0 0 0 0 1 0 1 0 1 1 1

Źródła informacji: O.B. Bogomołowa, D.Yu. Usenkov. B15: nowe zadania i nowe rozwiązania // Informatyka, nr 6, 2012, s. 25 35 – 39. K.Yu. Poliakow. Równania logiczne // Informatyka, nr 14, 2011, s. 2. 30-35. http://ege-go.ru/zadania/grb/b15/, [Zasoby elektroniczne]. http://kpolyakov.narod.ru/school/ege.htm, [Zasoby elektroniczne].

Cel usługi. Kalkulator online jest przeznaczony dla konstruowanie tabeli prawdy dla wyrażenia logicznego.
Tabela prawdy – tabela zawierająca wszystkie możliwe kombinacje zmiennych wejściowych i odpowiadających im wartości wyjściowych.
Tabela prawdy zawiera 2n wierszy, gdzie n to liczba zmiennych wejściowych, a n+m to kolumny, gdzie m to zmienne wyjściowe.

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

Na przykład wyrażenie logiczne abc+ab~c+a~bc należy wprowadzić w następujący sposób: a*b*c+a*b=c+a=b*c
Aby wprowadzić dane w postaci diagramu logicznego, skorzystaj z tej usługi.

Zasady wprowadzania funkcji logicznej

Zamiast symbolu v (alternatywa, OR) użyj znaku +.
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) .
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)

Operacji logicznej NIE stosuje się do pojedynczego argumentu, który może być prostym lub złożonym wyrażeniem logicznym. Wynik operacji NIE jest następujący:

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.

Następujące konwencje NIE są akceptowane w przypadku operacji negacji:
nie A, Ā, nie A, ¬A, !A
Wynik operacji negacji NIE jest określony przez poniższą tabelę prawdy:

A	ani
0	1
1	0

Wynik operacji negacji jest prawdziwy, gdy pierwotna instrukcja jest fałszywa i odwrotnie.

Operacja OR - dodawanie logiczne (alternatywa, suma)

Logiczna operacja OR pełni funkcję łączenia dwóch instrukcji, które mogą być prostym lub złożonym wyrażeniem logicznym. Instrukcje będące punktami wyjścia operacji logicznej nazywane są argumentami. Wynikiem operacji OR jest wyrażenie, które będzie prawdziwe wtedy i tylko wtedy, gdy przynajmniej jedno z pierwotnych wyrażeń będzie prawdziwe.
Stosowane oznaczenia: A lub B, A V B, A lub B, A||B.
Wynik operacji OR określa poniższa tabela prawdy:
Wynikiem operacji OR jest prawda, gdy A jest prawdą, B jest prawdą, lub oba A i B są prawdą, a fałszem, gdy argumenty A i B są fałszywe.

Operacja AND - mnożenie logiczne (koniunkcja)

Operacja logiczna AND pełni funkcję przecięcia dwóch instrukcji (argumentów), które mogą być prostym lub złożonym wyrażeniem logicznym. Wynikiem operacji AND jest wyrażenie, które będzie prawdziwe wtedy i tylko wtedy, gdy oba pierwotne wyrażenia będą prawdziwe.
Stosowane oznaczenia: A i B, A Λ B, A i B, A i B.
Wynik operacji AND określa poniższa tabela prawdy:

A	B	A i B
0	0	0
0	1	0
1	0	0
1	1	1

Wynik operacji AND jest prawdziwy wtedy i tylko wtedy, gdy oba stwierdzenia A i B są prawdziwe, a we wszystkich pozostałych przypadkach fałszywe.

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

Operacja ta łączy dwa proste wyrażenia logiczne, z których pierwsze jest warunkiem, a drugie konsekwencją tego warunku.
Stosowane oznaczenia:
jeśli A, to B; A pociąga za sobą B; jeśli A, to B; A → B.
Tabela prawdy:

A	B	A → B
0	0	1
0	1	1
1	0	0
1	1	1

Wynik operacji implikacji jest fałszywy tylko wtedy, gdy przesłanka A jest prawdziwa, a wniosek B (konsekwencja) jest fałszywy.

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

Stosowane oznaczenie: A ↔ B, A ~ B.
Tabela prawdy:

A	B	A↔B
0	0	1
0	1	0
1	0	0
1	1	1

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

Stosowana notacja: A XOR B, A ⊕ B.
Tabela prawdy:

A	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Wynik operacji równoważności jest prawdziwy tylko wtedy, gdy A i B są jednocześnie prawdziwe lub fałszywe.

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

Doskonała rozłączna postać normalna wzoru(SDNF) jest wzorem równoważnym, stanowiącym alternatywę spójników elementarnych i posiadającym następujące właściwości:

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

SDNF można uzyskać za pomocą tablic prawdy lub stosując równoważne transformacje.
Dla każdej funkcji SDNF i SCNF są jednoznacznie zdefiniowane aż do permutacji.

Doskonała spójna forma normalna

Doskonała spójna forma normalna wzoru (SCNF) Jest to równoważny mu wzór, będący koniunkcją elementarnych alternatyw i spełniający własności:

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

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

Kirgizova E.V., Nemkova A.E.

Lesosybirski Instytut Pedagogiczny –

oddział Syberyjskiego Uniwersytetu Federalnego w Rosji

Umiejętność spójnego myślenia, przekonującego rozumowania, stawiania hipotez i obalania negatywnych wniosków nie przychodzi sama z siebie; umiejętność tę rozwija nauka logiki. Logika jest nauką badającą metody ustalania prawdziwości lub fałszywości niektórych stwierdzeń na podstawie prawdziwości lub fałszywości innych stwierdzeń.

Opanowanie podstaw tej nauki nie jest możliwe bez rozwiązania problemów logicznych. Sprawdzanie rozwoju umiejętności zastosowania wiedzy w nowej sytuacji odbywa się poprzez zaliczenie. W szczególności jest to umiejętność rozwiązywania problemów logicznych. Zadania B15 na egzaminie Unified State Examination są zadaniami o zwiększonej złożoności, ponieważ zawierają układy równań logicznych. Istnieją różne sposoby rozwiązywania układów równań logicznych. Jest to redukcja do jednego równania, konstrukcja tabeli prawdy, rozkład, sekwencyjne rozwiązywanie równań itp.

Zadanie:Rozwiąż układ równań logicznych:

Rozważmy metoda redukcji do jednego równania . Metoda ta polega na przekształceniu równań logicznych w taki sposób, aby ich prawe strony były równe wartości logicznej (czyli 1). Aby to zrobić, użyj operacji logicznej negacji. Następnie, jeśli równania zawierają złożone operacje logiczne, zastępujemy je podstawowymi: „AND”, „OR”, „NOT”. Kolejnym krokiem jest połączenie równań w jedno, równoważne układowi, za pomocą operacji logicznej „AND”. Następnie należy przekształcić powstałe równanie w oparciu o prawa algebry logicznej i uzyskać konkretne rozwiązanie układu.

Rozwiązanie 1:Zastosuj inwersję do obu stron pierwszego równania:

Wyobraźmy sobie implikację poprzez podstawowe operacje „LUB” i „NIE”:

Ponieważ lewe strony równań są równe 1, możemy je połączyć za pomocą operacji „AND” w jedno równanie równoważne układowi pierwotnemu:

Otwieramy pierwszy nawias zgodnie z prawem De Morgana i otrzymany wynik przekształcamy:

Otrzymane równanie ma jedno rozwiązanie: A= 0, B = 0 i C = 1.

Następna metoda to konstruowanie tablic prawdy . Ponieważ wielkości logiczne mają tylko dwie wartości, można po prostu przejrzeć wszystkie opcje i znaleźć wśród nich te, dla których spełniony jest dany układ równań. Oznacza to, że budujemy jedną wspólną tabelę prawdy dla wszystkich równań układu i znajdujemy linię z wymaganymi wartościami.

Rozwiązanie 2:Utwórzmy tabelę prawdy dla systemu:








0	0	1	1	0	1

Linia, dla której spełnione są warunki zadania, została wyróżniona pogrubioną czcionką. Zatem A =0, B =0 i C =1.

Sposób rozkład . Chodzi o to, aby ustalić wartość jednej ze zmiennych (ustawić ją na 0 lub 1) i w ten sposób uprościć równania. Następnie możesz ustalić wartość drugiej zmiennej i tak dalej.

Rozwiązanie 3: Pozwalać A = 0, wówczas:

Z pierwszego równania otrzymujemy B =0, a od drugiego – C=1. Rozwiązanie układu: A = 0, B = 0 i C = 1.

Możesz także skorzystać z tej metody sekwencyjne rozwiązywanie równań , na każdym kroku dodając jedną zmienną do rozważanego zbioru. W tym celu należy przekształcić równania tak, aby zmienne były wprowadzane w kolejności alfabetycznej. Następnie budujemy drzewo decyzyjne, dodając kolejno do niego zmienne.

Pierwsze równanie układu zależy tylko od A i B, a drugie równanie od A i C. Zmienna A może przyjmować 2 wartości 0 i 1:

Z pierwszego równania wynika, że , więc kiedy A = 0 i otrzymujemy B = 0, a dla A = 1 mamy B = 1. Zatem pierwsze równanie ma dwa rozwiązania w odniesieniu do zmiennych A i B.

Przedstawmy drugie równanie, z którego wyznaczamy wartości C dla każdej opcji. Gdy A = 1, implikacja nie może być fałszywa, co oznacza, że druga gałąź drzewa nie ma rozwiązania. Na A= 0 otrzymujemy jedyne rozwiązanie C= 1 :

W ten sposób otrzymaliśmy 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 jest zastą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 wyznaczyć liczbę rozwiązań nowego układu. 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 . Uwzględniając nowe zmienne, równanie zostanie zapisane jako: X + Y = 1.

Rozłączenie jest prawdziwe w trzech przypadkach: (0;1), (1;0) i (1;1), natomiast X i Y jest implikacją, to znaczy jest prawdziwa w trzech przypadkach i fałszywa 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 całkowite możliwe rozwiązania tego równania to 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, żeX 1 – jest prawdą, to z pierwszego równania to otrzymujemyX 2 to samo prawda, od drugiego -X 3 =1 i tak dalej, aż x m= 1. Zatem zbiór (1; 1; …; 1) z M jednostek jest rozwiązaniem układu. Niech to terazX 1 =0, to z pierwszego równania, które mamyX 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. NaX 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 ( M +1 rozwiązanie w każdym rozwiązaniu 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 zobaczyć, że jest równy m +1.

Zmienne	Drzewo	Liczba rozwiązań
x 1
x 2
x 3

W przypadku trudności w rozumowaniu i budowaniu drzewa decyzyjnego można poszukać rozwiązania 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)*

Następnie widać, że jedno równanie jest prawdziwe w trzech przypadkach: (0; 0), (0; 1), (1; 1). Układ dwóch równań jest prawdziwy w czterech przypadkach (0; 0; 0), (0; 0; 1), (0; 1; 1), (1; 1; 1). W tym przypadku od razu widać, że istnieje rozwiązanie składające się tylko z zer i więcej M rozwiązania, w których dodawana jest jedna jednostka na raz, zaczynając od ostatniej pozycji, aż do zapełnienia wszystkich możliwych miejsc. Można założyć, że rozwiązanie ogólne będzie miało tę samą postać, jednak aby takie podejście stało się rozwiązaniem, potrzebny jest dowód, że założenie jest prawidłowe.

Podsumowując powyższe, chciałbym zwrócić uwagę na fakt, że nie wszystkie omówione metody są uniwersalne. Rozwiązując każdy układ równań logicznych należy wziąć pod uwagę jego cechy, na podstawie których należy wybrać metodę rozwiązania.

Literatura:

1. Problemy logiczne / O.B. Bogomołow – wyd. 2. – M.: BINOM. Laboratorium Wiedzy, 2006. – 271 s.: il.

2. Polyakov K.Yu. Układy równań logicznych / Gazeta dydaktyczno-metodyczna dla nauczycieli informatyki: Informatyka nr 14, 2011.

Istnieją różne sposoby rozwiązywania 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:

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.

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.

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 wyznaczyć liczbę rozwiązań nowego układu. 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. Uwzględniając nowe zmienne, równanie zostanie zapisane jako: 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 całkowite możliwe rozwiązania tego równania to 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 samo prawda, od drugiego - X 3 =1 i tak dalej, aż x m= 1. Oznacza to, że zbiór (1; 1; …; 1) m jednostek jest rozwiązaniem układu. Niech to teraz X 1 =0, to z pierwszego równania, które mamy X 2 =0 lub X 2 =1.

Gdy X 2 prawda, otrzymujemy, że pozostałe zmienne są również prawdziwe, czyli zbiór (0; 1; ...; 1) jest rozwiązaniem układu. Na X 2 =0 rozumiemy to X 3 =0 lub X 3 = i tak dalej. Kontynuując ostatnią zmienną stwierdzamy, że rozwiązaniami równania są następujące zbiory zmiennych (rozwiązanie m +1, każde rozwiązanie zawiera m wartości zmiennych):