Информатика — готовимся к ЕГЭ — задача №2
материал для подготовки к егэ (гиа) по информатике и икт (10, 11 класс)

Задача 2 – теория:

1. Алгебра логики – Джордж Буль, «Математический анализ логики» (1847).
2. Базовыми элементами, которыми оперирует алгебра логики, являются высказывания. Это не вопросительный предложения, это утверждения, которые можно считать истинными или ложными. Например:

• Сейчас идет дождь.
• Организм млекопитающего состоит из клеток.
• Я владею французским языком в совершенстве.

3. Высказывания обозначаются буквами латинского алфавита — переменными величинами. Переменные в алгебре логики могут принимать два значения A=1, если высказывание А истинно и А=0, если высказывание ложно.
4. Переменные могут включаться в разные логические функции. Простейшие функции это:

• НЕ (отрицание).
• И (логическое умножение или конъюнкция)
• ИЛИ (логическое сложение или дизъюнкция)

5. Логические функции полностью описываются таблицей истинности (ТИ).

Для упрощения логических функций с отрицаниями бывают полезны правила де Моргана:

Задача 2 – Пример 1

Примечание: для решения задачи этого вида нет единого алгоритма. Но надо:

1. Постараться упростить функцию, в частности, можно заменить «и/или» на «умножение/сложение».
2. Часто для упрощения можно разбить функцию на две части – A и B. После этого надо постараться найти «ключи» – увидеть соответствие между фрагментом ТИ и логической формулой.
3. В примере этой задачи показано, как можно по очереди исключать переменные из анализа. Для этого надо постараться определять их позицию в ТИ. Если они не меняют значения (всегда равны 1 или 0) их значение можно подставить в формулу и таким образом упростить ее.

Логическая функция F задаётся выражением: ((x /\ y) \/ (y /\ z)) ≡ ((x → w) /\ (w → z))

Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z.

Поиск решения:

1. Преобразуем функцию к более понятному виду: x · y + y · z ≡ (x → w) · (w → z)
2. Выделим правую и левую части:

A = x · y + y · z

B = (x → w) · (w → z)

A и B эквивалентны, то есть должны быть равны либо 0, либо 1

3. Попробуем найти переменную П1 — она всегда равна 0. Выдвинем гипотезу и проверим ее по первой строке (где остальные переменные равны 1):

• Если x = 0, то A = 1, и В = 1 — вариант.
• Если y = 0, то A = 0, но В ≠ 1 — не вариант.
• Если w = 0, то A = 1, но В ≠ 1 — не вариант.
• Если z = 0, то A = 1, но В ≠ 1 — не вариант.

4. Мы установили, что П1 = x, теперь мы можем упростить функцию:

A = x · y + y · z = 0 · y + y · z = y · z

B = (x → w) · (w → z) = (0 → w) · (w → z) = 1 · (w → z) = w → z

Теперь в функции нет переменной x, мы можем уменьшить фрагмент ТИ — исключить П1 (мы знаем, что это x=0) и вычеркнуть первую строчку (она уже «отработала»):

Посмотрим, какая переменная может быть единицей (по третьей строке, где остальные переменные равны 0):

• Если y = П2, то A = 0, а В = 1 — не вариант.
• Если w = П2, то A = 0 и В = 0 — вариант.
• Если z = П2, то A = 0, а В = 1 — не вариант.

5. Значит, П2 = w, теперь мы можем снова упростить функцию:

A = y · z

B = 1 → z

Теперь в функции нет переменной w, мы можем снова уменьшить фрагмент ТИ на один столбец (мы знаем, что П2 это w =1) и вычеркнуть третью строчку (она уже «отработала»):

• Если y = 0 и z = 1, то A = 0, В = 1 — не вариант.
• Если z = 0 и y = 1, то A = 0, В = 0 — вариант.

Ответ: xwzy

Примечание: в конце файла вы найдете еще два похожих примера

Задача 2 — Пример 2 (это простая, т.н. монотонная функция)

Логическая функция F задаётся выражением:

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

На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна.

Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z.

1. Постараемся упростить функцию:

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

¬x · y · z + ¬x · ¬y · z + ¬x · ¬y · ¬z =

Мы видим три слагаемых, одно из которых должно быть равно 1, чтобы функция стала равна 1.

В третьей строчке нулю равняется П2, этой строчке соответствует слагаемое ¬x · y · z — если П2=x, то слагаемое станет равным 1.

Во второй строчке нулю равны П2 = x и П3. Этой строчке соответствует слагаемое ¬x · ¬y · z — если П2=x и П3=у, то слагаемое станет равным 1.

Остается П1= z

Ответ: zxy

Задача 2 — отработка.

Отработка 1 по 10 заданиям сайта «Решу ЕГЭ – информатика» (https://inf-ege.sdamgia.ru ):

1. Задание № 9788.        Ответ: …                                Время …
2. Задание № 10278.        Ответ: …                                Время …
3. Задание № 11231.        Ответ: …                                Время …
4. Задание № 11338.        Ответ: …                                Время …
5. Задание № 13398.        Ответ: …                                Время …
6. Задание № 14217.        Ответ: …                                Время …
7. Задание № 14688.        Ответ: …                                Время …
8. Задание № 15124.        Ответ: …                                Время …
9. Задание № 15618.        Ответ: …                                Время …
10. Задание № 17366.        Ответ: …                                Время …

Отработка 2 по 10 по заданиям сайта «Решу ЕГЭ – информатика» (https://inf-ege.sdamgia.ru ):

1. Задание № 16805         Ответ: …                                Время …
2. Задание № 16431         Ответ: …                                Время …
3. Задание № 16377         Ответ: …                                Время …
4. Задание № 16029         Ответ: …                                Время …
5. Задание № 15970         Ответ: …                                Время …
6. Задание № 15939         Ответ: …                                Время …
7. Задание № 15912         Ответ: …                                Время …
8. Задание № 15842         Ответ: …                                Время …
9. Задание № 15814         Ответ: …                                Время …
10. Задание № 15787         Ответ: …                                Время …

Важно! Отработка ведет в экзаменационном темпе, без проверки – правильно или неправильно решена задача. Правильный ответ можно разыскать на сайте «Решу ЕГЭ», но здесь не надо никого обманывать (прежде всего – себя). Надо приучить себя к мысли, что ошибки могут быть (их нет только у тех, кто ничего не делает). А правильный ответ и правильное решение мы найдем при отработке самоконтроля. Все хорошо, не надо ничего бояться!

Важно! К «тиканью» времени люди привыкают. Тренированный человек не волнуется, что время идет быстро, а задача решается медленно. Он просто и спокойно решает задачи — как будто времени много, целые сутки. Разум сам старается спешить, не надо его погонять, он от этого умнее не станет. А фиксация времени нам нужна, чтобы привыкнуть к его ходу и не «дергаться». И еще чтобы сравнить нынешнюю скорость с той, что будет перед экзаменом.

Задача 2 – Пример 1a

Логическая функция F задаётся выражением: ((y → w) ≡ (x → ¬z)) /\ (x \/ w).

Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z.

Поиск решения:

1. Преобразуем функцию к более понятному виду: (y → w ≡ x → ¬z) · (x + w)
2. Попробуем найти переменную П1 по первой строчке. П1 здесь равна 0, остальные переменные равны 1, вся функция — ложна.

• Если x = 0, y = z = w = 1, то функция становится такой: (1 ≡ 1) · (0 + 1) — не вариант.
• Если y = 0, x = z = w = 1, то функция становится такой: (1 ≡ 0) · (1 + 1) — вариант.
• Если z = 0, x = y = w = 1, то функция становится такой: (1 ≡ 1) · (1 + 1) — не вариант.
• Если w = 0, x = y = z = 1, то функция становится такой: (0 ≡ 0) · (1 + 0) — не вариант.

3. Мы установили, что П1 = y, но упростить функцию пока не можем (П1 меняет значения в разных строках), можем только вычеркнуть первую строчку таблицы.

Посмотрим, какая переменная может быть единицей (по первой строке, где П3 = 1, y = 1, а остальные переменные равны 0). Функция здесь принимает вид: (1 → w ≡ x → ¬z) · (x + w)

• Если x = 1, z = 0, w = 0, то функция становится такой: (0 ≡ 1) · (0 + 1) — не вариант.
• Если z = 1, x = 0, w = 0, то функция становится такой: (0 ≡ 0) · (0 + 0) — не вариант.
• Если w = 1, x = 0, z = 0, то функция становится такой: (1 ≡ 1) · (0 + 1) — вариант.

4. Мы установили, что П3 = w, но упростить функцию пока не можем (П1 и П3 меняют значения в разных строках), можем снова вычеркнуть первую строчку таблицы.

Мы уже рассматривали варианты, когда y = П3 =1, а остальные переменные равны 0, это позволило нам определить П3 = w. Теперь нам придется попробовать вариант y = 0, П4 =1 — чтобы П4 отличалась П2=0.

Если y = w = 0, формула примет вид: (0 → 0 ≡ x → ¬z) · (x + 0). Или еще проще:

(1 ≡ x → ¬z) · x

Вариант x = 1, z = 0 даст функцию: (1 ≡ 1) · 1 — вариант.

Вариант x = 0, z = 1 даст функцию: (1 ≡ 1) · 0 — не вариант.

Значит: П2 = z, П4 = x,

Ответ: уzwx

Задача 2 – Пример 1b

Логическая функция F задаётся выражением: ((w → ¬x) ≡ (z → y)) /\ (y \/ w).

Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F. Определите, какому столбцу таблицы истинности соответствует каждая из переменных w, x, y, z.

Поиск решения:

5. Преобразуем функцию к более понятному виду: (w → ¬x ≡ z → y) · (y + w)
6. Попробуем найти переменную П4 по первой строчке. П4 здесь равна 0, остальные переменные равны 1, вся функция — ложна.

• Если x = 0, y = z = w = 1, то функция становится такой: (1 ≡ 1) · (1 + 1) — не вариант.
• Если y = 0, x = z = w = 1, то функция становится такой: (0 ≡ 0) · (0 + 1) — не вариант.
• Если z = 0, x = y = w = 1, то функция становится такой: (0 ≡ 1) · (1 + 1) — вариант.
• Если w = 0, x = y = z = 1, то функция становится такой: (1 ≡ 1) · (1 + 0) — не вариант.

7. Мы установили, что П4 = z, но упростить функцию пока не можем (П4 меняет значения в разных строках), можем только вычеркнуть первую строчку таблицы.

Посмотрим, какая переменная может быть единицей (по первой строке, где П3 = 1, z = 1, а остальные переменные равны 0). Функция здесь принимает вид: (w → ¬x ≡ 1 → y) · (y + w)

• Если x = 1, y = 0, w = 0, то функция становится такой: (1 ≡ 0) · (0 + 0) — не вариант.
• Если y = 1, x = 0, w = 0, то функция становится такой: (1 ≡ 1) · (1 + 0) — вариант.
• Если w = 1, x = 0, y = 0, то функция становится такой: (1 ≡ 0) · (0 + 1) — не вариант.

8. Мы установили, что П3 = y, но упростить функцию пока не можем (П1 и П4 меняют значения в разных строках), можем снова вычеркнуть первую строчку таблицы.

Мы уже рассматривали варианты, когда z = П3 =1, а остальные переменные равны 0, это позволило нам определить П3 = y. Теперь нам придется попробовать вариант z = 0, П2 =1 — чтобы П2 отличалась от П1=0.

Если y = z = 0, формула примет вид: (w → ¬x ≡ 1) · (0 + w). Или еще проще:

(w → ¬x ≡ 1) · w

Вариант x = 1, w = 0 даст функцию: (1 ≡ 1) · 0 — не вариант.

Вариант x = 0, w = 1 даст функцию: (1 ≡ 1) · 1 — вариант.

Значит: П1 = x, П2 = w,

Ответ: xwyz