Примеры полных систем функций к-значной логики с доказательством полноты.




Критерий полноты системы функций алгебры логики.

 

Опр: Функцией алгебры-логики , зависящей от переменных , будем называть функцию

Опр: Пусть имеется непустая система функций алгебры-логики B, будем говорить что система B полная, если каждая функция алгебры логики может быть представлена в виде формулы над B.

 

Примеры полных систем:

  1. – множество всех функций алгебры логики.
  2. B –

 

Теорема: О полноте.

Утверждение: О несамодвойственной функции.

Пусть , тогда путём подстановки вместо независимых переменных функции вида или можно получить из функции константу.

Утверждение: О немонотонной функции.

Пусть функция , тогда путём подстановки вместо констант и функций вида можно получить из отрицание .

Утверждение: О нелинейной функции.

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

 

Критерий полноты:

Пусть , B – непустая система функций из ,

Тогда B – полная ó B – не содержится целиком ни в одном из следующих классов:

Замечание:

класс всех булевых функций , сохраняющих константу 0. Т.е. функций для которых выполнено .

класс всех булевых функций , сохраняющих константу 1. Т.е. функций для которых выполнено .

класс самодвойственных функций, т.е. функций на таких, что .

М – множество всех монотонных функций. L – класс линейных функций.

Док-во:

(=>) Пусть B – полная система и B содержится в каком-то из перечисленных классов, т.е. , но тогда мы получи следующую цепочку включений: . Получили противоречие.

(<=) Пусть B – не содержится ни в одном из перечисленных классов, тогда

Эти функции необязательно различны. Покажем, что подмножество является полной системой (воспользуемся теоремой о полных системах).

Шаг 1. Получение констант.

Покажем, что константы 0 и 1 могут быть представлены в виде формулы над . Рассмотрим функции возможны 4-е случая:

1) ,

2) ,

3) ,

4) ,

Введём вспомогательные функции: и

В случае 1) получим:

(т.к. ),

,

,

Т.о. отрицание представляется в виде формулы над , но тогда использую функцию по утверждению о несамодвойственной фцнкуции, можно получить в виде формулы над какую-нибудь константу (0 или 1). Вторая константа получается из с помощью уже полученного отрицания, т.е. .

В случае 2) получим:

, т.к. ,

В случае 3) получим:

, ,

В случае 4) получим:

, ,

 

Шаг 2. Получение отрицания.

Если отрицание не было получено на первом шаге (случай 3), то представим его в виде формулы над , используя функцию и это можно сделать благодаря утверждению о немонотонной функции.

 

Шаг 3. Получение конъюнкции.

Конъюнкцию можно получить из функции по утверждению о нелинейной функции. Т.о. мы получили, что представляются в виде формулы над , а т.к. система - полная, то по теореме о полных системах мы получили, что и - полная и => - полная.


Примеры полных систем функций к-значной логики с доказательством полноты.

Опр: Система функций К -значной логики наз. полной, если замыкание совпадает со всеми , т.е:

Теорема: О полных системах.

Пусть для которых выполняются условия:

1) – полная система;

2) Каждая функция

Тогда система – полная.

Теорема: Пример полной системы к-значной логики.

– система функций, состоящая: , тогда эта система полна.

Док-во:

Рассмотрим систему – эта система полная. Выразим каждую функцию этой системы через функции системы .

Шаг 1. Получение константы. Рассмотрим функции:

Очевидно, что эти функции и рассмотрим функцию:

=> . Используя отрицание, получим из константы

k-1 все остальные константы:

 

Шаг 2. Получение функций .

, рассмотрим функцию

Если , то среди элементов есть элемент , но тогда => , но тогда , если , то и => , т.е.

 

Шаг 3. Получение функций .

Рассмотрим функция

Если , то , тогда тогда

Если , то , тогда тогда =>

 

Шаг 4. Получение произвольной функции от одной переменной.

Рассмотрим произвольную функцию

 

Шаг 5. Получение конъюнкции.

На 4-ом этапе мы получили все функции от одной переменной в виде формулы над , в частности отрицание тоже представляется в виде формулы над ,но тогда конъюнкцию можно получить следующим образом: => система полная по теореме о полной системе.



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-27 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: