Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь FAQ Написать работу КАТЕГОРИИ:  Археология Биология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия ЭкологияТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву 
Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Двойственность. Принцип двойственности.Содержание книги
Поиск на нашем сайте
Символы &, V называются двойственными. Формула А* называется двойственной формуле A, если она получена из A одновременной заменой всех символов &, V на двойственные. Например, A = x V(y &Ø z); A * = x & (y VØ z). Теорема 4.1. (Принцип двойственности). Если A º B, то A * º B *. Доказательство принципа двойственности можно найти, например, в [3]. Принцип двойственности можно использовать для нахождения новых равносильностей. Например, для 1-го закона поглощения (равносильность 6а) имеем: A &(A V B) º A. Следуя принципу двойственности, получим новую равносильность: A V A & B º A (2- ой закон поглощения).
Булева алгебра (алгебра логики). Нормальные формы Как известно, алгеброй называют систему, включающую в себя некоторое непустое множество объектов с заданными на нем функциями (операциями), результатами применения которых к объектам данного множества являются объекты того же множества. Булевой алгеброй или алгеброй логики называется двухэлементное множество B = {0, 1} вместе с операциями конъюнкции, дизъюнкции и отрицания. Система булевых функций { f 1, f 2, …, fn } называется полной, если любая булева функция может быть выражена в виде суперпозиции этих функций. Из равносильностей 12 – 16 (раздел 4.3) следует, что все логические операции могут быть выражены через операции конъюнкции, дизъюнкции и отрицания. Поэтому система функций {Ø, &, V} является полной. Также полными являются следующие системы функций: а) {Ø, V}; б) {Ø, &}; в) {Ø, É}. Полнота систем {Ø, V} и {Ø, &} следует из полноты системы {Ø, &, V}, а также законов де Моргана и двойного отрицания, следствием которых является возможность выразить конъюнкцию через дизъюнкцию и наоборот: A & B ºØ(Ø A VØ B); A V B º Ø(Ø A &Ø B). Поэтому система {Ø, &, V} может быть сокращена на одну функцию: Полнота системы {Ø, É} следует из полноты системы {Ø, V} и равносильности 12 (раздел 4.3), позволяющую выразить импликацию через отрицание и дизъюнкцию: A É B ºØ A V B.
Нормальные формы Определение 4.4. Элементарной конъюнкцией называется конъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных. Пример 4.6. x, y, x & y, Ø x 1& x 2&(Ø x 3) – элементарные конъюнкции. x V y, x 1&Ø x 2 VØ x 1& x 2 – не элементарные конъюнкции. Определение 4.5. Дизъюнктивной нормальной формой (ДНФ) называется формула, имеющая вид дизъюнкции элементарных конъюнкций (в вырожденном случае это может быть одна конъюнкция). Пример 4.7. x, x & y, x V Ø x &(Ø y), Ø x 1& x 2&(Ø x 3) V x 1&(Ø x 2)& x 3 V x 1& x 2&(Ø x 3) – ДНФ. (x V y)&Ø x – не ДНФ. Определение 4.6. Совершенной дизъюнктивной нормальной формой (СДНФ) называется такая дизъюнктивная нормальная форма, каждый конъюнктивный член которой содержит все переменные, либо их отрицания. Пример 4.8. x & y, x &Ø y V Ø x & y – СДНФ функции двух переменных. x VØ x & y, x V y – не СДНФ. Определение 4.7. Элементарной дизъюнкцией называется дизъюнкция (возможно одночленная), составленная из переменных или отрицаний переменных. Пример 4.9. x, y, x V y, Ø x 1V x 2V(Ø x 3) – элементарные дизъюнкции. x & y, (x 1VØ x 2) & (Ø x 1V x 2) – не элементарные дизъюнкции. Определение 4.8. Конъюнктивной нормальной формой (КНФ) называется формула, имеющая вид конъюнкции элементарных дизъюнкций (в вырожденном случае это может быть одна дизъюнкция). Пример 4.10. x, x & y, x & Ø x &(Ø y), (Ø x 1V x 2)&(Ø x 3)&(x 1VØ x 2V x 3) – КНФ. x & y V Ø x – не КНФ. Определение 4.9. Совершенной конъюнктивной нормальной формой (СКНФ) называется такая конъюнктивная нормальная форма, каждый дизъюнктивный член которой содержит все переменные, либо их отрицания. Пример 4.11. x V y, (x VØ y) &(Ø x V y) – СКНФ функции двух переменных. x &(Ø x V y), x & y – не СКНФ. Теорема 4.2. Для каждой формулы булевой функции A имеется равносильная ей дизъюнктивная нормальная форма (ДНФ) и конъюнктивная нормальная форма (КНФ). Доказательство теоремы состоит просто в указании алгоритмов нахождения для любой формулы A равносильных ей ДНФ и КНФ. Процесс нахождения этих форм называется приведением формулы A соответственно к ДНФ и КНФ. Для каждой формулы A имеется, вообще говоря, бесконечное множество ДНФ и КНФ, но для решения задач, в которых эти формы нужны, требуется, как правило, найти по крайней мере одну из них. Алгоритм 4.1 (Алгоритм приведения формул булевых функций к ДНФ (КНФ)). Шаг 1. Все подформулы A вида B É C (т.е. содержащие импликацию) заменяем на Ø B V C или на Ø(B &Ø C) (в соответствии с равносильностью 12 раздела 4.3). Шаг 2. Все подформулы A вида B ~ C (т.е. содержащие эквивалентность) заменяем на (A & B) V (Ø A &Ø B) или на (A VØ B)&(Ø A V B) (в соответствии с равносильностью 13). Шаг 3. Все отрицания, стоящие над сложными подформулами, опускаем по законам де Моргана (в соответствии с равносильностями 4, 19, 20). Шаг 4. Устраняем все двойные отрицания над формулами (в соответствии с равносильностью 8). Шаг 5. Осуществляем раскрытие всех скобок по закону дистрибутивности конъюнкции относительно дизъюнкции для ДНФ (в соответствии с равносильностями 3а и 17) или по закону дистрибутивности дизъюнкции относительно конъюнкции для КНФ (в соответствии с равносильностями 3б и 18). Шаг 6. для получения более простой формулы целесообразно использовать равносильности 5, 6, 7, 9, 10, 11. Очевидно, что в результате всех указанных операций формула имеет вид ДНФ или КНФ. Указанные операции, вообще говоря, могут осуществляться в любом порядке, однако целесообразно придерживаться изложенного выше, за исключением снятия двойных отрицаний (шаг 4), от которых следует избавляться по мере их появления. Пример 4.12. Приведем к ДНФ и КНФ рассмотренную ранее в примере 4.4 формулу f (x 1, x 2, x 3) = Ø(x 2 1. Устранив импликацию, получим: Ø(Ø x 2 VØ x 3) ~(Ø x 1V x 2). 2. Применив закон де Моргана к первой скобке и сняв двойные отрицания, получим: (x 2& x 3) ~ (Ø x 1V x 2). 3. Устранив эквивалентность, получим: (x 2& x 3) & (Ø x 1V x 2) V Ø(x 2& x 3) & Ø(Ø x 1V x 2). 4. Применив закон де Моргана ко второму члену дизъюнкции, получим (x 2& x 3) & (Ø x 1V x 2) V (Ø x 2VØ x 3) & (x 1& Ø x 2). 5. Применив закон дистрибутивности 3а, получим (x 2& x 3&Ø x 1 V x 2& x 3& x 2) V (Ø x 2& x 1&Ø x 2 V Ø x 3& x 1&Ø x 2). 6. Применив законы идемпотентности 5а и 5б, и располагая переменные по возрастанию индексов, получим: Ø x 1& x 2& x 3 V x 2& x 3 V x 1&Ø x 2 V x 1&Ø x 2&Ø x 3. 7. Применив 2–ой закон поглощения (6б), вместо Ø x 1& x 2& x 3.V x 2& x 3 запишем x 2& x 3, а вместо x 1&Ø x 2 V x 1&Ø x 2&Ø x 3 запишем x 1&Ø x 2 и в результате получим ДНФ нашей формулы: f (x 1, x 2, x 3) º x 2& x 3 V x 1&Ø x 2 При приведении к КНФ применим закон дистрибутивности 3б и получим: x 2& x 3 V x 1&Ø x 2 º (x 2V x 1) & (x 2VØ x 2) & (x 3V x 1) & (x 3VØ x 2). Учитывая, что. x 2VØ x 2 º 1 (равносильность 11), и применив свойство 9а, получим окончательно КНФ для f (x 1, x 2, x 3) f (x 1, x 2, x 3) º (x 1V x 2) & (x 1V x 3) & (Ø x 2V x 3). Приведение некоторой формулы к ДНФ и КНФ не является однозначным. Количество равносильных ДНФ и КНФ, вообще говоря, бесконечно. Однако, совершенные дизъюнктивные и конъюнктивные нормальные формы (СДНФ и СКНФ) или не существуют или единственны. Теорема 4.3. Каждая формула A, не равная тождественно нулю, может быть приведена к СДНФ, которая является единственной с точностью до перестановки дизъюнктивных членов. Теорема 4.4. Каждая формула A, не равная тождественно единице, может быть приведена к СКНФ, которая является единственной с точностью до перестановки конъюнктивных членов. Доказательство этих теорем состоит в указании алгоритма приведения формулы А к СДНФ и СКНФ. Алгоритм 4.2. (Алгоритм приведения формулы булевой функции к СДНФ) Шаг 1. Используя алгоритм построения ДНФ, находим формулу В, являющуюся ДНФ формулы А. Шаг 2. Вычеркиваем в B все элементарные конъюнкции, в которые одновременно входят какая-нибудь переменная и ее отрицание. Это обосновывается равносильностями: A &Ø A º 0, B &0 º 0, СV0 º С. Шаг 3. Если в элементарной конъюнкции формулы B некоторая переменная или ее отрицание встречается несколько раз, то оставляем только одно ее вхождение. Это обосновывается законом идемпотентности для конъюнкции: A & A º A. Шаг 4. Если в элементарную конъюнкцию С формулы В не входит ни переменная x, ни ее отрицание Ø x, то на основании 1- го закона расщепления (равносильность 7а) заменяем С на (С& x) V (C &Ø x). Шаг 5. В каждой элементарной конъюнкции формулы B переставляем конъюнктивные члены так, чтобы для каждого i (i = 1,..., n) на i -ом месте была либо переменная xi, либо ее отрицание Ø xi. Шаг 6. Устраняем возможные повторения конъюнктивных членов согласно закону идемпотентности для дизъюнкции: СVС º С. Пример 4.13. Найдем СДНФ формулы из примера 4.4: f (x 1, x 2, x 3) = Ø(x 2 1. Найденная ранее в примере 4.12 ДНФ формулы f (x 1, x 2, x 3) имеет вид: x 2& x 3 V x 1&Ø x 2. 2. Шаги 2 и 3 алгоритма не требуются (они уже выполнены), поэтому переходим к шагу 4 и применяем 1-ый закон расщепления. В результате вместо каждого из двух конъюнктивных членов получим две элементарных конъюнкции (всего их будет четыре): f (x 1, x 2, x 3) º x 2& x 3& x 1 V x 2& x 3&Ø x 1V x 1&Ø x 2& x 3 V x 1&Ø x 2&Ø x 3). 3. После применения шага 5 получим: f (x 1, x 2, x 3) º x 1& x 2& x 3 V Ø x 1& x 2& x 3 V x 1&Ø x 2& x 3 V x 1&Ø x 2&Ø x 3. 4. Шаг 6 не требуется. Найденное выражение формулы f (x 1, x 2, x 3) является СДНФ этой формулы. Алгоритм нахождения СКНФ полностью повторяет алгоритм нахождения СДНФ, если произвести двойственную замену & на V и V на &. Пример 4.14. Найдем СКНФ формулы из примера 4.4: f (x 1, x 2, x 3) = Ø(x 2 1. Найденная в примере 4.12 КНФ формулы f (x 1, x 2, x 3) имеет вид: f (x 1, x 2, x 3) º (x 1V x 2) & (x 1V x 3) & (Ø x 2V x 3). 2. Шаги 2 и 3 алгоритма не требуются, поэтому переходим к шагу 4 и применяем 2-ой закон расщепления (равносильность 7б). В соответствии с этим законом: x 1V x 2 º (x 1V x 2V x 3) & (x 1V x 2VØ x 3). x 1V x 3 º (x 1V x 3V x 2)&(x 1V x 3VØ x 2). Ø x 2 V x 3 º(Ø x 2V x 3V x 1) & (Ø x 2V x 3VØ x 1). Поэтому имеем: f (x 1, x 2, x 3) = (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1V x 3V x 2)&(x 1V x 3VØ x 2)&(Ø x 2V x 3V x 1)&(Ø x 2 V x 3VØ x 1). 3. Применив шаг 5, получим: f (x 1, x 2, x 3) º (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1V x 2V x 3)&(x 1VØ x 2V x 3)&(x 1VØ x 2V x 3)&(Ø x 1 VØ x 2V x 3). 4. Замечаем, что 1-ый и 3-ий, а также 4-ый и 5-ый дизъюнктивные члены полученного выражения совпадают, применяем шаг 6 и получим окончательно СКНФ формулы f (x 1, x 2, x 3): f (x 1, x 2, x 3) º (x 1V x 2V x 3)&(x 1V x 2VØ x 3)&(x 1VØ x 2V x 3)&(Ø x 1VØ x 2V x 3).
|
||||
|
|
Последнее изменение этой страницы: 2016-12-15; просмотров: 2531; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.147.81.172 (0.007 с.) |
Ø x 3) ~(Ø x 1V x 2).
