Основы информатики (элементы комбинаторики, алгебры логики и системы кодирования информации)

Поясним данное определение на примерах. Высказывание "Число 2 четное и простое" сложное, оно состоит из двух высказываний: а: "Число 2 четное" и b: "Число 2 простое", связанных союзом "и". Оба эти высказывания истинны. Истинным является и сложное высказывание, которое есть конъюнкция высказываний а и b.

3.3.Дизъюнкция

Дизъюнкцией двух высказываний а и b называется высказывание ab (читается "а или b"), которое истинно тогда и только тогда, когда истинно хотя бы одно из составляющих его высказываний. Это определение легко распространяется на любое конечное число высказываний. Определение дизъюнкции двух высказываний может быть выражено следующей таблицей истинности:

"Если последняя цифра числа равна 0 или 5, то это число делится на 5" есть дизъюнкция высказываний "Если последняя цифра числа равна 0, то это число делится на 5" и "Если последняя цифра числа равна 5, то это число делится на 5". Примером дизъюнкции высказываний может служить нестрогое неравенство, например 37. Такое неравенство считается истинным, если истинно хотя бы одно из входящих в него высказываний 3<7, 3=7.

3.4.Импликация

Импликацией двух высказываний а и b называется такое высказывание ab (читается "из а следует b" или "если а, то b"), которое ложно тогда и только тогда, когда а истинно, a b - ложно. Таблица истинности для импликации имеет следующий вид:

Высказывание а называют условием (или посылкой), a b – заключением (следствием). Существует немало синонимов для связки "если ..., то ...", например:

- из а следует b;

- а влечет за собой b;

- как только а, то b;

- а - достаточное условие b.

3.5.Эквивалентность

Эквивалентностью двух высказываний а и b называется такое высказывание ab, которое истинно тогда и только тогда, когда оба высказывания а и b либо истинны, либо ложны. Читается запись ab так: "а тогда и только тогда, когда b" или "Для того, чтобы а, необходимо и достаточно, чтобы b". Таблица истинности эквивалентности такова:

3.6.Законы логики

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

Пример. Составить таблицу истинности выражения

Решение. Выпишем в таблице все возможные сочетания значений a и и воспользуемся таблицами истинности отрицания и конъюнкции. Получим

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

Примеры равносильностей.

1. - закон двойного отрицания

2. - первый закон коммутативности

3. - второй закон коммутативности

4. - первый закон ассоциативности

5. - второй закон ассоциативности

6. - первый закон дистрибутивности

7. - второй закон дистрибутивности

8. - первый закон поглощения

9. - второй закон поглощения

10. - первый закон де Моргана

11. - второй закон де Моргана

Доказательство. Составим таблицы истинности для выражений, стоящих в левой и правой частях первой формулы (их удобно совместить). Получим