Логічна функція F задається виразом. Логіка та справжні набори
Джерело завдання: Рішення 2437. ЄДІ 2017. Інформатика. В.Р. Ліщинер. 10 варіантів.
Завдання 2.Логічна функція F задається виразом. Визначте, якому стовпцю таблиці істинності функції F відповідає кожна зі змінних x, y, z.
У відповіді напишіть літери x, y, z у тому порядку, в якому йдуть відповідні їм стовпці (спочатку - літера, що відповідає 1-му стовпцю, потім - літера, що відповідає 2-му стовпцю, потім - літера, що відповідає 3-му стовпцю) . Літери у відповіді пишіть поспіль, жодних роздільників між літерами ставити не потрібно.
Рішення.
Перепишемо вираз для F з урахуванням пріоритетів операцій заперечення, кон'юнкції та диз'юнкції:
.
Розглянемо 4-ту строчку таблиці (1,1,0)=0. Звідси видно, що у третьому місці має стояти або змінна y чи змінна z, інакше у другій дужці вийде 1, що призведе до значення F=1. Тепер розглянемо 5-й рядок таблиці (0,0,1) = 1. Так як на першому або другому місці повинна стояти x, то перша дужка дасть 1 тільки тоді, коли y стоятиме на 3-му місці. Враховуючи, що друга дужка завжди дорівнює 0, F=1 виходить завдяки 1 в першій дужці. Отже, отримали, що у 3-му місці стоїть y. Нарешті, розглянемо 7-му рядок таблиці (1,0,1)=0. Тут y = 1 і щоб F = 0 необхідно z = 0 і x = 1, отже, x стоїть на 1-му місці, а z - на другому.
Розбір 2 завдання ЄДІ 2017 з інформатики з проекту демоверсії. Це завдання базового рівня складності. Орієнтовний час виконання завдання 3 хвилини.
Перевірювані елементи змісту: вміння будувати таблиці істинності та логічні схеми. Елементи змісту, що перевіряються на ЄДІ: висловлювання, логічні операції, квантори, істинність висловлювання.
Завдання 2:
Логічна функція Fзадається виразом x /\¬ y /\ (¬ z \/ w).
На малюнку наведено фрагмент таблиці істинності функції F, що містить Усе Fістинна.
Визначте, якому стовпцю таблиці істинності функції Fвідповідає кожна зі змінних w, x, y, z.
У відповіді напишіть літери w, x, y, zв тому порядку, в якому йдуть відповідні їм стовпці (спочатку – буква, що відповідає першому стовпцю; потім – буква, що відповідає другому стовпцю, і т.д.).
приклад. Якби функція була задана виразом ¬ x \/ y, що залежать від двох змінних: xі y, і було наведено фрагмент її таблиці істинності, що містить Усенабори аргументів, за яких функція Fістинна.
Тоді першому стовпцю відповідала б змінна y, а другому стовпцю – змінна x. У відповіді слід написати: yx.
Відповідь: ________
x /\¬ y /\ (¬ z \/ w)
Кон'юнкція (логічне множення) істинна і тоді, коли істинні всі висловлювання. Отже змінної х 1 .
Таким чином, змінною xвідповідає стовпець зі змінною 3.
Змінною ¬yповинен відповідати той стовпець, у якому стоїть значення 0 .
Диз'юнкція (логічне додавання) двох висловлювань істинна і тоді, коли істинно хоча б одне висловлювання.
Диз'юнкція ¬z \/ wу даному рядку буде дійсна тільки якщо z=0, w=1.
Таким чином, змінною ¬zвідповідає стовпець зі змінною 1 (1 стовпець), змінною wвідповідає стовпець зі змінною 4 (4 стовпець).
Логічна функція Fзадається виразом x/\ ¬y/\ (¬z\/ w).
На малюнку наведено фрагмент таблиці істинності функції F, що містить Усенабори аргументів, за яких функція Fістинна.
Визначте, якому стовпцю таблиці істинності функції Fвідповідає кожна зі змінних w, x, y, z.
У відповіді напишіть літери w, x, y, zу тому порядку, в якому йдуть
відповідні їм стовпці (спочатку – літера, що відповідає першому
стовпцю; потім - літера, що відповідає другому стовпцю, і т.д.) Літери
у відповіді пишіть поспіль, ніяких роздільників між літерами ставити
не потрібно.
Демонстраційний варіант Єдиний державний іспит ЄДІ 2017 р. – завдання №2
Рішення:
Кон'юнкція (логічне множення) істинна і тоді, коли істинні всі висловлювання. Отже змінної х 1 .
Змінною ¬yповинен відповідати той стовпець, у якому всі значення дорівнюють 0 .
Диз'юнкція (логічне додавання) двох висловлювань істинна і тоді, коли істинно хоча б одне висловлювання.
Диз'юнкція ¬z \/ y z=0, w=1.
Таким чином, змінною ¬z wвідповідає стовпець зі змінною 4 (4 стовпець).
Відповідь: zyxw
Демонстраційний варіант Єдиний державний іспит ЄДІ 2016 р. – завдання №2
Логічна функція Fзадається виразом (¬z)/x/x/y. Визначте, якому стовпцю таблиці істинності функції F відповідає кожна зі змінних x, y, z.
У відповіді напишіть літери x, y, z у тому порядку, в якому йдуть відповідні їм стовпці (спочатку – літера, що відповідає 1-му стовпцю; потім – літера, що відповідає 2-му стовпцю; потім – літера, що відповідає 3-му стовпцю) . Літери у відповіді пишіть поспіль, жодних роздільників між літерами ставити не потрібно.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x і y, та таблиця істинності:
Тоді 1-му стовпцю відповідає змінна y, а 2-му стовпцю
відповідає змінна x. У відповіді слід написати: yx.
Рішення:
1. Запишемо за даний виразу більш простих позначеннях:
¬z*x + x*y = x*(¬z + y)
2. Кон'юнкція (логічне множення) істинна тоді і лише тоді, коли істинні всі висловлювання. Отже, щоб функція ( F) Дорівнювала одиниці ( 1 ), потрібно, щоб кожен множник був дорівнює одиниці (1 ). Таким чином, при F = 1, змінною хповинен відповідати той стовпець, у якому всі значення дорівнюють 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 y / z).
На малюнку наведено фрагмент таблиці істинності функції F, що містить усі набори аргументів, у яких функція F істинна. Визначте, якому стовпцю таблиці істинності функції F відповідає кожна змінна x, y, z.
У відповіді напишіть букви x, y, z у тому порядку, в якому йдуть відповідні їм стовпці (спочатку – буква, що відповідає першому стовпцю; потім – буква, що відповідає другому стовпцю, і т.д.). між літерами ставити не треба.
Р рішення:
Запишемо заданий вираз у більш простих позначеннях:
(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1
Це вираз істинно тоді, коли хоча б один з (x*y*z), (x*y*z), (x*yyz) дорівнює 1. Кон'юнкція (логічне множення) істинна тоді і тільки тоді, коли істинні всі висловлювання.
Хоча б одна з цих диз'юнкції x*y*¬z; x * y * z; x*¬y*¬zбуде істинна тільки якщо х = 1.
Таким чином, змінною хвідповідає стовпець зі змінною 2 (2 стовпець).
Нехай y-перем.1, z-прем.3. Тоді, у першому випадку x*¬y*¬zбуде істинна, у другому випадку x*y*¬z, а в третьому x*y*z.
Відповідь: yxz
Символом F позначено один із наведених нижче логічних виразів від трьох аргументів: X, Y, Z. Даний фрагмент таблиці істинності виразу F (див. таблицю справа). Який вираз відповідає 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
Рішення:
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?
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
Рішення:
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 (не відповідає на 2-му рядку)
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 (не відповідає на 1-му рядку)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (не відповідає на 1-му рядку)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1.0. …= 0 (не відповідає на 2-му рядку)
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 = й рядку)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x3... відповідає на 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)
Коли дорівнює 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, і даних з другого рядка, ми можемо зробити висновок, що в третьому стовпчику розташовується b.
Відповідь: cab
Логічна функція 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)
x. (¬y.z.w.y.z)
Виходячи з того, що при x=0, то F=0, ми можемо дійти невтішного висновку, що у другому стовпці розташовується x.
Відповідь: wxzy
Демонстраційний варіант ЄДІ 2019 – завдання № 2
Мишко заповнював таблицю істинності функції (¬x /\ ¬y) \/ (y≡z) \/ ¬w, але встиг заповнити лише фрагмент із трьох різних її рядків, навіть не вказавши, якому стовпцю таблиці відповідає кожна зі змінних w, x ,
y, z.
Визначте, якому стовпцю таблиці відповідає кожна змінна w, x, y, z.
У відповіді напишіть букви w, x, y, z у тому порядку, в якому йдуть відповідні їм стовпці (спочатку буква, що відповідає першому стовпцю; потім буква, що відповідає другому стовпцю, і т.д.). Літери
у відповіді пишіть поспіль, ніяких роздільників між літерами не потрібно ставити.
приклад. Якби функція була задана виразом x/y, що залежить від двох змінних, а фрагмент таблиці мав би вигляд
то першому стовпцю відповідала б змінна y, а другому стовпцю – змінна x. У відповіді слід написати yx.
(¬x ¬y)+(y≡z)+¬w=0
w=1 w має бути істинним; w - останній
y та z повинні бути різними, тому перед останнім це x. перші два y та z або z та y.
y і x не можуть бути хибними одночасно. перший - z.
Відповідь: zyxw
Демонстраційний варіант ЄДІ 2018 – завдання № 2
Логічна функція F задається виразом x/y//(z/w). На малюнку наведено фрагмент таблиці істинності функції F, що містить усі набори аргументів, у яких функція F хибна. Визначте, якому стовпцю таблиці істинності функції F відповідає кожна змінна w, x, y, z
У відповіді напишіть літери w, x, y, z у тому порядку, в якому йдуть відповідні їм стовпці (спочатку – літера, що відповідає першому стовпцю; потім – літера, що відповідає другому стовпцю, і т.д.) Літери у відповіді пишіть поспіль, ніяких роздільників між літерами не потрібно ставити. приклад. Якби функція була задана виразом x/y, що залежить від двох змінних: x і y, і був наведений фрагмент її таблиці істинності, що містить всі набори аргументів, при яких функція істинна.
Тоді першому стовпцю відповідала б змінна y, а другому стовпцю – змінна x. У відповіді слід написати: yx.
Відповідь: xzwy
Логічна функція Fзадається виразом x/\ ¬y/\ (¬z\/ w).
На малюнку наведено фрагмент таблиці істинності функції F, що містить Усенабори аргументів, за яких функція Fістинна.
Визначте, якому стовпцю таблиці істинності функції Fвідповідає кожна зі змінних w, x, y, z.
У відповіді напишіть літери w, x, y, zу тому порядку, в якому йдуть
відповідні їм стовпці (спочатку – літера, що відповідає першому
стовпцю; потім - літера, що відповідає другому стовпцю, і т.д.) Літери
у відповіді пишіть поспіль, ніяких роздільників між літерами ставити
не потрібно.
Демонстраційний варіант ЄДІ 2017 р. – завдання №2
Рішення:
Кон'юнкція (логічне множення) істинна і тоді, коли істинні всі висловлювання. Отже змінної х 1 .
Змінною ¬yповинен відповідати той стовпець, у якому всі значення дорівнюють 0 .
Диз'юнкція (логічне додавання) двох висловлювань істинна і тоді, коли істинно хоча б одне висловлювання.
Диз'юнкція ¬z \/ y z=0, w=1.
Таким чином, змінною ¬z wвідповідає стовпець зі змінною 4 (4 стовпець).
Відповідь: zyxw
Демонстраційний варіант ЄДІ 2016 р. – завдання №2
Логічна функція Fзадається виразом (¬z)/x/x/y. Визначте, якому стовпцю таблиці істинності функції F відповідає кожна зі змінних x, y, z.
У відповіді напишіть літери x, y, z у тому порядку, в якому йдуть відповідні їм стовпці (спочатку – літера, що відповідає 1-му стовпцю; потім – літера, що відповідає 2-му стовпцю; потім – літера, що відповідає 3-му стовпцю) . Літери у відповіді пишіть поспіль, жодних роздільників між літерами ставити не потрібно.
приклад. Нехай задано вираз x → y, що залежить від двох змінних x і y, та таблиця істинності:
Тоді 1-му стовпцю відповідає змінна y, а 2-му стовпцю
відповідає змінна x. У відповіді слід написати: yx.
Рішення:
1. Запишемо заданий вираз у більш простих позначеннях:
¬z*x + x*y = x*(¬z + y)
2. Кон'юнкція (логічне множення) істинна тоді і лише тоді, коли істинні всі висловлювання. Отже, щоб функція ( F) Дорівнювала одиниці ( 1 ), потрібно, щоб кожен множник дорівнював одиниці ( 1 ). Таким чином, при F = 1, змінною хповинен відповідати той стовпець, у якому всі значення дорівнюють 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 y / z).
На малюнку наведено фрагмент таблиці істинності функції F, що містить усі набори аргументів, у яких функція F істинна. Визначте, якому стовпцю таблиці істинності функції F відповідає кожна змінна x, y, z.
У відповіді напишіть букви x, y, z у тому порядку, в якому йдуть відповідні їм стовпці (спочатку – буква, що відповідає першому стовпцю; потім – буква, що відповідає другому стовпцю, і т.д.). між літерами ставити не треба.
Р рішення:
Запишемо заданий вираз у більш простих позначеннях:
(x*y*¬z) + (x*y*z) + (x*¬y*¬z)=1
Це вираз істинно тоді, коли хоча б один з (x*y*z), (x*y*z), (x*yyz) дорівнює 1. Кон'юнкція (логічне множення) істинна тоді і тільки тоді, коли істинні всі висловлювання.
Хоча б одна з цих диз'юнкції x*y*¬z; x * y * z; x*¬y*¬zбуде істинна тільки якщо х = 1.
Таким чином, змінною хвідповідає стовпець зі змінною 2 (2 стовпець).
Нехай y-перем.1, z-прем.3. Тоді, у першому випадку x*¬y*¬zбуде істинна, у другому випадку x*y*¬z, а в третьому x*y*z.
Відповідь: yxz
Символом F позначено один із наведених нижче логічних виразів від трьох аргументів: X, Y, Z. Даний фрагмент таблиці істинності виразу F (див. таблицю справа). Який вираз відповідає 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
Рішення:
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?
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
Рішення:
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 (не відповідає на 2-му рядку)
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 (не відповідає на 1-му рядку)
2) x1 ∨ ¬x2 ∨ x3 ∨ ¬x4 ∨ ¬x5 ∨ x6 ∨ x7 = 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1 (не відповідає на 1-му рядку)
3) x1 ∧ ¬x2 ∧ x3 ∧ ¬x4 ∧ x5 ∧ ¬x6 ∧ x7 = 1.0. …= 0 (не відповідає на 2-му рядку)
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 = й рядку)
4) ¬x1 ∨ ¬x2 ∨ ¬x3 ∨ ¬x4 ∨ ¬x5 ∨ ¬x6 ∨ ¬x7 ∨ ¬x8 = ¬x1 ∨ ¬x2 ∨ ¬x3... відповідає на 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?
Логічна функція 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)
Коли дорівнює 1, F дорівнює нулю так що останній стовпець c.
Щоб визначити перший і другий стовпці, ми можемо використовувати значення з 3-го ряду.
(a . 1) + (¬b . 1) = 0
Відповідь: abc
Логічна функція F задається виразом (a ∧ c)∨ (¬a ∧ (b ∨ ¬c)). Визначте, якому стовпцю таблиці істинності функції F відповідає кожна змінна a, b, c.
? | ? | ? | F | |
0 | 0 | 0 | 1 | |
0 | 0 | 1 | 1 | |
0 | 1 | 0 | 0 | |
0 | 1 | 1 | 0 | |
1 | 0 | 0 | 0 | |
1 | 0 | 1 | 1 | |
1 | 1 | 0 | 1 | |
0 | ||||
1 | 1 | 1 |
Виходячи з того, що при a = 0 і c = 0, то F = 0, і даних з другого рядка, ми можемо зробити висновок, що в третьому стовпчику розташовується b.
Відповідь: cab
Логічна функція 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)
x. (¬y.z.w.y.z)
Виходячи з того, що при x=0, то F=0, ми можемо дійти невтішного висновку, що у другому стовпці розташовується x.
Відповідь: wxzy
![mob_info](https://mapstr.ru/wp-content/themes/kuzov/pic/mob_info.png)