Ученики на Учителя.com


Презентация "Основы логики" 11 класс

Скачать материал
Подписи к слайдам:
ПОДГОТОВКА К ЕГЭ ПО ИНФОРМАТИКЕ
  • Тема «Основы логики»
  • Ведущие мастер-класса:
  • Соколова Светлана Александровна, учитель информатики МБУ школы № 90
  • Банникова Ольга Алексеевна, учитель информатики МБУ гимназии № 77
  • г. Тольятти
ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ
  • Логика – наука о формах и способах мышления. Основными формами мышления являются понятие, суждение, умозаключение.
  • Понятие – это форма мышления, фиксирующая основные, существенные признаки объекта.
  • Высказывание – это форма мышления, в которой что-либо утверждается или отрицается о реальных предметах, их свойствах и отношениях между ними.
  • Высказывание может быть либо истинно, либо ложно.
  • Умозаключение – это форма мышления, с помощью которой из одного или нескольких суждений (посылок) может быть получено новое суждение (вывод).
  • Логика — это наука, изучающая законы и формы мышления.
  • Алгебра логики — это математический аппарат, с помощью которого записывают (кодируют), упрощают, вычисляют и преобразовывают логические высказывания.
  • Высказывание — это повествовательное предложение, о котором можно сказать, истинно оно или ложно. При этом считается, что высказывание удовлетворяет закону исключенного третьего, т.е. каждое высказывание или истинно, или ложно и не может быть одновременно и истинным, и ложным.
  • Если высказывание:
  • истинно - его значение равно 1 (True, T);
  • ложно - 0 (False, F).
  • ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ
  • ЛОГИКИ
ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ
  • Высказывание не может быть выражено повелительным или вопросительным предложением, так как оценка их истинности или ложности невозможна.
  • Для образования сложных высказываний наиболее часто используются базовые логические операции, выражаемые с помощью логических связок И, ИЛИ и частицей НЕ. Значение истинности сложных высказываний зависит от истинности входящих в них простых высказываний и объединяющих их связок.
  • В математической логике не рассматривается конкретное содержание высказывания, важно только, истинно оно или ложно.
ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ
  • Поэтому высказывание можно представить некоторой переменной величиной, значением которой может быть 0 или 1.
  • Если высказывание:
  • истинно - его значение равно 1 (True, T),
  • ложно - 0 (False, F).
  • Простые высказывания назвали логическими переменными, а сложные высказывания логическими функциями. Значения логической функции также только 0 или 1. Для простоты записи высказывания обозначаются латинскими буквами А, В, С.
  • Пример простых высказываний:
  • A = “2+2=4” – истинно,
  • B = “Земля не вертится” – ложно.
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  • В основе булевой алгебры лежат 16 основных функций. Наиболее часто применяемые из них:
    • логическое отрицание (инверсия) – «не»; ¬ ; ¯ ;
  • логическое умножение (конъюнкция) – «и»; &; ^ ; • ;
  • логическое сложение (дизъюнкция) – «или»; +; ;
  • логическое следование (импликация) – 
  • логическая операция эквивалентности – ~ ;  ; ;
  • функция Вебба (отрицание дизъюнкции) – ИЛИ-НЕ;
  • функция Шеффера (отрицание конъюнкции) – И-НЕ;
  • сложение по модулю 2 (М2).
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  • Приведенные функции можно свести в таблицу истинности:
  • Аргументы
  • Функции
  • A
  • B
  • ¬A
  • ¬B
  • A^B
  • A  B
  • AB
  • AB
  • ИЛИ-НЕ
  • И-НЕ
  • М2
  • 0
  • 0
  • 1
  • 1
  • 0
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 1
  • 1
  • 0
  • 0
  • 1
  • 1
  • 0
  • 0
  • 1
  • 1
  • 1
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 0
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 0
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  • Логическое отрицание (инверсия):
    • в естественном языке соответствует словам
    • неверно, что... и частице не;
    • в языках программирования Not.
  • Обозначение ¬ A; Ā.
  • Таблица истинности:
  • Диаграмма Эйлера-Венна
  • Ā
  • A
  • A
  • Ā
  • 0
  • 1
  • 1
  • 0
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  • Логическое сложение (дизъюнкция):
    • в естественном языке соответствует союзу или;
    • в языках программирования Or.
  • Обозначение +; v .
  • Таблица истинности:
  • Диаграмма Эйлера-Венна
  • B
  • A
  • A
  • B
  • A  B
  • 0
  • 0
  • 0
  • 0
  • 1
  • 1
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  • Логическое умножение (конъюнкция):
    • в естественном языке соответствует союзу и;
    • в языках программирования And.
  • Обозначение &; ^ ; ∙ .
  • Таблица истинности:
  • Диаграмма Эйлера-Венна
  • A
  • B
  • A
  • B
  • A^B
  • 0
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
    • 0
  • 1
  • 1
  • 1
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  • Логическое следование (импликация) - логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющимся ложным тогда и только тогда, когда из истинной предпосылки(первого высказывания) следует ложный вывод (второе высказывание). В естественном языке
  • соответствует обороту
  • «если ..., то ...».
  • Обозначение  .
  • A
  • B
  • AB
  • 0
  • 0
  • 1
  • 0
  • 1
  • 1
  • 1
  • 0
  • 0
  • 1
  • 1
  • 1
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  • Логическое следование соответствует высказыванию
  • не A или B
  • Сравним таблицы истинности:
  • Логические выражения, у которых последние столбцы истинности совпадают, называются равносильными.
  • A
  • B
  • AB
  • 0
  • 0
  • 1
  • 0
  • 1
  • 1
  • 1
  • 0
  • 0
  • 1
  • 1
  • 1
  • A
  • B
  • ¬ A
  • ¬A˅B
  • 0
  • 0
  • 1
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 0
  • 1
  • 1
  • 0
  • 1
ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ
  • Логическая операция эквивалентности (равнозначность) - логическое равенство образуется соединением двух простых высказываний в одно с помощью оборота речи
  • «... тогда и только тогда, когда …».
  • Обозначение ~ ;  ;  .
  • Составное высказывание, образованное с помощью логической операции эквивалентности, истинно
  • тогда и только тогда, когда оба высказывания
  • одновременно либо ложны, либо истинны.
  • A
  • B
  • AB
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 0
  • 1
  • 1
  • 1
ПРИОРИТЕТ ВЫПОЛНЕНИЯ ЛОГИЧЕСКИХ ОПЕРАЦИЙ
  • Логическое отрицание (инверсия) – «не»; ¬ ; ¯ .
  • Логическое умножение (конъюнкция) – «и»; &; ^ ; ∙ .
  • Логическое сложение (дизъюнкция) – «или»; +;  .
  • Логическое следование (импликация) – 
  • Логическая операция эквивалентности – ~ ;  ; .
  • Для изменения указанного порядка могут использоваться скобки.
ТАБЛИЦЫ ИСТИННОСТИ
  • Таблица истинности определяет истинность или ложность логической функции при всех возможных комбинациях исходных значений простых высказываний.
  • Правила построения таблиц истинности.
  • Подсчитать количество переменных n в логическом выражении.
  • Определить количество строк в таблице, которое равно m=2n
  • Подсчитать количество операций в логическом выражении и определить количество столбцов в таблице: k = количество переменных (n) + количество операций.
  • Ввести названия столбцов таблицы в соответствии с последовательностью выполнения логических операций с учетом скобок и приоритетов.
  • Заполнить столбцы логических переменных наборами значений.
  • Провести заполнение таблицы истинности по столбцам, выполняя базовые логические операции в соответствии с установленной в п. 4 последовательностью.
ТАБЛИЦЫ ИСТИННОСТИ
  • Пример. Определить истинность формулы F=((C  B) B)^ (A^ B) B
  • Формула является тождественно истинной, если все значения строк результирующего столбца будут равны 1.
  • 1 шаг. Определяем количество строк в таблице: m=23=8
  • 2 шаг. Определяем количество столбцов в таблице:
  • k=3+5=8
ТАБЛИЦА ИСТИННОСТИ F=((C  B) B) ^ (A ^ B) B
  • 2
  • 3
  • 4=3  2
  • 5=42
  • 6=1^2
  • 7=5^6
  • 8=72
  • A
  • B
  • C
  • C  B
  • (C  B) B
  • A^ B
  • ((C  B) B) ^ (A^B)
  • F
  • 0
  • 0
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 0
  • 1
  • 1
  • 1
  • 0
  • 0
  • 1
  • 0
  • 1
  • 1
  • 1
  • 0
  • 1
  • 1
  • 1
  • 0
  • 1
  • 1
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 1
  • 1
  • 1
  • 0
  • 1
  • 1
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 1
  • 1
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
ЗАКОНЫ ЛОГИКИ A7 (повышенный уровень, время – 3 мин)
  • Для какого из указанных значений X истинно высказывание
  • ¬((X > 2)→(X > 3))?
  • 1) 1 2) 2 3) 3 4) 4
  • Определим порядок действий: сначала вычисляются результаты отношений в скобках, затем выполняется импликация (поскольку есть «большие» скобки), затем – отрицание (операция «НЕ») для выражения в больших скобках.
  • ¬((X > 2)→(X > 3))
  • Решение (Вариант 1. Прямая подстановка)
  • 2) Выполняем операции для всех приведенных возможных ответов (1 обозначает истинное условие, 0 – ложное); определяем результаты сравнения в двух внутренних скобках:
  • 1
  • 1
  • 1
  • 0
  • 0
  • 0
  • 1
  • 0
  • Таким образом, ответ – 3.
  • Решение (Вариант 1. Прямая подстановка)
Возможные ловушки и проблемы
  • Можно «забыть» отрицание (помните, что правильный ответ – всего один!)
  • Можно перепутать порядок операций (скобки, «НЕ», «И», «ИЛИ», «импликация»)
  • Нужно помнить таблицу истинности операции «импликация», которую очень любят составители тестов.
  • Этот метод проверяет только заданные числа и не дает общего решения, то есть не определяет все множество значений X, при которых выражение истинно.
Решение (Вариант 2. Упрощение выражения) ¬((X > 2)→(X > 3))
  • Обозначим простые высказывания буквами:
  • A = X > 2, B = X > 3
  • Тогда можно записать все выражение в виде:
  • ¬(A → B) или
  • Выразим импликацию через «НЕ» и «ИЛИ»:
  • A → B = ¬A + B = ¬A  B или
  • Раскрывая по формуле де Моргана, получаем:
  • ¬(¬A  B)= A  ¬B или
  • Таким образом, данное выражение истинно только тогда, когда A истинно (X > 2), а B – ложно (X ≤ 3),
  • то есть для всех X, таких что 2 < X ≤ 3
  • Таким образом, ответ – 3.
Возможные проблемы
  • Нужно помнить законы логики (например, формулы де Моргана).
  • При использовании формул де Моргана нужно не забыть заменить «И» на «ИЛИ» и наоборот.
  • Нужно не забыть, что инверсией (отрицанием) для выражения X > 3 является X ≤ 3, а не X < 3
Выводы
  • В данном случае, наверное, проще первый вариант решения (прямая подстановка всех предложенных ответов).
  • Второй вариант позволяет не только проверить заданные значения, но и получить общее решение – все множество X, для которых выражение истинно; это более красиво для человека, обладающего математическим складом ума.
A8 (базовый уровень, время – 1 мин) Решение (Вариант 1. Использование законов де Моргана)
  • Перепишем заданное выражение в других обозначениях: A  ¬(¬B  C) =
  • Применим формулу де Моргана, а затем закон двойного отрицания:
  • Перепишем ответы в других обозначениях:
    • ¬A  ¬B  ¬C =
    • A  ¬B  ¬C =
    • A  B  ¬C =
    • A  ¬B  C =
  • Таким образом, правильный ответ – 3 .
Возможные ловушки и проблемы
  • Серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений, поэтому рекомендуется сначала внимательно перевести их в удобный вид; потом сразу становится понятно.
  • При использовании законов де Моргана часто забывают, что нужно заменить «И» на «ИЛИ» и «ИЛИ» на «И».
  • Иногда для решения нужно упростить не только исходное выражение, но и заданные ответы, если они содержат импликацию или инверсию сложных выражений.
Решение (Вариант 2. Через таблицы истинности, если забыли формулы де Моргана)
  • Перепишем заданное выражение в других обозначениях: A  ¬(¬B  C) =
  • Перепишем ответы в других обозначениях:
    • ¬A  ¬B  ¬C =
    • A  ¬B  ¬C =
    • A  B  ¬C =
    • A  ¬B  C =
  • Для доказательства равносильности двух логических выражений достаточно показать, что они принимают равные значения при всех возможных комбинациях исходных данных.
Решение (Вариант 2. Продолжение)
  • Поэтому можно составить таблицы истинности для исходного выражения и всех ответов и сравнить их.
  • Здесь 3 переменных, каждая из которых принимает два возможных значения (всего 8 вариантов).
Решение. (Вариант 2. Продолжение)
  • 1
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 1
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • Таким образом, правильный ответ – 3 .
Решение (комментарий к таблице)
  • Исходное выражение истинно только тогда, когда и , то есть только при (в таблице истинности одна единица, остальные – нули)
  • 7) Выражение истинно, если хотя бы одна из переменных равна нулю, то есть, оно будет ложно только при (в таблице истинности один нуль, остальные – единицы).
Решение (комментарий к таблице)
  • Аналогично выражение ложно только при , а в остальных случаях – истинно.
  • Выражение истинно только при ,а в остальных случаях – ложно.
  • Выражение истинно только при
  • , а в остальных случаях – ложно.
Возможные проблемы Выводы
  • Сравнительно большой объем работы.
  • Очевидно, что проще использовать первый вариант решения (упрощение исходного выражения и, если нужно, ответов), но для этого нужно помнить формулы.
  • Если формулы забыты, всегда есть простой (хотя и более трудоемкий) вариант решения через таблицы истинности.
  • Укажите значения переменных К, L, M, N, при которых логическое выражение
  • (¬(М  L)  К) → (¬К  ¬М)  N)
  • ложно.
  • Ответ запишите в виде строки из 4 символов: значений переменных К, L, М и N (в указанном порядке). Так, например, строка 1101 соответствует тому, что К=1, L=1, M=0, N=1.
  • B4 (высокий уровень)
Решение (вариант 1)
  • Запишем уравнение
  • (¬(М  L)  К) → (¬К  ¬М)  N) = 0, используя более простые обозначения операций:
  • Из таблицы истинности операции «импликация» следует, что это выражение ложно тогда и только тогда, когда одновременно и
Решение (вариант 1)
  • Первое равенство выполняется тогда и только тогда, когда К=1 и . Отсюда следует , что может быть только при
  • Таким образом, три переменных мы уже определили: К = 1 , М = 0, L = 0
  • Из второго условия, , при К=1 и М=0 получаем N = 0
  • Таким образом, правильный ответ для К, L, М и N соответственно – 1000
  • Переменные однозначно определяются только для ситуаций «сумма = 0» (все равны 0) и «произведение = 1» (все равны 1), в остальных случаях нужно рассматривать разные варианты.
  • Не всегда выражение сразу распадается на 2 (или более) отдельных уравнения, каждое из которых однозначно определяет некоторые переменные.
  • Возможные проблемы
Решение (вариант 2)
  • Запишем уравнение
  • (¬(М  L)  К) → (¬К  ¬М)  N) = 0, используя более простые обозначения операций:
  • Заменим импликацию по формуле :
  • Раскроем инверсию сложного выражения по формуле де Моргана:
Решение (вариант 2)
  • Упростим выражение
  • Тогда получим:
  • Мы получили уравнение вида «сумма = 0», в нем все слагаемые должны быть равны нулю.
  • Поэтому сразу находим
  • Таким образом, правильный ответ для К, L, М и N соответственно – 1000
  • Этот способ работает всегда и дает более общее решение; в частности, можно легко обнаружить, что уравнение имеет несколько решений (тогда оно не сведется к форме «сумма = 0» или «произведение = 1»).
  • Замечание
  • Нужно помнить правила преобразования логических выражений и хорошо владеть этой техникой.
  • Сколько различных решений имеет уравнение
  • ((K  L) → (L  M  N)) = 0
  • где K, L, M, N – логические переменные?
  • В ответе не нужно перечислять все различные наборы значений K, L, M и N, при которых выполнено данное равенство. В качестве ответа Вам нужно указать количество таких наборов.
  • B4 (высокий уровень)
Решение
  • Перепишем уравнение, используя более простые обозначения операций:
  • ((K + L) → (L · M · N)) = 0.
  • Из таблицы истинности операции «импликация» следует, что это равенство верно тогда и только тогда, когда одновременно
  • K + L = 1 и L · M · N = 0.
  • Из уравнения следует, что хотя бы одна из переменных, K или L равна 1 или обе вместе; поэтому рассмотрим три случая.
  • K = 1 и L = 0; K = 1 и L = 1; K = 0 и L = 1.
  • Если K = 1 и L = 0, то второе равенство L · M · N = 0 выполняется при любых М и N; поскольку существует 4 комбинации двух логических переменных (00, 01, 10 и 11), имеем 4 разных решения.
  • K
  • L
  • М
  • N
    • 1.
  • 1
  • 0
  • 0
  • 0
    • 2.
  • 1
  • 0
  • 0
  • 1
    • 3.
  • 1
  • 0
  • 1
  • 0
    • 4.
  • 1
  • 0
  • 1
  • 1
  • Решение
  • Если K = 1 и L = 1, то второе равенство L · M · N = 0 выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения.
  • K
  • L
  • М
  • N
    • 1.
  • 1
  • 1
  • 0
  • 0
    • 2.
  • 1
  • 1
  • 0
  • 1
    • 3.
  • 1
  • 1
  • 1
  • 0
  • Решение
  • Если K = 0 и L = 1 (из первого уравнения); при этом второе равенство L · M · N = 0 выполняется при М · N = 0; существует 3 таких комбинации (00, 01 и 10), имеем еще 3 решения.
  • K
  • L
  • М
  • N
    • 1.
  • 0
  • 1
  • 0
  • 0
    • 2.
  • 0
  • 1
  • 0
  • 1
    • 3.
  • 0
  • 1
  • 1
  • 0
  • Всего получаем: 4 + 3 + 3 = 10 решений.
  • Решение
Совет
  • Лучше начинать с того уравнения, где меньше переменных.
  • Есть риск потерять какие-то решения при переборе вариантов.
  • Возможные проблемы
ЗАКОНЫ ЛОГИКИ Задание А7. Вариант 1
  • Логическое выражение ¬ Y  ¬ ((X  Y ) ^ ¬ Y) ^X ^ ¬ Y максимально упрощается до выражения:
  • 1) X ^Y 2) ¬Y 3) X 4) 1
  • ¬ Y  ¬ ((X  Y ) ^ ¬ Y) ^X ^ ¬ Y =
  • ¬ Y  ¬ (X ^¬ Y Y ^¬ Y) ^X ^ ¬ Y =
  • ¬ Y  ¬ (X ^¬ Y0) ^X ^ ¬ Y =
  • ¬ Y  ¬ (X ^¬ Y) ^X ^ ¬ Y =
  • ¬ Y  (¬ X ¬ ¬Y) ^X ^ ¬ Y =
  • ¬ Y  (¬ X Y) ^X ^ ¬ Y =
  • ¬ Y  (¬ X Y) ^X ^ ¬ Y =
  • ¬ Y  (¬ X ^X ^ ¬ Y Y ^X ^ ¬ Y) =
  • ¬ Y  (0^ ¬ Y X ^ 0) =
  • ¬ Y  0 = ¬ Y
  • Правильный ответ – 2
ЗАКОНЫ ЛОГИКИ Задание А7. Вариант 2
  • Логическое выражение ¬ (X  Y )  ¬X ^ Y  X  Y максимально упрощается до выражения:
  • 1) 0 2) 1 3) X 4) ¬ X ^Y
  • ¬ (X  Y )  ¬X ^ Y  X  Y =
  • ¬ X ^ ¬ Y  ¬X ^ Y  X  Y =
  • ¬ X ^ ¬ Y  ¬X ^ Y  X  Y =
  • ¬ X ^ ( ¬ Y  Y)  X  Y =
  • ¬ X ^ 1  X  Y =
  • ¬ X  X  Y =
  • ¬ X  X  Y =
  • 1 Y =
  • 1 Y = 1
  • Правильный ответ – 2
КРУГИ ЭЙЛЕРА-ВЕННА
  • Покажем области, определяемые выражениями:
  • A
  • B
  • С
  • A
  • B
  • С
КРУГИ ЭЙЛЕРА-ВЕННА
  • Покажем области, определяемые выражениями:
  • A
  • B
  • С
  • C
  • A
  • B
КРУГИ ЭЙЛЕРА-ВЕННА
  • A
  • B
  • С
  • A
  • B
  • С
  • A
  • B
  • С
  • A
  • B
  • С
КРУГИ ЭЙЛЕРА-ВЕННА
  • Покажем области, определяемые выражениями:
  • B
  • ¬ A
  • X
  • ∙
  • 6
  • B
  • ¬ A
  • X
  • 
  • 5
  • A
  • B
  • Ā
  • A
  • B
  • Ā
  • A
  • B
  • Ā
  • A
  • B
  • Ā
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 1
  • Высказывания A, B, C истинны для точек, принадлежащих соответственно для круга, треугольника и прямоугольника. Для всех точек выделенной на рисунке области истинно высказывание:
  • не B и A и не C
  • A и C и не B
  • не B и A или не C
  • C и A или не B
  • Высказывания A, B, C истинны для точек, принадлежащих соответственно для круга, треугольника и прямоугольника. Для всех точек выделенной на рисунке области истинно высказывание:
  • не B и A и не C
  • A и C и не B
  • не B и A или не C
  • C и A или не B
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 1
  • - A
  • - B
  • - C
  • 1 шаг. A и C
  • 2 шаг. A и C и не B
  • Варианты ответа:
  • не B и A и не C
  • A и C и не B
  • не B и A или не C
  • C и A или не B
  • Правильный ответ – 2
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 2
  • Высказывания A, B, C истинны для точек, принадлежащих соответственно для круга, треугольника и прямоугольника. Для всех точек выделенной на рисунке области истинно высказывание:
  • не A и не C и B
  • не A или не C или B
  • не (B и A) и C
  • B и (C или не A)
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 2
  • - A
  • - B
  • - C
  • 1 шаг. B и C
  • 2 шаг. B и не A
  • Варианты ответа:
  • не A и не C и B
  • не A или не C или B
  • не (B и A) и C
  • B и (C или не A)
  • Правильный ответ – 4
  • 3 шаг. (B и C) или (B и не A)
  • 4 шаг. B и (C или не A )
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 3
  • Высказывания A, B, C истинны для точек, принадлежащих соответственно для круга, треугольника и прямоугольника. Для всех точек выделенной на рисунке области истинно высказывание:
  • C и не A или не B
  • не (C или B и A)
  • (B или C) и (C или не A)
  • B и C или C и не A
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 3
  • - A
  • - B
  • - C
  • 1 шаг. не A и C
  • 2 шаг. B и C
  • Варианты ответа:
  • C и не A или не B
  • не (C или B и A)
  • (B или C) и (C или не A)
  • B и C или C и не A
  • Правильный ответ – 4
  • 3 шаг. (не A и C) или (B и С)
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 4
  • Высказывания A, B, C истинны для точек, принадлежащих соответственно для круга, треугольника и прямоугольника. Для всех точек выделенной на рисунке области истинно высказывание:
  • C и (B или не A)
  • B и C или не C и A
  • C или не A и не B
  • C и не A или B и C
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 4
  • - A
  • - B
  • - C
  • 1 шаг. B и C
  • 2 шаг. A и не C
  • Варианты ответа:
  • C и (B или не A)
  • B и C или не C и A
  • C или не A и не B
  • C и не A или B и C
  • Правильный ответ – 2
  • 3 шаг. (B и C) или (A и не C )
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 5
  • Высказывания A, B, C истинны для точек, принадлежащих соответственно для круга, треугольника и прямоугольника. Для всех точек выделенной на рисунке области истинно высказывание:
  • C и не A и не B
  • B и не A или C и не B
  • не (B и A) и не C
  • C и B или не A
КРУГИ ЭЙЛЕРА-ВЕННА Задание А8. Вариант 5
  • - A
  • - B
  • - C
  • 1 шаг. C и не B
  • 2 шаг. B и не A
  • Варианты ответа:
  • C и не A и не B
  • B и не A или C и не B
  • не (B и A) и не C
  • C и B или не A
  • Правильный ответ – 2
  • 3 шаг. (C и не B) или (B и не A)
B10 (повышенный уровень, время – 5 мин)
  • В таблице приведены запросы к поисковому серверу. Расположите номера запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу. Для обозначения логической операции «ИЛИ» в запросе используется символ |, а для логической операции «И» – &.
  • 1) принтеры & сканеры & продажа
  • 2) принтеры & продажа
  • 3) принтеры | продажа
  • 4) принтеры | сканеры | продажа
Решение (вариант 1)
  • 1) принтеры & сканеры & продажа
  • 2) принтеры & продажа
  • 3) принтеры | продажа
  • 4) принтеры | сканеры | продажа
  • Меньше всего результатов выдаст запрос с наибольшими ограничениями – первый (нужны одновременно принтеры, сканеры и продажа).
  • На втором месте – второй запрос (одновременно принтеры и сканеры).
  • Далее – третий запрос (принтеры или сканеры).
  • Четвертый запрос дает наибольшее количество результатов (принтеры или сканеры или продажа).
  • Таким образом, верный ответ – 1234 .
Возможные проблемы
  • Нужно внимательно читать условие, так как в некоторых задачах требуется перечислить запросы в порядке убывания количества результатов, а в некоторых – в порядке возрастания.
  • Можно ошибиться в непривычных значках: «И» = &, «ИЛИ» = |.
  • Можно перепутать значение операций «И» и «ИЛИ», а также порядок выполнения цепочки операций (сначала – «И», потом – «ИЛИ»).
  • Для сложных запросов не всегда удается так просто расположить запросы по возрастанию (или убыванию) ограничений.
Решение (вариант 2)
  • Запишем все ответы через логические операции.
  • 2. Покажем области, определяемые этими выражениями, на диаграмме с тремя областями:
  • Сравнивая диаграммы, находим последовательность областей в порядке увеличения. Таким образом, верный ответ – 1234.
  • A
  • B
  • С
  • A
  • B
  • С
  • A
  • B
  • С
  • A
  • B
  • С
  • Получается громоздкий рисунок, если используется более трех переменных (более трех кругов).
  • Возможные проблемы
ЛОГИЧЕСКИЕ ОСНОВЫ УСТРОЙСТВА КОМПЬЮТЕРА
  • &
  • А(0,0,1,1)
  • B(0,1,0,1)
  • F(0,0,0,1)
  • Логический элемент «И»
  • Логический элемент «ИЛИ»
  • 1
  • А(0,0,1,1)
  • B(0,1,0,1)
  • F(0,1,1,1)
  • Логический элемент «НЕ»
  • Каждой элементарной логической операции можно поставить в соответствие элементарную логическую схему, или вентиль.
  • А(0,1)
  • F(1,0)
  • На входе и выходе вентиля мы имеем физические сигналы двух видов, что можно ассоциировать с логическим 0 и логической 1.
ЛОГИЧЕСКИЕ СХЕМЫ
  • Построение логических схем по булеву выражению.
  • Определить число переменных.
  • Определить количество логических операций и их порядок.
  • Построить для каждой логической операции свою схему (если это возможно).
  • Объединить логические схеме в порядке выполнения логических операций.
  • Построение булева выражения по логической схеме.
  • На выходе каждого логического элемента записать результат логической операции.
  • Записать получившуюся формулу на выходе последнего элемента.
  • Упростить получившуюся формулу.
ПОСТРОЕНИЕ ЛОГИЧЕСКОЙ СХЕМЫ ПО БУЛЕВУ ВЫРАЖЕНИЮ
  • Пример. F= D^(A ^ B ^C  ¬ B ^ ¬C).
  • Число переменных (входы) – 4 (A, B, C, D).
  • Количество логических операций (количество вентилей) – 7.
  • Определяем порядок выполнения логических операций.
  • F
  • A
  • B
  • C
  • D
  • ¬ B
  • ¬C
  • A ^ B
  • A ^ B ^C
  • ¬ B ^ ¬C
  • &
  • &
  • 1
  • A ^ B ^C  ¬ B ^ ¬C
  • &
  • &
  • F= D^7(A ^3 B ^4C ˅6 ¬1 B ^5 ¬2C)
  • A
ПОСТРОЕНИЕ БУЛЕВА ВЫРАЖЕНИЯ ПО ЛОГИЧЕСКОЙ СХЕМЕ
  • Пример. Дана логическая схема. Построить логическое выражение, описывающее эту схему.
  • Запишем значения на выходах элементов:
  • ¬ A
  • ¬ A ^ B
  • A  ¬ A ^ B
  • ¬B
  • ¬B ^(A  ¬ A ^ B)
  • То есть F=¬B ^(A  ¬ A ^ B)
  • &
  • A
  • B
  • 1
  • 4
  • 1
  • 2
  • &
  • 3
  • 5
  • F
  • Полученную функцию можно сократить:
  • F = ¬B ^ (A  ¬ A ^ B) = = ¬B ^A  ¬B ^ ¬ A ^ B =
  • = A^ ¬B  ¬ A^B^ ¬B=
  • = A^ ¬B  ¬ A^0 =
  • = A^ ¬B
ПОСТРОЕНИЕ БУЛЕВА ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ ИСТИННОСТИ
  • Для каждой строки таблицы с единичным значением функции построить минтерм. (Минтермом называется терм-произведение, в котором каждая переменная встречается только один раз – либо с отрицанием, либо без него). Переменные, имеющие нулевые значения в строке, входят в минтерм с отрицанием, а переменные со значением 1 – без отрицания).
  • Объединить все минтермы операцией дизьюнкция, что даст стандартную сумму произведений для заданной таблицы истинности.
ПОСТРОЕНИЕ БУЛЕВА ВЫРАЖЕНИЯ ПО ТАБЛИЦЕ ИСТИННОСТИ
  • Пример. Дана таблица истинности. Построим булево выражение для F.
  • Найдем строки, в которых F=1. Это 2, 3, 6 строки.
  • Для второй строки: A=0,B=0, C=1.
  • Минтерм: ¬ A^ ¬ B^C
  • Для третьей строки: A=0,B=1, C=0.
  • Минтерм: ¬ A^ B^¬C
  • Для шестой строки: A=1,B=0, C=1.
  • Минтерм: A^ ¬ B^ C
  • Объединяя термы, получим булево выражение для F:
  • F(A,B,C) = ¬ A^ ¬ B^C ¬ A^ B^¬C A^ ¬ B^ C
  • A
  • B
  • C
  • F
  • 0
  • 0
  • 0
  • 0
  • 0
  • 0
  • 1
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • 0
  • 1
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 1
  • 1
  • 1
  • 0
A11 Вариант 2008_04_30
  • Дана таблица истинности выражения F.
  • Какое выражение соответствует F?
  • ¬X ^ Y^Z  X ^ ¬ Y ^Z  X ^ Y ^ ¬ Z
  • X ^ Y^Z  X ^ ¬ Y ^Z  X ^ ¬ Y ^ ¬ Z
  • ¬X ^ Y^Z  X ^ Y ^Z  X ^ ¬ Y ^ Z
  • ¬X ^ ¬ Y^ ¬ Z  ¬ X ^ Y ^Z  X ^ Y ^ ¬ Z
  • Построим булево выражение для данной таблицы истинности:
  • Найдем строки, в которых F=1. Это 1, 4, 7 строки.
  • Для первой строки минтерм:
  • ¬X ^ ¬ Y^ ¬ Z
  • Для четвертой строки минтерм:
  • ¬ X ^ Y ^Z
  • Для седьмой строки минтерм:
  • X ^ Y ^ ¬ Z
  • Объединяя термы, получим булево выражение для F:
  • F = ¬X ^ ¬ Y^ ¬ Z  ¬ X ^ Y ^Z  X ^ Y ^ ¬ Z
  • Таким образом, правильный ответ: 4
  • X
  • Y
  • Z
  • F
  • 0
  • 0
  • 0
  • 1
  • 0
  • 0
  • 1
  • 0
  • 0
  • 1
  • 0
  • 0
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
A9 (базовый уровень, время – 2 мин)
  • Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
  • Дан фрагмент таблицы истинности выражения F:
  • Какое выражение соответствует F?
        • ¬X  ¬Y  ¬Z
        • X  Y  Z
        • X  Y  Z
        • ¬X  ¬Y  ¬Z
Решение (Основной вариант)
  • Нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных.
  • Если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F.
Решение (Основной вариант)
  • Перепишем ответы в других обозначениях:
        • ¬X  ¬Y  ¬Z =
        • X  Y  Z =
        • X  Y  Z =
        • ¬X  ¬Y  ¬Z =
Решение (Основной вариант)
  • Первое выражение, , равно 1 только при , поэтому это неверный ответ (первая строка таблицы не подходит).
  • Второе выражение, , равно 1 только при , поэтому это неверный ответ (первая и вторая строки таблицы не подходят)
  • Решение (Основной вариант)
  • Третье выражение, , равно нулю при , поэтому это неверный ответ (третья строка таблицы не подходит)
  • Решение (Основной вариант)
  • Четвертое выражение, равно нулю только тогда, когда , а в остальных случаях равно 1, что совпадает с приведенной частью таблицы истинности
  • Таким образом, правильный ответ – 4.
  • Решение (Основной вариант)
Частичная таблица истинности для всех выражений имеет следующий вид:
  • Красный крестик показывает, что значение функции не совпадает с F, а знак «–» означает, что вычислять оставшиеся значения не обязательно.
Возможные ловушки и проблемы
  • Серьезные сложности представляет применяемая в заданиях ЕГЭ форма записи логических выражений, поэтому рекомендуется сначала внимательно перевести их в удобный вид.
  • Расчет на то, что ученик перепутает значки  и .
  • В некоторых случаях заданные выражения-ответы лучше сначала упростить, особенно если они содержат импликацию или инверсию сложных выражений.
Решение (вариант 2)
  • Часто правильный ответ – это самая простая функция, удовлетворяющая частичной таблице истинности, то есть, имеющая единственный нуль или единственную единицу в полной таблице истинности.
  • В этом случае можно найти такую функцию и проверить, есть ли она среди данных ответов.
  • В приведенной задаче в столбце F есть единственный нуль для комбинации .
  • Выражение, которое имеет единственный нуль для этой комбинации, это , оно есть среди приведенных ответов (ответ 4).
A9 (базовый уровень, время – 2 мин)
  • Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z.
  • Дан фрагмент таблицы истинности выражения F:
  • Какое выражение соответствует F?
  • 1) ¬X  ¬Y  ¬Z
  • 2) X  Y  Z
  • 3) X  ¬Y  ¬Z
  • 4) X  ¬Y  ¬Z
Решение
  • Перепишем ответы в других обозначениях:
    • ¬X  ¬Y  ¬Z =
    • X  Y  Z =
    • X  ¬Y  ¬Z =
    • X  ¬Y  ¬Z =
  • В столбце F есть единственная единица для комбинации , простейшая функция, истинная (только) для этого случая, имеет вид , она есть среди приведенных ответов.
  • Таким образом, правильный ответ – 3.
Задание А11. Вариант 10 Источник: «Информатика: готовимся к ЕГЭ», Зеленко Л.С., Сопченко Е.В., Самара, 2008
  • База данных «Книги», наряду с другими, имеет поля с названиями «возраст» и «год издания». В базе данных находятся 33 записи о книгах для детей младшего, среднего и старшего школьного возраста. Количество записей N, удовлетворяющих различным запросам, приведено в следующей таблице:
  • Количество записей, удовлетворяющих запросу «возраст = старший и год издания >=2000», равно:
  • 1) 8 2) 6 3) 3 4) 14
  • Запрос
  • N
  • Год издания >= 2000 или возраст <> средний
  • 25
  • Неверно, что (возраст = средний или возраст = младший)
  • 9
  • Год издания < 2000 и возраст <> младший
  • 14
  • 1 шаг. Обращаем внимание на логические операции и операции отношения.
  • Запрос «возраст = старший и год издания >=2000
  • 2 шаг. По закону де Моргана преобразуем вторую строку:
  • НЕ (СРЕД или МЛ) = НЕ СРЕД и НЕ МЛ =9,
  • следовательно старших (СТ) = 9
  • Запрос
  • N
  • Год издания >= 2000 или возраст <> средний
  • 25
  • Неверно, что (возраст = средний или возраст = младший)
  • 9
  • Год издания < 2000 и возраст <> младший
  • 14
  • НЕ (возраст = средний или возраст = младший)
  • 9
  • НЕ (возраст = средний) и НЕ (возраст = младший)
  • 9
  • возраст = старший
  • 9
  • Задание А11. Вариант 10 Источник: «Информатика: готовимся к ЕГЭ», Зеленко Л.С., Сопченко Е.В.,
  • Самара, 2008
  • Запрос «возраст = старший и год издания >=2000
  • 3 шаг. По законам де Моргана и двойного отрицания преобразуем первую строку:
  • Запрос
  • N
  • Год издания >= 2000 или возраст <> средний
  • 25
  • возраст = старший
  • 9
  • Год издания < 2000 и возраст <> младший
  • 14
  • Год издания >= 2000 или возраст <> средний
  • 25
  • НЕ (Год издания >= 2000 или (возраст <> средний))
  • 33-25=8
  • НЕ (Год издания >= 2000) и НЕ (возраст <> средний)
  • 8
  • Год издания < 2000 и возраст = средний
  • 8
  • Задание А11. Вариант 10 Источник: «Информатика: готовимся к ЕГЭ», Зеленко Л.С., Сопченко Е.В.,
  • Самара, 2008
  • Запрос: «возраст = старший и год издания >=2000»
  • 4 шаг. Запрос возраст <> младший соответствует запросу возраст = старший или возраст = средний.
  • Преобразуем третью строку:
  • Запрос
  • N
  • Год издания < 2000 и возраст = средний
  • 8
  • возраст = старший
  • 9
  • Год издания < 2000 и возраст <> младший
  • 14
  • Год издания < 2000 и возраст <> младший
  • 14
  • Год издания < 2000 и (возраст = старший или возраст = средний)
  • 14
  • Задание А11. Вариант 10 Источник: «Информатика: готовимся к ЕГЭ», Зеленко Л.С., Сопченко Е.В.,
  • Самара, 2008
  • Запрос «возраст = старший и год издания >=2000»
  • Варианты ответа: 1) 8 2) 6 3) 3 4) 14
  • 5 шаг. Сравнивая первую и третью строки, делаем вывод, что
  • 6 шаг. Из второй строки известно сколько всего возраст = старший (9).
  • Делаем вывод, что
  • Правильный ответ: 3
  • Запрос
  • N
  • Год издания < 2000 и возраст = средний
  • 8
  • возраст = старший
  • 9
  • Год издания < 2000 и (возраст = старший или возраст = средний)
  • 14
  • Год издания < 2000 и возраст = старший
  • 14-8=6
  • Год издания >= 2000 и возраст = старший
  • 9-6=3
  • Задание А11. Вариант 10 Источник: «Информатика: готовимся к ЕГЭ», Зеленко Л.С., Сопченко Е.В.,
  • Самара, 2008
  • Алгоритм решения логических задач
  • внимательно изучить условие;
  • выделить простые высказывания и обозначить их латинскими буквами;
  • записать условие задачи на языке алгебры логики;
  • составить конечную формулу, для этого объединить логическим умножением формулы каждого утверждения, приравнять произведение единице;
  • упростить формулу, проанализировать полученный результат или составить таблицу истинности, найти по таблице значения переменных, для которых Р = 1, проанализировать результаты.
  • В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях.
  • Один считает, что первой будет Наташа, а Маша будет второй.
  • Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.
  • Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.
  • Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов.
  • Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?
  • (В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.)
  • В школьном первенстве по настольному теннису в четверку лучших вошли девушки: Наташа, Маша, Люда и Рита. Самые горячие болельщики высказали свои предположения о распределении мест в дальнейших состязаниях.
  • Один считает, что первой будет Наташа, а Маша будет второй.
  • Другой болельщик на второе место прочит Люду, а Рита, по его мнению, займет четвертое место.
  • Третий любитель тенниса с ними не согласился. Он считает, что Рита займет третье место, а Наташа будет второй.
  • Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на чемпионате заняли Наташа, Маша, Люда, Рита?
  • (В ответе перечислите подряд без пробелов числа, соответствующие местам девочек в указанном порядке имен.)
  • B6 (повышенный уровень, время – 8 мин) Пример 1 (2007)
  • Н1  М2
  • Л2  Р4
  • Р3  Н2
  • Н1  М2 v Н1  М2 =1
  • Л2  Р4 v Л2  Р4 =1
  • Р3  Н2 v Р3  Н2 =1
  • (Н1  М2 v Н1  М2)  (Л2  Р4 v Л2  Р4 )  (Р3  Н2 v Р3  Н2 ) =
  • (Н1•М2 + Н1•М2) •
  • (Л2•Р4•Р3•Н2 +Л2•Р4•Р3•Н2 + Л2•Р4•Р3•Н2 + Л2•Р4•Р3•Н2) =
  • Н1•М2•Л2•Р4•Р3•Н2 + Н1•М2•Л2•Р4•Р3•Н2 + Н1•М2•Л2•Р4•Р3•Н2 +
  • Н1•М2•Л2•Р4•Р3•Н2 + Н1•М2•Л2•Р4•Р3•Н2 + Н1•М2•Л2•Р4•Р3•Н2 =
  • = Н1•М2•Л2•Р4•Р3•Н2
  • Наташа – 1
  • Маша – 4
  • Люда – 2
  • Рита – 3
  • Ответ: 1423
  • B6 (повышенный уровень, время – 8 мин) Пример 1 (2007)
  • Перед началом Турнира Четырех болельщики высказали следующие предположения по поводу своих кумиров:
  • А) Макс победит, Билл – второй;
  • В) Билл – третий, Ник – первый;
  • С) Макс – последний, а первый – Джон.
  • Когда соревнования закончились, оказалось, что каждый из болельщиков был прав только в одном из своих прогнозов. Какое место на турнире заняли Джон, Ник, Билл, Макс? (В ответе перечислите подряд без пробелов места участников в указанном порядке имен.)
  • B6 (повышенный уровень, время – 8 мин) Пример 2 (2008)
Решение
    • Применим к этой задаче формальный аппарат математической логики.
    • Каждый из трех болельщиков высказал два утверждения, всего получилось 6; обозначим их так:
      • A: М1 = «Макс – первый», Б2 = «Билл – второй»
      • B: Н1 = «Ник – первый», Б3 = «Билл – третий»
      • C: Д1 = «Джон – первый», М4 = «Макс – четвертый»
    • Теперь нужно записать, что у каждого одно высказывание верно, а второе неверно:
  • М1  Б2
  • Б3  Н1
  • М4  Д2
  • М1  Б2 v М1  Б2 =1
  • Б3  Н1 v Б3  Н1 =1
  • М4  Д2 v М4  Д2 =1
Решение
      • (М1 · ¬ Б2 + ¬ М1 · Б2) · (Б3 · ¬Н1+ ¬ Б3 · Н1) ·(М4 · ¬Д1+ ¬ М4 · Д1)
      • =(М1 · ¬ Б2 · Б3 · ¬Н1 + М1 · ¬ Б2 · ¬ Б3 · Н1 + ¬ М1 · Б2 · Б3 · ¬Н1 +
      • + ¬ М1 · Б2 · ¬ Б3 · Н1) ·(М4 · ¬Д1+ ¬ М4 · Д1) =
      • =(М1 · ¬ Б2 · Б3 · ¬Н1+ ¬ М1 · Б2 · ¬ Б3 · Н1) ·(М4 · ¬Д1+ ¬ М4 · Д1)
      • = М1 · ¬ Б2 · Б3 · ¬Н1 · М4 · ¬Д1+ М1 · ¬ Б2 · Б3 · ¬Н1 · ¬ М4 · Д1+
      • + ¬ М1 · Б2 · ¬ Б3 · Н1 · М4 · ¬Д1+ ¬ М1 · Б2 · ¬ Б3 · Н1 · ¬ М4 · Д1 =
      • = ¬ М1 · Б2 · ¬ Б3 · Н1 · М4 , следовательно
      • Ник – первый, Билл – второй, Макс четвертый Джон – третий
  • Ответ: 3124
  • Ё
  • 0
  • 0
  • Ё
  • Ё
  • 0
  • Ё
  • 0
  • 0
  • Классный руководитель пожаловался директору, что у него в классе появилась компания из 3-х учеников, один из которых всегда говорит правду, другой всегда лжет, а третий говорит через раз то ложь, то правду. Директор знает, что их зовут Коля, Саша и Миша, но не знает, кто из них правдив, а кто – нет. Однажды все трое прогуляли урок астрономии. Директор знает, что никогда раньше никто из них не прогуливал астрономию. Он вызвал всех троих в кабинет и поговорил с мальчиками. Коля сказал: «Я всегда прогуливаю астрономию. Не верьте тому, что скажет Саша». Саша сказал: «Это был мой первый прогул этого предмета». Миша сказал: «Все, что говорит Коля, – правда». Директор понял, кто из них кто. Расположите первые буквы имен мальчиков в порядке: «говорит всегда правду», «всегда лжет», «говорит правду через раз». (Пример: если бы имена мальчиков были Рома, Толя и Вася, ответ мог бы быть: РТВ).
  • B6 (повышенный уровень, время – 8 мин) Пример 3 (2009)
Решение (вариант 1)
  • Во-первых, есть «точная» информация, которая не подвергается сомнению: (*) все трое прогуляли урок астрономии в первый раз.
  • Запишем высказывания мальчиков:
  • Коля: 1. Я всегда прогуливаю астрономию.
  • 2. Саша врет.
  • Саша: 1. Я в первый раз прогулял астрономию.
  • Миша:1. Коля говорит правду.
  • Известно, что один из них все время лжет, второй ­– говорит правду, а третий говорит правду через раз (то есть, из двух его высказываний одно истинно, а второе – ложно).
Решение (вариант 1)
  • Коля: 1. Я всегда прогуливаю астрономию.
  • 2. Саша врет.
  • Саша: 1. Я в первый раз прогулял астрономию.
  • Миша:1. Коля говорит правду.
  • Сопоставив первое высказывание Коли (Я всегда прогуливаю астрономию) и высказывание Саши (Я в первый раз прогулял астрономию) с «точной» информацией (*), сразу определяем, то тут Коля соврал, а Саша сказал правду; это значит, что второе высказывание Коли – тоже неверно, поэтому мальчик Коля всегда лжет.
  • Тогда один из оставшихся, Саша или Миша, говорит правду всегда, а второй – через раз.
Решение (вариант 1)
  • Коля: лжет
  • Саша: 1. Я в первый раз прогулял астрономию.
  • Миша:1. Коля говорит правду.
  • Мишино высказывание неверно, поскольку мы уже определили, что Коля лжет; это значит, что Миша не всегда говорит правду, он – «полу-лжец».
  • Тогда получается, что Саша всегда правдив, и действительно, его высказывание верно.
  • Таким образом, верный ответ – СКМ (Саша – правдив, Коля – лжец, Миша – «полу-лжец» ).
Возможные проблемы
  • Длинное запутанное условие, из которого нужно выделить действительно существенную информацию и формализовать ее.
  • Легко по невнимательности перепутать порядок букв в ответе (здесь сначала правдивый, потом – лжец, потом – «полу-лжец»).
  • B6 (повышенный уровень, время – 8 мин) Пример 4 (Вариант №2, 2009)
  • Один из пяти братьев – Никита, Глеб, Игорь, Андрей или Дима – испек маме пирог. Когда она спросила, кто сделал ей такой подарок, братья ответили следующее:
  • Никита: «Пирог испек Глеб или Игорь».
  • Глеб: «Это сделал не я и не Дима».
  • Андрей: «Нет, один из них сказал правду, а другой обманул».
  • Дима: «Нет, Андрей, ты не прав».
  • Мама знает, что трое из сыновей всегда говорят правду. Кто же испек пирог?
  • Решение Пример 4 (Вариант №2, 2009)
  • Обозначим высказывания:
  • F =Г+И Никита: «Пирог испек Глеб или Игорь».
  • K = ¬Г · ¬Д Глеб: «Это сделал не я и не Дима».
  • C = (F · ¬ K) + (¬ F · K) Андрей: «Нет, один из них сказал правду, а другой обманул».
  • W = ¬ C Дима: «Нет, Андрей, ты не прав».
  • Составим таблицу истинности, найдем в ней строку с тремя истинными высказываниями из F, K, C, W.
  • По таблице истинности (см. следующий слайд) пирог испек Игорь.
  • Решение Пример 4 (Вариант №2, 2009)
  • F =Г+И K = ¬Г · ¬Д C = (F · ¬ K) + (¬ F · K) W = ¬ C
  • Г
  • И
  • Д
  • F =Г+И
  • ¬Г
  • ¬Д
  • K = ¬Г · ¬Д
  • ¬ K
  • ¬ F
  • (F · ¬ K)
  • (¬ F · K)
  • C = (F · ¬ K) + (¬ F · K)
  • W = ¬ C
  • 0
  • 0
  • 0
  • 0
  • 1
  • 1
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 0
  • 1
  • 1
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • 1
  • 1
  • 0
  • 0
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 2
  • 3
  • 4
  • B6 (повышенный уровень, время – 8 мин) Пример 5 (Вариант №1, 2009)
  • Три друга – Петр, Роман и Сергей – учатся на математическом (М), физическом (Ф) и химическом (Х) факультетах.
  • Если Петр математик, то Сергей не физик. Если Роман не физик, то Петр – математик. Если Сергей не математик, то Роман – химик.
  • Определите специальность каждого. Ответ запишите в виде строки из трех символов, соответствующих первым буквам названия специальностей Петра, Романа и Сергея (в указанном порядке). Так, например, строка МФК соответствует тому, что Петр – математик, Роман – физик, Сергей – химик.
  • Решение Пример 5 (Вариант №1, 2009)
  • A Петр - математик
  • B Сергей-не физик
  • C Роман физик
  • D Сергей математик D= = ¬B
  • E Роман химик E= ¬C
  • (A ¬B)•(¬C A) •(¬D  E)=
  • = (¬ A+¬B)•(C +A) •(D + E)=
  • = (¬ A+¬B)•(C +A) •(¬B +¬C)=
  • = ¬ B+(¬ A•¬C) •(A+C )= ¬ B=1,
  • Значит B=0,D=1 Сергей математик,
  • Следовательно, A=0
  • ¬C A=1
  • C+A=1
  • C=1 Роман физик, а Петр химик Ответ: ХФМ
  • Три студента Антонов, Волков, Сергеев стремятся сдать сессию на отлично. Были высказаны следующие предположения:
  • сдача экзаменов на отлично студентам Волковым равносильна тому, что сдаст на отлично Антонов или Сергеев;
  • неверно, что сдаст на отлично Волков или одинаково на отлично сдадут Антонов и Сергеев;
  • студент Сергеев не сдаст экзамены на отлично и это притом, что если Антонов сдаст на одни пятерки, то и Волков сдаст так же отлично.
  • После сессии оказалось, что только одно из трех предположений ложно. Кто сдал экзамены на отлично? В ответе укажите первые буквы фамилий студентов. Например, ответ АВС означает, что все трое сдали экзамены на одни пятерки.
  • B6 (повышенный уровень, время – 8 мин) Пример 6 (Вариант №4, 2009)
  • Андрей, Ваня и Саша собрались в поход. Учитель хорошо знавший этих ребят, высказал следующие предположения:
  • Андрей пойдет в поход только тогда, когда пойдут Ваня и Саша.
  • Андрей и Саша друзья, а это значит, что они пойдут в поход вместе или же оба останутся дома.
  • Чтобы Саша пошел в поход, необходимо, чтобы пошел Ваня.
  • Когда ребята пошли в поход, оказалось, что учитель немного ошибся: из трех его утверждений истинными оказались только два. Кто из названных ребят пошел в поход?
  • А В  С
  • А  С v А  С
  • С В
  • А v В  С
  • А  С v А  С
  • С v В
  • 1
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • B6 (повышенный уровень, время – 8 мин) Пример 7
  • А v В  С
  • А  С v А  С
  • С v В
  • 1
  • 1
  • 0
  • 1
  • 0
  • 1
  • 0
  • 1
  • 1
  • (А v В  С)  (А  С v А  С)  (С v В) = 1
  • (А v В  С)  (А  С v А  С)  (С v В) = 1
  • (А v В  С)  (А  С v А  С)  (С v В) = 1
  • Ответ: А  В  С
  • Решение Пример 7
  • Информационные ресурсы
  • «Практикум по информатике и информационным технологиям», Н.Д. Угринович, Л.Л. Босова, М.: Бином. Лаборатория знаний, 2004
  • «Информатика. Задачник- практикум в 2 т.», Под ред. И.Г. Семакина, Е.К. Хеннера, М.: Бином. Лаборатория знаний, 2002
  • «Информатика: готовимся к ЕГЭ», Зеленко Л.С., Сопченко Е.В., Самара, 2008
  • «ЕГЭ 2008. Информатика. Федеральный банк экзаменационных материалов», П.А. Якушкин, С.С. Крылов, М.: Эксмо, 2008
  • «ЕГЭ 2009. Информатика.», Ярцева, Цикина, 2009
  • «ЕГЭ 2009. Информатика - Универсальные материалы для подготовки учащихся», Крылов С.С, Лешинер В.Р, Якушкин П.А.
  • Готовимся к ЕГЭ по информатике - Самылкина Н.Н.
  • ЕГЭ Информатика : Раздаточный материал тренировочных тестов, Гусева И.Ю.
  • ЕГЭ Информатика - ЕГЭ это просто! Молодцов В.А.
  • ЕГЭ 2009 Информатика, Книга Сборник Экзаменационных заданий ЕГЭ 2009 ЭКСМО
  • ЕГЭ 2009 Информатика, ЕГЭ 2009 по информатике от ФИПИ
  • http://kpolyakov.narod.ru
  • http://www.ctege.org - Подготовка к ЕГЭ
  • http://www.websib.ru/noos/informatika/ege.htm - Предметный сайт для учителей информатики.
  • http://pedsovet.su/load/7 - "Сообщество взаимопомощи учителей", раздел по информатике.

Информатика - еще материалы к урокам: