ЛОГИЧЕСКИЕ ОСНОВЫ КОМПЬЮТЕРОВ АЛГЕБРА ВЫСКАЗЫВАНИЙ (АЛГЕБРА ЛОГИКИ)

ЛОГИКА, ВЫСКАЗЫВАНИЯ Аристотель ( до н.э.) Логика– это наука о том, как правильно рассуждать, делать выводы, доказывать утверждения. Формальная логика отвлекается от конкретного содержания, изучает только истинность и ложность высказываний. Логическое высказывание – это повествовательное предложение, относительно которого можно однозначно сказать, истинно оно или ложно.

ЛОГИКА И КОМПЬЮТЕР Двоичное кодирование – все виды информации кодируются с помощью 0 и 1. Задача – разработать оптимальные правила обработки таких данных. Почему «логика»? Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания. Джордж Буль разработал основы алгебры, в которой используются только 0 и 1 (алгебра логики, булева алгебра).

Термин «логика» происходит от древнегреческого logos – «слово, мысль, понятие, рассуждение, закон». Логика является одной из дисциплин, образующих математический фундамент информатики. В вычислительной технике и автоматике используются логические схемы – устройства, которые преобразуют двоичные сигналы. Анализ и проектирование логических схем опираются на законы алгебры логики. Любой язык программирования содержит логические переменные и средства для описания и вычисления логических выражений. Логические методы применяются и при работе с базами данных.

АЛГЕБРА ВЫСКАЗЫВАНИЙ В алгебре высказываний высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: «истина» (1) или «ложь» (0)

Основным объектом в логике является высказывание. Высказывание – это повествовательное предложение, о котором можно сказать истинно оно или ложно. Высказывание называется простым, если никакая его часть сама не является высказыванием. Высказывание называется составным, если оно состоит из простых высказываний, соединенных логическими связками: И, ИЛИ, частицей НЕ

Примеры: 1. Москва – столица России 2. Студент математического факультета педагогического университета 3. Треугольник АВС подобен треугольнику АВС 4. Луна есть спутник Марса 5. Кислород – газ 6. Каша – вкусное блюдо 7. Математика – интересный предмет 8. Железо тяжелее свинца 9. Треугольник называется равносторонним, если все его стороны равны 10. Сегодня плохая погода 11. Река Ангара впадает в озеро Байкал Какие из этих предложений являются высказываниями?

Простые высказывания обозначают заглавными латинскими буквами A, B, C…X, Y, Z и называют логическими переменными Значения высказываний ИСТИНА или ЛОЖЬ обозначают соответственно цифрами 1 и 0 и называют логическими величинами Составные высказывания называются логическими выражениями и включают в себя логические переменные, операции логики и скобки для изменения порядка действий операций

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ

ЛОГИЧЕСКОЕ УМНОЖЕНИЕ (КОНЪЮНКЦИЯ, &) Объединение двух или нескольких высказываний в одно с помощью союза «И» называется операцией логического умножения или конъюнкцией.

ОПЕРАЦИЯ И Высказывание «A и B» истинно тогда и только тогда, когда А и B истинны одновременно. 220 В A и B A B

ТАБЛИЦА ИСТИННОСТИ ФУНКЦИИ ЛОГИЧЕСКОГО УМНОЖЕНИЯ АВF=A&B

ПРИМЕР 1. А=«2*2=5»(ложь),В=«3*3=10»(ложь) F=А&В – ложь 2. А=«2*2=4»(истина),В=«3*3=6»(ложь) F=А&В – ложь 3. А=«2*2=4»(истина),В=«3*3=9»(ист.) F=А&В – истина 4. Все гуси – птицы и Все игрушки – машиныF=?

ЛОГИЧЕСКОЕ УМНОЖЕНИЕ (КОНЪЮНКЦИЯ) Составное высказывание, образованное в результате логического умножения или конъюнкции, истинно тогда и только тогда, когда истинны все входящие в него простые высказывания

ОПЕРАЦИЯ ИЛИ (ЛОГИЧЕСКОЕ СЛОЖЕНИЕ, ДИЗЪЮНКЦИЯ) Высказывание «A или B» истинно тогда, когда истинно А или B, или оба вместе. 220 В A или B AB

ТАБЛИЦА ИСТИННОСТИ ФУНКЦИИ ЛОГИЧЕСКОГО СЛОЖЕНИЯ АВF=AVB

ПРИМЕР 1. А=«2*2=5»(ложь),В=«3*3=10»(ложь) F=АVВ – ложь 2. А=«2*2=4»(истина),В=«3*3=6»(ложь) F=АVВ – истина 3. А=«2*2=4»(истина),В=«3*3=9»(ист.) F=АVВ – истина 4. 2 * 2 = 4 или Белые медведи живут в Африке F=?

ЛОГИЧЕСКОЕ ОТРИЦАНИЕ (ИНВЕРСИЯ) Присоединение частицы «НЕ» к высказыванию называется операцией логического отрицания или инверсией.

ЛОГИЧЕСКОЕ ОТРИЦАНИЕ (ИНВЕРСИЯ) Логическое отрицание (инверсия) делает истинное высказывание ложным, и наоборот, ложное – истинным.

ТАБЛИЦА ИСТИННОСТИ ФУНКЦИИ ЛОГИЧЕСКОГО ОТРИЦАНИЯ АF=Ā

ПРИМЕР 1. А=«Два умножить на два равно четырем» F=Ā ложь 2. А=«Два умножить на два равно четырем» F=А истина

ДИАГРАММЫ ВЕННА (КРУГИ ЭЙЛЕРА) A B A B A A·BA·BA+B

Мы пойдем в театр и будем смотреть балет или пойдем в цирк и посмотрим представление. Это сложное логическое выражение состоит из четырех простых. А=«Мы пойдем в театр» В=«Мы будем смотреть балет». С=«Мы пойдем в цирк». D=«Мы посмотрим представление». Запись сложного логического выражения с помощью формулы X=A*B+C*DX=A&BVC&D

ЗАДАЧА Вычислить значение логической формулы: (не Х и У) или (Х и Z), если логические переменные имеют следующие значения: Х=0, У=1, Z=1 Решение. Отметим цифрами сверху порядок выполнения операций в выражении: не 0=1 1 и 1= 1 0 и 1 =0 1 или 0 =1 ОТВЕТ: 1