• 

  1 слайд

  Алгебра логики
  СДНФ
  СКНФ
  Полином Жегалкина
  

• 

  2 слайд

  Одна и та же логическая функция может быть представлена в различных формах.
  Одной из таких форм является НОРМАЛЬНАЯ форма.
  
  Нормальная форма существует в двух видах:
  
  1. Конъюнктивная (КНФ) - конъюнкция нескольких дизъюнкций.
  𝑨∨ 𝑩 ∨𝑪 ∧ 𝑨∨𝑪
  
  2. Дизъюнктивная (ДНФ) – дизъюнкция нескольких конъюнкций.
  𝑨∧ 𝑩 ∧𝑪 ∨ 𝑨∧𝑪
  

• 

  3 слайд

  Если КНФ удовлетворяют условиям:
  
  не содержит одинаковых элементарных дизъюнкций;
  ни одна из дизъюнкций не содержит одинаковых переменных;
  каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ,
  
  то такая КНФ называется СОВЕРШЕННОЙ и обозначается
  
  
  СКНФ
  

• 

  4 слайд

  Если ДНФ удовлетворяют условиям:
  
  не содержит одинаковых элементарных конъюнкций;
  ни одна из конъюнкций не содержит одинаковых переменных;
  каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке,
  
  то такая ДНФ называется СОВЕРШЕННОЙ и обозначается
  
  
  СДНФ
  

• 

  5 слайд

  Например:
  
  1. Выражение  
  𝒙∨𝒚 𝒛
  
  является ДНФ, но не СДНФ.
  
  2. Выражение  
  𝒙𝒚𝒛∨𝒙 𝒚 𝒛 ∨ 𝒙 𝒚𝒛
  
  является СДНФ.
  

• 

  6 слайд

  Полином Жегалкина — многочлен  с коэффициентами вида 0 и 1, где в качестве произведения берётся конъюнкция, а в качестве сложения — исключающее или. 
  
  Например,
  𝟏⨁𝒙⨁𝒙 𝒛 ⨁𝒙𝒚𝒛
  

• 

  7 слайд

  Полином Жегалкина можно находить разными способами. Самым простым способом является метод треугольника.
  Метод аналогичен построению треугольника Паскаля.
  
  Для построения треугольника Паскаля пользуемся правилами сложения:
  
  0+0=0
  1+1=0
  1+0=1
  0+1=1
  0 1 1 1 0 0 0 1
  1 0 0 1 0 0 1
  1 0 1 1 0 1
  1 1 0 1 1
  0 1 1 0
  1 0 1
  1 1
  0
  

• 

  8 слайд

  Найти СКНФ, СДНФ, полином Жегалкина можно путём преобразования логической функции или используя таблицу истинности.
  Рассмотрим на конкретных примерах как это сделать.
  
  Очень часто в подобных задачах логическая функция задаётся не формулой, а набором результатов таблицы истинности.
  Например:
  Функция 𝒇 𝒙,𝒚 =𝒙𝒚⨁ 𝒚 ↓𝒙 может быть заданна набором 𝒇 𝒙,𝒚 = 𝟎𝟏𝟎𝟎 .
  
  В наших примерах будем рассматривать функции заданные набором значений таблицы истинности.
  

• 

  9 слайд

  Пример 1.
  Дана функция 𝒇 𝒙,𝒚 = 𝟏𝟎𝟏𝟎 .
  Найти: СДНФ, СКНФ, полином Жегалкина.
  Решение:
  Составим таблицу истинности. Из таблицы выделим две части.
  

• 

  10 слайд

  2. Рассмотрим первую таблицу.
  Значения функции равно 1.
  
  
  Конъюнкция состоит из переменной, если её значение равно 1 и отрицания переменной, если её значение равно 0.
  СДНФ=( 𝒙 ∧ 𝒚 )∨(𝒙∧ 𝒚 )
  
  Или другой вид записи:
  СДНФ= 𝒙 𝒚 ∨𝒙 𝒚
  
  

• 

  11 слайд

  3. Рассмотрим вторую таблицу.
  Значения функции равно 0.
  
  
  Дизъюнкция состоит из переменной, если её значение равно 0 и отрицания переменной, если её значение равно 1.
  СКНФ=(𝒙∨ 𝒚 )∧( 𝒙 ∨ 𝒚 )
  
  Или другой вид записи:
  СКНФ=(𝒙∨ 𝒚 )( 𝒙 ∨ 𝒚 )
  
  

• 

  12 слайд

  4. Построим треугольник Паскаля.
  
  
  Полином Жегалкина равен 𝟏⨁𝐲
  

• 

  13 слайд

  Пример 2. Дано 𝒇 𝒙,𝒚,𝒛 = 𝟎𝟎𝟏𝟎𝟏𝟏𝟏𝟏 .
  Найти: СДНФ, СКНФ, полином Жегалкина.
  
  Решение:
  
  

• 

  14 слайд

  Найдём СДНФ.
  𝒙 𝒚 𝒛 ∨𝒙 𝒚 𝒛 ∨𝒙 𝒚 𝒛∨𝒙𝒚 𝒛 ∨𝒙𝒚𝒛
  

• 

  15 слайд

  Найдём СКНФ.
  (𝒙∨𝒚∨𝒛)(𝒙∨𝒚∨ 𝒛 )(𝒙∨ 𝒚 ∨ 𝒛 )
  
  

• 

  16 слайд

  Найдём полином Жегалкина
  𝒙𝒚𝒛⨁𝒙𝒚⨁𝒙⨁𝒚𝒛⨁𝒚
  

• 

  17 слайд

  Задания для самостоятельного решения.
  Найти СДНФ, СКНФ и полином Жегалкина для следующих функций:
  
  𝒇 𝒙,𝒚 = 𝟏𝟎𝟏𝟏
  𝒇 𝒙,𝒚 = 𝟎𝟏𝟏𝟎
  𝒇 𝒙,𝒚,𝒛 = 𝟏𝟏𝟏𝟏𝟎𝟎𝟎𝟏
  𝒇 𝒙,𝒚,𝒛 = 𝟏𝟏𝟎𝟎𝟏𝟏𝟎𝟎
  𝒇 𝒙,𝒚,𝒛 = 𝟎𝟏𝟎𝟏𝟏𝟎𝟎𝟏
  
  УДАЧИ! ВСЁ ПОЛУЧИТСЯ!
  

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