Математическая логика
Полные системы операций и функций
жүктеу/скачать 0.93 Mb.
|
- Бұл бет үшін навигация:
- 6. Выводимость
| Полные системы операций и функций.
Алгебра Жегалкина Система операций называется полной, если любая логическая операция может быть представлена формулой над . Так как всякая формула может быть представлена приведенной формулой, то система 0 = {, , } - полна. Полной будет и любая система , через операции которой можно выразить конъюнкцию, дизъюнкцию и отрицание. Если все операции полной системы * представимы формулами над системой , то полна, в этом случае говорят, что сводится к *. Алгебра над множеством логических функций с двумя операциями и называется алгеброй Жегалкина. В алгебре Жегалкина выполняются следующие соотношения: , , , , а также ассоциативность, коммутативность, идемпотентность конъюнкции и свойства констант. Задание. Доказать полноту системы 5 = {, }. Решение. Сведем систему 5 к полной системе 0. . Доказательство неполноты системы операций необходимо проводить в терминах булевых функций. 6. Выводимость Пусть задано множество формул от высказывательных переменных ( ), ( ), . . . , ( ). (1) Это множество формул назовем системой посылок. Определение. Формула ( ) называется выводимой из системы формул (1) в алгебре высказываний, что обозначается , . . , , тогда и только тогда, когда формула (2) является ТИ-высказыванием, т.е. . Из определения следует, что если конъюнкция (3) тождественно истинна, то из такой системы посылок (1) выводимы только тождественно истинные формулы, которые выводимы из любой системы посылок. Если же конъюнкция (3) тождественно ложна, то из системы посылок (1) выводима любая формула. Если формула выводима из системы формул (1), то из истинности всех формул системы при некоторых значениях высказывательных переменных следует истинность формулы при тех же значениях переменных. Нетрудно доказать следующие свойства выводимости. Если и то . Если и ~ , то . Проверка выводимости формулы из системы посылок (1) непосредственно по определению, т.е. путем доказательства тождественной истинности формулы (2), достаточно громоздко. Рассмотрим более простой способ доказательства выводимости формулы из системы посылок (1), для которых конъюнкция (3) не является ни ТИ-высказыванием, ни ТЛ-высказыванием. жүктеу/скачать 0.93 Mb. Достарыңызбен бөлісу:
|