Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Совершенная дизъюнктивная нормальная форма
Правила построения СДНФ: 1) проанализировать ф-цию: а) определить кол-во переменных; б) определить вид ф-ции (если ф-ция задана таблицей начений то перейти к построению, а если формулой, то получить таблицу значений ф-ции, выполняя операции по действиям); 2) построить СДНФ: а) в таблице значений выбрать только те наборы переменных, на которых ф-ция принимает значение равное 1 и записать конъюнкции инвертируя переменны со значениями 0 и оставлять без изменения переменные со значениями 1. Каждому набору соответствует конъюнкция все переменных, таким образом между таблицей значений и СДНФ устанавливается взаимооднозначноо соответствие. Теорема: Для каждой булевой функции n переменных кроме константы 0 существует единственная СДНФ с точностью до порядка букв в конъюнкции. Теорема: Всякая логическая ф-ция может быть представлена булевой ф-лой, т.е. как суперпозиция конъюнкций, дизъюнкций и отрицаний. Определение: Длиной дизъюнктивной нормальной формулы ф-ции n переменных называют количество переменных, как букв в этой форме. Аналогично вводится понятие совершенной конъюнктивной нормальной формы (СКНФ). Это рассматривается как конъюнкция соответствующих дизъюнкций. ДНФ, которая имеет минимальную длину называется минимальной ДНФ. 33. Эквивалентные преобразования. Доказательство. Эквив-е преоб-я – преоб-я, использ-е эквивалентные соотн-я и правила замены. Эквив-е преобр-я явл-ся мощным ср-м доказ-ва эквивалентности формул. 1.Правило подстановки формулы F вместо переменной х. При подстановке ф-kf вместо пре-й х все вхождения пер-й х в исходное соотн-е д.б. одновременно заменены ф-й F. Правило применяется к эквивал-м соот-м для получения эк-х соот-й. Правило замены подформул. Если какая-либо ф-ла F, описываюшая ф-ю f, содержит F1 в качестве подформулы, то замена F1 на эквивал-ю F2 (F1=F2) не изменит ф-и f; полученная при такой замене ф-ла F’ эквив-на исходной F. Правило замены подформул позволяет, используя известные эквив-е соотн-я, получать ф-лы, эквив-е данной, в частности, упрощать формулы. Соотношения: (*= или ) Ассоциативность конъюнкции и дизъюнкции: x1*(x2*x3)=(x1*x2)*x3=x1*x2*x3 Коммутативность x1*x2=x2* x1 Дистрибутивность К отн-но Д x1 (x2 x3)=x1 x2 x1 x3 Дистрибутивность К отн-но Д
x1 (x2 x3)=(x1 x2) (x1 x3) Идемпотентность x*x=x Закон 2-го отрицания =х Св-ва констант 0 и 1 х 1=х; х 0=0; х 1=1; х 0=х; =1; =0 Правило Де Моргана = ; = Закон противоречия х =0 Закон исключенного третьего х =1 Поглощение х х у=х; х (х у)=х Склеивание х у х =х Обощенное склеивание x z y x y=x z y x y=x y
|
|||||
Последнее изменение этой страницы: 2017-02-21; просмотров: 309; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 18.217.84.171 (0.008 с.) |