Решение задания 18 егэ по информатике с помощью таблиц истинности

Л. И. Мазничевская

средняя общеобразовательная школа № 763, Москва

Решение задания 18 ЕГЭ ПО ИНФОРМАТИКЕ С ПОМОЩЬЮ ТАБЛИЦ ИСТИННОСТИ

Аннотация

В статье представлены материалы, предназначенные для использования учителями информатики при подготовке учащихся к ЕГЭ по информатике.

К сожалению, правильно решают задание 18 ЕГЭ по информатике малая часть учащихся. Это связано с тем, что предлагаются различные способы решения этого задания, но эти способы применимы только на некотором сегменте заданий.

В представленных вашему вниманию материалах четыре различных типа задач решаются с помощью составления таблиц истинности. Все задачи выбраны из заданий для тренировки с известного сайта К. Ю. Полякова[1].

Ключевые слова: информатика, таблица истинности, алгоритм, законы алгебры логики, импликация.

Контактная информация

Мазничевская Лариса Ивановна, учитель информатики высшей категории, государственное бюджетное общеобразовательное учреждение города Москвы “Школа № 763”, адрес: 129346, г. Москва, ул. Стартовая, д. 27, к. 3; телефон: (495) 474-90-60; e-mail: mli97@inbox.ru

При решении любого задания 18 ЕГЭ по информатике необходимо знать основные понятия и законы математической логики, а также выполнить следующие шаги алгоритма:

• определение элементарных высказываний

• замена переменных (при необходимости)

• раскрытие импликации или эквивалентности

• преобразование с использованием законов алгебры логики

• построение таблиц истинности

• запись ответа.

Задача 1(105 Поляков)

На числовой прямой даны два отрезка: P = [44; 49] и Q = [28; 53]. Укажите наибольшую возможную длину такого отрезка A, что формула

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

Решение:

Введем обозначения и упростим выражение:

=P Q

Вся числовая ось распадается на интервалы, построим таблицу истинности для одного из значений заданного интервала для полученной формулы

Так как нам нужна наибольшая возможная длина такого отрезка A, чтобы формула

была тождественно истинна, то есть принимала значение 1 при любом значении переменной х, то А принимает значение истинно на [28;53], длина этого отрезка равна 53-28=25

Ответ: 25

Задача 2(135 Поляков)

Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m». Для какого наименьшего натурального числа А формула

ДЕЛ(x, A)  (ДЕЛ(x, 14)  ДЕЛ(x, 21))

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

Решение:

Упростим выражение:

ДЕЛ(x, A)  (ДЕЛ(x, 14)  ДЕЛ(x, 21))=  ДЕЛ(x, A) ДЕЛ(x, 14)  ДЕЛ(x, 21)

Определим числа, входящие во множество ДЕЛ(x, 14) и ДЕЛ(x, 21): 14, 21, 28, 42, 56,63…

Построим таблицу истинности для формулы  ДЕЛ(x, A) ДЕЛ(x, 14)  ДЕЛ(x, 21)

Необходимо выбрать первое значение А, при котором высказывание «Х не кратно А»может принимать любое значение Х=42, оно является наименьшим.

Ответ: 42

Задача 3(150 Поляков)

Введём выражение M & K, обозначающее поразрядную конъюнкцию M и K (логическое «И» между соответствующими битами двоичной записи). Определите наименьшее натуральное число A, такое что выражение

(X & 56  0)  ((X & 48 = 0)  (X & A  0))

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

Решение:

Для удобства введем обозначения и упростим выражение

56= X & 56  0

48=X & 48  0

A= X & A  0

(X & 56  0)  ((X & 48 = 0)  (X & A  0))=56  ( 48  A ) = А

Переведем в двоичную систему счисления числа 18, 54

56₁₀=111000₂

48₁₀=110000₂

Искомое число х – разрядное слагаемое двоичной системы счисления из множества {1, 2, 4,8,16,32}. Построим таблицу истинности

Из таблицы х=8, оно является наименьшим

Ответ: 8

Задача 4(88 Поляков)

Элементами множества А являются натуральные числа. Известно, что выражение

(x {2, 4, 6, 8, 10, 12}) → (((x {3, 6, 9, 12, 15})  ¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))

истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.

Решение:

Для удобства введем обозначения и упростим выражение

В=x {2, 4, 6, 8, 10, 12}

С= x {3, 6, 9, 12, 15}

А= x A

(x {2, 4, 6, 8, 10, 12}) → (((x {3, 6, 9, 12, 15})  ¬(x A)) → ¬(x {2, 4, 6, 8, 10, 12}))=B→((C ¬A) → ¬B) = ¬B((C ¬A) → ¬B)= ¬B¬C ¬A) ¬B= ¬B¬C

Построим таблицу истинности

6+12=18

Ответ: 8

Литература

1. http://kpolyakov.spb.ru/school/probook.htm