Решение логических уравнений и систем логических уравнений

• 1 слайд

  Решение систем логических уравнений
  (задача 23 ЕГЭ)
  Моисеева Ольга Михайловна
  учитель информатики
  МАОУ СОШ №94 города Тюмени
  

• 2 слайд

  Используемые обозначения
  ¬Отрицание
  /\ Умножение (конъюнкция)
  VСложение (дизъюнкция)
    Импликация
  ≡Эквивалентность
  

• 3 слайд

  Основные логические операции
  Отрицание
  Инверсия
  Умножение
  Конъюнкция
  Сложение
  Дизъюнкция
  Импликация
  Эквиваленция
  

• 4 слайд

  Формулы преобразования
  дистрибутивность конъюнкции относительно дизъюнкции;
  A /\ (B V C) = (A /\ B) V (A /\ C)
  дистрибутивность дизъюнкции относительно конъюнкции;
  A V (B /\ C) = (A V B) /\ (A V C)
  законы де Моргана;
  ¬(A /\ B) = ¬A V ¬B 
  ¬(A V B) = ¬A /\ ¬B
  замена импликации;
  A  B = ¬A V B
  замена эквивалентности;
  A ≡ B = (A V ¬B) /\ (¬AVB) A ≡ B = (A /\ B) V (¬A /\ ¬B)
  законы поглощения
  A /\ (A V B) = A, A V (A /\ B)=A
  законы склеивания
  (A V B) /\ (¬A V B) = A, (A /\ B) V (¬A /\ B) = A
  законы Порецкого A V ¬A /\ B = A V B, A /\ ¬A V B = A /\ B
  

• 5 слайд

  Простые уравнения
  Задачи с импликациями
  Замена переменных
  Метод отображения
  План решения задач:
  

• 6 слайд

  (K /\ L /\ M) V(¬L /\ ¬M /\ N)=1
  J /\ ¬K /\ L /\ ¬M /\ (N V ¬N)=0
  ((J K) (L /\ M /\ N)) V ¬((L /\ M /\ N)  (¬J V K)) V (M /\ J)=0
  (((K /\ ¬L /\ ¬N)  (¬L M)) V ((¬K V L V N) (¬L /\ ¬M))) /\(K V N)=1
  Решение простых уравнений
  

• 7 слайд

  Задачи с импликациями
  

• 8 слайд

  Первая система, которую надо научится решать,
  может иметь следующий вид:
  или это одно уравнение вида:
  где Х1-Х10 – логические переменные
  X2X1 = 1
  X3X2 = 1
  X4X3 = 1
  …
  X10X9 =1
  X1 V ¬ X2 = 1
  X2 V ¬ X3 = 1
  X3 V ¬ X4 = 1
  …
  X9 V ¬ X10 =1
  (X2  X1) /\ (X3  X2) /\ … /\ (Xn  X(n-1) ) =1
  

• 9 слайд

  
  X2  X1 =1 (1)
  X3  X2 =1 (2)
  X4  X3 =1 (3)
  …
  X10  X9 =1 (9) 
  Будем использовать табличный способ решения
  Пусть X1 = 0,
  Импликация
  Пусть теперь X1 = 1, а X2 = 0,
  

• 10 слайд

  Если же X1 = 1, и X2 = 1, а X3 = 0,
  Рассуждая аналогично и занося все решения в таблицу, получим 11 решений (наборов).
  

• 11 слайд

  Если же система будет такого вида, то количество решений будет 11, но вид таблицы немного изменится.
  
  X1  X2 =1 (1)
  X2  X3 =1 (2)
  X3  X4 =1 (3)
  …
  X9  X10 =1 (9) 
  Нам теперь известно количество решений подобных систем и равно оно n+1 (n-количество переменных)
  
  

• 12 слайд

  (X1  X2) /\ (X2  X3 ) /\ … /\(X6  X7)=1 (1)
  (Y1  Y2) /\ (Y2  Y3 ) /\ … /\(Y6  Y7)=1 (2)
  X1  Y1=1 (3)
  Сколько решений имеет система (2 уравнения):
  Решение (1) уравнения
  
  Решение (2) уравнения
  
  8
  Решение.
  Т.к. множества решений решений уравнений 1 и 2 не пересекаются, то количество решений системы уравнений будет равно 8*8=64
  

• 13 слайд

  (X1  X2) /\ (X2  X3 ) /\ … /\(X6  X7)=1 (1)
  (Y1  Y2) /\ (Y2  Y3 ) /\ … /\(Y6  Y7)=1 (2)
  X1  Y1=1 (3)
  Решение (1) уравнения
  
  Решение (2) уравнения
  
  8
  Сколько решений имеет система (3 уравнения):
   X1≠1, а при этом Y1≠0
  Решений 8*8 =64
  (X1  X2) /\ (X2  X3 ) /\ … /\(X6  X7)=1 (1)
  (Y1  Y2) /\ (Y2  Y3 ) /\ … /\(Y6  Y7)=1 (2)
  X1  Y1=1 (3)
  7
  Число решений всей системы
  64 – 1*7 = 57
  

• 14 слайд

  (X1  X2) /\ (X2  X3 ) /\ … /\(X6  X7)=1 (1)
  (Y1  Y2) /\ (Y2  Y3 ) /\ … /\(Y6  Y7)=1 (2)
  X1  Y1=0 (3)
  Решение (1) уравнения
  
  Решение (2) уравнения
  
  Решений 8*8 =64
  7
  В итоге, число решений всей системы:
  = 7
  1*7
   X1=1 и Y1=0
  Сколько решений имеет система (3 уравнения):
  (X1  X2) /\ (X2  X3 ) /\ … /\(X6  X7)=1 (1)
  (Y1  Y2) /\ (Y2  Y3 ) /\ … /\(Y6  Y7)=1 (2)
  X1  Y1=0 (3)
  

• 15 слайд

  Замена переменных
  

• 16 слайд

  Сколько различных решений имеет система уравнений
  ((X1 ≡X2) /\ (X3 ≡X4)) V (¬(X1 ≡X2) /\ ¬(X3 ≡X4)) = 0
  ((X3 ≡X4) /\ (X5 ≡X6)) V (¬(X3 ≡X4) /\ ¬(X5 ≡X6)) = 0
  ((X5 ≡X6) /\ (X7 ≡X8)) V (¬(X5 ≡X6) /\ ¬(X7 ≡X8)) = 0
  ((X7 ≡X8) /\ (X9 ≡X10)) V (¬(X7 ≡X8) /\ ¬(X9 ≡X10)) = 0
  Сделаем замену переменных
  А1= X1≡X2 А2= X3≡X4 А3= X5≡X6 А4= X7≡X8 А5= X9≡X10
  Рассмотрим первое уравнение с учетом замен
  (А1 /\ А2) V (¬А1 /\ ¬А2) = 0
  Из таблицы видно, что левая часть уравнения это А1≠А2.
  Рассматривая аналогично остальные уравнения, получим систему вида
  А1≠А2
  А2≠А3
  А3≠А4
  А4≠А5
  

• 17 слайд

  А1≠А2
  А2≠А3
  А3≠А4
  А4≠А5
  Построим таблицу
  Всего 64 решения
  Каждая эквиваленция дает 2 решения.
  

• 18 слайд

  Сколько различных решений имеет система уравнений
  ((X1 X2) /\ (X3 X4)) V (¬(X1 X2) /\ ¬(X3 X4)) = 0
  ((X3 X4) /\ (X5 Х6)) V (¬(X3 X4) /\ ¬(X5 X6)) = 0
  ((X5 X6) /\ (X7 X8)) V (¬(X5 X6) /\ ¬(X7 X8)) = 0
  ((X7 X8) /\ (X9 X10)) V (¬(X7 X8) /\ ¬(X9 X10)) = 0
  Аналогично предыдущей системе делаем замену переменных
  А1= X1X2 А2= X3X4 А3= X5X6 А4= X7X8 А5= X9X10
  А1≠А2
  А2≠А3
  А3≠А4
  А4≠А5
  Построим таблицу
  Всего 64 решения
  Всего 36 решений
  

• 19 слайд

  Сколько решений имеет система:
  (X1 ≡ X2) V (X1 ≡ X3 ) =1
  (X2 ≡ X3) V (X2 ≡ X4 ) =1
  …
  (X8 ≡ X9) V (X8 ≡ X10) =1
  Здесь замена переменных не получается и на помощь приходит метод отображений.
  

• 20 слайд

  Метод отображений
  Автор метода Мирончик Е.А.,
  МБ НОУ «Лицей №111», г. Новокузнецк.
  

• 21 слайд

  Сколько различных решений имеет система уравнений
  Х1 V Х2 = 1
  Х2 V Х3 = 1
  Х3 V Х4 = 1
  Х4 V Х5 = 1
  Рассмотрим первое уравнение Х1 V Х2 = 1. Мы знаем, что у него 3 решения
  Каждая переменная имеет два допустимых значения.
  Проиллюстрируем это следующим образом:
  Эта связь помогает нам считать решения
  Если в уравнении имеется N решений для Х1=0, то эти N решений имеются и для Х2=1.
  Если у нас есть К решений для Х1=1, то эти К решений есть и для Х2=0 и для Х2=1
  

• 22 слайд

  Теперь полученную схему нужно обобщить для всей системы.
  Данная система состоит из 4-х уравнений, каждое уравнение состоит из двух переменных, все уравнения связаны между собой.
  Всего 13 решений
  

• 23 слайд

• 24 слайд

  Сколько различных решений имеет система уравнений
  Построим таблицу истинности первого уравнения.
  Затем построим отображение Х1Х2 в Х3Х4
  

• 25 слайд

  Всего решений 346
  

• 26 слайд

• 27 слайд

  Всего решений 1013
  Построим таблицу истинности для первого уравнения и построим отображение Х1Y1 в X2Y2
  

• 28 слайд

  Отличие от предыдущей системы в последнем уравнении, которое накладывает ограничения на количество решений: нам необходимо вычеркнуть те решения, которые не удовлетворяют уравнению X8 Y8=1, а именно набор 10.
  Всего решений 1005
  

• 29 слайд

  Рекомендуемые ссылки
  http://kpolyakov.spb.ru/download/ege23/doc
  http://kpolyakov.spb.ru/download/mea-2016-8.pdf
  http://kpolyakov.spb.ru/download/mea-2013-10.pdf
  https://www.youtube.com/watch?v=aQCYn9kraKo&t=2s&list=PL-joPVQJyHSuyq_qDcF-YGqMKpjNSRvES&index=5
  https://vk.com/informatics_100
  https://inf-ege.sdamgia.ru