Преподавателю
Информатика
Подготовка учащихся к ЕГЭ по информатике и ИКТ по теме: ЛОГИКА

Подготовка учащихся к ЕГЭ по информатике и ИКТ по теме: ЛОГИКА

Подготовка учащихся к ЕГЭ по информатике и ИКТ по теме: "Логика".Задачи по теме "Логика" включены в материалы Единого государственного экзамена в достаточно большом количестве. Большинство логических задач части А и части В достаточно удобно решать построением таблиц истинности (А3,А10,B15). В данном материале рассмотрены несколько способов решения задач, даны задания для самостоятельного решения.Задании А3 - рассматривается задача на соответствие данного фрагмент таблицы истинности и данного в...

Раздел	Информатика
Класс	-
Тип	Другие методич. материалы
Автор	Виноградова М.Н.
Дата	18.12.2014
Формат	doc
Изображения	Есть

Поделитесь с коллегами:

ОСНОВЫ ЛОГИКИ

Задания с выбором одного ответа

№ 1

Для составления цепочек разрешается использовать бусины четырех типов, обозначенные

буквами Н, У, Ы, Х. Каждая цепочка должна состоять из четырех бусин, при этом должны

соблюдаться правила:

- любая цепочка начинается с согласной,

- любая цепочка заканчивается буквой Ы или У,

- на втором месте не может стоять гласная.

Какая из цепочек построена по этим правилам?

1) ЫХХУ 2) ХЫХЫ 3) НУХЫ 4) НХЫЫ

Решение:

Здесь правила есть логические высказывания. Требуется определить, какая из

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

истинность высказываний:

Ответы

любая цепочка начинается с согласной

любая цепочка заканчивается буквой Ы или У

на втором месте не может стоять гласная

1) ЫХХУ

нет

да

2) ХЫХЫ

да

нет

3) НУХЫ

да

нет

4) НХЫЫ

да

Все высказывания истинны только для ответа № 4.

Ответ: № 4

№ 2

Пятеро студентов, желающих защитить курсовую работу, записали свои пожелания на

очередность: Мария хочет защищаться первой или третьей; Евгений - только последним;

Жанна хочет быть второй или третьей; Алексей - четвертым или пятым; Илья - первым

или вторым. Предложено четыре варианта очереди. Какой из них устроит всех? (М -

Мария, Е - Евгений, Ж- Жанна, А - Алексей, И - Илья)

1) М И Ж Е А 2) И Ж М Е А 3) И Ж М А Е 4) М Ж А И Е

Решение:

Требуется выяснить, для какого из вариантов ответов все высказывания студентов

истинны. Внесем их в таблицу,

Номер защиты

Студент

М, И

Ж, И

М, Ж

А, Е

Проверим истинность высказываний для каждого ответа.

Ответы:

1: М, И

2: Ж, И

3: М, Ж

4: А

5: А, Е

1) М И Ж Е А

да

нет

да

2) И Ж М Е А

да

нет

да

3) И Ж М А Е

да

4) М Ж А И Е

да

нет

да

Все высказывания истинны только для ответа № 3

Ответ: № 3

№ 3

Таблица истинности логической функции F = А Λ В V ¬ А Λ ¬В имеет вид

¬ А

¬В

А Λ В

¬ А Λ ¬В

А Λ В V ¬ А Λ ¬В

1) 2) 3) 4)

Ответ: № 3

№ 4

Дан фрагмент таблицы истинности выражения F

Какое выражение может соответствовать F?

1) ¬ X Λ ¬ Y Λ ¬ Z

2) ¬ X V ¬ Y Λ ¬ Z

3) X Λ ¬ Y V Z

4) X Λ ¬ Y V ¬ Z

Решение:

Если бы таблица истинности была задана полностью, т.е. на всех наборах переменных X,

Y и Z, можно было бы решить это задание построением КНФ или ДНФ.

Самый простой способ решения этого задания - подстановка значений переменных из

строк таблицы истинности в предложенные в ответах выражения и сравнение результата

вычисления выражения с соответствующим значением F в заданном фрагменте таблицы

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

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

¬ X Λ ¬ Y Λ ¬ Z

¬ X V ¬ Y Λ ¬ Z

X Λ ¬ Y V Z

X Λ ¬ Y V ¬ Z

Значения выражения варианта ответа № 4 совпадают с F на всех заданных наборах.

Ответ: № 4

№ 5

Для какого из указанных значений числа X истинно выражение

¬ (( X - 2 > 6) V ( X - 4 > 8 )) Λ ¬ ( X*3 > 25 ) ?

1) 7 2) 9 3) 11 4) 12

Решение: Преобразуем неравенства так, чтобы слева оставалась только переменная X.

Получим ¬ (( X > 8) V ( X > 12 )) Λ ¬ ( X > 25/3) .

Эту задачу можно решить составлением таблицы истинности. Введем логические

переменные А, В и С: А = ( X - 2 > 6) , В =( X - 4 > 8 ), С = ( X*3 > 25 ). Тогда выражение

можно записать в виде ¬ (A V B) Λ ¬ C. Порядок выполнения операций: отрицание C,

логическое сложение (A V B), отрицание (A V B) , логическое умножение.

( X > 8)

( X > 12)

( X > 25/3)

¬ C

(AVB)

¬ (AVB)

¬ (AVB) Λ¬ C

Ответ: № 1

№ 6

Укажите тождественно истинное выражение

1) ¬ А V¬В Λ (¬ А V А Λ В) V ¬ В =F

2) А Λ (¬ А Λ В V А Λ ¬В) V ¬А =F

3) А Λ (¬А Λ В V А Λ ¬В) Λ ¬А =F

4) АV В Λ(¬А V А Λ В) V ¬В =F

1).

¬ А

¬В

АΛВ

¬АVАΛВ

¬ВΛ(¬АVАΛВ

2).

¬А

¬В

¬АΛВ

АΛ¬В

¬АΛВVАΛ¬В

АΛ(¬АΛВVАΛ¬В)

3).

¬А

¬В

¬АΛВ

АΛ¬В

¬АΛВVАΛ¬В

АΛ(¬АΛВVАΛ¬В)

4).

¬ А

¬В

АΛВ

¬АVАΛВ

ВΛ(¬АVАΛВ

(При нахождении F в 1) и 4) примерах производим сложение трех слагаемых).

Ответ: № 4.

№ 7

Логическое выражение ¬(А Λ В V ¬С) V ¬А Λ В равносильно выражению

1) 0

2) ¬А Λ В V ¬А Λ C V ¬В ΛС

3) ¬А V ¬В V ¬С

4) ¬А Λ В V ¬А Λ ¬C V ¬В Λ ¬С

Решение: все предложенные варианты ответов представлены в нормальных

формах. Приведем исходное выражение к нормальной форме, избавляясь от импликации,

используя законы де Моргана и двойного отрицания.

¬(А Λ В V ¬С) V ¬А Λ В = (¬(А Λ В) Λ С)) V (¬А Λ В) = (¬А V¬В)Λ С V(¬А Λ В)= ¬А Λ C V ¬В ΛС V ¬А Λ В =¬А Λ В V ¬А Λ C V ¬В ΛС

Ответ: № 2.

Задания с кратким ответом

№ 8

Классный руководитель пожаловался директору, что у него в классе появилась компания

из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий

говорит через раз то ложь, то правду. Директор знает, что их зовут Петя, Семен и Максим,

но не знает, кто из них правдив, а кто - нет. Однажды все трое опоздали на урок. Он

вызвал всех троих в кабинет и поговорил с мальчиками. Петя сказал: "По крайней мере

часть утверждений Семена правдива". Семен сказал: "Петя сказал про меня неправду".

Директор понял, кто из них кто. Расположите первые буквы имен мальчиков в порядке:

"говорит всегда правду", "всегда лжет", "говорит правду через раз". (Пример: если бы

имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ)

Решение:

У нас три ученика. 3!=3*2*1=6

Следовательно 6 различный вариантов.

Обозначим:

1 - "говорит всегда правду",

2 - "всегда лжет",

3 - "говорит правду через раз".

Петя

Семен

Максим

Проверим три предположения: Петя «всегда говорит правду», Петя «всегда лжет» и Петя

«говорит правду через раз».

1) Допустим, Петя всегда говорит правду. Его ответ "По крайней мере

часть утверждений Семена правдива". При ответе Семена "Петя сказал про меня неправду», если Семен всегда лжет противоречит этому предположению.

А если Семен говорит правду через раз - удовлетворяет предположению.

2) Допустим, Петя всегда лжет. Его ответ "По крайней мере часть утверждений Семена правдива". При ответе Семена "Петя сказал про меня неправду», если Семен говорит всегда правду - противоречит этому предположению.

А если Семен говорит правду через раз, тоже противоречит этому предположению.

3) Допустим, Петя говорит правду через раз. Его ответ "По крайней мере часть утверждений Семена правдива". При ответе Семена "Петя сказал про меня неправду», если Семен говорит всегда правду - противоречит этому предположению.

А если Семен говорит всегда ложь, тоже противоречит этому предположению.

Следовательно, Петя всегда говорит правду, а Семен говорит правду через раз.

Ответ: ПМС

№ 9

На одной улице стоят в ряд 4 дома, в которых живут 4 человека: Алексей, Егор, Виктор и

Михаил. Известно, что каждый из них владеет ровно одной из следующих профессий:

Токарь, Столяр, Хирург и Окулист, но неизвестно, кто какой, и неизвестно, кто в каком

доме живет. Однако, известно, что:

1) Хирург живет рядом с Окулистом

2) Окулист живет правее Столяра

3) Токарь живет рядом с Хирургом и Столяром

4) Алексей живет рядом с Токарем

5) Егор не живет рядом с Хирургом

6) Михаил живет левее Алексея

Выясните, кто где живет, и дайте ответ в виде перечня заглавных букв имен людей, в

порядке слева направо. Например, если бы в домах жили (слева направо) Константин,

Николай, Роман и Олег, ответ был бы: КНРО

Решение.

По условию задачи требуется установить не только профессию, но и

последовательность домов. Каждый человек имеет одну профессию и живет в одном из

домов. Заметим, что первые символы имен и профессий не совпадают, поэтому будем

использовать их в таблицах.

Составим таблицу, в которой укажем номера домов и профессии.

3) Токарь живет рядом с Хирургом и Столяром, тогда Токарь не может жить в 1 и 4 домах.

2) Окулист живет правее Столяра, тогда Столяр не может жить в 4 доме, а Окулист - в 1 доме.

Предположим: Токарь живет в 3 доме: так как Столяр не может жить в 4 доме, тогда в 4 доме живет Хирург. Столяр живет во 2 доме. Окулист живет правее Столяра, тоже в 3 доме. Этого быть не может.

Следовательно Токарь живет во 2 доме, Окулист только в 4 доме. Рядом с Окулистом Хирург - в 3 доме. А в 1 доме живет Столяр.

Определим профессии людей. Для этого составим вторую таблицу, в которой

профессии упорядочим по расположению домов.

Из высказываний:

4) Алексей живет рядом с Токарем, тогда он Столяр или Хирург, но

6) Михаил живет левее Алексея, тогда Алексей не может быть Столяром, следовательно, он - Хирург. Михаил - Токарь.

5) Егор не живет рядом с Хирургом, тогда он Столяр.

Остается: Виктор - Окулист.

Ответ: ЕМАВ.

№ 10

Девять ребят нашли на улице бездомного котёнка. Один из них взял этого котёнка домой.

Необходимо установить, кто из ребят взял домой котёнка. Ниже даны утверждения ребят.

Паша: это сделал Вася

Борис: это сделал либо Вася, либо Паша

Аня: Паша неправ

Сергей: Маша этого не делала

Андрей: Ни Маша, ни Паша этого не делали

Вася: Ни Вася, ни Паша этого не делали

Маша: Паша этого не делал

Коля: Андрей неправ

Ирина: это сделала Маша

Кто взял домой котёнка, если известно, что из девяти высказываний истинны только

четыре? Ответ запишите в виде первой буквы имени.

Решение:

Будем проверять истинность всех девяти высказываний при истинности одного из

четырех предположений, кто из ребят взял котенка домой.

Результат запишем в таблицу.

Паша

Вася

Маша

Паша

Борис

Аня

Сергей

Андрей

Вася

Маша

Коля

Ирина

К-во истинных высказываний

Котенка взял домой Паша.

Ответ: П.

№ 11

Три знатока чая попробовали один сорт, не зная, что это за чай. После дегустации

они высказали предположения

1) чай Ахмад, произведен в Англии;

2) чай Ристон, произведен в Индии;

3) чай Беседа, произведен не в Англии.

Выяснилось, что каждый знаток прав только в одном из двух своих высказываний.

Какой это был чай и в какой стране он был изготовлен? В ответе запишите две

первые буквы: название чая и страны выпуска. Например, если чай выпущен в Китае и

называется Сенча, то в ответе надо записать СК.

Если каждый знаток прав только в одном из двух своих высказываний, тогда

чай Ахмад, произведен не в Англии - (в Индии)

не чай Ахмад, произведен в Англии;

чай Ристон, произведен не в Индии - (в Англии)

не чай Ристон, произведен в Индии;

чай Беседа, произведен в Англии.

не чай Беседа, произведен не в Англии - (в Индии)

страна

Англия

Индия

высказывание

чай

Ахмад

Ристон

Беседа

В таблице чай Ахмад и страна Индия больше всего истинных высказываний.

Ответ: АИ.

№ 12

Сколько различных решений имеет уравнение

((J V ¬K V L) → ¬(M → ¬N)) Λ ((M Λ N) → (J V ¬K V L)) Λ(M V N V ¬K) = 1

где J, K, L, M, N - логические переменные?

Решение: Построим таблицу истинности. Определим порядок их выполнения логических операций в соответствии с приоритетами и скобками, при этом некоторые группы операций обозначим одним номером.

Введем обозначения, проведем при этом некоторые преобразования, которые

сделают построение таблицы истинности более удобным:

F1 = J V ¬K V L

F2 = ¬(M → ¬N) = ¬(¬M V ¬N) = M Λ N

F3 = M Λ N = F2

F4 = J V ¬K V L = F1

F5 = M V N V ¬K

F6 = F1 → F2 = ¬F1 V F2

F7 = F3 → F4 = F2 → F1 =¬F2 V F1

F8 = F6 Λ F7 Λ F5

¬ K

¬ N

¬F1

¬F2

В таблице истинности выражения девять значений равны 1, следовательно,

уравнение имеет 9 решений.

Ответ: 9.

№ 13

Сколько различных решений имеет уравнение

¬((J → K) → (M Λ N ΛL)) V ¬((J Λ¬K) → ¬(M Λ N Λ L)) V (M Λ J) = 0

где J, K, L, M, N - логические переменные?

Введем обозначения, проведем при этом некоторые преобразования, которые

сделают построение таблицы истинности более удобным:

F1 = J → K = ¬J V K

F2 = M Λ N Λ L

F3 = J Λ¬K

F4 = ¬(M Λ N Λ L)= ¬F2

F5 = M Λ J

F6 = ¬ (F1 → F2) =¬ (¬F1 V F2) = F1 Λ ¬F2 = F1 Λ F4

F7 =¬ (F3 → ¬F2) = =¬ (¬F3 V¬ F2) = F3 Λ F2

F8 = F6V F7 V F5

Таблица истинности:

¬J

¬ K

В таблице истинности выражения шесть значений равны 0, следовательно,

уравнение имеет 6 решений.

Ответ: 6

№ 14

Сколько различных решений имеет уравнение

¬ ((J → K) → (M Λ N Λ L)) V ¬((M ΛN Λ L) → (¬J V K)) V(M ΛJ) = 0

где J, K, L, M, N - логические переменные?

Введем обозначения, проведем при этом некоторые преобразования, которые

сделают построение таблицы истинности более удобным:

F1 = J → K = ¬J V K

F2 = M Λ N Λ L

F3 = M Λ N Λ L= F2

F4 = ¬J ΛK = F1

F5 = M Λ J

F6 = ¬ (F1 → F2) =¬ (¬F1 V F2) = F1 Λ ¬F2

F7 =¬ (F3 → F4) =¬ (F2 → F1) =¬ (¬F2 V F1) = F2 Λ¬ F1

F8 = F6V F7 V F5

Таблица истинности:

¬J

¬F1

¬F2

В таблице истинности выражения шесть значений равны 0, следовательно,

уравнение имеет 6 решений.

Ответ: 6

№ 15

Сколько различных решений имеет уравнение

((J → K) → (M Λ N Λ L)) Λ ((M Λ N Λ L) → (¬J V K)) Λ (M → J) = 1

где J, K, L, M, N - логические переменные?

Решение:

перепишем уравнение, используя более простые обозначения операций:

Подготовка учащихся к ЕГЭ по информатике и ИКТ по теме: ЛОГИКА

имеем логическое произведение трех выражений, которое истинно тогда и только тогда, когда каждое выражение истинно; таким образом, нужно решить систему логических уравнений

Подготовка учащихся к ЕГЭ по информатике и ИКТ по теме: ЛОГИКА

идея состоит в том, чтобы найти все решения одного из уравнений и проверить истинность остальных двух для всех полученных на предыдущем шаге комбинаций значений переменных
рассмотрим первое уравнение: ; оно справедливо в двух случаях:
1. , - любое, или , где звездочка означает, что переменная может принимать значения 0 или 1; всего получается 8 вариантов
2. , , что дает ещё три варианта:
  - два варианта

Подготовка учащихся к ЕГЭ по информатике и ИКТ по теме: ЛОГИКА - один вариант

остается проверить истинность второго ()и третьего () равенств для этих 11 вариантов; сразу видим, что импликация ложна только тогда, когда , то есть для комбинации (10111), а импликация ложна для при любых значениях остальных переменных:
J
K
L
M
N

1
0
0
0
0
1
1

1
0
0
0
1
1
1

1
0
0
1
0
1
1

1
0
0
1
1
1
1

1
0
1
0
0
1
1

1
0
1
0
1
1
1

1
0
1
1
0
1
1

1
0
1
1
1
0
1

0
0
1
1
1
1
0

0
1
1
1
1
1
0

1
1
1
1
1
1
1

таким образом, остается 8 вариантов, отмеченных галочками справа от таблицы
Ответ - 8

Ответ: Решений - 8.

загрузить