АЛГЕБРА ЛОГИКИ

В быту мы часто используем слова «логика»,«логично». Логика (от греческого логикус) – это наука о том, как правильно рассуждать, делать выводы, доказывать утверждения. Родоначальником этой науки является Джордж Буль. Поэтому логику часто называют булевой алгеброй. Результат выполнения операции можно представить как истинность (1) или ложность (0) некоторого высказывания. Поэтому кодирование всех видом информации в компьютере подчинено логическим законам.

Опр. Логика – это наука о формах и способах мышления.

Формы мышления ПонятиеВысказываниеУмозаключение

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

Опр. Высказывание – это форма мышления представленная в виде повествовательного предложения, о котором можно однозначно сказать истинно оно или ложно. Пример. 2x2=4 (истинно или равно 1) 2x2=5 (ложно или равно 0)

Опр. Умозаключение – форма мышления, с помощью которой из одного или нескольких высказываний, может быть получено новое. Пример. Высказывание1. Все металлы электропроводны. Высказывание 2. Ртуть металл. Умозаключение: Ртуть – электропроводна.

Высказывания или нет? Солнце есть спутник Земли. 2+3=4; сегодня отличная погода; в романе Л.Н. Толстого Война и мир слов; Санкт-Петербург расположен на Неве; музыка Баха слишком сложна; первая космическая скорость равна 7.8 км/сек; железо металл; если один угол в треугольнике прямой, то треугольник будет тупоугольным; если сумма квадратов двух сторон треугольника равна квадрату третьей, то он прямоугольный.

Высказывания бывают простыми или составными. Они обозначаются буквами латинского алфавита. И принимают значения 1 (истина) или 0 (ложь). Пример: Сегодня пасмурно – простое высказывание. Составное высказывание состоит из простых соединенных логическими операциями: не, или, и, если.. то, тогда и только тогда когда, либо.. либо. Пример: Сегодня пасмурно и идет дождь – составное высказывание.

Логические операции: Отрицание (инверсия) Дизъюнкция (логическое сложение) Конъюнкция (логическое умножение) Импликация (следование) Эквиваленция (равносильность) Исключающее ИЛИ (деление по модулю 2) Штрих Шеффера Стрелка Пирса

Опр. Отрицание – логическая операция, которая делает истинное высказывание ложным и наоборот. Логическая связка – не на языке Паскаль - not Если А – простое высказывание, то отрицание от А обозначается, как ¬ А или Пример: А : 2х2=4 : 2х24

Опр. Дизъюнкция – логическая операция в результате применения которой, составное высказывание истинно, тогда, когда хотя бы одно их входящих в него высказываний истинно. Логическая связка – или на языке Паскаль - or Если А и В – простые высказывания, то дизъюнкция обозначается, как А V В или А+В Пример: А: Сергей купил пирожок В: Сергей купил пиццу А V В: Сергей купил пирожок или пиццу.

Опр. Конъюнкция – логическая операция в результате применения которой, составное высказывание истинно, тогда, когда истинны оба входящих в него высказывания. Логическая связка – и на языке Паскаль - and Если А и В – простые высказывания, то конъюнкция обозначается, как А Λ В или АВ или АхВ или А*В или А&В Пример: А: Сергей купил пирожок В: Сергей купил пиццу А Λ В : Сергей купил пирожок и пиццу.

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

Опр. Эквиваленция – логическая операция в результате применения которой, составное высказывание истинно, тогда, когда высказывания входящие в него истинны или ложны одновременно. Логические связки – тогда и только тогда, когда, равнозначность, равносильно, необходимо Если А и В – простые высказывания, то эквиваленция обозначается, как АВ или АВ или А~В Пример: А: Получить пятерку по информатике В: Сделать качественный проект А В: Получить пятерку по информатике можно только тогда когда сделаешь качественный проект.

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

Опр. Штрих Шеффера – логическая операция в результате применения которой, составное высказывание ложно, тогда, тогда, когда истинны оба входящих в него высказывания. Логическая связка – и.. не на языке Паскаль - nand Если А и В – простые высказывания, то исключающее или обозначается, как А|В Пример: А: Сергей купил пирожок В: Сергей купил пиццу А | В: Сергей купил пирожок и не купил пиццу.

Опр. Стрелка Пирса – логическая операция в результате применения которой, составное высказывание истинно, тогда, когда ложны оба входящих в него высказывания. Логическая связка – или..не на языке Паскаль - nor Если А и В – простые высказывания, то исключающее или обозначается, как АВ

Базовый набор операций С помощью операций дизъюнкции, конъюнкции и отрицания можно реализовать любую логическую операцию. ИЛИИ НЕ базовый набор операций

В составных высказываниях логические операции выполняются в следующем порядке: 1.Действия в скобках 2.Отрицание (не) 3.Конъюнкция (и) 4.Дизъюнкция (или) и исключающее ИЛИ 5.Импликация 6.Эквиваленция

Таблицы истинности АВА V В А Λ В А В А|ВА|В Вы научитесь решать задачи алгебры логики выучите таблицу истинности наизусть!!!

Задание 1 Запишите в алгебраической форме высказывания: а) если (а или (b и с)), то d; б) если (не а и не b), то (с или d); в) (а или b) тогда и только тогда, когда (с и не d). Решение: а) (а V b Λ с) d;

Задание 2 Найдите значения логических выражений: 1.(1 V 1) V (1 V 0) 2.((1 V 0) V 1) V 1) 3.(0 V 1) V (1 V 0) 4.(0 Λ 1) Λ Λ (1 Λ 1) Λ 1 6.((1 Λ 0) Λ (1 Λ 1)) Λ (0 Λ 1) 7.((1 Λ 0) V (1 Λ 0)) V 1 8.((1 Λ 1) V 0) Λ (0 V 1) 9.((0 Λ 0) V 0) Λ (1 V 1) =1 V 1 = 1 (см. таблицу истинности) 11

Задание 3 Определите истинность составных высказываний: 1) "(2 х 2 = 4 или 3 х 3 = 10) и (2 х 2 = 5 или 3 х 3 = 9)" 2) "(2 х 2 = 4 и 3 х 3 = 10) или (2 х 2 = 5 и 3 х 3 = 9)" 3) "(2 х 2 = 4 и 3 х 3 = 10) и (2 х 2 = 5 и 3 х 3 = 9) " Решение: 1) (1 V 0) Λ(0 V 1)=1 Λ 1=1