Понятие равносильности формул
Определение 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.
Суперпозиция линейных функций есть функция линейная, следовательно, множество…