Основные операции алгебры высказываний

1. Логическая операция конъюнкция (лат. conjunctio - связываю).

· В естественном языке соответствует союзу «и»;

· Обозначение: &;

· В языках программирования обозначение: and;

· Иное название: логическое умножение.

Конъюнкция - это логическая операция, ставящая в соответствие каждым двум простым высказываниям составное высказывание, являющееся истинным тогда и только тогда, когда оба исходных высказывания истинны. Таблица истинности конъюнкции:

A	B	A&B

2. Логическая операция дизъюнкция (лат. disjunctio - различаю).

· В естественном языке соответствует союзу «или»;

· Обозначение: ;

· В языках программирования обозначение: or;

· Иное название: логическое сложение.

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

Таблица истинности дизъюнкции:

A	B	A B

3. Логическая операция инверсия (лат. inversio - переворачиваю).

· в естественных языках соответствует частице «не»;

· Обозначение ;

· В языках программирования обозначение: not;

· Иное название: отрицание.

Отрицание - это логическая операция, которая каждому простому высказыванию ставит в соответствие составное высказывание, заключающееся в том, что исходное высказывание отрицается.

Таблица истинности отрицания:

A

4. Логическая операция импликация (лат. implicatio - тесно связываю).

· В естественном языке соответствует обороту Если..., то...;

·

Обозначение:→;

· Иное название: логическое следование.

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

A	B	A→B

5. Логическая операция эквиваленция (лат. аequivalens - равноценное).

· В естественном языке соответствует оборотам речи тогда и только тогда и в том и только в том случае;

· Обозначение: ~;

· иное название: равнозначность.

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

Таблица истинности эквиваленции:

A	B	A~B

Логические операции имеют следующий приоритет:

1. Действия в скобках;

2. Инверсия;

3. &;

4. ;

5. →;

6. ~.

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

Алгоритм построения таблицы истинности:

1. Подсчитать количество переменных n в логическом выражении;

2. Определить число строк в таблице m = 2 ⁿ;

3. Подсчитать количество логических операций в формуле;

4. Установить последовательность выполнения логических операций с учетом скобок и приоритетов;

5. Определить количество столбцов в таблице: число переменных плюс число операций;

6. Выписать наборы входных переменных с учетом того, что они представляют собой натуральный ряд n-разрядных двоичных чисел от 0 до 2 ⁿ -1;

7. Провести заполнение таблицы истинности по столбикам, выполняя логические операции в соответствии с установленной в п.4 последовательностью.

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

a) Определить количество наборов входных переменных;

b) Разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки 0, а нижнюю -1;

c) Разделить колонку значений второй переменной на четыре части и заполнить каждую четверть чередующимися группами 0 или 1, начиная с группы 0;

d) Продолжать деление колонок значений последующих переменных на 8, 16 и т.д. частей и заполнение их группами 0 или 1 до тех пор, пока группы 0 и 1 не будут состоять из одного символа.