что такое сднф в информатике

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

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

Среди нормальных форм выделяются совершенные нормальные формы (такие формы, в которых функции записываются единственным образом).

Совершенная дизъюнктивная нормальная форма (СДНФ)

Определение. Формулу называют элементарной конъюнкцией, если она образованна конъюнкцией некоторого числа переменных или их отрицаний.

Определение. Формула называтся дизъюнктивной нормальной формой (ДНФ), если она является дизъюнкцией неповторяющихся элементарных конъюнкций.

Определение. Логическая формула от k переменных называется совершенной дизъюнктивной нормальной формой (СДНФ), если:
1) формула является ДНФ, в которой каждая элементарная конъюнкция есть конъюнкция k переменных х1, х2, …, хk, причем на i-м месте этой конъюнкции стоит либо переменная хi, либо ее отрицание;
2) все элементарные конъюнкции в такой ДНФ попарно различны.

Совершенная конъюнктивная нормальная форма (СКНФ)

Определение. Формулу называют элементарной дизъюнкцией, если она образована дизъюнкцией некоторого числа переменных или их отрицаний.

Определение. Формула называется конъюнктивной нормальной формой (КНФ), если она является конъюнкцией неповторяющихся элементарных дизъюнкций.

Определение. Логическая формула от k переменных называется совершенной конъюнктивной нормальной формой (КДНФ), если:
1) формула является КНФ, в которой каждая элементарная дизъюнкция есть дизъюнкция k переменных х1, х2, …, хk, причем на i-м месте этой дизъюнкции стоит либо переменная хi, либо ее отрицание;
2) все элементарные дизъюнкции в такой КНФ попарно различны.

Алгоритм построения СДНФ по таблице истинности

Алгоритм построения СКНФ по таблице истинности

Пример: Дана таблица истинности логической функции от трех переменных. Построить логическую формулу, реализующую эту функцию.

xyzF (x, y, z)
0001
0011
0101
0111
1000
1010
1101
1111

Т.к. на большинстве строк таблицы истинности значение функции равно 1, то построим СКНФ. В результате получим следующую логическую формулу:
F = (¬ x ∨ y ∨ z) ∧ (¬ x ∨ y ∨ ¬ z)

Проверим полученную формулу. Для этого построим таблицу истинности функции.

xyz¬ x¬ x ∨ y ∨ z¬ z¬ x ∨ y ∨ ¬ zF (x, y, z)
00011111
00111011
01011111
01111011
10000110
10101000
11001111
11101011

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

Copyright © 2014-2021, Урок информатики
Все права защищены

Источник

Построение СКНФ и СДНФ по таблице истинности

Вы будете перенаправлены на Автор24

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

Нормальная форма существует в двух видах:

не содержит одинаковых элементарных дизъюнкций;

ни одна из дизъюнкций не содержит одинаковых переменных;

каждая элементарная дизъюнкция содержит каждую переменную из входящих в данную КНФ.

Любая булева формула, которая не является тождественно истинной, может быть представлена в СКНФ.

Правила построения СКНФ по таблице истинности

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

не содержит одинаковых элементарных конъюнкций;

ни одна из конъюнкций не содержит одинаковых переменных;

каждая элементарная конъюнкция содержит каждую переменную из входящих в данную ДНФ, к тому же в одинаковом порядке.

Любая булева формула, которая не является тождественно ложной, может быть представлена в СДНФ, к тому же единственным образом.

Правила построения СДНФ по таблице истинности

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

Примеры нахождения СКНФ и СДНФ

Записать логическую функцию по ее таблице истинности:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Решение:

Воспользуемся правилом построения СДНФ:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

\[F\left(x_1,\ x_2,\ x_3\right)=\left(\overline\wedge \overline\wedge \overline\right)\vee \left(\overline\wedge \overline\wedge x_3\right)\vee \left(x_1\wedge \overline\wedge \overline\right)\vee \left(x_1\wedge \overline\wedge x_3\right)\vee \left(x_1\wedge x_2\wedge x_3\right)\]

Воспользуемся правилом построения СКНФ:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

\[F\left(x_1,\ x_2,\ x_3\right)=\left(x_1\vee \overline\vee x_3\right)\wedge \left(x_1\vee \overline\vee \overline\right)\wedge \left(\overline\vee \overline\vee x_3\right)\]

Готовые работы на аналогичную тему

Функция задана таблицей истинности:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Представить эту функцию в виде СДНФ и СКНФ.

Решение:

Запишем логическую функцию в СДНФ. Для удобства решения добавим к таблице вспомогательный столбец.

Используя правило составления СДНФ не забываем вводить знак отрицания для переменных со значением 0. Инвертировать нулевые значения переменных обязательно, т.к. иначе они превратят значения конъюнкций в нули основной функции.

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Полученные во вспомогательном столбце конъюнкции соединим знаком дизъюнкции и получим искомую логическую функцию в виде СДНФ:

\[F\left(x_1,x_2,x_3,x_4\right)=\left(\overline\wedge \overline\wedge z\wedge f\right)\vee \left(\overline\wedge x_2\wedge \overline\wedge \overline\right)\vee \left(\overline\wedge x_2\wedge x_3\wedge x_4\right)\vee \left(x_1\wedge \overline\wedge \overline\wedge \overline\right).\]

Запишем логическую функцию в СКНФ.

Используя правило составления СКНФ не забываем вводить знак отрицания для переменных со значением 1. Инвертировать единичные значения переменных обязательно, т.к. иначе они превратят значения дизъюнкций в единицы основной функции.

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Полученные во вспомогательном столбце дизъюнкции соединим знаком конъюнкции и получим искомую логическую функцию в виде СКНФ:

\[F\left(x_1,x_2,x_3,x_4\right)=\left(x_1\vee x_2\vee x_3\vee x_4\right)\wedge \left(x_1\vee x_2\vee x_3\vee \overline\right)\wedge \left(x_1\vee x_2\vee \overline\vee x_4\right)\wedge \left(x_1\vee \overline\vee x_3\vee \overline\right)\wedge \left(x_1\vee \overline\vee \overline\vee x_4\right)\wedge \left(\overline\vee x_2\vee x_3\vee \overline\right)\wedge \left(\overline\vee x_2\vee \overline\vee x_4\right)\wedge \left(\overline\vee x_2\vee \overline\vee \overline\right)\wedge \left(\overline\vee \overline\vee x_3\vee x_4\right)\wedge \left(\overline\vee \overline\vee x_3\vee \overline\right)\wedge \left(\overline\vee \overline\vee \overline\vee x_4\right)\wedge \left(\overline\vee \overline\vee \overline\vee \overline\right).\]

Источник

Информатика. 10 класс

Конспект урока

Информатика, 10 класс. Урок № 12.

Тема — Преобразование логических выражений

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

Глоссарий по теме: основные законы алгебры логики, логические функции, дизъюнктивная и конъюнктивная нормальная форма, совершенная дизъюнктивная нормальная форма (СДНФ), совершенная конъюнктивная нормальная форма (СКНФ)

Основная литература по теме урока:

Л. Л. Босова, А. Ю. Босова. Информатика. Базовый уровень: учебник для 10 класса

— М.: БИНОМ. Лаборатория знаний, 2017 (с.197—209)

Открытые электронные ресурсы по теме:

Теоретический материал для самостоятельного изучения.

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

Основные законы алгебры логики

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Справедливость законов можно доказать построением таблиц истинности.

Пример 1. Упростим логическое выражение что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Последовательно применим дистрибутивный закон и закон исключенного третьего:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

В общем случае можно предложить следующую последовательность действий:

Пример 2. Упростим логическое выражение что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике.

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Здесь последовательно использованы замена операции импликация, закон де Моргана, распределительный закон, закон противоречия и операция с константой, закон идемпотентности и поглощения.

Аналогичные законы выполняются для операции объединения, пересечения и дополнения множеств. Например:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Пример 3. На числовой прямой даны отрезки B = [2;12] и C = [7;18]. Каким должен быть отрезок A, чтобы предикат что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатикестановился истинным высказыванием при любых значениях x.

Преобразуем исходное выражение, избавившись от импликации:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

A, B, C — множества. Для них можно записать что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике(U — универсальное множество).

Будем считать, чточто такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике.

Тогда что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике, причем это минимально возможное множество А.

Так как множество B — это отрезок [2;12], а множество что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике— это промежутки что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатикеичто такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике, то пересечением этих множеств будет служить промежуток что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике. В качестве ответа мы можем взять этот промежуток, а также любой другой, его включающий.

Пример 4. Для какого наименьшего неотрицательного целого десятичного числа а выражение

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатикетождественно истинно (т. е. принимает значение 1 при любом неотрицательном целом значении десятичной переменной х)? Здесь & — поразрядная конъюнкция двух неотрицательных целых десятичных чисел.

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Перепишем исходное выражение в наших обозначениях и преобразуем его:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Рассмотрим предикат что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике. В числе 2810=111002 4-й, 3-й и 2-й биты содержат единицы, а 1-й и 0-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 4, 3 или 2 содержит единицу. Если и 4-й, и 3-й, и 2-й биты числа х нулевые, то высказывание что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатикебудет ложным.

Рассмотрим предикат что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике. В числе 4510=1011012 5-й, 3-й, 2-й и 0-й биты содержат единицы, 4-й и 1-й — нули. Следовательно, множеством истинности этого предиката являются такие числа х, у которых хотя бы один из битов с номерами 5, 3, 2 или 0 содержит единицу. Если и 5-й, и 3-й, и 2-й, и 0-й биты числа х нулевые, то высказывание что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатикебудет ложным.

Рассмотрим предикат что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике. В числе 1710=100012 3-й, 2-й и 1-й биты содержат нули, 4-й и 0-й — единицы. Побитовая конъюнкция 17 и х будет равна 0, если в числе х 4-й и 0-й биты будут содержать нули. Множество истинности этого предиката — все х с нулями в 4-м и 0-м битах.

По условию задачи надо, чтобы что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике.

Запишем это выражение для рассмотренных множеств истинности:

что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике

Так как что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике, примем что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике.

Объединением множеств M и N являются все двоичные числа, у которых хотя бы один из битов с номерами 5, 4, 3, 2, 0 содержит единицу. Пересечением этого множества с множеством K будут все двоичные числа, у которых биты с номерами 4 и 0 будут заняты нулями, т.е. такие двоичные числа, у которых хотя бы один из битов с номерами 5, 3, 2 содержит 1. Все эти числа образуют множество А.

Искомое число a должно быть таким, чтобы при любом неотрицательном целом значении переменной х: что такое сднф в информатике. Смотреть фото что такое сднф в информатике. Смотреть картинку что такое сднф в информатике. Картинка про что такое сднф в информатике. Фото что такое сднф в информатике, и, кроме того, оно должно быть минимальным из возможных. Этим условиям удовлетворяет число 1011002 = 4410.

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

Для n=2 существует 16 различных логических функций. Рассмотрим их подробнее.

Источник

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *