Логические выражения и логические операции над высказываниями

 

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

В булевой алгебре простым высказываниям ставятся в соответствие логические переменные, значение которых равно 1, если высказывание истинно, и 0, если высказывание ложно. Обозначаются логические переменные буквами латинского алфавита A, B, C, …, X, Y,Z. Каждая логическая связка рассматривается как операция над логическими высказываниями и имеет свое название и обозначение. Действия логических операций будем представлять в виде таблиц истинности.

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

Логические операции:

1. Операция «НЕ»: Операция, выражаемая словом «не», называется инверсией (отрицанием) и обозначается чертой над высказыванием (знаком Ø, либо ¢).

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

ПРИМЕР.

А: 7 делится на 5 без остатка.

Ø А: Неверно, что 7 делится на 5 без остатка.

 

А	Ø А
0	1
1	0

Эта таблица и принимается в качестве определения операции отрицания.

2. Операция «И»: Операция, выражаемая связкой «и», называется конъюнкцией (лат. conjunctio – соединение) или логическим умножением и обозначается точкой «^. » (может также обозначаться знаками  или &).

Высказывание А × В истинно тогда и только тогда, когда оба высказывания А и В истинны.

ПРИМЕРЫ:

A. 6 делится на 3 без остатка (1);

B. 10 больше 5 (1);

C. 7 делится на 3 без остатка (0);

D. 3 больше 7 (0);

A&B =1

A&C =0

C&D =0

 

А	В	А & В
0	0	0
0	1	0
1	0	0
1	1	1

Эта таблица и принимается в качестве определения операции конъюнкции

3. Операция «ИЛИ» Операция, выражаемая связкой «или» (в не исключающем смысле этого слова), называется дизъюнкцией (лат. disjunctio – разделение) или логическим сложением и обозначается знаком .

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

ПРИМЕРЫ:

A. 6 делится на 3 без остатка (1);

B. 10 больше 5 (1);

C. 7 делится на 3 без остатка (0);

D. 3 больше 7 (0);

A B=1

A  D=1

C D=0

А	В	А В
0	0	0
0	1	1
1	0	1
1	1	1

Эта таблица и принимается в качестве определения операции дизъюнкции.

4. Операция «Исключающее ИЛИ» (Операция неравнозначности (равноименности) «строгая дизъюнкция», «сумма по модулю два»,). Строгой дизъюнкцией высказываний А и В называется высказывание, которое истинно тогда и только тогда, когда истинно только одно из этих высказываний. Обозначается знаком .

А	В	А В
0	0	0
0	1	1
1	0	1
1	1	0

 

5. Операция «ЕСЛИ-ТО»: Операция, выражаемая связками «если..., то», «из... следует», «... влечет...», называется импликацией (лат. implico — тесно связаны) или логическим следованием и обозначается знаком . Высказывание  ложно тогда и только тогда, когда А истинно, а В ложно. Высказывание А называется антецедентом, а В – консеквентом.

А	В	А В
0	0	1
0	1	1
1	0	0
1	1	1

 

6. Операция «РАВНОСИЛЬНО»: Операция, выражаемая связками «тогда и только тогда», «необходимо и достаточно», «... равносильно...», называется эквиваленцией или двойной импликацией, или логическим тождеством и обозначается знаком  или ~,или .

Высказывание  истинно тогда и только тогда, когда значения А и В совпадают.

А	В	А~В
0	0	1
0	1	0
1	0	0
1	1	1

 

7. Обратная конъюнкция И – НЕ (Штрих Шеффера  ê )

А	В	А ê В
0	0	1
0	1	1
1	0	1
1	1	0

 

8. Обратная дизъюнкция ИЛИ – НЕ (Стрелка Пирса , функция Вебба)

А	В	А В
0	0	1
0	1	0
1	0	0
1	1	0

Используя эти логические операции можно строить сколь угодно сложные высказывания. Приоритет выполнения операций: ⌐ & Ú  ~  ê

ПРИМЕР. Сложное высказывание: «Если вы не пропускаете занятия и успешно занимаетесь, то Вы сдадите экзамен хорошо» можно записать следующим образом. Обозначим:

П – пропускаете занятия;

Y – успешно занимаетесь;

Х – сдадите экзамен хорошо,

тогда все высказывание запишется:

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

ПРИМЕР.

Пусть A =1, B =0, C =0, D =1. Подставим эти значения в высказывание и получим:

Символы ⌐ & Ú  ~  ê  называются пропозициональными связками,

А, В, С, … и т.д. – пропозициональными переменными.

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

ПРИМЕР.

Определить значение истинности составного высказывания

D=А&(А&В ) &В

при А=0, В=1, С=1

              А&В=0, А&В С=1

    А&(А&В С)=0

    &В=1, D=1.