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


 

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

27010. Реляционные языки 95.5 KB
  Например составьте список все студентов со средним баллом превышающим 4 σSRBAL 4STUDENT Проекция операция над одним отношением. Например создать список среднего балла студентов с указанием атрибутов FIO NGR SRBAL ПFIONGRSRBALSTUDENT.Получить список номеров читателей которые в срок не сдали книги 6.Получить список книг которые ни разу не брали читатели 8.
27011. Построение запросов с использованием обобщающих функций 86 KB
  Таблица 3: onum номер заявки amt сумма заявкиodate дата cnum номер покупателя snun номер продавца Чтобы найти сумму на которую сделаны заявки: SELECT SUMamt FROM Orders; Подсчитать число продавцов имеющих заказы: SELECT COUNTDISTINCT snum FROM Orders; Результат: 5. Подсчитать количество читателей имеющих отчество Иванович Подсчитать количество книг которое числится за каждым читателем Отыскать читателя который взял максимальное число книг. Подсчитать общее число экземпляров книг издательства Мир Подсчитать...
27012. Создание и использование представлений 77 KB
  Введение в представления. В отличии от них представления это таблицы которые содержат данные других таблиц. В действительности представления это запросы выполняемые всякий раз когда представление является объектом команды. Например: CREATE VIEW СотрудникиМН AS SELECT FROM СОтрудники WHERE №отд = ‘О2; В результате создается представление СотрудникиМН с этим представлением можно выполнять любые операции то есть формировать запросы удалять вставлять соединять с другими таблицами и представлениями.
27013. Учет расчетов с подотчетными лицами 14.51 KB
  В бухгалтерском учете операции с подотчетными лицами отражаются следующими проводками: 1 выдан аванс на командировочные расходы: Дебет счета 71 Расчеты с подотчетными лицами Кредит счета 50 Касса; 2 отражены расходы по найму жилого помещения без учета НДС: Дебет счета 44 Расходы на продажу Кредит счета 71 Расчеты с подотчетными лицами; 3 учтена сумма НДС уплаченная за найм жилого помещения: Дебет счета 19 Налог на добавленную стоимость по приобретенным ценностям Кредит счета 71 Расчеты с подотчетными лицами; 4 возврат...
27014. Учет вложений в нефинансовые активы 15.97 KB
  Учет операций по вложениям в объекты основных средств нематериальных непроизведенных активов при их приобретении в том числе в сумме затрат связанных с выполнением научноисследовательских опытноконструкторских технологических работ отражается по дебету соответствующих счетов аналитического учета счета 010600000 Вложения в нефинансовые активы 010611310 010613330 010631310 010632320 с кредитом соответствующих счетов аналитического учета счета 010700000 Нефинансовые активы в пути 010711310 010731310 в случае приобретения объектов...
27015. Документальное оформление, оценка и учет отгрузки (отпуска) и продажи продукции, работ и услуг покупателям и заказчикам. Аналитический и синтетический учет отгрузки и реализации продукции 22.19 KB
  Аналитический и синтетический учет отгрузки и реализации продукции.Учет готовой продукции осуществляется в количественных и стоимостных показателях. Оценка готовой продукции ГП учитывается по фактическим затратам связанным с ее изготовлением по фактической производственной себестоимости включающей затраты связанные с использованием в процессе производства ос сырья материалов топлива энергии трудовых ресурсов и других затрат на производство продукции.
27016. Система нормативного регулирования бюджетного учета 14.8 KB
  Система нормативного регулирования бюджетного учета Бухгалтерский учет упорядоченная система сбора регистрации и обобщения информации в денежном выражении об имуществе обязательствах организаций и их движении путем сплошного непрерывного и документального учета всех хозяйственных операций. Бюджетный учет представляет собой упорядоченную систему сбора регистрации и обобщения информации в денежном выражении о состоянии финансовых и нефинансовых активов и обязательств Российской Федерации субъектов Российской Федерации и муниципальных...
27017. Анализ состояния и использования ОФ 18.16 KB
  Анализ состояния и использования ОФ Задачами анализа состояния и эффективности использования основных производственных фондов являются: установление обеспеченности предприятия и его структурных подразделений основными фондами соответствия величины состава и технического уровня фондов потребности в них; выяснение выполнения плана их роста обновления и выбытия; изучение технического состояния основных средств и особенно наиболее активной их части машин и оборудования; определение степени использования основных ...
27018. Аудиторские доказательства 13.93 KB
  Аудиторские доказательства Аудиторские доказательства это информация полученная аудитором при проведении проверки и результаты анализа указанной информации на которых основывается мнение аудитора. К аудиторским доказательствам относятся первичные документы и бухгалтерские записи являющиеся основой финансовой бухгалтерской отчетности а также письменные разъяснения уполномоченных сотрудников аудируемого лица и информация полученная из различных источников от третьих лиц. ОЦЕНКА Аудитор должен выбрать и выполнить уместные в рамках...