Математическая логика и теория алгоритмов. Галуев Г.А. - 10 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 10 из 64
© 2003 Галуев Геннадий Анатольевич
Двойственным к понятию СДНФ является понятие совершенной конъюнктивной
нормальной формы некоторой булевой функции. От СДНФ к СКНФ можно перейти,
записывая дизъюнкцию конъюнкций, соответствующих наборам где функция обраща-
ется в 0, и применяя далее к полученному выражению операцию отрицания (⎤) с по-
следующим преобразованием по законам Де Моргана (2.6).
Например. Используем предыдущий пример. Тогда
СКНФ функции F(X
1
,X
2
) будет
иметь вид:
⎤X
1
&⎤X
2
⎤(⎤X
1
&⎤X
2
)↔(⎤⎤X
1
∨ ⎤⎤X
2
)↔(X
1
∨ X
2
)
Таким образом, если функция имеет меньше единичных наборов, то её эконо-
мичней представить в СДНФ, в противном случае – в СКНФ.
Таким образом, мы установили, что любая истинностная (булева) функция может
быть представлена пропозиционной формой, содержащей лишь операции (&,
∨ ,⎤) (т.е.
в виде СДНФ или СКНФ). В свою очередь, каждая пропозиционная форма определяет
некоторую истинностную функцию.
Следует отметить, что не только набор операций &,
∨
,⎤ является функционально
полным для представления булевых функций.
В целом имеем определение: Система булевых функций {F
1
,...,F
n
} является пол-
ной, если любая булева функция может быть записана в виде формулы через функ-
ции этой системы.
Кроме системы {&,
∨
,⎤} существуют и другие полные системы функций.
Например:
{&, ⎤}; {
∨ , ⎤}; {→, ⎤}; {↓}; {⏐}.
Аксиоматическое построение исчисления высказываний.
Рассмотренный выше подход к исчислению высказываний (путём их представле-
ния в виде пропозиционных форм, проведения эквивалентных преобразований этих
форм с целью их упрощения, построения таблиц истинности и установление факта
тождественной истинности высказывания) базировался на интуитивных, содержа-
тельных понятиях и получил название «теории моделей», когда задавал различные
возможные значения пропозиционных букв (
истина или ложь) во всевозможных ком-
бинациях мы получали «модели», «реализации», «воплощения» того, что могут вы-
ражать те или иные высказывания.
Сейчас мы рассмотрим другой подход к построению логики и исчислению выска-
зываний; а именно, аксиоматический подход или метод формальных теорий. Этот
подход ещё называют теорией доказательств, и он связан с
вопросом о том, нельзя
ли описать логические доказательства и выводы так, как это делается в геометрии.
Введём ряд определений.
Формальная (аксиоматическая) теория Т считается определённой, если выпол-
няются следующие условия:
1. Задано конечное или счетное множество символов теории Т (множество, эле-
менты которого можно поставить во взаимно однозначное соответствие
числам
натурального ряда 1, 2, 3, … называется счётным). Конечные по-
следовательности символов теории Т называются выражениями этой тео-
рии Т;
2. Имеется эффективно распознаваемое подмножество выражений теории Т, на-
зываемое формулами этой теории;
3. Выделено некоторое подмножество формул, называемых аксиомами теории Т;
4. Имеется конечное множество правил вывода P
1
,...,P
n
. Для каждого правила P
i
существует некоторое положительное значение j, такое, что для каждого
подмножества содержащего j формул и некоторую форму А, эффективно
решается вопрос о применимости правила P
i
к этому подмножеству фор-
мул и формуле А. Если правило применимо, то А называется следствием
данных формул по правилу P
i
.

Страницы