67607

Полнота и замкнутость

Лекция

Математика и математический анализ

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

Русский

2014-09-12

131.5 KB

1 чел.

Лекция № 16  (11.04.00)

Полнота и замкнутость

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

Пример: 1) Само множество ;

2);

3) - не полна.

Теорема || Пусть даны две системы функций из

, (I)

. (II)

Известно, что система I полная и каждая функция системы I выражается через функции системы II. Тогда система II является полной.

Доказательство || Пусть . В силу полноты сист. I функцию h можно выразить в виде формулы . По условию теоремы

Поэтому

ч. и т.д.

Примеры ||

1)  - полная.

2)  - тоже полная, так как .

3)  - тоже полная.

4)  - тоже полная, так как

,

,

. ((2) – I)

5)  - неполная. Докажем это от противного.

Предположим, что .

Но . Противоречие.

6)  - неполная (сохраняет константу 0 – см. след лекц.).

7)  - неполная (сохраняет константу 1 – см. след лекц.).

6)  -  полная

8)  

тогда взяв в качестве сист. I сист. 2) можно заключить, сист. функций 8) – полная. Тем самым, справедлива

Теорема Жегалкина || Каждая функция из  может быть выражена при помощи полинома по модулю 2 – (полинома Жегалкина):

.

Имеем: число разных сочетаний  равно числу подмн-в мн-ва из n элементов. Каждое aik может принимать одно из 2-х значений {0,1}. Тогда число разных пол. Жег. равно , т.е. равно числу различных булевых функций.

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

Примеры

Следовательно,

Пока опустим

2 способ T-преобразов. вектора функции

X1

x2

x3

0

0

0

0

0

0

1

0

0

1

0

0

0

1

1

1

1

0

0

0

1

0

1

1

1

1

0

1

1

1

1

1

3 способ – алгебраических преобразований

Опр. Пусть M – некоторое подмножество функций из P2. Замыканием M называется мн-во всех булевых функций, представимых в виде формул через функции мн-ва M. Обозначается [M].

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

Примеры.

1) M=P2, [M]=P2.

2) M={1,x1x2}, [M] – мн-во L всех линейных ф-й вида

,   (ci{0,1}).

Свойства замыкания:

  1.  [M]=M;
  2.  [[M]]=[M];
  3.  M1M2  [M1][M2];
  4.  [M1M2][M1][M1].

Опр. Класс (мн-во) M называется (функционально) замкнутым, если [M]=M.

Примеры.

  1.  Класс M=P2 функционально замкнут;
  2.  Класс {1,x1x2} не замкнут;
  3.  Класс L замкнут (линейное выражение, составленное из линейных выражений линейно).

Новое определение полноты. M – полная система, если [M]=P2.


 

А также другие работы, которые могут Вас заинтересовать

34093. Договор аренды земельных участков 34 KB
  Договор аренды земельных участков. В основе аренды лежит договор. По договору аренды одна сторона арендодатель обязуется передать другой стороне арендатору земельный участок во временное владение или и пользование за плату. Заключается договор аренды в простой письменной форме.
34094. Договор дарения земельного участка. Наследование земельных участков 32 KB
  Договор дарения земельного участка. Право дарения земельного участка имеют собст ДАРЕНИЕ венники земли граждане и юридические лица ЗЕМЕЛЬНОГО на основании Указа Президента РФ О регули УЧАСТКА ровании земельных отношений и развитии аг рарной реформы в России п. Для обеспечения заключения договоров дарения так же как и договоров мены Комитетом РФ по земельным ресурсам и землеустройству была разработана форма договора дарения земельного участка1. Договор дарения земельного участка должен быть оформлен...
34095. Общая долевая собственность на земельные участки 63.5 KB
  Право общей долевой собственности на земельный участок 1 возникает на основе юридических фактов обусловливающих право собственности граждан и юридических лиц. Право собственности на земельные доли предметом рассмотрения в данной статье не является. Право частной собственности на землю. N 13051 О собственности в СССР но которые не были надлежаще оформлены и зарегистрированы имеют право бесплатно приобрести право собственности на указанные земельные участки в соответствии с правилами установленными ст.
34096. Общая совместная собственность на земельные участки 26.5 KB
  Общая совместная собственность на земельные участки. Общая собственность на земельные участки Существует 2 вида: долевая; общая совместная. Общая долевая собственность возникает при попадании двум и более лицам неделимого участка в случаях предусмотренных в законе или договоре. Совместная собственность возникает в следующих случаях прямо предусмотренных законами: общая собственность супругов если брачным контрактом не предусмотрено иное; возникает собственность крестьянскофермерских хозяйств если соглашением между членами...
34097. Изъятие (выкуп) земельных участков для государственных и муниципальных нужд: основания, порядок 62.5 KB
  Следует иметь в виду что предполагаемое назначение объекта должно соответствовать полномочиям органа принимающего решение об изъятии земельного участка. Например решение об изъятии земельного участка для целей связанных с защитой Государственной границы России может быть принято только органами государственной власти Российской Федерации согласно п. Данное обстоятельство по сути означает что в случае возникновения судебного спора орган принявший решение об изъятии земельного участка должен будет представить суду убедительные...
34098. Право ограниченного пользования чужим земельным участком (сервитут). Обременения земельного участка 33 KB
  Обременения земельного участка. Однако возможно рассмотрение сервитута в качестве обременения земельного участка.С точки зрения собственника земельного участка который соседи используют для прохода к водоему сервитут является ограничением его права. Публичные сервитуты могут устанавливаться для:1 прохода или проезда через земельный участок;2 использования земельного участка для ремонта коммунальных инженерных электрических и других линий и сетей а также транспортной инфраструктуры;3 размещения на участке межевых и геодезических знаков...
34099. Право пользования земельным участком собственником недвижимости. Последствия утраты собственником недвижимости права пользования земельным участком 93 KB
  В случае когда земельные участки находящиеся в государственной или муниципальной собственности предоставляются за плату наряду с решением органа государственной власти или местного самоуправления о предоставлении земельного участка юридический состав образует также договор куплипродажи земельного участка. При наследовании земельного участка по наследству переходят также находящиеся в границах этого земельного участка поверхностный почвенный слой замкнутые водоемы находящиеся на нем лес и растения. Раздел земельного участка...
34100. Права и обязанности субъектов, использующих землю. Защита их прав 52.5 KB
  Взаимосвязанные между собой права и обязанности субъектов земельных правоотношений составляют суть содержания любого правоотношения. Права субъектов земельных правоотношений можно классифицировать на две основные группы: 1. Право на действия субъектов земельных правоотношений можно подразделить на: а виды действий. Право на бездействие субъектов земельных правоотношений можно подразделить на: а полное бездействие.
34101. онятие и особенности ответственности в области использования и охраны земель 25.5 KB
  Ответственность за земельные правонарушения. Ответственность нужно понимать в двояком смысле: юридическая ответственность как правовой институт в объективном смысле – это совокупность юридических норм устанавливающих неблагоприятные последствия за совершение правонарушения в области использования и охраны земель и порядок их возложения на правонарушителя; в субъективном смысле юридическая ответственность – это обязанность лица виновного в совершении правонарушения претерпеть неблагоприятные последствия предусмотренные законом...