42421

Равносильность формул. Закон двойственности. Логические функции

Лабораторная работа

Математика и математический анализ

Каждая формула представляет собой функцию входящих в нее букв А В Определение1: Формулы F1 и F2 называются равносильными если при любых значениях входящих в них переменных x1x2xn эти формулы принимают одинаковые значения. Между понятиями равносильности и эквивалентности существует связь: если формулы F1 и F2 равносильны то формула F1F2 эквивалентность принимает одни и те же значения при всех значениях переменных и обратно: если формула F1F2 принимает одни и те же значения при всех значениях переменных то формулы F1 и F2...

Русский

2013-10-29

120.5 KB

23 чел.

Практическое занятие №8

Тема: Равносильность формул. Закон двойственности.

Логические функции.

Занятие рассчитано на 2 академических часа.

Цель работы: овладение практическими навыками  равносильных преобразований булевых функций с помощью закона двойственности.

Теоретическая часть

Равносильность формул

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

Определение1: Формулы F1 и F2 называются равносильными, если при любых значениях входящих в них переменных x1,x2,…,xn эти формулы принимают одинаковые значения.

Примеры равносильных формул:

равносильно х

ху равносильно ух

у)z равносильно х z)

х+у равносильно у+х

(х+у)+ z равносильно х+(у+z)

х+х равно х

хх равно х

х+(ху) равносильно х

равносильно

равносильно .

Между понятиями равносильности и эквивалентности существует связь: если формулы F1 и F2 равносильны, то формула (F1F2) (эквивалентность) принимает одни и те же значения при всех значениях переменных и обратно: если формула (F1F2) принимает одни и те же значения при всех значениях переменных, то формулы F1 и F2 равносильны.

Логические операции ,,, и не являются независимыми друг от друга. Одни из них можно выражать через другие так, что при этом получаются равносильные формулы. Например, знак ~ может быть выражен через знаки и &  на основании соотношения x~y равносильно  (xy)&(yx), которое легко доказывается на основании определения действий ~, и &.

Итак, все операции посредством равносильных выражений можно заменить двумя: и  . Аналогичным образом, можно все операции заменить на &  и . Исходя из этого, операция двойственна и наоборот.

Закон двойственности

Определение 2: Формулы F и U называются двойственными, если одна получается из другой заменой каждой операции на двойственную.

Примеры.

  1.   двойственно .
  2.  двойственно .
  3.   двойственно .
  4.   двойственно .

Как для операций, так и для формул отношение двойственности взаимно.

Закон двойственности: Если формулы F и U равносильны, то и двойственные им формулы F* и  U* также равносильны.

Если, применяя к формуле F дистрибутивные преобразования на основании первого дистрибутивного закона, мы получим формулу U, то переход от двойственной формулы F* к  U* осуществляется на основании второго дистрибутивного закона.

Принцип двойственности применяют для нахождения новых равносильностей, что  позволяет почти в два раза сократить усилия на вывод тождеств, при рассмотрении свойств элементарных функций.

Логические функции.

Как известно, законы логики являются тождественно-истинными формулами (тавтологиями).

Логические функции могут зависеть от одной или более переменных в теоретико-множественном смысле, логическая функция от n переменных y=f(x1,x2,…,xn), представляет собой отображение множества наборов вида (x1,x2,…,xn), являющихся областью его определения, на множество её значений N=(a1,a2,…,ak).

Определение 3: Однородной называется функция, если её аргументы принимают свои значения из того же набора, что и сама функция.

Булевы функции одной переменной:

x

y1=f1(x)

y2=f2(x)

y3=f3(x)

y4=f4(x)

0

1

0

1

0

1

1

0

0

1

Функции y1=0, y2=1 –функции константы, так как не меняют своего значения при любых значениях аргумента; y4=x – равна своему аргументу, y3=x – инверсия или отрицание, т.к. принимает значение противоположное аргументу.

Число всех функций, зависящих от n переменных х1, х2,…, хn равно.

Булевы функции двух переменных:

x1

0

0

1

1

обозначение

название

чтение

x2

0

1

0

1

y0

0

0

0

0

0

константа 0

любое 0

y1

0

0

0

1

,

конъюнкция

x1 и x2

y2

0

0

1

0

\

отрицание импликации

x1, но не x2

y3

0

0

1

1



повторение первого аргумента

как x1

y4

0

1

0

0

\

отрицание обратной импликации

не x1, но x2

y5

0

1

0

1



повторение второго аргумента

как x2

y6

0

1

1

0



сумма по модулю 2

x1не как x2

y7

0

1

1

1



дизъюнкция

x1 или x2

y8

1

0

0

0



стрелка Пирса

ни x1 ни x2

y9

1

0

0

1



эквиваленция

x1 как x2

y10

1

0

1

0



отрицание второго аргумента

не x2

y11

1

0

1

1



обратная импликация

если x2, то x1

y12

1

1

0

0



отрицание первого аргумента

не x1

y13

1

1

0

1



импликация

если x1, то x2

y14

1

1

1

0



штрих Шеффера

не x1, или не x2

y15

1

1

1

1

1

константа 1

любое 1

               

Методические указания

Для лучшего запоминания теоретического материала, изучите приведенные примеры.

Пример1: Применение принципа двойственности для нахождения равносильностей.

Используя дистрибутивность & относительно получаем равносильность:

Xi&(XjXk)(Xi&Xj)(Xi&Xj)  Xi(Xi&Xk)(XiXj)&(XiXk).

Пример 2: Доказать, что функция  G является тавтологией

G(x1,x2,x3)=()((

Решение: 

Пример 3: Является ли заданная функция сомодвойственной:

f(x1,x2,x3)=x1+x2+x3

Решение:  f*(x1,x2,x3)=fx1,x2,x3x1x2x3x1+x2+x3,

Следовательно f(x1,x2,x3)-сомодвойственна.

Контрольные вопросы

1. Какие формулы называются равносильными? Приведите примеры.

2. Какие формулы называются двойственными?

3. Сформулируйте закон двойственности. С какой целью его применяют?

4. Какая функция называется однородной?

  1.  Постройте таблицы истинности булевых функций для двух переменных.
  2.  Сколько всех функций, зависящих от n переменных?

Индивидуальные задания

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

2. Используя придуманное вами высказывание и полученную формулу, составьте двойственную ей формулу.

3. Применив эквивалентные преобразования, упростите приведённые формулы так, чтобы в результате получить только один атом:

  1.  ; 2)  3)  4)

5)  6)  

7)С

4. Упростите приведённые формулы, насколько это возможно:

1) С  11) С

2) С|  12) С

3) С  13) С

4) С|  14) С

5) С 15) 

6) С|С  16) С

7) СС  17) СС

8) С  18) С|

9)   19) С|

10) С  20) С.

21) СС       

22) С   

23) С 

24) СВА

25) С   

26) СС

27) СС  

28) СС   

29) С

30) С.

5.  Для каждой из приведенных формул составьте двойственную ей формулу:

1) (AC; 2) C; 3) (A(CD))(AC);

4) ((CC))1.

6. Примените принцип двойственности к каждой из приведенных эквивалентностей:

1) AA; 2) A(BC)(AC; 3) A(A; 4) (A.

7.  Какая формула, содержащая только операции конъюнкции, дизъюнкции и отрицания (отнесены только к атомам), будет истинной тогда и только тогда, когда лишь одна  из трех переменных А, В и С  принимает значение «истина»?

Какое значение истинности примет при этом условии двойственная формула?

8. Какая формула, содержащая только операции конъюнкции , дизъюнкции и отрицания (отнесены только к атомам), будет истинной тогда и только тогда, когда лишь две  из трех переменных А, В и С  истинны?

Будет ли истинной при этом двойственная формула?

PAGE  1


 

А также другие работы, которые могут Вас заинтересовать

37284. Система управления частоты вращения турбины построенная на центробежном датчике 1.06 MB
  2Система управления частоты вращения турбины построенная на центробежном датчике. На рисунке5 показана принципиальная схема системы управления скоростью вращения паровой турбины. Центробежный датчик создает механическое перемещение плунжера золотника зависящее от скорости вращения турбины Так как на выходе этого датчика сила и перемещение невелики то чтобы по лучить мощность достаточную для управления клапаном регулирующим расход пара к турбине его нужно усилить с помощью...
37285. МЕТОДИЧНІ ВКАЗІВКИ ПО ВИРІШЕННЮ ЗАДАЧ З МЕХАНИКИ ТА МОЛЕКУЛЯРНОЇ ФІЗИКИ 4.36 MB
  Кінематика поступального руху матеріальної точки Закон руху матеріальної точки вважається заданим якщо можна визначити положення точки в будьякий момент часу в даній системі відліку. Головна задача кінематики: знаючи закон руху точки визначити всі кінематичні величини які характеризують її рух. Зворотня задача кінематики: за кінематичними характеристиками руху визначити закон руху точки. В кинематиці закон руху точи задається одним з трьох способів.
37286. Автогенератор с автотрансформаторной обратной связью 815.67 KB
  Коэффициент обратной связи на резонансной частоте 8. Поэтому коэффициент обратной связи оказался независимым от частоты что справедливо при относительно невысоких частотах в половину меньших граничной частоты транзистора. С повышением частоты схема замещения автогенератора усложняется и коэффициент обратной связи должен рассматриваться с учетом перечисленных факторов. Амплитуда генерируемых колебаний определяется из уравнения баланса амплитуд Регулировка амплитуды колебаний производится изменением величины коэффициента обратной...
37287. Особенности ведения и учета налога на прибыль бюджетными организациями 432.5 KB
  Налоговый учет осуществляется для формирования полной и достоверной информации о порядке учета для целей налогообложения хозяйственных операций, осуществленных налогоплательщиком в течение отчетного (налогового) периода, а также обеспечения информацией внутренних и внешних пользователей для контроля за правильностью исчисления, полнотой и своевременностью исчисления и уплаты в бюджет налога.
37288. Расчеты сметы затрат на проектирование сегментов локальной вычислительной сети в здании ГВЦ ОАО НЛМК 175.5 KB
  Организуется автоматизированный документооборот электронная почта создаются различные массивы управленческой коммерческой и другой информации общего назначения и персонально используются вычислительные ресурсы всей сети а не только отдельного компьютера. Таким образом решится проблема окупаемости и рентабельности внедрения корпоративной сети. С внедрением на предприятии компьютерного оборудования и подключением к глобальной сети Internet организация получает практически неограниченные информационные возможности оперативное получение...
37289. Бюджетно-финансовая политика 141 KB
  Государственные финансы – это все финансовые средства государственных организаций. Они включают в себя государственный бюджет и внебюджетные денежные фонды, которые находятся в ведении государства (пенсионный фонд, фонд социального страхования, фонд обязательного медицинского страхования).
37290. Влияние копинг-поведения на уровень эмоционального выгорания медицинских сестер 234.71 KB
  Изучить феномен психического выгорания как социально-психологическую проблему; подобрать диагностический инструментарий; выявить особенности эмоционального выгорания медицинских сестер с различным типом копинг-поведения; разработать программу тренинга по формированию навыков снятия эффекта эмоционального выгорания.
37291. ПРИВОД ЛЕБЕДКИ 3.8 MB
  Привод лебедки. Целью курсового проекта по дисциплине Детали машин и основы конструирования является приобретение первых инженерных навыков по расчётам и конструированию деталей и узлов машин на основе полученных теоретических знаний.