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

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

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

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

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

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

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

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

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

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

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

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

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

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

f(x₁, x₂, …, x_n) = x₁ f(1, x₂, …, x_n) + f(0, x₂, …, x_n). (1.4)

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

Пример 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)

Дата добавления: 2014-11-09