Теория для 2 задания ЕГЭ по информатике
Основная тема задания №2 — алгебра логики. С неё и начнём. Для успешного решения номера вам важно знать 3 теоретических момента:
- Основные логические операции
- Порядок логических операций
- Законы логики
Основные логические операции
1. Инверсия «НЕ»
Логическое отрицание
Обозначения: ¬А, Ā
Меняет значение на противоположное
![Таблица истинности для инверсии](https://sun9-18.userapi.com/c206828/v206828314/735db/cP0N69uxQnM.jpg)
2. Конъюнкция «И»
Логическое умножение
Обозначения: А∧В, А & В, А и В, AB
Принимает значение «истина», когда все значения единицы.
Хотя бы один 0 обнуляет всё.
![Таблица истинности для конъюнкции](https://sun9-45.userapi.com/c206828/v206828314/735fc/1Kh3f4SIMJ8.jpg)
3. Дизъюнкция «ИЛИ»
Логическое сложение
Обозначения: А∨В, А | В, А или В
Принимает значение «истина», когда хотя бы одна единица. «Ложь», когда все нули.
![Таблица истинности для дизъюнкции](https://sun9-58.userapi.com/c206828/v206828314/73661/I0z8q3IGOY0.jpg)
4. Импликация "Если, то"
Следование
Обозначения: А→В, А => В
Из истины следует истина, из лжи что угодно
![Таблица истинности для импликации](https://sun9-33.userapi.com/c206828/v206828314/73678/IcO6SbSPK0c.jpg)
5. Эквивалентность «Равны»
Тождество
Обозначения: А≡В, А <=> В
Иcтина, когда значения одинаковы. Ложь, когда различны
![Таблица истинности для эквивалентности](https://sun9-18.userapi.com/c206828/v206828314/73699/PZwkzFXFv20.jpg)
Порядок логических операций
- Действия в скобках
- Инверсия
- Конъюнкция
- Дизъюнкция
- Импликация
- Эквивалентность
Законы логики
Законов логики существует огромное количество, но именно для ЕГЭ достаточно знать 10 законов из данной таблицы. Некоторые из них очевидные, некоторые придётся выучить.
![Законы логики](https://sun9-8.userapi.com/c206828/v206828314/736b6/NzcX3keRauc.jpg)
Практика
Основных вариантов решения два: логические рассуждения, либо построение таблицы истинности. Иногда проще решать первым методом, иногда вторым.
Первый метод. Логические рассуждения.
Пример:
Логическая функция F задаётся выражением y ∧ (x → z) ∧ ¬w. Во фрагменте таблицы истинности приведены все строки, при которых значение функции F истинно.Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
![Статистика выполнения задания 13 ЕГЭ по профилю по годам](https://sun9-16.userapi.com/c206816/v206816647/7223c/wPstBew50kE.jpg)
Решение:
Итоговая функция всегда истинна для нашей таблицы (единички в значениях F). Заметим, что в последнюю очередь выполняются две конъюнкции, значение которых будет = 1 только тогда, когда значение каждого выражение равно 1.
Вывод:
y = 1
(x → z) = 1
¬w = 1,а значит w = 0
y всегда 1, такой столбик лишь один: y — переменная 4
w всегда 0, такой столбик лишь один: w — переменная 2
Для x и z остаётся переменная 1 и переменная 3. Осталось определится с порядком.
(x → z) = 1, значит не может быть набора, когда x = 1, а z = 0.
Во второй строчке перем1 = 1, а перем3 = 0. Следовательно, z — переменная 1, x — переменная 3.
z — переменная 1
w — переменная 2
x — переменная 3
y — переменная 4
Ответ: zwxy
Второй метод. Таблица истинности
Пример:
Логическая функция F задаётся выражением (y → w) ∨ (¬x ∧ z). Во фрагменте таблицы истинности приведены все строки, при которых значение функции F ложно. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
![](https://sun9-34.userapi.com/c206816/v206816688/71a7a/-FrPVTCKirU.jpg)
Решение:
Итоговая функция всегда равна нулю. Между скобками дизъюнкция, значит обе скобки должны быть ложными. Рассмотрим каждую скобку отдельно:
y → w = 0
![](https://sun9-64.userapi.com/c206816/v206816688/71aae/uOfc3I2jO7U.jpg)
¬x ∧ z = 0
![](https://sun9-37.userapi.com/c206816/v206816688/71abf/V1SE44S4GfM.jpg)
Объединяем все переменные в одну таблицу:
![](https://sun9-58.userapi.com/c206816/v206816688/71ad8/ZOSQalFGIR0.jpg)
Соотносим её с таблицей из условия:
y — переменная 4
w — переменная 2
x — переменная 1
z — переменная 3
Ответ: xwzy