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 najtrudniejszym zadaniem KIM Unified State Examination 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ść nauczycielska 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 Na egzaminie 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ę zadań z dwoma typami metoda zmienna Uczniowie z powodzeniem korzystali z mapowań, jednak po pojawieniu się Y w wyrażeniu logicznym zaczęłam zauważać, że odpowiedzi dzieci nie odpowiadały już testom. 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óżnych rozwiązań ma ten system? równania logiczne
(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
)
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 metoda rozwiązania problemu 23 z egzaminu Unified State Exam KIM pozwoliła uczniom odzyskać pewność siebie i skutecznie rozwiązać tego typu problem.
Literatura:
1. FIPI. Zalecenia metodyczne dla nauczycieli, przygotowane na podstawie analizy typowe błędy uczestnicy Unified State Exam 2015 z zakresu INFORMATION SCIENCE 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. Magazyn Informatyka, nr 10, 2013, s. 10-10. 18-26. Wydawnictwo „Pierwszy września”, Moskwa.
Rozwiązywanie układów równań logicznych poprzez zmianę zmiennych
Metodę podstawienia zmiennych stosuje się, jeśli niektóre zmienne są uwzględniane w równaniach tylko w postaci określonego wyrażenia i nic więcej. Następnie wyrażenie to można wyznaczyć jako nową zmienną.
Przykład 1.
Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, x5, x6, x7, x8, które spełniają wszystkie poniższe warunki?
(x1 → x2) → (x3 → x4) = 1
(x3 → x4) → (x5 → x6) = 1
(x5 → x6) → (x7 → x8) = 1
Odpowiedź nie wymaga wymieniania wszystkich różnych zbiorów wartości zmiennych x1, x2, x3, x4, x5, x6, x7, x8, dla których spełniony jest ten układ równości. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
(x1 → x2) = y1; (x3 → x4) = y2; (x5 → x6) = y3; (x7 → x8) = y4.
Następnie możemy zapisać układ w postaci pojedynczego równania:
(y1 → y2) ∧ (y2 → y3) ∧ (y3 → y4) = 1. Koniunkcja wynosi 1 (prawda), gdy każdy operand przyjmuje wartość 1. Oznacza to, że każda z implikacji musi być prawdziwa i dotyczy to wszystkich wartości z wyjątkiem (1 → 0). Te. w tabeli wartości zmiennych y1, y2, y3, y4 nie należy znajdować się na lewo od zera:
Te. warunki są spełnione dla 5 serii y1-y4.
Ponieważ y1 = x1 → x2, wówczas wartość y1 = 0 osiągana jest na pojedynczym zestawie x1, x2: (1, 0), a wartość y1 = 1 – na trzech zbiorach x1, x2: (0,0) , (0 ,1), (1.1). Podobnie dla y2, y3, y4.
Ponieważ każdy zbiór (x1,x2) dla zmiennej y1 jest łączony z każdym zbiorem (x3,x4) dla zmiennej y2 itd., to liczby zbiorów zmiennych x są mnożone:
|
Liczba zestawów na x1…x8 |
||||
Dodajmy liczbę zestawów: 1 + 3 + 9 + 27 + 81 = 121.
Odpowiedź: 121
Przykład 2.
Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, ... x9, y1, y2, ... y9, które spełniają wszystkie wymienione poniżej warunki?
(¬ (x1 ≡ y1)) ≡ (x2 ≡ y2)
(¬ (x2 ≡ y2)) ≡ (x3 ≡ y3)
(¬ (x8 ≡ y8)) ≡ (x9 ≡ y9)
W odpowiedzi nie ma potrzeby wymień wszystkie różne zestawy wartości zmiennych x1, x2, ... x9, y1, y2, ... y9, dla których tego systemu równa się W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
Dokonajmy zmiany zmiennych:
(x1 ≡ y1) = z1, (x2 ≡ y2) = z2,…. ,(x9 ≡ y9) = z9
Układ można zapisać w postaci pojedynczego równania:
(¬ z1 ≡ z2) ∧ (¬ z2 ≡ z3) ∧ …..∧ (¬ z8 ≡ z9)
Równoważność jest prawdziwa tylko wtedy, gdy oba operandy są równe. Istnieją dwa zestawy rozwiązań tego równania:
| z1 | z2 | z3 | z4 | z5 | z6 | z7 | z8 | z9 |
| 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
Ponieważ zi = (xi ≡ yi), wówczas wartość zi = 0 odpowiada dwóm zbiorom (xi,yi): (0,1) i (1,0), a wartość zi = 1 odpowiada dwóm zbiorom (xi,yi ): (0,0) i (1,1).
Wtedy pierwszy zbiór z1, z2,…, z9 odpowiada 2 9 zbiorom (x1,y1), (x2,y2),…, (x9,y9).
Ta sama liczba odpowiada drugiemu zestawowi z1, z2,…, z9. Zatem jest w sumie 2 9 +2 9 = 1024 zestawy.
Odpowiedź: 1024
Rozwiązywanie układów równań logicznych metodą wizualnego wyznaczania rekurencji.
Metodę tę stosuje się, jeśli układ równań jest dość prosty i kolejność zwiększania liczby zbiorów przy dodawaniu zmiennych jest oczywista.
Przykład 3.
Ile różnych rozwiązań ma układ równań?
¬x9 ∨ x10 = 1,
gdzie x1, x2, … x10 to zmienne logiczne?
Odpowiedź nie wymaga wymieniania wszystkich różnych zbiorów wartości x1, x2, ... x10, dla których spełniony jest ten układ równości. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
Rozwiążmy pierwsze równanie. Dysjunkcja jest równa 1, jeśli przynajmniej jeden z jej argumentów jest równy 1. To znaczy rozwiązaniami są zbiory:
Dla x1=0 istnieją dwie wartości x2 (0 i 1), a dla x1=1 istnieje tylko jedna wartość x2 (1), tak że zbiór (x1,x2) jest rozwiązaniem równania. W sumie są 3 komplety.
Dodajmy zmienną x3 i rozważmy drugie równanie. Jest ona podobna do pierwszej, co oznacza, że dla x2=0 istnieją dwie wartości x3 (0 i 1), a dla x2=1 tylko jedna wartość x3 (1), tak że zbiór (x2 ,x3) jest rozwiązaniem równania. W sumie są 4 komplety.
Łatwo zauważyć, że dodając kolejną zmienną, dodawany jest jeden zbiór. Te. rekurencyjny wzór na liczbę zbiorów (i+1) zmiennych:
N i +1 = N i + 1. Wtedy dla dziesięciu zmiennych otrzymujemy 11 zbiorów.
Odpowiedź: 11
Rozwiązywanie układów równań logicznych różnych typów
Przykład 4.
Ile jest różnych zbiorów wartości zmiennych logicznych x 1, ..., x 4, y 1,..., y 4, z 1,..., z 4, które spełniają wszystkie poniższe warunki ?
(x 1 → x 2) ∧ (x 2 → x 3) ∧ (x 3 → x 4) = 1
(y 1 → r 2) ∧ (y 2 → r 3) ∧ (y 3 → r 4) = 1
(z 1 → z 2) ∧ (z 2 → z 3) ∧ (z 3 → z 4) = 1
x 4 ∧ y 4 ∧ z 4 = 0
W odpowiedzi nie ma potrzeby wymień wszystkie różne zbiory wartości zmiennych x 1, ..., x 4, y 1, ..., y 4, z 1, ..., z 4, dla których spełniony jest ten układ równości.
W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
Należy zauważyć, że trzy równania układu są takie same dla różnych niezależnych zbiorów zmiennych.
Spójrzmy na pierwsze równanie. Koniunkcja jest prawdziwa (równa 1) tylko wtedy, gdy wszystkie jej operandy są prawdziwe (równe 1). Implikacja wynosi 1 dla wszystkich krotek z wyjątkiem (1,0). Oznacza to, że rozwiązaniem pierwszego równania będą następujące zbiory x1, x2, x3, x4, w których 1 nie leży na lewo od 0 (5 zbiorów):
Podobnie rozwiązania drugiego i trzeciego równania będą absolutnie tymi samymi zbiorami y1,…,y4 i z1,…, z4.
Przeanalizujmy teraz czwarte równanie układu: x 4 ∧ y 4 ∧ z 4 = 0. Rozwiązaniem będą wszystkie zbiory x4, y4, z4, w których przynajmniej jedna ze zmiennych jest równa 0.
Te. dla x4 = 0 odpowiednie są wszystkie możliwe zbiory (y4, z4), a dla x4 = 1 odpowiednie są zbiory (y4, z4), w których jest przynajmniej jedno zero: (0, 0), (0,1 ) , (1, 0).
|
Liczba zestawów |
||||
Całkowita liczba zestawów wynosi 25 + 4*9 = 25 + 36 = 61.
Odpowiedź: 61
Rozwiązywanie układów równań logicznych poprzez konstruowanie wzorów rekurencyjnych
Metodę konstruowania formuł rekurencyjnych stosuje się przy rozwiązywaniu złożonych układów, w których kolejność zwiększania liczby zbiorów nie jest oczywista, a zbudowanie drzewa jest niemożliwe ze względu na objętości.
Przykład 5.
Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2,...x7, y1, y2,...y7, które spełniają wszystkie poniższe warunki?
(x1 ∨ y1) ∧ ((x2 ∧ y2) → (x1 ∧ y1)) = 1
(x2 ∨ y2) ∧ ((x3 ∧ y3) → (x2 ∧ y2)) = 1
(x6 ∨ y6) ∧ ((x7 ∧ y7) → (x6 ∧ y6)) = 1
Odpowiedź nie wymaga wymieniania wszystkich różnych zbiorów wartości zmiennych x1, x2, ..., x7, y1, y2, ..., y7, dla których ten układ równości jest spełniony. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie:
Należy zauważyć, że pierwsze sześć równań układu jest identycznych i różni się jedynie zbiorem zmiennych. Spójrzmy na pierwsze równanie. Jego rozwiązaniem będą następujące zestawy zmiennych:
Oznaczmy:
liczba krotek (0,0) na zmiennych (x1,y1) do A 1,
liczba krotek (0,1) na zmiennych (x1,y1) do B 1,
liczba krotek (1,0) na zmiennych (x1,y1) do C 1,
liczba krotek (1,1) na zmiennych (x1,y1) do D 1 .
liczba krotek (0,0) na zmiennych (x2,y2) do A 2 ,
liczba krotek (0,1) na zmiennych (x2,y2) do B 2,
liczba krotek (1,0) na zmiennych (x2,y2) do C 2,
liczba krotek (1,1) na zmiennych (x2,y2) do D 2 .
Widzimy to z drzewa decyzyjnego
ZA 1 =0, B 1 =1, Do 1 =1, D 1 =1.
Należy zauważyć, że zbiór (0,0) na zmiennych (x2,y2) otrzymuje się ze zbiorów (0,1), (1,0) i (1,1) na zmiennych (x1,y1). Te. ZA 2 = B 1 + C 1 + D 1.
Zbiór (0,1) na zmiennych (x2,y2) otrzymuje się ze zbiorów (0,1), (1,0) i (1,1) na zmiennych (x1,y1). Te. B 2 = B 1 + C 1 + D 1.
Argumentując podobnie, zauważamy, że C 2 = B 1 + C 1 + D 1. D2 = D1.
Otrzymujemy w ten sposób powtarzające się wzory:
A ja+1 = B ja + do ja + re ja
B ja+1 = B ja + do ja + re ja
do ja+1 = b ja + do ja + re ja
re ja+1 = ZA ja + B ja + do ja + re ja
Zróbmy stół
| Zestawy | Oznaczenie. | Formuła |
Liczba zestawów |
||||||
| ja=1 | ja=2 | ja=3 | ja=4 | ja=5 | ja=6 | ja=7 | |||
| (0,0) | A ja | A i+1 =B i +C i +D ja | 0 | 3 | 7 | 15 | 31 | 63 | 127 |
| (0,1) | B ja | B i+1 =B i +C i +D ja | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,0) | C ja | C i+1 =B i +C i +D ja | 1 | 3 | 7 | 15 | 31 | 63 | 127 |
| (1,1) | D ja | D ja+1 =D ja | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
Ostatnie równanie (x7 ∨ y7) = 1 spełniają wszystkie zbiory z wyjątkiem tych, w których x7=0 i y7=0. W naszej tabeli liczba takich zestawów wynosi A 7.
Wtedy całkowita liczba zestawów wynosi B 7 + C 7 + D 7 = 127+127+1 = 255
Odpowiedź: 255
Miejska budżetowa instytucja oświatowa
"Przeciętny szkoła średnia nr 18"
dzielnica miejska miasta Salavat w Republice Baszkortostanu
Układy równań logicznych
w zagadnieniach jednolitego egzaminu państwowego z informatyki
Sekcja „Podstawy algebry logicznej” w Zadania z egzaminu jednolitego stanu uważany za jeden z najtrudniejszych i słabo rozwiązanych. Średni odsetek wykonanych zadań z tego tematu jest najniższy i wynosi 43,2.
| Sekcja kursu | Średni procent wykonania według grup zadaniowych |
| Kodowanie informacji i mierzenie jej ilości | |
| Modelowanie informacji | |
| Systemy liczbowe | |
| Podstawy algebry logicznej | |
| Algorytmizacja i programowanie | |
| Podstawy technologii informacyjnych i komunikacyjnych |
W oparciu o specyfikację CMM 2018 blok ten obejmuje cztery zadania różne poziomy złożoność.
| № zadania | Sprawdzalny elementy treści | Poziom trudności zadania |
| Umiejętność konstruowania tablic prawdy i obwodów logicznych | ||
| Umiejętność wyszukiwania informacji w Internecie | ||
| Znajomość podstawowych pojęć i praw logika matematyczna | ||
| Umiejętność konstruowania i przekształcania wyrażeń logicznych |
Zadanie 23 ma wysoki poziom trudności, dlatego też ma najniższy procent ukończenia. Wśród absolwentów przygotowanych (81-100 punktów) zadanie wykonało 49,8%, przygotowanych średnio (61-80 punktów) wykonało 13,7%, pozostała grupa studentów nie wykonała tego zadania.
Sukces w rozwiązaniu układu równań logicznych zależy od znajomości praw logiki i precyzyjnego zastosowania metod rozwiązywania układu.
Rozważmy rozwiązanie układu równań logicznych metodą mapowania.
(23,154 Polyakov K.Yu.) Ile różnych rozwiązań ma układ równań?
((X1 y1 ) (X2 y2 )) (X1 X2 ) (j1 y2 ) =1
((X2 y2 ) (X3 y3 )) (X2 X3 ) (j2 y3 ) =1
((X7 y7 ) (X8 y8 )) (X7 X8 ) (y7 y8 ) =1
Gdzie X1 , X2 ,…, X8, Na1 , j2 ,…,j8 - zmienne logiczne? Odpowiedź nie musi wymieniać wszystkich różnych zestawów wartości zmiennych, dla których zachodzi ta równość. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie. Wszystkie równania zawarte w układzie są tego samego typu, a każde równanie zawiera cztery zmienne. Znając x1 i y1, możemy znaleźć wszystkie możliwe wartości x2 i y2, które spełniają pierwsze równanie. Rozumując w podobny sposób, ze znanych x2 i y2 możemy znaleźć x3, y3, które spełniają drugie równanie. Oznacza to, że znając parę (x1, y1) i określając wartość pary (x2, y2), znajdziemy parę (x3, y3), co z kolei doprowadzi do pary (x4, y4) i tak dalej.
Znajdźmy wszystkie rozwiązania pierwszego równania. Można tego dokonać na dwa sposoby: konstruując tablicę prawdy, rozumując i stosując prawa logiki.
Tabela prawdy:
| x 1 y 1 | x 2 y 2 | (x1 tak 1) (x2 y2) | (x1 x2) | (y 1 y2) | (x1 x2) (y 1 y2) | |||||
Konstruowanie tabeli prawdy jest pracochłonne i nieefektywne czasowo, dlatego stosujemy drugą metodę - logiczne wnioskowanie. Iloczyn jest równy 1 wtedy i tylko wtedy, gdy każdy czynnik jest równy 1.
(X1 y1 ) (X2 y2 ))=1
(X1 X2 ) =1
(y1 y2 ) =1
Spójrzmy na pierwsze równanie. Konsekwencja jest równa 1, gdy 0 0, 0 1, 1 1, co oznacza (x1 y1)=0 dla (01), (10), to para (X2 y2 ) może mieć dowolną wartość (00), (01), (10), (11), a gdy (x1 y1) = 1, czyli (00) i (11) para (x2 y2) = 1 przyjmuje te same wartości (00) i (11). Wykluczmy z tego rozwiązania te pary, dla których równanie drugie i trzecie jest fałszywe, czyli x1=1, x2=0, y1=1, y2=0.
| (X1 , y1 ) | (X2 , y2 ) |
Całkowita liczba par 1+1+1+22= 25
2) (23.160 Polyakov K.Yu.) Ile różnych rozwiązań ma układ równań logicznych?
(X 1 (X 2 y 2 )) (j 1 y 2 ) = 1
(X 2 (X 3 y 3 )) (j 2 y 3 ) = 1
...
( X 6 ( X 7 y 7 )) ( y 6 y 7 ) = 1
X 7 y 7 = 1
Rozwiązanie. 1) Równania są tego samego typu, więc rozumując znajdziemy wszystkie możliwe pary (x1,y1), (x2,y2) pierwszego równania.
(X1 (X2 y2 ))=1
(y1 y2 ) = 1
Rozwiązaniem drugiego równania są pary (00), (01), (11).
Znajdźmy rozwiązania pierwszego równania. Jeśli x1=0, to x2, y2 - dowolne, jeśli x1=1, to x2, y2 przyjmuje wartość (11).
Utwórzmy połączenia pomiędzy parami (x1, y1) i (x2, y2).
| (X1 , y1 ) | (X2 , y2 ) |
Stwórzmy tabelę, aby obliczyć liczbę par na każdym etapie.
| 0 |
|||||||
Uwzględniając rozwiązania ostatniego równania X 7 y 7 = 1, wykluczmy parę (10). Znajdujemy całkowita liczba rozwiązania 1+7+0+34=42
3)(23.180) Ile różnych rozwiązań ma układ równań logicznych?
(X1 X2 ) (X3 X4 ) = 1
(X3 X4 ) (X5 X6 ) = 1
(X5 X6 ) (X7 X8 ) = 1
(X7 X8 ) (X9 X10 ) = 1
X1 X3 X5 X7 X9 = 1
Rozwiązanie. 1) Równania są tego samego typu, więc rozumując znajdziemy wszystkie możliwe pary (x1,x2), (x3,x4) pierwszego równania.
(X1 X2 ) (X3 X4 ) = 1
Wyłączmy z rozwiązania pary, które w ciągu dają 0 (1 0), są to pary (01, 00, 11) i (10).
Utwórzmy połączenia pomiędzy parami (x1,x2), (x3,x4)
Metody rozwiązywania układów równań logicznych
Można rozwiązać układ równań logicznych, np. korzystając z tabeli prawdy (jeśli liczba zmiennych nie jest zbyt duża) lub korzystając z drzewa decyzyjnego, uprzednio upraszczając każde równanie.
1. Metoda zastępowania zmiennych.
Wprowadzenie nowych zmiennych pozwala uprościć układ równań, zmniejszając liczbę niewiadomych.Nowe zmienne muszą być od siebie niezależne. Po rozwiązaniu układu uproszczonego musimy wrócić do oryginalnych zmiennych.
Rozważmy zastosowanie tej metody na konkretnym przykładzie.
Przykład.
((X1 ≡ X2) ∧ (X3 ≡ X4)) ∨ (¬(X1 ≡ X2) ∧ ¬(X3 ≡ X4)) = 0
((X3 ≡ X4) ∧ (X5 ≡ X6)) ∨ (¬(X3 ≡ X4) ∧ ¬(X5 ≡ X6)) = 0
((X5 ≡ X6) ∧ (X7 ≡ X8)) ∨ (¬(X5 ≡ X6) ∧ ¬(X7 ≡ X8)) = 0
((X7 ≡ X8) ∧ (X9 ≡ X10)) ∨ (¬(X7 ≡ X8) ∧ ¬(X9 ≡ X10)) = 0
Rozwiązanie:
Wprowadźmy nowe zmienne: A=(X1≡ X2); B=(X3 ≡ X4); С=(X5 ≡ X6); D=(X7 ≡ X8); E=(X9 ≡ X10).
(Uwaga! Każda ze zmiennych x1, x2, ..., x10 musi znajdować się tylko w jednej z nowych zmienne A, B, C, D, E, tj. nowe zmienne są od siebie niezależne).
Wtedy układ równań będzie wyglądał następująco:
(A ∧ B) ∨ (¬A ∧ ¬B)=0
(B ∧ C) ∨ (¬B ∧ ¬C)=0
(C ∧ D) ∨ (¬C ∧ ¬D)=0
(D ∧ E) ∨ (¬D ∧ ¬E)=0
Zbudujmy drzewo decyzyjne dla powstałego systemu:
Rozważmy równanie A=0, tj. (X1≡ X2)=0. Ma 2 korzenie:
X1 ≡ X2 |
||
Z tej samej tabeli widać, że równanie A=1 ma również 2 pierwiastki. Uporządkujmy liczbę korzeni w drzewie decyzyjnym:
Aby znaleźć liczbę rozwiązań jednej gałęzi, należy pomnożyć liczbę rozwiązań na każdym poziomie. Lewa gałąź ma 2⋅ 2 ⋅ 2 ⋅ 2 ⋅ 2=32 rozwiązania; prawa gałąź również ma 32 rozwiązania. Te. cały układ ma 32+32=64 rozwiązania.
Odpowiedź: 64.
2. Sposób rozumowania.
Trudność rozwiązywania układów równań logicznych polega na uciążliwości całego drzewa decyzyjnego. Metoda rozumowania pozwala nie budować całego drzewa, ale zrozumieć, ile będzie miało gałęzi. Przyjrzyjmy się tej metodzie na konkretnych przykładach.
Przykład 1. Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, które spełniają wszystkie poniższe warunki?
(x1 → x2) /\ (x2 → x3) /\ (x3 → x4) /\ (x4 → x5) = 1
(y1 → y2) /\ (y2 → y3) /\ (y3 → y4) /\ (y4 → y5) = 1
x1\/y1 =1
Odpowiedź nie musi wymieniać wszystkich różnych zbiorów wartości zmiennych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, dla których ten układ równości jest spełniony. W odpowiedzi należy podać liczbę takich zestawów.
Rozwiązanie :
Pierwsze i drugie równanie zawierają zmienne niezależne, które są powiązane trzecim warunkiem. Zbudujmy drzewo rozwiązań dla pierwszego i drugiego równania.
Aby przedstawić drzewo rozwiązań układu pierwszego i drugiego równania, każda gałąź pierwszego drzewa musi być kontynuowana drzewem zmiennych Na . Zbudowane w ten sposób drzewo będzie miało 36 gałęzi. Niektóre z tych gałęzi nie spełniają trzeciego równania układu. Zaznaczmy liczbę gałęzi drzewa na pierwszym drzewie„y” , które spełniają trzecie równanie:
Wyjaśnijmy: aby spełnić trzeci warunek, gdy x1=0 musi istnieć y1=1, czyli wszystkie gałęzie drzewa"X" , gdzie x1=0 można kontynuować tylko z jedną gałęzią drzewa„y” . I tylko dla jednej gałęzi drzewa"X" (po prawej) wszystkie gałęzie drzewa pasują„y”. Zatem, pełne drzewo Cały system składa się z 11 oddziałów. 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.
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ń.
Pozostaje zauważyć, że 15 znalezionych rozwiązań odpowiada dowolnej z dwóch możliwych wartości zmiennej logicznej N, więc oryginalne 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 prostszy zapis 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 akceptują prawdziwe wartości w trzech przypadkach każdy, 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 „LUB” 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
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.
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 patrzymy na trzeci warunek i 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 | X|
| 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 ( dokładne wartości korzenie w ogóle nas nie interesują!);
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 dziedzinie stwierdzenie jest prawdziwe dla wszystkich liczb całkowitych, a w dziedzinie - dla wszystkich liczb całkowitych, zatem dla liczb całkowitych można je zastąpić wyrażeniem równoważnym
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
Przeliczmy:
(¬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.