Свойства логических операций

1) ХÚУ = УÚХ (переместительное свойство дизъюнкции);

2) Х^У = У^Х (переместительное свойство конъюнкции);

3) ХÚ (УÚ Z) = (Х Ú У) Ú Z – сочетательное свойство;

4) Х ^ (Y ^ Z) = (X ^ Y) ^ Z - сочетательное свойство;

5) Х ^ (Y Ú Z) = (X ^ Y)Ú (X ^ Z) – распределительное свойство;

6) Х Ú (Y ^ Z) = (X Ú Y) ^ (X Ú Z) – распределительное свойство;

7) ;

8) ;

9) ;

10) ;

11) X ^ (X Ú Z) = X,

X Ú (X ^ Y) = X – закон поглощения;

12) - закон противоречия;

13) X Ú - закон исключенного третьего;

X Ú X = X, X ^ X = X.

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

Пример: Доказать, что Х®У = .

Решение: .

Определение 5. Х~У есть высказывание, истинное тогда и только тогда, когда Х и У оба истинны или оба ложны. Это высказывание называется эквивалентностью (Х эквивалентно У).

Таблица истинности:

1) Х~ У= (Х^Y) Ú ;

2) Х~ У= (Х®У) ^ (У®Х).

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

Некоторые свойства равносильности:

равносильно Х;

Х ^ X равносильно X;

X Ú X равносильно X;

равносильно Y;

равносильно .

истинно, ложно.

Пример:

Применение алгебры высказываний:

Пример (Логическая задача):

На вопрос, кто из трех студентов изучал логику, был получен правильный ответ: если изучал первый, то изучал и второй, но не верно, что если изучал третий, то изучал и второй. Кто из студентов изучал логику?

Решение: Обозначим через Х₁, Х₂, Х₃ – высказывания, состоящие в том, что I, II, III студенты изучали логику. Из задачи следует истинность высказывания:

,

т.к. - ложно. Значит, - ложно.

Из истинности S вытекает истинность отсюда вытекает, что логику изучал третий студент, а первый и второй не изучали.

Алгебра высказываний применяется при анализе рэлейноламповых схем. Под переключательной схемой мы будем понимать схематическое изображения, какого либо устройства, содержащего только двухзначные переключатели, т.е. переключатели, которые могут находиться в двух состояниях: в замкнутом (ток проходит) и разомкнутом (ток не проходит). Связь между переключательными схемами и алгеброй высказываний устанавливается следующим образом. Каждому переключателю ставится в соответствии высказывания, истинное тогда, когда переключатель замкнут, и ложное, если переключатель разомкнут. На схемах переключатели будем обозначать теми же буквами, что и соответствующие им высказывания.

Переключателям, соединенным параллельно, будет соответствовать сумма соответствующих высказываний. Переключателям, соединенным последовательно, будет соответствовать произведение высказываний. Каждой переключательной схеме будет соответствовать высказывание, истинное тогда и только тогда, когда схема проводит ток. Любую схему методами математической логики можно преобразовать до простейшей, где меньше переключателей.

Пример 1:

(Х ^ У) Ú (Х ^ Z) = X ^ (Y Ú Z);

X ^ (YÚ Z).

Эти две схемы эквивалентны, но вторая схема содержит меньше переключателей, поэтому она предпочтительнее.

Пример 2: Упростить схему

(Х ^ Y) Ú ((X Ú Z) ^ ) = (X ^ Y) Ú (X ^ ) Ú (Z ^ ) =

= X ^ (Y Ú ) Ú (Z ^ ) = X Ú (Z ^ ).

Тогда схема имеет вид

Вторая схема оптимальна, т.к. меньше переключателей.

Не нашли, что искали? Воспользуйтесь поиском: