2 funkcja logiczna f jest dana wyrażeniem x. Funkcję logiczną F podaje się za pomocą wyrażenia

Na podstawie: wersji demonstracyjnych Unified State Exam z informatyki na rok 2015, na podstawie podręcznika Ludmiły Leonidovnej Bosowej

W poprzedniej części 1 omówiliśmy z Wami operacje logiczne Rozłączenie i Koniunkcja, pozostaje nam jedynie przeanalizować inwersję i przejść do rozwiązywania zadania Unified State Exam.

Inwersja

Inwersja- operacja logiczna, która wiąże każde stwierdzenie z nowym stwierdzeniem, którego znaczenie jest przeciwne do pierwotnego.

Do zapisu inwersji używane są następujące znaki: NOT, `¯`, ` ¬ `

Inwersję określa następująca tabela prawdy:

Inwersję nazywa się inaczej negacją logiczną.

W formularzu można zapisać dowolne złożone oświadczenie wyrażenie logiczne— wyrażenia zawierające zmienne logiczne, znaki operatorów logicznych i nawiasy. Operacje logiczne na wyrażeniu logicznym wykonywane są w następującej kolejności: inwersja, koniunkcja, alternatywna. Możesz zmienić kolejność operacji za pomocą nawiasów.

Operacje logiczne mają następujący priorytet: inwersja, koniunkcja, dysjunkcja.

I tak przed nami zadanie nr 2 z Unified State Exam z informatyki 2015

Aleksandra uzupełniała tabelę prawdy dla wyrażenia F. Udało jej się wypełnić jedynie niewielki fragment tabeli:

x1	x2	x3	x4	x5	x6	x7	x8	F
	0						1	0
1			0					1
			1				1	1

Jakim wyrażeniem może być F?

Rozwiązanie problemu znacznie ułatwia fakt, że w każdej wersji wyrażenia złożonego F występuje tylko jedna operacja logiczna: mnożenie lub dodawanie. W przypadku mnożenia /\ jeśli przynajmniej jedna zmienna jest równa zero, to wartość całego wyrażenia F również musi być równa zero. A w przypadku dodawania V, jeśli choć jedna zmienna jest równa jeden, to wartość całego wyrażenia F musi być równa 1.

Dane znajdujące się w tabeli dla każdej z 8 zmiennych wyrażenia F wystarczą nam do rozwiązania.

Sprawdźmy wyrażenie numer 1:

• ? /\ 1 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 0 )
• z drugiego wiersza tabeli x1=1, x4=0 widzimy, że F jest możliwe i może wynosić = 1, jeśli wszystkie pozostałe zmienne są równe 1 (1 /\ ? /\ ? /\ 1 /\ ? /\ ? /\ ? /\ ? )
• zgodnie z trzecim wierszem tabeli x4=1, x8=1 widzimy, że F=0 (? /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ 0 ), a w tabeli mamy F=1, a to oznacza, że ​​wyrażenie numer jeden jest dla nas ZDECYDOWANIE NIE ODPOWIEDNIE.

Sprawdźmy wyrażenie numer 2:

• z pierwszego wiersza tabeli x2=0, x8=1 widzimy, że F jest możliwe i może wynosić = 0, jeśli wszystkie pozostałe zmienne są równe 0 (? V 0 V ? V ? V ? V ? V ? V 0 )
• z drugiego wiersza tabeli x1=1, x4=0 widzimy, że F = 1 ( 1 V ? V ? V 1 V ? V ? V ? V ? )
• zgodnie z trzecim wierszem tabeli x4=1, x8=1 widzimy, że F jest możliwe i może wynosić = 1, jeśli chociaż jedna z pozostałych zmiennych jest równa 1 ( ? V ? V ? V 0 V ? V ? V ? V 0 )
  

Sprawdźmy wyrażenie numer 3:

• z pierwszego wiersza tabeli x2=0, x8=1 widzimy, że F=0 (? /\ 0 /\ ? /\ ? /\ ? /\ ? /\ ? /\ 1 )
• z drugiego wiersza tabeli x1=1, x4=0 widzimy, że F =0 (0 /\ ? /\ ? /\ 0 /\ ? /\ ? /\ ? /\ ? ), a w tabeli mamy F=1, a to oznacza, że ​​daje nam wyrażenie numer trzy ZDECYDOWANIE NIE ODPOWIEDNIE.

Sprawdźmy wyrażenie numer 4:

• z pierwszego wiersza tabeli x2=0, x8=1 widzimy, że F=1 ( ? V 1 V ? V ? V ? V ? V ? V 0 ), a w tabeli mamy F=0, a to oznacza, że ​​daje nam wyrażenie numer cztery ZDECYDOWANIE NIE ODPOWIEDNIE.

Rozwiązując zadanie na egzaminie ujednoliconego stanu, musisz zrobić dokładnie to samo: odrzucić te opcje, które zdecydowanie nie są odpowiednie na podstawie danych w tabeli. Pozostała możliwa opcja (jak w naszym przypadku opcja nr 2) będzie poprawną odpowiedzią.

Katalog zadań.
Liczba programów z etapem obowiązkowym

Sortowanie Podstawowe Pierwsze proste Pierwsze złożone Popularność Pierwsze nowe Pierwsze stare
Rozwiąż testy dotyczące tych zadań
Wróć do katalogu zadań
Wersja do druku i kopiowania w programie MS Word

Wykonawca A16 przelicza liczbę zapisaną na ekranie.

Wykonawca ma trzy zespoły, którym przypisane są numery:

1. Dodaj 1

2. Dodaj 2

3. Pomnóż przez 2

Pierwszy z nich zwiększa liczbę na ekranie o 1, drugi zwiększa ją o 2, trzeci mnoży ją przez 2.

Program dla wykonawcy A16 jest ciągiem poleceń.

Ile jest programów, które konwertują pierwotną liczbę 3 na liczbę 12, a jednocześnie ścieżka obliczeniowa programu zawiera liczbę 10?

Trajektoria obliczeniowa programu to sekwencja wyników wykonania wszystkich poleceń programu. Na przykład dla programu 132 o początkowej liczbie 7 trajektoria będzie składać się z liczb 8, 16, 18.

Rozwiązanie.

Wymagana liczba programów jest równa iloczynowi liczby programów, które z liczby 3 uzyskają liczbę 10, przez liczbę programów, które z liczby 10 uzyskają liczbę 12.

Niech R(n) będzie liczbą programów, które konwertują liczbę 3 na liczbę n, a P(n) będzie liczbą programów, które konwertują liczbę 10 na liczbę n.

Dla wszystkich n > 5 prawdziwe są następujące zależności:

1. Jeśli n nie jest podzielne przez 2, to R(n) = R(n - 1) + R(n - 2), ponieważ n można uzyskać na dwa sposoby - przez dodanie jednego lub dodanie dwóch. Podobnie P(n) = P(n - 1) + P(n - 2)

2. Jeśli n jest podzielne przez 2, to R(n) = R(n - 1) + R(n - 2) + R(n / 2). Podobnie P(n) = P(n - 1) + P(n - 2) + P(n / 2)

Obliczmy sekwencyjnie wartości R(n):

R(5) = R(4) + R(3) = 1 + 1 = 2

R(6) = R(5) + R(4) + R(3) = 2 + 1 + 1 = 4

R(7) = R(6) + R(5) = 4 + 2 = 6

R(8) = R(7) + R(6) + R(4) = 6 + 4 + 1 = 11

R(9) = R(8) + R(7) = 11 + 6 = 17

R(10) = R(9) + R(8) + R(5) = 17 + 11 + 2 = 30

Teraz obliczmy wartości P(n):

P(11) = P(10) = 1

P(12) = P(11) + P(10) = 2

Zatem liczba programów spełniających warunki zadania wynosi 30 · 2 = 60.

Odpowiedź: 60.

Odpowiedź: 60

Źródło: Wersja demonstracyjna egzaminu Unified State Exam 2017 z informatyki.

1. Dodaj 1

2. Dodaj 3

Ile jest programów, dla których przy początkowej liczbie 1 wynikiem jest liczba 17, a jednocześnie trajektoria obliczeń zawiera liczbę 9? Trajektoria obliczeniowa programu to sekwencja wyników wykonania wszystkich poleceń programu. Na przykład dla programu 121 o początkowej liczbie 7 trajektoria będzie składać się z liczb 8, 11, 12.

Rozwiązanie.

Stosujemy metodę programowania dynamicznego. utwórzmy tablicę dp, gdzie dp[i] to liczba sposobów uzyskania liczby i za pomocą takich poleceń.

Baza dynamiki:

Formuła przejścia:

dp[i]=dp + dp

Nie uwzględnia to wartości dla liczb większych niż 9, które można uzyskać z liczb mniejszych niż 9 (pomijając w ten sposób trajektorię 9):

Odpowiedź: 169.

Odpowiedź: 169

Źródło: Praca szkoleniowa z informatyki, klasa 11 29 listopada 2016 Opcja IN10203

Performer May17 konwertuje liczbę na ekranie.

Wykonawca ma dwa zespoły, którym przypisane są numery:

1. Dodaj 1

2. Dodaj 3

Pierwsza komenda zwiększa liczbę na ekranie o 1, druga zwiększa ją o 3. Program dla wykonawcy May17 to ciąg komend.

Ile jest programów, dla których przy początkowej liczbie 1 wynikiem jest liczba 15, a jednocześnie ścieżka obliczeniowa zawiera liczbę 8? Trajektoria obliczeniowa programu to sekwencja wyników wykonania wszystkich poleceń programu. Na przykład dla programu 121 o początkowej liczbie 7 trajektoria będzie składać się z liczb 8, 11, 12.

Rozwiązanie.

Stosujemy metodę programowania dynamicznego. Stwórzmy tablicę dp, gdzie dp[i] to liczba sposobów uzyskania liczby i za pomocą takich poleceń.

Baza dynamiki:

Formuła przejścia:

dp[i]=dp + dp

Ale to nie uwzględnia liczb większych niż 8, ale możemy do nich dotrzeć od wartości mniejszej niż 8. Poniżej zostaną pokazane wartości w komórkach dp od 1 do 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 .

Źródło pracy: Rozwiązanie 2437. Ujednolicony egzamin państwowy 2017. Informatyka. VR Leschinera. 10 opcji.

Zadanie 2. Funkcję logiczną F podaje się za pomocą wyrażenia . Określ, która kolumna tabeli prawdy funkcji F odpowiada każdej ze zmiennych x, y, z.

W swojej odpowiedzi wpisz litery x, y, z w kolejności, w jakiej pojawiają się odpowiadające im kolumny (najpierw - litera odpowiadająca 1. kolumnie, następnie - litera odpowiadająca 2. kolumnie, następnie - litera odpowiadająca 3. kolumnie kolumna). Litery odpowiedzi wpisz po kolei, nie ma potrzeby wstawiania żadnych separatorów pomiędzy literami.

Rozwiązanie.

Przepiszmy wyrażenie na F uwzględniając priorytety operacji negacji, koniunkcji i alternatywy:

.

Rozważmy czwarty wiersz tabeli (1,1,0)=0. Z tego widzimy, że na trzecim miejscu musi znajdować się albo zmienna y, albo zmienna z, w przeciwnym razie drugi nawias będzie zawierał 1, co doprowadzi do wartości F=1. Rozważmy teraz piąty wiersz tabeli (0,0,1)=1. Ponieważ x musi znajdować się na pierwszym lub drugim miejscu, pierwszy nawias da 1 tylko wtedy, gdy y znajduje się na trzecim miejscu. Biorąc pod uwagę, że drugi nawias jest zawsze równy 0, wówczas F=1 otrzymuje się z 1 w pierwszym nawiasie. W ten sposób odkryliśmy, że y jest na trzecim miejscu. Na koniec rozważ siódmy wiersz tabeli (1,0,1)=0. Tutaj y=1 i dla F=0 konieczne jest posiadanie z=0 i x=1, zatem x jest na pierwszym miejscu, a z na drugim.

Funkcja logiczna F jest dane przez wyrażenie X/\ ¬j/\ (¬z\/ w).

Na rysunku przedstawiono fragment tablicy prawdy funkcji F zawierający Wszystko zestawy argumentów, dla których funkcja F PRAWDA.

Określ, która kolumna tabeli prawdy funkcji F każda ze zmiennych odpowiada w, X, y, z.

Wpisz litery w swojej odpowiedzi w, X, y, z w kolejności, w jakiej przychodzą

odpowiadające im kolumny (pierwsza – litera odpowiadająca pierwszej

kolumna; następnie litera odpowiadająca drugiej kolumnie itp.) Litery

W swojej odpowiedzi pisz w wierszu, nie wstawiaj żadnych separatorów między literami.

nie ma potrzeby.

Wersja demonstracyjna Unified State Examination USE 2017 – zadanie nr 2

Rozwiązanie:

Spójnik (mnożenie logiczne) jest prawdziwy wtedy i tylko wtedy, gdy wszystkie zdania są prawdziwe. Dlatego zmienna X 1 .

Zmienny ¬j musi pasować do kolumny, w której wszystkie wartości są równe 0 .

Rozdzielenie (dodatek logiczny) dwóch zdań jest prawdziwe wtedy i tylko wtedy, gdy przynajmniej jedno zdanie jest prawdziwe.
Dysjunkcja ¬z\/y z=0, w=1.

Zatem zmienna ¬z w odpowiada kolumnie ze zmienną 4 (kolumna 4).

Odpowiedź: zyxw

Wersja demonstracyjna Unified State Examination USE 2016 – zadanie nr 2

Funkcja logiczna F wyraża się wyrażeniem (¬z)/\x \/ x/\y. Określ, która kolumna tabeli prawdy funkcji F odpowiada każdej ze zmiennych x, y, z.

W swojej odpowiedzi wpisz litery x, y, z w kolejności, w jakiej pojawiają się odpowiadające im kolumny (najpierw - litera odpowiadająca 1. kolumnie, następnie - litera odpowiadająca 2. kolumnie, następnie - litera odpowiadająca 3. kolumnie kolumna). Litery odpowiedzi wpisz po kolei, nie ma potrzeby wstawiania żadnych separatorów pomiędzy literami.

Przykład. Niech zostanie podane wyrażenie x → y w zależności od dwóch zmiennych x i y oraz tabeli prawdy:

Wtedy pierwsza kolumna odpowiada zmiennej y, a druga kolumna
odpowiada zmiennej x. W odpowiedzi musisz napisać: yx.

Rozwiązanie:

1. Zapiszmy podane wyrażenie w prostszej notacji:

¬z*x + x*y = x*(¬z + y)

2. Koniunkcja (mnożenie logiczne) jest prawdziwa wtedy i tylko wtedy, gdy wszystkie zdania są prawdziwe. Zatem, aby funkcja ( F) był równy jeden ( 1 ), każdy współczynnik musi być równy jeden ( 1 ). Zatem kiedy F=1, zmienny X musi pasować do kolumny, w której wszystkie wartości są równe 1 .

3. Rozważ (¬z + y), Na F=1 to wyrażenie jest również równe 1 (patrz punkt 2).

4. Rozdzielenie (dodatek logiczny) dwóch zdań jest prawdziwe wtedy i tylko wtedy, gdy przynajmniej jedno zdanie jest prawdziwe.
Dysjunkcja ¬z\/y w tej linii będzie prawdziwe tylko wtedy, gdy

1. z = 0; y = 0 Lub y = 1;
2. z = 1; y = 1

5. Zatem zmienna ¬z odpowiada kolumnie ze zmienną 1 (1 kolumna), zmienna y

Odpowiedź: zyx

KIM Unified State Examation Unified State Exam 2016 (okres wczesny)– zadanie nr 2

Funkcję logiczną F podaje się za pomocą wyrażenia

(x /\ y /\¬z) \/ (x /\ y /\ z) \/ (x /\¬y /\¬z).

Na rysunku przedstawiono fragment tablicy prawdy funkcji F, zawierający wszystkie zbiory argumentów, dla których funkcja F jest prawdziwa. Określ, która kolumna tabeli prawdy funkcji F odpowiada każdej ze zmiennych x, y, z.

W swojej odpowiedzi wpisz litery x, y, z w kolejności, w jakiej pojawiają się odpowiadające im kolumny (najpierw - litera odpowiadająca pierwszej kolumnie, następnie - litera odpowiadająca drugiej kolumnie itd.) Wpisz litery w odpowiedz z rzędu, bez separatorów. Nie ma potrzeby umieszczania jej pomiędzy literami.

R rozwiązanie:

Zapiszmy dane wyrażenie w prostszej notacji:

(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1

To wyrażenie jest prawdziwe, gdy przynajmniej jedno z (x*y*¬z), (x*y*z), (x*¬y*¬z) jest równe 1. Koniunkcja (mnożenie logiczne) jest prawdziwa wtedy i tylko wtedy, gdy wszystkie stwierdzenia są prawdziwe.

Przynajmniej jedno z tych rozbieżności x*y*¬z; x*y*z; x*¬y*¬z będzie prawdą tylko wtedy, gdy x=1.

Zatem zmienna X odpowiada kolumnie ze zmienną 2 (kolumna 2).

Pozwalać y- zmienna 1, z- premia 3. Następnie w pierwszym przypadku x*¬y*¬z będzie prawdą w drugim przypadku x*y*¬z i w trzecim x*y*z.

Odpowiedź: yxz

Symbol F oznacza jedno z następujących wyrażeń logicznych z trzech argumentów: X, Y, Z. Podano fragment tablicy prawdy wyrażenia F (patrz tabela po prawej). Które wyrażenie pasuje do F?

X	Y	Z	F
0	0	0	0
1	0	1	1
0	1	0	1

1) X ∧ Y ∧ Z 2) ¬X ∨ Y ∨¬Z 3) X ∧ Y ∨ Z 4) X ∨ Y ∧ ¬Z

Rozwiązanie:

1) X ∧ Y ∧ Z = 1.0.1 = 0 (nie pasuje do drugiej linii)

2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1+0+1 = 1 (nie pasuje do pierwszej linii)

3) X ∧ Y ∨ Z = 0,1+0 = 0 (nie pasuje do 3. linii)

4) X ∨ Y ∧ ¬Z (odpowiada F)

X ∨ Y ∧ ¬Z = 0 ∨ 0 ∧ ¬0 = 0+0,1 = 0

X ∨ Y ∧ ¬Z = 1 ∨ 0 ∧ ¬1 = 1+0,0 = 1

X ∨ Y ∧ ¬Z = 0 ∨ 1 ∧ ¬0 = 0+1,1 = 1

Odpowiedź: 4

Biorąc pod uwagę fragment tabeli prawdy wyrażenia F. Które wyrażenie odpowiada F?

A	B	C	F
0	1	1	1
1	0	0	0
1	0	1	1

1) (A → ¬B) ∨ C 2) (¬A ∨ B) ∧ C 3) (A ∧ B) → C 4) (A ∨ B) → C

Rozwiązanie:

1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (nie pasuje do 2. linii)

2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0+0).1 = 0 (nie pasuje do 3. linii)

3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (nie pasuje do drugiej linii)

4) (A ∨ B) → C (odpowiada F)

(A ∨ B) → do = (0 ∨ 1) → 1 = 1

(A ∨ B) → do = (1 ∨ 0) → 0 = 0

(A ∨ B) → do = (1 ∨ 0) → 1 = 1

Odpowiedź: 4

Podano wyrażenie logiczne zależne od 6 zmiennych logicznych:

X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6

Ile jest różnych zestawów wartości zmiennych, dla których wyrażenie jest prawdziwe?

1) 1 2) 2 3) 63 4) 64

Rozwiązanie:

Fałszywe wyrażenie tylko w 1 przypadku: X1=0, X2=1, X3=0, X4=1, X5=0, X6=0

X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6 = 0 ∨ ¬1 ∨ 0 ∨ ¬1 ∨ 0 ∨ 0 = 0

W sumie jest 2 6 =64 opcji, co oznacza prawdę

Odpowiedź: 63

Podano fragment tablicy prawdy wyrażenia F.

x1	x2	x3	x4	x5	x6	x7	F
0	1	0	1	1	1	0	0
1	1	0	1	0	1	0	1
0	1	0	1	1	0	1	0

Które wyrażenie pasuje do F?

1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7

Rozwiązanie:

1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 + … = 1 (nie pasuje do 1. linii)

2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (nie pasuje do pierwszej linii)

3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1,0. ...= 0 (nie pasuje do drugiej linii)

4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (odpowiada F)

x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 1.1.1.1.1.1.1 = 1

x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 = 0. … = 0

Odpowiedź: 4

x1	x2	x3	x4	x5	x6	x7	x8	F
		0				1		1
1		0			1			0
			1				0	1

Jakim wyrażeniem może być F?

1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8

Rozwiązanie:

1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1 . ¬x2. 0. ... = 0 (nie pasuje do pierwszej linii)

2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (odpowiada F)

3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 = … ¬x7 ∧ ¬x8 = … ¬1 ∧ ¬x8 = … 0 ∧ ¬x8 = 0 (nie pasuje do 1 - ta linia)

4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x3 … = ¬1 ∨ ¬x2 ∨ ¬0 .. = 1 (nie mecze w drugiej linii)

Odpowiedź: 2

Podano fragment tablicy prawdy dla wyrażenia F:

x1	x2	x3	x4	x5	x6	x7	F
0	0	1	1	0	0	1	0
0	1	0	0	1	1	0	1
0	0	0	0	1	1	1	1
1	0	1	0	1	1	0	1
0	1	1	1	0	1	0	1

Znajdź minimalną możliwą liczbę różnych wierszy w pełnej tabeli prawdy tego wyrażenia, w której wartość x5 odpowiada F.

Rozwiązanie:

Minimalna możliwa liczba odrębnych wierszy, w których x5 odpowiada F = 4

Odpowiedź: 4

Podano fragment tablicy prawdy dla wyrażenia F:

x1	x2	x3	x4	x5	x6	x7	x8	F
0	0	1	1	0	0	1	0	0
0	1	0	0	1	1	0	1	1
0	0	0	0	1	1	1	1	1
1	0	1	0	1	1	0	1	1
0	1	1	1	0	1	0	0	1

Znajdź maksymalną możliwą liczbę różnych wierszy w pełnej tablicy prawdy tego wyrażenia, w której wartość x6 nie pokrywa się z F.

Rozwiązanie:

Maksymalna możliwa liczba = 2 8 = 256

Maksymalna możliwa liczba różnych wierszy, w których wartość x6 nie pasuje F = 256 – 5 = 251

Odpowiedź: 251

Podano fragment tablicy prawdy dla wyrażenia F:

x1	x2	x3	x4	x5	x6	x7	F
0	0	1	1	0	0	1	0
0	1	0	0	1	1	0	1
0	0	0	0	1	1	1	1
1	0	1	0	1	1	0	1
0	1	1	1	0	1	0	1

Znajdź maksymalną możliwą liczbę różnych wierszy pełnej tablicy prawdy tego wyrażenia, w której wartość ¬x5 ∨ x1 pokrywa się z F.

Rozwiązanie:

1+0=1 – nie pasuje do F

0+0=0 – nie pasuje do F

0+0=0 – nie pasuje do F

0+1=1 – pokrywa się z F

1+0=1 – pokrywa się z F

2 7 = 128 – 3 = 125

Odpowiedź: 125

Każde wyrażenie logiczne A i B zależy od tego samego zestawu 6 zmiennych. W tabelach prawdy każde z tych wyrażeń ma dokładnie 4 jednostki w kolumnie wartości. Jaka jest minimalna możliwa liczba jedynek w kolumnie wartości tabeli prawdy wyrażenia A ∨ B?

Rozwiązanie:

Odpowiedź: 4

Każde wyrażenie logiczne A i B zależy od tego samego zestawu 7 zmiennych. W tabelach prawdy każde z tych wyrażeń ma dokładnie 4 jednostki w kolumnie wartości. Jaka jest maksymalna możliwa liczba jedynek w kolumnie wartości tabeli prawdy wyrażenia A ∨ B?

Rozwiązanie:

Odpowiedź: 8

Każde wyrażenie logiczne A i B zależy od tego samego zestawu 8 zmiennych. W tabelach prawdy każde z tych wyrażeń ma dokładnie 5 jednostek w kolumnie wartości. Jaka jest minimalna możliwa liczba zer w kolumnie wartości tabeli prawdy wyrażenia A ∧ B?

Rozwiązanie:

2 8 = 256 – 5 = 251

Odpowiedź: 251

Każde wyrażenie logiczne A i B zależy od tego samego zestawu 8 zmiennych. W tabelach prawdy każde z tych wyrażeń ma dokładnie 6 jednostek w kolumnie wartości. Jaka jest maksymalna możliwa liczba zer w kolumnie wartości tabeli prawdy wyrażenia A ∧ B?

Rozwiązanie:

Odpowiedź: 256

Każde z wyrażeń logicznych A i B zależy od tego samego zestawu 5 zmiennych. W tabelach prawdy obu wyrażeń nie ma pasujących wierszy. Ile jedynek będzie zawarte w kolumnie wartości tabeli prawdy wyrażenia A ∧ B?

Rozwiązanie:

W tabelach prawdy obu wyrażeń nie ma pasujących wierszy.

Odpowiedź: 0

Każde z wyrażeń logicznych A i B zależy od tego samego zestawu 6 zmiennych. W tabelach prawdy obu wyrażeń nie ma pasujących wierszy. Ile jedynek będzie zawarte w kolumnie wartości tabeli prawdy wyrażenia A ∨ B?

Rozwiązanie:

Odpowiedź: 64

Każde z wyrażeń boolowskich A i B zależy od tego samego zestawu 7 zmiennych. W tabelach prawdy obu wyrażeń nie ma pasujących wierszy. Jaka jest maksymalna możliwa liczba zer w kolumnie wartości tabeli prawdy wyrażenia ¬A ∨ B?

Rozwiązanie:

A=1,B=0 => ¬0 ∨ 0 = 0 + 0 = 0

Odpowiedź: 128

Każde z wyrażeń boolowskich F i G zawiera 7 zmiennych. W tablicach prawdy wyrażeń F i G znajduje się dokładnie 8 identycznych wierszy i dokładnie 5 z nich ma w kolumnie wartość 1. Ile wierszy tabeli prawdy dla wyrażenia F ∨ G zawiera 1 w kolumnie wartości ?

Rozwiązanie:

Jest dokładnie 8 identycznych wierszy i dokładnie 5 z nich ma wartość 1 w kolumnie wartości.

Oznacza to, że dokładnie 3 z nich mają w kolumnie wartości wartość 0.

Odpowiedź: 125

Funkcję logiczną F wyraża się wyrażeniem (a ∧ ¬c) ∨ (¬b ∧ ¬c). Określ, która kolumna tabeli prawdy funkcji F odpowiada każdej ze zmiennych a, b, c.

?	?	?	F
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	0

W swojej odpowiedzi wpisz litery a, b, c w kolejności, w jakiej pojawiają się odpowiadające im kolumny.

Rozwiązanie:

(a. ¬c) + (¬b. ¬c)

Gdy c wynosi 1, F wynosi zero, więc ostatnia kolumna to c.

Do określenia pierwszej i drugiej kolumny możemy wykorzystać wartości z trzeciego wiersza.

(a . 1) + (¬b . 1) = 0

Odpowiedź: ABC

Funkcję logiczną F wyraża się wyrażeniem (a ∧ c)∨ (¬a ∧ (b ∨ ¬c)). Określ, która kolumna tabeli prawdy funkcji F odpowiada każdej ze zmiennych a, b, c.

Na podstawie faktu, że gdy a=0 i c=0, to F=0 i danych z drugiego wiersza, możemy stwierdzić, że trzecia kolumna zawiera B.

Odpowiedź: taksówka

Funkcja logiczna F jest dana przez x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). Na rysunku przedstawiono fragment tablicy prawdy funkcji F, zawierający wszystkie zbiory argumentów, dla których funkcja F jest prawdziwa. Określ, która kolumna tabeli prawdy funkcji F odpowiada każdej ze zmiennych x, y, z, w.

?	?	?	?	F
0	1	0	1	1
0	1	1	0	1
1	1	0	1	1

W swojej odpowiedzi wpisz litery x, y, z, w w kolejności, w jakiej pojawiają się odpowiadające im kolumny.

Rozwiązanie:

x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)

X. (¬y. z. ¬w. y. ¬z)

Z faktu, że przy x=0, to F=0, możemy stwierdzić, że druga kolumna zawiera X.

Odpowiedź: wxzy

Analiza zadania 2 egzaminu Unified State Exam 2017 z informatyki z projektu w wersji demonstracyjnej. Jest to zadanie o podstawowym stopniu trudności. Przybliżony czas na wykonanie zadania to 3 minuty.

Testowane elementy treści: umiejętność konstruowania tablic prawdy i obwodów logicznych. Elementy treści sprawdzane na egzaminie Unified State Exam: stwierdzenia, operacje logiczne, kwantyfikatory, prawdziwość stwierdzeń.

Zadanie 2:

Funkcja logiczna F jest dane przez wyrażenie X /\¬ y /\ (¬ z \/ w).
Na rysunku przedstawiono fragment tablicy prawdy funkcji F zawierający Wszystko F PRAWDA.
Określ, która kolumna tabeli prawdy funkcji F każda ze zmiennych odpowiada w, X, y, z.

Wpisz litery w swojej odpowiedzi w, x, y, z w kolejności występowania odpowiednich kolumn (najpierw - litera odpowiadająca pierwszej kolumnie, następnie - litera odpowiadająca drugiej kolumnie itd.) Litery odpowiedzi wpisz z rzędu, nie ma potrzeby wstawiania żadnych separatory między literami.

Przykład. Jeżeli funkcję podano wyrażeniem ¬ X \/ y, w zależności od dwóch zmiennych: X I y, i podano fragment jego tablicy prawdy, zawierający Wszystko zestawy argumentów, dla których funkcja F PRAWDA.

Wtedy pierwsza kolumna będzie odpowiadać zmiennej y, a druga kolumna jest zmienną X. Odpowiedź powinna być napisana: yx.

Odpowiedź: ________

X /\¬ y /\ (¬ z \/ w)

Spójnik (mnożenie logiczne) jest prawdziwy wtedy i tylko wtedy, gdy wszystkie zdania są prawdziwe. Dlatego zmienna X 1 .

Zatem zmienna X odpowiada kolumnie ze zmienną 3.

Zmienny ¬j kolumna zawierająca wartość musi być zgodna 0 .

Rozdzielenie (dodatek logiczny) dwóch zdań jest prawdziwe wtedy i tylko wtedy, gdy przynajmniej jedno zdanie jest prawdziwe.
Dysjunkcja ¬z\/w w tej linii będzie prawdziwe tylko wtedy, gdy z=0, w=1.

Zatem zmienna ¬z odpowiada kolumnie ze zmienną 1 (1 kolumna), zmienna w odpowiada kolumnie ze zmienną 4 (kolumna 4).