Известно, что для каждой формулы алгебры высказываний можно составить таблицу истинности. А можно ли по заданной таблице истинности найти соответствующую ей формулу? Оказывается, эта задача также всегда разрешима с помощью СДНФ или СКНФ. Пусть, например, дана таблица истинности некоторой, неизвестной пока формулы F , содержащей переменные x , y , z:. Выделим строки, в которых значение формулы равно 1. Это строки 1, 4 и 8. Для каждой из выделенных строк составим конъюнкцию переменных или их отрицаний так, чтобы наборам значений переменных в выделенных строках соответствовали истинные конъюнкции. Для этого переменные, под которыми в соответствующей строке стоит 0, взять со знаком отрицания, а переменные над 1 — без отрицания. Тот факт, что полученная формула действительно соответствует данной таблице истинности, легко проверить. Если формула F ложна, то ложна и дизъюнкция, так как ложна каждая из составляющих ее конъюнкций. Подобным образом можно составить формулу для всякой таблицы истинности, в последнем столбце которой есть хотя бы одна единица. Очевидно, что одну и ту же таблицу истинности имеет множество равносильных формул. Формула, которая получается в результате применения описанного способа, является совершенной дизъюнктивной формой данной формулы и всех формул с теми же переменными, ей равносильных. Так как для любой формулы можно составить таблицу истинности, и притом, единственную, то всякая формула, не являющаяся тождественно ложной, имеет СДНФ и притом единственную. Формулу, соответствующую данной таблице истинности, можно составить и другим способом, а именно:. FAQ Обратная связь Вопросы и предложения. Upload Опубликованный материал нарушает ваши авторские права? Пусть, например, дана таблица истинности некоторой, неизвестной пока формулы F , содержащей переменные x , y , z: В результате получим конъюнкции: Дизъюнкция этих конъюнкций и есть искомая формула: Формулу, соответствующую данной таблице истинности, можно составить и другим способом, а именно: В результате для данной таблицы получится формула: Каждая формула, не являющаяся тавтологией, имеет СКНФ и притом единственную. Конъюнктивная и дизъюнктивная нормальная форма. Совершенная дизъюнктивная нормальная форма, ее характерные признаки. Совершенная конъюнктивная нормальная форма, ее характерные признаки. Приведение к СДНФ или СКНФ с помощью равносильных преобразований. Получение СДНФ и СКНФ по таблице истинности произвольной формулы. Единственность СДНФ и СКНФ для формул алгебры высказываний.
Таблица истинности
Объяснительная записка воспитателя
Население на рынке ценных бумаг
Магазин делает пенсионерам