Презентация по математической логике на тему Двойственные функции

Двойственные функцииБулевы функции Двойственные функцииБулева функция f*(x1, …, xn) называется двойственной булевой функции f(x1, …, xn), если она получена из f(x1, …, xn) инверсией всех аргументов и самой функции, то есть ПримерПостроим функцию, двойственную стрелке Пирса.Значения двойственной функции можно получить переворотом и инверсией столбца значений исходной функции Пары двойственных элементарных функций:0 - 1 Дизъюнкция – конъюнкцияШтрих Шеффера – стрелка ПирсаЭквивалентность – антиэквивалентность Пример. Покажем, что дизъюнкция двойственна конъюнкции (применив законы де Моргана и двойного отрицания): Двойственная формулаОпределениеФормула F* называется двойственной формуле F, если она получена из F заменой символов функций на символы двойственных им функций.Пример ПримерРассмотрим формулу задающую булеву функцию НЕ-ИЛИ, то есть стрелку Пирса. Двойственная ей формула  должна задавать функцию, двойственную стрелке Пирса – это штрих Шеффера: в самом деле   это функция НЕ-И, то есть штрих Шеффера. Самодвойственная функцияФункция, совпадающая со своей двойственной, называется самодвойственной.F*=FСледствие из принципа двойственности.Если формулы F1 и F2 равносильны, то двойственные им формулы F*1 и F*2, также равносильны. Способы получения двойственной функции– по определению двойственной функции – инверсией в формуле Ff всех аргументов и самой функции;– по определению двойственной формулы и принципу двойственности – заменой в формуле Ff символов функций на символы двойственных им функций;– построением таблицы истинности исходной функции по заданной формуле Ff, а затем переходом к таблице истинности двойственной функции (переворотом и инверсией столбца значений исходной функции). Упражнение 1Построить формулы для функций, двойственных данным, пользуясь двумя разными способами: определением двойственной функции и принципом двойственности. Сравнить таблицы истинности, построенные по полученным формулам. Упражнение 2Двойственны ли формулы Ff и Gg? Функции f и g?