Понятие равносильности формул

Понятие равносильности формул

Определение 4.1. Формулы и алгебры высказываний называются равносильными (эквивалентными), если при любых значениях входящих в них…   Не следует думать, что в обе формулы и непременно входят одни и те же переменные. Некоторые из переменных могут…

Булева алгебра

Функции алгебры логики

Значение формулы алгебры логики полностью зависит от значений входящих в нее высказываний. Поэтому такая формула может считаться функцией входящих в… Каждую функцию алгебры логики можно записать в виде формулы или представить… Из этой таблицы следует, что две функции являются константами f1(x) = 1 и – f2(x) = x, а остальные f3(x) = Ø x…

Представление произвольной логической функции в виде формулы алгебры логики

Пусть с помощью таблицы истинности задана произвольная функция алгебры логики n переменных F(x1, x2, …, xn). Рассмотрим формулу: F(1, 1, …, 1) Ù x1 Ù x2 Ù … Ù xn Ú Ú F(1, 1, …, 1, 0) Ù x1 Ù x2 Ù … Ù xn-1 Ù Ø xn Ú (1)

Принцип двойственности.

Если функция f задана формулой, построенной с помощью &,?,¬,0,1 и переменных, то по теореме о суперпозиции двойственных функций и ввиду того, что для функций x&y, ¬x, ,1,0 двойственными являются x?y ,x ,0,1 соответственно, то f* получается из f заменой & на ?, 0 на 1 и т.д. при сохранении исходной расстановки скобок.

 

 

Дизъюнктивная нормальная форма и совершенная дизъюнктивная нормальная форма

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

Конъюнктивная нормальная форма и совершенная конъюнктивная нормальная форма

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

Сокращенная ДНФ

Запишем функцию (медиана) в виде совершенной ДНФ: . Известно, что это выражение равносильно следующему: . Вынесем в каждой скобке общий конъюнкт…

Минимальная ДНФ

 

Метод Квайна

1. склеивание 2. поглощение Суть метода заключается в последовательном выполнении всех возможных склеиваний и затем всех поглощений, что приводит…

Метод Квайна-Мак-Класки

1) Все конституэнты "1" из СДНФ булевой функции записываются их двоичными номерами. 2) Все номера разбиваются на непересекающиеся группы, в i-ой группе находятся… 3) Склеиваются только номера соседних групп, склеивание номера как-либо отмечают.

Метод диаграмм Вейча

Добавление к диаграмме 3-х переменных еще такой же даст диаграмму 4-х переменных, если приписать еще одну диаграмму 4-х переменных, то получим…   Правила склеивания конституэнт "1" на диаграммах Вейча: склеиванию подлежат прямоугольные конфигурации,…

Минимизация частично определенных булевых функций

  Алгоритм поиска МДНФ частично определенной функции:  

Минимизация функций в базисах И-НЕ и ИЛИ-НЕ

Для n переменных:

Полные системы булевых функций

Множество функций алгебры логики называется полной системой, если замыкание этого множества совпадает с множеством всех функций. (В частности, для… Критерий Поста формулирует необходимое и достаточное условие полноты системы… Широко известны такие полные системы булевых функций:

Линейные функции

Число различных линейных функций от не более чем n переменных определяется формулой N = 2n+1. Суперпозиция линейных функций есть функция линейная, следовательно, множество…