Р.В.Шамин. Лекции по информатике. Лекция №5. Тема №2 "Нормальные формы"

• В видео обсуждаются нормальные формы логических функций, которые представляют функции в определенном каноническом виде.  

• Нормальные формы позволяют упростить представление функций и сделать их более компактными.  

• Дезинктивная нормальная форма (ДНФ) - это конъюнкция простых конъюнкций, где каждая переменная встречается не более одного раза.  

• Примеры ДНФ: икс и игрек, икс или не икс, икс или игрек или не зет.  

• Совершенная дезинктивная нормальная форма (СКНФ) - это ДНФ, где каждая простая конъюнкция включает все переменные из списка переменных функции.  

• Примеры СКНФ: икс или игрек, икс и не зет, икс или не икс или не зет.  

• Любую логическую функцию можно представить в виде СКНФ, если она не равна тождественно нулю.  

• Для представления функции, не равной тождественно нулю, нужно представить ее в виде СКНФ.  

• Для этого нужно разбить функцию на наборы переменных, где она принимает значение истины или ложь, и составить из них простую конъюнкцию.  

• Видео объясняет, что для функций можно составить конъюнктивные и дизъюнктивные нормальные формы.  

• Задача состоит в том, чтобы найти такие формы, которые однозначно представляют функцию.  

• Видео объясняет, что можно использовать различные полные наборы функций для выражения других функций.  

• Обычно используются конъюнкция, дизъюнкция и отрицание, но можно использовать и другие наборы.  

• Видео объясняет, что упрощение логических выражений называется минимизацией.  

• Для простых функций можно использовать алгебраические преобразования, но для сложных функций может потребоваться вычислительная помощь.  

• Построение совершенно дезинктивных и совершенно конъюнктивных нормальных форм может быть сложной вычислительной проблемой.