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

А\/1=1 А\/0=А

А&1=A A&0=0

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

A    NOT A

0    1

1    0

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

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

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

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. Упростить выражения  так, чтобы в полученных формулах не содержалось отрицания сложных высказываний.

Решение: 
 

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

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

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

Дави́д Ги́льберт (нем. David Hilbert; 23 янв

аря 1862 — 14 февраля 1943) — немецкий математик-универсал, внёс значительный вклад в развитие многих областей математики. В 1910—1920-е годы (после смерти Анри Пуанкаре) был признанным мировым лидером математиков. Гильберт разработал широкий спектр фундаментальных идей во многих областях математики, в том числе теорию инвариантов и аксиоматику евклидовой геометрии. Он сформулировал теорию гильбертовых пространств, одну из основ современного функционального анализа^[4].

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

Логическое выражение, составленное из одного или нескольких простых (или сложных) логических выражений, связанных с помощью логических операций.