Алгебра логики Учитель физики, математики, информатики Цапов О. В. с. Александров-Гай, 2009 г.

1. Формы мышления В основе современной логики лежат учения, созданные ещё древнегреческими мыслителями, хотя первые учения о формах и способах мышления возникли в Древнем Китае и Индии. Основоположником формальной логики является Аристотель, который впервые отделил логические формы мышления от его содержания.

Логика Логика – это наука о формах и способах мышления. Это учение о способах рассуждений и доказательств. Законы мира, сущность предметов, общее в них мы познаём посредством абстрактного мышления. Логика позволяет строить формальные модели окружающего мира, отвлекаясь от содержательной стороны. Мышление всегда осуществляется через понятия, высказывания и умозаключения.

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

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

Пример 2. Истинное высказывание: «Буква «а» - гласная». Ложное высказывание: «Компьютер был изобретён в середине XIX века».

Упражнение 1. Какие из предложений являются высказываниями? Определите их истинность. 1.Какой длины эта лента? 2.Прослушайте сообщение. 3. Делайте утреннюю зарядку! 4. Назовите устройство ввода информации. 5. Кто отсутствует? 6. Париж – столица Англии. 7. Число 11 является простым = Без труда не вытащишь и рыбку из пруда. 10. Сложите числа 2 и Все медведи – бурые. 12. Чему равно расстояние от Москвы до Ленинграда.

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

Пример 3. Дано высказывание: «Все углы равнобедренного треугольника равны». Получить высказывание «Этот треугольник равносторонний» путём умозаключений. Пусть основанием треугольника является сторона с. Тогда а=b. Так как в треугольнике все углы равны, следовательно, основанием может быть любая другая сторона, например, а. Тогда b=с. Следовательно а=b=с. Треугольник равносторонний.

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

Логическая переменная Логическая переменная – это простое высказывание, содержащее только одну мысль. Её символическое обозначение – латинская буква (например, A, B, X, Y и т.д.). Значением логической переменной могут быть только константы ИСТИНА (1) и ЛОЖЬ (0). Можно определить понятия логической переменной, логической функции и логической операции.

логическая функция Составное высказывание – логическая функция, которая содержит несколько простых мыслей, соединённых между собой с помощью логических операций. Её символическое обозначение – F (A, B, …). На основании простых высказываний могут быть построены составные высказывания. Логические операции Логические операции – логическое действие.

Рассмотрим три базовые логические операции – конъюнкцию, дизъюнкцию и отрицание и дополнительные – импликацию и эквивалентность.

логическое выражение Если составное высказывание (логическую функцию) выразить в виде формулы, в которую войдут логические переменные и знаки логических операций, то получится логическое выражение, значение которого можно вычислить. Значением логического выражения могут быть только ЛОЖЬ или ИСТИНА. При составлении логического выражения необходимо учитывать порядок выполнения логических операций, а именно: 1)Действия в скобках; 2)Инверсия, конъюнкция, дизъюнкция, импликация, эквивалентность.

Пример 4. Записать в виде логического выражения следующее высказывание: «Летом Петя поедет в деревню и, если будет хорошая погода, то он пойдёт на рыбалку». 1.Проанализируем составное высказывание. Оно состоит из следующих простых высказываний: «Петя поедет в деревню», «Будет хорошая погода», «Он пойдёт на рыбалку». Обозначим их через логические переменные: А = Петя поедет в деревню; B = Будет хорошая погода; С = Он пойдёт на рыбалку. 2. Запишем высказывание в виде логического выражения, учитывая порядок действий. Если необходимо, расставим скобки: F = A & (BC).

Упражнение 2. Есть два простых высказывания: А – «Число 10 – чётное»; В – «Волк – травоядное животное». Составьте из них все возможные составные высказывания и определите их истинность. А&BАvB¬А¬А¬В¬ВАВАВАВАВ

Упражнение 3. Запишите следующие высказывания в виде логических выражений: 1.Число 17 нечётное и двузначное. 2.Неверно, что корова – хищное животное. 3.Тише едешь – дальше будешь. Решение: 1.А – «Число 17 – нечётное», В – «Число 17 – двузначное» А & В 2. А – «Корова – хищное животное» ¬ А 3. А – «Тише едешь», В – «Дальше будешь» А В

3. Таблицы истинности АВ F = А & В F = А v В Логическое умножение (конъюнкция) и логическое сложение (дизъюнкция)

Логическое отрицание (инверсия)А F = ¬ А 01 10

Пример 5. иF=А&В=0 1.«22=4 и 33=10»; F=А&В=0 илиF=АvВ=1 2.«22=4 или 33=10»; F=АvВ=1 F=¬А=0 3.«224»; F=¬А=0

АВ F = А В Логическое следование (импликация) логического следования (импликации), Составное высказывание, образованное с помощью операции логического следования (импликации), ложно тогда и только тогда, когда из истинной предпосылки (первого высказывания) следует ложный вывод (второе высказывание).

АВ F = А В Логическое равенство (эквивалентность) логической операции эквивалентности Составное высказывание, образованное с помощью логической операции эквивалентности истинно тогда и только тогда, когда оба высказывания одновременно либо ложны, либо истинны.

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

1. Закон тождества А = А Всякое высказывание тождественно самому себе. 2. Закон непротиворечия А & ¬А = 0 Логическое произведение высказывания и его отрицания является ложным.

3. Закон исключённого третьего А v ¬А = 1 Логическое сложение высказывания и его отрицания является истинным. 4. Закон двойного отрицания ¬(¬А) = А Двойное отрицание некоторого высказывания равно исходному высказыванию.

5. Законы де Моргана ¬(АvВ) = ¬А & ¬В ¬(А&В) = ¬А v ¬В 6. Закон коммутативности А&В = В&А АvВ = ВvА

7. Закон ассоциативности (А&В)&С = А&(В&С) (АvВ)vС = Аv(ВvС) Если в логическом выражении используются только операции логического умножения или только операция логического сложения, то можно пренебрегать скобками или произвольно их расставлять.

8. Закон дистрибутивности (А&В)v(А&С) = А&(ВvС) (АvВ)&(АvС) = Аv(В&С) В отличие от обычной алгебры, в алгебре высказываний можно выносить за скобки как общие множители, так и общие слагаемые.

Пример 6. Упростить логическое выражение: (А & В) v (А & ¬В). 1. Воспользуемся законом дистрибутивности и вынесем за скобки А: (А & В) v (А & ¬В) = А & (В v ¬В). 2. По закону исключённого третьего В v ¬В = 1, следовательно: А & (В v ¬В) = А & 1 = А.

Самостоятельная работа Вариант Соедините правильные определения или обозначения: 1)Логика 2)Дизъюнкция 3)Импликация 4)Высказывание 5)Инверсия 6)Алгебра логики 7)Конъюнкция 8)Логическая константа 9)Эквивалентность 1)АВ 2)Логическое сложение 3)Наука о формах и способах мышления 4)Логическое отрицание 5)ИСТИНА и ЛОЖЬ 6)АВ 7)& 8)Наука об операциях над высказываниями 9)Повествовательное предложение, в котором что-либо утверждается или отрицается

Вариант 1 2. Даны высказывания: А={33=9}, В={33=10}. Определите истинность высказываний: 1) А; 4) В; 2) ¬В; 5) ¬А; 3) А&В; 6) АvВ. 3.Заполните таблицу: АВ ¬А¬А¬А¬А АvВАvВАvВАvВ Вариант 2 2. Даны высказывания: А={5+7=13}, В={5+7=12}. Определите истинность высказываний: 1) А; 4) В; 2) ¬В; 5) ¬А; 3) А&В; 6) АvВ. 3.Заполните таблицу:АВ ¬В¬В¬В¬В А&ВА&ВА&ВА&В Самостоятельная работа