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


 

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

12579. Метод определения критической температуры Тк давления Рк для СО2 по появлению и исчезновению мениска 106.06 KB
  ВВЕДЕНИЕ Исследование критического состояния вещества необходимо не только с прикладной точки зрения но имеет и большое теоретическое значение. Особенности поведения вещества вблизи критической точки системы жидкостьпар определенным образом характеризуют структу
12580. Фармацевтический холокост - концлагерь для человечества 503.5 KB
  Прима Андрей Фармацевтический холокост концлагерь для человечества Смертельные болезни и препаратыубийцы АЗТ 2007г. Поводом к написанию этой книги послужили реальные события недавнего времени произошедшие с её и автором. Жизненная ситуация с которой он ст
12581. ИССЛЕДОВАНИЕ ХОЛОКОСТА. Глобальное видение 2.15 MB
  ИССЛЕДОВАНИЕ ХОЛОКОСТА. Глобальное видение. Материалы международной Тегеранской конференции 1112 декабря 2006 года. Минск ЗАО Христианская инициатива 2007 Исследование холокоста Глобальное видение. Материалы международной Тегеранской к
12582. Холокост. Общие сведения 402 KB
  ХОЛОКОСТ Реферат Холоко́ст англ. holocaust термин под которым сионистская пропаганда понимает систематическое уничтожение по заранее разработанному плану Германией и её союзниками в ходе Второй Мировой войны всех евреев только за то что они евреи. Теория холокост
12583. Освенцим: мифы и факты 41.55 KB
  Освенцим: мифы и факты Марк Вебер Почти всякий слышал об Освенциме на Западе Освенцим называется Аушвиц примеч. перев. немецком концентрационном лагере 2й Мировой войны где как утверждается были истреблены массы заключенных главным образом евреев в газовых кам
12584. М. Вебер Холокост: нужно выслушать обе стороны 34.42 KB
  М. Вебер Холокост: нужно выслушать обе стороны Почти каждый слышал что немцы убили во время Второй мировой войны шесть миллионов европейских евреев. Американское телевидение кино газеты и журналы постоянно муссируют эту тему. В столице США Вашингтоне построен огр...
12585. Опровержение холокоста 122.5 KB
  ОПРОВЕРЖЕНИЕ ХОЛДОКОСТА Холокост от англ. holocaust из др.греч. ὁλοκαύστος всесожжение жертвоприношение у евреев при котором жертва животное полностью пожиралась огнем: дегенераты зачемто мучили бедных животных. Для того чтобы сжечь 6 шесть млн. всем имевшим...
12586. Музей Холокоста 28.5 KB
  Музей Холокоста Музей Холокоста в Вашингтоне округ Колумбия предлагает своим посетителям увидеть вспомнить и вновь пережить трагедию. Холокост это массовое убийство еврейского народа нацистами во время Второй мировой войны который жил в Германии и в других европей...
12587. Почему я не верю в холокост 1.18 MB
  Почему я не верю в холокост Я перестал верить в холокост изза того что сочинители этого мифа считают меня идиотом постоянно пытаясь выдать за правду несуществующие и невероятные факты. Давно обратил внимание что во всей теории холокоста в какую историю не ткни в...