42421

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

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

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

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

Русский

2013-10-29

120.5 KB

28 чел.

Практическое занятие №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


 

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

2127. Основы экономики минерального сырья. Теория и практика 935.89 KB
  Факторы промышленной ценности месторождений полезных ископаемых. Роль распределения минеральных ресурсов в земной коре. Сырье для топливно-энергетического комплекса. Факторы предложения нефтяного сырья. Факторы спроса угольного сырья. Цены на урановое сырье. Проблемы экономики уранового сырья.
2128. Автоматизовані системи наукових досліджень (АСНІ) 907.68 KB
  Формальне визначення системи. Методологічні відмінності на рівні змінних і параметрів. Системи даних з нечіткими каналами спостереження. Особливості переходів, залежно від властивостей параметричної множини. Системи із станами, що змінюються. Дослідження і проектування за допомогою АСНІ.
2129. Симметричные вибраторы как специфические виды антенн 2.51 MB
  Распределение тока на симметричном вибраторе. Симметричный вибратор с емкостной нагрузкой на концах. Распределение напряжения по симметричному вибратору. Поле излучения симметричного вибратора. Резонансная длина вибратора. Основные методы настройки симметричных вибраторов.
2130. Анализ деятельности рельсобалочного цеха (РБЦ) ОАО МК 1.14 MB
  Проверка мощности главных двигателей стана. Сортамент готовой продукции цеха и исходной заготовки. Краткая характеристика основного и вспомогательного оборудования цеха. Расчет усилия прокатки при прокатке швеллера. Технологический процесс производства фасонных профилей из заготовки проката.
2131. Теорія та методологія географічної науки 3.84 MB
  Сучасні інформаційні технології як людський капітал. Прикладне і конструктивне значення географічних знань. Дискретні форми географічного простору. Субстанційний, реляційний і конвенціальний час.
2132. Предмет и задачи биофизики как науки. Ее теоретические аспекты 3.54 MB
  Методы биофизических исследований. Искусственные липидные мембраны. Кинетика процессов переноса, происходящих с преодолением потенциального барьера. Пассивный транспорт веществ через биологические мембраны. Испускание энергии атомами и молекулами. Модель мышечного сокращения Дещеревского.
2133. Бегуны для переработки кусковых, порошкообразных и волокнистых материалов 186.87 KB
  Общие требования к курсовому проектированию по механическому оборудованию предприятий строительной индустрии. Конструкции и принцип действия бегунов. Области рационального использования.
2134. Валковые агрегаты для измельчения и переработки материалов 213.28 KB
  ОБЩИЕ ТРЕБОВАНИЯ К КУРСОВОМУ ПРОЕКТИРОВАНИЮ ПО МЕХАНИЧЕСКОМУ ОБОРУДОВАНИЮ ПРЕДПРИЯТИЙ СТРОИТЕЛЬНОЙ ИНДУСТРИИ. КОНСТРУКЦИЯ И ПРИНЦИП ДЕЙСТВИЯ. РАСЧЕТ ОСНОВНЫХ ПАРАМЕТРОВ.
2135. Машины для перемешивания материалов. Смесители периодического действия 226.55 KB
  Расчет основных параметров смесителей периодического действия. Смесители периодического действия для перемешивания жидких масс. Лопастные и горизонтальные смесители. Гравитационные бетоносмесители циклического типа. Бетоносмесители планетарные.