Логические основы алгоритмизации

Элементарные логические операции.

ИСТОРИЯ:

Начало исследований в области формальной логики было положено Аристотелем в IV в. до н.э. Однако математические подходы к этим вопросам были впервые указаны Джорджем Булем, который положил в основу математической логики алгебру логики (булеву, а логические значения называют булевыми). Алгебра логики используется при построении основных узлов ЭВМ, например, таких как шифратор, сумматор и др.

Итак, алгебра логики оперирует с высказываниями, т.е. повествовательными предложениями, о которых можно сказать (И) - Истинно оно или (Л) - Ложно. Например: «4< 3» -ложно, «Москва больше Саратова»- истинно. Высказывания обозначают большими латинскими буквами и пишут A= 1(t,true),B= 0 (f, false).

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

Наиболее часто используются логические операции, выражаемые словами «и», «или», «не». А именно:

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

Опред. Соединение двух (или несколько) высказываний в одно с помощью союза И (AND) называется конъюнкцией (или операцией логического умножения). Обозначаются Л, &, х. Значения логических операций определяются по правилам, задаваемым в таблице истинности.

Истинность конъюнкции задается следующей таблицей.

А	В	А & В

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

Опред. Соединение двух (или несколько) высказываний в одно с помощью союза ИЛИ (OR) называется дизъюнкцией (или логического сложения). Обозначаются I, V, +.

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

А	В	А V В	А хor В

Xor-модифицированная операция «ИЛИ» исключающее или (хor), от обычного «ИЛИ» отличается последней строкой.

3. Отрицание (инверсия)

Опред. Присоединение частицы НЕ (NOT) к данному высказыванию называется операцией отрицания (инверсии). Ā, ¬ А – «не А»

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

А	¬ А

Существует помимо этих 3-х и ряд других операций.

Например:

4.Эквивалентности. Обозначаются А ~ В (А ≡ В, А eqv В)

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

А	В	А ~ В

5. Операция импликации (логического следования). Обозначаются А→ В,

(А imp В). Объединяет высказывания словами «если…, то …».

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

А	В	А→ В

Логические операции можно применять многократно.

Дата добавления: 2014-01-03