Презентация по математике на тему "Монотонные булевы функции"

• 1 слайд

  Монотонные булевы функции
  Авторы презентации:
  преподаватель математики
  ГПОУ ЯО ЯГК
  Холманова Вероника Михайловна
  
  M
  

• 2 слайд

  Отношение предшествовать на B
  M
  
  По аналогии с отношением «меньше или равно»на рассмотрим отношение «предшествовать» на B
  
  
  
  

• 3 слайд

  Отношение предшествовать на Bn
  M
  На Bn элемент будет предшествовать элементу , когда выполняется «покоординатное» предшествование, то есть:
  для всех
  
  
  𝑎=( 𝑎 1 , 𝑎 2 , 𝑎 3 , …, 𝑎 𝑛 )
  𝛽=( 𝛽 1 , 𝛽 2 , 𝛽 3 , …, 𝛽 𝑛 )
  (𝑎≺𝛽)
  𝑖= 1,𝑛 .
  𝑎 𝑖 ≺ 𝛽 𝑖
  

• 4 слайд

  Отношение предшествовать на Bn
  M
  
  
  
  
  
  ?
  

• 5 слайд

  M
  Сравнимые элементы Bn
  Два элемента и называются сравнимыми между собой, если либо первый из них предшествует второму, либо второй предшествует первому, то есть: или
  
  𝒂 ∈ 𝑩 𝒏
  𝜷 ∈ 𝑩 𝒏
  𝑎≺𝛽
  𝛽≺𝑎.
  Элементы (01) и (10) – несравнимые элементы B2
  

• 6 слайд

  Класс монотонных булевых функций обозначается символом M.
  
  Булева функция n переменных называется монотонной, если для любых двух её аргументов, сравнимых между собой, из того, что первый предшествует второму следует, что значение функции на первом аргументе предшествует значению функции на втором аргументе:
  
  M
  𝑓 𝑎 1 , 𝑎 2 , 𝑎 3 , …, 𝑎 𝑛 ≺𝑓 𝛽 1 , 𝛽 2 , 𝛽 3 , …, 𝛽 𝑛 .
  
  𝑎 1 , 𝑎 2 , 𝑎 3 , …, 𝑎 𝑛 ≺( 𝛽 1 , 𝛽 2 , 𝛽 3 , …, 𝛽 𝑛 )
  
  Монотонные булевы функции
  

• 7 слайд

  Проверку на монотонность удобно осуществлять для булевой функции, заданной таблицей значений.
  Если выполнены все условия определения, функция принадлежит классу монотонных булевых функций:
  𝒇∈𝑴.
  Если найдутся любые два сравнимые между собой её аргумента, первый из которых будет предшествовать второму, а значение функции на первом аргументе не будет предшествовать значению функции на втором, то данному классу функция принадлежать не будет:
  𝒇𝑴.
  Монотонные булевы функции
  M
  

• 8 слайд

  Задача: исследовать функцию на принадлежность к классу монотонных булевых функций.
  
  
  Исследование булевой функции на монотонность
  M
  𝑓=(0011)
  

• 9 слайд

  0
  0
  1
  1
  0
  1
  1
  0
  1
  1
  0
  0
  Вектор задаёт булеву функцию двух переменных
  Исследование булевой функции на монотонность
  M
  𝑓=(0011)
  

• 10 слайд

  0
  0
  1
  1
  0
  1
  1
  0
  1
  1
  0
  0
  Исследование булевой функции на монотонность
  M
  𝑓=(0011)
  

• 11 слайд

  0
  0
  1
  1
  0
  1
  1
  0
  1
  1
  0
  0
  
  Исследование булевой функции на монотонность
  M
  𝑓=(0011)
  𝒇∈𝑴
  

• 12 слайд

  Отсутствие в булевом векторе после единиц нулей является достаточным условием монотонности булевой функции, заданной вектором
  Исследование булевой функции на монотонность
  M
  (по достаточному условию монотонности)
  𝒇∈𝑴
  f=(00000111),
  𝒇∈𝑴
  

• 13 слайд

  Достаточное условие монотонности функции, заданной булевым вектором, не является необходимым.
  Исследование булевой функции на монотонность
  M
  f
  =
  (0
  1
  0
  1)
  0
  0
  1
  1
  0
  1
  1
  0
  1
  1
  0
  0
  𝒇∈𝑴
  

• 14 слайд

  Исследование булевой функции на монотонность
  M
  Если после единиц в булевом векторе присутствуют нули, функция нуждается в проверке на монотонность по определению
  Булева функция может быть как монотонной, так и немонотонной
  

• 15 слайд

  Задача: исследовать функцию на принадлежность к классу монотонных булевых функций
  
  
  Исследование булевой функции на монотонность
  M
  

• 16 слайд

  Зададим булеву функцию таблицей значений
  
  
  Исследование булевой функции на монотонность
  M
  𝒇 𝒙,𝒚,𝒛 = 𝒙𝒚∨𝒚𝒛∨ 𝒛
  0
  0
  0
  0
  0
  0
  0
  0
  1
  1
  1
  1
  1
  1
  1
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  0
  0
  0
  1
  1
  0
  0
  1
  0
  1
  0
  1
  0
  1
  0
  0
  0
  0
  1
  0
  1
  0
  1
  1
  0
  1
  1
  1
  0
  1
  1
  0
  1
  0
  0
  0
  1
  0
  0
  0
  1
  0
  0
  0
  1
  0
  0
  

• 17 слайд

  
  Исследование булевой функции на монотонность
  M
  f=(01000100)
  

• 18 слайд

  
  Исследование булевой функции на монотонность
  M
  0
  0
  0
  0
  0
  0
  0
  0
  1
  1
  1
  1
  1
  1
  1
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  0
  0
  0
  1
  1
  0
  0
  1
  0
  1
  0
  1
  0
  1
  0
  0
  0
  0
  1
  0
  1
  0
  1
  1
  0
  1
  1
  1
  0
  1
  1
  0
  1
  0
  0
  0
  1
  0
  0
  0
  1
  0
  0
  0
  1
  0
  0
  Второй и третий аргументы не сравнимы между собой
  
  

• 19 слайд

  
  Исследование булевой функции на монотонность
  M
  0
  0
  0
  0
  0
  0
  0
  0
  1
  1
  1
  1
  1
  1
  1
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  1
  0
  0
  0
  1
  0
  0
  
  
  001 ≺ 011 .
  𝑓 001 ⊀𝑓 011
  𝒇∉𝑴
  

Краткое описание документа:

В презентации "Монотонные булевы функции" представлен основной теоретический материал, рассматриваются примеры монотонных и немонотонных булевых функций двух и трёх переменных, заданных аналитически, таблицей значений и булевым вектором.

Работа может быть использована учителем для организации факультативных занятий по математике или информатике в 11 классе в рамках изучения темы "Функции алгебры логики".