Тема 1 Функции алгебры логики

1.1 Логические операции

1.2 Булевы функции

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

1.1 Логические операции. Алгебра логики – самый простой раздел математической логики. Язык алгебры логики является одним из простейших языков математики. Основными объектами данного раздела являются высказывания. Понятие «высказывание» является первичным, оно не определяется, а поясняется. Под высказыванием понимают предложение, о котором можно сказать одно из двух: истинно оно или ложно. Например, высказывание «2+3=5» – истинное, высказывание «существует действительное число Х такое, что

Х2 = –1» ложное. Очевидно, не каждое предложение является высказыванием. Например, предложения: «Когда ты был дома?», «Пойдем со мной!» не являются высказываниями. Высказывания будем обозначать малыми латинскими буквами

X, y, z,…, а их значения, т. е. истину и ложь, соответственно 1 и 0. Из двух данных высказываний с помощью связок «не», «и», «или», «если … то», «тогда и только тогда, когда …» можно образовать новые высказывания. Например, из высказываний «число 2 простое», «число 2 четное» с помощью указанных выше связок получаем высказывания «число два простое и четное», «число 2 непростое», «число 2 простое или четное». Высказывание «если π иррационально, то π2 тоже иррационально» получается связыванием двух высказываний связкой «если … то». Эти операции соответствуют упомянутым выше связками, употребляемым в обычной речи.

Рассмотрим примеры логических операций.

1. Логическая операция, соответствующая связке «и», называется

Конъюнкцией и обозначается &. В некоторых книгах эту операцию обозначают символом . Пусть X и y – высказывания. Высказывание X×y назовем конъюнкцией X И Y. Данное высказывание истинно тогда и только тогда, когда истинны оба высказывания X и Y.

Соответствующее определение запишем в виде таблицы истинности

X	Y	Xy
0	0	0
0	1	0
1	0	0
1	1	1

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

Конъюнкция X1x2…xn, которую мы кратко обозначим через , истинна тогда и только тогда, когда истинны все высказывания.

2. Логическая операция, соответствующая связке «или», называется

Дизъюнкцией и обозначается .

Пусть X и Y – высказывания. Высказывание XÚY назовем дизъюнкцией X и Y. Данное высказывание истинно тогда и только тогда, когда хотя бы одно из высказываний X и Y истинно.

Данное определение запишем в таблицы истинности.

X	Y	XY
0	0	0
0	1	1
1	0	1
1	1	1

Определение дизъюнкции двух высказываний естественным образом распространяется на любое конечное число высказываний. Дизъюнкция X1Ú X2 Ú … Ú XN, которую мы кратко обозначим через , истинна тогда и только тогда, когда хотя бы одно из высказываний X1, X2, …, XN истинно.

3. Логическая операция, соответствующая связке «не», называется

Отрицанием.

Отрицание высказывания X записывается так: и определяется следующей таблицей истинности:

X
0	1
1	0

4. Логическая операция, соответствующая связке «если … то», называется Импликацией. Эту операцию будем обозначать символом _. При этом высказывание «если X, то Y» записывается в виде x_Y. Высказывание X называется посылкой импликации, Y – ее заключением. Импликация двух высказываний

X и Y задается следующей таблицей истинности:

X	Y	X_Y
0	0	1
0	1	1
1	0	0
1	1	1

Из определения импликации вытекает, что:

· импликация с ложной посылкой всегда истинна;

· импликация с истинным заключением всегда истинна;

· импликация ложна тогда и только тогда, когда посылка истинна, а заключение ложно.

5. Логическая операция, соответствующая связке «тогда и только тогда, когда …» называется Эквивалентностью и обозначается символом n.

Пусть X и Y – высказывания. Высказывание XNY назовем эквивалентностью X и Y. Данное высказывание истинно тогда и только тогда, когда оба высказывания X и Y или истинны или ложны.

Данное определение запишем в виде таблицы истинности:

X	Y	XNY
0	0	1
0	1	0
1	0	0
1	1	1

1.

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

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

Обычно функции алгебры логики называют булевыми функциями. Название «булевы функции» возникло в связи с использованием функций рассматриваемого типа в алгебре логики, начало которой было положено трудами ирландского ученого 19 века Дж. Буля. Областью определения булевой функции от n переменных служат совокупность всевозможных n-мерных упорядоченных наборов , где .

Следует отметить, что любой такой набор можно рассматривать как представление некоторого целого неотрицательного числа в двоичной системе счисления. Например, набору (0,1,0,1) соответствует число , а набору (1,1,1) – число .

Все наборы размерности n нумеруются целыми числами от 0,2n-1. Отсюда нетрудно заметить, что число таких наборов равно 2n.

Всякая булева функция от n переменных может быть задана с помощью таблицы истинности:

Таблица 1

X1	X2	…	XN-1	XN	F(X1,X2,…,XN-1,XN)
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)
…	…	…	…	…	…
1	1	…	1	1	F (1,1,…,1,1)

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

Очевидно, что булевы функции от n переменных однозначно определяются своими последними столбцами из таблицы 1, т. е. наборами из 2n нулей и единиц. Следовательно, различных булевых функций от n переменных будет столько, сколько имеется различных наборов длины 2n, а их число равно . Итак, мы доказали следующую теорему:

Теорема 1. Имеется точно Булевых функций от Переменных.

В алгебре логики особое значение имеют следующие булевы функции, которые называют элементарными булевыми функциями.

— константа 0;

— константа 1;

— тождественная функция;

— отрицание х;

— конъюнкция X и y;

— дизъюнкция х и у;

— импликация х и у;

— эквивалентность х и у;

— сложение х и у по mod2;

— функция Шеффера;

— стрелка Пирса.

Последние три функции задаются следующими таблицами истинности:

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

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

Переменная XI в функции называется Фиктивной, если = при любых значениях остальных переменных. В этом случае функция , по существу, зависит от (n-1) – переменной, т. е. представляет собой функцию от (n-1) переменной. Говорят, что функция g получается из функции f удалением фиктивной переменной, а функция f получается из g введение фиктивной переменной, причем эти функции являются равными.

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

< Предыдущая		Следующая >

Введение в логику. Функции алгебры логики. Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма

Математика \ Специальные главы математики

Страницы работы

6 страниц (Word-файл)

Посмотреть все страницы

Скачать файл

Фрагмент текста работы

Логических функций двух переменных – 16; они приведены в таблице ниже.

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

Функции  и  — константы 0 и 1, т.е. функции с двумя несущественными переменными. Переменная  в функции f называется несущественной (или фиктивной), если изменение значения  в любом наборе ,…,  не меняет значения функции. Функции , и , формально различны. Однако принято функции, отличающиеся лишь несущественными переменными считать равными.

Функция  называется конъюнкцией, ее обозначение , ее часто называют функцией И.

Функция  называется дизъюнкцией, ее обозначение , ее часто называют функцией ИЛИ.

Функция  — это сложение по модулю 2, ее обозначение .

Функция  называется эквивалентностью, ее обозначение .

Еще три функции имеют свои названия:

 — импликация, обозначение , читается «если , то »,

 — стрелка Пирса, обозначение ,

 — штрих Шеффера, обозначение .

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

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

()(()).

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

В отличие от табличного задания представление данной функции формулой не единственно. Например, если в качестве исходного множества функций зафиксировать множество функций {, , }, т.е. функции И, ИЛИ, НЕ, то функцию штрих Шеффера можно представить формулами

 и , а функция стрелка Пирса – формулами:

             и .

Формулы, представляющие одну и ту же функцию называются эквивалентными или равносильными.

Булева алгебра.

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

Разложение функций по переменным. Совершенная дизъюнктивная нормальная форма.

Введем обозначение , . Пусть α – параметр, равный 0 или 1. Тогда , если x = α, и , если .

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

,   (*)

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

Это равенство называется разложением по переменным .

Теорема доказывается подстановкой в обе части равенства (*) произвольного набора всех n переменных. Так как , только когда x = α, то среди конъюнкций  правой части равенства в 1 обратится только одна – та, в которой . Все остальные конъюнкции равны 0. Поэтому получим:

, т.е. тождество □.

Выполним разложение по всем n переменным. При этом все переменные в правой части равенства (*) получают фиксированные значения и функции в конъюнкциях правой части становятся равными 0 или 1, что дает:

,                            (**)

где дизъюнкция берется по всем наборам , на которых f = 1. Такое разложение называется совершенной дизъюнктивной нормальной формой (СДНФ) функции f.

Соотношение (**) приводит к важной теореме.

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

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

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

Рассмотрим основные свойства булевых операций.

Ассоциативность:

а) ;          б) .

Коммутативность:

а) ;       б) .

Дистрибутивность конъюнкции относительно дизъюнкции:

.

Дистрибутивность дизъюнкции относительно конъюнкции:

.

Идемпотентность:

а) ;        б) .

Двойное отрицание:

.

Свойства констант:

.

Правила де Моргана:

а) ;       б) .

Закон противоречия:

.

Закон «исключенного третьего»:

Знак & в формулах, там где это не вызывает сомнений, не ставился.

Если из формулы  с помощью некоторых эквивалентных преобразований можно получить формулу , то и  можно получить из , используя те же эквивалентные соотношения; иначе говоря, всякое эквивалентное преобразование обратимо. Это позволяет доказать следующую теорему.

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

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

Язык логики предикатов.

Значение логики предикатов, заключается не столько в ее собственных

Похожие материалы

Информация о работе

Скачать файл

Выбери свой ВУЗ

• АлтГТУ 419
• АлтГУ 113
• АмПГУ 296
• АГТУ 267
• БИТТУ 794
• БГТУ «Военмех» 1191
• БГМУ 172
• БГТУ 603
• БГУ 155
• БГУИР 391
• БелГУТ 4908
• БГЭУ 963
• БНТУ 1070
• БТЭУ ПК 689
• БрГУ 179
• ВНТУ 120
• ВГУЭС 426
• ВлГУ 645
• ВМедА 611
• ВолгГТУ 235
• ВНУ им. Даля 166
• ВЗФЭИ 245
• ВятГСХА 101
• ВятГГУ 139
• ВятГУ 559
• ГГДСК 171
• ГомГМК 501
• ГГМУ 1966
• ГГТУ им. Сухого 4467
• ГГУ им. Скорины 1590
• ГМА им. Макарова 299
• ДГПУ 159
• ДальГАУ 279
• ДВГГУ 134
• ДВГМУ 408
• ДВГТУ 936
• ДВГУПС 305
• ДВФУ 949
• ДонГТУ 498
• ДИТМ МНТУ 109
• ИвГМА 488
• ИГХТУ 131
• ИжГТУ 145
• КемГППК 171
• КемГУ 508
• КГМТУ 270
• КировАТ 147
• КГКСЭП 407
• КГТА им. Дегтярева 174
• КнАГТУ 2910
• КрасГАУ 345
• КрасГМУ 629
• КГПУ им. Астафьева 133
• КГТУ (СФУ) 567
• КГТЭИ (СФУ) 112
• КПК №2 177
• КубГТУ 138
• КубГУ 109
• КузГПА 182
• КузГТУ 789
• МГТУ им. Носова 369
• МГЭУ им. Сахарова 232
• МГЭК 249
• МГПУ 165
• МАИ 144
• МАДИ 151
• МГИУ 1179
• МГОУ 121
• МГСУ 331
• МГУ 273
• МГУКИ 101
• МГУПИ 225
• МГУПС (МИИТ) 637
• МГУТУ 122
• МТУСИ 179
• ХАИ 656
• ТПУ 455
• НИУ МЭИ 640
• НМСУ «Горный» 1701
• ХПИ 1534
• НТУУ «КПИ» 213
• НУК им. Макарова 543
• НВ 1001
• НГАВТ 362
• НГАУ 411
• НГАСУ 817
• НГМУ 665
• НГПУ 214
• НГТУ 4610
• НГУ 1993
• НГУЭУ 499
• НИИ 201
• ОмГТУ 302
• ОмГУПС 230
• СПбПК №4 115
• ПГУПС 2489
• ПГПУ им. Короленко 296
• ПНТУ им. Кондратюка 120
• РАНХиГС 190
• РОАТ МИИТ 608
• РТА 245
• РГГМУ 117
• РГПУ им. Герцена 123
• РГППУ 142
• РГСУ 162
• «МАТИ» — РГТУ 121
• РГУНиГ 260
• РЭУ им. Плеханова 123
• РГАТУ им. Соловьёва 219
• РязГМУ 125
• РГРТУ 666
• СамГТУ 131
• СПбГАСУ 315
• ИНЖЭКОН 328
• СПбГИПСР 136
• СПбГЛТУ им. Кирова 227
• СПбГМТУ 143
• СПбГПМУ 146
• СПбГПУ 1599
• СПбГТИ (ТУ) 293
• СПбГТУРП 236
• СПбГУ 578
• ГУАП 524
• СПбГУНиПТ 291
• СПбГУПТД 438
• СПбГУСЭ 226
• СПбГУТ 194
• СПГУТД 151
• СПбГУЭФ 145
• СПбГЭТУ «ЛЭТИ» 379
• ПИМаш 247
• НИУ ИТМО 531
• СГТУ им. Гагарина 114
• СахГУ 278
• СЗТУ 484
• СибАГС 249
• СибГАУ 462
• СибГИУ 1654
• СибГТУ 946
• СГУПС 1473
• СибГУТИ 2083
• СибУПК 377
• СФУ 2424
• СНАУ 567
• СумГУ 768
• ТРТУ 149
• ТОГУ 551
• ТГЭУ 325
• ТГУ (Томск) 276
• ТГПУ 181
• ТулГУ 553
• УкрГАЖТ 234
• УлГТУ 536
• УИПКПРО 123
• УрГПУ 195
• УГТУ-УПИ 758
• УГНТУ 570
• УГТУ 134
• ХГАЭП 138
• ХГАФК 110
• ХНАГХ 407
• ХНУВД 512
• ХНУ им. Каразина 305
• ХНУРЭ 325
• ХНЭУ 495
• ЦПУ 157
• ЧитГУ 220
• ЮУрГУ 309

Полный список ВУЗов 254) мудрец: Б Булева функция с 8 переменными мудрец: B. нелинейность () 112 мудрец: B.алгебраический_иммунитет () 4

АВТОР:

• Русиди Х. Макарим (2016-10-13): добавить функции, относящиеся к линейным конструкциям

• Русиди Х. Макарим (09.07.2016): добавить is_plateaued()

• Yann Laigle-Chapuy (2010-02-26): добавить базовую арифметику

• Yann Laigle-Chapuy (28 августа 2009 г.): первая реализация

класс sage.crypto.boolean_function.BooleanFunction

Базы: SageObject

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

Мы можем построить Булеву функцию из:

• целое число — результатом является нулевая функция с x переменных;

• список — ожидается, что это будет таблица истинности результат. Поэтому его длина должна быть степенью двойки, а его элементы интерпретируются как логические значения; 9л) )

ПРИМЕР:

из числа переменных:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
шалфей: BooleanFunction(5)
Булева функция с 5 переменными
 

из таблицы истинности:

 мудрец: BooleanFunction([1,0,0,1])
Логическая функция с 2 переменными
 

обратите внимание, что элементы могут быть разных типов:

 мудрец: B = BooleanFunction([False, sqrt(2)])
мудрец: Б
Логическая функция с 1 переменной
мудрец: [b вместо b в B]
[False true]
 97 )
мудрец: Б
Булева функция с 8 переменными
 

два случая отказа:

 мудрец: BooleanFunction(sqrt(2))
Traceback (последний последний вызов):
. ..
TypeError: невозможно запустить логическую функцию
мудрец: BooleanFunction([1, 0, 1])
Traceback (последний последний вызов):
...
ValueError: длина таблицы истинности должна быть степенью 2
 

absolut_indicator( *args , **kwds )

Устарело: вместо этого используйте absolute_indicator() . Подробности смотрите в билете № 28001.

абсолютная_автокорреляция ()

Возвращает абсолютную автокорреляцию функции.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
мудрец: отсортировано (B.absolute_autocorrelation().items())
[(0, 33), (8, 58), (16, 28), (24, 6), (32, 2), (128, 1)]
 

абсолютный_индикатор()

Возвращает абсолютный показатель функции.

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

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
мудрец: B.absolute_indicator()
32
 

Имя старого метода содержало опечатку, оно устарело:

 мудрец: B.absolut_indicator()
доктест: предупреждение
...
DeprecationWarning: absolut_indicator устарел. Используйте вместо него absolute_indicator.
Подробнее см. https://trac.sagemath.org/28001.
32
 

absolute_walsh_spectrum()

Возвращает абсолютный спектр Уолша для функции.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
шалфей: отсортировано (B.absolute_walsh_spectrum().items())
[(0, 64), (16, 64)]
мудрец: B = BooleanFunction("0113077C165E76A8")
мудрец: B.absolute_walsh_spectrum()
{8: 64}
 

алгебраическая_степень()

Вернуть алгебраическую степень этой булевой функции.

Алгебраическая степень булевой функции определяется как степень его алгебраической нормальной формы. Обратите внимание, что степень константы нулевая функция определяется как равная -1.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B. = BooleanPolynomialRing()
мудрец: f = BooleanFunction(x1*x2 + x1*x2*x3 + x1)
мудрец: f.алгебраическая_степень()
3
мудрец: g = BooleanFunction([0, 0])
мудрец: g.алгебраическая_степень()
-1
 

алгебраический_иммунитет ( аннигилятор = Ложь )

Вернуть алгебраический иммунитет булевой функции.

Это наименьшее целое число \(i\), для которого не существует тривиальный аннулятор для \(self\) или \(~self\).

ВВОД:

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: R. = BooleanPolynomialRing(6)
мудрец: B = BooleanFunction(x0*x1 + x1*x2 + x2*x3 + x3*x4 + x4*x5)
мудрец: B. 31)
мудрец: B.алгебраический_иммунитет ()
4
 

алгебраическая_нормальная_форма()

Вернуть sage.rings.polynomial.pbori.BooleanPolynomial соответствующей алгебраической нормальной форме.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = BooleanFunction([0,1,1,0,1,0,1,1])
мудрец: P = B.алгебраическая_нормальная_форма ()
мудрец: П
х0*х1*х2 + х0 + х1*х2 + х1 + х2
мудрец: [P(*ZZ(i).digits(base=2,padto=3)) для i в диапазоне(8)]
[0, 1, 1, 0, 1, 0, 1, 1]
 

аннигилятор( d , тусклый=ложь )

Вернуть (если существует) аннулятор булевой функции степень не выше \(d\), то есть булев многочлен \(g\) такой, что

\[f(x)g(x) = 0 \для всех x.\]

ВВОД:

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: f = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
мудрец: f. annihilator(1) — None
Истинный
мудрец: g = BooleanFunction( f.annihilator(3))
мудрец: установить ([fi*g(i) для i,fi в enumerate(f)])
{0}
 9{f(i)\oplus f(i\oplus j)}.\] 

 
 ПРИМЕРЫ: 
 
 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = BooleanFunction("03")
мудрец: B.autocorrelation()
(8, 8, 0, 0, 0, 0, 0, 0)
 

корреляция_иммунитета ()

Возвращает максимальное значение \(m\), такое, что функция корреляционная устойчивость порядка \(m\).

Говорят, что булева функция не зависит от порядка \(m\) , если выход функции статистически не зависит от комбинации любых m его входов.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
мудрец: B.correlation_immunity()
2
 

производная( и )

Возврат производной в направлении u

ВВОД:

Производная \(f\) по направлению \(u\) определяется как \(х \сопоставляется с f(x) + f(x + u)\).

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: f = BooleanFunction([0,1,0,1,0,1,0,1])
мудрец: f.derivative(1).алгебраическая_нормальная_форма()
1
мудрец: и = [1,0,0]
мудрец: f.derivative(u).алгебраическая_нормальная_форма()
1
мудрец: v = вектор (GF (2), u)
мудрец: f.derivative(u).алгебраическая_нормальная_форма()
1
мудрец: f.derivative(8).алгебраическая_нормальная_форма()
Traceback (последний последний вызов):
...
IndexError: индекс выходит за пределы
 9п\) такое, что
\(f(x \oplus a) \oplus f(x)\) — постоянная функция. 

 
 См. также 
 
  is_linear_structure()  ,
  linear_structures()  . 
 
 ПРИМЕРЫ: 
 
 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0])
мудрец: f.has_linear_structure()
Истинный
мудрец: f.autocorrelation()
(16, -16, 0, 0, 0, 0, 0, 0, -16, 16, 0, 0, 0, 0, 0, 0)
мудрец: g = BooleanFunction([0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1])
мудрец: g. has_linear_structure()
ЛОЖЬ
мудрец: g.autocorrelation()
(16, 4, 4, 4, 4, -4, -4, -4, -4, 4, -4, -4, -4, 4, -4, -4)
 

is_balanced()

Возвращает значение True, если функция принимает значение True в половине случаев.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = логическая функция (1)
мудрец: B.is_balanced()
ЛОЖЬ
мудрец: B[0] = Истина
мудрец: B.is_balanced()
Истинный
 

is_bent()

Вернуть True, если функция искривлена.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = BooleanFunction("0113077C165E76A8")
мудрец: B.is_bent()
Истинный
 

is_linear_structure ( значение )

Возврат True , если val является линейной структурой этого логического значения функция.

ВВОД:

См. также

has_linear_structure() , linear_structures() .

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0])
мудрец: f.is_linear_structure(1)
Истинный
мудрец: л = [1, 0, 0, 1]
мудрец: f.is_linear_structure(l)
Истинный
мудрец: v = вектор (GF (2), l)
мудрец: f.is_linear_structure(v)
Истинный
мудрец: f.is_linear_structure(7)
ЛОЖЬ
sage: f.is_linear_structure(20) #параметр вне допустимого диапазона
Traceback (последний последний вызов):
...
IndexError: индекс вне допустимого диапазона
мудрец: v = вектор (GF (3), [1, 0, 1, 1])
мудрец: f.is_linear_structure(v)
Traceback (последний последний вызов):
...
TypeError: базовое кольцо входного вектора должно быть GF(2)
мудрец: v = вектор (GF (2), [1, 0, 1, 1, 1])
мудрец: f.is_linear_structure(v)
Traceback (последний последний вызов):
...
TypeError: входной вектор должен быть элементом векторного пространства с размерностью 4
sage: f.is_linear_structure('X') #случай отказа
Traceback (последний последний вызов):
. ..
TypeError: невозможно вычислить is_linear_structure() с использованием параметра X
 

is_plateaued()

Возврат Истинно , если эта функция выходит на плато, т. е. ее преобразование Уолша принимает не более трех значений \(0\) и \(\pm \lambda\), где \(\lambda\) - некоторое положительное число.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
шалфей: R. = логическое многочленное кольцо ()
мудрец: f = BooleanFunction(x0*x1 + x2 + x3)
мудрец: f.walsh_hadamard_transform()
(0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 8, 8, 8, -8)
мудрец: f.is_plateaued()
Истинный
 

is_симметричный ()

Возвращает True, если функция симметрична, т.е. инвариантна относительно перестановка его входных битов. Другой способ увидеть это состоит в том, что выход зависит только от веса Хэмминга входа.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = логическая функция (5)
мудрец: B[3] = 1
мудрец: B. is_симметричный()
ЛОЖЬ
мудрец: V_B = [0, 1, 1, 0, 1, 0]
мудрец: для i в srange(32): B[i] = V_B[i.popcount()]
мудрец: B.is_симметричный()
Истинный
 9н\). 

 
 См. также 
 
  is_linear_structure()  ,
  has_linear_structure()  . 
 
 ПРИМЕРЫ: 
 
 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: f = BooleanFunction([0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0])
мудрец: LS = f.linear_structures()
мудрец: LS.dimension()
2
мудрец: LS.basis_matrix()
[1 0 0 0]
[0 0 0 1]
мудрец: LS.list()
[(0, 0, 0, 0), (1, 0, 0, 0), (0, 0, 0, 1), (1, 0, 0, 1)]
 

нелинейность()

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

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = логическая функция (5)
мудрец: B[1] = B[3] = 1
мудрец: B.  нелинейность ()
2
мудрец: B = BooleanFunction("0113077C165E76A8")
мудрец: B. нелинейность ()
28
 

переменные()

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

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: BooleanFunction(4).nvariables()
4
 

resiliency_order()

Возвращает максимальное значение \(m\), такое, что функция упругость порядка \(m\).

Булева функция называется устойчивой порядка \(m\), если она сбалансирована и корреляционно устойчива порядка \(m\).

Если функция не сбалансирована, возвращаем -1.

ПРИМЕР:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
шалфей: B = BooleanFunction("077CE5A2F8831A5DF8831A5D077CE5A26996699669699696669999665AA5A55A")
мудрец: B.resiliency_order()
3
 

sum_of_square_indicator()

Возвращает сумму квадратов показателя функции.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = BooleanFunction("7969817CC5893BA6AC326E47619F5AD0")
мудрец: B.sum_of_square_indicator()
32768
 

true_table (формат = 'bin' )

Таблица истинности булевой функции.

ВВОД: строка, представляющая желаемый формат, может быть либо

• ‘bin’ (по умолчанию): мы возвращаем кортеж логических значений

• ‘int’ : мы возвращаем кортеж из 0 или 1 значений

• ‘hex’: мы возвращаем строку, представляющую таблицу истинности в шестнадцатеричном формате

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: R. = BooleanPolynomialRing(3)
мудрец: B = BooleanFunction( x*y*z + z + y + 1 )
мудрец: B.true_table()
(Правда, Правда, Ложь, Ложь, Ложь, Ложь, Правда, Ложь)
мудрец: B.truth_table (format = 'int')
(1, 1, 0, 0, 0, 0, 1, 0)
мудрец: B. truth_table(format='hex')
'43'
шалфей: BooleanFunction('00ab').truth_table(format='hex')
'00аб'
мудрец: H = '0abbacadabbacad0'
мудрец: лен(ч)
16
мудрец: T = BooleanFunction(H).truth_table(format='hex')
мудрец: T == H
Истинный
шалфей: Н = Н * 4
мудрец: T = BooleanFunction(H).truth_table(format='hex')
мудрец: T == H
Истинный
шалфей: Н = Н * 4
мудрец: T = BooleanFunction(H).truth_table(format='hex')
мудрец: T == H
Истинный
мудрец: Лен(Т)
256
мудрец: B.truth_table(format='oct')
Traceback (последний последний вызов):
...
ValueError: неизвестный формат вывода
 93 )
мудрец: B.walsh_hadamard_transform()
(0, -4, 0, 4, 0, 4, 0, 4)
 

класс sage.crypto.boolean_function.BooleanFunctionIterator

Базы: объект

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

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = логическая функция (3)
мудрец: тип (B.__iter__())
<класс 'sage. crypto.boolean_function.BooleanFunctionIterator'>
 

sage.crypto.boolean_function.random_boolean_function ( n )

Возвращает случайную логическую функцию с \(n\) переменными.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать random_boolean_function
мудрец: B = random_boolean_function(9)
мудрец: B.nvariables()
9
мудрец: пока нет (210 < B.nonlinearity() < 220):
....: B = random_boolean_function(9)
 

sage.crypto.boolean_function.unpickle_BooleanFunction( логический_список )

Специальная функция для расшифровки логических функций.

ПРИМЕРЫ:

 мудрец: из sage.crypto.boolean_function импортировать BooleanFunction
мудрец: B = логическая функция ([0,1,1,0])
sage: load(dumps(B)) == B # косвенный doctest
Истинный
 

Булева логика ПЛК в функциональных блоках

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

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

Булева логика

Ранее мы говорили, что программисты ПЛК полагаются на математические концепции для оптимизации своих проектов. Программисты ПЛК используют булеву алгебру, также называемую булевой логикой, каждый раз, когда создают программу.

Пусть вас не пугает термин «алгебра», потому что концепции булевой логики не так уж сложны.

Булева логика основывается на фундаментальной концепции, согласно которой все значения либо Истина , либо Ложь . Сделав еще один шаг, True и False могут быть представлены либо битом 1 , либо битом 0 .

Вы, вероятно, заметили, что в большинстве языков программирования ПЛК используется термин BOOL для обозначения цифрового входа или выхода. BOOL — это сокращение от Boolean. Каждый цифровой вход/выход может быть представлен цифрой 1 или 0.

Базовые функциональные блоки

Функциональная блок-схема (FBD), описанная в IEC 61131-3, быстро заменяет релейную логику в качестве предпочтительного языка программирования среди программистов ПЛК.

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

Функциональный блок ИЛИ

Функциональный блок ИЛИ имеет как минимум два входа. Ранее в булевой логике мы говорили, что все значения либо истинны, либо ложны и могут быть представлены либо 1, либо 0 битами.

Функциональный блок ИЛИ имеет таблицу истинности , которая выполняет две функции.

Во-первых, здесь представлены все возможные входные условия.

Во-вторых, показывает, как выход реагирует на входные условия.

Из Таблицы истинности мы видим, что С истинно, когда истинно А ИЛИ В.

OK… Здесь мы подходим к части булевой алгебры. Математическое выражение для функционального блока ИЛИ: A OR B равно C. Знак плюс используется для обозначения функции ИЛИ.

В начальной школе нас учили, что плюс используется для сложения. Итак... может показаться, что функциональный блок ИЛИ выполняет логическое сложение .

Функциональный блок И

Хорошо… Давайте перейдем к функциональному блоку И. Функциональный блок И имеет как минимум два входа.

Из таблицы истинности И мы видим, что С истинно, когда истинно А И В.

 

Математическое выражение для функционального блока AND: A AND B равно C.

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

Мы можем опустить символ умножения, и выражение будет выглядеть так: AB = C

Пример оптимизации FBD

Как мы уже говорили ранее, программисты ПЛК полагаются на булеву логику для оптимизации своих проектов. Давайте рассмотрим простой пример оптимизации булевой логики.

При первом преобразовании системных требований в СХЕМУ ФУНКЦИОНАЛЬНЫХ БЛОКОВ программист закончил с тремя функциональными блоками.

Программист задастся вопросом… Могу ли я оптимизировать эту СХЕМУ ФУНКЦИОНАЛЬНЫХ БЛОКОВ и исключить какие-либо функциональные блоки с помощью булевой алгебры? Ответ: Да. Итак, давайте посмотрим, как.

Выражение булевой логики для этой программы: D = AB + AC

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

Хорошо… теперь давайте перестроим нашу ФУНКЦИОНАЛЬНУЮ СХЕМУ и посмотрим, продвинулись ли мы в направлении оптимизации.

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

Я показал вам, как булеву логику можно использовать для оптимизации программ ПЛК. Нравится вам это или нет, но опытные программисты ПЛК стали математиками.

Я рекомендую ознакомиться со следующими статьями по теме, если вы еще этого не сделали, чтобы лучше понять функциональные блоки ПЛК:

Что такое блок управления или функциональный блок?

В чем разница между релейной логикой и схемами функциональных блоков?

Резюме

Хорошо… давайте повторим:

— Программисты ПЛК обладают разнообразными знаниями и навыками в области электротехники, механики и разработки программного обеспечения.

– Программисты ПЛК обладают навыками экспертного уровня в программном обеспечении ПЛК конкретного поставщика и полагаются на математические концепции для оптимизации своих проектов.

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

— Диаграмма функциональных блоков (FBD) быстро заменяет релейную логику в качестве предпочтительного языка программирования среди программистов ПЛК.

– Двумя основными функциональными блоками на СХЕМЕ ФУНКЦИОНАЛЬНЫХ БЛОКОВ являются ИЛИ и И.

– Булева логика может использоваться программистами ПЛК при оптимизации программ ПЛК.

Если у вас есть какие-либо вопросы о булевой логике или о функциональных блоках ПЛК в целом, задайте их в комментариях ниже, и мы свяжемся с вами менее чем через 24 часа.

У вас есть друг, клиент или коллега, которым может пригодиться эта информация? Пожалуйста, поделитесь этой статьей.

Команда RealPars

Поиск:

Инженер по автоматизации

Опубликовано 22 марта 2021 г.

Тед Мортенсон

Инженер по автоматизации 22 января 2021 г.