• 

  1 слайд

  Логические задачи
  Подготовка к ЕГЭ
  Задача А3,А10,В12,B15
  Автор: Керженова М.З.
  

• 

  2 слайд

  Содержание
  План подготовки к ЕГЭ
  Базовые знания по теме «Логика»
  Методика решения некоторых логических задач
  Дополнительная литература и сайты по теме ЕГЭ
  

• 

  3 слайд

  Основные знания по теме «Логика»
  Базовые логические операции НЕ, И, ИЛИ
  А
  не А
  0
  1
  1
  0
  A
  B
  А и B
  0
  0
  0
  0
  1
  0
  1
  0
  0
  1
  1
  1
  A
  B
  А или B
  0
  0
  0
  0
  1
  1
  1
  0
  1
  1
  1
  1
  Дополнительные логические операции
  A
  B
  А  B
  0
  0
  0
  0
  1
  1
  1
  0
  1
  1
  1
  0
  A
  B
  А  B
  0
  0
  1
  0
  1
  1
  1
  0
  0
  1
  1
  1
  A
  B
  А  B
  0
  0
  1
  0
  1
  0
  1
  0
  0
  1
  1
  1
  Исключающее ИЛИ
  Импликация
  Эквивалентность
  

• 

  4 слайд

  Основные знания по теме «Логика»
  

• 

  5 слайд

  Приоритет логических операций :
  вычисление в скобках
  НЕ, И, ИЛИ, исключающее ИЛИ
  импликация
  эквивалентность
  Основные знания по теме «Логика»
  Замена операций
    
  через И, ИЛИ и НЕ:
  Формулы де Моргана:
  

• 

  6 слайд

  Построение таблиц истинности логических выражений*
  
  Разбор задачи A3
  
  Задание А3. Задача. Дан фрагмент таблицы истинности выражения F.
  Какое выражение соответствует F?
  1) (X  Y)  ¬Z 2) ¬X  Y  Z 3) X  Y  ¬Z 4) X  ¬Y  Z
  

• 

  7 слайд

  Решение:
  нужно для каждой строчки подставить заданные значения X, Y и Z во все функции, заданные в ответах, и сравнить результаты с соответствующими значениями F для этих данных
  если для какой-нибудь комбинации X, Y и Z результат не совпадает с соответствующим значением F, оставшиеся строчки можно не рассматривать, поскольку для правильного ответа все три результата должны совпасть со значениями функции F
  Из полученной таблицы видно, что F соответствует выражение 1: (X  Y)  ¬Z (выделено зеленым). Значения остальных выражений не совпадают с F (выделено розовым).
  

• 

  8 слайд

  Каким из приведённых ниже выражений может быть F?
  ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
  ¬x1 \/ x2 \/ ¬x3 \/ x4 \/ ¬x5 \/ ¬x6 \/ x7
  x1 /\ ¬x2 /\ x3 /\ ¬x4 /\ x5 /\ x6 /\ ¬x7
  x1 \/ ¬x2 \/ x3 \/ ¬x4 \/ ¬x5 \/ x6 \/ ¬x7
  
  Дан фрагмент таблицы истинности выражения F.
  Разбор задачи A3
  
  Построение таблиц истинности логических выражений*
  
  

• 

  9 слайд

  Решение:
  Сначала определим, как связаны переменные в F: с помощью конъюнкции (Λ) или дизъюнкции (V).
  Если выражение содержит только конъюнкции, то оно может быть истинно только на одной области.
  В данном случае F истинна (равна 1) на одной области (область №3 в таблице выше), поэтому начнем с проверки выражений, содержащих конъюнкции. Это вариант 1 и вариант 3.
  Получили вариант 1: ¬x1 /\ x2 /\ ¬x3 /\ x4 /\ x5 /\ ¬x6 /\ ¬x7
  

• 

  10 слайд

  Разбор задачи A10
  На числовой прямой даны два отрезка: P = [2, 10] и Q = [6, 14]. Выберите такой отрезок A, что формула
  ( (x ∈ А) → (x ∈ P) ) \/ (x ∈ Q)
  тождественно истинна, то есть принимает значение 1 при любом значении переменной х.
  [0, 3]
  [3, 11]
  [11, 15]
  [15, 17]
  
  

• 

  11 слайд

  Решим уравнение: ( (x ∈ А) → (x ∈ P) ) \/ (x ∈ Q)=1 методом подстановки.
  В уравнение вместо P, Q впишем сами отрезки: [2, 10] и [6, 14].
  (x ∈ А)=1 для всех вариантов.
  

• 

  12 слайд

  Задание А10. Задача: Для какого имени истинно высказывание:
  ¬ (Первая буква имени гласная → Четвертая буква имени согласная)?
  1) ЕЛЕНА2) ВАДИМ3) АНТОН4) ФЕДОР
  

• 

  13 слайд

  Решение (рассуждения):
  Запишем выражение: ¬ (1Г → 4С) 1
  перед выражением стоит отрицание, при котором высказывание истинно, значит без отрицания выражение в скобках должно быть ложно: 1Г → 4С  0
  импликация ложна, если ее первая часть («посылка») истинна, а вторая («следствие») – ложна:
  1Г  1 4С  0
  первое условие истинно, когда первая буква гласная, то есть для ответов 1 и 3
  второе условие «четвертая буква согласная» ложно тогда, когда четвертая буква гласная, то есть, для ответа 3: 4Г  1
  таким образом, для варианта 3 исходное условие в целом истинно
  ответ: 1.
  

• 

  14 слайд

  Разбор задачи B12
  В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&».
  В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
  
  Какое количество страниц (в тысячах) будет найдено по запросу Эсминец?
  Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
  

• 

  15 слайд

  Решение:
  Изобразим запросы в виде диаграмм Эйлера-Венна.
  Запрос "Фрегат" обозначим символом "Ф", "Эсминец" - символом "Э".
  
  Э=(Ф|Э)-Ф+(Ф&Э)=3400-2100+900=2200.
  

• 

  16 слайд

  I. Простая задача, решаемая с методом рассуждений:
  Сколько различных решений имеет уравнение
  (K  L  M)  (¬L  ¬M  N) = 1
  N-любое (0 или 1)
  
  K-любое, L=0, M=0, N=1, всего два решения
  Примеры решения задач
  Итого 7 х 2 = 14 решений
  Есть только одно совпадающее решение
  K=1, L=0, M=0, N=1
  Сколько будет решений,
  если заменить  →  ?
  

• 

  17 слайд

  Задание В 15. Задача. Сколько различных решений имеет уравнение (M N)  ((N  K)  (¬L M))0, где K,L,M,N - логические переменные.
  Решение (вариант 2, составление таблицы истинности):
  нужно для каждой строчки подставить значения K,L,M,N и вычислить значение функции
  для четырех комбинаций K,L,M,N результат будет ложным. Ответ: 4.
  

• 

  18 слайд

  II. Задача, решаемая с методом рассуждений:
  Сколько различных решений имеет уравнение
  (X1  X2)(X2  X3)(X3  X4)(X4  X5) = 1
  Все скобки
  должны быть равны 1
  Операция импликации дает только одно решение = 0, когда 1  0,
  то есть нельзя, чтобы после 1 был 0
  Примеры решения задач
  Вывод:
  Количество решений на единицу больше количества переменных (6 реш.)
  
  Если X1…X10, то количество решений будет равно 11
  

• 

  19 слайд

  III. Задача, решаемая с помощью замены переменных:
  Сколько различных решений имеет система уравнений
  ((x1 ≡ x2)  (x3 ≡ x4))  (¬(x1 ≡ x2)  ¬(x3 ≡ x4)) =1
  ((x3 ≡ x4)  (x5 ≡ x6))  (¬(x3 ≡ x4)  ¬(x5 ≡ x6)) =1
  ((x5 ≡ x6)  (x7 ≡ x8))  (¬(x5 ≡ x6)  ¬(x7 ≡ x8)) =1
  ((x7 ≡ x8)  (x9 ≡ x10))  (¬(x7 ≡ x8)  ¬(x9 ≡ x10)) =1
  Примеры решения задач
  t1 = (x1 ≡ x2)
  t2 = (x3 ≡ x4)
  t3 = (x5 ≡ x6)
  t4 = (x7 ≡ x8)
  t5 = (x9 ≡ x10)
  Произведем замену:
  Перепишем уравнения, заметим, что уравнения = 1, когда t1 ≠ t2
  ( t1  t2 )  ( ¬ t1  ¬ t2) =1
  ( t2  t3 )  ( ¬ t2  ¬ t3) =1
  ( t3  t4 )  ( ¬ t3  ¬ t4) =1
  ( t4  t5 )  ( ¬ t4  ¬ t5) =1
  

• 

  20 слайд

  Поскольку значения переменных в скобках должны быть разными, они будут чередоваться:
  Примеры решения задач
  t1 = (x1 ≡ x2)
  t2 = (x3 ≡ x4)
  t3 = (x5 ≡ x6)
  t4 = (x7 ≡ x8)
  t5 = (x9 ≡ x10)
  Для каждой комбинации из 5-ти значений t1 … t5 существует по 2 решения:
  если t1 = 0, то x1 =1, x2 =0
  или x1 =0, x2 =1
  если t1 = 1, то x1 =1, x2 =1
  или x1 =0, x2 =0
  
  ( t1  t2 )  ( ¬ t1  ¬ t2) =1
  ( t2  t3 )  ( ¬ t2  ¬ t3) =1
  ( t3  t4 )  ( ¬ t3  ¬ t4) =1
  ( t4  t5 )  ( ¬ t4  ¬ t5) =1
  Получим 2 решения:
  То есть 2 варианта по 5 переменным дают 25=32 решения, 32+32=64
  

• 

  21 слайд

• 

  22 слайд

  Источники дополнительных сведений
  ФИПИ http://www.fipi.ru/view
  Открытый сегмент ЕГЭ http://www.fipi.ru/view/sections/160/docs/
  КИМ ЕГЭ по информатике http://www.fipi.ru/view/sections/226/docs/627.html
  Сайт на Яндексе www.ege.yandex.ru
  

Краткое описание материала