Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Практическое применение методов математической логики
Всякая логическая функция «n» переменных может быть задана таблицей, в левой части которой перечислены все 2n наборов значений переменных (то есть всевозможных наборов двоичных векторов длины «n»), а в правой части приведены значения функции на этих наборах. При любом фиксированном упорядочении наборов значений переменных логическая функция «n» переменных полностью определена вектор-столбцом своих значений, то есть вектором длины 2n. Поэтому число различных логических функций «n» переменных будет . В самом деле, для одного набора значений своих переменных (строка левой части таблицы) значение функции может быть либо 1, либо 0 (две возможности). Число же возможных различных наборов аргументов функции, как уже отмечалось равно 2n, поэтому число различных логических функций будет /1/. Заданием в данном пункте является построение таблицы истинности для следующего высказывания:
,
Высказыванием называется повествовательное предложение, о котором можно сказать в данный момент, что оно истинно или ложно, но не то и другое одновременно. “Истинность” или “ложность” предложения – это истинностное значение высказывания. Каждому высказыванию сопоставляется переменная, равная 1, если высказывание истинно, и равная 0, если оно ложно. Эти высказывания будут считаться простыми. Из простых высказываний с помощью логических связок могут быть построены составные высказывания. В таблице 1 приведены некоторые логические связки, используемые при задании данной функции (1).
Таблица 1-Логические связки
Правильно построенные составные высказывания называются (пропозиционарными) формулами. Истинностное значение формулы определяется через истинностные значения её составляющих в соответствии с единой таблицей истинности (таблица 2).
Таблица 2-Истиностные значения формул высказывания
Для того чтобы составить таблицу истинности для формулы, необходимо выполнить последовательность всех логических операций.
, (1)
После последовательного выполнения всех логических операций составляется таблица истинности для данной функции Таблица 3- Таблица истинности функции (1)
Приведение функции к конъюнктивным и дизъюнктивным нормальным формам. Конъюнктивным (дизъюнктивным) одночленом от переменных а1, а2, а3,…,а n называется конъюнкция (дизъюнкция) этих переменных или их отрицаний. Формула, равносильная данной формуле алгебры высказываний и являющаяся дизъюнкцией элементарных произведений (конъюнктивных одночленов), называется дизъюнктивной нормальной формой (ДНФ) данной формулы. Формула, равносильная данной формуле алгебры высказываний и являющаяся конъюнкцией элементарных произведений (дизъюнктивных одночленов), называется конъюнктивной нормальной формой (КНФ) данной формулы /2/. Справедливы следующие теоремы: любая булева функция, тождественно не равная нулю, представима и притом единственным образом в виде ДНФ по формуле:
V (2)
Любая булева функция, тождественно не равная единице представима и притом единственным образом в виде КНФ.
L (3).
Любая булева функция представима формулой, в которую входит только конъюнкция, дизъюнкция и отрицание /2/. Искомая ДНФ для функции (1) имеет вид:
Искомая КНФ для функции (1) будет иметь следующий вид:
В расчетах ДНФ и КНФ использована методика /2/. Построение полинома Жегалкина. Представление булевой функции над базисом {0,1,v,Å} называется полиномом Жегалкина. Таким образом, всякая булева функция представима в виде:
где ∑ - сложение по модулю два, знак · обозначает конъюнкцию/7/. Для функции f (x, y, z) (1) полином Жегалкина имеет вид:
P(x, y, z)=b0×1Åb1×xÅb2×yÅb3×zÅb4×x×yÅb5×x×zÅb6y×zÅb7x×y×z
Метод неопределенных коэффициентов заключается в том, что путем последовательной подстановки переменных x, y, z и соответственно значений функции при этих переменных, из таблицы 1 в данный полином (4), строится система уравнений:
0=b0×1Åb1×0Åb2×0Åb3×0Åb4×0×0Åb5×0×0Åb60×0Åb70×0×0 0=b0×1Åb1×0Åb2×0Åb3×1Åb4×0×0Åb5×0×1Åb60×1Åb70×0×1 1=b0×1Åb1×0Åb2×1Åb3×0Åb4×0×1Åb5×0×0Åb61×0Åb70×1×0 0=b0×1Åb1×0Åb2×1Åb3×1Åb4×0×1Åb5×0×1Åb61×1Åb70×1×1 0=b0×1Åb1×1Åb2×0Åb3×0Åb4×1×0Åb5×1×0Åb60×0Åb71×0×0 0=b0×1Åb1×1Åb2×0Åb3×1Åb4×1×0Åb5×1×1Åb60×1Åb71×0×1 0=b0×1Åb1×1Åb2×1Åb3×0Åb4×1×1Åb5×1×0Åb61×0Åb71×1×0 0=b0×1Åb1×1Åb2×1Åb3×1Åb4×1×1Åb5×1×1Åb61×1Åb71×1×1
По свойству суммы по модулю два находится b:
b0=0, b1=0, b2=1, b3=0, b4=1, b5=0, b6=1, b7=1
Полином Жегалкина будет иметь вид:
¦(x, y, z) = y Å x×y Å y×z Å x×y×z
Правильность построения полинома проверяется таблицей истинности:
Таблица 4 - Таблица истинности для полинома Жегалкина
Дифференцирование функции нескольких переменных. Производной булевой функции ¦(xn) по совокупности переменных называется функция:
На основе данной формулы (5) находится производная по одной переменной x
Для данной функции (1) производная по формуле (6) принимает вид:
Таблица 5 - Производная ∂¦⁄∂ x для формулы(7)
Вектор значений функции (7) имеет вид:
Производная по двум переменным находится также по формуле (5):
Для данной функции (1) производная принимает вид:
Таблица 6 - Производная ∂2¦⁄∂(x; y) для формулы(9)
Вектор значений функции (6) имеет вид:
Применение теории графов
|
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2019-10-15; просмотров: 174; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.143.31 (0.029 с.) |