42423

Полные системы булевых функций. Многочлен Жегалкина. Теорема Поста

Лабораторная работа

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

Цель работы: овладение навыками представления булевых функций в виде полинома Жегалкина. Теоретическая часть Таблицы истинности булевых функций сростом числа аргументов становятся громоздкими и неудобными. Более удобный аналитический способ задания булевых функций основан на рассмотрении двузначной алгебры Поста с операцией суперпозиции над множеством булевых функций.

Русский

2013-10-29

60 KB

59 чел.

Практическое занятие №10

Тема: Полные системы булевых функций.

Многочлен Жегалкина. Теорема Поста.

Цель работы: овладение  навыками   представления булевых функций в виде полинома Жегалкина. Изучения свойств функционально полных систем.

Теоретическая часть

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

Принцип суперпозиции

Определение 1 :Функцию f, соответствующую формуле F, называют суперпозицией функции из множества функций, а процесс получения функции из множества функций будем называть операцией суперпозиции.

Пример.

F1=(((x1x2)+x1)+x2) строится за три шага:

  1.  (x1x2)
  2.  ((x1x2)+x1)
  3.  (((x1x2)+x1)+x2)=F1

x1

x2

x1x2

(x1x2)+x1

((x1x2)+x1)+x2

0

0

0

0

0

0

1

0

0

1

1

0

0

1

1

1

1

1

1

1

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

Определение 2: Система булевых функций{f1,…,fm}называется полной, если любая булева функция может быть выражена через функции f1,…,fm с помощью суперпозиций (т.е. составления сложных функций).

Утверждение 1: Пусть даны две системы функций:

А={f1,f2,…,fm} (1)

 B={g1,g2,…,gm} (2)

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

Многочлен Жегалкина.

Одной из интересных систем является набор Жегалкина ( , 1)

В алгебре логики теорема Жегалкина играет важную роль.

Определение 3: Любая переключательная функция f  может быть представлена при помощи полинома по «mod 2» (полинома Жегалкина).

Полином Жегалкина – канонический многочлен.

 f(x1,x2,…,xn)=k0+k1x1+k2x2+k3x1x2+…+knx1x2xn,

где k1…ks – коэффициенты, которые принимают значения 0 или 1.

Пример.

Выразить х12 в виде композиции полиномов Жегалкина.

Ищем выражение для х12 в виде полинома с неопределенными коэффициентами:

х12=ах1х2+bх1+cх2+d,

при х12=0 имеем 0=d;

при х1=0, х2=1 имеем 1=с;

при х1=1, х2=0 имеем 1=b;

при х12=1 имеем 1=a+b+c.

Тогда окончательно:

х121х212.

Каждая булева функция может быть представлена многочленом Жегалкина. 

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

Утверждение 1 дает лишь достаточное условие полноты системы булевых функций.

Перейдем теперь к установлению критерия полноты системы булевых функций.

Определение 4: Множество (класс) К булевых функций называется функционально замкнутым, если вместе с функциями из этого класса он содержит и все их суперпозиции.

Определение 5: Булева функция называется линейной, если она может быть представлена полиномом первой степени, т.е. записана в виде

f(x1,…,xn)=a0a1x1a2x2anxn, где a0,a1,…an - коэффициенты 0 или 1.

Например, отрицание и сумма (по mod 2) линейны, а конъюнкция и дизъюнкция нелинейны.

Количество линейных функций .

Определение 6: Функция, удовлетворяющая условию f(0,…,0)=0, называется функцией сохраняющей 0 или константой нуля. Например, сохраняют константу 0 дизъюнкция и конъюнкция, а отрицание и импликация не сохраняют ее.

Определение 7: Функция, удовлетворяющая условию f(1,…,1)=1, называется функцией сохраняющей 1. Например, сохраняют константу 1 дизъюнкция и конъюнкция, а отрицание и сумма (по mod 2) не сохраняют ее.

Определение 8:

Пусть f(x1,…, xn) - булева функция. Функция f*(x1,…, xn) называется двойственной f(x1,…, xn), если f*(x1,…, xn)=f(x1,…, xn). Например, двойственной x1x2 является функция x1x2 и наоборот.

Определение 9: Функция f(x1,…, xn) называется самодвойственной, если f(x1,…, xn)=f(x1,…, xn), т.е. самодвойственная функция f на противоположных наборах принимает противоположные значения. Примерами самодвойственной функции является отрицание (все остальные функции не самодвойственны).

Определение 10: Булева функция называется монотонной, если при любом возрастании набора значения этой функции не убывают.

Монотонны, например, дизъюнкция, конъюнкция, тогда как отрицание и сумма (по mod 2) немонотонны.

Теорема Поста: Система функционально полна тогда и только тогда, когда содержит:

  1.  хотя бы одну функцию, не сохраняющую константу 0;
  2.  хотя бы одну функцию, не сохраняющую константу 1;
  3.  хотя бы одну нелинейную функцию;
  4.  хотя бы одну немонотонную функцию;
  5.  хотя бы одну несамодвойственную функцию.

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

Полная система называется несократимой, если исключение любой функции системы нарушает ее полноту. В связи с тем, что каждая из функций не обладает несколькими свойствами, функционально полные системы могут быть построены с помощью одной, двух, трех и четырех функций. Наиболее распространенная система – система из трех функций: И, ИЛИ, НЕ. С помощью этих функций могут быть описаны процессы управления любыми производствами.

Примеры выполнения заданий

Пример 1: Доказать полноту систем функций:1) {, &, }, 2) {, }, 3){} 4){}.

Решение:

1) Полнота системы {, &, } следует из теоремы  2 (лабораторная работа 4).

2) Для доказательства полноты системы {, }воспользуемся полнотой системы {, ,} и утверждением 1, где в роли функций f1,f2,f3 выступают соответственно,,, а в роли функций g1,g2 - ,. Тогда f1=g1, f2=x1x2=x1x2, т.е. функция f2 выражена через g1 и g2, а f3=g2.

3) Полнота системы {}доказывается аналогично предыдущему случаю с использованием равносильности X1X2=X1X2).

4) Для доказательства полноты системы {}воспользуемся полнотой системы и утверждением 1, где в роли функций  f1 и f2  выступают соответственно , , а в роли функций g1,g2 - . Тогда f1=g1, f2=x1x2= X1X2.

Пример 2: Исследовать систему функций {+,,1}.

Решение: Это полная система, что следует из утверждения 1, полноты системы

{, }и равносильности .По таблицам истинности нетрудно проверить, что выполняются тождества:

  1.   
  2.   
  3.   
  4.  
  5.  
  6.  
  7.  

Пример 3: Представить многочленом Жегалкина функции:

1) XY, 2)  XYZ:

Решение:

xy=xyx+1y+1+1xy+x+y+1+1=xy+x+y;

xyz=xyz+xy+xz+yz+x+y+z.

Контрольные вопросы

  1.  Сформулируйте принцип суперпозиции.
  2.  Сколько имеется линейных функций от n переменных?
  3.  Какие функции называются самодвойственными?
  4.  Какие функции называются монотонными? Перечислить все монотонные функции от двух переменных.
  5.  Какое множество называется функционально замкнутым?
  6.  Какие из указанных ниже систем функций являются функционально замкнутыми классами:

а) функции от одной переменной;

б) функции от двух переменных;

в) все функции алгебры логики;

г) линейные функции;

д) самодвойственные функции;

е) монотонные функции;

ж) функции, сохраняющие нуль, но не сохраняющие единицу?

  1.  Сколько имеется самодвойственных функций от n переменных?
  2.  Дайте определение полной системы.
  3.  Как определяется многочлен Жегалкина?
  4.  Сформулируйте теорему Поста.

Индивидуальные задания

1. Выразить с помощью суперпозиции:

1) через 1,,;

2) , через ,   ;

3)   через 0, ;

4)   ,, через (штрих Шеффера xy=xy);

5)  ,, через ( стрелка Пирса xy=xy);

6)  через   и ~;

7)    через .

2. Представить многочленом Жегалкина :

  1.  XY;
  2.  X~Y.

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

4. Доказать, что число сомодвойственных функцийц от n переменных равно

5. Определите, будет ли функция самодвойственной:

1) f(x1,x2,x3)=x1+x2&x3

2) f(x1,x2,x4)=(x1&x3)+x2

3) f(x1,x2,x3)=x3&(x1&x2)

6.  Какие функции являются монотонными и почему:

1) f(x1)=x1;

2) f(x1,x2)=x1&x2;

3) f(x1,x2)=x1+x2;

4) f(x1,x2)=x1~x2.

7.  Найти все самодвойственные функции от двух переменных.

PAGE  1


 

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

42374. Измерение толщины металлических пленок с помощью интерферометра МИИ-4 175 KB
  В результате интерференции двух систем волн в фокальной плоскости окуляра наблюдаются характерные интерференционные полосы. в результате интерференции волн получаются светлые полосы а в точках где разность хода равна λ 2 3λ 2 5λ 2 и т. темные полосы. В отъюстированном микроинтерферометре при работе в монохроматическом свете в поле зрения должны быть видны чередующиеся черные и светлые полосы.
42375. Адміністрування безпеки операційної системи WINDOWS 2k 479 KB
  С помощью утилиты NET. Выполнить исследование локальной сети с помощью утилиты NBTSTT программы PWLTOOLS. С помощью утилит User2sid и Sid2user определить перечень логинов пользователей на том же удаленном компьютере что и в пункте 4.] Выполнить тестирование компьютера указанного в пункте 4 с помощью программы DDoSPing.
42376. Програмні засоби для шифрування та приховування інформації 1.79 MB
  С помощью программы PGP выполните обмен зашифрованной информацией. Для этого необходимо: а с помощью утилиты PGPkeys создать ключевую пару подчиняясь следующему порядку: выполнить запуск Strt Пуск Progrms Программы PGP PGPkeys необходимо указать собственное имя Full nme и адрес электронной почты Emil ddress не забывая что именно эти данные будут ассоциированы программой с вашими ключами выбор типа ключа Key Pir Type: ключ RS действительно архаичнее и медленнее своего ретивого молодого собрата DiffieHellmn DSS однако...
42377. Використання M.EXCEL в розвязанні матричних ігор 437.5 KB
  Планується до випуску Кі варіанти конструкції нового товару. Виготовлення їх можливо за допомогою одного з альтернативних технологічних процесів Тj . Експерти оцінили споживчі властивості конструкції Кі , виготовленої за допомогою технологічного процесу Тj за десятибальною шкалою в аij балів. Конструкція, яка має більший бал якості, має також і більшу собівартість. Ресурси обмежені, тому менеджерам необхідно прийняти компромісне рішення. Обґрунтувати прийняте рішення.
42378. Работа с пакетом Microsoft Office (Word, Excel, Access, PowerPoint) 699.5 KB
  Для таких целей следует использовать команду меню Формат Абзац и в диалоговом окне установить необходимые отступы и интервалы. Установка первых строк производится с помощью команды меню Формат – Абзац или масштабной линейки. Изучите пункты меню панели инструментов и элементы окна. Рисунок 1 Рабочее окно программы Word Установите поля: левое – 25 см правое – 15 см верхнее и нижнее 2 см через меню Файл команду Параметры страницы.
42379. Текстовый процессор Word «Приемы и средства автоматизации разработки текстовых документов» 63 KB
  Формула задается как выражение в котором использованы: абсолютные ссылки на ячейки таблицы в виде списка 1; B5; E10 или блока 1:F10; ключевые слова для ссылки на блок ячеек: LEFT – ссылка на ячейки расположенные в строке левее ячейки с формулой; RIGHT – ссылка на ячейки расположенные в строке правее ячейки с формулой; BOVE – ссылка на ячейки расположенные в столбце выше ячейки с формулой; BELOW – ссылка на ячейки расположенные в столбце ниже ячейки с формулой; константычисла текст в двойных кавычках; закладки...
42380. Операционная система Windows XP: настройка операционной системы Windows, оформление Рабочего стола, настройка Проводника 148.5 KB
  Работа с архиватором WinZip: создание самораспаковывающегося и защищенного архива извлечение файлов из ZIPархива. Что такое многотомный архив Как добавить файл в архив Какие вы знаете архиваторы Их особенности для различных видов информации. ПРИЛОЖЕНИЕ В Работа с архиватором WinZip Запустите WinZip 8. Дайте команду File New rchive Файл Создать архив.
42381. Приемы и средства автоматизации разработки текстовых документов в Excel 62 KB
  Изучите основные понятия: Относительная ссылка указывает на ячейку основываясь на ее положении относительно ячейки в которой находится формула например на две строки выше. Относительная ссылка это изменяющийся при копировании и перемещении формулы адрес ячейки содержащий исходное данное. Абсолютная ссылка – это не изменяющийся при копировании и перемещении формулы адрес ячейки содержащих исходное данное. Заполните таблицу: При заполнении таблицы используйте: Выделите А1:Е1 выберите Формат Ячейки Выравнивание Объединение ячеек...
42382. Построение диаграмм с помощью мастера диаграмм 221 KB
  Требования к изученному материалу: уметь строить графики математических функций; строить диаграммы по экономическим задачам; уметь изменять тип параметры построенных диаграмм; уметь добавлять диапазон данных к построенной диаграмме; уметь добавлять легенды. В Excel существуют стандартные и нестандартные диаграммы. В следующем окне рисунок 2 появляется образец диаграммы. Далее подписать заголовки: название диаграммы – График квадратной функции; Ось Х – Х; Ось У – У; убрать линии сетки и подписи.