Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Равносильные формулы алгебры логики





Равносильность формул будем обозначать знаком º, тогда запись означает, что формулы А и В равносильны.

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

,

xÚxºx,

(xÙ ) Úyºy.

Тавтологией, или тождественно истинной, называется формула, принимающая значение 1 при всех значениях входящих в нее переменных.

Тождественно истинные формулы:

xÚ ,

xÉ(xÉy).

Тождественно ложной называется формула, принимающая значение 0 при всех значениях входящих в нее переменных.

Тождественно ложная формула: хÙ .

Между понятиями равносильности и эквивалентности существует следующая связь: если формулы А и В равносильны, то формула А « В — тавтология, и об­ратно, если формула А« В — тавтология, то формулы А и В равносильны.

Важнейшие равносильности алгебры логики можно разбить на три группы:

основные равносильности;

равносильности, выражающие одни логические операции через другие;

равносильности, выражающие основные законы алгебры логики.

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

Равносильные преобразования используются для доказательства равносильности, для приведения формул к заданному виду, для упрощения формул.

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

Основные равносильности

 

 

Равносильности, выражающие одни логические операции через другие

 

 

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

Дальнейшее исключение логических операций невозможно. Так, если мы будем использовать только конъюнкцию, то уже такая формула, как отрицание х, не мо­жет быть выражена с помощью операции конъюнкции.

Однако существуют операции, с помощью которых может быть выражена любая из пяти логических операций, которыми мы пользуемся. Такой операцией являет­ся, например, операция Штрих Шеффера. Эта операция обозначается символом | и определяется следующей таблицей истинности:

x y x|y

 

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





Дата добавления: 2014-01-03; Просмотров: 588; Нарушение авторских прав?


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


Рекомендуемые страницы:

Читайте также:
studopedia.su - Студопедия (2013 - 2020) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление
Генерация страницы за: 0.002 сек.