Презентация на тему: Алгебра логики

Алгебра логики

Алгебра логики — это математический аппарат, с помощью которого записывают, вычисляют, упрощают и преобразовывают логические высказывания.

Возникновение логики Понятие логики как науки появилось ещё в  XIX в., т.е. задолго до появления науки информатики и компьютеров. Элементы математической логики можно найти уже в работах древнегреческих философов. В XVII в. Г. В. Лейбниц высказал идею о том, что рассуждения могут быть сведены к механическому выполнению определенных действий по установленным правилам. Однако как самостоятельный раздел математики логика начала формироваться только с середины XIX в..

Употребляемые в обычной речи слова и словосочетания "не”, “и”, “или”, “если... , то”, “тогда и только тогда” и другие позволяют из уже заданных высказываний строить новые высказывания. Такие слова и словосочетания называются логическими связками.

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

Так, например, из элементарных высказываний “Петров — врач”, “Петров — шахматист” при помощи связки “и” можно получить составное высказывание “Петров — врач и шахматист”, понимаемое как “Петров — врач, хорошо играющий в шахматы”. При помощи связки “или” из этих же высказываний можно получить составное высказывание “Петров — врач или шахматист”, понимаемое в алгебре логики как “Петров или врач, или шахматист, или и врач и шахматист одновременно”. Истинность или ложность получаемых таким образом составных высказываний зависит от истинности или ложности элементарных высказываний.

Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение: (1) Операция, выражаемая словом “не”, называется отрицанием и обозначается чертой над высказыванием (или знаком щ ). Высказывание истинно, когда A ложно, и ложно, когда A истинно. Пример. “Луна — спутник Земли” (А); “Луна — не спутник Земли” ( ).

(2) Операция, выражаемая связкой “и”, называется конъюнкцией (лат. conjunctio — соединение) или логическим умножением и обозначается точкой "•" (может также обозначаться знаками Щ или &). Высказывание А•В истинно тогда и только тогда, когда оба высказывания А и В истинны. Например, высказывание “10 делится на 2 и 5 больше 3” истинно, а высказывания “10 делится на 2 и 5 не больше 3”, “10 не делится на 2 и 5 больше 3”, “10 не делится на 2 и 5 не больше 3” ложны.

(3) Операция, выражаемая связкой “или” (в неразделительном, неисключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio — разделение) или логическим сложением и обозначается знаком v (или плюсом). Высказывание А v В ложно тогда и только тогда, когда оба высказывания А и В ложны. Например, высказывание “10 не делится на 2 или 5 не больше 3” ложно, а высказывания “10 делится на 2 или 5 больше 3”, “10 делится на 2 или 5 не больше 3”, “10 не делится на 2 или 5 больше 3” истинны.

(4) Операция, выражаемая связками “если ..., то”, “из ... следует”, “... влечет ...”, называется импликацией (лат. implico — тесно связаны) и обозначается знаком . Высказывание А В ложно тогда и только тогда, когда А истинно, а В — ложно. Например, даны 2 высказывания: “данный четырёхугольник — квадрат” (А) и “около данного четырёхугольника можно описать окружность” (В).

Рассмотрим составное высказывание А В, понимаемое как “если данный четырёхугольник квадрат, то около него можно описать окружность”. Есть три варианта, когда высказывание А В истинно: А истинно и В истинно, то есть данный четырёхугольник квадрат, и около него можно описать окружность; А ложно и В истинно, то есть данный четырёхугольник не является квадратом, но около него можно описать окружность (разумеется, это справедливо не для всякого четырёхугольника); A ложно и B ложно, то есть данный четырёхугольник не является квадратом, и около него нельзя описать окружность. Ложен только один вариант: А истинно и В ложно, то есть данный четырёхугольник является квадратом, но около него нельзя описать окружность.

(5) Операция, выражаемая связками “тогда и только тогда”, "необходимо и достаточно”, “... равносильно ...”, называется эквиваленцией или двойной импликацией и обозначается знаком или ~ . Высказывание А В истинно тогда и только тогда, когда значения А и В совпадают.

Существуют и другие логические операции: Операция, выражаемая связками “если ..., то”, “из ... следует”, “... влечет ...”, называется импликацией. Операция, выражаемая связками “тогда и только тогда”, "необходимо и достаточно”, “... равносильно ...”, называется эквиваленцией или двойной импликацией. Импликацию можно выразить через дизъюнкцию и отрицание. Эквиваленцию можно выразить через отрицание, дизъюнкцию и конъюнкцию.

Любое высказывание можно формализовать, то есть заменить логической формулой. Формулы, принимающие значение “истина” при любых значениях истинности входящих в них переменных называются тождественно истинными формулами или тавтологиями. Формулы, принимающие значение “ложно” при любых значениях истинности входящих в них переменных , называются тождественно ложными формулами или противоречиями. Две формулы при одинаковых наборах значений входящих в них переменных, принимающие одинаковые значения, называются равносильными.

Логический элемент компьютера — это часть электронной логичеcкой схемы, которая реализует элементарную логическую функцию. Таблица истинности это табличное представление логической схемы (операции), в котором перечислены все возможные сочетания значений истинности входных сигналов (операндов) вместе со значением истинности выходного сигнала (результата операции) для каждого из этих сочетаний.

С х е м а   И

Таблица истинности

С х е м а   ИЛИ

Таблица истинности

С х е м а   НЕ

Таблица истинности

С х е м а   И - НЕ

Таблица истинности

С х е м а   ИЛИ - НЕ

Таблица истинности

Преобразование выражений, состоящих из булевых функций от перестановки мест аргументов результат не изменяется A & B = B & A существует следующий закон A & (B & C)  = (A & B) & C Также существуют некоторые тождества, опирающиеся на особые свойства функции, например: 1) A & (~A) = ЛОЖЬ 2) (~A) & (~B) = ~ (A v B) Аналогично, сложение и логическое «ИЛИ»: от перестановки мест аргументов результат не изменяется A v B =  B v A существует следующий закон (A v B) v С = A v (B v C) можно выносить общий множитель за скобки (A & B) v (С & B) = B & (A v C) И также некоторые собственные законы: 1) A v (~A) = ИСТИНА 2) (~A) v (~B) = ~ (A & B)

Самостоятельная работа №8 Что такое алгебра логики? Перечислите основные логические операции? Что такое логический элемент компьютера?