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.


 

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

14798. Ата мен ана – бала тәрбиесiнiң қамқоршысы, өнегесi 43 KB
  Ата мен ана бала тәрбиесiнiң қамқоршысы өнегесi. Қазақстан Республикасы Ата Заңының 27бап 2тармағында Балаларына қамқорлық жасау және оларды тәрбиелеу ата ананың табиғи құқығы әрi парызы делiнсе Қазақстан 2030 бағдарламасында Әкелер мен аналардың аталар ме...
14799. Білім мазмұны 63.5 KB
  Білім мазмұны Жоспары 1. Білім мазмұны түсінігі жəне оның мəні 2. Білім мазмұнын қалыптастыруға байланысты негізгі теориялар 3. Мемлекеттік білім стандарты 4. Оқу жоспарлары бағдарламалары жəне оқу құралдары 1. Білім мазмұны түсінігі жəне оның мəні Табысты...
14800. БІЛІМ НЕГІЗІ – БАСТАУЫШ МЕКТЕП 234 KB
  БІЛІМ НЕГІЗІ БАСТАУЫШ МЕКТЕП Егеменді еліміздің өсіп келе жатқан ұрпағын ойлы да іскер жігерлі де батыл өзінеөзі сенімді интеллектуалдық деңгейі биік дүниетанымы дұрыс қалыптасқан азамат етіп тәрбиелеуде мектептің алатын орны айрықша. Мектеп қазірг...
14801. Білім басқарудың мемлекеттік – қоғамдық жүйелері 52.5 KB
  Білім басқарудың мемлекеттік қоғамдық жүйелері Жоспары: 1. Педагогикалық жүйелерді басқарудың ерекшеліктері 2. Педагогикалық жүйелерді басқарудың негізгі принциптері 1. Педагогикалық жүйелерді басқарудың ерекшеліктері Қазіргі заман жағдайында жалпы білім...
14802. Білім мəні мен маңызы 81.5 KB
  Білім мəні мен маңызы Жоспары 1. Білім жалпыадамзаттық құбылыс 2. Білім əлеуметтік қажеттілік 3. Білімнің жүйелілігі 4. Білімпедагогикалық процесс 5. Қазіргі заман білім жүйесін реформалаудың негізгі бағыттары 4.1. Білім жалпыадамзаттық құбылыс Қаншалы...
14803. ДYНИЕНI ДYБIРЛЕТКЕН ТYРКIЛЕРДIҢ ДЕНЕ ТӘРБИЕСI 48 KB
  ДYНИЕНI ДYБIРЛЕТКЕН ТYРКIЛЕРДIҢ ДЕНЕ ТӘРБИЕСI Қолына олимпиялық алауды ұстаған халық оның жалынын әрi қарай шалқыта түсуге тиiс Пьер де Кубертен қазiргi олимпиялық ойындардың негiзiн салушы Бiздер қазiргi кезде мекендеп ғұмыр кешiп отырған Қазақстан Республикасының аум
14804. Тəрбие құралы – əлеуметтік орта 67.5 KB
  Тəрбие құралы əлеуметтік орта Жоспары 1. Отбасы педагогикалық қатынас субъекті 2. Мектеп ұжымы 3. Балалар жəне жасөспірімдер бірлестіктері 1. Отбасы педагогикалық қатынас субъекті Отбасы мектеп пен мектепке дейінгі тəрбие мекемелері балалар жəне жасө
14805. Көне дүниедегі мектеп және тәрбие 78 KB
  Көне дүниедегі мектеп және тәрбие. Ертедегі Шығыстың өркениеті жағдайындағы тәрбие және оқыту. Ертедегі Грециядағы тәрбие жүйесі. Ертедегі Грецияда педагогикалық теорияның пайда болуы. Ертедегі Римде тәрбие мен педагогикалық ойпікірдің дамуы. ...
14806. Көне Түркі жазба ескерткіштеріндегі және 58.5 KB
  Көне Түркі жазба ескерткіштеріндегі және Қорқыт ата кітабындағы халықтық педагогика Жазба ескерткіштер. Тәрбиенің мәңгілігі қажетгілігі қасиетгілігі жайлы ой түркі жазбасының ертедегі ескерткіштерімен дөледденеді. Бұл түрғыда ерекше қызығушылық түғазатын