Учреждение образования

«Белорусский государственный университет

информатики и радиоэлектроники»

кафедра ЭТТ

РЕФЕРАТ

На тему:

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

МИНСК, 2008

Из множества функционально полных наборов рассмотрим только те, которые имеют наибольшее практическое значение.

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

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

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

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

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

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

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

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

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

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

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

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

x1 Úx2 = x2 Úx1;               x1 Ùx2 = x2 Ù x1.                                        (1)

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

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

x1 Úx2 Úx3 = x1Ú(x2 Úx3) = (x1 Úx2)Úx3= x2Ú( x1 Úx3);        (2)

x1 Ùx2 Ùx3 = x1Ùx2 Ùx3) = (x1 Ùx2)Ùx3= x2Ù( x1 Ùx3).

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

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

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