Хорошее кафе в Коблево страница ресторана сходите посмотрите
Случайное фото

Лекции, шпаргалки, информация по предметам, статьи, лабораторные, тех.задания


Кафедра ИС(АВТ)

Основы дискретной математики - Вопрос 4-5-6

Лекции(шпаргалка) по основам дискретной математики для кафедры Информационных систем (ИС), факультет Автоматики и вычислительной техники (АВТ).

Вопрос 4-5-6
Сов КНФ, Сов ДНФ. Построение Сов КНФ по таблице истинности.
Построение СовДНФ по таблице истинности Итак, любая булева функция может быть задана таблицей истинности. Располагая значением каждой переменной, по этой таблице можно найти соответствующее значение функции, причем в ней отражены все ситуации, в которых может сказаться описываемая ею система. Однако наряду с табличным способом задания функции, как указывалось выше, широко применяется и аналитический - для нахождения значений функции используются вычисления по соответствующей формуле. Оказывается, используя таблицу истинности, задающую булеву функцию, всегда можно получить формулу, задающую эту функцию. Опишем вначале один из двух возможных способов получения этой формулы и проиллюстрируем его примером функции, заданной следующей таблицей истинности:

x y z f(x,y,z)
0 0 0 0
0 0 1 1
0 1 0 1
0 1 1 0
1 0 0 1
1 0 1 0
1 1 0 0
1 1 1 1
Для получения булевой формулы необходимо:

1) Выделить в таблице те строки, в которых значение булевой функции равно 1 (в данном случае это вторая, третья, пятая и восьмая строки).

2) Выписать искомую формулу в виде логической суммы. Число слагаемых в этой сумме равно числу отмеченных строк (в данном случае число слагаемых в искомой формуле равно 4). Схематически нашу искомую формулу можно изобразить так f(x, у, z) = с1\/c2\/c3\/c3\/c4.

3) Каждое слагаемое с, записать в виде логического произведения типа нех/\неу/\неz. В любом таком произведений обязательно имеется ровно столько сомножителей, сколько переменных входит в функцию f (у нас это переменные х, у, z), записанных либо "без черты", либо "с чертой", например, х или нех, что и отмечено тремя точками над этими переменными.

4) Если значение какой-либо переменной в соответствующей строке таблицы равно 1, то в формулу эта переменная записывается без черты, если же значение переменной равно 0, то с чертой. Например, произведение, соответствующее второй строке таблицы, имеет вид нех/\неу/\z.

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

Применяя приведенные выше рекомендации, можно выписать формулу, соответствующую рассматриваемой таблице истинности: f(x,y, z) = нех/\неу/\z\/неx/\y\/неz\/x/\неy/\неz\/x/\y/\y. x y x->y
0 0 1
0 1 1
1 0 0
1 1 1
В строках первой, второй и четвертой значение этой булевой функции равно 1. Поэтому здесь в СовДНФ имеется три слагаемых: х—>у=нех/\неу\/нех/\у\/х/\у. В силу принципа двойственности должна существовать еще одна форма представления булевых функций. Действительно, булева функция может быть записана в виде логического произведения типа f(x, у, z,...) =d1/\d2/\d3/\... Для этого необходимо отметить те строки таблицы истинности, в которых значение функции равно нулю, и составить для них логические суммы di из всех переменных, беря эти переменные с отрицанием по отношению к переменным наборов выбранных строк. Число сумм равно количеству отмеченных строк. Произведение всех этих сумм дает искомую булеву формулу. Эта формула представляет собой конъюнкцию конституент нуля, которые равны нулю на тех же наборах, что и заданная функция. Она называется совершенной конъюнктивной нормальной формой (СовКНФ)или второй стандартной формой.

Пример 3.2. Найти совершенную конъюнктивную нормальную форму для импликации.

Решение.
Воспользуемся таблицей истинности примера 3.1-Из нее видно, что импликация равна 0 только в третьей строке. Следовательно, искомая конъюнкция состоит из одного сомножителя, который является логической суммой отрицаний значений переменных третьей строки: х->у=х\/у. В данном примере вторая стандартная форма дает выражение более простое, чем первая. Последнее связано с тем, что в таблице истинности для функции х -> у нулей меньше, чем единиц. Но нули являются исходными для СовКНФ, а единицы - для СовДНФ. Отсюда следует, что иногда для написания булевой формулы по таблице истинности предпочтительней выбирать ту стандартную форму, которой соответствует меньшее количество одинаковых значений булевой функции.

Обсудить вопрос в студенческом форуме

 

Сайт содержит информацию о учебном заведении и студенческой общине и не является официальным