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

Question

[MatveyGogolev]

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

Comments

[Lynn «Кофеман»]

Это ж в любом учебнике написано

Answer 1

[Wataru]

Потому что эти формы - это тупо перечисление всех наборов входных значений, которые дают истину, или ложь (в другой форме). В СДНФ вы получаете слагаемые, объедененные через ИЛИ. Каждое слагаемое через И задает все переменные так, что только вот в конкретном наборе входных данных это слагаемое будет истинно. Раз они все через ИЛИ соединены, то вся функция истинна только если входные значение из нужного набора. Аналогично СКНФ - но там каждая скобочка истина, если входные переменные не равны набору, на котором функция должна давать ложь.

Answer 2

[Alexandroppolus]

Просто посмотри, как они строятся по таблице истинности, и всё станет очевидно

Answer 3

[mayton2019]

Автор вот ты написал СДНФ или СКНФ. Это означает что ты уже читаешь булеву алгебру. И ты уже прошел
основы булевой алгебры. Я не помню где это написано. Честно не помню. Но разве тебя не удивляет что в
математике целое число можно представить в виде суммы других чисел. Или гладкая функция - представима
в виде суперпозиции других гладких функций.

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