Формулы алгебры логики

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

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

Формулы алгебры логики будем обозначать большими буквами латинского алфавита: A, B, C, ….

Для упрощения записи формул принят ряд соглашений. Скобки можно опускать, придерживаясь следующего порядка действий:

1) конъюнкция выполняется раньше, чем все остальные операции, при этом сам знак конъюнкции можно опустить;

2) дизъюнкция выполняется раньше, чем импликация и эквиваленция;

3) если над формулой стоит знак отрицания, то скобки тоже опускаются.

Например, формулу можно записать в виде .

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

Построить таблицу истинности достаточно просто.

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

1) подсчитать количество переменных п в формуле;

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

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

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

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

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

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

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

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

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

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

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

Замечание 2. Примеры таблиц истинности будут приведены в конце этой темы.