Тема 4.Формула алгебры логики. Таблица истинности.

▪ Определение формулы, подформулы, главной подформулы.

▪ Правила опускания скобок.

▪ Таблица истинности.

▪ Равносильные формулы алгебры логики.

▪ Понятия тождественно истинной(тавтологии) и тождественно ложной формул.

▪Понятия совместности, несовместности, противоположности и логического следования двух формул алгебры логики.

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

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

Если А – формула, а В – какая-либо её связная часть, которая сама тоже является формулой, то В наз. подформулой формулы А.

Главной подформулой формулы А наз. такая её подформула, которая не является частью никакой другой подформулы формулы А.

Формулы алгебры логики будем обозначать большими буквами латинского алфавита А, В,

С, ...

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

В связи с этим формулы (1) могут быть записаны так:

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

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

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

Например:

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

Равносильные формулы алгебра логики

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

Равносильность формул будем обозначать знаком =, а запись А = В означает, что формулы А и В равносильны.

Например, равносильны формулы:

Формула А называется тождественно истинной (или тавтологией) , если она принимает значение 1 при всех значениях входящих в нее переменных.

Например, тожественно истинны формулы

Формула А называется тождественно ложной, если она принимает значение 0 при всех значениях входящих в нее переменных.

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

Ясно, что отношение равносильности рефлексивно, симметрично и транзитивно.

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

Тема.5. Основные равносильности алгебры логики

▪ Три группы равносильностей алгебры логики:

- основные равносильности;

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

- равносильности, выражающие основные законы алгебры логики.

▪ Закон двойственности.

▪ Равносильные преобразования формул алгебры логики.

Важнейшие равносильности алгебры логики можно разбить на три группы.