Головна
Системи безпеки
Вирішу його інформатика завдання 18 номер.

Вирішу його інформатика завдання 18 номер.

Для вирішення цього завдання нам потрібно зробити кілька логічних висновків, тому "стежте за руками".

  1. Від нас хочуть, щоб ми знайшли мінімальне ціле невід'ємне А, при якому вираз завжди є істинним.
  2. Що являє собою вираз загалом? Щось там імплікаціящось там у дужках.
  3. Згадаймо таблицю істинності для імплікації:
    1 => 1 = 1
    1 => 0 = 0
    0 => 1 = 1
    0 => 0 = 1
  4. Отже, можливі три варіанти, коли це буде істинно. Розглядати всі ці три варіанти – це вбитись і не жити. Давайте подумаємо, чи можемо ми піти "від неприємного".
  5. Давайте замість шукати А, спробуємо знайти x, у якому цей вираз хибно.
  6. Тобто візьмемо деяке число А (поки не знаємо якесь, просто якесь). Якщо раптом ми знайдемо таке x, при якому все висловлювання хибне, значить, обране А - погане (бо в умові потрібно, щоб вираз завжди був істинним)!
  7. Таким чином, ми зможемо отримати якісь обмеження на число А.
  8. Отже, давайте підемо від неприємного і згадаємо, коли імплікація буває хибною? Коли перша частина істинна, а друга - хибна.
  9. Значить
    \((\mathrm(x)\&25\neq 0)= 1 \\ (\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
  10. Що означає, що ((x \ 25 \ neq 0) = 1 \)? Це означає, що дійсно \(\mathrm(x)\&25\neq 0\) .
  11. Давайте переведемо 25 у двійкову. Отримаємо: 11001 2 .
  12. Які обмеження накладає на x? Якщо не дорівнює нулю, значить, при порозрядній кон'юнкції має десь вийти одиниця. Але де вона може бути? Тільки там, де о 25 вже є одиниця!
  13. Отже, серед x хоча б у одному хресті має бути одиниця: XX**X.
  14. Відмінно, тепер розглянемо другий множник: \((\mathrm(x)\&17=0\Rightarrow \mathrm(x)\&\mathrm(A)\neq 0) = 0\)
  15. Цей вираз із себе також представляє імплікацію. При цьому воно так само хибне.
  16. Отже, його частина повинна бути істинною, а друга — хибною.
  17. Значить
    \((\mathrm(x)\&17=0) = 1 \\ ((\mathrm(x)\&\mathrm(A)\neq 0) = 0) = 0\)
  18. Що означає, що \(\mathrm(x)\&17=0\)? Те, що на всіх місцях, де в 17 стоять одиниці, в х повинні стояти нулі (інакше в результаті не вийде 0).
  19. Переведемо 17 до двійкової: 10001 2 . Значить, у x на останньому з кінця та на 5 з кінця місці повинні стояти нулі.
  20. Але стоп, ми ж у пункті 13 отримали, що на останньому АБОна 4 з кінця АБОна 5 з кінця має бути одиниця.
  21. Якщо згідно з рядком 19 на останньому або 5 з кінця місцях одиниці бути не може, значить, вона мусить бутина 4 з кінця місці.
  22. Тобто, якщо хочемо, що з нашому x весь вираз було хибним, на 4 з кінця місці має стояти одиниця: XX...XX1XXX 2 .
  23. Добре, розглянемо тепер останню умову: \((\mathrm(x)\&\mathrm(A)\neq 0) = 0\). Що це означає?
  24. Це означає, що не так, що \(\mathrm(x)\&\mathrm(A)\neq 0\).
  25. Тобто насправді \(\mathrm(x)\&\mathrm(A)=0\) .
  26. Що ми знаємо про x? Що на 4 з кінця місці є там одиниця. У решті х може бути практично будь-яким.
  27. Якщо ми хочемо, щоб вихідний вираз за умови завдання був завжди істинним, ми не повинні знайтих, який би задовольняв усі умови. Адже, дійсно, якби ми знайшли такий x, вийшло б, що вихідний вираз не завжди є істинним, що суперечить умові завдання.
  28. Отже, ось ця остання умова просто має виконуватися.
  29. А як воно може виконуватися? Якщо тільки ми будемо впевнені на 100%, то при порозрядній кон'юнкції десь залишиться одиниця.
  30. І це можливо: якщо А також на 4 місці з кінця буде одиниця, то в результаті порозрядної кон'юнкції на 4 з кінця місці залишиться одиниця.
  31. Яке мінімально можливе двійкове число має одиницю на 4 з кінця місці? Очевидно, що 1000 2 . Значить, це число буде відповіддю.
  32. Залишилося тільки перевести його в десяткову: \(1000_2=0\times 2^0 + 0\times 2^1 + 0\times 2^2 + 1\times 2^3=8\)

Відповідь: мінімально можливе A, що відповідає умовам, одно 8.

Євген Смирнов

Експерт в IT, вчитель інформатики

Рішення №2

Можна запропонувати трохи коротший підхід. Позначимо наше висловлювання як F = (A->(B->C)), де А - це висловлювання "Х&25 не дорівнює 0", = "Х&17=0" і C="X&A не дорівнює 0".

Розкриємо імплікації, користуючись відомим законом X->Y = не(Х) АБО Y, отримаємо F = A -> (не(В) АБО C) = не(А) АБО не(B) АБО С. Розпишемо також двійкові значення констант 25 та 17:

Наш вислів - логічний АБО від трьох висловлювань:

1) не(А) - це означає, X&25 = 0 (біти 0,3,4 числа Х усі рівні 0)

2) не(B) - значить, X&17 не дорівнює 0 (біти 0 і 4 числа Х хоча б один дорівнює 1)

3) C - знає, X&A не дорівнює 0 (біти, що задаються маскою A, хоча б 1 дорівнює 1)

Х – довільне число. Усі його біти незалежні. Тому вимагати виконання якоїсь умови на біти довільного числа можна тільки в одному випадку - коли мова йде про одну і ту ж маску (набір бітів). Ми можемо помітити, що двійкова маска 17 - майже те саме, що і 25, тільки не вистачає біта номер 3. Ось якби доповнити 17 бітом номер 3, то вираз (не(В) АБО С) перетворився б на не(неА ), тобто. в А = (X&25 не дорівнює 0). Інакше: припустимо, А=8 (біт 3=1). Тоді вимога (не(В) B або С) рівносильна вимогі: (Хоча один з бітів 4,0 дорівнює 1) АБО (біт 3 дорівнює 1) = (хоча б один з бітів 0,3,4 не дорівнює 1) - тобто. інверсія не(А) = А = (Х&25 не дорівнює 0).

У результаті ми помітили, що якщо А = 8, то наш вираз набуває вигляду F = не (А) АБО А, що, за законом виключеного третього, завжди тотожно істинно. При інших, менших, значеннях А незалежність значення Х отримати не вдається, т.к. маски виходять різні. Ну, а за наявності у старших бітах А одиниць у бітах вище 4 нічого не змінюється, т.к. в решті масок у нас нулі. Виходить, що тільки за А=8 формула перетворюється на тавтологію для довільного Х.

Дмитро Лісін

Завдання 18 Каталог завдань. Логічні висловлювання

1. Завдання 18 №701. Для якого імені хибне висловлювання:

(Перша буква імені голосна→ Четверта буква імені приголосна).

1) ОЛЕНА

2) ВАДИМ

3) АНТОН

4) ФЕДІР

Пояснення.

Імплікація хибна тоді і тільки тоді, коли посилка істинна, а слідство хибне. У нашому випадку - якщо перша буква імені голосна і четверта буква голосна. Цій умові задовольняє ім'я Антон.

Примітка.

Той самий результат випливає з таких перетворень: ¬ (A→ B) = ¬ (¬ A∨ B) = A∧ (¬ B).

Правильна відповідь вказана за номером 3.

2. Завдання 18 №8666. На числовій прямій дано два відрізки: P = і Q = . Вкажіть максимальну довжину проміжку A, для якого формула

(¬ (xA)→ (xP))→ ((xA)→ (xQ))

тотожно істинна, тобто набуває значення 1 при будь-якому значенні змінної х.

Пояснення.

Перетворимо цей вираз:

(¬ ( xA) → ( x P)) → (( x A) → ( xQ))

((xA)∨ (x P))→ ((x не A)∨ (x Q))

¬(( xпринадлA) ∨ ( xпринадлP)) ∨ (( x не належатьA) ∨ ( x принадлQ))

( xне належатьA) ∧ ( xне належатьP) ∨ ( x принадлA) ∨ ( x не належатьQ)

( xне належатьA) ∨ ( x принадлQ)

Таким чином, або x повинен належати Q, або не належати A. Це означає, що для досягнення істинності для всіх x необхідно, щоб A повністю містився в Q. Тоді максимум, яким він зможе стати, це всім Q, тобто довжиною 15 .

3. Завдання 18 № 9170. На числовій прямій дано два відрізки: P = і Q = .

Вкажіть максимальну довжину відрізка A, для якого формула

((xA)→ ¬(xP))→ ((xA)→ (xQ))

тотожно істинна, тобто набуває значення 1 при будь-якому значенні змінноїх .

Пояснення.

Перетворимо цей вираз.

(( x€ A) → ¬( xпринадлP)) → (( x принадлA) → ( x принадлQ))

(( xне належатьA) ∨ ( xне належатьP)) → (( x не належатьA) ∨ ( x принадлQ))

¬((x не належать A)∨ (xне належать P))∨ ((xне належать A)∨ (xпринадл Q))

Правильно, що A∧ B∨ ¬A = ¬A∨ B. Застосуємо це тут, отримаємо:

(x принадл P)∨ (xне належать A)∨ (x належ Q)

Тобто або точка повинна належати Q, або належати P, або не належати А. Це означає, що А може покривати всі точки, які покривають P і Q. Тобто A = P Q = =. |A| = 48 – 10 = 38.

4. Завдання 18 № 9202. Елементами множин А, P, Q є натуральні числа, причому P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (3, 6, 9, 12, 15, 18) , 21, 24, 27, 30).

Відомо, що вираз

((xA)→ (xP))∨ (¬(xQ)→ ¬(xA))

істинно (тобто приймає значення 1) за будь-якого значення змінної х.

5. Завдання 18 № 9310. Елементами множин А, P, Q є натуральні числа, причому P = (2, 4, 6, 8, 10, 12, 14, 16, 18, 20), Q = (5, 10, 15, 20, 25, 30) 35, 40, 45, 50).

Відомо, що вираз

((xA)→ (xP))∨ (¬(xQ)→ ¬(xA))

істинно (тобто приймає значення 1) за будь-якого значення змінної х.

Визначте найбільш можливу кількість елементів у множині A.

6. Завдання 18 № 9321. Позначимо черезСПРАВ ( n, m ) затвердження «натуральне число n ділиться без залишку на натуральне числоm ». Для якого найбільшого натурального числаА формула

¬ СПРАВ ( x, А ) → (¬ СПРАВ ( x , 21) ∧ ¬ СПРАВ ( x , 35))

тотожно істинна (тобто набуває значення 1 за будь-якого натурального значення змінноїx )?

(Завдання М. В. Кузнєцової)

7. Завдання 18 № 9768. Позначимо через m & n m і n 2 & 0101 2 = 0100 2 А формула

x & 29 ≠ 0 → (x & 12 = 0 → x & А ≠ 0)

тотожно істинна (тобто набуває значення 1 при будь-якому невід'ємному цілому значенні змінної х )?

8. Завдання 18 №9804. Позначимо через m & n порозрядну кон'юнкцію невід'ємних цілих чисел m і n . Так, наприклад, 14 & 5 = 1110 2 & 0101 2 = 0100 2 = 4. Для якого найменшого невід'ємного цілого числа А формула

x & 29 ≠ 0 → (x & 17 = 0 → x & А ≠ 0)

тотожно істинна (тобто приймає значення 1 при будь-якому невід'ємному цілому значенні змінної x )?

9. Завдання 18 №723. Для якого імені істинно висловлювання:

Третя буква голосна→ ¬ (Перша буква згодна \/ У слові 4 голосних букви)?

1) Римма

2) Анатолій

3) Світлана

4) Дмитро

Пояснення.

Застосуємо перетворення імплікації:

Третя буква Згодна∨ (Перша літера Голосна∧ У слові НЕ 4 голосних літери)

Диз'юнкція є істинною, коли істинно хоча б одне висловлювання. Отже, підходить лише варіант 1.

10. Завдання 18 №4581. Яке з наведених імен задовольняє логічну умову:

(перша буква згодна→ остання буква приголосна) /\ (перша буква голосна→ остання буква голосна)?

Якщо таких слів кілька, вкажіть найдовше з них.

1) ГАННА

2) БЕЛЛА

3) АНТОН

4) БОРИС

Пояснення.

Логічне І істинно тільки тоді, коли істинні обидва твердження.

Імплікація хибна тільки тоді, коли з істини випливає брехня. (2)

Варіант 1 підходить за всіма умовами.

Варіант 2 не підходить через умови (2).

Варіант 3 не підходить через умови (2).

Варіант 4 підходить за всіма умовами.

Необхідно вказати найдовше зі слів, отже, відповідь 4.

Завдання для самостійного вирішення

1. Завдання 18 №711. Яка з наведених назв країн задовольняє наступну логічну умову: ((остання буква згодна) \/ (перша буква згодна))→ (назва містить букву «п»)?

1) Бразилія

2) Мексика

3) Аргентина

4) Куба

2. Завдання 18 №709. Яке з наведених імен задовольняє логічну умову:

(Перша буква голосна)∧ ((Четверта буква згодна)∨ (В слові чотири літери))?

1) Сергій

2) Вадим

3) Антон

4) Ілля

№3

№4

№5. Завдання 18 №736. Яке з наведених імен задовольняє логічну умову

Перша буква голосна∧ Четверта буква згодна∨ У слові чотири літери?

1) Сергій

2) Вадим

3) Антон

4) Ілля

вчитель інформатики МБОУ «Ліцей»

першої кваліфікаційної категорії

Мурзіна Ольга Іванівна

МБОУ «Ліцей» м. Арзамас

Теорія та практика вирішення завдання 18 ЄДІ з інформатики

Арзамас, 2017

Мнемонічне правило

Один із її головних принципів – доповнення до цілого (доповнення протилежністю)

Соціоніка – це інформаційна психологія

Вирішальна формула

В алгебрі логіки є формула доповнення до цілого:

У деяких завданнях ми використовуватимемо замість цієї формули множення протилежностей:

Типи завдання 18

  • Завдання на відрізки
  • Завдання на множини
  • Завдання на порозрядну кон'юнкцію
  • Завдання на умову подільності

Завдання на відрізки

(№ 376) На числовій прямій дано два відрізки: P= і Q=. Вкажіть найменшу можливу довжину такого відрізка A, що формула ((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A)

тотожно істинна, тобто набуває значення 1 при будь-якому значенні змінної х.

Вирішальна формула

приймає значення 1 за будь-якого значення змінної х.

Розв'язання задачі на відрізки

  • Легенда
  • Формалізація умови
  • Розв'язання логічного рівняння

Розділимо розв'язання задачі на етапи:

Розв'язання задачі на відрізки

  • Легенда– це зручні нам умовні позначення, які ми будемо використовувати під час вирішення.

    • Введемо такі позначення:

Розв'язання задачі на відрізки

2) Формалізація умови– перепишемо формулу з умови завдання у відповідність до легенди.

((x ∈ P) ∧ (x ∈ Q)) → (x ∈ A) = 1

(P ∧ Q) → A = 1

Розв'язання задачі на відрізки

3) Рішення логічного рівняння –Спочатку це, можливо, найскладніший етап у розв'язанні задачі. Але пізніше, при накопиченні досвіду, він уже не здаватиметься таким вже складним 

Розглянемо рішення логічного рівняння кроками.

Розв'язання задачі на відрізки

3.1. Представимо логічне проходження в базових логічних операціях за формулою: А → В = ¬А  В:

(P ∧ Q) → A = 1

¬(P ∧ Q)  A = 1

Розв'язання задачі на відрізки

А  ¬А = 1 (в алгебрі логіки справедливий закон комутативності, тобто А  ¬А = ¬А  А) :

¬(P ∧ Q)  A = 1, звідси

¬А = ¬(P ∧ Q)

Відповіддю в логічному рівнянні буде:

Розв'язання задачі на відрізки

.

Наша відповідь: А = P ∧ Q.

У алгебрі логіки цей вислів означає перетин обсягів двох логічних об'єктів. За умовою нашого завдання – це перетин відрізків P та Q.

Розв'язання задачі на відрізки

Перетин відрізків P та Q можна візуалізувати: P= та Q=.

За умовою нашого завдання нам потрібна мінімальна довжина відрізка А. Знаходимо її: 15 – 12 = 3.

Відповідь на сайті Полякова К.Ю.: 3

Завдання на відрізки

(№ 360) На числовій прямій дано три відрізки: P=, Q= та R=. Яка максимальна довжина відрізка A, при якому формула ((x ∈ Q) → (x ∉ R)) ∧ (x ∈ A) ∧ (x ∉ P)

тотожно хибна, тобто набуває значення 0 при будь-якому значенні змінної х?

Джерело - сайт Полякова К.Ю.

Вирішальна формула

Для вибору вирішальної формули важливо уважно прочитати вимогу завдання.

У нашій задачі у вимогі сказано:

приймає значення 0 за будь-якого значення змінної х.

Вибір вирішальної формули очевидний:

Розв'язання задачі на відрізки

  • Легенда
  • Формалізація умови
  • Розв'язання логічного рівняння
  • Інтерпретація отриманого результату

Розв'язання задачі на відрізки

  • Легенда

Розв'язання задачі на відрізки

2) Формалізація умови

((x ∈ Q) → (x ∉ R)) ∧ (x ∈ A) ∧ (x ∉ P) = 0

(Q → ¬R) ∧ A ∧ ¬ P = 0

Розв'язання задачі на відрізки

(Q → ¬R) ∧ A ∧ ¬ P = 0

3.1. Представимо логічне проходження в базових логічних операціях за формулою: А → В = ¬А  В, і переставимо множники згідно із законом комутативності множення:

A ∧ (¬ Q  ¬R) ∧ ¬ P = 0

Розв'язання задачі на відрізки

3) Розв'язання логічного рівняння

A ∧ (¬ Q  ¬R) ∧ ¬ P = 0

3.2. Зведемо вираз до вирішальної формули: А  ¬А = 0 і знайдемо, чому дорівнює ¬А:

¬А = (¬ Q  ¬R) ∧ ¬ P

Розв'язання задачі на відрізки

3) Розв'язання логічного рівняння

¬А = (¬ Q  ¬R) ∧ ¬ P

3.3. Спростимо вираз для ¬А згідно із законом де Моргана ¬А¬В=¬(АВ):

¬А = ¬ (Q  R) ∧ ¬ P,

і за іншим законом де Моргана ¬А¬В=¬(АВ):

¬А = ¬ (Q  R  P)

Розв'язання задачі на відрізки

3) Розв'язання логічного рівняння

¬А = ¬ (Q  R  P)

3.4. Очевидно, що

А = Q  R  P

Розв'язання задачі на відрізки

4) Інтерпретація отриманого результату

А = Q  R  P

Відрізок А – це перетин відрізків Q та R та його поєднання з відрізком Р.

Розв'язання задачі на відрізки

Перетин відрізків R та Q можна візуалізувати: Q= та R=.

Відрізок P= нанесемо на наше креслення і поєднаємо з перетином:

Розв'язання задачі на відрізки

За умовою нашого завдання нам потрібна максимальна довжина відрізка А. Знаходимо її: 30 – 10 = 20.

А = Q  R  P

Відповідь на сайті Полякова К.Ю.: 20

2. Завдання на множини

(№ 386) Елементами множин А, P, Q є натуральні числа, причому P = (1,2,3,4,5,6), Q = (3,5,15). Відомо, що вираз (x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q)

істинно (тобто приймає значення 1 за будь-якого значення змінної х. Визначте найменшу можливу кількість елементів у множині A.).

Джерело - сайт Полякова К.Ю.

Розв'язання задачі на безлічі

  • Легенда
  • Формалізація умови
  • Розв'язання логічного рівняння
  • Інтерпретація отриманого результату

Розв'язання задачі на безлічі

  • Легенда

Розв'язання задачі на безлічі

2) Формалізація умови

(x ∉ A) → ((x ∉ P) ∧ (x ∈ Q)) ∨ (x ∉ Q) = 1

¬ A → (¬P ∧ Q)  ¬ Q = 1

Розв'язання задачі на безлічі

3) Розв'язання логічного рівняння

¬ A → (¬P ∧ Q)  ¬ Q = 1

3.1. Представимо логічне проходження в базових логічних операціях і згрупуємо:

A  ((¬P ∧ Q)  ¬ Q) = 1

Розв'язання задачі на безлічі

A  ((¬P ∧ Q)  ¬Q) = 1

3.2. Зведемо вираз до вирішальної формули:

і знайдемо, чому дорівнює ¬А:

¬А = (¬P ∧ Q)  ¬Q

Розв'язання задачі на безлічі

¬А = (¬P ∧ Q)  ¬Q

3.3. Спростимо вираз для ¬А, розкривши дужки згідно із законом дистрибутивності складання:

¬А = (¬P  ¬Q)  (Q  ¬Q)

¬А = (¬P  ¬Q)

Розв'язання задачі на безлічі

¬А = (¬P  ¬Q)

За законом де Моргана:

¬А = ¬(P  Q)

3.4. Очевидно, що

Розв'язання задачі на безлічі

4) Інтерпретація отриманого результату

Розв'язання задачі на безлічі

P = 1, 2, 3, 4, 5, 6 і Q =(3, 5,15), таким чином A =(3, 5)

і містить лише 2 елементи.

Відповідь на сайті Полякова: 2

2. Завдання на множини

(№ 368) Елементами множин А, P, Q є натуральні числа, причому P = (2,4,6,8,10,12) і Q = (4,8,12,116). Відомо, що вираз (x ∈ P) → (((x ∈ Q) ∧ (x ∉ A)) → (x ∉ P))

істинно (тобто приймає значення 1) за будь-якого значення змінної х. Визначте найменше можливе значення суми елементів множини A.

Джерело - сайт Полякова К.Ю.

  • Легенда
  • Формалізація умови
  • Розв'язання логічного рівняння
  • Інтерпретація отриманого результату

Розв'язання задачі на безлічі

  • Легенда

Розв'язання задачі на безлічі

2) Формалізація умови

(x ∈ P)→(((x ∈ Q) ∧ (x ∉ A))→(x ∉ P)) = 1

P → ((Q ∧ ¬A) → ¬P) = 1

Розв'язання задачі на безлічі

Розв'язання задачі на безлічі

3) Розв'язання логічного рівняння

P → ((Q ∧ ¬A) → ¬P) = 1

3.1. Представимо перше логічне слідування (у дужках) у базових логічних операціях:

P → (¬(Q ∧ ¬A)  ¬P) = 1

Розв'язання задачі на безлічі

P → (¬(Q ∧ ¬A)  ¬P) = 1

Представимо друге логічне проходження в базових логічних операціях, застосуємо закон де Моргана і перегрупуємо:

¬P (¬(Q ∧ ¬A)  ¬P) = 1

¬P ¬Q  A  ¬P = 1

Розв'язання задачі на безлічі

A  (¬P ¬Q  ¬P) = 1

3.2. Зведемо вираз до вирішальної формули:

і знайдемо, чому дорівнює ¬А:

¬А = (¬P ¬Q  ¬P)

Розв'язання задачі на безлічі

¬А = ¬P ¬Q  ¬P

3.3. Спростимо вираз для ¬А за формулою А  А = А:

¬А = ¬(P Q)

Розв'язання задачі на безлічі

¬А = ¬(P Q)

3.4. Очевидно, що

4) Інтерпретація отриманого результату

Шукана множина А являє собою перетин множин P і Q.

Розв'язання задачі на безлічі

Шукана множина А є перетин множин

P = 2, 4, 6, 8, 10, 12 та

Q = (4, 8, 12, 16), таким чином

і містить лише 3 елементи, сума яких 4+8+12=24 .

Відповідь на сайті Полякова: 24

(№ 379) Позначимо через m&nпораз-рядну кон'юнкцію невід'ємних цілих чисел mі n. Так, наприклад, 14&5=11102&01012=01002=4. Для якого найменшого невід'ємного цілого числа Аформула (x & 29 ≠ 0) → ((x & 12 = 0) → (x & А ≠ 0))

тотожно істинна (тобто. приймає значення 1 при будь-якому невід'ємному цілому значенні змінної х)?

  • Легенда
  • Формалізація умови
  • Розв'язання логічного рівняння
  • Інтерпретація отриманого результату
  • Легенда

    • B = (x & 29 ≠ 0)

    C = (x & 12 ≠ 0)

    A = (x & А ≠ 0)

Розв'язання задачі на порозрядну кон'юнкцію

Ми сприймаємо справжнє висловлювання порозрядну кон'юнкцію, відмінну від нуля, інакше порозрядна кон'юнкція втрачає свій логічний сенс, т.к. завжди можна уявити Х усіма нулями.

Розв'язання задачі на порозрядну кон'юнкцію

2) Формалізація умови

(x & 29 ≠ 0)→((x & 12 = 0)→(x & А ≠ 0))=1

В → (С → А) = 1

Розв'язання задачі на порозрядну кон'юнкцію

3) Розв'язання логічного рівняння

В → (С → А) = 1

В → (С А) = 1

(¬В  С) А = 1

¬А = ¬В  С

¬А = ¬(В ¬ С)

Очевидно, що

А = В ¬ С

Розв'язання задачі на порозрядну кон'юнкцію

Розв'язання задачі на порозрядну кон'юнкцію

4) Інтерпретація отриманого результату

Розв'язання задачі на порозрядну кон'юнкцію

B = (x & 29 ≠ 0)

або 29 = 111012

C = (x & 12 ≠ 0)

¬С або інверсія 12 = 00112

Розв'язання задачі на порозрядну кон'юнкцію

або 29 = 111012

¬С або інверсія 12 = 00112

А = В ¬ С

А = 100012 = 17

Відповідь на сайті Полякова: 17

3. Завдання на порозрядну кон'юнкцію

(№ 375) Введемо вираз M & K, що позначає порозрядну кон'юнкцію M і K (логічне «І» між відповідними бітами двійкового запису). Визначте найменше натуральне число A, таке, що вираз (X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))

тотожно істинно (тобто набуває значення 1 за будь-якого натурального значення змінної X)?

  • Легенда
  • Формалізація умови
  • Розв'язання логічного рівняння
  • Інтерпретація отриманого результату

Розв'язання задачі на порозрядну кон'юнкцію

  • Легенда

    • Легенда для завдань на порозрядну кон'юнкцію відрізняється від решти випадків:

    B = (x & 49 ≠ 0)

    C = (x & 33 ≠ 0)

    A = (x & А ≠ 0)

Розв'язання задачі на порозрядну кон'юнкцію

2) Формалізація умови

(X & 49 ≠ 0) → ((X & 33 = 0) → (X & A ≠ 0))=1

В → (С → А) = 1

Розв'язання задачі на порозрядну кон'юнкцію

3) Розв'язання логічного рівняння

В → (С → А) = 1

В → (С  А) = 1

(¬В  С)  А = 1

¬А = (¬В  С)

Очевидно:

Розв'язання задачі на порозрядну кон'юнкцію

Розв'язання задачі на порозрядну кон'юнкцію

4) Інтерпретація отриманого результату

Потрібне двійкове значення порозрядної кон'юнкції А – це двійкове значення порозрядної кон'юнкції значення В та інверсії двійкового значення С.

Розв'язання задачі на порозрядну кон'юнкцію

B = (x & 49 ≠ 0)

або 49 = 1100012

C = (x & 33 ≠ 0)

¬С або інверсія 33 = 0111102

Розв'язання задачі на порозрядну кон'юнкцію

або 49 = 1100012

¬С або інверсія 33 = 0111102

А = В ¬ С

011110 2

А = 100 002 = 16

Відповідь на сайті Полякова: 16

(№ 372) Позначимо через ДІЛ(n, m) твердження «натуральне число n ділиться без залишку на натуральне число m». Для якого найбільшого натурального числа А формула ? СПРАВА(x,А) → (¬ СПРАВА(x,21) ∧ ¬СПРАВА(x,35))

Джерело - сайт Полякова К.Ю.

  • Легенда
  • Формалізація умови
  • Розв'язання логічного рівняння
  • Інтерпретація отриманого результату

Рішення завдання

на умову подільності

  • Легенда

Рішення завдання

на умову подільності

Легенда проста: А = СПРАВ(x,А)

21 = СПРАВ(х,21)

35 = СПРАВ(x,35)

2) Формалізація умови

Рішення завдання

на умову подільності

¬СПРАВА(x,А) → (¬СПРАВА(x,21) ∧ ¬СПРАВА(x,35))

¬А → (¬21 ∧ ¬35) = 1

тотожно істинна (тобто набуває значення 1)

3) Розв'язання логічного рівняння

Рішення завдання

на умову подільності

¬А → (¬21 ∧ ¬35) = 1

А (¬21 ∧ ¬35) = 1

¬А = ¬21 ∧ ¬35

Очевидно, що

4) Інтерпретація отриманого результату

У цьому завдання це найскладніший етап рішення. Потрібно зрозуміти, що ж таке число А – НОК чи НОД чи …

Рішення завдання

на умову подільності

4) Інтерпретація отриманого результату

Отже, наше число А таке, що Х ділиться на нього без залишку, тоді і тільки тоді, коли Х ділиться без залишку на 21 або на 35. У цьому випадку шукаємо

А = НОД (21, 35) = 7

Рішення завдання

на умову подільності

Відповідь на сайті Полякова: 7

4. Завдання на умову подільності

(№ 370) Позначимо через ДІЛ(n, m) твердження «натуральне число n ділиться без залишку на натуральне число m». Для якого найбільшого натурального числа А формула ? СПРАВА(x,А) → ((СПРАВ(x,6) → ? СПРАВА(x,4))

тотожно істинна (тобто набуває значення 1 за будь-якого натурального значення змінної х)?

Джерело - сайт Полякова К.Ю.

  • Легенда
  • Формалізація умови
  • Розв'язання логічного рівняння
  • Інтерпретація отриманого результату

Рішення завдання

на умову подільності

  • Легенда

    • А = СПРАВ(x,А)

Рішення завдання

на умову подільності

2) Формалізація умови

Рішення завдання

на умову подільності

¬СПРАВА(x,А) → ((СПРАВА(x,6) → ¬СПРАВА(x,4))

тотожно істинна (тобто набуває значення 1

¬А → (6 → ¬4) = 1

3) Розв'язання логічного рівняння

¬А → (6 → ¬4) = 1

¬А → (¬ 6  ¬4) = 1

А  (¬ 6  ¬4) = 1

¬А = ¬ 6  ¬4

Очевидно:

Рішення завдання

на умову подільності

4) Інтерпретація отриманого результату

Отже, А таке, що Х ділиться на нього без залишку тоді і тільки тоді, коли Х ділиться на залишок і на 6, і на 4. Тобто. А = НОК(6, 4) = 12

Відповідь на сайті Полякова: 12

Рішення завдання

на умову подільності

Чи зможете Ви пояснити рішення завдання 18 своїм учням чи друзям?

(Так, ні, не знаю).

Дякую за увагу!

Бєлова Т.В.
як навчити вирішувати завдання 18 еге з інформатики

муніципальна бюджетна загальноосвітня установа «Ліцей»,

м. Арзамас, ya. bellova. tatyana@ yandex. ru

Перед тим як приступати до вирішення завдань 18 «Перевірка істинності логічного вираження» екзаменаційної роботи з інформатики, потрібно пояснити (або згадати) учням, що таке поняття «об'єднання» та «перетин» кількох множин. Оскільки завдання 18 пов'язані з визначенням відрізків, те й найкраще ці поняття пояснювати на відрізках. Але пов'язати необхідно ці поняття з поняттями алгебри логіки – «кон'юнкція» та «диз'юнкція», та й, звичайно ж, «інверсія». Наведу це на прикладі. Спочатку розглянемо інверсію відрізка, чи, простіше кажучи, заперечення відрізка.

Даний відрізок P=. Знайти відрізки, які будуть інверсією відрізку P=. Розглянемо координатну пряму (рис. 1):

Мал. 1

На прямій відзначаємо відрізок P (синя область), тоді зрозуміло, що проміжки P не будуть проміжки і (зелена область) – рис. 1. Звертаючи увагу, що точки 6 і 15 в інверсію відрізка не входитимуть.

Розглянемо ще приклад: дано два відрізки P= і Q=(наведені самі позначення, як у завданні ЄДІ, щоб учні відразу звикали до позначень). Знайти відрізок, який позначатиме кон'юнкцію (об'єднання) та диз'юнкцію (перетин) цих відрізків

Малюємо відрізки на координатній прямій (рис. 2):

Мал. 2

Спочатку відзначаємо області на координатній прямій, які позначають відрізки P (синій колір) та Q (жовтий колір). Потім визначаємо, яка частина координатної прямої буде кон'юнкцією цих двох відрізків. Тут згадуємо, що кон'юнкція – це логічна операція, яка об'єднуємо два простих висловлювання у складне за допомогою логічного зв'язування «і», і складне висловлювання набуватиме значення «істина» тоді і тільки тоді, коли істини обидва вихідних простих висловлювання. Таким чином, отримуємо, що потрібно знайти області, де відрізок P і відрізок Q мають місце, а така область тільки одна - відрізок (червоний колір). Докладніше досліджуємо всі відрізки прямий, щоб учням було наочніше і зрозуміліше сприймати матеріал, отже:

Тепер аналогічно розберемося з диз'юнкцією цих відрізків. Знову ж таки звернемося до визначення цієї логічної операції – «диз'юнкцією називається логічна операція, яка відповідно до двох і більше логічних висловлювань ставить нове, яке істинно тоді й тільки тоді, коли істинно хоча б одне з вихідних вихідних висловлювань». Тобто іншими словами, нам треба знайти на координатній прямій такі проміжки, де є хоча б один із вихідних наших відрізків, цей проміжок, що шукається, буде – зелений колір (рис. 2). Також розберемо кожен із проміжків і покажемо, що це справді так:

Поєднуючи знайдені проміжки, отримуємо що шуканий відрізок, що означає диз'юнкцію вихідних відрізків – це відрізок – зелений колір (рис. 2).

Після аналізу даного прикладу, можна дати учням спробувати знайти різні поєднання логічних операцій - диз'юнкції, кон'юнкції та заперечення. Наприклад, дано два відрізки P=[-4,10] і Q=. Знайти відрізок, який позначатиме наступні логічні операції: , , (можна вигадати й інші різні поєднання цих логічних операцій).

Мал. 3

Мал. 4

Мал. 5

Коли розібрано всі приклади, то в учнів не виникне труднощів із розумінням та рішенням завдання №18 з екзаменаційної роботи єдиного державного іспиту з інформатики.

Наведемо приклади розв'язків кількох завдань:

На числовій прямій дано два відрізки: P = і Q =. Виберіть такий відрізок A, що формула

(xA) → ((x P) → (xQ)) тотожно істинна, тобто набуває значення 1 при будь-якому значенні змінної х. Можливі варіанти відповідей:

1) 2) 3) 4)

Рішення (рис. 6): щоб спростити розуміння висловлювання, позначимо окремі висловлювання буквами - A: xА,P: xP,Q: xQ.Таким чином, отримуємо наступний вираз з урахуванням заміни: → ( P→ )=1. Рівність виразу 1 говорить про те, що яке б значення змінної хми не взяли, наш логічний вираз набуває значення 1, тобто на всій числовій прямій. Згадаймо деякі логічні закони та рівності та перетворимо наш вираз: =1. У результаті одержуємо, що нам треба побудувати диз'юнкцію трьох відрізків, два з яких нам відомі. Їх ми і побудуємо (рис. 7). Для початку, як і у всіх наведених вище прикладах, ми повинні побудувати інверсії відрізків P (помаранчевий колір) і Q (червоний колір). Потім із усього виразу ми можемо визначити проміжки диз'юнкції =1 (зелені області рис. 7). Таким чином отримуємо, що у нас на координатній прямій є «вільна» частина – . Цю частину прямий і повинен перекрити шуканий відрізок А.

Розділи