Логические выражения и таблицы истинности

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

Каждое составное высказывание можно выразить в виде формулы (логического выражения), в которую войдут логические переменные, обозначающие высказывания, и знаки логических операций. Для записи составных высказываний в виде логических выражений на формальном языке (языке алгебры логики) в составном высказывании нужно выделить простые высказывания и логические связи между ними. Запишем в форме логического выражения составное высказывание "(2 х 2 = 5 или 2 х 2 = 4) и (2 х 2 <> 5 или 2 х 2 <> 4">. Проанализируем составное высказывание. Оно содержит два простых высказывания:
А = {2 х 2 = 5} - ложно (0);
В = {2 х 2 = 4} - истинно (1).
Теперь необходимо записать высказывание в форме логического выражения с учетом последовательности выполнения логических операций. Для изменения указанного порядка могут использоваться скобки: (А v В) & (А v В).

Построение таблиц истинности логических выражений.

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

1. Необходимо определить количество строк в таблице истинности, которое равно количеству возможных комбинаций значений логических переменных, входящих в логическое выражение. Если количество логических переменных n, то Количество строк = 2n. В нашем случае логическое выражение (А v В) & (А v В) имеет две переменные и, следовательно, количество строк в таблице истинности должно быть равно 4

2. Необходимо определить количество столбцов в таблице истинности, которое равно количеству логических переменных плюс количество логических операций (при желании можно сократить количество столбцов, объединив несколько логических операций в одном столбце). В нашем случае количество переменных равно двум, а количество логических операций равно пяти, т. е. количество столбцов таблицы истинности равно:Количество столбцов = 2 + 5 = 7.

3. Необходимо построить таблицу истинности с указанным количеством строк и столбцов, обозначить столбцы и внести все возможные наборы значений логических переменных. Наборы входных переменных, во избежание ошибок, рекомендуют вводить следующим образом:
1) разделить столбец значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю - единицами;
2) разделить столбец значений второй переменной на четыре части и заполнить четверти чередующимися группами нулей и единиц, начиная с группы нулей;
3) продолжать деление слолбцов значений последующих переменных на 8, 16 и т. д. частей и заполнение их группами нулей или единиц до тех пор, пока группа нулей (единиц) не будет состоять из одного символа.

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

Построим таблицу истинности для данного выше выражения.

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

Пример 1. Построить таблицу истинности логического выражения

Количество логических переменных равно трем, следовательно, количество строк в таблице истинности должно быть:
Количество строк = 8.
Количество логических операций равно пяти, следовательно, количество столбцов в таблице истинности должно быть:
Количество столбцов = 3 + 5 = 8.
Построим таблицу истинности.

Пример 2. Доказать, что логические выражения ¬А& ¬B и ¬(A+B) равносильны.

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

Для доказательнства построим таблицы истинности логических выражений.

Таблица истинности первого выражения

Таблица истинности второго логического выражения

Таблицы истинности совпадают, следовательно логические выражения равносильны. ¬А& ¬B = ¬(A+B)

Пример 3. Символом F обозначено одно из указанных ниже логических выражений от трех аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

Какое выражение соответствует F? 1) ¬X /\ ¬Y /\ ¬Z 2) X /\ Y /\ Z 3) X \/ Y \/ Z 4) ¬X \/ ¬Y \/ ¬Z

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

Частичная таблица истинности для всех выражений имеет следующий вид:

Таким образом, правильный ответ - 4.