Реферат: Функционально полные системы логических функций Алгебраический подход

1. Основная функционально полная система логических функций. Наибольшее распространение получил набор, в состав которого входят три логические функции:

· f₁₀ – инверсия (логическая связь НЕ, логическое отрицание);

· f₁ – конъюнкция (логическая связь И, логическое умножение),

· f₇ – дизъюнкция (логическая связь ИЛИ, логическое сложение).

Этот набор получил название функционально полной системы логических функций (ОФПС). Из теоремы о функциональной полноте следует, что основная функционально полная система логических функций является избыточной, так как условиям теоремы отвечают наборы функций f₁₀ и f₁ или f₁₀ и f₇ . Свойства этих функций были рассмотрены ранее.

Из определения представления переключательной функции в виде дизъюнктивной или конъюнктивной нормальной формы следует, что эти представления реализуются в основной функционально полной системе логических функций.

2. Законы алгебры логики в ОФПС и их следствия. В алгебре логики имеются четыре основных за­кона, регламентирующих порядок производства операций НЕ, И, ИЛИ в любом логическом выражении:

· переместительный (коммутативный);

· сочетательный (ассоциативный);

· распределительный (дистрибутивный);

· инверсии (правило Де Моргана).

Переместительный закон. Этот закон справедлив как для дизъюнкции, так и для конъюнкции:

x ₁ Ú x ₂ = x ₂ Ú x ₁ ; x ₁ Ù x ₂ = x ₂ Ù x ₁ . (1)

Справедливость выражения (5.1) нетрудно доказать простой подста­новкой в него различных значений x ₁ и x ₂ . Поскольку любую переста­новку большего количества слагаемых можно свести к последователь­ности перестановок слагаемых в отдельных парах, то переместитель­ный закон будет справедлив при любом числе слагаемых.

Сочетательный закон. Этот закон, так же как и переместительный, является симметричным, т. е. справедливым и для дизъюнкции, и для конъюнкции:

x₁ Úx₂ Úx₃ = x₁ Ú(x₂ Úx₃ ) = (x₁ Úx₂ )Úx₃ = x₂ Ú( x₁ Úx₃ ); (2)

x₁ Ùx₂ Ùx₃ = x₁ Ùx₂ Ùx₃ ) = (x₁ Ùx₂ )Ùx₃ = x₂ Ù( x₁ Ùx₃ ).

Доказательство этого закона также не представляет никаких труд­ностей и может быть выполнено простой подстановкой.

Распределительный закон. В отличие от обычной алгебры алгебра логики симметрична. В ней справедливы два распределительных закона:

для логического умножения относительно логического сложения (рас­пределительный закон 1-го рода) и для логического сложения относи­тельно логического умножения (распределительный закон 2-го рода).

1. Распределительный закон 1-го рода записывается следующим образом:

(x₁ Úx₂ )Ùx₃ =(x₁ Ùx₃ )Ú ( x₂ Ùx₃ ) . (3)

Справедливость формулы (5.3), а также и ее более общего случая, когда в скобках заключена сумма любого количества слагаемых, можно доказать путем установления идентичности условий обращения в 0 или 1 ее левой и правой частей. Условием обращения в нуль левой части выражения (5.3) состоит в том, чтобы нулю равнялся либо один аргумент х₃ , либо одновременно аргументы x ₁ и x ₂ . Условия обращения в нуль правой части выражения (5.1) такие же. Следовательно, распределительный закон 1-го рода справедлив для алгебры логики.

2. Распределительный закон 2-го рода имеет вид

(x₁ Ùx₂ )Úx₃ =(x₁ Úx₃ )Ù ( x₂ Úx₃ ). (4)

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

Закон инверсии (правило Де Моргана). Этот закон, так же как и все предыдущие, симметричен относительно логических сложения и умножения.

1. Отрицание логической суммы нескольких аргументов равно ло­гическому произведению отрицаний этих же аргументов:

(5)

--> ЧИТАТЬ ПОЛНОСТЬЮ <--