Jak rozwiązywać układy równań logicznych ZASTOSOWANIE. Logika. Funkcje logiczne. Rozwiązywanie równań

Jak rozwiązać niektóre zadania z części A i B egzaminu z informatyki

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

Duża liczba problemów egzaminu Unified State Exam poświęcona jest logice zdań. Do rozwiązania większości z nich wystarczy znajomość podstawowych praw logiki zdań, znajomość tablic prawdy funkcji logicznych jednej i dwóch zmiennych. Podam podstawowe prawa logiki zdań.

Przemienność alternatywy i koniunkcji:
a ˅ b ≡ b ˅ a
a^b ≡ b^a
Prawo rozdzielności dotyczące alternatywy i koniunkcji:
a ˅ (b^с) ≡ (a ˅ b) ^(a ˅ с)
za ^ (b ˅ c) ≡ (a ^ b) ˅ (a ^ c)
Negacja negacji:
¬(¬a) ≡ za
Konsystencja:
a ^ ¬а ≡ fałsz
Ekskluzywna trzecia:
a ˅ ¬а ≡ prawda
Prawa De Morgana:
¬(a ˅ b) ≡ ¬a ˄ ¬b
¬(a ˄ b) ≡ ¬a ˅ ¬b
Uproszczenie:
a ˄ za ≡ za
a ˅ za ≡ za
a ˄ prawda ≡ a
a ˄ fałsz ≡ fałsz
Wchłanianie:
za ˄ (a ˅ b) ≡ za
a ˅ (a ˄ b) ≡ za
Zastąpienie implikacji
a → b ≡ ¬a ˅ b
Zastąpienie tożsamości
za ≡ b ≡(a ˄ b) ˅ (¬a ˄ ¬b)

Reprezentacja funkcji logicznych

Dowolną funkcję logiczną n zmiennych - F(x 1, x 2, ... x n) można określić za pomocą tablicy prawdy. Taka tabela zawiera 2n zbiorów zmiennych, dla każdego z nich podana jest wartość funkcji na tym zbiorze. Metoda ta jest dobra, gdy liczba zmiennych jest stosunkowo niewielka. Już dla n > 5 reprezentacja staje się słabo widoczna.

Innym sposobem jest zdefiniowanie funkcji za pomocą jakiegoś wzoru przy użyciu znanych, dość prostych funkcji. Układ funkcji (f 1, f 2, ... f k) nazywa się kompletnym, jeśli dowolną funkcję logiczną można wyrazić wzorem zawierającym tylko funkcje f i.

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

W rzeczywistości system dwóch funkcji – negacji i koniunkcji lub negacji i alternatywy – jest również kompletny. Z praw De Morgana wynikają idee, które pozwalają wyrazić koniunkcję poprzez negację i alternatywę, a zatem wyrazić alternatywę poprzez negację i koniunkcję:

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

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

Do podstawowych funkcji języków programowania zalicza się najczęściej tożsamość, negację, koniunkcję i alternatywę. W przypadku problemów związanych z egzaminem ujednoliconym stanowym wraz z tymi funkcjami często można znaleźć implikacje.

Przyjrzyjmy się kilku prostym problemom obejmującym funkcje logiczne.

Zadanie 15:

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

X 1	X2	X 3	X 4	F
1	1	0	0	1
0	1	1	1	1
1	0	0	1	0

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

Funkcja numer 3.

Aby rozwiązać problem, należy znać tablice prawdy podstawowych funkcji i pamiętać o priorytetach działań. Przypominam, że koniunkcja (mnożenie logiczne) ma wyższy priorytet i jest wykonywana wcześniej niż rozłączenie (dodawanie logiczne). Podczas obliczeń łatwo zauważyć, że funkcje o numerach 1 i 2 w trzecim zbiorze mają wartość 1 i dlatego nie odpowiadają fragmentowi.

Zadanie 16:

Która z podanych liczb spełnia warunek:

(cyfry, zaczynając od cyfry najbardziej znaczącej, są uporządkowane malejąco) → (liczba – parzysta) ˄ (niska cyfra – parzysta) ˄ (wysoka cyfra – nieparzysta)

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

13579
97531
24678
15386

Warunek spełnia liczba 4.

Dwie pierwsze liczby nie spełniają warunku, ponieważ najniższa cyfra jest nieparzysta. Koniunkcja warunków jest fałszywa, jeśli jeden z warunków koniunkcji jest fałszywy. Dla trzeciej liczby warunek dotyczący najwyższej cyfry nie jest spełniony. Dla czwartej liczby spełnione są warunki nałożone na dolną i górną cyfrę liczby. Pierwszy człon spójnika jest również prawdziwy, ponieważ implikacja jest prawdziwa, jeśli jej przesłanka jest fałszywa, co ma miejsce w tym przypadku.

Problem 17: Dwóch świadków złożyło następujące zeznania:

Pierwszy świadek: Jeśli A jest winny, to B jest jeszcze bardziej winny, a C jest niewinny.

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

Jakie wnioski na temat winy A, B i C można wyciągnąć z zeznań?

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

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

Pierwszą rzeczą do zrobienia jest sformalizowanie stwierdzeń. Wprowadźmy trzy zmienne logiczne - A, B i C, z których każda ma wartość true (1), jeśli odpowiedni podejrzany jest winny. Następnie zeznanie pierwszego świadka wyraża się wzorem:

A → (B ˄ ¬C)

Zeznanie drugiego świadka wyraża się wzorem:

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

Przyjmuje się, że zeznania obu świadków są prawdziwe i stanowią koniunkcję odpowiednich wzorów.

Stwórzmy tabelę prawdy dla tych odczytów:

A	B	C	F 1	F 2	F 1 ˄ F 2
0	0	0	1	0	0
0	0	1	1	0	0
0	1	0	1	0	0
0	1	1	1	0	0
1	0	0	0	0	0
1	0	1	0	1	0
1	1	0	1	1	1
1	1	1	0	0	0

Zbiorczy materiał dowodowy jest prawdziwy tylko w jednym przypadku, co prowadzi do jasnej odpowiedzi – A i B są winni, a C jest niewinny.

Z analizy tej tabeli wynika także, że zeznania drugiego świadka są bardziej pouczające. Z prawdziwości jego świadectwa wynikają tylko dwie rzeczy: możliwe opcje- A i B są winni, a C jest niewinny, lub A i C są winni, a B jest niewinny. Zeznania pierwszego świadka są mniej pouczające - istnieje 5 różnych opcji odpowiadających jego zeznaniom. Łącznie zeznania obu świadków dają jednoznaczną odpowiedź co do winy podejrzanych.

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

Niech F(x 1, x 2, …x n) będzie funkcją logiczną n zmiennych. Równanie logiczne wygląda następująco:

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

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

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

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

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

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

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

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

Rozważmy system k równania logiczne:

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

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

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

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

Ф = fa 1 ˄ fa 2 ˄ … fa k

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

W niektórych zadaniach USE związanych ze znalezieniem rozwiązań układu równań logicznych liczba zmiennych sięga 10. Wtedy skonstruowanie tabeli prawdy staje się zadaniem prawie niemożliwym. Rozwiązanie problemu wymaga innego podejścia. Dla dowolnego układu równań nie ma innej ogólnej metody niż wyliczenie, która pozwalałaby na rozwiązanie takich problemów.

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

Wyjaśnię, czym jest binarne drzewo decyzyjne i jak jest zbudowane na przykładach kilku problemów.

Problem 18

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

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

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

Zbudujmy drzewo decyzyjne dla implikacji (x1 → x2) - pierwszego wyrazu koniunkcji, który można uznać za pierwsze równanie. Tak 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 jest prawdziwe. Ponieważ równanie określa implikację, gałąź, w której X 1 ma wartość 1, wymaga, aby w tej gałęzi X 2 miało wartość 1. Gałąź, w której X 1 ma wartość 0, tworzy dwie gałęzie o wartościach X 2 równe 0 i 1 Skonstruowane drzewo definiuje trzy rozwiązania, na których implikacja X 1 → X 2 przyjmuje wartość 1. Na każdej gałęzi wypisany jest odpowiedni zbiór wartości zmiennych, dający rozwiązanie równania.

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

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

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

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

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

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

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

Problem 19

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

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

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

Z równania X 1 → Y 1 wynika, że gdy X 1 ma wartość 1 (istnieje jedno takie rozwiązanie), to Y 1 również ma wartość 1. Zatem istnieje jeden zbiór, na którym X 1 i Y 1 mają wartości 1. Gdy X 1 jest równe 0, Y 1 może mieć dowolną wartość, zarówno 0, jak i 1. Zatem każdy zbiór z X 1 równym 0, a jest 5 takich zbiorów, odpowiada wszystkim 6 zbiorom ze zmiennymi Y. Zatem całkowita liczba rozwiązań wynosi 31.

Problem 20

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

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

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

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

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

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

Zadanie 21

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

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

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

Zbudujmy drzewo decyzyjne dla tego równania:

Zadanie 22

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

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

((X 3 ≡X 4) ˄ (X 5 ≡X 6)) ˅(¬(X 3 ≡X 4) ˄ ¬(X 5 ≡X6)) = 0

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

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

Odpowiedź: 64

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

Y 1 = (X 1 ≡ X 2); Y 2 = (X 3 ≡ X 4); Y 3 = (X 5 ≡ X 6); Y 4 = (X 7 ≡ X 8); Y 5 = (X 9 ≡ X 10);

Wtedy pierwsze równanie przyjmie postać:

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

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

(Y 1 ≡ Y 2) = 0

Przechodząc do formy tradycyjnej, układ po uproszczeniu zapisujemy w postaci:

¬(Y 1 ≡ Y 2) = 1

¬(Y 2 ≡ Y 3) = 1

¬(Y 3 ≡ Y 4) = 1

¬(Y 4 ≡ Y 5) = 1

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

Wracając do oryginalnych zmiennych X, zauważ, że dla każdej wartości zmiennej Y przypadają 2 wartości w zmiennych X, więc każde rozwiązanie w zmiennych Y generuje 2 5 rozwiązań w zmiennych X. Obie gałęzie generują 2 * 2 5 rozwiązań, więc całkowita liczba rozwiązań wynosi 64.

Jak widać, każdy problem rozwiązania układu równań wymaga własnego podejścia. Powszechną techniką jest wykonywanie równoważnych przekształceń w celu uproszczenia równań. Powszechną techniką jest konstruowanie drzew decyzyjnych. Zastosowane podejście przypomina częściowo konstruowanie tabeli prawdy z tą różnicą, że konstruowane są nie wszystkie zbiory możliwych wartości zmiennych, a tylko te, na których funkcja przyjmuje wartość 1 (prawda). Często w proponowanych problemach nie ma potrzeby budowania pełnego drzewa decyzyjnego, ponieważ już etap początkowy możliwe jest ustalenie schematu pojawiania się nowych gałęzi na każdym kolejnym poziomie, jak to zrobiono na przykład w zadaniu 18.

Ogólnie rzecz biorąc, zadania polegające na znajdowaniu rozwiązań układu równań logicznych są dobrymi ćwiczeniami matematycznymi.

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

Napisanie takiego programu nie jest trudne. Taki program z łatwością poradzi sobie ze wszystkimi zadaniami oferowanymi w Unified State Exam.

Co dziwne, znalezienie rozwiązań układów równań logicznych jest dla komputera trudne i okazuje się, że komputer ma swoje ograniczenia. Komputer dość łatwo poradzi sobie z zadaniami, w których liczba zmiennych wynosi 20-30, ale zacznie myśleć o problemach przez długi czas większy rozmiar. Faktem jest, że funkcja 2 n, która określa liczbę zbiorów, jest funkcją wykładniczą, która rośnie szybko wraz ze wzrostem n. Tak szybko, że zwykły komputer osobisty nie jest w stanie w ciągu dnia udźwignąć zadania, które ma 40 zmiennych.

Program w języku C# do rozwiązywania równań logicznych

Napisanie programu do rozwiązywania równań logicznych jest przydatne z wielu powodów, choćby dlatego, że można za jego pomocą sprawdzić poprawność własnego rozwiązania problemów testowych Unified State Exam. Innym powodem jest to, że taki program jest doskonałym przykładem zadania programistycznego spełniającego wymagania dla zadań kategorii C w Unified State Examination.

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

W takim programie trzeba zbudować pętlę na podstawie liczby zbiorów, uformować sam zbiór w treści pętli na podstawie numeru zbioru, obliczyć wartość funkcji na tym zbiorze i jeśli ta wartość wynosi 1, to zbiór daje rozwiązanie równania.

Jedyna trudność jaka pojawia się przy wdrażaniu programu związana jest z zadaniem wygenerowania samego zbioru wartości zmiennych na podstawie zadanej liczby. Piękno tego problemu polega na tym, że to pozornie trudne zadanie w rzeczywistości sprowadza się do prostego problemu, który pojawiał się już wiele razy. Rzeczywiście wystarczy zrozumieć, że zbiór wartości zmiennych odpowiadających liczbie i, składający się z zer i jedynek, reprezentuje binarną reprezentację liczby i. Zatem złożone zadanie uzyskania zestawu wartości zmiennych według ustalonej liczby sprowadza się do znanego zadania konwersji liczby na postać binarną.

Tak wygląda funkcja w C#, która rozwiązuje nasz problem:

///

/// program do zliczania liczby rozwiązań

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

///

/// funkcja logiczna - metoda,

/// którego podpis jest określony przez delegata DF

///

/// liczba zmiennych

/// liczba rozwiązań

statyczny int SolveEquations(DF zabawa, int n)

zestaw bool = nowy bool[n];

int m = (int)Math.Pow(2, n); //liczba zestawów

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

//Zakończ wyszukiwanie według liczby zestawów

for (int i = 0; tj< m; i++)

//Tworzenie kolejnego zestawu - set,

//określony przez binarną reprezentację liczby i

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

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

//Oblicz wartość funkcji na zbiorze

Mam nadzieję, że wyjaśnienia idei programu i uwagi zawarte w jego tekście wystarczą do zrozumienia programu. Skupię się jedynie na wyjaśnieniu tytułu danej funkcji. Funkcja SolveEquations ma dwa parametry wejściowe. Parametr fun określa funkcję logiczną odpowiadającą rozwiązywanemu równaniu lub układowi równań. Parametr n określa liczbę zmiennych zabawy. W rezultacie funkcja SolveEquations zwraca liczbę rozwiązań funkcji logicznej, czyli liczbę tych zbiorów, w których funkcja ma wartość true.

U dzieci w wieku szkolnym często zdarza się, że pewna funkcja F(x) parametr wejściowy x jest zmienną typu arytmetycznego, łańcuchowego lub logicznego. W naszym przypadku zastosowano mocniejszą konstrukcję. Funkcja SolveEquations odnosi się do funkcji wyższego rzędu - funkcji typu F(f), których parametrami mogą być nie tylko proste zmienne, ale także funkcje.

Klasę funkcji, która może zostać przekazana jako parametr do funkcji SolveEquations, określa się następująco:

delegat bool DF(bool zmienne);

Do tej klasy należą wszystkie funkcje, którym jako parametr przekazywany jest zbiór wartości zmiennych logicznych określonych przez tablicę vars. Wynikiem jest wartość logiczna reprezentująca wartość funkcji w tym zbiorze.

Na koniec, oto program, który wykorzystuje funkcję SolveEquations do rozwiązywania kilku układów równań logicznych. Funkcja SolveEquations jest częścią poniższej klasy ProgramCommon:

Program zajęć Wspólny

delegat bool DF(bool zmienne);

statyczna nieważność Main(argumenty ciągu)

Console.WriteLine("I funkcje - " +

Rozwiąż Równania(Zabawa, 2));

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

Rozwiąż Równania(Zabawa51, 5));

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

Rozwiąż Równania(Zabawa53, 10));

statyczny bool FunAnd(bool vars)

zwróć vars && vars;

statyczny bool Fun51(bool vars)

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

statyczny bool Fun53(bool vars)

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

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

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

10 zadań do samodzielnej pracy

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:

X 1	X2	X 3	X 4	F
1	0	0	1	1
0	1	1	1	1
1	0	1	0	0

Której z trzech funkcji odpowiada ten fragment:

(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żeli zagłosuje na nią przewodniczący jury, poparty przez co najmniej jednego z członków jury. W przeciwnym razie nie zostanie podjęta żadna decyzja. Zbuduj funkcję logiczną formalizującą proces decyzyjny.
X wygrywa z Y, jeśli w czterech rzutach monetą wypadnie trzy reszki. Zdefiniuj funkcję logiczną opisującą wypłatę X.
Słowa w zdaniu są numerowane począwszy od jednego. Zdanie uważa się za poprawnie zbudowane, jeśli spełnione są następujące zasady:
1. Jeśli słowo o liczbie parzystej kończy się samogłoską, wówczas następne słowo, jeśli istnieje, musi zaczynać się od samogłoski.
2. Jeśli słowo o liczbie nieparzystej kończy się spółgłoską, wówczas następne słowo, jeśli istnieje, musi zaczynać się od spółgłoski i kończyć samogłoską.
  Które z poniższych zdań jest poprawnie zbudowane:
3. Mama umyła Maszę mydłem.
4. Lider jest zawsze wzorem.
5. Prawda jest dobra, ale szczęście jest lepsze.
Ile rozwiązań ma równanie:
(a ˄ ¬ b) ˅ (¬a ˄ b) → (c ˄ d) = 1
Wypisz wszystkie rozwiązania równania:
(a → b) → do = 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
X 5 → X 6 ˄ X 6 → X 7 = 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 problemy:

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ą opinie członków jury. Funkcję logiczną określającą podjęcie pozytywnej decyzji można zapisać w następujący sposób:
P ˄ (M 1 ˅ M 2)
Niech zmienna logiczna P i przyjmie wartość 1, gdy i-ty rzut monetą zakończy się reszką. Funkcję logiczną określającą wypłatę X można zapisać w następujący sposób:
¬((¬P 1 ˄ (¬P 2 ˅ ¬P 3 ˅ ¬P 4)) ˅
(¬P 2 ˄ (¬P 3 ˅ ¬P 4)) ˅
(¬P 3 ˄ ¬P 4))
Zdanie 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)

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

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

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

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

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

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

Jeśli liczba zmiennych jest mała, np. mniejsza niż 5, to nie jest trudno skonstruować tablicę prawdy dla tej funkcji, która pozwala nam powiedzieć, ile rozwiązań ma dany układ i jakie zbiory dostarczają rozwiązań.

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

Wyjaśnię, czym jest binarne drzewo decyzyjne i jak jest zbudowane na przykładach kilku problemów.

Problem 18

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

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

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

Zbudujmy drzewo decyzyjne dla implikacji () - pierwszego członu koniunkcji, który można uznać za pierwsze równanie. Tak wygląda graficzna reprezentacja tego drzewa

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

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

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

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

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

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

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

Problem 19

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

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

Z równania wynika, że gdy ma wartość 1 (istnieje jedno takie rozwiązanie), to ma wartość 1. Zatem istnieje jeden zbiór, na którym i ma wartości 1. Gdy jest równe 0, może mają dowolną wartość, zarówno 0, jak i 1. Dlatego każdy zbiór z , równy 0, a jest 5 takich zbiorów, odpowiada wszystkim 6 zbiorom ze zmiennymi Y. Zatem całkowita liczba rozwiązań wynosi 31.

Problem 20

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

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

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

Zadanie 21

Ile rozwiązań ma równanie:

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

Zbudujmy drzewo decyzyjne dla tego równania:

Zadanie 22

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

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

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

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

Zasady wprowadzania funkcji logicznej

Zamiast symbolu v (alternatywa, OR) użyj znaku +.
Nie ma potrzeby podawania oznaczenia funkcji przed funkcją logiczną. Na przykład zamiast F(x,y)=(x|y)=(x^y) musisz po prostu wpisać (x|y)=(x^y) .
Maksymalna liczba zmiennych wynosi 10.

Projektowanie i analiza komputerowych obwodów logicznych odbywa się za pomocą specjalnej gałęzi matematyki - algebry logicznej. W algebrze logiki można wyróżnić trzy główne funkcje logiczne: „NOT” (negacja), „AND” (koniunkcja), „OR” (alternatywa).
Aby stworzyć dowolne urządzenie logiczne, konieczne jest określenie zależności każdej ze zmiennych wyjściowych od istniejących zmiennych wejściowych; zależność ta nazywana jest funkcją przełączającą lub funkcją algebry logicznej.
Funkcję algebry logicznej nazywa się w pełni zdefiniowaną, jeśli podane są wszystkie 2n jej wartości, gdzie n jest liczbą zmiennych wyjściowych.
Jeśli nie wszystkie wartości są zdefiniowane, funkcję nazywa się częściowo zdefiniowaną.
Urządzenie nazywamy logicznym, jeżeli jego stan opisujemy za pomocą funkcji algebry logicznej.
Do przedstawienia funkcji algebry logicznej służą następujące metody:
W formie algebraicznej można zbudować obwód urządzenia logicznego za pomocą elementów logicznych.

Rysunek 1 – Schemat urządzenia logicznego

Wszystkie operacje algebry logicznej są zdefiniowane tablice prawdy wartości. Tabela prawdy określa wynik operacji dla każdy jest możliwy x wartości logiczne oryginalnych instrukcji. Liczba opcji odzwierciedlających wynik zastosowania operacji będzie zależała od liczby instrukcji w wyrażeniu logicznym. Jeśli liczba instrukcji w wyrażeniu logicznym wynosi N, wówczas tabela prawdy będzie zawierać 2 N wierszy, ponieważ istnieje 2 N różnych kombinacji możliwych wartości argumentów.

Działanie NOT - negacja logiczna (inwersja)

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

jeśli pierwotne wyrażenie jest prawdziwe, to wynik jego negacji będzie fałszywy;
jeśli pierwotne wyrażenie jest fałszywe, to wynik jego negacji będzie prawdziwy.

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

A	ani
0	1
1	0

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

Operacja OR - dodawanie logiczne (alternatywa, suma)

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

Operacja AND - mnożenie logiczne (koniunkcja)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Priorytet operacji logicznych

Akcje w nawiasach
Inwersja
Spójnik (&)
Rozłączenie (V), wyłączne OR (XOR), suma modulo 2
Implikacja (→)
Równoważność (↔)

Doskonała rozłączna postać normalna

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

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

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

Doskonała spójna forma normalna

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

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

Możesz wybrać różne sposoby 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 tak, 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 w równaniach znajdują się złożone operacje logiczne, zastępujemy je podstawowymi: „AND”, „OR”, „NOT”. Następnym krokiem jest połączenie równań w jedno, równoważne układowi, za pomocą operacji logicznej „AND”. Następnie należy przekształcić powstałe równanie w oparciu o prawa algebry logicznej i uzyskać konkretne rozwiązanie układu.

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

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

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

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

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

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

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








0	0	1	1	0	1

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

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

Rozwiązanie 3: 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. Uwzględniając nowe zmienne, równanie zostanie zapisane jako: X + Y = 1.

Rozłączenie jest prawdziwe w trzech przypadkach: (0;1), (1;0) i (1;1), natomiast X i Y są implikacjami, czyli jest prawdziwe w trzech przypadkach i fałszywe w jednym. Zatem przypadek (0;1) będzie odpowiadał trzem możliwym kombinacjom parametrów. Przypadek (1;1) – będzie odpowiadał dziewięciu możliwym kombinacjom parametrów pierwotnego równania. 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. 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.

Załóżmy, że X 1 – jest prawdą, to z pierwszego równania to otrzymujemy X 2 to również 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 używają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)*

Temat lekcji: Rozwiązywanie równań logicznych

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

Rozwojowe - stworzyć warunki do rozwoju zainteresowanie poznawcze studenci, promują rozwój pamięci, uwagi, logicznego myślenia;

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

Typ lekcji: lekcja łączona

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

Postęp lekcji

Powtarzanie i aktualizacja podstawowej wiedzy. Sprawdzanie pracy domowej (10 minut)

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

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

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

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

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

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

A – spółgłoska pierwszej litery

B – spółgłoska drugiej litery

S – samogłoska ostatniej litery

D – przedostatnia litera samogłoski

Zróbmy wyrażenie:

Zróbmy tabelę:

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

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

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

Które wyrażenie pasuje do F?

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

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

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

1. Rozwiąż równanie logiczne

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

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

Rozwiązanie:

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

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

Odpowiedź: 0100

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

Rozwiązanie: przekształć wyrażenie

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

A +B =1 i C +D =1

Metoda 2: sporządzenie tabeli prawdy

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

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

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

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

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

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

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

Uprośćmy wyrażenie:

3 sposoby: budowa SDNF

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

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

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

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

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

Rozwiązanie:

3. Praca domowa (5 minut)

Rozwiąż równanie:

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

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

uprościć to.