2.4.3 Классы Поста
Определение. Говорят, что булева функция сохраняет 0, если .
Обозначим через множество функций от переменных, сохраняющих 0, а через – множество всех булевых функций, сохраняющих 0, т.е. .
Например, , т.к. ; , т.к. .
Определение. Говорят, что булева функция сохраняет 1, если .
Обозначим через множество функций от переменных, сохраняющих 1, а через – множество всех булевых функций, сохраняющих 1, т.е. .
Например, , т.к. ;
, т.к. .
Упражнение 2.30. а) Какие из функций одной переменной принадлежат, а какие не принадлежат множествам , ?
б) Какие из элементарных функций двух переменных принадлежат, а какие не принадлежат множествам , ?
◄ а)
,
,
, .
б) решить самостоятельно.►
Упражнение 2.31. а) Перечислите векторы значений булевых функций 2-х переменных, сохраняющих 0.
б) Перечислите векторы значений булевых функций 2-х переменных, сохраняющих как 0, так и 1.
в) Сколько имеется булевых функций от переменных, сохраняющих 0?
г) Сколько имеется булевых функций от переменных, сохраняющих 1?
д) Сколько булевых функций содержится во множестве ?
е) Сколько булевых функций содержится во множестве ?
◄ а) и б) решите самостоятельно.
в) Пусть
.
Вектор значений такой функции имеет
координат, первая из которых равна 0,
т.е. .
Следовательно,
функций от
переменных, сохраняющих 0, столько же,
сколько булевых векторов длины
,
т.
е.
.
е) Разобьем множество на три подмножества: в первое включим функции, сохраняющие 0, но не сохраняющие 1, во второе – функции, сохраняющие 1, но не сохраняющие 0, в третье – функции, сохраняющие как 0, так и 1. В первом подмножестве содержится функций (первая и последняя координаты вектора значений этих функция равны 0), во втором — (первая и последняя координаты вектора значений этих функция равны 1), в третьем — (первая координата вектора значений этих функция равна 0, последняя — 1). Следовательно, .
Другой подход к решению – использование формулы мощности объединения множеств:
►
Определение. Булева
функция называется самодвойственной,
если
,
т.е. на
любом наборе
значений переменных
выполняется равенство т.е.
.
Иначе говоря, булева функция самодвойственная, если на противоположных наборах она принимает противоположные значения
Обозначим через множество
самодвойственных функций от
переменных, а через
Упражнение 2.32. Дать определение несамодвойственной функции.
◄ Булева функция несамодвойственная, если существует такой набор значений переменных такой, что .►
Например, , т.к. .
Упражнение 2.33. а) Перечислите самодвойственные функции одной переменной.
б) Перечислите элементарные самодвойственные функции двух переменных.
◄ а) ,
,
,
,
таким образом, среди функций одного
аргумента самодвойственными являются
тождественная функция и отрицание.
б) решить самостоятельно.►
Определение. Если для любого ( ), то говорят, что вектор предшествует вектору и пишут .
Обратите внимание, если номер вектора меньше номера вектора (и, значит, в таблице истинности стоит выше ), то это еще не значит, что предшествует . Чтобы выяснить предшествует ли один вектор другому, нужно сравнить их координаты (первую с первой, вторую со второй, и т.д.). Например, вектор предшествует , но не предшествует вектору . Еще примеры: ; . Заметьте, есть пары векторов, в которых ни один из векторов не предшествует другому.
Если имеет место хотя бы одно из соотношений или , то и называют сравнимыми. В противном случае – несравнимыми.
Упражнение
2.32. а) Перечислите булевы вектора, предшествующие .
◄ а) Булев вектор будет предшествовать вектору , если его первая и третья координаты будут либо равны 0, либо 1, а вторая и четвертая равны 0. Этим условиям удовлетворяют вектора , , , а также сам вектор .
б) решить самостоятельно.►
Упражнение 2.35. а) Сколько существует булевых векторов, предшествующих вектору ?
б) Сколько существует булевых векторов, которым предшествует вектор (101000101)?
◄ а) Вектора, предшествующие вектору
Следовательно, общее число
предшествующих векторов равно .б) Решить самостоятельно.►
Определение. Говорят, что булева функция
Обозначим через множество монотонных функций от переменных, а через – множество всех монотонных функций; т.е. .
Упражнение 2.36. Дать определение немонотонной функции.
◄ Булева функция немонотонная, если найдутся такие наборы и значений переменных, что , а . ►
В случае функции
одной переменной функция монотонна
при выполнении неравенства
.
В частном случае двух переменных функция
монотонна, если выполняются неравенства:
,
,
,
,
.
Упражнение 2.37. Выяснить, монотонна или нет функция:
а) ; б) .
0 | 0 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 1 |
0 | 1 | 0 | 0 | 0 |
0 | 1 | 1 | 1 | 1 |
1 | 0 | 0 | 0 | 0 |
1 | 0 | 1 | 0 | 1 |
1 | 1 | 0 | 1 | 1 |
1 | 1 | 1 | 0 | 1 |
◄ а) Будем
последовательно перебирать пары булевых
векторов, отбирать из них сравнимые и
сопоставлять значения функции
на векторах этих пар.
Перебор можно вести, придерживаясь такой схемы: сначала перебираем пары с вектором ,
затем пары с вектором (вектор уже не рассматриваем), затем пары с вектором (вектора и уже не рассматриваем) и т.д.
Вектор предшествует всем прочим булевым векторам длины 3, при этом значение функции на этом векторе, будучи равным нулю, меньше либо равно значениям функции на всех других векторах. Этот факт не позволяет сделать никаких выводов относительно монотонности функции , поэтому переходим к рассмотрению пар с вектором . Вектор предшествует векторам , , , при этом , однако уже . Следовательно, условие монотонности нарушено, и, значит, функция немонотонна.
б) Последовательно перебрав все пары сравнимых векторов, убеждаемся, что функция монотонна.►
Обратите внимание:
для вывода о не монотонности функции
достаточно указать два булевых вектора
и
,
такие что
,
а
.
Для вывода о монотонности, нужно сравнить
значения функции на всех парах сравнимых векторов.
Определение. Говорят, что булева функция линейна, если степень ее канонического полинома Жегалкина меньше либо равна 1.
Иначе говоря, функция линейна, если ее полином Жегалкина имеет вид .
Обозначим через множество линейных функций от переменных, а через – множество всех линейных булевых функций, т.е. .
Упражнение 2.38. Дать определение нелинейной функции.
◄ Булева функция нелинейна, если степень ее канонического полинома Жегалкина больше либо равна двум. ►
Из определений
следует: для того, чтобы определить,
является функция линейной или нет,
необходимо вначале реализовать ее
полиномом Жегалкина.
Например, все функции одной переменной линейны; , , , линейными не являются.
Упражнение 2.39. а) Выписать полиномы Жегалкина линейных булевых функций от 2-х переменных.
б) Выяснить, сколько имеется линейных булевых функций от переменных.
◄ а) решите самостоятельно.
б) Между булевыми функциями переменных и каноническими полиномами Жегалкина от переменных существует взаимно однозначное соответствие, значит, линейных булевых функций от переменных столько же, сколько канонических полиномов Жегалкина вида . Каждый такой полином Жегалкина определяется набором коэффициентов , а количество таких наборов равно . Значит, .►
Упражнение 2.40. Определите, каким из классов Поста принадлежат функции:
а) ; б) ; а) ; б) .
◄ а) . Имеем:
, следовательно, ;
, следовательно, ;
, следовательно, ;
, а , следовательно, ;
, следовательно, .
б) . Имеем:
, следовательно, ;
, следовательно, ;
, следовательно, ;
, а , следовательно, ;
, следовательно, .
Пункты в) и г) решите самостоятельно.►
Классы , , , , называют классами Поста.
Упражнение 2.41. Определите, каким из классов Поста принадлежат функции
а) ; б) .
◄ а) Удобно работать с функцией, заданной таблично:
0 | 0 | 0 | 0 | 1 | 0 | 0 |
0 | 0 | 1 | 0 | 1 | 0 | 0 |
0 | 1 | 0 | 1 | 1 | 0 | 1 |
0 | 1 | 1 | 1 | 1 | 0 | 1 |
1 | 0 | 0 | 1 | 0 | 1 | 0 |
1 | 0 | 1 | 1 | 0 | 0 | 1 |
1 | 1 | 0 | 1 | 0 | 1 | 0 |
1 | 1 | 1 | 1 | 0 | 0 | 1 |
, следовательно, ;
, следовательно, ;
, следовательно, ;
,
а
,
следовательно,
.
Чтобы определить, линейна ли функция, найдем ее полином Жегалкина. Воспользуемся для этого методом неопределенных коэффициентов. Начнем с того, что выпишем в общем виде канонический полином Жегалкина от трех переменных:
.
Нам нужно подобрать такие коэффициенты , чтобы на каждом наборе значений переменных выполнялось равенство: :
; мы сократили запись, учтя, что все слагаемые, идущие вслед за , равны нулю на наборе .
; мы сократили запись, учтя, что все слагаемые, идущие вслед за , равны нулю на наборе (далее будем поступать также).
;
;
;
;
.
Теперь можем
выписать для функции полином Жегалкина
(опустив нулевые члены и единичные
коэффициенты):
.
Поскольку в полиноме Жегалкина есть
произведения переменных, делаем вывод:
.
б) решите самостоятельно. ►
Критерий Поста | это… Что такое Критерий Поста?
Критерий Поста — одна из центральных теорем в теории булевых функций, устанавливающая необходимое и достаточное условие для того, чтобы некоторый набор булевых функций обладал достаточной выразительностью, чтобы представить любую булеву функцию. Впервые сформулирован американским математиком Эмилем Постом.
В середине 60-х годов почти одновременно в СССР и во Франции появились работы, где с иных позиций и в более доступной форме излагались результаты Поста. В 80-е годы сразу целому ряду исследователей с использованием различных подходов и различной техники удалось получить достаточно компактные доказательства результатов Поста. Алгебраический подход в изучении замкнутых классов булевых функций (подалгебр итеративной алгебры Поста над множеством ) принадлежит А. И. Мальцеву.
Содержание
|
Критерий полнотыАлгебра Поста и замкнутые классы
Основная статья: Замкнутые классы булевых функций
Булева функция — это функция типа , где , а — арность. Количество различных функций арности равно , общее же количество различных булевых функций бесконечно. Вместе с тем, очевидно, что многие функции могут быть выражены через другие с использованием оператора суперпозиции. Например, давно известно, что из дизъюнкции и отрицания можно, используя законы де Моргана, получить конъюнкцию. Кроме того, любая булева функция (за исключением тождественной единицы) может быть представлена в виде ДНФ, то есть, в терминах конъюнкции, дизъюнкции и отрицания. Возникает естественный вопрос: как определить, будет ли данный набор функций достаточным, чтобы представить любую булеву функцию? Такие наборы называются функционально полными.
Теорема Поста даёт ответ на этот вопрос. Поскольку условие теоремы является необходимыми и достаточным, её называют также критерием.
Идея теоремы состоит в том, чтобы рассматривать множество всех булевых функций как алгебру относительно операции суперпозиции. Сейчас она носит имя алгебра Поста. Эта алгебра содержит в качестве своих подалгебр множества функций, замкнутых относительно суперпозиции. Их называют ещё замкнутыми классами. Пусть — некоторое подмножество . Замыканием множества называется минимальная подалгебра , содержащая . Иными словами, замыкание состоит из всех функций, которые являются суперпозициями . Очевидно, что будет функционально полно тогда и только тогда, когда . Таким образом, вопрос, будет ли данный класс функционально полон, сводится к проверке того, совпадает ли его замыкание с .
Оператор является оператором замыкания. Иными словами, он обладает (среди прочих) свойствами:
- (экстенсивность)
- (монотонность)
- (идемпотентность)
Говорят, что множество функций порождает замкнутый класс (или класс порождается множеством функций ), если .
Множество функций называется базисом замкнутого класса , если и для любого подмножества множества , отличного от .
Если к подалгебре , не совпадающей с прибавить один элемент, ей не принадлежащий, и образовать замыкание, результатом будет новая подалгебра, содержащая данную. При этом, она совпадёт с , в том и только в том случае, если между исходной подалгеброй, и нет никаких других подалгебр, то есть, если исходная подалгебра была максимальной. Таким образом, для того, чтобы проверить, что данное множество функций функционально полно, достаточно убедиться, что оно не входит целиком ни в одну из максимальных подалгебр . Оказывается, что таких подалгебр всего пять, и вопрос принадлежности к ним может быть решён просто и эффективно.
Двойственность, монотонность, линейность. Критерий полноты
Ниже приведены некоторые следствия, вытекающие из теорем о двойственных функциях.
- Если — замкнутый класс, то — также замкнутый класс.
- Множество образует замкнутый класс.
- Если , то . В частности, если — базис класса , то — базис класса .
Перейдем теперь к выяснению полноты конкретных наборов функций.
Основные классы функций
- Функция называется сохраняющей ноль, если . Обозначают, что .
- Функция называется сохраняющей единицу, если . Обозначают, что .
- Функция называется самодвойственной, если на противоположных наборах она принимает противоположные значения, то есть для самодвойственной функции выполняется тождество . Обозначают, что .
- Функция называется монотонной: . Обозначают, что .
- Функция называется линейной, когда её можно представить полиномом первой степени, то есть . Обозначают, что .
Теорема о замкнутости основных классов функций
Отметим, что ни один из замкнутых классов целиком не содержится в объединении остальных четырёх.
Это вытекает из следующих соотношений:
|
Формулировка критерия
|
См. также
- Булева функция
- Законы де Моргана
- Алгебра логики
- Стрелка Пирса
- Дискретная математика
Литература
- С. С. Марченков, «Замкнутые классы булевых функций»
- Образовательный сайт MiniSoft
Базовая подготовка блюстителя порядка
Сертифицированный POST регулярный базовый курс (базовая академия) является стандартом обучения для офицеров полиции, заместителей шерифа, школьных окружных полицейских, следователей окружного прокурора, а также некоторых других категорий блюстителей порядка.
Базовая академия сложна как физически, так и умственно. Он включает как минимум 664 часа обучения и тестирования, разработанных POST, в 42 отдельных областях обучения, называемых областями обучения. Большинство академий базового обучения, сертифицированных POST, превышают минимум 664 часа на 200 или более часов, а некоторые академии предлагают более 1000 часов обучения и тестирования.
Студенты Академии проходят различные письменные тесты, тесты на навыки, упражнения и сценарии. Студенты также должны участвовать в строгой программе физической подготовки, кульминацией которой является батарея рабочих образцов (тест на физические способности) в конце академии. Студенты должны пройти все тесты, чтобы закончить базовую академию.
Для многих других офицеров по поддержанию мира курс PC 832 является стандартом обучения. 40-часовой курс PC 832 Arrest и 24-часовой курс PC 832 по огнестрельному оружию могут быть представлены отдельно или как единый курс. Тем, кто заинтересован в обучении по курсу PC 832, следует напрямую связаться с ведущими курса по курсу PC 832, чтобы получить информацию о регистрации, расписании и требованиях к курсу.
Стандартный формат регулярного базового курса представляет собой последовательность инструкций, состоящую из одной части, с минимальным требованием 664 часов. Существует два стиля презентации: интенсивный и расширенный. Интенсивный формат — это очная академия, которая обычно собирается с понедельника по пятницу с 8:00 до 17:00. Расширенный формат — это академия неполного рабочего дня или выходного дня, которая работает по вечерам и в выходные дни.
Модульный формат регулярного базового курса поставляется в виде последовательности из трех частей, которая одновременно обеспечивает программу обучения резерва, поскольку эти три модуля совпадают с требованиями к обучению для трех уровней офицеров полиции резерва Калифорнии. Минимальное требование составляет 730 часов, что обеспечивает необходимую избыточность обучения в критических областях навыков из-за последовательности из трех частей, которую можно проходить в течение длительного периода времени.
Аффилированные и неаффилированные студенты
Аффилированные студенты — это те студенты, которые успешно завершили процесс найма/отбора в отделе, были наняты в качестве новобранца или стажера, и отдел «спонсирует» (т.
е. оплачивает) их обучение в академии. Эти новобранцы / кадеты обычно получают зарплату стажера во время учебы в академии. Неаффилированные студенты — это те, кто «самостоятельно спонсирует» (т. е. они сами оплачивают обучение в академии). Эти студенты, как правило, работают полный или неполный рабочий день, не связанный с правоохранительными органами, и могут или не могут начать процесс подачи заявления в правоохранительный орган.
Вне зависимости от того, являетесь ли вы аффилированным или неаффилированным студентом, академия разработана таким образом, чтобы обеспечить требовательную, строгую и интерактивную среду обучения для всех студентов. Цель каждой академии, сертифицированной POST, состоит в том, чтобы гарантировать, что выпускники будут хорошо подготовлены и успешны в программе полевой подготовки / полицейской подготовки, а также в своей карьере в качестве офицера по поддержанию мира в Калифорнии.
41 Сертифицированные POST академии базовой подготовки, а не POST, представляют академию как в стандартном, так и в модульном форматах.
Те, кто заинтересован в получении конкретной информации об академиях о вступительных требованиях, стоимости и расписании курсов, должны обращаться непосредственно в академии. Лица, заинтересованные в приеме на работу и посещении академии в качестве аффилированного или спонсируемого новобранца, должны напрямую связаться с агентствами или их отделами кадров, чтобы инициировать процесс найма.
Этический кодекс сотрудников правоохранительных органов
Этический кодекс устанавливает основу для всех мотивов, действий и ожиданий сотрудников правоохранительных органов. В соответствии с Постановлением Комиссии 1013 Кодекс должен применяться ко всем стажерам блюстителей порядка во время базового курса и ко всем другим лицам во время назначения. Этический кодекс правоохранительных органов выглядит следующим образом:
Как сотрудник правоохранительных органов, моя основная обязанность — служить; для защиты жизни и имущества; защищать невиновных от обмана, слабых от угнетения или запугивания, а миролюбивых от насилия и беспорядков; и уважать конституционные права всех на свободу, равенство и справедливость.
Я сохраню свою личную жизнь незапятнанной в пример всем; сохранять мужественное спокойствие перед лицом опасности, презрения или насмешек; развивать самообладание; и постоянно помните о благополучии других. Честный в мыслях и делах как в личной, так и в официальной жизни, я буду образцовым в соблюдении законов страны и правил моего ведомства. Все, что я увижу или услышу, конфиденциального характера или что будет доверено мне в моем официальном качестве, будет всегда храниться в секрете, если раскрытие не потребуется для выполнения моих обязанностей.
Я никогда не буду вести себя официозно и никогда не позволю личным чувствам, предрассудкам, враждебности или дружбе влиять на мои решения. Без компромиссов в преступлении и с безжалостным преследованием преступников я буду применять закон вежливо и надлежащим образом, без страха или благосклонности, злого умысла или недоброжелательности, никогда не применяя ненужную силу или насилие и никогда не принимая чаевых.
Я признаю значок моего офиса как символ общественной веры и принимаю его как общественное доверие до тех пор, пока я верен этике полицейской службы.
Я буду постоянно стремиться к достижению этих целей и идеалов, посвящая себя перед Богом* избранной профессии… правоохранительным органам.
* Ссылка на религиозное убеждение может быть опущена, если офицер возражает против этого.
Совет по стандартам и обучению блюстителей порядка Джорджии
Совет по стандартам и обучению блюстителей порядка ДжорджииГлавная | О P.O.S.T. | Часто задаваемые вопросы | Ссылки по теме | Контакты/Проезд | ||
*** Специальные уведомления От ПОЧТА. Совет*** Сообщение от Директор Айерс Изменения правил вступили в силу 1 января 2022 г. Новое изменение правил уровней инструкторов Вступает в силу с января 2023 г. Программа обучения устойчивости в Грузии представляет собой упреждающее вмешательство обучение этому способствует здоровью и благополучию наших блюстителей порядка. Нажмите на логотип выше, чтобы узнать об этой новой программе. *** Общая информация о помощи ***
*** Офицер по охране общественного порядка Аннуитет и Благотворительный фонд ***
*** P.O.S.T. Документы ***
| ||
O.S.T. Следователь
