Rozwiązywanie równań logicznych w matematyce. Sposoby rozwiązywania układów równań logicznych

Niech będzie logiczną funkcją n zmiennych. Równanie logiczne to:

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

Równanie logiczne może mieć od 0 do różnych rozwiązań. Jeśli C jest równe 1, to rozwiązaniami są wszystkie te zbiory zmiennych z tabeli prawdy, na których funkcja F przyjmuje wartość prawda (1). Pozostałe zbiory są rozwiązaniami równania dla C równego zero. Zawsze możemy brać pod uwagę tylko równania postaci:

Rzeczywiście, niech zostanie podane równanie:

W takim przypadku możesz przejść do równoważnego równania:

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

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

Jeżeli liczba zmiennych jest mała, na przykład mniej niż 5, to nie jest trudno skonstruować dla funkcji tablicę prawdy, która pozwala powiedzieć ile rozwiązań ma system i jakie są zbiory, które dają rozwiązania.

W niektórych zadaniach Unified State Examination dotyczących znajdowania rozwiązań układu równań logicznych liczba zmiennych osiąga wartość 10. Wtedy budowanie tabeli prawdy staje się zadaniem prawie nierozwiązywalnym. Rozwiązanie problemu wymaga innego podejścia. Dla dowolnego układu równań nie ma innej ogólnej drogi niż wyliczenie, która pozwalałaby rozwiązać takie problemy.

W problemach proponowanych na egzaminie rozwiązanie zazwyczaj opiera się na uwzględnieniu specyfiki układu równań. Powtarzam, poza wyliczeniem wszystkich wariantów zbioru zmiennych, nie ma ogólnego sposobu rozwiązania problemu. Rozwiązanie musi być zbudowane w oparciu o specyfikę systemu. Często przydatne jest wstępne uproszczenie układu równań przy użyciu znanych praw logiki. Kolejna przydatna technika rozwiązania tego problemu jest następująca. Nie interesują nas wszystkie zbiory, a tylko te, na których funkcja ma wartość 1. Zamiast budować kompletną tablicę prawdy, zbudujemy jej analog - binarne drzewo decyzyjne. Każda gałąź tego drzewa odpowiada jednemu rozwiązaniu i określa zbiór, na którym funkcja ma wartość 1. Liczba gałęzi w drzewie decyzyjnym pokrywa się z liczbą rozwiązań układu równań.

Czym jest binarne drzewo decyzyjne i jak jest zbudowane, wyjaśnię na przykładach kilku zadań.

Problem 18

Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, które spełniają układ dwóch równań?

Odpowiedź: System ma 36 różnych rozwiązań.

Rozwiązanie: Układ równań zawiera dwa równania. Znajdźmy liczbę rozwiązań dla pierwszego równania w zależności od 5 zmiennych - . Pierwsze równanie można z kolei traktować jako układ 5 równań. Jak pokazano, układ równań w rzeczywistości reprezentuje koniunkcję funkcji logicznych. Prawdziwe jest również stwierdzenie odwrotne - koniunkcję warunków można uznać za układ równań.

Zbudujmy drzewo decyzyjne dla implikacji () - pierwszy wyraz koniunkcji, który można uznać za pierwsze równanie. Oto jak wygląda graficzny obraz tego drzewa

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

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

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

ma 6 rozwiązań. Oto jak wygląda pełne drzewo decyzyjne dla tego równania:

Drugie równanie naszego układu jest podobne do pierwszego:

Jedyna różnica polega na tym, że równanie wykorzystuje zmienne Y. To równanie ma również 6 rozwiązań. Ponieważ każde rozwiązanie zmienne może być połączone z każdym rozwiązaniem zmiennym, łączna liczba rozwiązań wynosi 36.

Zauważ, że skonstruowane drzewo decyzyjne podaje nie tylko liczbę rozwiązań (według liczby gałęzi), ale także same rozwiązania, wypisane na każdej gałęzi drzewa.

Problem 19

Ile jest różnych zestawów wartości zmiennych logicznych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, które spełniają wszystkie poniższe warunki?

To zadanie jest modyfikacją poprzedniego zadania. Różnica polega na tym, że dodaje się kolejne równanie, które wiąże zmienne X i Y.

Z równania wynika, że jeśli ma wartość 1 (istnieje jedno takie rozwiązanie), to ma wartość 1. Zatem jest jeden zbiór, na którym i mają wartości 1. Gdy jest równy 0, może mieć dowolna wartość, zarówno 0, jak i 1. Zatem każdemu zbiorowi równemu 0, a jest 5 takich zbiorów, odpowiada wszystkie 6 zbiorów ze zmiennymi Y. Zatem łączna liczba rozwiązań wynosi 31.

Problem 20

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

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

To równanie ma dwa rozwiązania, gdy wszystkie mają wartość 1 lub 0.

Problem 21

Ile rozwiązań ma równanie:

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

Zbudujmy drzewo decyzyjne dla tego równania:

Problem 22

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

Stosowanie równań jest szeroko rozpowszechnione w naszym życiu. Wykorzystywane są w wielu obliczeniach, budowie konstrukcji, a nawet sporcie. Równania były używane przez człowieka od czasów starożytnych i od tego czasu ich użycie tylko wzrosło. W matematyce są pewne zadania poświęcone logice zdań. Aby rozwiązać tego rodzaju równanie, musisz mieć pewną wiedzę: znajomość praw logiki zdań, znajomość tablic prawdy funkcji logicznych 1 lub 2 zmiennych, metody przekształcania wyrażeń logicznych. Ponadto musisz znać następujące właściwości operacji logicznych: spójniki, alternatywy, inwersje, implikacje i równoważności.

Dowolna funkcja logiczna z \ zmiennych - \ może być określona przez tablicę 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\]

Zacznijmy rozwiązanie od \[X1\] i określmy, jakie wartości może przyjąć ta zmienna: 0 i 1. Następnie rozważmy każdą z powyższych wartości i zobaczmy, jakie \[X2.\] może być w tym przypadku

Jak widać z tabeli, nasze równanie logiczne ma 11 rozwiązań.

Gdzie mogę rozwiązać równanie logiczne online?

Możesz rozwiązać równanie na naszej stronie https: // site. Darmowy solver online pozwoli Ci rozwiązać równanie online o dowolnej złożoności w kilka sekund. Wszystko, co musisz zrobić, to po prostu wprowadzić swoje dane do solvera. Możesz również obejrzeć instrukcję wideo i dowiedzieć się, jak rozwiązać równanie na naszej stronie internetowej. A jeśli masz jakieś pytania, możesz je zadać w naszej grupie Vkontakte http://vk.com/pocketteacher. Dołącz do naszego grona, zawsze chętnie Ci pomożemy.

Niniejszy materiał zawiera prezentację prezentującą metody rozwiązywania równań logicznych i układów równań logicznych w zadaniu B15 (nr 23, 2015) Zunifikowanego Egzaminu Państwowego z Informatyki. Wiadomo, że to zadanie jest jednym z najtrudniejszych spośród zadań egzaminu. Prezentacja może być przydatna podczas prowadzenia lekcji na temat „Logika” na zajęciach specjalistycznych, a także w przygotowaniu do zdania egzaminu.

Pobierać:

Zapowiedź:

Aby skorzystać z podglądu prezentacji, załóż konto (konto) Google i zaloguj się: https://accounts.google.com

Podpisy slajdów:

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

Zadanie B15 jest jednym z najtrudniejszych na egzaminie z informatyki !!! Sprawdzane są umiejętności: przekształcania wyrażeń zawierających zmienne logiczne; opisać w języku naturalnym zbiór wartości zmiennych logicznych, dla których dany zbiór zmiennych logicznych jest prawdziwy; policz liczbę zestawów binarnych, które spełniają podane warunki. Najtrudniejsze, bo nie ma żadnych formalnych zasad, jak to zrobić, wymagane jest zgadywanie.

Bez czego nie robić!

Koniunkcja konwencji: A /\ B , A  B , AB , А &B, A i B alternatywa: A \ / B , A + B , A | B , A lub B negacja:  A , A, nie równoważnik A: A  B, A  B, A  B XOR: A  B , A xor B

Metoda podstawienia zmiennych Ile jest różnych zestawó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, pod którymi dany system równości jest spełniony. W odpowiedzi należy podać ilość takich zestawów (wersja demo 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ż jedno z równań: (t1 \/ t2) /\ (¬t1 \/ ¬ t2) =1 Oczywiście =1 tylko wtedy, gdy jedna ze zmiennych wynosi 0, a druga 1 Używamy wzoru do wyrażenia operacji XOR w postaci koniunkcji i alternatywy: (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 .to. tk = x2k-1 ≡ x2k (t1 = x1  x2 ,….), to każda wartość tk odpowiada dwóm parom wartości x2k-1 i x2k , np.: tk =0 odpowiada dwóm parom - (0, 1) i (1, 0) , a tk =1 to pary (0,0) i (1,1).

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

Metoda eliminacji rozwiązania częściowego Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, …, x5, y1,y2,…, y5, które spełniają wszystkie następujące warunki: (x1→ x2)∧(x2→x3)∧ (x3→x4)∧(x4→x5) =1; (y1→y2)∧(y2→y3)∧(y3→y4)∧(y4→y5) =1; y5 → x5 =1. Odpowiedź nie musi wymieniać wszystkich różnych zbiorów x1, x2, ..., x5, y 1, y2, ..., y5, pod którymi ten system równości jest spełniony. Jako odpowiedź musisz podać liczbę takich zestawów.

Decyzja. Krok 1. Sekwencyjne rozwiązywanie 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 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 tabeli:

Krok 1. Sekwencyjne rozwiązanie równań Т.о. Otrzymano 6 zestawów rozwiązań dla х1,х2,х3,х4,х5: (00000), (00001), (00011), (00111), (01111), (11111). Argumentują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 ma w nich zmiennych wspólnych, to rozwiązaniem tego układu równań (bez uwzględnienia trzeciego równania) będzie 6 * 6 = 36 par „xes” i „tak”. Rozważ trzecie równanie: y5 → x5 =1 Pary są rozwiązaniem: 0 0 0 1 1 1 Para nie jest rozwiązaniem: 1 0

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

Dynamiczna metoda programowania 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 obowiązuje ta równość. W odpowiedzi musisz podać liczbę takich zestawów.

Rozwiązanie Krok1. Analiza warunku Po lewej stronie równania operacje implikacji są zapisywane sekwencyjnie, priorytet jest taki sam. Przepisz: ((((X 1 → X 2) → X 3) → X 4) → X 5) → X 6 = 1 Uwaga! Każda następna zmienna nie zależy od poprzedniej, ale od wyniku poprzedniej implikacji!

Krok 2. Ujawnienie wzoru Rozważmy pierwszą implikację, X 1 → X 2. Tablica prawdy: X 1 X 2 X 1 → X 2 0 0 1 0 1 1 1 0 0 1 1 1 Z jednego 0 mamy 2, a z 1 mamy dostałem jedno 0 i jedno 1. Tylko jedno 0 i trzy 1, to jest wynik pierwszej operacji.

Krok 2. Odsłaniając wzorzec Łą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 zer - dwie jedynki, z każdego 1 (są 3) po jednym 0 i 1 (3 + 3)

Krok 3. Wyprowadzenie wzoru możesz tworzyć wzory do obliczania liczby zer N i i liczby jedynek E i dla równania z i zmiennymi: ,

Krok 4. Wypełnianie tabeli Wypełnijmy tabelę dla i = 6 od lewej do prawej, obliczając liczbę zer i jedynek korzystając z powyższych wzorów; tabela pokazuje jak zbudowana jest następna kolumna według 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 obowiązuje ta równość. W odpowiedzi musisz podać liczbę takich zestawów.

Rozwiązanie Zauważ, że J → K = ¬ J  K Wprowadzamy zmianę zmiennych: J → K=A, M  N  L =B Przepisujemy 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ż ostatnią implikację M → J =1 Jest to możliwe, jeśli: M= J=0 M=0, J=1 M=J=1

Rozwiązanie A  B , wtedy M=J=0 otrzymujemy 1 + K=0. Nie ma rozwiązań. Przy M=0, J=1 otrzymujemy 0 + K=0, K=0 oraz N i L - dowolne, 4 rozwiązania: ¬ J  K = M  N  L K N L 0 0 0 0 0 1 0 1 0 0 1 jeden

Rozwiązanie 10. Przy 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. Bogomolova, D.Yu. Usenkow. В15: nowe zadania i nowe rozwiązanie // Informatyka, nr 6, 2012, s. 35 – 39. K.Yu. Poliakow. Równania logiczne // Informatyka, nr 14, 2011, s. 30-35. http://ege-go.ru/zadania/grb/b15/, [Zasoby elektroniczne]. http://kpolyakov.narod.ru/school/ege.htm, [Zasoby elektroniczne].

Jak rozwiązać niektóre problemy w sekcjach A i B egzaminu z informatyki?

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

Duża część zadań USE poświęcona jest logice propozycji. Do rozwiązania większości z nich wystarczy znajomość podstawowych praw logiki zdań, znajomość tablic prawdy funkcji logicznych jednej i dwóch zmiennych. Podam podstawowe prawa logiki zdań.

Przemienność alternatywy i koniunkcji:
a ˅ b ≡ b ˅ a
a^b ≡ b^a
Prawo rozdzielcze dotyczące alternatywy i koniunkcji:
a ˅ (b^c) ≡ (a ˅ b) ^(a ˅ c)
a ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Negatywna negacja:
¬(¬a) ≡ a
Spójność:
a ^ ¬a ≡ fałsz
Wyłączna trzecia:
a ˅ ¬a ≡ prawda
Prawa de Morgana:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b
Uproszczenie:
a ˄ a ≡ a
a ˅ a ≡ a
a ˄ prawda ≡ a
a ˄ fałsz ≡ fałsz
Wchłanianie:
a ˄ (a ˅ b) ≡ a
a ˅ (a ˄ b) ≡ a
Zastępowanie implikacji
a → b ≡ ¬a ˅ b
Zmiana tożsamości
a ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Reprezentacja funkcji logicznych

Dowolna funkcja logiczna n zmiennych - F(x 1 , x 2 , ... x n) może być zdefiniowana przez tablicę prawdy. Taka tabela zawiera 2 n zbiorów zmiennych, dla każdego z których określona jest wartość funkcji na tym zbiorze. Ta metoda jest dobra, gdy liczba zmiennych jest stosunkowo niewielka. Nawet dla n > 5 reprezentacja staje się słabo widoczna.

Innym sposobem jest zdefiniowanie funkcji za pomocą jakiejś formuły, używając dobrze znanych, dość prostych funkcji. Układ funkcji (f 1 , f 2 , … f k ) nazywamy kompletnym, jeśli jakakolwiek funkcja logiczna może być wyrażona przez formułę zawierającą tylko funkcje fi .

System funkcji (¬, ˄, ˅) jest kompletny. Prawa 9 i 10 są przykładami tego, jak implikacja i tożsamość są wyrażane poprzez negację, koniunkcję i alternatywę.

W rzeczywistości system dwóch funkcji jest również kompletny - negacja i koniunkcja lub negacja i alternatywa. Reprezentacje wynikają z praw De Morgana, które pozwalają na wyrażenie koniunkcji przez negację i alternatywę, a zatem wyrażanie alternatywy przez negację i koniunkcję:

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

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

Podstawowe funkcje języków programowania to zazwyczaj tożsamość, negacja, koniunkcja i alternatywa. W zadaniach egzaminu, wraz z tymi funkcjami, często pojawia się implikacja.

Przyjrzyjmy się kilku prostym zadaniom związanym z funkcjami logicznymi.

Zadanie 15:

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

x1	x2	x3	x4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

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

Cecha numer 3.

Aby rozwiązać problem, musisz znać tabele prawdy podstawowych funkcji i mieć na uwadze priorytety operacji. Przypomnę, że koniunkcja (mnożenie logiczne) ma wyższy priorytet i jest wykonywana przed alternatywą (dodawanie logiczne). Przy obliczaniu łatwo zauważyć, że funkcje o numerach 1 i 2 na trzecim zbiorze mają wartość 1 iz tego powodu nie odpowiadają fragmentowi.

Zadanie 16:

Która z poniższych liczb spełnia warunek:

(cyfry, zaczynając od najbardziej znaczącej cyfry, idź w kolejności malejącej) → (liczba - parzyste) ˄ (najniższa cyfra - parzyste) ˄ (najwyższa cyfra - nieparzyste)

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

13579
97531
24678
15386

Warunek spełnia cyfra 4.

Pierwsze dwie liczby nie spełniają warunku, ponieważ najniższa cyfra jest nieparzysta. Koniunkcja warunków jest fałszywa, jeśli jeden z warunków koniunkcji jest fałszywy. W przypadku trzeciej liczby warunek najwyższej cyfry nie jest spełniony. W przypadku czwartego numeru spełnione są warunki nałożone na małą i dużą cyfrę numeru. Pierwszy wyraz spójnika również jest prawdziwy, ponieważ implikacja jest prawdziwa, jeśli jego przesłanka jest fałszywa, co ma miejsce w tym przypadku.

Problem 17: Dwóch świadków zeznało, co następuje:

Pierwszy Świadek: Jeśli A jest winny, to B jest z pewnością winny, a C jest niewinny.

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

Jakie wnioski na temat winy A, B i C można wyciągnąć z dowodów?

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

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

Pierwszą rzeczą do zrobienia jest sformalizowanie oświadczeń. Wprowadźmy trzy zmienne logiczne, A, B i C, z których każda jest prawdziwa (1), jeśli odpowiedni podejrzany jest winny. Wtedy zeznanie pierwszego świadka podaje formuła:

A → (B ˄ ¬C)

Zeznanie drugiego świadka podaje formuła:

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

Zakłada się, że zeznania obu świadków są prawdziwe i stanowią połączenie odpowiednich formuł.

Zbudujmy tabelę prawdy dla tych odczytów:

A	B	C	F1	F2	F1 F2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Podsumowanie dowodów jest prawdziwe tylko w jednym przypadku, co prowadzi do jednoznacznej odpowiedzi – A i B są winni, a C jest niewinny.

Z analizy tej tabeli wynika również, że bardziej pouczające są zeznania drugiego świadka. Z prawdziwości jego zeznań wynikają tylko dwie możliwe opcje – A i B są winni, a C jest niewinny, albo A i C są winni, a B jest niewinny. Zeznania pierwszego świadka są mniej pouczające - istnieje 5 różnych opcji, które odpowiadają jego zeznaniom. Wspólnie zeznania obu świadków dają jednoznaczną odpowiedź na temat winy podejrzanych.

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

Niech F(x 1 , x 2 , …x n) będzie funkcją logiczną n zmiennych. Równanie logiczne to:

F(x 1, x 2, ... x n) \u003d C,

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

Równanie logiczne może mieć od 0 do 2n różnych rozwiązań. Jeśli C jest równe 1, to rozwiązaniami są wszystkie te zbiory zmiennych z tabeli prawdy, na których funkcja F przyjmuje wartość prawda (1). Pozostałe zbiory są rozwiązaniami równania dla C równego zero. Zawsze możemy brać pod uwagę tylko równania postaci:

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

Rzeczywiście, niech zostanie podane równanie:

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

W takim przypadku możesz przejść do równoważnego równania:

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

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

F 1 (x 1, x 2, ... x n) \u003d 1

F 2 (x 1, x 2, ... x n) \u003d 1

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

Ф = F 1 ˄ F 2 ˄ … F k

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

W problemach proponowanych na egzaminie rozwiązanie zazwyczaj opiera się na uwzględnieniu specyfiki układu równań. Powtarzam, poza wyliczeniem wszystkich wariantów zbioru zmiennych, nie ma ogólnego sposobu rozwiązania problemu. Rozwiązanie musi być zbudowane w oparciu o specyfikę systemu. Często przydatne jest wstępne uproszczenie układu równań przy użyciu znanych praw logiki. Kolejna przydatna technika rozwiązania tego problemu jest następująca. Nie interesują nas wszystkie zbiory, a tylko te, na których funkcja Ф ma wartość 1. Zamiast budować kompletną tablicę prawdy, zbudujemy jej analog - binarne drzewo decyzyjne. Każda gałąź tego drzewa odpowiada jednemu rozwiązaniu i określa zbiór, na którym funkcja Ф ma wartość 1. Liczba gałęzi w drzewie decyzyjnym pokrywa się z liczbą rozwiązań układu równań.

Czym jest binarne drzewo decyzyjne i jak jest zbudowane, wyjaśnię na przykładach kilku zadań.

Problem 18

Ile jest różnych zbiorów wartości zmiennych logicznych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, które spełniają układ dwóch równań?

Odpowiedź: System ma 36 różnych rozwiązań.

Rozwiązanie: Układ równań zawiera dwa równania. Znajdźmy liczbę rozwiązań dla pierwszego równania w zależności od 5 zmiennych – x 1 , x 2 , …x 5 . Pierwsze równanie można z kolei traktować jako układ 5 równań. Jak pokazano, układ równań w rzeczywistości reprezentuje koniunkcję funkcji logicznych. Prawdziwe jest również stwierdzenie odwrotne - koniunkcję warunków można uznać za układ równań.

Zbudujmy drzewo decyzyjne dla implikacji (x1 → x2), pierwszy wyraz koniunkcji, który można uznać za pierwsze równanie. Oto jak wygląda graficzna reprezentacja tego drzewa:

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

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

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

(x1→x2) /\ (x2→x3) /\ (x3→x4) /\ (x4→x5) = 1
ma 6 rozwiązań. Oto jak wygląda pełne drzewo decyzyjne dla tego równania:

Drugie równanie naszego układu jest podobne do pierwszego:

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

Jedyna różnica polega na tym, że równanie wykorzystuje zmienne Y. To równanie ma również 6 rozwiązań. Ponieważ każde rozwiązanie zmienne X i można połączyć z każdym rozwiązaniem zmiennym Y j , całkowita liczba rozwiązań wynosi 36.

Zauważ, że skonstruowane drzewo decyzyjne podaje nie tylko liczbę rozwiązań (według liczby gałęzi), ale także same rozwiązania, wypisane na każdej gałęzi drzewa.

Problem 19

Ile jest różnych zestawów wartości zmiennych logicznych x1, x2, x3, x4, x5, y1, y2, y3, y4, y5, które spełniają wszystkie poniższe warunki?

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

To zadanie jest modyfikacją poprzedniego zadania. Różnica polega na tym, że dodaje się kolejne równanie, które wiąże zmienne X i Y.

Z równania X 1 → Y 1 wynika, że jeśli X 1 ma wartość 1 (istnieje jedno takie rozwiązanie), to Y 1 ma wartość 1. Jest więc taki zbiór, w którym X 1 i Y 1 mają wartości 1. Kiedy X 1 równe 0, Y 1 może mieć dowolną wartość, zarówno 0, jak i 1. Dlatego każdy zestaw z X 1 równym 0, a jest 5 takich zestawów, odpowiada wszystkim 6 zestawom ze zmiennymi Y. Dlatego łączna liczba rozwiązań wynosi 31 .

Problem 20

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

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

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

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

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

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

Problem 21

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

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

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

Zbudujmy drzewo decyzyjne dla tego równania:

Problem 22

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

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

((X 3X 4) (X5X 6) ˅(¬(X 3X 4) ˄ ¬(X5X6)) = 0

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

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

Odpowiedź: 64

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

Y1 = (X1 ≡ X2); Y 2 \u003d (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 \u003d (X 7 ≡ X 8); Y 5 \u003d (X 9 ≡ X 10);

Wtedy pierwsze równanie przyjmie postać:

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

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

(T 1 ≡ T 2) = 0

Przechodząc do tradycyjnej postaci, piszemy system po uproszczeniach w postaci:

¬(Y 1 ≡ Y 2) = 1

¬(T 2 ≡ T 3) = 1

¬(T 3 ≡ T 4) = 1

¬(T 4 ≡ T 5) = 1

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

Wracając do oryginalnych zmiennych X, zauważ, że każda wartość zmiennej Y odpowiada 2 wartościom zmiennych X, więc każde rozwiązanie w zmiennych Y generuje 2 5 rozwiązań w zmiennych X. Dwie gałęzie generują 2*2 5 rozwiązań , więc łączna liczba rozwiązań wynosi 64.

Jak widać, każde zadanie rozwiązywania układu równań wymaga własnego podejścia. Powszechną sztuczką jest wykonanie równoważnych przekształceń w celu uproszczenia równań. Powszechną techniką jest budowa drzew decyzyjnych. Zastosowane podejście częściowo przypomina konstrukcję tabeli prawdy z tą cechą, że konstruowane są nie wszystkie zbiory możliwych wartości zmiennych, ale tylko te, na których funkcja przyjmuje wartość 1 (prawda). Często w proponowanych problemach nie ma potrzeby budowania pełnego drzewa decyzyjnego, gdyż już na początkowym etapie można ustalić prawidłowość pojawiania się nowych gałęzi na każdym kolejnym poziomie, jak to miało miejsce np. w zadaniu 18. .

Ogólnie rzecz biorąc, problemy ze znalezieniem rozwiązań układu równań logicznych są dobrymi ćwiczeniami matematycznymi.

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

Napisanie takiego programu jest łatwe. Taki program bez problemu poradzi sobie ze wszystkimi zadaniami oferowanymi na egzaminie.

Co dziwne, ale zadanie znajdowania rozwiązań układów równań logicznych również jest trudne dla komputera, okazuje się, że komputer ma swoje ograniczenia. Komputer bez problemu poradzi sobie z zadaniami, w których liczba zmiennych wynosi 20-30, ale zacznie długo myśleć o większych zadaniach. Chodzi o to, że funkcja 2 n określająca liczbę zbiorów jest wykładnikiem, który szybko rośnie wraz z n. Tak szybko, że zwykły komputer osobisty nie poradzi sobie z zadaniem z 40 zmiennymi w ciągu dnia.

Program C# do rozwiązywania równań logicznych

Napisanie programu do rozwiązywania równań logicznych jest przydatne z wielu powodów, choćby dlatego, że można go wykorzystać do sprawdzenia poprawności własnego rozwiązania problemów testowych USE. Innym powodem jest to, że taki program jest doskonałym przykładem problemu programistycznego, który spełnia wymagania dla problemów kategorii C w USE.

Idea skonstruowania programu jest prosta – opiera się na pełnym wyliczeniu wszystkich możliwych zbiorów wartości zmiennych. Ponieważ liczba zmiennych n dla danego równania logicznego lub układu równań jest znana, znana jest również liczba zbiorów - 2 n , które należy uporządkować. Korzystając z podstawowych funkcji języka C# - negacji, alternatywy, koniunkcji i tożsamości, łatwo jest napisać program, który dla danego zbioru zmiennych oblicza wartość funkcji logicznej odpowiadającej logicznemu równaniu lub układowi równań.

W takim programie trzeba zbudować cykl według liczby zestawów, w treści cyklu, według numeru zestawu, sformować sam zestaw, obliczyć wartość funkcji na tym zestawie i jeśli ta wartość jest równy 1, to zbiór daje rozwiązanie równania.

Jedyna trudność, jaka pojawia się podczas realizacji programu, wiąże się z zadaniem samodzielnego uformowania zbioru wartości zmiennych o zadaną liczbę. Piękno tego zadania polega na tym, że to pozornie trudne zadanie w rzeczywistości sprowadza się do prostego zadania, które już wielokrotnie się pojawiało. Rzeczywiście wystarczy zrozumieć, że zbiór wartości zmiennych odpowiadających liczbie i, składający się z zer i jedynek, reprezentuje binarną reprezentację liczby i. Tak więc złożone zadanie uzyskania zestawu wartości zmiennych przez określoną liczbę sprowadza się do dobrze znanego problemu zamiany liczby na system binarny.

Tak wygląda funkcja C# rozwiązująca nasz problem:

///

/// program do liczenia ilości rozwiązań

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

///

/// funkcja logiczna - metoda,

/// którego podpis jest ustawiany przez delegata DF

///

/// liczba zmiennych

/// liczba rozwiązań

statyczne int SolveEquations(DF fun, int n)

bool set = nowy bool[n];

int m = (int)Moc.matematyczne(2, n); //liczba zestawów

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

//Pełne wyliczenie według liczby zestawów

dla (int i = 0; i< m; i++)

//Tworzenie kolejnego zestawu — zestaw,

//podany przez binarną reprezentację liczby i

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

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

//Oblicz wartość funkcji na zestawie

Do zrozumienia programu mam nadzieję, że wystarczą wyjaśnienia idei programu i komentarze w jego tekście. Zajmę się tylko wyjaśnieniem nagłówka powyższej funkcji. Funkcja SolveEquations ma dwa parametry wejściowe. Parametr fun określa funkcję logiczną odpowiadającą rozwiązywanemu równaniu lub układowi równań. Parametr n określa liczbę zmiennych w funkcji fun. W rezultacie funkcja SolveEquations zwraca liczbę rozwiązań funkcji logicznej, czyli liczbę zestawów, na których funkcja ma wartość true.

Dla dzieci w wieku szkolnym jest zwyczajem, że dla jakiejś funkcji F(x) parametr wejściowy x jest zmienną typu arytmetycznego, łańcuchowego lub logicznego. W naszym przypadku zastosowano mocniejszy projekt. Funkcja SolveEquations odnosi się do funkcji wyższego rzędu - funkcji typu F(f), których parametrami mogą być nie tylko zmienne proste, ale również funkcje.

Klasa funkcji, które można przekazać jako parametr do funkcji SolveEquations, jest zdefiniowana w następujący sposób:

deleguj bool DF(zmienne logiczne);

Ta klasa zawiera wszystkie funkcje, które jako parametr przekazuje zbiór wartości zmiennych binarnych określonych przez tablicę vars. Wynikiem jest wartość logiczna reprezentująca wartość funkcji w tym zestawie.

Na zakończenie podam program, w którym funkcja SolveEquations służy do rozwiązywania kilku układów równań logicznych. Funkcja SolveEquations jest częścią następującej klasy ProgramCommon:

klasa ProgramCommon

deleguj bool DF(zmienne logiczne);

static void Main(args string)

Console.WriteLine("Funkcje i rozwiązania - " +

Rozwiąż równania(FunAnd, 2));

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

Rozwiąż równania(Fun51, 5));

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

Rozwiąż równania(Fun53, 10));

static bool FunAnd(bool vars)

return vars && vars;

static bool Fun51 (bool vars)

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

static bool Fun53(bool vars)

f = f && ((zm == zm) || (zm == zm));

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

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

10 zadań do samodzielnej pracy

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

x1	x2	x3	x4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Która z trzech funkcji odpowiada temu fragmentowi:

(X 1 ˅ ¬X 2) ˄ (X 3 → X 4)
(X 1 → X 3) ˄ X 2 ˅ X 4
X 1 ˄ X 2 ˅ (X 3 → (X 1 ˅ X 4))
Jury składa się z trzech osób. Decyzja zostaje podjęta, jeśli głosuje przewodniczący jury, poparty przynajmniej jednym z członków jury. W przeciwnym razie żadna decyzja nie zostanie podjęta. Zbuduj funkcję logiczną, która formalizuje proces podejmowania decyzji.
X wygrywa z Y, jeśli cztery rzuty monetą wypadną trzy razy. Zdefiniuj funkcję logiczną opisującą wypłatę X.
Słowa w zdaniu są numerowane od jednego. Zdanie jest uważane za dobrze sformułowane, jeśli spełnione są następujące zasady:
1. Jeśli parzyste słowo kończy się na samogłoskę, to następne słowo, jeśli istnieje, musi zaczynać się od samogłoski.
2. Jeśli nieparzyste słowo kończy się na spółgłoskę, to następne słowo, jeśli istnieje, musi zaczynać się od spółgłoski i kończyć na samogłoskę.
  Które z poniższych zdań są poprawne:
3. Mama umyła Maszę mydłem.
4. Lider jest zawsze wzorem.
5. Prawda jest dobra, ale szczęście jest lepsze.
Ile rozwiązań ma równanie:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
Wypisz wszystkie rozwiązania równania:
(a → b) → c = 0
Ile rozwiązań ma następujący układ równań:
X 0 → X 1 ˄ X 1 → X 2 = 1
X 2 → X 3 ˄ X 3 → X 4 = 1
X5 → X6 ˄ X6 → X7 = 1
X 7 → X 8 ˄ X 8 → X 9 = 1
X 0 → X 5 = 1
Ile rozwiązań ma równanie:
((((X 0 → X 1) → X 2) → X 3) → X 4) → X 5 = 1

Odpowiedzi na zadania:

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

Temat lekcji: Rozwiązywanie równań logicznych

Edukacyjny - badanie sposobów rozwiązywania równań logicznych, kształtowanie umiejętności i zdolności rozwiązywania równań logicznych i budowania wyrażenia logicznego zgodnie z tabelą prawdy;

Edukacyjny - tworzyć warunki do rozwoju zainteresowań poznawczych uczniów, promować rozwój pamięci, uwagi, logicznego myślenia;

Edukacyjny : przyczyniają się do edukacji umiejętności słuchania opinii innych, wykształcenie woli i wytrwałości w osiąganiu ostatecznych rezultatów.

Rodzaj lekcji: lekcja łączona

Ekwipunek: komputer, projektor multimedialny, prezentacja 6.

Podczas zajęć

Powtórzenie i aktualizacja podstawowej wiedzy. Sprawdzanie pracy domowej (10 minut)

Na poprzednich lekcjach zapoznaliśmy się z podstawowymi prawami algebry logiki, nauczyliśmy się używać tych praw do uproszczenia wyrażeń logicznych.

Sprawdźmy pracę domową z uproszczenia wyrażeń logicznych:

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

(pierwsza spółgłoska → druga spółgłoska)٨ (ostatnia litera samogłoska → przedostatnia litera samogłoska)? Jeśli takich słów jest kilka, wskaż najmniejsze z nich.

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

Wprowadźmy notację:

A to pierwsza litera spółgłoski

B to druga litera spółgłoski

S to ostatnia samogłoska

D - przedostatnia samogłoska

Zróbmy wyrażenie:

Zróbmy stół:

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

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

3. Podano fragment tabeli prawdy wyrażenia F:

Jakie wyrażenie odpowiada F?

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

Zapoznanie się z tematem lekcji, prezentacja nowego materiału (30 minut)

Kontynuujemy naukę podstaw logiki i tematu naszej dzisiejszej lekcji „Rozwiązywanie równań logicznych”. Po przestudiowaniu tego tematu poznasz podstawowe sposoby rozwiązywania równań logicznych, zdobędziesz umiejętności rozwiązywania tych równań przy użyciu języka algebry logicznej oraz umiejętność układania wyrażenia logicznego na tablicy prawdy.

1. Rozwiąż równanie logiczne

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

Napisz odpowiedź jako ciąg czterech znaków: wartości zmiennych K, L, M i N (w tej kolejności). Na przykład linia 1101 odpowiada K=1, L=1, M=0, N=1.

Decyzja:

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

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

Odpowiedź: 0100

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

Rozwiązanie: przekształć wyrażenie

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

A+B=1 i C+D=1

Metoda 2: kompilacja tabeli prawdy

3 sposób: konstrukcja SDNF - doskonała dysjunktywna forma normalna dla funkcji - alternatywa pełnych regularnych spójników elementarnych.

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

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

Uzupełnijmy spójniki do spójników pełnych (iloczyn wszystkich argumentów), otwórzmy nawiasy:

Rozważ te same spójniki:

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

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

Uprośćmy wyrażenie:

3 sposób: budowa SDNF

Rozważ te same spójniki:

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

Budowanie wyrażenia logicznego zgodnie z tabelą prawdy:

dla każdego wiersza tabeli prawdy zawierającego 1 składamy iloczyn argumentów, a zmienne równe 0 są uwzględniane w iloczynie z negacją, a zmienne równe 1 nie są negowane. Pożądane wyrażenie F będzie składało się z sumy otrzymanych produktów. Następnie, jeśli to możliwe, to wyrażenie należy uprościć.

Przykład: podano tabelę prawdy wyrażenia. Zbuduj wyrażenie logiczne.

Decyzja:

3. Praca domowa (5 minut)

Rozwiązać równanie:

Ile rozwiązań ma równanie (odpowiedz tylko liczbę)?

Zgodnie z podaną tabelą prawdy, zrób wyrażenie logiczne i

uprościć to.