Выполнимые формулы в логике высказываний
Обновлено: 22.12.2024
Определим понятие формулы логики высказываний.
Алфавит логики высказываний состоит из трех групп символов: высказывательные переменные a , b , c , d , …, x , y , z ; логические символы , , →, ↔, −; символы скобок ( , ). Словом в алфавите называется произвольная конечная последовательность символов.
Слово в алфавите логики высказываний называется формулой, если оно удовлетворяет следующему определению:
1) любая высказывательная переменная – формула;
2) если А и В формулы, то слова , , , , – формулы;
3) только те слова являются формулами, для которых это следует из 1) и 2).
Например: или . Скобки указывают порядок выполнения действий.
Скобки в формулах можно опускать, придерживаясь следующего порядка выполнения действий: коньюнкция, дизьюнкция, импликация и эквиваленция.
Пример.
1) равносильно .
2) равносильно .
Логическое значение формулы полностью определяется логическими значениями входящих в нее элементарных высказываний.
Пример.
При x = 1, y = 1, z = 0 формула
Логическое значение формулы изменяется в зависимости от изменений значений элементарных высказываний, входящих в формулу. Все возможные логические значения формулы могут быть описаны полностью с помощью таблицы истинности.
Пример.
Таблица истинности логических значений формулы будет следующая:
Если формула содержит n элементарных высказываний, то она принимает 2 n значений. Таблица истинности будет содержать 2 n строк.
Две формулы алгебры логики A и B называются равносильными, если они принимают одинаковые логические значения на любом наборе значений, входящих в формулы элементарных высказываний.
Обозначается равносильность ≡, т. е. A ≡ B .
Пример.
Следующие формулы являются равносильными:
Формула А называется тождественно истинной (или тавтологией ), если она принимает значение 1 при всех значениях входящих в нее переменных.
Пример.
Следующие формулы являются тавтологиями: ,
Формула А называется тождественно ложной , если она принимает значение 0 при всех значениях входящих в нее переменных.
Пример.
Формула является тождественно ложной.
Отношение равносильности обладает следующими свойствами: оно рефлексивно, симметрично и транзитивно.
Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула – тавтология, и обратно, если формула – тавтология, то формулы А и В равносильны.
Равносильности алгебры логики используются для того, чтобы любую формулу алгебры логики можно заменить равносильной ей формулой.
Важнейшие равносильности алгебры логики можно разбить на три группы.
1. Основные равносильности
– законы идемпотентности.
– закон снятия двойного отрицания.
– законы поглощения.
Докажем формулу 4.
Пусть А ≡ при x = 1, значение А = 1, при х = 0, значение А = 0. Итак во всех случаях значения формулы А совпадают со значениями х, следовательно, А ≡ х.
2. Равносильности, выражающие одни логические операции через другие
Замечание. Формулы 5 и 6 получаются из 3 и 4, если от обеих частей последних взять отрицания и воспользоваться законом снятия двойного отрицания.
Докажем формулы 1–4.
Докажем формулу 1.
1) при одинаковых логических значениях x и y формулы , и – истинны, следовательно, истинной будет и коньюнкция т. е. обе части равносильности имеют одинаковые истинные значения.
2) пусть теперь x и y имеют разные логические значения , тогда будут ложными и одна из или . При этом будет ложной и коньюнкция т. е. обе части равносильности имеют одинаковые ложные значения. Что и требовалось доказать.
Докажем формулу 3.
1) пусть x и y одновременно принимают истинные значения , тогда будет истинной и коньюнкция и ложным ее отрицание . В то же время будут ложными и , следовательно, будет ложной и дизьюнкция .
2) пусть хотя бы одна из переменных x или y принимает значение ложь, тогда тоже ложь, а – истина. В то же время отрицание хотя бы одной из переменных будет истинным, следовательно, будет истиной и дизьюнкция .
Следовательно, во всех случаях обе части равносильности 3 принимают одинаковые логические значения.
Аналогично доказываются равносильности 2 и 4.
Из равносильностей группы 2 следует, что всякую формулу алгебры логики можно заменить равносильной ей формулой, содержащей только две логические операции: коньюнкцию и отрицание или дизьюнкцию и отрицание.
3. Равносильности, выражающие основные законы алгебры логики
– комм утативность коньюнкции и дизьюнкции.
– ассоциативность коньюнкции и дизьюнкции.
– дистрибутивность коньюнкции относительно дизьюнкции и наоборот.
Докажем формулу 6.
При х = 1, формулы , и будут истинны, тогда и – тоже истинна.
При х = 0, ≡ , ≡ ≡ следовательно,
Таким образом, обе части формулы 6 равносильны одной и той же формуле и поэтому принимают одинаковые логические значения. Что и требовалось доказать.
Равносильности 3-ей группы выражают основные законы алгебры логики: коммутативность, ассоциативность и дистрибутивность (относительно логических операций – коньюнкции и дизьюнкции). Эти же законы имеют место в алгебре чисел. Поэтому над формулами алгебры логики можно производить те же преобразования, которые проводятся в алгебре чисел, т. е.
1) раскрытие скобок;
2) заключение в скобках;
3) вынесения за скобки общего множителя.
Кроме этих преобразований над формулами алгебры логики можно производить и преобразования, основанные на использовании равносильностей.
Равносильные преобразования формул используют
1) для доказательства равносильностей,
2) для приведения формул к заданному виду,
3) для упрощения формул.
Под упрощением формулы, не содержащей операций импликации и эквиваленции, понимают равносильное преобразование, приводящее к формуле, которая либо содержит по сравнению с исходной меньшее число операций коньюнкции и дизьюнкции и не содержит отрицаний неэлементарных формул, либо содержит меньшее число вхождений переменных.
Читайте также: