Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
|
16. Полностью и не полностью определенные ФАЛ *Опред.: Если значение ФАЛ определено на всех наборах её аргументов, то она называется полностью определённой. *Опред.: Если значение функции на некоторых наборах явл. безразличным и однозначно не определено, то такая функция наз. не полностью (частично) определённой. - полное число наборов; - наборы, на которых ф-ия равна 1 (обязательные). - наборы, на которых ф-ия равна 0 (запрещённые). - множество наборов, на которых значение функции безразлично(условные наборы). 20. Функции: дизъюнкция, конъюнкция, инверсия. Основные законы алгебры логики. Опред: две Булевых, значения которых совпадают при одинаковых значениях переменных, называются равносильными (соединяются знаком «=»). 1)x+0=0; x+1=1; ; 2) 3)Законы алгебры логики. *переместит: x1 x2 x3= x2 x1 x3 x1+ x2+ x3= x2 +x1+ x3 *распределит:x1 x2+ x1x3=x1(x2+ x3) *сочетат: (x1 x2) x3= x1 (x2 x3) (x1+ x2)+ x3= (x1+ x3)+ x2 *отриц:
4)Формула поглощения: x1+x1 x2+ x1 x3= x1(1+ x2+ x3)= x1 x1(x1+ x2) (x1+ x3)= x1 5) Формулы склеивания: x1 x2+ x1= x1(x2+)= x1 (x1+ x2)( x1+)= x1 6) Ф-лы полезные для практики: x1+ x2= x1+ x2 + x1 x2=+ x2 Приведённые формулы используют с целью уменьшения символов. |
17. Булевы функции от одной и двух переменных. Одной переменной: Число наборов значений одной переменной равно двум. Поэто- -функция, тождественно равная 0 (тождественный нуль); Двух переменных: Число различных наборов значений двух переменных составля- 1)f0=0; 2) f15=1 – константы 3) f3=x1; 4) f5= x2 – повторение 5) f10=; 6) f12= – НЕ 7) f1= x1 x2 – И 8)f14= –И-НЕ, штрих Шефера 9) f7= x1+ x2 – ИЛИ 10) f8= –ф-ия Пирса(стрелка) 11) f11= x2 x1=+ x1 – если…то (импликация) 12) f11= x1 x2=+ x2 13) f2= x1 x2= x1 –ф-ия запрета 14) f4= x2 x1= x2 – НЕТ 15) f9= x1 x2= x1 x2+ - тождевственность 16) f6= x1+ x2= x2+ x1 - неравнозначность. Ф-ии 1,7,10(12) – основные ф-ии. С их помощью можно получить любую др. ф-ию алгебры логики. |
28. Методы минимизации ФАЛ. Метод Квайна-Мак-Класки. Метод Квайна—Мак-Класки. Для формирования простых импликант и получения сокращенной ДНФ все конституенты минимизируемой ФАЛ n переменных записывают в виде их двоичных номеров. Последние разбивают по числу m единиц, содержащихся в их коде, на группы. Группы двоичных номеров с одинаковым индексом располагают в столбец, разделяя их горизонтальной чертой в порядке возрастания индекса m. Далее выполняют следующие операции: попарно сравнивают двоичные номера всех членов группы с индексом m с членами группы, имеющей индекс m + 1: если сравниваемые двоичные коды различаются только в одном разряде, в первый столбец остатков записывают код с прочерком на месте этого разряда. Указанные операции повторяют для всех групп последовательно в порядке возрастания К полученному первому столбцу остатков с укороченными двоичными номерами вновь применяют рассмотренные операции и формируют второй столбец остатков. Склеиванию( подлежат только те укороченные двоичные номера, которые содержат прочерки в одних и тех же разрядах и различаются значением только одного разряда. Во втором столбце остатков сокращенные двоичные номера будут содержать уже два прочерка Процесс формирования сокращенных двоичных кодов продолжается до тех пор, пока имеется возможность склеивания. Для составления тупиковых форм из простых импликант и получения минимальной формы используют импликантную таблицу, которую называют также таблицей покрытий. Ее строки соответствуют простым импликантам, а графы — конституентам функции (членам ДСНФ) Столбцы членов ДСНФ. При склеивании которых образована данная импликанта. отмечают метками X. Говорят, что данная импликанта покрывает (поглощает) данную констнтуенту. Если в каком либо из столбцов составленной таблицы имеется только одна метка, простую импликанту. стоящую в соответствующей строке, называют существенной, и метку обводят кружком. Существенная импликанта не может быть исключена, так как без нее не будет получено покрытие всего множества конституент функции. |
19. Основные классы функций алгебры логики. 1) Функция, сохр. константу «0». Опред.: ф-ия n-переменных наз. сохраняющей const «0», если на наборе нулевых значений её аргумента она принимает значение «0». 2) Функция, сохр. константу «1». Опред: ф-ия n-переменных наз. сохраняющей const «1», если на наборе единичн.знач. её аргумента она принимает значение «1». 3) Двойственная ф-ия. Ф-ия f*(x1,x2…xn) наз.двойственной по отношению к f*() если имеет место равенство: f*() = f*(x1,x2…xn). 4) Самодвойственная. Ф-ия n-перем. наз. сомодвойственной, если она совпадает с двойственной. 5) Монотонная. Опред: логич. ф-ия наз. монотонной, если для любой пары наборов её аргументов () и () (др.словами ) таких, что для любого i справедливо нерав-во f() f() – для монотонно-возрастающей и f() f() – для монотонно-убывающей. 6) Линейная. Опред: логич.ф-ия 2-ух переменных f(x1,x2…xn) наз. линейной если она представлена в виде поленома f(x1,x2…xn)=(знаки "+" в кружочках) 7) Симметричная. Опред: ф-ия f(x1,x2…xn) наз. симметричной, если она не изм. перед произвольной нумерацией аргументов f(x1,x2…xn)= f(a1,a2…an), где (a1,a2…an) – 18. Понятие о суперпозиции ФАЛ. Суперпозицией называют подстановку в функцию вместо её аргументов других функций. Функции, полученные суперпозицией, в общем случае отличаются от исходных и их свойства отличаются от свойств исходных функций. Однако существуют ФАЛ, обладающие основными свойствами. Для них характерно следующее. При суперпозиции функций алгебры логики, имеющих основные свойства, получаются функции алгебры логики с основными свойствами, и только они. Вполне очевидно, что полная система функций не может состоять только из функций, обладающих основными свойствами. |