Основи алгоритмізації та програмування (Циммерман О.В.)

Закон, выражающий дистрибутивность (распределительность) одной данной логической или математической операции относительно другой данной операции. Примером этого закона может служить закон обычной арифметики: а (b + с) = аb + ас, выражающий распределительность умножения относительно сложения.

Формула закона:

.

.

1. Закон двойного отрицания (двойное отрицание исключает отрицание):

   А = .

• для логического сложения: А Ú B = B Ú A;

• для логического умножения: A & B = B & A.

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

• для логического сложения: (А Ú B) Ú C = A Ú (B Ú C);

• для логического умножения: (A & B) & C = A & (B & C).

При одинаковых знаках скобки можно ставить произвольно или вообще опускать.

• для логического сложения: (А Ú B) & C = (A & C) Ú (B & C);

• для логического умножения: (A & B) Ú C = (A Ú C) & (B Ú C).

Закон определяет правило выноса общего высказывания за скобку.

• для логического сложения: =  &;

• для логического умножения: =   Ú 

• для логического сложения: А Ú A = A;

• для логического умножения: A & A = A .

Закон означает отсутствие показателей степени.

• для логического сложения: А Ú 1 = 1, А Ú 0 = A;

• для логического умножения: A & 1 = A, A & 0 = 0.

• A &  = 0.

Невозможно, чтобы противоречащие высказывания были одновременно истинными.

• A Ú  = 1.

Из двух противоречащих высказываний об одном и том же предмете одно всегда истинно, а второе — ложно, третьего не дано.

• для логического сложения: А Ú (A & B) = A;

• для логического умножения: A & (A Ú B) = A.

Знание законов логики позволяет проверять правильность рассуждений и доказательств. Основываясь на законах, можно выполнять упрощение сложных логических выражений. Такой процесс замены сложной логической функции более простой, но равносильной ей, называется минимизацией функции.

Некоторые преобразования логических формул похожи на преобразования формул в обычной алгебре (вынесение общего множителя за скобки, использование переместительного и сочетательного законов и т.п.), другие - основаны на свойствах, которыми не обладают операции обычной алгебры (использование распределительного закона для конъюнкции, законов поглощения, склеивания, де Моргана и др.).

Нарушения законов логики приводят к логическим ошибкам и вытекающим из них противоречиям.

Упрощение формул.

Пример 1. Упростить формулу (А Ú В) & (А Ú С).

Решение:

Таким образом, мы доказали закон дистрибутивности.

Всякую формулу можно преобразовать так, что в ней не будет отрицаний сложных высказываний - все отрицания будут применяться только к простым высказываниям.

Пример 2. Упростить выражения  так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.

Решение: 
 

В конструктивную математическую логику А. А. Марков вводит понятие «разрешимое высказывание» и связанное с ним понятие «прямое отрицание». В логике А. А. Маркова имеется и другой вид отрицания — усиленное отрицание, относящееся к так называемым полуразрешимым высказываниям.

Кроме материальной и усиленной импликации, при установ­лении истинности которых приходится заботиться об истинности посылки и заключения, А. А. Марков вводит дедуктивную имп­ликацию, определяемую по другому принципу. Дедуктивная имп­ликация «если А, то В»выражает возможность выведения В из А по фиксированным правилам, каждое из которых в применении к верным формулам даст верные формулы. Всякое высказывание, выводимое из истинного высказывания, будет истинным.

Через дедуктивную импликацию А. А. Марков определяет редукционное отрицание (reductio ad absurdum). Редукционное отрицание высказывания А (сформулированного на данном язы­ке) понимается как дедуктивная импликация «если А, то Л», где через Л обозначен абсурд. Это определение отрицания соответ­ствует обычной практике рассуждений математика: математик отрицает ту посылку, из которой вытекает абсурд. Для установ­ления истинности редукционного отрицания высказывания не требуется вникать в смысл этого высказывания. Высказывание, для которого установлена истинность редукционного отрицания, не может быть истинным.

Английский математик и логик. Профессор математики Королевского колледжа Корка с 1849 года. Один из основателей математической логики. Буль был, вероятно, первым после Джона Валлиса математиком, обратившимся к логической проблематике. Буль не считал логику разделом математики, но находил глубокую аналогию между символическим методом алгебры и символическим методом представления логических форм и силлогизмов.На математические темы Булем в течение жизни были созданы два систематических трактата: «Трактат о дифференциальных уравнениях» (1859; второе издание не завершено, материалы к нему опубликованы посмертно в 1865) и задуманный как его продолжение «Трактат о конечных разностях» (1860). Эти труды внесли важный вклад в соответствующие разделы математики и в то же время продемонстрировали глубокое понимание Булем философии своего предмета.

 американский инженер, криптоаналитик и математик. Cчитается «отцом информационного века».

Является основателем теории информации, нашедшей применение в современных высокотехнологических системах связи. Предоставил фундаментальные понятия, идеи и их математические формулировки, которые в настоящее время формируют основу для современных коммуникационных технологий. Его статьи «Математическая теория связи» и «Теория связи в секретных системах» считаются основополагающими для теории информации и криптографии. Клод Шеннон был одним из первых, кто подошел к криптографии с научной точки зрения, он первым сформулировал ее теоретические основы и ввел в рассмотрение многие основные понятия. Шеннон внес огромный вклад в теорию вероятностных схем; теорию игр; теорию автоматов и теорию систем управления — области наук, входящие в понятие «кибернетика».

В 1948 году предложил использовать слово «бит» для обозначения наименьшей единицы информации (в статье «Математическая теория связи»). Кроме того, понятие энтропии было важной особенностью теории Шеннона. Он продемонстрировал, что введенная им энтропия эквивалентна мере неопределённости информации в передаваемом сообщении

Таблица истинности — это таблица, описывающая логическую функцию.

Под «логической функцией» в данном случае понимается функция, у которой значения переменных (параметров функции) и значение самой функции выражают логическую истинность. Например, в двузначной логике они могут принимать значения «истина» либо «ложь» (True либо False, 1 либо 0).

Табличное задание функций встречается не только в логике, но для логических функций таблицы оказались особенно удобными, и с начала XX века за ними закрепилось это специальное название. Особенно часто таблицы истинности применяются в булевой алгебре и в аналогичных системах многозначной логики.

Бинарная логическая операция,  булева функция над двумя переменными. Введена в рассмотрение Генри Шеффером в 1913 г. Штрих Шеффера, обычно обозначаемый |, эквивалентен операции И-НЕ.

Таким образом, высказывание X | Y означает, что X и Y несовместны, то есть не являются истинными одновременно. От перемены мест операндов результат операции не изменяется.

Задаётся следующей таблицей истинности:

Логическая функция - это функция, которая устанавливает соответствие между одним или несколькими высказываниями, которые называются аргументами функции, и высказыванием которое называется значением функции.

Предика́т- это то, что утверждается о субъекте. Субъектом высказывания называется то, о чём делается утверждение.