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


 

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

51905. Кредитно – денежная система. Монетарная политика 48.5 KB
  Функции центрального банка: разработка и реализация денежно кредитной политики; эмиссия и изъятие денег из обращения; хранение золотовалютных резервов страны; выполнение кредитных и расчётных операций для правительства; контроль за деятельностью коммерческих банков и т. функция замещения наличных денег кредитными операциями. Процесс создания денег. Денежный мультипликатор Предложение денег на денежном рынке увеличивается или уменьшается в результате деятельности коммерческих банков за счет так называемых кредитных денег.
51906. Психологический анализ урока 38 KB
  В ходе анализа рассматривается насколько урок соответствует уровню подготовки учащихся и их интеллектуальному развитию. Анализируются психологическая природа усвоения учебного материала развития интеллектуальной активности обучаемых в учебном процессе соответствие приемов и способов работы возрастным и индивидуальнопсихологическим особенностям учащихся. критерии Психологическая цель урока: 1 проектирование развития учащихся в пределах изучения конкретного учебного предмета и конкретного урока; 2 учет в целевой установке урока...
51911. Финансовые отношения предприятия с бюджетом 44 KB
  Налоги это обязательные платежи взимаемые государством с юридических и физических лиц в государственные или местные бюджеты. По методу установления налоги подразделяются на: Косвенные налоги устанавливаемые в виде надбавки к цене или тарифу НДС акцизы. Прямые налоги устанавливаются на доход или имущество налогоплательщика. В зависимости от органов власти устанавливающих налоги выделяют: 1 Государственные это налоги которые разрабатывает правительство и которые зачисляются в центральный или местные бюджеты налог на прибыль на...