Законы логики высказываний

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

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

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

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

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

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

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

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

Пример. Для формулы АÙ(BÚBÙC) построить таблицу
истинности.

A	B	C	_ B	_ C	B Ù C	B Ù B Ù C	АÙ(B Ú B Ù C)

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

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

2) разделить колонку значений первой переменной пополам и заполнить верхнюю часть колонки нулями, а нижнюю — единицами;

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

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

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

Пример. Дляполучаем:

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

Дата добавления: 2014-01-06