Лекция 7 Полные системы фал. Теорема Поста


Скачать 101.2 Kb.
НазваниеЛекция 7 Полные системы фал. Теорема Поста
Дата27.10.2012
Размер101.2 Kb.
ТипЛекция
Лекция 7

Полные системы ФАЛ. Теорема Поста.

  1. Полные системы ФАЛ.

Определение 1. Пусть задана конечная система функций алгебры логики от «m» переменных .

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

Например, тривиально полной является система из 16 функций от 2–х переменных. Каждая функция может быть задана соответствующей таблицей истинности.

Полной является набор (система) функций 2–х переменных {&, , }. Из этих функций строится СДНФ и СКНФ для любой функции от «n» переменных.

Интерес представляют такие системы (наборы) функций, которые содержат наименьшее число функций. Например, интересно знать, есть ли набор из функций 2–х переменных, состоящий всего лишь из 2–х функций, либо только из одной функции.

Определение 2. Набор функций называется базовым или минимальным (min), если при вычёркивании из него хотя бы одной функции, он теряет свойство полноты.

Например, если из {&, , } вычеркнуть, то свойство полноты потеряется (нельзя сделать СДНФ и вообще ДНФ). А если вычеркнуть  (или &), что будет? На этот вопрос отвечает теорема Поста.

Заметим! Единственная операция, при помощи которой можно конструировать функции из функций – подстановка. Нужно вспомнить конструирование рекурсивных функций и информационные структуры алгоритмов – ИСА).

Доказательство полноты набора функций {, &,}. Количество различных СДНФ –. Представим любую СДНФ в форме:

.

Рассмотрим вектор , где . Число различных векторов – . Таким образом, число различных формул равно числу функций, и любая функция может быть записана уникальной формулой в зависимости от комбинации «0» и «1» вектора .

  1. О критерии полноты системы функций

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

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

В 1942 г. Пост выделил 5 классов функций принадлежность (или не принадлежность) к ним всех определяла полноту набора функций F. Каждый класс Поста был замкнутым относительно операции подстановки, т.е. система функций, обладающая свойством класса, при помощи подстановок порождала функции, имеющие это свойство, и только их. Таким образом класс являлся «ловушкой» для функций, обладающих характерным свойством. Например, если полная система состоит из единственной функции, то она должна не принадлежать (не иметь свойств) ни к одному из классов Поста. Иначе операция подстановки не могла бы породить все функций. Порождённые функции остались бы в «ловушке» и не «выскочили» бы за пределы множества функций, обладающих уникальным свойством. Таким образом, чтобы набор был полным, в нём должны быть функции, не принадлежащие к классам Поста.



  1. Классы Поста. Теорема Поста.




    1. Функции, сохраняющие const «0» – Р0.

Свойство: , на нулевом наборе имеет значение «нуль».

Пример: .

(& и )  P0; x1x2; функция Шеффера (0, 0)=;| P0.

    1. Функции, сохраняющие const «1» – Р1

.

(& и )  P1; |1, 1 = 0;|  P1.

    1. Самодвойственные функции – S

Введём оператор двойственности , он преобразует ФАЛ в соответствии с определением.



Пример:


x1, x2

&





x1x2







x1, x2



0 0

0 1

1 0

1 1

0

0

0

1

1 1

1 0

0 1

0 0

1

1

1

0

0 0

0 1

1 0

1 1

0

1

1

1
табл. 1. & табл. 2. табл. 3.


ФАЛ называется самодвойственной, если

  S.

Пример ; сравни табл. 1.& с табл. 3. (&)

Пример:  (отрицание); S


х






х



0

1

1

0

=

1

0

0

1




    1. Линейные функции – L

ФАЛ называется линейной, если она представима в виде: , где

Примеры: а) представима в виде



б) не представима; доказывается перебором значений вектора l, &  L

5) Монотонные функции – М

Введём отношение предшествования двух наборов

и

если все элементы в наборах находятся в отношении .

Пример: а) ;

б) и . Наборы не сравнимы.

ФАЛ называется монотонной, если для всех i и i таких, что .

Сравнение наборов и значений функций удобно проверить на гиперкубе.

Примеры.

а) Грань для ФАЛ с двумя переменными, на которой отмечена функция дизъюнкции.

Наборы: (11) >(01); (11) > (00); (11) > (10); (10) > (00); (01) > (00).

Функция: 1 = 1; 1 > 0; 1 = 1; 1 > 0; 1 > 0;



Дизъюнкция «» относится к классу монотонных функций .

б) Конъюнкция &




(11) > (01); (11) > (00); (11) > (10); (10) > (00); (01) > (00).

1 > 0; 1 > 0; 1 > 0; 0 = 0; 0 = 0.

Конъюнкция «&» относится к классу монотонных функций .

в) Сложение по mod2 не является монотонной





x1 x2



0

1

2

3

0 0

0 1

1 0

1 1

0

1

1

0



(11) > (01); (11) > (00); (11) > (10); (10) > (00); (01) > (00).

1 < 0; 0 = 0; 0 < 1; 1> 0; 1 > 0.

Теорема Поста. Набор , будет полным, если он содержит функции не принадлежащие к P0, P1, S, L, M.

Классы P0, P1, S, L, M называются предполными классами Поста. Если задана система функций, то её можно тестировать на полноту, составляя для нее, т.н. таблицу Поста.


Таблица Поста для восьми элементарных функций («+» отмечена принадлежность к классу).





Функция

Р0

Р1

S

L

M

1



+

+





+

2



+

+





+

3







+

+



4



+





+



5





+







6













7

1



+



+

+

8

0

+





+

+


По этой таблице можно выбрать min наборы, которые еще называются базовыми наборами.

1) {}; ; . Этот набор является базовым.

Базовым набором будет единственная функция | – штрих Шеффера. Если задана система функций, то можно проверить ее на полноту.

2) Таблица Поста для .




Р0

Р1

S

L

M







+







+





+

+

Система F = {f1, f2} является полной.

3) Таблица Поста для .




Р0

Р1

S

L

M



+

+

+

+

+



+

+





+

Система F = {f1, f2} является неполной.


Свойства полных наборов


№№

п/п

Полные

наборы

Свойства

1



Булева Алгебра

2



Переход к дизъюнкции

3



Переход к конъюнкции

4





5





6





7





8











Добавить документ в свой блог или на сайт

Похожие:

Разместите кнопку на своём сайте:
cat.convdocs.org


База данных защищена авторским правом ©cat.convdocs.org 2012
обратиться к администрации
cat.convdocs.org
Главная страница