A) элементтері болса 3 страница

1-ый ранг - операция «НЕ» (инверсия),

2-ой ранг - операция «И» (конъюнкция, логическое умножение),

3-ий ранг - операция «ИЛИ» (дизъюнкция, логическое сложение),

4-ый ранг – остальные операции.

Остальные операции выполняются в порядке их появления в формуле.

, порядок выполнения:

Изменить порядок выполнения операций можно с помощью скобок.

, порядок выполнения:

При определении порядка выполнения операций надо иметь в виду, что операция «НЕ» (черта наверху) одновременно играет роль скобок.

 

 

Функционально полной системой является такой минимальный состав логических операций, с помощью которого можно выразить любую логическую функцию. Этот состав имеет название «логический базис» или, просто, «базис». Существуют базисы состоящие из одной, двух и трех операций, но не более. Полный набор базисов представлен в таблице 1.6.1.

 

Таблица 1.6.1
Число операций составляющих базис. Базисы
Одна ;
Две
Три

 

Из этих базисов рассмотрим лишь те, которые в прикладном плане представляют наибольший интерес.

 

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

f(x1, x2, … , xn) = x1 f(1, x2, … , xn) + f(0, x2, …, xn). (1.4)

Доказательство теоремы осуществляется путём подстановки x1=1 и x=0. Если иметь в виду особенность операции «И» (таб. 1.4.1), получим соотношения и . После их подстановки в (1.4), данное равенство превращается в тождество, что и требовалось доказать. Рассмотренная теорема демонстрирует возможность разложения f(x1, x2, … , xn) по переменной x1. При разложении используются только операции «И», «ИЛИ» и «НЕ». Точно таким же образом полученный результат (1.4) можно разложить относительно переменной x2. Процедуру разложения можно продолжать вплоть до переменной xn. Результатом многократного разложения будет логическое выражение, содержащее только операции «И», «ИЛИ» и «НЕ».

Пример 1.6.1

. В таблице 1.4.1 для операции « » значится

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

 

Основа для доказательства существования базиса содержится в равенстве

(1.5)

Справедливость этого равенства обнаруживается при сравнивании табличной формы представления его левой и правой частей. По сути дела, (1.5) есть форма эквивалентного преобразования операции «И» в операции «ИЛИ» и «НЕ». Если такое преобразование осуществить с выражением, представленном в базисе {И, ИЛИ, НЕ}, получим эквивалентное выражение в базисе {ИЛИ, НЕ}.

 

Пример 1.6.2.

. .

 

В основе доказательства существования рассматриваемого базиса лежит равенство

. (1.6)

Доказательство справедливости (1.6) аналогично доказательству равенства (1.5). Формула служит для замены операции «ИЛИ» на операции «И» и «НЕ». Выражение (1.6) является формулой преобразования базиса {И, ИЛИ, НЕ} в базис {И, НЕ}.

Пример 1.6.3

 

1.6.4. Базис .

Доказательство существования базиса состоит в подтверждении возможности эквивалентной замены логических выражений в базисе {И, ИЛИ, НЕ} на выражения содержащие только операцию « ». Для доказательства обратимся к равенству (1.2).

.

Пусть . Подставим это двойное равенство в (1.2). Учитывая суть операции «ИЛИ» (см. табл. 1.4.1), получим первую формулу рассматриваемого преобразования

. (1.7)

Это есть переход от операции «НЕ» к операции « ». Вторая формула преобразования обеспечивает переход от операции «И» к операции « ». Она компонуется на основании (1.2) , (1.5) и (1.7).

. (1.8)

Для вывода третьей формулы преобразования достаточно (1.2) и (1.7)

.. (1.9)

Пример 1.6.4.

где ;

.

 

Для доказательства существования базиса, как и в предыдущем пункте, достаточно показать возможность преобразования операций базиса {И, ИЛИ, НЕ} в операцию « / ». Основу для выбора функций преобразования составляет равенство (1.3).

.

Если в (1.3) сделать , получим первую формулу преобразования

. (1.10)

Следующая формула преобразования выводится с использованием (1.3) и (1.10).

(1.11)

 

На основе (1.3), (1.6) и (1.10) получим для этого базиса последнюю формулу преобразования

. (1.12)

Пример1.6.5.

,

Где ;

.

1.6.6. Базис .

 

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

(1.13)