Rozwiązuj równania logiczne online w informatyce. Logika. Funkcje logiczne. Rozwiązywanie równań

Noskin Andriej Nikołajewicz,
nauczyciel informatyki
najwyższa kategoria kwalifikacyjna,
Kandydat nauk wojskowych, profesor nadzwyczajny
Liceum GBOU nr 1575, Moskwa

Zoptymalizowana metoda mapowania do rozwiązania problemu 23 z KIM Unified State Examination z informatyki i ICT

Jednym z najtrudniejszych zadań w egzaminie Unified State Exam KIM jest zadanie 23, w którym należy znaleźć liczbę różnych zbiorów wartości zmiennych logicznych spełniających podany warunek.
To zadanie jest chyba najbardziej trudne zadanie KIM Jednolity egzamin państwowy z informatyki i ICT. Z reguły radzi sobie z tym nie więcej niż 5% zdających (1).
Tak niewielki odsetek uczniów, którzy wykonali to zadanie, tłumaczy się następująco:
- uczniowie mogą pomylić (zapomnieć) znaki operacji logicznych;
- błędy matematyczne w procesie wykonywania obliczeń;
- błędy w rozumowaniu przy poszukiwaniu rozwiązania;
- błędy w procesie upraszczania wyrażeń logicznych;
- nauczyciele zalecają rozwiązanie tego problemu po ukończeniu całej pracy, ponieważ prawdopodobieństwo
błędów jest bardzo dużo, a „waga” zadania to tylko jeden z głównych punktów.
Ponadto niektórzy nauczyciele sami mają trudności z rozwiązaniem tego typu problemów i dlatego starają się z dziećmi rozwiązywać prostsze problemy.
Sytuację komplikuje również fakt, że w tym bloku jest duża liczba różne zadania i nie ma możliwości wyboru rozwiązania szablonowego.
Aby naprawić tę sytuację, społeczność pedagogiczna finalizuje dwie główne metody rozwiązywania problemów tego typu: rozwiązanie wykorzystujące łańcuchy bitów (2) i metodę mapowania (3).
Konieczność udoskonalenia (optymalizacji) tych metod wynika z faktu, że zadania stale zmieniają się zarówno pod względem struktury, jak i liczby zmiennych (tylko jeden typ zmiennych X, dwa typy zmiennych X i Y, trzy typy: X, Y , Ż.).
Trudność opanowania tych metod rozwiązywania problemów potwierdza fakt, że na stronie internetowej K.Yu. Polyakova istnieje 38 analiz tego typu problemu (4). Niektóre analizy dostarczają więcej niż jednego rodzaju rozwiązania problemu.
Ostatnio w KIM Unified State Examination z informatyki występują problemy z dwoma rodzajami zmiennych X i Y.
Zoptymalizowałem metodę wyświetlania i zachęcam moich uczniów do korzystania z ulepszonej metody.
To daje rezultaty. Odsetek moich uczniów, którzy radzą sobie z tym zadaniem, waha się w granicach 43% zdających. Z reguły co roku do Jednolitego Egzaminu Państwowego z informatyki przystępuje od 25 do 33 uczniów ze wszystkich 11. klas.
Przed pojawieniem się problemów z dwoma typami zmiennych uczniowie z powodzeniem stosowali metodę mapowania, jednak po pojawieniu się Y w wyrażeniu logicznym zaczęłam zauważać, że odpowiedzi dzieci nie pokrywały się już z testami. Okazało się, że nie byli do końca pewni, jak utworzyć tabelę odwzorowań z nowym typem zmiennej. Wtedy przyszła mi do głowy myśl, że dla wygody całe wyrażenie należy sprowadzić do jednego typu zmiennej, tak jak jest to wygodne dla dzieci.
Podam tę technikę bardziej szczegółowo. Dla wygody rozważę to na przykładzie układu wyrażeń logicznych podanego w (4).
Ile różne rozwiązania ma układ równań logicznych

(x 1 ^ tak 1)=(¬x 2 V ¬ y 2 )
(x 2 ^ tak 2)= (¬ X 3 V ¬ y 3 )
...
(x 5 ^ y 5) = (¬ X 6 V ¬ y 6 )

GdzieX 1 , …, X 6 , y 1 , …, y 6 , - zmienne logiczne? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości zmiennych, dla których zachodzi ta równość. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
1. Z analizy układu równań logicznych widzimy, że istnieje 6 zmiennych X i 6 zmiennych U. Ponieważ każda z tych zmiennych może przyjmować tylko dwie wartości (0 i 1), zastępujemy te zmienne 12 zmiennymi tego samego typu, na przykład Z.
2. Przepiszmy teraz system, dodając nowe zmienne tego samego typu. Trudność zadania polegać będzie na robieniu dokładnych notatek podczas zastępowania zmiennych.

(z 1 ^ z 2)= (¬z 3V¬ z 4 )
(z 3 ^ z 4)= (¬ z 5 V¬ z 6 )
...
(z 9 ^ z 10) = (¬ z 11 V¬ z 12)

3. Stwórzmy tabelę, w której omówimy wszystkie opcje z 1 , z 2 , z 3 , z 4 , ponieważ w pierwszym równaniu logicznym znajdują się cztery zmienne, tabela będzie miała 16 wierszy (16=2 4); usuń takie wartości z tabeli z 4 , dla którego pierwsze równanie nie ma rozwiązania (liczby przekreślone).


0	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1
1	0	0	0
			1
		1	0
			1
	1	0	0
			1
		1	0
			1

4. Analizując tabelę budujemy regułę wyświetlania par zmiennych (np. para Z 1 Z 2 =00 odpowiada para Z 3 Z 4 = 11) .

5. Wypełnij tabelę, obliczając liczbę par zmiennych, dla których system ma rozwiązanie.

6. Dodaj wszystkie wyniki: 9 + 9 + 9 + 27 = 54
7. Odpowiedź: 54.
Powyższa zoptymalizowana metodologia rozwiązania problemu 23 z Unified State Exam KIM pozwoliła uczniom odzyskać pewność siebie i skutecznie rozwiązać tego typu problem.

Literatura:

1. FIPI. Wytyczne dla nauczycieli, przygotowany na podstawie analizy typowych błędów popełnianych przez uczestników Jednolitego Egzaminu Państwowego 2015 z informatyki i ICT. Tryb dostępu: http://www.fipi.ru/sites/default/files/document/1442163533/informatika_i_ikt.pdf

2. K.Yu. Polyakov, MA Roitberga.Układy równań logicznych: rozwiązanie za pomocą ciągów bitowych. Journal of Informatics, nr 12, 2014, s. 10-12. 4-12. Wydawnictwo „Pierwszy września”, Moskwa.
3. EA Mironczik, Metoda wyświetlania. Czasopismo Informatyka, nr 10, 2013, s. 10-10. 18-26. Wydawnictwo „Pierwszy września”, Moskwa.

J ∧ ¬K ∧ L ∧ ¬M ∧ (N ∨ ¬N) = 0, gdzie J, K, L, M, N są zmiennymi logicznymi?

Wyjaśnienie.

Zatem wyrażenie (N ∨ ¬N) jest prawdziwe dla dowolnego N

J ∧ ¬K ∧ L ∧ ¬M = 0.

Zastosujmy negację do obu stron równania logicznego i skorzystajmy z prawa De Morgana ¬ (A ∧ B) = ¬ A ∨ ¬ B. Otrzymujemy ¬J ∨ K ∨ ¬L ∨ M = 1.

Suma logiczna jest równa 1, jeśli przynajmniej jedno z jej zdań składowych jest równe 1. Zatem otrzymane równanie jest spełnione przez dowolną kombinację zmiennych logicznych, z wyjątkiem przypadku, gdy wszystkie wielkości zawarte w równaniu są równe 0. Każda z nich 4 zmienne mogą być równe 1 lub 0, dlatego wszystkie możliwe kombinacje to 2,2,2,2 = 16. Zatem równanie ma 16 -1 = 15 rozwiązań.

Należy zauważyć, że 15 znalezionych rozwiązań odpowiada któremukolwiek z nich możliwa wartość wartości zmiennej logicznej N, więc pierwotne równanie ma 30 rozwiązań.

Odpowiedź: 30

Ile różnych rozwiązań ma równanie?

((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ ¬K) → ¬ (M ∧ N ∧ L)) ∧ (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.

Wyjaśnienie.

Używamy wzorów A → B = ¬A ∨ B i ¬(A ∨ B) = ¬A ∧ ¬B

Rozważmy pierwszą podformułę:

(J → K) → (M ∧ N ∧ L) = ¬(¬J ∨ K) ∨ (M ∧ N ∧ L) = (J ∧ ¬K) ∨ (M ∧ N ∧ L)

Rozważmy drugą podformułę

(J ∧ ¬K) → ¬(M ∧ N ∧ L) = ¬(J ∧ ¬K) ∨ ¬(M ∧ N ∧ L) = (¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L

Rozważmy trzecią podformułę

1) M → J = 1 zatem,

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (1 ∧ N ∧ L) = ¬K ∨ N ∧ L;

(0 ∨ K) ∨ 0 ∨ ¬N ∨ ¬L = K ∨ ¬N ∨ ¬L;

Połączmy:

¬K ∨ N ∧ L ∧ K ∨ ¬N ∨ ¬L = 0 ∨ L ∨ 0 ∨ ¬L = L ∨ ¬L = 1 stąd 4 rozwiązania.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (1 ∧ ¬K) ∨ (0 ∧ N ∧ L) = ¬K;

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (0 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L = K ∨ 1 ∨ ¬N ∨ ¬L

Połączmy:

K ∨ 1 ∨ ¬N ∨ ¬L ∧ ¬K = 1 ∨ ¬N ∨ ¬L stąd 4 rozwiązania.

c) M = 0 J = 0.

(J ∧ ¬K) ∨ (M ∧ N ∧ L) = (0 ∧ ¬K) ∨ (0 ∧ N ∧ L) = 0.

(¬J ∨ K) ∨ ¬M ∨ ¬N ∨ ¬L = (1 ∨ K) ∨ 1 ∨ ¬N ∨ ¬L.

Odpowiedź: 4 + 4 = 8.

Odpowiedź: 8

Ile różnych rozwiązań ma równanie?

((K ∨ L) → (L ∧ M ∧ N)) = 0

gdzie K, L, M, N są zmiennymi logicznymi? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości K, L, M i N, dla których zachodzi ta równość. Jako odpowiedź należy podać liczbę takich zestawów.

Wyjaśnienie.

Przepiszmy równanie, stosując prostszą notację operacji:

((K + L) → (L M N)) = 0

1) z tablicy prawdy operacji „implikacji” (patrz problem pierwszy) wynika, że równość ta jest prawdziwa wtedy i tylko wtedy, gdy jednocześnie

K + L = 1 i L M N = 0

2) z pierwszego równania wynika, że co najmniej jedna ze zmiennych K lub L jest równa 1 (lub obie razem); więc rozważmy trzy przypadki

3) jeśli K = 1 i L = 0, to druga równość jest spełniona dla dowolnego M i N; ponieważ istnieją 4 kombinacje dwóch zmiennych boolowskich (00, 01, 10 i 11), mamy 4 różne rozwiązania

4) jeśli K = 1 i L = 1, to druga równość zachodzi dla M · N = 0; są 3 takie kombinacje (00, 01 i 10), mamy jeszcze 3 rozwiązania

5) jeśli K = 0, to L = 1 (z pierwszego równania); w tym przypadku druga równość jest spełniona, gdy M · N = 0; są 3 takie kombinacje (00, 01 i 10), mamy jeszcze 3 rozwiązania

6) w sumie otrzymujemy 4 + 3 + 3 = 10 rozwiązań.

Odpowiedź: 10

Ile różnych rozwiązań ma równanie?

(K ∧ L) ∨ (M ∧ N) = 1

Wyjaśnienie.

Wyrażenie jest prawdziwe w trzech przypadkach, gdy (K ∧ L) i (M ∧ N) są równe odpowiednio 01, 11, 10.

1) „01” K ∧ L = 0; M ∧ N = 1, => M, N są równe 1, a K i L są czymkolwiek oprócz jednocześnie 1. Zatem istnieją 3 rozwiązania.

2) „11” K ∧ L = 1; M ∧ N = 1. => 1 rozwiązanie.

3) „10” K ∧ L = 1; M ∧ N = 0. => 3 rozwiązania.

Odpowiedź: 7.

Odpowiedź: 7

Ile różnych rozwiązań ma równanie?

(X ∧ Y ∨ Z) → (Z ∨ P) = 0

gdzie X, Y, Z, P są zmiennymi logicznymi? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości, dla których obowiązuje ta równość. W odpowiedzi wystarczy podać liczbę takich zestawów.

Wyjaśnienie.

(X ∧ Y ∨ Z) → (Z ∨ P) = 0 =>

¬(X ∧ Y ∨ Z) ∨ (Z ∨ P) = 0;

(¬X ∨ ¬Y ∧ ¬Z) ∨ (Z ∨ P) = 0;

Logiczne OR jest fałszywe tylko w jednym przypadku: gdy oba wyrażenia są fałszywe.

Stąd,

(Z ∨ P) = 0 => Z = 0, P = 0.

¬X ∨ ¬Y ∧ ¬Z = 0 => ¬X ∨ ¬Y ∧ 1 = 0 =>

¬X ∨ ¬Y = 0 => X = 1; Y = 1.

Dlatego równanie ma tylko jedno rozwiązanie.

Odpowiedź 1

Ile różnych rozwiązań ma równanie?

(K ∨ L) ∧ (M ∨ N) = 1

gdzie K, L, M, N są zmiennymi logicznymi? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości K, L, M i N, dla których zachodzi ta równość. W odpowiedzi wystarczy podać liczbę takich zestawów.

Wyjaśnienie.

Logiczne I jest prawdziwe tylko w jednym przypadku: gdy wszystkie wyrażenia są prawdziwe.

K ∨ L = 1, M ∨ N = 1.

Każde równanie daje 3 rozwiązania.

Rozważ równanie A ∧ B = 1, jeśli zarówno A, jak i B przyjmą prawdziwe wartości w każdym z trzech przypadków, to w sumie równanie ma 9 rozwiązań.

Dlatego odpowiedź brzmi 9.

Odpowiedź: 9

Ile różnych rozwiązań ma równanie?

((A → B)∧ C) ∨ (D ∧ ¬D)= 1,

gdzie A, B, C, D są zmiennymi logicznymi?

Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości A, B, C, D, dla których zachodzi ta równość. W odpowiedzi należy podać liczbę takich zestawów.

Wyjaśnienie.

Logiczne „OR” jest prawdziwe, gdy przynajmniej jedno ze stwierdzeń jest prawdziwe.

(D ∧ ¬D)= 0 dla dowolnego D.

Stąd,

(A → B)∧ C) = 1 => C = 1; A → B = 1 => ¬ A ∨ B = 1, co daje nam 3 możliwe rozwiązania dla każdego D.

(D ∧ ¬ D)= 0 dla dowolnego D, co daje nam dwa rozwiązania (dla D = 1, D = 0).

Zatem: całkowite rozwiązania 2*3 = 6.

Łącznie 6 rozwiązań.

Odpowiedź: 6

Ile różnych rozwiązań ma równanie?

(¬K ∨ ¬L ∨ ¬M) ∧ (L ∨ ¬M ∨ ¬N) = 0

Wyjaśnienie.

Zastosujmy negację do obu stron równania:

(K ∧ L ∧ M) ∨ (¬L ∧ M ∧ N) = 1

Logiczne LUB jest prawdziwe w trzech przypadkach.

Opcja 1.

K ∧ L ∧ M = 1, następnie K, L, M = 1 i ¬L ∧ M ∧ N = 0. N jest dowolne, to znaczy 2 rozwiązania.

Opcja 2.

¬L ∧ M ∧ N = 1, następnie N, M = 1; L = 0, K dowolne, czyli 2 rozwiązania.

Dlatego odpowiedź brzmi 4.

Odpowiedź: 4

A, B i C są liczbami całkowitymi, dla których stwierdzenie jest prawdziwe

¬ (A = B) ∧ ((A > B) → (B > C)) ∧ ((B > A) → (C > B)).

Ile wynosi B, jeśli A = 45 i C = 43?

Wyjaśnienie.

1) ¬(A = B); (A > B) → (B > C); (B > A) → (C > B);

2) te proste instrukcje łączy operacja ∧ (AND, koniunkcja), czyli muszą być wykonane jednocześnie;

3) z ¬(A = B)=1 natychmiast wynika, że A B;

4) załóżmy, że A > B, to z drugiego warunku otrzymujemy 1 →(B > C)=1; to wyrażenie może być prawdziwe wtedy i tylko wtedy, gdy B > C = 1;

5) zatem mamy A > B > C, tylko liczba 44 odpowiada temu warunkowi;

6) na wszelki wypadek sprawdźmy jeszcze opcję A 0 →(B > C)=1;

to wyrażenie jest prawdziwe dla dowolnego B; teraz spójrz na trzeci warunek, który otrzymujemy

wyrażenie to może być prawdziwe wtedy i tylko wtedy, gdy C > B, i tu mamy sprzeczność, gdyż nie ma takiej liczby B, dla której C > B > A.

Odpowiedź: 44.

Odpowiedź: 44

Zbuduj tabelę prawdy dla funkcji logicznej

X = (A ↔ B) ∨ ¬(A → (B ∨ C))

w którym kolumna wartości argumentu A jest binarną reprezentacją liczby 27, kolumna wartości argumentu B jest liczbą 77, kolumna wartości argumentu C jest liczbą 120. Liczba w kolumnie zapisuje się od góry do dołu, od najbardziej znaczącego do najmniej znaczącego (łącznie z zestawem zerowym). Konwertuj wynikową reprezentację binarną wartości funkcji X na system liczb dziesiętnych.

Wyjaśnienie.

Zapiszmy równanie, stosując prostszą notację operacji:

1) jest to wyrażenie z trzema zmiennymi, więc w tabeli prawdy będą linie; dlatego binarna reprezentacja liczb użytych do zbudowania kolumn tabeli A, B i C musi składać się z 8 cyfr

2) przekonwertuj liczby 27, 77 i 120 na system binarny, natychmiast dodając do 8 cyfr zer na początku liczb

3) jest mało prawdopodobne, że będziesz mógł od razu zapisać wartości funkcji X dla każdej kombinacji, dlatego wygodnie jest dodać do tabeli dodatkowe kolumny, aby obliczyć wyniki pośrednie (patrz tabela poniżej)

A	W	Z
0	0
0	1	1
0	0	1
1	0	1
1	1	1
0	1	0
1	0	0
1	1	0

4) uzupełnij kolumny tabeli:

A	W	Z					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

wartość wynosi 1 tylko w tych wierszach, gdzie A = B

wartość wynosi 1 w tych wierszach, gdzie B lub C = 1

wartość wynosi 0 tylko w tych wierszach, gdzie A = 1 i B + C = 0

wartość jest odwrotnością poprzedniej kolumny (0 jest zastępowane przez 1, a 1 jest zastępowane przez 0)

wynik X (ostatnia kolumna) jest sumą logiczną obu kolumn i

5) aby uzyskać odpowiedź, przepisz bity z kolumny X od góry do dołu:

6) przekonwertuj tę liczbę na system dziesiętny:

Odpowiedź: 171

Jaka jest największa liczba całkowita X, dla której stwierdzenie (10 (X+1)·(X+2)) jest prawdziwe?

Wyjaśnienie.

Równanie jest operacją implikacji pomiędzy dwiema relacjami:

1) Oczywiście tutaj możesz zastosować tę samą metodę, co w przykładzie 2208, ale będziesz musiał rozwiązać równania kwadratowe(Nie chcę…);

2) Zauważ, że pod warunkiem interesują nas tylko liczby całkowite, więc możemy spróbować w jakiś sposób przekształcić oryginalne wyrażenie, uzyskując równoważne stwierdzenie (w ogóle nie interesują nas dokładne wartości pierwiastków!);

3) Rozważmy nierówność: oczywiście może to być liczba dodatnia lub ujemna;

4) Łatwo sprawdzić, że w dziedzinie stwierdzenie jest prawdziwe dla wszystkich liczb całkowitych , a w dziedzinie - dla wszystkich liczb całkowitych (aby się nie pomylić, wygodniej jest zastosować nierówności nieścisłe i , zamiast I );

5) Dlatego w przypadku liczb całkowitych można je zastąpić równoważnym wyrażeniem

6) dziedziną prawdziwości wyrażenia jest suma dwóch nieskończonych przedziałów;

7) Rozważmy teraz drugą nierówność: oczywiste jest, że może to być zarówno liczba dodatnia, jak i ujemna;

8) W regionie stwierdzenie jest prawdziwe dla wszystkich liczb całkowitych, a w regionie - dla wszystkich liczb całkowitych, dlatego w przypadku liczb całkowitych można je zastąpić równoważnym wyrażeniem

9) dziedziną prawdziwości wyrażenia jest przedział zamknięty;

10) Podane wyrażenie jest prawdziwe wszędzie, z wyjątkiem obszarów, gdzie i ;

11) Należy pamiętać, że wartość nie jest już odpowiednia, ponieważ tam i , czyli implikacja daje 0;

12) Podstawiając 2, (10 (2+1) · (2+2)), czyli 0 → 0, co spełnia warunek.

Zatem odpowiedź brzmi 2.

Odpowiedź: 2

Jaka jest największa liczba całkowita X, dla której stwierdzenie jest prawdziwe

(50 (X+1)·(X+1))?

Wyjaśnienie.

Zastosujmy transformację implikacji i przekształćmy wyrażenie:

(50 (X+1)·(X+1)) ⇔ ¬(X 2 > 50) ∨ ((X+1) 2) ∨ (|X+1|).

Logiczne LUB jest prawdziwe, gdy przynajmniej jedno logiczne stwierdzenie jest prawdziwe. Po rozwiązaniu obu nierówności i uwzględnieniu tego widzimy, że największą liczbą całkowitą, dla której przynajmniej jedna z nich jest spełniona, jest 7 (na rysunku dodatnie rozwiązanie drugiej nierówności pokazano na żółto, a pierwszej na niebiesko).

Odpowiedź: 7

Wskaż wartości zmiennych K, L, M, N, przy których występuje wyrażenie logiczne

(¬(M ∨ L) ∧ K) → (¬K ∧ ¬M ∨ N)

FAŁSZ. Zapisz odpowiedź jako ciąg 4 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.

Wyjaśnienie.

Duplikuje zadanie 3584.

Odpowiedź: 1000

(¬K ∨ M) → (¬L ∨ M ∨ N)

Wyjaśnienie.

Zastosujmy transformację implikacji:

(K ∧ ¬M) ∨ (¬L ∨ M ∨ N) = 0

Zastosujmy negację do obu stron równania:

(¬K ∨ M) ∧ L ∧ ¬M ∧ ¬N = 1

Przekształćmy:

(¬K ∧ L ∨ M ∧ L) ∧ ¬M ∧ ¬N = 1

Zatem M = 0, N = 0, rozważmy teraz (¬K ∧ L ∨ M ∧ L):

z faktu, że M = 0, N = 0 wynika, że M ∧ L = 0, wówczas ¬K ∧ L = 1, czyli K = 0, L = 1.

Odpowiedź: 0100

Podaj wartości zmiennych K, L, M, N, przy których występuje wyrażenie logiczne

(¬(M ∨ L) ∧ K) → ((¬K ∧ ¬M) ∨ N)

FAŁSZ. 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.

Wyjaśnienie.

Zapiszmy równanie stosując prostszy zapis operacji (warunek „wyrażenie jest fałszywe” oznacza, że jest ono równe zero logicznemu):

1) z sformułowania warunku wynika, że wyrażenie musi być fałszywe tylko dla jednego zbioru zmiennych

2) z tablicy prawdy operacji „implikacja” wynika, że wyrażenie to jest fałszywe wtedy i tylko wtedy, gdy jednocześnie

3) pierwsza równość (iloczyn logiczny równy 1) jest spełniona wtedy i tylko wtedy i ; z tego wynika (suma logiczna jest równa zeru), co może nastąpić tylko wtedy, gdy ; Zatem zdefiniowaliśmy już trzy zmienne

4) z drugiego warunku, , dla i otrzymujemy .

Duplikuje zadanie

Odpowiedź: 1000

Podaj wartości zmiennych logicznych P, Q, S, T, przy których występuje wyrażenie logiczne

(P ∨ ¬Q) ∨ (Q → (S ∨ T)) jest fałszywe.

Zapisz odpowiedź jako ciąg czterech znaków: wartości zmiennych P, Q, S, T (w tej kolejności).

Wyjaśnienie.

(1) (P ∨ ¬Q) = 0

(2) (Q → (S ∨ Т)) = 0

(1) (P ∨ ¬Q) = 0 => P = 0, Q = 1.

(2) (Q → (S ∨ Т)) = 0 Zastosujmy transformację implikacji:

¬Q ∨ S ∨ T = 0 => S = 0, T = 0.

Odpowiedź: 0100

Podaj wartości zmiennych K, L, M, N, przy których występuje wyrażenie logiczne

(K → M) ∨ (L ∧ K) ∨ ¬N

FAŁSZ. 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.

Wyjaśnienie.

Logiczne OR jest fałszywe wtedy i tylko wtedy, gdy oba stwierdzenia są fałszywe.

(K → M) = 0, (L ∧ K) ∨ ¬N = 0.

Zastosujmy transformację implikacji dla pierwszego wyrażenia:

¬K ∨ M = 0 => K = 1, M = 0.

Rozważmy drugie wyrażenie:

(L ∧ K) ∨ ¬N = 0 (patrz wynik pierwszego wyrażenia) => L ∨ ¬N = 0 => L = 0, N = 1.

Odpowiedź: 1001.

Odpowiedź: 1001

Podaj wartości zmiennych K, L, M, N, przy których występuje wyrażenie logiczne

(K → M) ∧ (K → ¬M) ∧ (¬K → (M ∧ ¬L ∧ N))

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

Wyjaśnienie.

Logiczne „AND” jest prawdziwe wtedy i tylko wtedy, gdy oba stwierdzenia są prawdziwe.

1) (K → M) = 1 Zastosuj transformację implikacji: ¬K ∨ M = 1

2) (K → ¬M) = 1 Zastosuj transformację implikacji: ¬K ∨ ¬M = 1

Wynika z tego, że K = 0.

3) (¬K → (M ∧ ¬L ∧ N)) = 1 Zastosuj transformację implikacji: K ∨ (M ∧ ¬L ∧ N) = 1 z faktu, że K = 0 otrzymujemy:

M ∧ ¬L ∧ N = 1 => M = 1, L = 0, N = 1.

Odpowiedź: 0011

Wiadomo, że dla liczb całkowitych X, Y i Z prawdziwe jest stwierdzenie:

(Z Ile wynosi Z, jeśli X=25 i Y=48?

Wyjaśnienie.

Po podstawieniu liczb otrzymujemy, że Z = 47.

Należy pamiętać, że to złożone stwierdzenie składa się z trzech prostych

1) (Z 2) te proste instrukcje łączy operacja ∧ (AND, koniunkcja), to znaczy muszą być wykonane jednocześnie.

3) od ¬(Z+1 24 i od ¬(Z+1 47.

4) z (Z Z Odpowiedź: 47.

Odpowiedź: 47

A, B i C są liczbami całkowitymi, dla których prawdziwe jest następujące stwierdzenie:

(C Jaka jest wartość C, jeśli A=45 i B=18?

Wyjaśnienie.

Logiczne „AND” jest prawdziwe wtedy i tylko wtedy, gdy oba stwierdzenia są prawdziwe.

Podstawiamy liczby do wyrażenia:

1) (C (C 2) ¬(C+1, C ≥ 44.

3) ¬(C+1, C ≥ 17.

Z 2) i 1) wynika, że C

Odpowiedź: 44

¬(A = B) ∧ ((BA)) ∧ ((A 2C))

Jaka jest wartość A, jeśli C = 8 i B = 18?

Wyjaśnienie.

Logiczne „AND” jest prawdziwe wtedy i tylko wtedy, gdy oba stwierdzenia są prawdziwe.

1) ¬(A = B) = 1, czyli A ≠ 18 = 1.

2) ((BA A)) Zastosuj transformację implikacji: (18 > A) ∨ (16 > A) = 1

3) (A 2C) Zastosuj transformację implikacji: (A > 18) ∨ (A > 16) = 1

Z 2) i 3) wynika, że (18 > A) i (A > 16), gdyż w przeciwnym razie powstaje sprzeczność: A = 17.

Odpowiedź: 17

A, B i C są liczbami całkowitymi, dla których stwierdzenie jest prawdziwe

¬(A = B) ∧ ((A > B) → (C = B)) ∧ ((B > A) → (C = A))

Jaka jest wartość B, jeśli A = 45 i C = 18?

Wyjaśnienie.

Logiczne „AND” jest prawdziwe tylko wtedy, gdy wszystkie stwierdzenia są prawdziwe.

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

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

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

Ponieważ lewa strona równań jest równa 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ń. To znaczy, że taki budujemy stół ogólny prawdę dla wszystkich równań układu i znajdź prostą o wymaganych wartościach.

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. Więc ogółem możliwe rozwiązania tego równania 3+9=15.

Następnym sposobem określenia liczby rozwiązań układu równań logicznych jest drzewo binarne. Rozważmy Ta metoda Na przykład.

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

(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ą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)*

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, umiejętność ta jest rozwijana przez naukę logiki. Logika to nauka badająca 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ść decydowania problemy logiczne. 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:

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

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

Ponieważ lewa strona równań jest równa 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.

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 , zatem 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 szukać rozwiązania korzystając 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.

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

Dowolną funkcję logiczną \zmiennych - \można określić za pomocą tabeli prawdy.

Rozwiążmy kilka równań logicznych:

\[\rightharpoondown X1\vee X2=1 \]

\[\rightharpoondown X2\vee X3=1\]

\[\rightharpoondown X3\vee X4=1 \]

\[\rightharpoondown X9\vee X10=1\]

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

Jak widać z tabeli, nasz 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 rozwiązanie 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.

A	W	Z					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

A	W	Z					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1

A	W	Z					X
0	0	0	1	0	1	0	1
0	1	1	0	1	1	0	0
0	0	1	1	1	1	0	1
1	0	1	0	1	1	0	0
1	1	1	1	1	1	0	1
0	1	0	0	1	1	0	0
1	0	0	0	0	0	1	1
1	1	0	1	1	1	0	1