35. Классы самодвойственных и монотонных функций. Примеры.

Функция f называется монотонной, если для любых двух наборов значений входных переменных a и b из того, что a³b, следует, что f(a)³f(b).

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

В минимальной ДНФ монотонной функции нет переменных в инверсной форме.

Из этого свойства можно вывести, что суперпозиция монотонных функций снова будет монотонной функцией, т.е. множества монотонных функций образует класс монотонных функций, обозначаемый как M. Базис класса М образуют обе константы и пара функций – конъюнкция и дизъюнкция, т.е. множество {xx×yy, xxÚyy, 0,1}.

Для функции f(xx₁,xx₂,…,xx_n) функция ff(`xx<sub>1</sub>,`xx₂,…,`xx_n) называется двойственной к ней.

Обозначим двойственную функцию как f*.

Функция называется самодвойственной, если она равна своей двойственной.

Свойства самодвойственных функций.

1. Самодвойственная функция полностью определяется своим видом на верхней половине таблицы истинности. Например, значение функции на наборе <a₁, a₂, …, a_n> равно 0, то значение функции на инверсном наборе <`a<sub>1</sub>,`a₂, …,`a_n> должно быть равно 1.

2. Из первого свойства вытекает, что число различных функций от n переменных равно 2^m, где m=2^n-1.

3.Ссамодвойственных функций, существенно зависящих ровно от двух переменных нет.

4. СДНФ самодвойственной функции будет иметь ровно 2^n-1 конъюнкций.

5. Суперпозиция самодвойственных функций будет функция самодвойственная. Множество самодвойственных функций образуют класс, который принято обозначать как D. Базисом класса является функция трёх переменных {xx×`yy Úxx×`z Ú`yy×`z}.

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

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

В качестве примера можно назвать штрих Шеффера или стрелку Пирса.

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

• (конъюнкция, дизъюнкция, отрицание);

• (конъюнкция, сложение по модулю два, константа один).

Первая система используется, например, для представления функций в виде дизъюнктивных и конъюнктивных нормальных форм, вторая — для представления в виде полиномов Жегалкина.

37 Алгебра предикатов. Логические и кванторные операции над предикатами. Примеры.

Операции отрицание, конъюнкция, дизъюнкция, импликация, эквивалентность определяются аналогично как для предикатов, так и для высказываний. Такими операциями над предикатами являются две кванторные операции – квантор общности и квантор существования

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

Конъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «истина» при тех и только тех значениях х из Т, при которых каждый из предикатов принимает значение «истина», и принимает значение «ложь» во всех остальных случаях.

Дизъюнкцией двух предикатов А(х) и В(х) называется новый предикат , который принимает значение «ложь» при тех и только тех значениях х из Т, при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях.

Отрицанием предиката А(х) называется новый предикат, который принимает значение «истина» при всех значениях х из Т, при которых предикат А(х) принимает значение «ложь», если А(х) принимает значение «истина». Множеством истинности предиката, х Х является дополнение Т' к множеству Т в множестве Х.

Импликацией предикатов А(х) и В(х) называется новый предикат , который является ложным при тех и только тех значениях х из Т, при которых А(х) принимает значение «истина», а В(х) — значение «ложь», и принимает значение «истина» во всех остальных случаях

Операцией связывания квантором общности называется правило, по которому каждому одноместному предикату , определенному на множестве, сопоставляется высказывание, обозначаемое(читается: "для всякого [значения][истинное высказывание]"), которое истинно в том и только в том случае, когда предикаттождественно истинен, и ложно в противном случае,

Пример:

Пусть

Тогда

38

Отношение равносильности на множестве формул алгебры высказываний. Равносильности, определяющие законы оперирования с кванторами.

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

Отношение равносильности формул А и В является отношением эквивалентности (А~В):

а) А≡А для любой формулы А (рефлексивность),

б) если А≡В, то B≡A для любых формул А и В (симметричность),

в) если А≡В и В≡С, то А≡С для любых формул А, В, С (транзитивность).

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

2 Формулы, содержащие одинаковые кванторы, называют равносильными, или эквивалентными Они имеют следующий вид:

Vx VyP (x, y) = VxP (xf у) (формулы вида Vx УУР (х, у) и вида / у УхР (х, у) истинные тогда и только тогда, когда Р (х, у) - тождественно

З 3yP (xt у) = Зу Зхр (х, у) (формулы вида З 3yP (xt у) и вида Зу 3xP (xt в) истинные только тогда, когда Р (х, у) является тождественно-истинным предикатом)

39. Выразительные возможности формального языка алгебры высказываний.

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