Каталог на работните места.
Брой програми със задължителен етап
Направете тест за тези задачи
Върнете се в каталога със задачи
Версия за печат и копиране в MS Word
Художник A16 преобразува записаното на екрана число.
Изпълнителят има три екипа, на които са присвоени номера:
1. Добавете 1
2. Добавете 2
3. Умножете по 2
Първият увеличава броя на екрана с 1, вторият го увеличава с 2, третият го умножава по 2.
Програмата за изпълнителя A16 е последователност от команди.
Колко програми съществуват, които преобразуват оригиналното число 3 в 12 и пътят за изчисляване на програмата съдържа числото 10?
Пътят за изчисляване на програмата е последователност от резултати от изпълнение на всички програмни команди. Например, за програма 132 с начален номер 7, траекторията ще се състои от числа 8, 16, 18.
Решение.
Необходимият брой програми е равен на произведението на броя на програмите, получаващи числото 10 от числото 3 на броя програми, получаващи числото 12 от числото 10.
Нека R (n) е броят на програмите, които преобразуват числото 3 в числото n, и P (n) броят на програмите, които преобразуват числото 10 в числото n.
За всички n> 5 са верни следните отношения:
1. Ако n не се дели на 2, тогава R (n) = R (n - 1) + R (n - 2), тъй като има два начина да се получи n - чрез добавяне на един или добавяне на два. По подобен начин P (n) = P (n - 1) + P (n - 2)
2. Ако n е делим на 2, тогава R (n) = R (n - 1) + R (n - 2) + R (n / 2). По същия начин P (n) = P (n - 1) + P (n - 2) + P (n / 2)
Нека последователно изчислим стойностите на 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
Сега нека изчислим стойностите на P (n):
P (11) = P (10) = 1
P (12) = P (11) + P (10) = 2
По този начин броят на програмите, които отговарят на условието на задачата, е 30 2 = 60.
Отговор: 60.
Отговор: 60
Източник: Демо версия на Единния държавен изпит-2017 по информатика.
1. Добавете 1
2. Добавете 3
Колко програми има, за които, като се има предвид първоначалното число 1, резултатът е числото 17 и изчислителната траектория съдържа числото 9? Пътят за изчисляване на програмата е последователност от резултати от изпълнение на всички програмни команди. Например, за програма 121 с начален номер 7, траекторията ще се състои от числа 8, 11, 12.
Решение.
Използваме метода за динамично програмиране. нека вземем масив dp, където dp [i] е броят начини за получаване на номера i с помощта на такива команди.
База на динамиката:
Преходна формула:
dp [i] = dp + dp
Това не взема предвид стойностите за числа по -големи от 9, които могат да бъдат получени от числа по -малки от 9 (като по този начин се пропуска траектория 9):
Отговор: 169.
Отговор: 169
Източник: Обучителна работа по ИНФОРМАТИКА 11 клас 29 ноември 2016 г. Вариант IN10203
Художник May17 преобразува числото на екрана.
Изпълнителят има два отбора, на които са присвоени номера:
1. Добавете 1
2. Добавете 3
Първата команда увеличава броя на екрана с 1, втората го увеличава с 3. Програмата за изпълнителя May17 е последователност от команди.
Колко програми има, за които, като се има предвид първоначалното число 1, резултатът е числото 15, а пътят на изчисление съдържа числото 8? Пътят за изчисляване на програмата е последователност от резултати от изпълнение на всички програмни команди. Например, за програма 121 с начален номер 7, траекторията ще се състои от числа 8, 11, 12.
Решение.
Използваме метода за динамично програмиране. Нека създадем масив dp, където dp [i] е броят начини за получаване на номера i с помощта на такива команди.
База на динамиката:
Преходна формула:
dp [i] = dp + dp
Но това не взема предвид такива числа, които са по -големи от 8, но можем да влезем в тях от стойност по -малка от 8. След това ще бъдат дадени стойностите в клетки dp от 1 до 15: 1 1 1 2 3 4 6 9 9 9 18 27 36 54 81 ...
Анализ на 2 задачи на изпита през 2017 г. по компютърни науки от демо проекта. Това е основно ниво на трудност. Очакваното време за изпълнение на задачата е 3 минути.
Тествани елементи на съдържанието: способност за изграждане на таблици на истината и логически диаграми. Елементи на съдържанието, тествани на изпита: изявления, логически операции, квантори, истинност на изявление.
Задание 2:
Логическа функция Fдадени от израза х /\¬ y /\ (¬ z \/ w).
Фигурата показва фрагмент от таблицата на истината на функцията Fсъдържащи всичко Fвярно.
Определете коя колона от таблицата на истината на функцията Fвсяка от променливите съответства w, х, y, z.
Напишете букви в отговора w, x, y, zв реда, в който се движат съответните колони (първо - буквата, съответстваща на първата колона; след това - буквата, съответстваща на втората колона и т.н.) Напишете буквите в отговора подред, не е нужно да поставяте никакви разделители между буквите.
Пример... Ако функцията се дава с израза ¬ х \/ yв зависимост от две променливи: хи y, и беше даден фрагмент от неговата таблица на истината, съдържащ всичконабори аргументи, за които функцията Fвярно.
Тогава първата колона ще съответства на променливата y, а втората колона е променливата х... Отговорът трябваше да бъде написан: yx.
Отговор: ________
х /\¬ y /\ (¬ z \/ w)
Съединението (логическо умножение) е вярно, ако и само ако всички твърдения са верни. Оттук и променливата NS 1 .
Значи променливата хсъответства на колоната с променлива 3.
Променлива ¬yколоната, съдържаща стойността, трябва да съвпада 0 .
Разделянето (логическото добавяне) на две твърдения е вярно, ако и само ако поне едно твърдение е вярно.
Разединение ¬z \ / wна даден ред ще бъде вярно само ако z = 0, w = 1.
Значи променливата ¬zсъответства на колона с променлива 1 (1 колона), променлива wсъответства на колона с променлива 4 (4 колона).
Логическа функция Fдадени от израза х/\ ¬y/\ (¬z\/ w).
Фигурата показва фрагмент от таблицата на истината на функцията Fсъдържащи всичконабори аргументи, за които функцията Fвярно.
Определете коя колона от таблицата на истината на функцията Fвсяка от променливите съответства w, х, y, z.
Напишете букви в отговора w, х, y, zв реда, в който вървят
съответните им колони (първа - буквата, съответстваща на първата
колона; след това - буквата, съответстваща на втората колона и т.н.) Букви
пишете подред в отговора, не поставяйте разделители между буквите
не е задължително.
Демонстрационна версия на Единния държавен изпит Единния държавен изпит 2017 - задача номер 2
Решение:
Съединението (логическо умножение) е вярно, ако и само ако всички твърдения са верни. Оттук и променливата NS 1 .
Променлива ¬yтрябва да съвпада с колоната, в която всички стойности са равни 0 .
Разделянето (логическото добавяне) на две твърдения е вярно, ако и само ако поне едно твърдение е вярно.
Разединение ¬z \ / y z = 0, w = 1.
Значи променливата ¬z wсъответства на колона с променлива 4 (4 колона).
Отговор: zyxw
Демонстрационна версия на Единния държавен изпит Unified State Examination 2016 - задача номер 2
Логическа функция Fсе дава от израза (¬z) / \ x \ / x / \ y. Определете коя колона от таблицата на истината на функцията F отговаря на всяка от променливите x, y, z.
В отговора напишете буквите x, y, z в реда, в който се движат съответните колони (първо - буквата, съответстваща на 1 -ва колона; след това - буквата, съответстваща на 2 -ра колона; след това - буквата, съответстваща на 3 -та колона) ... Напишете буквите подред в отговора; не е необходимо да поставяте разделители между буквите.
Пример... Нека бъде даден израз x → y, в зависимост от две променливи x и y, и таблица за истинност:
Тогава първата колона съответства на променливата y, а втората колона
променливата x съответства. В отговора трябва да напишете: yx.
Решение:
1. Нека напишем дадения израз в по -проста нотация:
¬z * x + x * y = x * (¬z + y)
2. Съединението (логическо умножение) е вярно, ако и само ако всички твърдения са верни. Следователно за функцията ( F) е равно на едно ( 1 ), е необходимо всеки фактор да е равен на един ( 1 ). По този начин, за F = 1, променлива NSтрябва да съвпада с колоната, в която всички стойности са равни 1 .
3. Помислете (¬z + y), в F = 1този израз също е равен на 1 (виж точка 2).
4. Разделянето (логическото добавяне) на две твърдения е вярно, ако и само ако поне едно твърдение е вярно.
Разединение ¬z \ / yна даден ред ще бъде вярно само ако
- z = 0; y = 0или y = 1;
- z = 1; y = 1
5. По този начин променливата ¬zсъответства на колона с променлива 1 (1 колона), променлива y
Отговор: zyx
Единен държавен изпит на КИМ Единен държавен изпит 2016 (ранен период)- задача номер 2
Логическата функция F се дава от израза
(x / \ y / \ ¬z) \ / (x / \ y / \ z) \ / (x / \ ¬y / \ ¬z).
Фигурата показва фрагмент от таблицата на истината на функцията F, съдържаща всички набори аргументи, за които функцията F е вярна. Определете коя колона от таблицата на истината на функцията F отговаря на всяка от променливите x, y, z.
В отговора напишете буквите x, y, z в реда, в който се движат съответните колони (първо - буквата, съответстваща на първата колона; след това - буквата, съответстваща на втората колона и т.н.) Напишете буквите в отговор подред, без разделители няма нужда да се поставя между букви.
R решение:
Нека напишем дадения израз в по -проста нотация:
(x * y * ¬z) + (x * y * z) + (x * ¬y * ¬z) = 1
Този израз е верен, ако поне един от (x * y * ¬z), (x * y * z), (x * ¬y * ¬z) е равен на 1. Съединението (логическо умножение) е вярно, ако и само ако когато всички твърдения са верни.
Поне едно от тези разединения x * y * ¬z; x * y * z; x * ¬y * ¬zще бъде вярно само ако x = 1.
Значи променливата NSсъответства на колона с променлива 2 (колона 2).
Нека бъде y-променлива 1, z- 3. След това, в първия случай x * ¬y * ¬zще бъде вярно, във втория случай x * y * ¬zа в третия x * y * z.
Отговор: yxz
Символ F означава един от следните логически изрази от три аргумента: X, Y, Z. Даден е фрагмент от таблицата на истината на израз F (виж таблицата вдясно). Кой израз съвпада с F?
| х | 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
Решение:
1) X ∧ Y ∧ Z = 1.0.1 = 0 (не съответства на 2 -ри ред)
2) ¬X ∨ Y ∨¬Z = ¬0 ∨ 0 ∨ ¬0 = 1 + 0 + 1 = 1 (не съответства на 1 -ви ред)
3) X ∧ Y ∨ Z = 0,1 + 0 = 0 (не съответства на 3 -ти ред)
4) X ∨ Y ∧ ¬Z (съответства на 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
Отговор: 4
Даден е фрагмент от таблицата на истината на израза F. Кой израз съответства на F?
| А | Б | ° С | 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
Решение:
1) (A → ¬B) ∨ C = (1 → ¬0) ∨ 0 = (1 → 1) + 0 = 1 + 0 = 1 (не съответства на 2 -ри ред)
2) (¬A ∨ B) ∧ C = (¬1 ∨ 0) ∧ 1 = (0 + 0) .1 = 0 (не съответства на 3 -ти ред)
3) (A ∧ B) → C = (1 ∧ 0) → 0 = 0 → 0 = 1 (не съответства на втория ред)
4) (A ∨ B) → C (съответства на F)
(A ∨ B) → C = (0 ∨ 1) → 1 = 1
(A ∨ B) → C = (1 ∨ 0) → 0 = 0
(A ∨ B) → C = (1 ∨ 0) → 1 = 1
Отговор: 4
Даден е логически израз, който зависи от 6 логически променливи:
X1 ∨ ¬X2 ∨ X3 ∨ ¬X4 ∨ X5 ∨ X6
Колко различни набора от стойности на променливи има, за които изразът е верен?
1) 1 2) 2 3) 63 4) 64
Решение:
Фалшив израз само в 1 случай: 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
Има общо 2 6 = 64 опции, което означава вярно
Отговор: 63
Даден е фрагмент от таблицата на истината на израз 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 |
Кой израз съвпада с 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
Решение:
1) x1 ∨ x2 ∨ ¬x3 ∨ x4 ∨ ¬x5 ∨ x6 ∨ ¬x7 = 0 + 1 +… = 1 (не съответства на първия ред)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (не съответства на първия ред)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1,0. ... = 0 (не съответства на втория ред)
4) x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ ¬x5 ∧ x6 ∧ ¬x7 (съответства на 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
Отговор: 4
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | F |
| 0 | 1 | 1 | ||||||
| 1 | 0 | 1 | 0 | |||||
| 1 | 0 | 1 |
Какъв израз може да бъде 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
Решение:
1) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ x6 ∧ ¬x7 ∧ ¬x8 = x1. ¬x2. 0. ... = 0 (не съвпада на 1 -ви ред)
2) ¬x1 ∨ x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ x8 (съответства на F)
3) ¬x1 ∧ x2 ∧ ¬x3 ∧ x4 ∧ x5 ∧ ¬x6 ∧ ¬x7 ∧ ¬x8 =… ¬x7 ∧ ¬x8 =… ¬1 ∧ ¬x8 =… 0 ∧ ¬x8 = 0 (не съответства на 1 - ти ред)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x3… = ¬1 ∨ ¬x2 ∨ ¬0 .. = 1 (не мачове на 2 -ри ред)
Отговор: 2
Даден е фрагмент от таблицата на истината за израза 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 |
Посочете минималния възможен брой отделни редове в пълната таблица на истинността на този израз, където x5 е същото като F.
Решение:
Минимално възможен брой отделни линии, където x5 съвпада с F = 4
Отговор: 4
Даден е фрагмент от таблицата на истината за израза 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 |
Посочете максималния възможен брой отделни редове в пълната таблица на истинността на този израз, където x6 не съвпада с F.
Решение:
Максимално възможно число = 2 8 = 256
Максимално възможен брой отделни редове, където x6 не съвпада с F = 256 - 5 = 251
Отговор: 251
Даден е фрагмент от таблицата на истината за израза 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 |
Посочете максималния възможен брой отделни редове от пълната таблица на истинността на този израз, в който стойността ¬x5 ∨ x1 е същата като F.
Решение:
1 + 0 = 1 - не съвпада с F
0 + 0 = 0 - не съвпада с F
0 + 0 = 0 - не съвпада с F
0 + 1 = 1 - съвпада с F
1 + 0 = 1 - съвпада с F
2 7 = 128 – 3 = 125
Отговор: 125
Всеки булев израз A и B зависи от един и същи набор от 6 променливи. В таблиците на истината на всеки от тези изрази има точно 4 единици в колоната със стойности. Какъв е минималният възможен брой такива в колоната със стойности на таблицата за истинност на израза A ∨ B?
Решение:
Отговор: 4
Всеки булев израз A и B зависи от един и същи набор от 7 променливи. В таблиците на истината на всеки от тези изрази има точно 4 единици в колоната със стойности. Какъв е максималният възможен брой такива в колоната със стойности в таблицата на истината на израза A ∨ B?
Решение:
Отговор: 8
Всеки булев израз A и B зависи от един и същи набор от 8 променливи. В таблиците на истината на всеки от тези изрази има точно 5 единици в колоната със стойности. Какъв е минималният възможен брой нули в колоната със стойности в таблицата на истината на израза A ∧ B?
Решение:
2 8 = 256 – 5 = 251
Отговор: 251
Всеки булев израз A и B зависи от един и същи набор от 8 променливи. В таблиците на истината на всеки от тези изрази има точно 6 единици в колоната със стойности. Какъв е максималният възможен брой нули в колоната със стойности в таблицата на истината на израза A ∧ B?
Решение:
Отговор: 256
Булевите изрази A и B зависят всеки от един и същи набор от 5 променливи. Няма съвпадащи редове в таблиците на истината и на двата израза. Колко такива ще се съдържат в колоната със стойности в таблицата на истината на израза A ∧ B?
Решение:
Няма съвпадащи редове в таблиците на истината и на двата израза.
Отговор: 0
Булевите изрази A и B зависят всеки от един и същи набор от 6 променливи. Няма съответстващи редове в таблиците на истината и на двата израза. Колко такива ще се съдържат в колоната със стойности в таблицата на истината на израза A ∨ B?
Решение:
Отговор: 64
Булевите изрази A и B зависят всеки от един и същи набор от 7 променливи. Няма съвпадащи редове в таблиците на истината и на двата израза. Какъв е максималният възможен брой нули в колоната със стойности в таблицата на истината на израза ¬A ∨ B?
Решение:
A = 1, B = 0 => ¬0 ∨ 0 = 0 + 0 = 0
Отговор: 128
Всеки от логическите изрази F и G съдържа 7 променливи. В таблиците за истинност на изрази F и G има точно 8 еднакви реда, а точно 5 от тях в колоната със стойности имат 1. Колко реда от таблицата на истината за израза F ∨ G съдържа 1 в колоната със стойности?
Решение:
Има точно 8 еднакви реда и точно 5 от тях имат 1 в колоната със стойности.
Това означава, че точно 3 от тях имат 0 в колоната със стойности.
Отговор: 125
Логическата функция F е дадена с израза (a ∧ ¬c) ∨ (¬b ∧ ¬c). Определете коя колона от таблицата на истината на функцията F отговаря на всяка от променливите 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 |
В отговора напишете буквите a, b, c в реда, в който се появяват съответните колони.
Решение:
(a. ¬c) + (¬b. ¬c)
Когато c е 1, F е нула, така че последната колона е c.
За да определим първата и втората колони, можем да използваме стойностите от 3 -ти ред.
(a. 1) + (¬b. 1) = 0
Отговор: abc
Логическата функция F е дадена с израза (a ∧ c) ∨ (¬a ∧ (b ∨ ¬c)). Определете коя колона от таблицата на истината на функцията F отговаря на всяка от променливите a, b, c.
Въз основа на факта, че за a = 0 и c = 0, тогава F = 0 и данните от втория ред, можем да заключим, че третата колона съдържа б.
Отговор: такси
Логическата функция F е дадена от x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z). Фигурата показва фрагмент от таблицата на истината на функцията F, съдържаща всички набори аргументи, за които функцията F е вярна. Определете коя колона от таблицата на истината на функцията F отговаря на всяка от променливите x, y, z, w.
| ? | ? | ? | ? | F |
| 0 | 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 1 | 0 | 1 | 1 |
В отговора напишете буквите x, y, z, w в реда, в който се появяват съответните колони.
Решение:
x ∧ (¬y ∧ z ∧ ¬w ∨ y ∧ ¬z)
х. (¬y. Z. ¬w. Y. ¬z)
Въз основа на факта, че при x = 0, тогава F = 0, можем да заключим, че втората колона съдържа х.
Отговор: wxzy
Нека първо да определим какво имаме в задачата:
- логическа функция F, дадена от някакъв израз. Елементите на таблицата на истината на тази функция също са представени в задачата под формата на таблица. По този начин, когато замествате конкретни стойности на x, y, z от таблицата в израза, резултатът трябва да съвпада с този, даден в таблицата (вижте обяснението по -долу).
- Променливите x, y, z и трите колони, които им съответстват. Освен това в този проблем не знаем коя колона съответства на коя променлива. Тоест във Var. 1 може да бъде или x или y или z.
- От нас се иска само да определим коя колона съответства на коя променлива.
Нека разгледаме един пример.
Решение
- Нека се върнем към решението сега. Нека разгледаме отблизо формулата: \ ((\ neg z) \ клин x \ vee x \ клин y \)
- Той има две конюнктурни конструкции, свързани чрез дизъюнкция. Както знаете, най -често разединението е вярно (за това е достатъчно един от условията да е истина).
- Нека разгледаме по -отблизо редовете, в които изразът F е невярен.
- Първият ред не ни е интересен, тъй като не може да се определи къде се намира (всички стойности са еднакви).
- Помислете тогава за предпоследния ред, той съдържа най -вече 1, но резултатът е 0.
- Може ли z да е в третата колона? Не, тъй като в този случай формулата ще съдържа 1 навсякъде и следователно резултатът ще бъде равен на 1, но според таблицата на истината стойността на F в този ред е 0. Следователно z не може да бъде Var. 3.
- По същия начин за предишния ред имаме, че z не може да бъде Var. 2.
- Следователно, z е Var. 1.
- Знаейки, че z е в първата колона, помислете за третия ред. Може ли x да е във втората колона? Заменете стойностите:
\ ((\ neg z) \ клин x \ vee x \ клин y = \\ = (\ neg 0) \ клин 1 \ vee 1 \ клин 0 = \\ = 1 \ клин 1 \ vee 0 = \\ = 1 \ vee 0 = 1 \) - Въпреки това, според таблицата на истината, резултатът трябва да бъде 0.
- Следователно, x не може да бъде Var. 2.
- Следователно, x е Var. 3.
- Следователно, чрез метода на елиминиране, y е Var. 2.
- Така отговорът е следният: zyx (z - Var. 1, y - Var. 2, x - Var. 3).
