lec06

Из схем 1,2,3 путем последовательного и параллельного их соединения могут быть получены новые двухполюсные переключательные схемы (П-схемы).

Так как любая формула может быть записана в ДНФ или КНФ, то каждой формуле алгебры логики можно поставить в соответствие некоторую П-схему, а каждой П-схеме можно поставить в соответствие некоторую формулу алгебры логики.

Реализацией ДНФ служит параллельно-последовательная схема соединения контактов. CКНФ – последовательно-параллельная П- схема. Задав сложность П-схемы количеством реле – существует задача уменьшения сложности П-схемы (нахождения наименьшего ранга для ДНФf), решаемая инструментами алгебры логики.

21

Пример 6.8. П-схемы и СДНФ.

(x,y,z) = x (yz xy) (из примера 3.6, 6.7)

СДНФ =

П-схема для приведена на схеме 5:

Эквивалентными преобразованиями (в

примере 3.6в) была получена КНФ ≡ x

(она же ДНФmin), т.е. П-схема для (x,y,z) может быть упрощена до схемы 6:

22

Возможности алгебры логики для решения логических задач (дедукция в криминалистике)

Пример 6.9. Пытаясь вспомнить победителей прошлогоднего турнира, пять бывших зрителей турнира заявили:

-Илья был вторым, а Борис - пятым.

-Виктор был вторым, а Денис - третьим.

-Григорий был первый, а Борис - третьим.

-Илья был третьим, а Евгений - шестым.

-Виктор был третьим, а Евгений - четвертым.

Впоследствии выяснилось, что каждый зритель ошибся в одном из двух своих высказываний. Найти истинное распределение топ-5 мест в турнире?

Обозначим высказывание зрителя - Xi, где Х – обозначение участника, i – номер занятого им места.

Т.к. в высказываниях каждого зрителя одна часть ложна, а вторая истинна, то дизъюнкция этих частей будет истинна:

И2 Б5 ≡ 1, В2 Д3 ≡ 1, Г1 Б3 ≡ 1, И3 Е6 ≡ 1, В3 Е4 ≡ 1.

Тогда будет истинной и формула F:

F = (И2 Б5) (В2 Д3) (Г1 Б3) (И3 Е6) (В3 Е4)

При X, Y {И, Б, В, Д, Г, Е} учитываем, что (Xi Xj) = 0 при i≠j, а также, что (Xi Yi) = 0. Применив эквивалентные преобразования:

F= И3 Б5 В2 Г1 Е4

при F ≡ 1: И3 ≡ 1, Б5 ≡ 1, В2 ≡ 1, Г1 ≡ 1, Е4 ≡ 1.

24

Сводка основных результатов.

1) Булева функция : Вn В1.

Способы задания: табличный/векторный и геометрический.

2)Основные булевы функции: , &, ¬.

3)Свойства операций (аксиомы булевой алгебры). Особо важны:

f = 1	f = 0 =
=	f	1 =	f 1 = 1
f 0 = 0	f	0 =

4)Элементарные булевы функции: основные и

5)СДНФ: а) -вектор; б) - -формула ДНФ (заменяя элементарные функции на основные и дополняя конъюнкцией с 1) СДНФ

6)СДНФ * = СКНФ , СКНФ * = СДНФ .

7)Минимизация ДНФ.

а) геометрический метод n 3 (хотя можно из для );
б) Метод Карно для n ≤ 4;
в) Метод Квайна – Мак-Класки – n.	25