- •Элементы математической логики Лекция 2. Истинностные функции логики высказываний
- •Формулы логики высказываний
- •Истинностные значения и истинностные таблицы формул логики высказываний
- •Отношение равносильности формул
- •Истинностные функции
- •Совершенные нормальные формы истинностных функций
- •Полные системы истинностных функций
- •Виды формул алгебры высказываний
- •Контрольные вопросы
Полные системы истинностных функций
Из теоремы следует, что для выражения любой истинностной функции достаточно трех логических операций: отрицания, конъюнкции и дизъюнкции.
Определение. Система истинностных функций называется полной, если с помощью функций этой системы можно выразить любую истинностную функцию.
Система {, . } — полная, что следует из предыдущей теоремы.
Существуют и более “бедные” функциями системы, являющиеся полными. Теорема. Системы истинностных функций
{, }, {, }, {, }– полные.
□ Для доказательства полноты системы {, } достаточно, исходя из полноты системы {, . } выразить дизъюнкцию через отрицание и конъюнкцию. Но это имеет место в силу равносильности
АВ≡ (АВ). (1)
Полнота системы {, } следует из равносильности
АВ≡ (АВ). (2)
Полнота системы {, } следует из равносильности
АВ ≡ АВ. (3)
Равносильности (1), (2), (3) можно доказать, например, составлением истинностных таблиц. ■
Среди указанных в таблице двухместных истинностных функций имеются и такие, которые в единственном числе образуют полную систему истинностных функций.
Например, функции штрих Шеффера (отрицание конъюнкции или дизъюнкция отрицаний ) и стрелка Пирса (отрицание дизъюнкции или конъюнкция отрицаний ):
А |
В |
А| В |
|
А |
В |
АВ |
И |
И |
Л |
|
И |
И |
Л |
И |
Л |
И |
|
И |
Л |
Л |
Л |
И |
И |
|
Л |
И |
Л |
Л |
Л |
И |
|
Л |
Л |
И |
Теорема. Системы истинностных функций {|} и {}– полные.
□ Полноту системы {|} доказывают равносильности:
А А|А,
АВ= (А|А) | (В|В)
АВ= (А|В) | (А|В)
Покажем, что и выражаются через |.
А |
А|A | |
и |
л |
л |
л |
и |
и |
А |
В |
А|В |
(А|B)|(A|B) |
AB |
и |
и |
л |
и |
и |
и |
л |
и |
л |
л |
л |
и |
и |
л |
л |
л |
л |
и |
л |
л |
Т.к. - полная система функций, а{|} выражается через , то{|} - полная система.
Полноту системы {} доказывают равносильности:
А АА,
АВ= (АА)(ВВ)
АВ= (АВ)(АВ)
Выразим через
A |
|
AA |
и |
л |
л |
л |
и |
и |
Покажем, что
А |
В | ||||
и |
и |
л |
л |
и |
и |
и |
л |
л |
и |
л |
л |
л |
и |
и |
л |
л |
л |
л |
л |
и |
и |
л |
л |
Т.к. {}- полная система функций, то - полная система функций.■
Виды формул алгебры высказываний
Формула А называется
общезначимой (тождественно истинной, тавтологией), если во всех своих интерпретациях она принимает значение И
невыполнимой (тождественно ложной, противоречием), если во всех своих интерпретациях она принимает значение Л
нейтральной, если она не является ни общезначимой, ни невыполнимой
выполнимой, если она общезначимая или нейтральная
необщезначимой, если она невыполнимая или нейтральная.
Три классификации формул алгебры высказываний:
Только И |
Хотя бы одно И, и хотя бы одно Л |
Только Л |
общезначимые |
нейтральные |
невыполнимые |
выполнимые |
невыполнимые | |
общезначимые |
необщезначимые |