И код направления подготовки
Нормальные формы формул. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы
жүктеу/скачать 341.63 Kb.
|
- Бұл бет үшін навигация:
- Определение.
- Полные системы логических функций
- Определение 1
| 1. Нормальные формы формул. Совершенная дизъюнктивная и совершенная конъюнктивная нормальные формы.
Поскольку одна и та же булева функция может быть представлена различными формулами, возникает вопрос о единственности представления булевых функций, т.е. нахождения такой универсальной формы, чтобы каждая булева функция могла быть представлена в ней. Такими формами в булевой алгебре являются совершенные дизъюнктивная и конъюнктивная нормальные формы. Определение. Всякая булева формула, построенная с помощью одной только операции дизъюнкции над литералами (булевыми переменными или их отрицаниями), взятых не более чем по одному разу, называется элементарной дизъюнкцией, или дизъюнктом. Например, - элементарная дизъюнкция. Дизъюнкции , , 1 являются элементарными. Причем первая элементарная дизъюнкция имеет ранг (число литералов) 2, вторая 3, а третья 0. Следующие дизъюнкции: , , , , 0 не являются элементарными. Определение. Всякая булева формула, построенная с помощью одной только операции конъюнкции над литералами (булевыми переменными или их отрицаниями), взятых не более чем по одному разу, называется элементарной конъюнкцией, или конъюнктом. Например, конъюнкции , , 1 являются элементарными. Причем первая элементарная конъюнкция имеет ранг (число литералов) 2, вторая 3, а третья 0. Например, - элементарная конъюнкция. Следующие конъюнкции: , , , , 0 не являются элементарными. Вопросы для закрепления: Что представляет ДНФ? Приведите пример. Что представляет КНФ?Приведите пример? Литература: Основная [1]; дополнительная [3]; Интернет ресурсы [1]-[4] Тема 6 Полные системы логических функций Количество часов 1 Основные вопросы/план темы: Полные системы логических функций. Теорема Поста о функциональной полноте. Минимизация в классе дизъюнктивных нормальных форм. Тезисы лекции*: Определение 1. Система логических функций S = {f1, f2, …, fm} называется функционально полной, если любая логическая функция может быть представлена в виде суперпозиции функций из S. Приведем примеры функционально полных систем: S0 = {Ù, Ú,¬ }, S1 = {Ù, ¬}, S2 = {Ú, ¬}, S3 = {Ù, Å, 1}, S4 = {|}, S5 = {¯}. Действительно, S0 полна по теореме 1 п.3 данной лекции, S1, S2 – полные, т.к. по законам де Моргана – конъюнкцию можно выразить через дизъюнкцию и отрицание, а дизъюнкцию – через конъюнкцию и отрицание. (Так что с точки зрения полноты систему S0 можно считать избыточной). жүктеу/скачать 341.63 Kb. Достарыңызбен бөлісу:
|