Лекция 1 Тема: Алгебра высказываний. Цель: Разъяснить понятие высказывания.

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

Алгебра высказываний 1. Основные по н ятия. Логические операции Под высказыванием мы понимаем предложение, о котором можно сказать, истинно оно или ложно. Высказывания мы будем обозначать заглавными буквами латинского алфавита, возможно с индексами: Если высказывание А истинно, мы будем писать А=1; если высказывание А ложно, мы будем писать А=0. Примеры 1. А=«два умножить на два равно семи» 2. В=«два плюс два равно 4» 3. С=«если сентябрь – весенний месяц, то 5*5=25» 4.D=«число делится на 3 тогда и только тогда, когда сумма его цифр делится на 3» 5.E=«если после четверга следует пятница, то в году 13 месяцев» A=0 B=1 C=? D=1 E=?

Операции над высказываниями. Отрицание Определение 1 Высказывание "неверно, что А" называется отрицанием А и обозначается Задается действие отрицания с помощью таблицы истинности: A Например, пусть A ="2*2=5", тогда = " неверно, что 2*2=5"

Из высказываний А, В можно образовать высказывание "А и В". Например, "2*2=4 и 5+3=9" Определение 2 Высказывание "А и В" называется конъюнкцией (или логическим умножением) высказываний А и В. Конъюнкция имеет много обозначений: Конъюнкция задается с помощью таблицы истинности: AB Конъюнкция

Из высказываний А, В можно образовать высказывание "А или В". Например, "2*2=4 или 5+3=9". Определение 3 Высказывание "А или В" называется дизъюнкцией (или логическим сложением) высказываний А и В и обозначается A v B Дизъюнкция задается с помощью таблицы истинности: ABAvBAvB Дизъюнкция

Из высказываний А, В можно образовать следующее высказывание: "А тогда и только тогда, когда В". Например, треугольник является равносторонним тогда и только тогда, когда все его углы равны между собой. Синонимами служат фразы: "А в том и только в том случае, когда В", "А необходимо и достаточно для того, чтобы выполнялось В", "А равносильно В", "А эквивалентно B". Определение 4 Высказывание "А равносильно В" называется эквивалентностью высказываний А и В и обозначается: Эквивалентность

Эквивалентность задается таблицей истинности: AB Эквивалентность

Из высказываний А и В можно образовать высказывание "если А, то В". Например, если две прямые параллельны третьей, то они параллельны между собой. Синонимами служат следующие фразы: "из А следует В", "В является следствием А", "А влечет В", "А достаточное условие для В", "В необходимое условие для А" и т.п. Определение 5 Высказывание "если А, то В" называется импликацией высказываний А и В и обозначается: В этой ситуации высказывание А называется посылкой, а В – заключением. Импликация

Задается импликация таблицей истинности: AB Импликация Примеры 1. D="если сегодня среда, то завтра будет четверг" D=1 2. Y="если после четверга следует пятница, то после пятницы следует воскресенье Y=0 3. Х="если два плюс два равно пяти, то три плюс два равно десяти X=1 4. Z="если 1+1=3, то после пятницы следует суббота Z=1

Сделаем замечания, которые могут прояснить суть определения таблицы истинности для импликации и, возможно, помогут получше ее запомнить: 1) если посылка ложна, то импликация всегда истинна, независимо от заключения, то есть 2) если заключение истинно, то импликация также истинна, независимо от посылки, то есть Или обобщающая фраза: из истины ложь не следует Импликация

Пример Формализовать высказывание: F=«Хлеба уцелеют тогда и только тогда, когда будут вырыты ирригационные канавы; если хлеба не уцелеют, то фермеры обанкротятся и оставят фермы.» Решение Пусть А=«хлеба уцелеют» B=«будут вырыты ирригационные канавы» С=«фермеры обанкротятся» D=«фермеры оставят фермы». Тогда

Пример Построить таблицу истинности для высказывания ABCF