Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 1.97 Mb.
|
Задачи1. Доказать, что пересечение любых двух замкнутых классов замкнуто. 2. Доказать, что объединение двух замкнутых классов не всегда замкнуто Тема 3.7 Теорема Поста. Для того чтобы система функций была полной, необходимо и достаточно, чтобы она не содержалась целиком ни в одном из классов T0, T1, L, S, M. Доказательство. Докажем необходимость этого условия. Пусть система N = {f1, f2, ...fs, ...} полна в Р2, покажем, что тогда она не лежит целиком в Q, где через Q обозначим любой из классов T0, T1, L, S, M. Докажем от противного, пусть N Q, очевидно, [N] [Q] = Q, но [N] = P2, т.к. N – полна в Р2, отсюда Р2=Q, но это не так. Необходимость доказана. Докажем достаточность. Пусть F = {f0, f1, fL, fm, fs}, где f0T0, f1T1, fLL, fsS и fmM. Покажем, что суперпозицией функций системы F можно получить полную систему G = {x1&x2,  }.1. Пусть g(x) = f0(x, …, x). Тогда g(0) = f( 0, …, 0) = 1. Далее возможны два случая: g(1) = 1. Тогда g(x) 1. Функция h(x) = f1(g(x), …, g(x)) = f1(1, …, 1) = 0, т.е. h(x) 0. Получили константы 0 и 1; g(1) = 0. Тогда g(x) = . По лемме о несамодвойственной функции суперпозицией над {fs, } можно получить одну из констант, например, 0. Тогда f0(0, …, 0) = 1 есть другая константа.В обоих случаях получили обе константы. 2. По лемме о немонотонной функции суперпозицией над {fm, 0, 1} можно получить отрицание. 3. По лемме о нелинейной функции суперпозицией над {fL, 1, } можно получить конъюнкцию. Теорема доказана.Следствие. Всякий замкнутый класс функций из Р2, не совпадающий с Р2 содержится, по крайней мере, в одном из замкнутых классов T0, T1, L, S, M. Действительно, если N не является подмножеством Q, то [N] = P2, что неверно.
x1 x2 x3x1x2x30 0 0 0 1 1 1 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 10 0 0 0 1 0 0 1 Из таблицы видно, что какой бы класс мы ни взяли, всегда есть функция из данной системы , которая в этот класс не входит. Можно сформулировать следующее правило: для того чтобы система функций была полна, необходимо и достаточно, чтобы в каждом столбце критериальной таблицы был хотя бы один «минус». Отметим еще одно обстоятельство, касающееся приведенной системы. Какую бы функцию из этой системы мы ни удалили, система станет неполной, действительно, {f2, f3, f4}L, {f1, f3, f4}T1, {f1, f2, f4}T0, {f1, f2, f3}M.
Система функций {f1, ..., fs, ...} называется базисом в Р2,если она полна в Р2, но любая ее подсистема не будет полной. Например, система функций {x1&x2, 0, 1, x1 x2x3} – базис.Контрольная работа Вариант I
Вариант II
Раздел 4. ПРЕДИКАТЫ И БИНАРНЫЕ ОТНОШЕНИЯ. Тема 4.1 Понятие предиката. Область определения и область истинности предиката. Предикатом  называется функция , где произвольное множество, а определённое двоичное множество .Иначе говоря, местным предикатом, определённым на множестве называется двузначная функция от аргументов из произвольного множества . Множество называется предметной областью предиката, переменные - предметными переменными. В принципе, можно определить предикат как функцию , то есть допустить, что переменные принимают значения из различных множеств – в некоторых случаях это оказывается удобным.Для любых и существует взаимно однозначное соответствие между местными отношениями и местными предикатами на множестве , определяемое следующим образом. Каждому местному отношению соответствует предикат такой, что тогда и только тогда, когда ; всякий предикат определяет отношение такое, что тогда и только тогда, когда . При этом задаёт область истинности предиката.Всякой функции можно поставить в соответствие местный предикат такой, что тогда и только тогда, когда . Поскольку функция должна быть однозначной, то это соответствие требует, чтобы для любого выполнялось . Поэтому обратное соответствие (от предиката к функции) возможно только при выполнении указанного условия.Пример 1. а) Предикат является двухместным предикатом, предметной областью которого могут служить любые множества действительных чисел. Высказывание истинно, а высказывание ложно. Если вместо одной из переменных подставить число, то получится одноместный предикат: и так далее. б) В описаниях вычислительных процедур и, в частности, в языках программирования, часто встречаются указания типа “повторять цикл до тех пор, пока переменные и не станут равными или прекратить вычисление цикла после ста повторений”. Если обозначить через счётчик повторений, то описанное здесь условие примет вид , а само указание в целом описывается выражением: “повторять, если ”.Тема 4.2 Логические операции над предикатами. Над предикатами можно проделывать те же самые логические операции, что и над высказываниями. 1. Отрицанием n – местного предиката Р(х1, х2, …, хn), определенного на множествах М1, М2, …, Мn, называется новый n-местный предикат, определенный на тех же множествах, обозначаемый Р(х1, х2, …, хn), который превращается в истинное высказывание при всех тех значениях предметных переменных, при которых исходный предикат превращается в ложное высказывание. Теорема. Для n-местного предиката Р(х1, х2, …, хn), определенного на множествах М1, М2, …, Мn, множество истинности его отрицания Р(х1, х2, …, хn) совпадает с его дополнением множества истинности данного предиката: или .2. Конъюнкцией n – местного предиката Р(х1, х2, …, хn), определенного на множествах М1, М2, …, Мn, и т-местного предиката Q(у1, у2, …, ут), определенного на множествах N1, N2, …, Nm, называется новый (n + m)-местный предикат, определенный на множествах М1, М2, …, Мn, N1, N2, …, Nm, обозначаемый Р(х1, х2, …, хn) Q(у1, у2, …, ут), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых оба исходных предиката превращаются в истинные высказывания. Теорема. Для n-местных предикатов Р(х1, х2, …, хn) и Q(х1, х2, …, хn), определенных на множествах М1, М2, …, Мn, множество истинности конъюнкции Р(х1, х2, …, хn) Q(х1, х2, …, хn), совпадает с пересечением множеств истинности исходных предикатов: .3. Дизъюнкцией n – местного предиката Р(х1, х2, …, хn), определенного на множествах М1, М2, …, Мn, и т-местного предиката Q(у1, у2, …, ут), определенного на множествах N1, N2, …, Nm, называется новый (n + m)-местный предикат, определенный на множествах М1, М2, …, Мn, N1, N2, …, Nm, обозначаемый Р(х1, х2, …, хn) Q(у1, у2, …, ут), который превращается в истинное высказывание при всех тех и только тех значениях предметных переменных, при которых в истинное высказывание превращается по меньшей мере один исходный предикат. Теорема. Для n-местных предикатов Р(х1, х2, …, хn) и Q(х1, х2, …, хn), определенных на множествах М1, М2, …, Мn, множество истинности дизъюнкции Р(х1, х2, …, хn) Q(х1, х2, …, хn), совпадает с объединением множеств истинности исходных предикатов: .Самостоятельная работа №8. Тема 4.3 Кванторные операции над предикатами. Специфическая природа предикатов, позволяет ввести над ними такие операции, которые не имеют аналогов среди операций над высказываниями. Имеются в виду две кванторные операции над предикатами. 1. Квантор общности Для превращения одноместного предиката в высказывание нужно вместо его переменной подставить какой-нибудь конкретный предмет из области задания предиката. Имеется еще один способ для такого превращения – это применение к предикату операций связывания квантором общности или квантором существования. Каждая из этих операций ставит в соответствие одноместному предикату некоторое высказывание, истинное или ложное в зависимости от исходного предиката. Операцией связывания квантором общности называется правило, по которому каждому одноместному предикату Р(х), определенному на множестве М, сопоставляется высказывание, обозначаемое , которое истинно в том и только в том случае, когда предикат Р(х) тождественно истинен, и ложно в противном случае, то естьСловесным аналогом квантору общности является: «для любого», «для каждого», «для всякого» и т.п. В выражении переменная х уже перестает быть переменной в обычном смысле этого слова, то есть вместо нее невозможно подставить какие бы то ни было конкретные значения. Говорят, что переменная х связанная.Если одноместный предикат Р(х) задан на конечном множестве М = {a1, a2, …, an}, то высказывание эквивалентно конъюнкции Р(а1) Р(а2) … Р(аn). Пример. Пусть х определен на множестве людей М, а Р(х) – предикат «х – смертен». Дать словесную формулировку предикатной формулы .Решение. Выражение означает «все люди смертны». Оно не зависит от переменной х, а характеризует всех людей в целом, т. е. выражает суждение относительно всех х множества М.Операцией связывания квантором общности по переменной х1 называется правило, по которому каждому n-местному (n 2) предикату Р(х1, х2, …, хn), определенному на множествах М1, М2, …, Мn, сопоставляется новый (n-1)-местный предикат, обозначаемый , который для любых предметов, превращается в высказывание , истинное в том и только в том случае, когда одноместный предикат , определенный на множестве М1, тождественно истинен, и ложное в противном случае, то есть: |
}
. Определите булевую функцию, которую реализует данная формула (составить таблицу истинности) 
. Определите булевую функцию, которую реализует данная формула (составить таблицу истинности)
