Программа по формированию навыков безопасного поведения на дорогах и улицах «Добрая дорога детства» 2
Скачать 1.97 Mb.
|
Совершенной дизъюнктивной формой формулы алгебры высказываний (СДНФ) называется ДНФ, в которой:
 ,где дизъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=1. Теорема (о СДНФ). Для всякой не равной тождественному нулю формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СДНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки дизъюнктивных членов. Совершенной конъюнктивной формулой формулы алгебры высказываний (СКНФ) называется КНФ, в которой:
,где конъюнкция берется по всем наборам с=(с1, с2, …, сn) из 0 и 1, для которых F(c)=0. Теорема (о СКНФ). Для всякой не равной тождественной единице формулы логики высказываний F(x1, x2, …, xn) существует такая формула F1, зависящая от того же списка переменных и находящаяся в СКНФ относительно этого списка, что F1 выражает собой формулу F. Формула F1 определена однозначно с точностью до перестановки конъюнктивных членов. Опишем два способа приведения к совершенным нормальным формам. 1-й способ – аналитический. Приведение к СДНФ. Алгоритм приведения.
Полученная формула и является СДНФ данной формулы. Привести следующие формулы к СДНФ с помощью равносильных преобразований: 1. ;2. ;3. .Решение. 1. .2. 3. Приведение к СКНФ. Алгоритм приведения.
Полученная формула и является СКНФ данной формулы. Привести следующие формулы к СКНФ с помощью равносильных преобразований: 1. ;2. .Решение. 1. 2. 2-й способ – табличный. Составляем таблицу истинности для данной функции. Приведение к СДНФ. Алгоритм приведения. Строим таблицу значений формулы. Рассматриваем только те строки, в которых значение формулы равно единице. Каждой такой строке соответствует конъюнкция всех аргументов (без повторений). Причем, аргумент, принимающий значение 0, входит в нее с отрицанием, значение 1 – без отрицания. Наконец, образуем дизъюнкцию всех полученных конъюнкций. Построить СДНФ для данных формул логики высказываний. 1. .2. Решение. 1. .Строим таблицу истинности для формулы F: №xyz 00001101001110201000030110104100111510111161100007111011Рассматриваем только 4, 5 и 7 наборы, так как только на этих наборах формула принимает значение равное единице.СДНФ имеет вид: 2. 2. Строим таблицу истинности для формулы F: №xyx yF=(x y)xy00010101102100031111СДНФ (1): № 3: F = x y. Приведение к СКНФ. Алгоритм приведения. Рассматриваем только те строки таблицы, где формула принимает значение 0. Каждой такой строке соответствует дизъюнкция всех переменных (без повторений). Причем аргумент, принимающий значение 0, берется без отрицания, значение 1 – с отрицанием. Наконец, образуют конъюнкцию полученных дизъюнкций. Построить СКНФ для данных формул логики высказываний. 1. .2. Решение.
№xyz 0000010010201003011041001510116110071111Рассматриваем только наборы, на которых формула принимает значение ноль.СКНФ (0): № 0, 1, 2, 3, 6:
№xyF=(x y)xy0000101021003111СКНФ (0): № 0, 1, 2: Самостоятельная работа №5. Тема 3.3 Минимальная ДНФ. Уже известно, что произвольная булева функция может быть представлена формулой в дизъюнктивной и конъюнктивной нормальной форме. Равносильными преобразованиями можно получить формулу, содержащую меньшее, чем исходная, число переменных. Минимальной ДНФ (МДНФ) функции f(x1, x2, …, xn) называется ДНФ, реализующая функцию f и содержащая минимальное число символов переменных по сравнению со всеми другими ДНФ, реализующими функцию f. Минимальную ДНФ данной формулы можно найти, перебрав конечное число равносильных ей ДНФ и выбрав среди них ту, которая содержит минимальное число переменных. Однако при большом числе переменных такой перебор практически невыполним. Существуют эффективные способы нахождения минимальной ДНФ. Рассмотрим два из них. Каждый из рассмотренных ниже методов состоит из двух этапов:
Если для всякого набора а = (а1, а2, …, an) значений переменных условие g(a)=1 влечет f(a)=1, то функция g называется частью функции f (или функция f накрывает функцию g). Если при этом для некоторого набора с = (с1, с2, …, сn)функция g(c)=1, то говорят, что функция g накрывает единицу функции f на наборе с (или что g накрывает конституенту единицы функции f).Конституента единицы функции f есть часть функции f, накрывающая единственную единицу функции f. Элементарная конъюнкция К называется импликантом функции f, если для всякого набора а = (а1, а2, …, an) из 0 и 1 условие К(а)=1 влечет f(a)=1. Определение. Импликант К функции f называется простым, если выражение, получающееся из него выбрасыванием любых множителей, уже не импликант функции f. Всякий импликант функции f есть часть функции f. Теорема. Всякая функция реализуется дизъюнкцией всех своих простых импликант. Сокращенная ДНФ функции f есть дизъюнкция всех простых импликант функции f. Всякая функция f реализуется своей сокращенной ДНФ. Для всякой функции, не равной тождественно нулю, существует единственная сокращенная ДНФ. Минимизация формул алгебры логики на кубе. Рассмотрим проблему минимизации для геометрического способа задания формул алгебры логики на кубе. Сопоставим различным геометрическим элементам куба (вершинам, ребрам, граням и кубу) конъюнкции различных рангов. Сумма размерности геометрического эквивалента и ранга конъюнкции, ему соответствующей равна числу аргументов формулы алгебры логики. Каждый геометрический элемент меньшей размерности покрывается геометрическими элементами большей размерности. Каждая конъюнкция большего ранга покрывается всеми конъюнкциями меньшего ранга. Геометрические эквиваленты называют интервалами. Интервал L-го ранга – подмножество вершин куба, соответствующих конъюнкции ранга L. Например: Kонъюнкции x соответствует 4 вершины: 100, 101, 110, 111. На кубе отмечают вершины, где формула алгебры логики равна 1. Эти вершины образуют подмножество Т1. Для того, чтобы задать ДНФ на кубе, необходимо задать покрытие всех вершин. Максимальный интервал J – интервал, для которого не существует никакого другого интервала J’ с рангом меньше, чем у J, и такого, что выполняется следующее соотношение .Например: Пусть есть функция, которая равна 1 в отмеченных точках. J1 и J3 – максимальные интервалы,J2 – не является максимальным  где ri – ранги конъюнкции, образующих покрытие множества T1. Необходимо найти Т1, при котором R будет минимальным. Сокращенная ДНФ(СДНФ) – ДНФ, которая соответствует покрытию множества Т1 всеми максимальными интервалами. В данном примере СДНФ = .Минимальная ДНФ получается из СДНФ путем выбрасывания из покрытия множества Т1 максимальными интервалами некоторых “лишних” интервалов. Тема 3.4 Представление булевой функции в виде минимальной ДНФ. Метод квайна, минимизация при помощи карт Вейча-Карно Самостоятельная работа №6. Самостоятельная работа №7 Тема 3.5 Полнота множества функций. Любую булеву функцию можно выразить в виде формулы через элементарные функции: отрицание, конъюнкцию, дизъюнкцию, двоичное сложение и константу 0 или 1. Эти функции можно рассматривать как систему элементарных функций, через которые выражается любая булева функция. Система булевых функций {f1, f2, …, fm} называется полной, если любая булева функция может быть выражена через функции этой системы с помощью составления из них сложных функций.. Составление сложных функций из элементарных функций системы называется суперпозицией. Достаточное условие полноты системы. Пусть система функций {f1, f2, …, fm} (I) полная и любая из функций этой системы может быть выражена через функции g1, g2, …, gl , тогда система { g1, g2, …, gl}(II) тоже полная. Полноту системы можно доказать , опираясь на то, что любая булева функция представима в виде полинома, или доказав с помощью достаточного условия. Тема 3.6 Важнейшие замкнутые классы. Пусть MР2. Замыканием М называется множество всех функций из P2, которые можно выразить формулами над М. Замыкание М обозначается [M]. Множество функций М называется замкнутым классом, если [M]=M. Пример: 1) P2 – замкнутый класс.
В терминах замыкания и замкнутого класса можно дать другое определение полноты, эквивалентное исходному: М – полная система, если [M] = P2. 3) A = {f(x1, ..., xn) f(1, 1, ..., 1) = 0} – незамкнутый класс. Возьмем формулу над этим множеством. Пусть f, g1, ..., gn A, т.е. f(1, 1, ..., 1) = 0, g1(1, 1, ..., 1) = 0, тогда f(g1, ..., gn) [A]. Посмотрим, принадлежит ли функция f(g1, ..., gn) множеству А. f(g1(1, ..., 1), g2(1, ..., 1), ..., gn(1, ..., 1) = f(0, ..., 0)), но f(0, ..., 0) не обязано быть равным 0. Действительно, пусть g1(x1, x2) = x1 x2, g2(x) = x A. Возьмем g2(g1(x1, x2)) = x1 x2 [A], g2(g1(1, 1)) = 1 1 = 0, следовательно, g2(g1(x1, x2)) A, отсюда [A] A и А – незамкнутый класс.
Т0 = { f(x1, ..., xn f(0, ..., 0) = 0, n = 1, 2, ...}. Покажем, что Т0 является собственным подмножеством Р2, т.е. Т0 и Т0 Р (не совпадает с Р2). Для этого достаточно привести примеры функций, входящих в Т0, и примеры функций из Р2, не входящих в Т0: x1&x2, x1x2, xТ0 и x1|x2, x1 x2, Т0. Покажем далее, что [Т0] = Т0. Вложение Т0 [ Т0] очевидно, так как по определению формулы любая функция из Т0 является формулой над Т0 и, следовательно, принадлежит [Т0]. Покажем, что [Т0] Т0. Для этого надо показать, что Ф = f(f1, ..., fm) [ Т0], если все функции f, f1, f2, f3, ..., fm Т0. Надо заметить, что в формуле в качестве функции f1 могут быть взяты переменные, которые мы договорились считать тождественными функциями. Тождественная функция принадлежит классу Т0, поэтому достаточно показать, что Ф = f (f 1, ..., fm) Т0. Для этого рассмотрим следующую функцию: Ф(0, ..., 0) = f (f 1(0, ..., 0), f 2(0, ..., 0), ...) = f(0, ..., 0) = 0.Число функций, зависящих от n переменных и принадлежащих Т0, будет равно
T1 = {f(x1, ...) f(1, 1, ...) = 1}; x1&x2, x1x2, xT1, х1х2, x1 x2T1, следовательно Т1 – собственное подмножество Р2.  Покажем, что [T1] T1, обратное включение следует из определения формулы и замыкания. Так как тождественная функция входит в Т1, можно рассмотреть Ф = f(f1, ..., fn) [T1], где f, f1, ..., fn T1. Найдем Ф(1, ..., 1) = f(f1(1, ..., 1), ..., fn(1, ..., 1)) = f(1, ..., 1) = 1, следовательно, Ф = f(f1, ..., fn) T1, отсюда следует [T1] = T1.
S = {f(x1, ...)f* = f }; x, , x1x2x3S, x1&x2, x1x2, x1x2S, следовательно, S – собственное подмножество Р2. |S(n)| = . Покажем, что [S]S. Ф = f(f1, ..., fn) [S], если f, f1, ..., fn S, а также, что Ф S. По принципу двойственности, Ф* = f*(f1*, ..., fn*) = f(f1, ..., fn) = Ф, отсюда S – замкнутый класс.
L = {f(x1, ...) f = c0c1x1...cnxn}; очевидно, L , с другой стороны L P2, так как x1&x2 L. Заметим, что тождественная функция принадлежит L и |L(n)| = 2n+1. Покажем, что [L] L. Рассмотрим Ф = f(f1, ..., fm), где f, f1, ..., fn L. Тогда Ф = а0 а1(с10 с11х1 ... c1nxn1) a2(c20 c21x1 c22x2...c2nxn2)...an(cm0 cm1x1 ... cmnxnm) = в0 в1х1 ... вnхn ФL.
Набор = (1, ..., n) предшествует набору = (1, ..., n) и обозначается , если для 1in ii, например: = (0010), = (0110), тогда . Не любые два набора находятся в отношении предшествования, например, наборы (0110) и (1010) в таком отношении не находятся. Отношение предшествования () является отношением порядка на множестве наборов длины n, множество таких наборов будет частично упорядоченным множеством по отношению к операции.Функция f(x1, ..., xn) называется монотонной, если для двух наборов и , таких что , выполняется f()f(). Функции 0, 1, x, x1&x2, x1x2 M, x1x2, x1 x2, x1 ~ x2 M. Для числа монотонных функций, зависящих от n переменных, существуют оценки сверху и снизу, но точное число сосчитать не удается. Покажем, что М замкнутый класс. Рассмотрим функцию Ф[M], Ф = f(f1, ..., fm), где f, f1, ..., fmM, причем можем считать, что все они зависят от n переменных. Пусть набор = 1, ..., n), = (1, ..., n). Рассмотрим Ф1, ..., n) = f(f11, ..., n), …, fm1, ..., n)) и Ф(1, ..., n) = f(f1(1, ..., n), ..., fm(1, ..., n)). Здесь f1() f1(), ..., fm() fm(), тогда набор (f1(), ..., fm())(f1(), ..., fm()), но тогда Ф() Ф(), так как fM, отсюда Ф = f(f1, ..., ) – монотонная функция.Функция f есть суперпозиция над M, если f реализуется некоторой формулой над M. Лемма о немонотонной функции. Отрицание можно получить суперпозицией констант 0 и 1, тождественной функции и немонотонной функции. Доказательство. Пусть f(x1, ..., xn) – немонотонная функция. Тогда существуют наборы и , для которых но Пусть i1, …, ik есть все те номера аргументов, для которых , p=1, …, k. На всех остальных аргументных местах j имеем j = j. В выражении заменим нули на местах i1, …, ik на x. В результате получим функцию g(x), для которой g(0) = f() = 1 и g(1) = f() = 0. Функция g(x) является отрицанием.Классы T0, T1, L, S, M пересекаются, но не совпадают, что видно из следующей таблицы, где «+» означает, что функция принадлежит данному классу и «-» – не принадлежит.
|
