Основные понятия алгебры логики. Логические выражения и логические операции (Лекция 05) презентация

ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ. ЛОГИЧЕСКИЕ ВЫРАЖЕНИЯ И ЛОГИЧЕСКИЕ ОПЕРАЦИИ

ОСНОВНЫЕ ПОНЯТИЯ АЛГЕБРЫ ЛОГИКИ Алгебра – это раздел математики, предназначенный для описания действий над переменными величинами, которые принято обозначать строчными латинскими буквами, например a, b, x, y и т.д. Логика (древнегреч. – слово logos, означает «мысль, понятие, рассуждение, закон») - наука о законах и формах мышления. Алгебра логики изучает общие операции над высказываниями.

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ Аристотель (384-322 гг. до н.э.) – древнегреческий философ, основоположник логики. Книги: «Категории» «Первая аналитика» «Вторая аналитика» Исследовал различные формы рассуждений, ввел понятие силлогизма.

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ Силлогизм - рассуждение, в котором из заданных двух суждений выводится третье. Все млекопитающие имеют скелет. Все киты - млекопитающие. Следовательно, все киты имеют скелет. Все квадраты - ромбы. Все ромбы - параллелеграммы. Следовательно, все квадраты - параллелограммы.

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ Аристотель выделил все правильные формы силлогизмов, которые можно составить из рассуждений вида: «Все а суть в» «Некоторые А суть В» «Все А не суть В» «Некоторые А не суть В» Логика, основанная на теории силлогизмов, называется классической.

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ Декарт Рене (1596-1650, французский философ, математик) –

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ Лейбниц Готфрид Вильгельм (1646-1716, немецкий ученый и математик) –

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ Джордж Буль (1815-1864, английский математик-самоучка, основоположник математической логики)

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ Огастес де Морган (1806 – 1871, шотландский математик и логик) -

ЭТАПЫ РАЗВИТИЯ ЛОГИКИ Платон Сергеевич Порецкий (1846-1907) – русский астроном, математик.

ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ Логика оказала влияние на развитие математики, прежде всего теории множеств, функциональных систем, алгоритмов, рекурсивных функций. В гуманитарных науках (логика, криминалистика). Математическая логика является средством для изучения деятельности мозга – для решения этой самой важной проблемы биологии и науки вообще. Идеи и аппарат логики используется в кибернетике, вычислительной технике и электротехнике (компьютеры построены на основе законов математической логики). Идеи и аппарат логики используется в программировании, базах данных и экспертных системах (PROLOG – язык логического программирования).

ПРИМЕНЕНИЕ МАТЕМАТИЧЕСКОЙ ЛОГИКИ 1938 г. – американский инженер и математик и инженер Клод Шеннон (1916 – 2001) связал Булеву алгебру (аппарат математической логики), двоичную систему кодирования и релейно-контактные переключательные схемы, заложив основы будущих ЭВМ.

АЛГЕБРА ВЫСКАЗЫВАНИЙ Алгебра логики (высказываний) - раздел математической логики, изучающий высказывания и логические операции над ними.

АЛГЕБРА ВЫСКАЗЫВАНИЙ Высказывание (суждение) – любое повествовательное предложение в отношении которого можно однозначно сказать, истинно оно или ложно. Примеры высказываний: 1) Земля - планета Солнечной системы. 2) 2+8<5 3) 55=25 4) Всякий квадрат есть параллелограмм 5) Каждый параллелограмм есть квадрат 6) 22=5

АЛГЕБРА ВЫСКАЗЫВАНИЙ Высказываниями не являются: 1) восклицательные и вопросительные предложения; 2) определения; 3) предложения типа: «он сероглаз» «x2-4x+3=0»

АЛГЕБРА ВЫСКАЗЫВАНИЙ Определите какие из следующих выражений являются высказываниями: Число 6 – четное. Здравствуйте! Все роботы являются машинами. Кто отсутствует? Выразите 1 ч 15 мин в секундах. А – первая буква в алфавите.

АЛГЕБРА ВЫСКАЗЫВАНИЙ Определите истинность высказываний. Треугольник – геометрическая фигура. У каждой лошади есть хвост. Париж – столица Китая. Лед – твердое состояние воды. Все люди – космонавты.

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

АЛГЕБРА ВЫСКАЗЫВАНИЙ 2. Логические переменные (предикаты) – логические высказывания, значения которых меняются в зависимости от входящих в них переменных, обозначаются заглавными латинскими буквами А, В, С, D, F,… А = {Аристотель - основоположник логики} В = {На яблонях растут бананы}. Истинному высказыванию ставится в соответствие 1, ложному — 0. Таким образом, А = 1, В = 0.

АЛГЕБРА ВЫСКАЗЫВАНИЙ 3. Логические функции ( логические формулы) – сложные логические выражения, образованные из простых и связанные логическими операциями И, ИЛИ, НЕ и др.) Высказывание «Все мышки и кошки с хвостами» является сложным и состоит из двух простых высказываний. А=«Все мышки с хвостами» и В=«Все кошки с хвостами» Его можно записать в виде логической функции, значение которой истинно: F(A,B)=A и B

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

АЛГЕБРА ВЫСКАЗЫВАНИЙ В алгебре логики высказывания принято обозначать прописными латинскими буквами: A, B, X, Y. Действия, которые производятся над высказываниями, записываются в виде логических выражений. Высказывание (логическое выражение) может принимать только одно из двух значений – ИСТИНА (1) или ЛОЖЬ (0). Истина, ложь – логические константы.

АЛГЕБРА ВЫСКАЗЫВАНИЙ Логические выражения бывают простыми или сложными. Простое логическое выражение состоит из одного высказывания и не содержит логические операции. В нём возможно только два результата – либо «истина», либо «ложь». На улице светит солнце. (А) На улице идет дождь. (В)

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

ОСНОВНЫЕ ОПЕРАЦИИ АЛГЕБРЫ ЛОГИКИ Основные логические операции: НЕ (логическое отрицание, инверсия) ИЛИ (логическое сложение, дизъюнкция) И (логическое умножение, конъюнкция)

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Конъюнкция (логическое умножение) – соединение двух логических выражений (высказываний) с помощью союза И. Обозначение: и, and, ×, & ,  Логическая операция конъюнкция истинна только в том случае, если оба простых высказывания истинны, в противном случае она ложна. А – У меня есть знания для сдачи зачета. В – У меня есть желание для сдачи зачета. У меня есть знания и желание для сдачи зачета. A  B

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Все операции алгебры логики определяются таблицами истинности значений. Таблица истинности определяет результат выполнения операций для всех возможных логических значений исходных высказываний.

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Таблица истинности конъюнкции:

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Дизъюнкция (логическое сложение) – соединение двух логических высказываний с помощью союза ИЛИ. Обозначение: или, or, +, V Логическая операция дизъюнкция ложна, если оба простых высказывания ложны. В остальных случаях она истинна. A – Летом я поеду в лагерь B – Летом я поеду к бабушке Летом я поеду в лагерь или поеду к бабушке A V B

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Таблица истинности дизъюнкции:

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Отрицание (инверсия) – операция логического отрицания. Добавляется частица НЕ или слова НЕВЕРНО,ЧТО… Обозначение: не, not, ¬ , ¯. Если исходное выражение истинно, то результат его отрицания будет ложным, и наоборот, если исходное выражение ложно, то оно будет истинным. А – Земля вращается вокруг Солнца – истинно ¬А – Земля не вращается вокруг Солнца – ложно

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Таблица истинности отрицания:

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Импликация (логическое следование) – связывает два логических выражения, из которых первое является условием, а второе – следствием из этого условия. Операция обозначается словами: «Если…, то…» (Если А, то В). Обозначение: →,  Результат операции импликации ложен только тогда, когда предпосылка А истинна, а заключение В (следствие) ложно. А – идёт дождь В – на улице сыро Если идёт дождь, то на улице сыро. А → В

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Таблица истинности импликации:

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Эквивалентность (логическое тождество, равнозначность) – определяет результат сравнения двух логических выражений. Операция обозначается словами: «…тогда и только тогда, когда…» (А т. и т. т. когда В) Обозначение:  ,  ,  , ~ Результат операции эквивалентность истинен только тогда, когда А и В одновременно истинны или одновременно ложны. А – день сменяет ночь В – солнце скрывается за горизонтом День сменяет ночь тогда и только тогда, когда солнце скрывается за горизонтом. А ~ В

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Таблица истинности эквивалентности:

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Приоритет выполнения логических операций в сложном логическом выражении: Инверсия (отрицание) Конъюнкция (умножение) Дизъюнкция (сложение) Импликация (следование) Эквивалентность (тождество) Для изменения указанного порядка выполнения логических операций используются скобки.

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

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Построение таблицы истинности сложных ЛВ: 1) определить число простых ЛВ (n); 2) определить число строк в таблице истинности (q=2n); 3) записать все возможные значения простых ЛВ; 4) определить количество логических операций и их порядок; 5) записать логические операции в таблицу истинности и определить для каждой значение.

ОСНОВНЫЕ ЛОГИЧЕСКИЕ ОПЕРАЦИИ Задание 1: Постройте таблицу истинности сложного ЛВ

Построение логических выражений по таблице истинности: 1) записать логическое умножение всех простых ЛВ для каждой строки, в которой сложное ЛВ = 1 (если значение простого ЛВ = 0, то берется его отрицание); 2) логически сложить полученные выражения.

Составьте сложное логическое выражение по таблице истинности