Алгебра логики

Основные понятия

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

В алгебре логики высказывания обозначаются именами логических переменных, которые могут принимать лишь два значения: "истина" (1) и "ложь" (0).

Рассмотрим два простых высказывания: А - "Два умножить на два равно четырем". В - "Два умножить на два равно пяти". Первое высказывание истинно (А = 1), а второе ложно (В = О).

Составные высказывания на естественном языке образуются с помощью связок "и", "или", "не", которые в алгебре логики заменяются на логические операции. Логические операции задаются таблицами истинности.

Рассморим логические операции в последовательности их выполнения в формулах.

1. Инверсия (логическое отрицание)

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

Обозначение: ¬, НЕ, NOT

Таблица истинности отрицания
A¬A
01
10

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

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

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

Обозначение: /\, *, И, AND

Таблица истинности конъюнкции
ABA/\B
000
010
100
111

По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического умножения. Рассмотрим, например, составное высказывание " 2 х 2 = 4 и 3 х 3 = 10 " , Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = 0), с использованием таблицы истинности логического умножения определяем, что данное составное высказывание ложно.

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

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

Обозначение: \/, +, ИЛИ, ОR

Таблица истинности дизъюнкции
ABA/\B
000
011
101
111

По таблице истинности легко определить истинность составного высказывания, образованного с помощью операции логического сложения. Рассмотрим, например, составное высказывание "2 х 2 = 4 или 3 х 3 = 10". Первое простое высказывание истинно (А = 1), а второе высказывание ложно (В = О), с помощью таблицы истинности логического сложения определяем, что данное составное высказывание истинно.

Практические задания

Пример 1. Вычислить значение логической формулы: ¬X /\ Y \/ X /\ Z , если логические переменные имеют следующие значения: X=0, Y=1, Z=1.

1. ¬X = 1
2. ¬X /\ Y =1 /\ 1 =1
3. x /\ Z = 0 /\ 1 = 0
4. 1 \/ 0 = 1
Ответ: 1

Пример 2. По мишени произведено 3 выстрела. Пусть Аk?{Мишень поражена при k-ом выстреле} Что означают следующие высказывания? (Переведите формулы на русский язык)

1) А1\/А2\/А3 : Мишень поражена при первом, втором или третьем выстреле
2) А1^А2^А3 : Мишень поражена и первым, и вторым, и третьим выстрелом (Попали 3 раза).
3) (А1^¬А2^¬А3)\/(¬А1^А2^¬А3)\/(¬А1^¬А2^А3) : Мишень поражена только 1 раз.
4) (А1^А2)\/(¬А1^А2^А3)\/(А1^¬А2^А3): Мишень поражена только 2 раза.