@MatveyGogolev

Почему любую булеву функцию можно представить в виде СДНФ или СКНФ?

Почему любую булеву функцию можно представить в виде СДНФ или СКНФ? Как это доказать?
  • Вопрос задан
  • 165 просмотров
Пригласить эксперта
Ответы на вопрос 3
wataru
@wataru Куратор тега Математика
Разработчик на С++, экс-олимпиадник.
Потому что эти формы - это тупо перечисление всех наборов входных значений, которые дают истину, или ложь (в другой форме). В СДНФ вы получаете слагаемые, объедененные через ИЛИ. Каждое слагаемое через И задает все переменные так, что только вот в конкретном наборе входных данных это слагаемое будет истинно. Раз они все через ИЛИ соединены, то вся функция истинна только если входные значение из нужного набора. Аналогично СКНФ - но там каждая скобочка истина, если входные переменные не равны набору, на котором функция должна давать ложь.
Ответ написан
Комментировать
Alexandroppolus
@Alexandroppolus
кодир
Просто посмотри, как они строятся по таблице истинности, и всё станет очевидно
Ответ написан
Комментировать
mayton2019
@mayton2019
Bigdata Engineer
Автор вот ты написал СДНФ или СКНФ. Это означает что ты уже читаешь булеву алгебру. И ты уже прошел
основы булевой алгебры. Я не помню где это написано. Честно не помню. Но разве тебя не удивляет что в
математике целое число можно представить в виде суммы других чисел. Или гладкая функция - представима
в виде суперпозиции других гладких функций.

Я не знаю какое нужно притащить доказательство чтобы обобщать этот тезис на любую функцию. Но начни
с простых функций - и просто индуктивно увидишь что для любой функции всегда можно создать формулу.
Хотя она может быть длинной и некрасивой.
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы