Эквивалентные преобразования логических выражений (т. е. способ получения равносильных формул) направлен на их упрощение и минимизацию

Функционально полный набор логических операций

СКНФ – совершенная конъюнктивная нормальная форма, такая форма, в которой нет одинаковых сомножителей и все сомножители содержат одни и те же переменные, причем каждая переменная только 1 раз включает знак вхождения под знак отрицания.

(xÚ y)(xÚ y) - СКНФ.

Логическая функция n аргументов не равная тождественно 1 реализуется однозначно СКНФ.

Замечания.

1) Для построения СКНФ логической функции n аргументов, заданной таблицей соответствия, необходимо по каждому кортежу переменных, на которой логическая функция принимает значение 0, записать дизъюнкцию всех n переменных, инвертируя переменные, имеющие значения 1.

(xÚ yÚ z)(xÚ yÚ z)(xÚ yÚ z) (xÚ yÚ z) - СКНФ.

(функционально полные системы булевых функций)

Система функций алгебры логики (сигнатура):

W = { fⁱ ₁, fⁱ ₂, …, f^k_n }

f^l_p - B_n ® B, B = {0;1}

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

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

Пример

1.j ₆(x ₁, x ₂) = j ₁(j ₇(x ₁, x ₂) ù j ₇(x ₁, x ₂))

(где j - функция из большой таблицы двоичных функций.)

2. j ₆(х₁,х₂)= х_1Å х₂= (х_1Ú х₂) (х_1Ù х₂) =(х_1Ú х₂)(х_1Ú х₂) = х₁ х_2Ú х₁ х₂

Система функций {Ú,ù }, {Ù,ù }, {/}, { }, {, ù } является функционально полной.

Базисом является система функций {Ú,Å }, которая называется базисом Жегалкина.

а) Упрощение формул означает получение равносильных формул с меньшим числом символов их образующих. В булевой алгебре логики для упрощения формул используется следующие тождества (аксиомы, законы, тождественные константы):

1) xÙ y = yÙ x

xÚ y = yÚ x - коммутативность Ú и Ù

2) xÚ (yÚ z) = xÚ (yÚ z)

(xÙ y)Ú z = xÚ (yÚ z) - ассоциативность Ú и Ù

3) xÙ (yÚ z) = (xÙ y)Ù (xÚ z)

x Ú (y Ù z) = (x Ú y)Ù (xÚ z) - дистрибутивность Ú и Ù

4) xÚ x=x, xÙ x=x - повторение Ú и Ù

эти свойства являются законом идемпотентности Ú и Ù

5) x = x - закон двойного отрицания (эндоморфизм 2-го порядка, инволюция)

6) xÙ 1=x, xÙ 0=0

xÚ 1=1, xÚ 0=x

0 =1, 1 = 0

это свойства булевых операций с константами

7) xÙ y = yÙ x

xÚ y = yÚ x

эти тождества – соотношения двойственности (закон де Моргана)

8) xÙ x = 0

xÚ x = 1

Эти тождества – закон дополнения (комплементарности противоречия) и закон исключенного третьего (закон двузначности высказывания)

Примечание. Для перехода от формул содержащих операции импликации и эквивалентности к булевым формулам используются равенства (соотношения)

x® y = xÚ y

x~y = (xÙ y)Ú (xÙ y) = (x_1Ú x₂) (x_1Ú x₂)

Методом совершенной индукции, т.е. методом соответствия, можно доказать справедливость тождеств 1-8, которые можно рассматривать и как формулы метапеременных.

б) Минимизация

При минимизации ДНФ и КНФ используют законы поглощения, склеивания.

Законы поглощения

xÚ xy = x

x(xÚ y) = x

Законы склеивания:

yÚ xy = x

xzÚ yzÚ xy = xzÚ yz

xÚ xy = xÚ y; x(xÚ y) = xy

(xÚ xz - ДНФ принцип расщепления)

xÚ xz= x(zÚ z)Ú xz = xzÚ xzÚ xz = xzÚ xz)

Дата добавления: 2014-01-06