Вычислить значение логического выражения (формулы ЛВ) – значит найти значение истинности этого выражения при заданных значениях истинности составляющих переменных

При вычислении значения формулы ЛВ логические операции (если нет скобок) вычисляются в определенном порядке:

1) негация (отрицание); 2) конъюнкция; 3) дизъюнкция; 4) импликация и 5) эквиваленция.

Пример 10: Даны формулы. Определить порядок вычисления формул:

1. . Порядок вычисления следующий:

1) отрицание ; 2) конъюнкция ; 3) дизъюнкция ; 4) импликация и, наконец, эквиваленция .

2. . Порядок вычисления следующий:

1) отрицание ; 2) импликация ; 3) конъюнкция ; 4) дизъюнкция ; и 5) эквиваленция .

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

Для начала научимся определять количество строк в таблице. Если высказывание одно, то оно может принимать только два значения истинности – «истина» и «ложь», поэтому строк в такой таблице 3 (две строки для значений переменной и строка заголовка). Примером такой таблицы служит таблица истинности в определении негации. Если переменных в формуле две, то они могут принимать одновременно такие значения: оба высказывания истинны, первое – истинно, а второе – ложно, первое – ложно, а второе – истинно и, наконец, оба они могут быть ложными. Число строк в такой таблице равно 5 (плюс строка заголовка). Вообще, число наборов значений, которые могут принимать п переменных, находится как 2^п.

Сформулируем алгоритм построения таблицы истинности сложного высказывания:

1. Вычислить количество строк и столбцов в таблице истинности.

Пусть в формуле п различных переменных и k операций. Переменные считаем каждую только один раз, а символы операций – все, сколько есть. Тогда число строк в таблице равно 2^п + 1 (число наборов значений переменных плюс строка заголовка), а число столбцов в таблице равно n + k.

2. Начертить таблицу.

3. Заполнить строку заголовка.

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

4. Заполнить оставшиеся строки таблицы, начиная с первого столбца.

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

Пример 11: Составить таблицы истинности для формул: 1) ; 2) .

1. . Эта формула содержит 2 различные переменные (К и С) и 4 символа логических операций, т.е. n = 2 и k = 4. Тогда строк в таблице 2² + 1 = 4 + 1 = 5, а столбцов – 2 + 4 = 6. Рисуем таблицу:

Определим порядок выполнения операций: 1) отрицание ; 2) дизъюнкция ; 3) конъюнкция и 4) импликация .

Заполняем строку заголовка, начиная с элементарных формул:

К	С

По-другому строка заголовка может выглядеть так:

К	С

Заполняем первый столбик значениями истинности переменной К, для этого число пустых строк делим пополам (4: 2 = 2) и в половине пишем значение «истина», а в оставшейся половине – «ложь»:

К	С

Заполняем второй столбик значениями истинности переменной С. Для этого число пустых строк делим на 4 (4: 4 = 1) и попеременно записываем в строки по одному значению «истина» и «ложь» таким образом, чтобы каждому значению истинности переменной К соответствовали оба значения истинности переменной С:

К	С

Начиная с третьего столбика, заполняем строки результатами выполнения операций. В третьем столбике записываем результат выполнения операции отрицания . При этом смотрим на соответствующие значения переменной С:

К	С

В четвертом столбике записываем результаты выполнения дизъюнкции , обращая внимание на значения истинности переменных К и С в соответствующей строке:

К	С

В пятом столбике записываем результаты выполнения операции конъюнкции . При этом используем значения истинности соответствующих операций из третьего и четвертого столбиков:

К	С

И, наконец, в шестом столбике записываем результаты выполнения итоговой операции импликации , используя результаты предыдущей операции конъюнкции и значения истинности переменной К:

К	С

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