шпорки инф

№35

Логические функции от n-переменных

 Булевой функцией от n переменных (аргументов) называется любая функция f(x₁, x_n): Bⁿ -> B . Каждый из ее аргументов x_i, 1 <= i <= n , может принимать одно из двух значений 0 или 1 и значением функции на любом наборе из B_n также может быть 0 или 1. Обозначим через  множество всех булевых функций от n переменных. Нетрудно подсчитать их число.

Теорема 3.1. .

Доказательство.Действительно, по теореме 1.1 число функций из k -элементного множества A в m -элементное множествоB равно m^k . В нашем случае B={0, 1}, а A = Bⁿ . Тогда m=2 и k= |Bⁿ| = 2ⁿ . Отсюда следует утверждение теоремы.

Имеется несколько различных способов представления и интерпретации булевых функций. В этом разделе мы рассмотрим геометрическое и табличное представления, а также представление с помощью логических формул. В лекции 4 будет показано, как булевы функции можно представлять с помощью формул специального вида - дизъюнктивных и конъюнктивных нормальных форм и многочленов Жегалкина. Кроме того, в лекциях 1 и 2 (курс "Введение в схемы, автоматы и алгоритмы") будет рассмотрено еще два способа представления булевых функций: логические схемы и упорядоченные бинарные диаграммы решений.

№36

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

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

0	0	0		1
0	0	1		0
0	1	0		1
0	1	1		1
1	0	0		0
1	0	1		0
1	1	0		1
1	1	1		0

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

В качестве простейших примеров замкнутых классов булевых функций можно назвать множество , состоящее из одной тождественной функции, или множество , все функции из которого тождественно равны нулю вне зависимости от своих аргументов. Замкнуты также множество функций  и множество всех унарных функций. А вот объединениезамкнутых классов может таковым уже не являться. Например, объединив классы  и , мы с помощью суперпозиции  сможем получить константу 1, которая в исходных классах отсутствовала.

Разумеется, множество  всех возможных булевых функций тоже является замкнутым.

№37

канонические формы логических функций

Дизъюнктивная нормальная форма (ДНФ)

Основная статья: Дизъюнктивная нормальная форма

Простой конъюнкцией или конъюнктом называется конъюнкция некоторого конечного набора переменных или их отрицаний, причём каждая переменная встречается не более одного раза. Дизъюнктивной нормальной формой или ДНФ называется дизъюнкция простых конъюнкций. Элементарная конъюнкция

• правильная, если каждая переменная входит в неё не более одного раза (включая отрицание);

• полная, если каждая переменная (или её отрицание) входит в неё ровно 1 раз;

• монотонная, если она не содержит отрицаний переменных.

Например   — является ДНФ.

Совершенной дизъюнктивной нормальной формой или СДНФ относительно некоторого заданного конечного набора переменных называется такая ДНФ, у которой в каждую конъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Например: .

Легко убедиться, что каждой булевой функции соответствует некоторая ДНФ, а функции, отличной от тождественного нуля — даже СДНФ. Для этого достаточно в таблице истинности этой функции найти все булевы векторы, на которых её значение равно 1, и для каждого такого вектора  построить конъюнкцию , где  . Дизъюнкция этих конъюнкций является СДНФ исходной функции, поскольку на всех булевых векторах её значения совпадают со значениями исходной функции. Например, для импликации  результатом является , что можно упростить до .

[править]Конъюнктивная нормальная форма (КНФ)

Основная статья: Конъюнктивная нормальная форма

Конъюнктивная нормальная форма1 (КНФ) определяется двойственно к ДНФ. Простой дизъюнкцией или дизъюнктом называется дизъюнкция одной или нескольких переменных или их отрицаний, причём каждая переменная входит в неё не более одного раза. КНФ — это конъюнкция простых дизъюнкций.

Совершенной конъюнктивной нормальной формой (СКНФ), относительно некоторого заданного конечного набора переменных, называется такая КНФ, у которой в каждую дизъюнкцию входят все переменные данного набора, причём в одном и том же порядке. Поскольку (С)КНФ и (С)ДНФ взаимодвойственны, свойства (С)КНФ повторяют все свойства (С)ДНФ, грубо говоря, «с точностью до наоборот».

КНФ может быть преобразована к эквивалентной ей ДНФ путём раскрытия скобок по правилу:

которое выражает дистрибутивность конъюнкции относительно дизъюнкции. После этого необходимо в каждой конъюнкции удалить повторяющиеся переменные или их отрицания, а также выбросить из дизъюнкции все конъюнкции, в которых встречается переменная вместе со своим отрицанием. При этом результатом не обязательно будет СДНФ, даже если исходная КНФ была СКНФ. Точно также можно всегда перейти от ДНФ к КНФ. Для этого следует использовать правило

выражающее дистрибутивность дизъюнкции относительно конъюнкции. Результат нужно преобразовать описанным выше способом, заменив слово «конъюнкция» на «дизъюнкция» и наоборот.

№38

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

Логической  функцией называется зависимость поведения выходных логических величин от изменения входных логических величин.

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

Имеются различные способы представления логических взаимодействий.

 

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

Таблица истинности содержит 2ⁿ строк, n +m  столбцов (количество входов n+количество выходовm).

Например: пусть требуется задать функцию двух переменных, т.е. дискретное устройство на два входа и на один выход, следовательно, число столбцов = 2+1, а число строк = 4.

x	y	A
0	0	0
1	0	0
0	1	0
1	1	1

       

 

Таблица. 3.2Пример таблицы истинности

 

 

 

Таблицы истинности возможно составить по условиям задания. Задание на управление для выше приведенного примера может выглядеть следующим образом: лампа А горит только тогда, когда одновременно нажаты обе кнопки x и y.

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

 

Словесно-аналитический способ задания функции алгебры логики.

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

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

Ударение делается на союзы предложения, которые, в большинстве случаев, указывают на логическое действие.

Рис. 3.3 Пример аналитического задания логической функции

 

 

 

 

В данном примере описана работа распределителя, с помощью которого производиться управление цилиндром.Электромагнит Y1 включиться (соответственно цилиндр начнет  свое движение), если будет нажата кнопка S1 и датчикB1 активен. Союз и указывает на логическое взаимодействие сигналов управления от кнопки и датчика.

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

 

 Графические способы.

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

При взаимодействии нескольких приводов наиболее наглядным средством установления логических взаимосвязей является шаговая диаграмма.

№39

№38

№35

Логические функции от n-переменных.

Булевы функции находят применение в конструировании и упрощении логических схем. Такие схемы встречаются в электронных устройствах, используе­мых в компьютерах, калькуляторах, телефонных системах и ряде других устройств.Обозначим множество {0;1} через  , т. е. .Функция f из множества  называется булевой функцией n переменных.  Напомним, что

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

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

 .Например, булевых функции 1 переменной,

булевых функции 2 переменных,

 булевых функции 3 переменных .

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

 

            

№34

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

(Булева функция). Булевой функцией от n аргументов называется функция f из n-ой степени множества { 0, 1 } в множество { 0, 1 }.Иначе говоря, булева функция – это функция, и аргументы и значение которой принадлежит множеству { 0, 1 }. Множество { 0, 1 } мы будем в дальнейшем обозначать через B.

Булеву функцию от n аргументов можно рассматривать как n-местную алгебраическую операцию на множестве B. При этом алгебра <B;>, где  – множество всевозможных булевых функций, называется алгеброй логики.

Конечность области определения функции имеет важное преимущество – такие функции можно задавать перечислением значений при различных значениях аргументов. Для того, чтобы задать значение функции от n переменных, надо определить значения для каждого из 2ⁿнаборов. Эти значения записывают в таблицу в порядке соответствующих двоичных чисел. В результате получается таблица следующего вида:

x1	x2	...	xn-1	xn	f
0	0	...	0	0	f(0,0,...,0,0)
0	0	...	0	1	f(0,0,...,0,1)
0	0	...	1	0	f(0,0,...,1,0)
0	0	...	1	1	f(0,0,...,1,1)
...	...	...	...	...	...
1	1	...	0	0	f(1,1,...,0,0)
1	1	...	0	1	f(1,1,...,0,1)
1	1	...	1	0	f(1,1,...,1,0)
1	1	...	1	1	f(1,1,...,1,1)

Раз у нас есть стандартный порядок записывания наборов, то для того, чтобы задать функцию, нам достаточно выписать значенияf(0,0,...,0,0), f(0,0,...,0,1), f(0,0,...,1,0), f(0,0,...,1,1),..., f(1,1,...,0,0), f(1,1,...,0,1), f(1,1,...,1,0), f(1,1,...,1,1). Этот набор называют вектором значений функции.

Таким образом, различных функций n переменных столько, сколько различных двоичных наборов длины 2^n*. А их 2 в степени 2ⁿ.

Множество B содержит два элемента – их можно рассматривать как булевы функции от нуля (пустого множества) переменных – константу 0 и константу 1.

Функций от одной переменной четыре: это константа 0, константа 1, тождественная функция, т.е. функция, значение которой совпадает с аргументом и так называемая функция ``отрицание''. Отрицание будем обозначать символом ¬ как унарную операцию. Приведём таблицы этих четырёх функций:

x	0	x	¬ x	1
0	0	0	1	1
1	0	1	0	1

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