Egzamin stanowy z informatyki ujednoliconej 2. Funkcję logiczną F podaje się za pomocą wyrażenia

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

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 trajektoria 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 ścieżka obliczeniowa 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 istnieje 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 .

Najpierw zdefiniujmy, co mamy w problemie:

• funkcja logiczna F zdefiniowana przez jakieś wyrażenie. Elementy tablicy prawdy tej funkcji przedstawiono także w zadaniu w formie tabeli. Zatem podstawiając do wyrażenia określone wartości x, y, z z tabeli, wynik powinien pokrywać się z podanym w tabeli (patrz wyjaśnienie poniżej).
• Zmienne x, y, z i trzy kolumny im odpowiadające. Co więcej, w tym zadaniu nie wiemy, która kolumna odpowiada której zmiennej. Oznacza to, że w kolumnie Zmienna. 1 może oznaczać x, y lub z.
• Jesteśmy proszeni o określenie, która kolumna odpowiada której zmiennej.

Spójrzmy na przykład.

Rozwiązanie

1. Wróćmy teraz do rozwiązania. Przyjrzyjmy się bliżej formule: \((\neg z) \wedge x \vee x\wedge y\)
2. Zawiera dwie konstrukcje z spójnikiem, połączone alternatywną. Jak wiadomo, najczęściej alternatywna wersja jest prawdziwa (w tym celu wystarczy, że jeden z terminów jest prawdziwy).
3. Przyjrzyjmy się zatem uważnie liniom, w których wyrażenie F jest fałszywe.
4. Pierwsza linia nie jest dla nas interesująca, ponieważ nie określa, gdzie jest (wszystkie wartości są takie same).
5. Rozważmy zatem przedostatni wiersz, który zawiera większość 1, ale wynikiem jest 0.
6. Czy z może znajdować się w trzeciej kolumnie? Nie, ponieważ w tym przypadku we wzorze wszędzie będą jedynki, a zatem wynik będzie równy 1, ale zgodnie z tabelą prawdy wartość F w tym wierszu wynosi 0. Zatem z nie może być zmienną . 3.
7. Podobnie w poprzednim wierszu mamy, że z nie może być zmienne. 2.
8. Stąd, z jest zmienną. 1.
9. Wiedząc, że z znajduje się w pierwszej kolumnie, rozważmy trzeci wiersz. Czy x może znajdować się w drugiej kolumnie? Zastąpmy wartości:
   \((\neg z) \wedge x \vee x\wedge y = \\ = (\neg 0) \wedge 1 \vee 1\wedge 0 = \\ = 1 \wedge 1 \vee 0 = \\ = 1 \vee 0 = 1\)
10. Jednak zgodnie z tabelą prawdy wynik musi wynosić 0.
11. Stąd, x nie może być Per. 2.
12. Stąd, x jest zmienną. 3.
13. Dlatego metodą eliminacji y jest zmienną. 2.
14. Zatem odpowiedź jest następująca: zyx (z - Zmienna 1, y - Zmienna 2, x - Zmienna 3).

Na podstawie: wersji demonstracyjnych Unified State Examination 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 poniższa 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 to 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ą.

Wersja demonstracyjna Unified State Exam 2019 – zadanie nr 2

Misza wypełnił tablicę prawdy funkcji (¬x /\ ¬y) \/ (y≡z) \/ ¬w, ale udało mu się wypełnić jedynie fragment trzech różnych linii, nie wskazując nawet, która kolumna tabeli odpowiada każdej ze zmiennych w, x,
y, z.

Określ, której kolumnie tabeli odpowiada każda zmienna w, x, y, z.
W swojej odpowiedzi wpisz litery w, 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.). Listy
W swojej odpowiedzi napisz wierszem; nie ma potrzeby wstawiania żadnych separatorów między literami.
Przykład. Gdyby funkcję podano wyrażeniem ¬x \/y w zależności od dwóch zmiennych, a fragment tabeli wyglądałby tak

wówczas pierwsza kolumna odpowiadałaby zmiennej y, a druga kolumna odpowiadałaby zmiennej x. Odpowiedź powinna być napisana yx.

(¬x ¬y)+(y≡z)+¬w=0

w=1 w musi być prawdziwe; w - ostatni

y i z muszą być różne, więc przed ostatnim jest x. pierwsze dwa to y i z lub z i y.

y i x nie mogą być jednocześnie fałszywe. Pierwszym jest z.

Odpowiedź: zyxw

Wersja demonstracyjna egzaminu Unified State Exam 2018 – zadanie nr 2

Funkcję logiczną F wyraża się wyrażeniem ¬x \/ y \/ (¬z /\ w). Na rysunku przedstawiono fragment tablicy prawdy funkcji F, zawierający wszystkie zbiory argumentów, dla których funkcja F jest fałszywa. Określ, która kolumna tabeli prawdy funkcji F odpowiada każdej ze zmiennych w, x, y, z

W swojej odpowiedzi wpisz litery w, 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 itp.) Wpisz litery w odpowiedzi z rzędu Nie ma potrzeby wstawiania żadnych separatorów między literami. Przykład. Jeżeli funkcję podano wyrażeniem ¬x\/y, w zależności od dwóch zmiennych: x i y, oraz podano fragment jej tablicy prawdy, zawierający wszystkie zbiory argumentów, dla których funkcja jest prawdziwa.

Wtedy pierwsza kolumna odpowiadałaby zmiennej y, a druga kolumna odpowiadałaby zmiennej x. Odpowiedź powinna być napisana: yx.

Odpowiedź: xzwy

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, itd.) Litery

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

nie ma potrzeby.

Wersja demonstracyjna egzaminu Unified State Exam 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 egzaminu Unified State Exam 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 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?

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?

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.

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

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:

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 wartość x5 odpowiada F = 4

Odpowiedź: 4

Podano fragment tablicy prawdy dla wyrażenia F:

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:

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 - tak samo jak F

1+0=1 - tak samo jak 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:

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

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