Информатика (ЕГЭ 18 задание). Преобразование логических выражений

Сегодня мы поучимся работать с логическими высказываниями в 18 задании ЕГЭ по информатике.

Общая методика решения данных заданий сводится к использованию логических формул, чтобы преобразовывать их в удобный вид. Чаще всего используется такой закон:

A → B = ¬ A  + B.

Задание 1

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n. Так, например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

Для какого наименьшего неотрицательного целого числа А формула

тождественно истинна (т.е. принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение

Преобразуем выражение: x&25 ≠ 0 → (x&17 = 0 → x&А ≠ 0)= x&25= 0 + x&17 ≠ 0 + x&А ≠ 0. Это дизъюнкция.  Она истина, когда хотя бы одно из выражений истинно.

Переведем числа в двоичный вид:

25₁₀ = 11001₂

17₁₀ = 10001₂ .

Чтобы выражение было истинно для всех х, необходимо, чтобы А равнялась тому числу, при которым выражения  x&25= 0 и  x&17  ≠  0 будут ложными.

Для  x&25= 0  это тогда, когда оно не равно нулю (хотя бы на одной из нулевой, 3 или 4 позиций стоит 1).

А для x&17  ≠  0 это тогда, когда оно равно нулю (на нулевой и 4 позиции одновременно стоят нули).

Этому условию удовлетворяет 1000₂ = 8₁₀

Ответ: 8.

Задание 1

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Например, 14&5 = 1110₂&0101₂ = 0100₂ = 4.

Для какого наименьшего неотрицательного целого числа А формула

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной х)?

Решение

Преобразуем выражение: x&25 ≠ 0 → (x&9 = 0 → x&А ≠ 0) = x&25= 0 + x&9 ≠ 0 + x&А≠0. Это дизъюнкция.  Она истина, когда хотя бы одно из выражений истинно.

Переведем числа в двоичный вид:

25₁₀ = 11001₂

9₁₀ = 01001₂

Чтобы выражение было истинно для всех х, необходимо, чтобы А равнялась тому числу, при которым выражения  x&25=0 и  x&9 ≠0 будут ложными.

Для  x&25= 0  это тогда, когда оно не равно нулю (хотя бы на одной из нулевой, 3 или 4 позиций стоит 1).

А для x&9  ≠  0 это тогда, когда оно равно нулю (на нулевой и 3 позиции одновременно стоят нули).

Этому условию удовлетворяет 10000₂ = 16₁₀.

Ответ: 16.