Логические функции. Разложение логических функций с СДНФ и СКНФ

Логической (булевой) функцией n переменных y = f(x ₁, x ₂, …, x_n) называется такая функция, у которой все переменные и сама функция могут принимать только два значения: 0 и 1.

Переменные, которые могут принимать только два значения 0 и 1 называются логическими переменными (или просто переменными). Логическая переменная х может подразумевать под числом 0 некоторое высказывание, которое ложно, и под числом 1 высказывание, которое истинно.

Конъюнкцией (логическое умножение) n переменных f (x ₁, x ₂,…, x_n) = x ₁ x ₂ …x_n называется функция, которая принимает значение 1, если и только если все переменные равны 1 (и, значит, равна 0, если хотя бы одна из этих переменных равна 0).

Дизъюнкцией (логическое сложение) n переменных f (x ₁, x ₂, …, x_n) = x _1Ú x _2Ú … Ú x_n называется такая функция, которая равна 0 если и только если все переменные равны 0 (и, значит, равна 1 тогда и только тогда, когда хотя бы одна переменная равна 1).

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

– все возможные комбинации расстановок отрицаний над переменными (отрицание – s = 0, нет отрицания – s = 1)

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

…

Для получения СДНФ на основе таблицы истинности необходимо:

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

2) Полученные элементарные конъюнкции объединяются знаками дизъюнкции.

Для получения СКНФ на основе таблицы истинности необходимо:

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

2) Полученные элементарные дизъюнкции объединяются знаками конъюнкции.

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

Задача 1

Для заданной функции полезности решим 1 задачу потребителя.

Бюджет – А

Вектор цен С = (С1, С2)

Функция полезности U = x1 x2

Функция Лагранжа

Тогда

Если

То есть

То

Задача 2

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

2. Вычислим относительную пропускную способность:

Величина q означает, что в установившемся режиме телефонная линия будет обслуживать примерно 50% поступающих вызовов.

3. Абсолютную пропускную способность определим по формуле:

(звонков в минуту)

Это означает, что система способна осуществить в среднем 0,25 обслуживания вызовов в час.

4. Определим номинальную пропускную способность системы:

(звонков в минуту).

Значит, что А_ном в 2 раза больше, чем фактическая пропускная способность, вычисленная с учетом случайного характера потока заявок и времени обслуживания.