Основные законы алгебры логики.

Основные понятия математической логики.

Высказывания (суждение)- это повествовательное предложение, в котором что-либо утверждается или отрицания. По поводу любого высказывания можно сказать, истинно оно или ложно .

Например:

“Лёд- твёрдое состояние воды” - истинное высказывание.

“Треугольник- это геометрическая фигура” - истинное высказывание.

“Париж- столица Китая” - ложное высказывание.

B<5- ложное высказывание.

Логические величины: понятия, выраженные словами: ИСТИНА, ЛОЖЬ (TRUE , FOLSE)

Следовательно, истинность высказывания выражается через величины.

Логические константы- ИСТИНА ИЛИ ЛОЖЬ.

Логическая переменная: символически обозначенная логическая величена.

Следовательно, если известно, что A,B,X,Y и пр.- переменные логические, то это значит, что огни могут принимать значение только ИСТИНА ИЛИ ЛОЖЬ.

Логическое выражение- простые или сложные высказывания.

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

Логические операции. В математической логике определены пять основных логических операций: конъюнкция 1-ые три

дизъюнкция составляют

отрицание полную систему

импликация операций

эквивалентность

В информатике обычно используют первые три операции.

Конъюнкция (логическое умножение)

В русском языке выражается союзом “и”.

В математической логике используются знаки & или L.

Конъюнкция - двухместная операция, записывается в виде

Р=ALB или Р= A&B.

Значение такого выражения будет ложь, если хотя бы значение одного из операторов ложно.

Таблица истинности функции логического умножения

Дизъюнкция (логическое сложение)

В русском языке этой связке соответствует союз ИЛИ.

В математической логике оно обозначается знаком V .

Дизъюнкция- двухместная операция, записывается в виде

Р = A v B

Значение этого выражения будет ИСТИНА , если значение хотя бы одного из операторов истина.

Таблица истинности функции логического сложения

Отрицание.

В русском языке этой связке соответствует союз НЕ .

Отрицание- одноместная (унарная операция)

В математической логике оно обозначается знаком Ø А или А.

Высказывание А истинно, когда А ложно, и ложно, когда А истинно.

Таблица истинности функции логического отрицания

Х	Р= Х

Импликация (логическое следование, от implicatio – тесно связывать)

Эта операций в классической логике выражается словосочетанием “Если.., то .” или В необходимо для А , А достаточно для В.

Импликация - двухместная операция, записывается в виде

Р=А→В.

По определению импликация всегда истинна , за исключением случая когда А истинно ,а В ложно.

Таблица истинности логической функции импликации

Из первых двух строчек таблицы следует , обычно использующееся в классической логике, утверждение “из лжи можно вывести всё что угодно” , то есть получить как истинное, так и ложное высказывание. Например А) Если 2+3=4, то 2*2=4 Б) Если 2+3=4, то 2*2=5

Очень часто высказывание, стоящее после слова “Если” , называется основанием или посылкой ,а стоящее после слова “то” называется следствием или заключением. Например “Если идет дождь, то земля мокрая”.

Здесь простое высказывание “идет дождь” – основное , а следствие “земля мокрая”.

Эквиваленция (эквивалентность, дойная импликация, от aequivalens – равноценное, равнозначное).

Операция равенства, выражаемое связками «тогда и только тогда», «необходимо и достаточно», «…равносильно…», называется эквиваленцией или двойной импликацией.

Эквиваленция двухместная операция, обозначается

Р=А↔В или

Р=А~В.

Сложное высказывание Р=А↔В (читается: А эквивалентно В) истинно тогда и только тогда, когда А истинно и В истинно, либо А ложно и В ложно, т.е. когда совпадают. В остальных случаях Р=А↔В ложно.

Таблица истинности составного высказывания А↔В .

Порядок выполнения логических операций:

Операция отрицания (НЕ)

Операция конъюнкции (И)

Операция дизъюнкции (ИЛИ)

Операция импликации.

Основные законы алгебры логики.

Переместительный закон коммутативности:

Для логического сложения

xÚy=yÚx

x+y=y+x

для логического умножения

xÙy=yÙx

xy=yx

Сочетательный законассоциативности:

Для логического сложения

xÚ(yÚz)=(xÙy)Ùz

x+(y+z)=(x+y)+z

для логического умножения

(x/\y)/\z=x/\(y/\z)

(xy)z=x(yz)

Распределительный , или дистрибутивный, закон:

Для логического сложения

(x\/y)/\z=(x/\z)\/(y/\z)

(x+y)z=xz+yz

для логического умножения

(x/\y)\/z=(x\/z)/\(y\/z)

xy+z=(x+z)(y+z)

Закон инверсии:

Для логического сложения

x\/y = x /\ y

x+y=xy

для логического умножения

x/\y = x \/ y

xy = x + y

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

Всегда истинные высказывания:

X+1=1

X + x= 1(закон исключённого третьего)

Не нашли, что искали? Воспользуйтесь поиском по сайту: